wumpus changed the topic of #bitcoin-wizards to: This channel is is for discussing theoretical ideas with regard to cryptocurrencies, not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja
chris13243 has quit [Ping timeout: 240 seconds]
ghtdak has quit [Quit: WeeChat 1.3]
Ylbam has quit [Quit: Connection closed for inactivity]
Graet has quit [Ping timeout: 255 seconds]
Graet has joined #bitcoin-wizards
b-itcoinssg has quit [Quit: Connection closed for inactivity]
<jtimon>
phantomcircuit: Bitcoin BT: only includes Boring Txanges that are more boring to review than the name of the banch itself but are obviously urgent if you are considering a 100 years lifetime for the project
<jtimon>
phantomcircuit: btw, do you know what xt stands for?
<gmaxwell>
you found the XKCD 5 random words survey is a great source of brainwallet passwords?
<ryan-c>
check that brainwallet construction out
<ryan-c>
so i did the math on it, and it's *super* gpu friendly because he didn't understand what he was doing.
<gmaxwell>
ah amazing like that.
<ryan-c>
the main part of it can be broken up into 16384 threads each needing 8MB of ram
<ryan-c>
the beginning/end is up to 64 1MB threads
AlphaTech has joined #bitcoin-wizards
<gmaxwell>
Did you ever seen the original bitshares "memory hard POW"? been waiting to see a scam brainwallet based on that.
<ryan-c>
his "challenge wallet" got drained in less than two weeks.
<ryan-c>
also, it would appear that someone wrote a custom GPU cracker for his 0.5BTC
<gmaxwell>
ryan-c: So there are now people (more than one) that appear to be making a living writing GPU and FPGA engines for new altcoins and taking all their hashpower... so doing that for brainwallets doesn't seem surprising to me.
<gmaxwell>
sure 0.5 btc isn't a ton, but if there are no new vulnerable altcoins this week...
<ryan-c>
that's kinda cool
<ryan-c>
so i guess these people don't have to have a job because they just win at mining alt coins, and they have good gpu/fpga skills, and lulz?
Dizzle has quit [Quit: Leaving...]
<gmaxwell>
in any case, see my comment about xkcd? The xkcd guy is collecting a perfect set of priors for brainwallet cracking.
<gmaxwell>
ryan-c: right.
<ryan-c>
gmaxwell: oh, yes, the survey
AlphaTech has quit [Ping timeout: 268 seconds]
<ryan-c>
yeah, but probably not his intent
<gmaxwell>
hah no. still funny.
<ryan-c>
I want to know the % of people that responded with "five random words"
<ryan-c>
I put "chosen by fair die roll"
<gmaxwell>
Thats what I responded with.
<gmaxwell>
"five random words"
<gmaxwell>
SO responded with "random random random random random"
<gmaxwell>
or something like that.
<gmaxwell>
(I probably just deanonymized her survey)
<gmaxwell>
Apparently she put in actual random words than changed. I successfully guessed two of her words.
<ryan-c>
heh
dEBRUYNE has joined #bitcoin-wizards
<gmaxwell>
(the two I guessed were duck and refrigerator; I don't remember the other ones though I think I would have gotten all of them with 100 tries)
<ryan-c>
meat is an impressively poor random number generator
<gmaxwell>
Duck is the most random word.
<ryan-c>
TIL
<gmaxwell>
I expect it will be very highly ranked.
<ryan-c>
the java code cost me a sanity point, i don't recommend
NewLiberty has quit [Ping timeout: 250 seconds]
<midnightmagic>
I often wonder whether the existence of brainwallets puts all bitcoin users at some kind of non-negligible additional risk in places that don't mind throwing you in prison for an extended period of time for no particular reason.
<midnightmagic>
(re: $5 wrench comment in first pp on that URL)
<ryan-c>
midnightmagic: I think that most places that would be willing to do that would do it without bothering to come up with a pretense.
* midnightmagic
thinks about the US..
<ryan-c>
midnightmagic: Well, the most likely way in the US would be contempt.
<ryan-c>
midnightmagic: The "right to remain silent" should protect you unless they can convince a judge that it's a "foregone conclusion" that address X is a brainwallet that you have the passphrase for.
<midnightmagic>
No, I'm Canadian, I don't have rights when I visit the US.
<ryan-c>
if they show that, they can probably compel you (I use "you" here in the general sense, not to refer to anyone in particular) to divulge it under threat of being put in jail for contempt
<gmaxwell>
H. Beatty Chadwick is fun.
<ryan-c>
midnightmagic: what about fireduck?
<ryan-c>
gmaxwell: thank you, i was just googling to try to find his name
spinza has quit [Ping timeout: 244 seconds]
<ryan-c>
yeah, he got thrown in jail for *years* by a divorce court that claimed he was hiding money
AlphaTech has quit [Disconnected by services]
<ryan-c>
14 years
<ryan-c>
midnightmagic: has this fireduck guy been involved in other silliness?
AlphaTech_ has joined #bitcoin-wizards
bildramer has quit [Ping timeout: 250 seconds]
AlphaTech_ has quit [Disconnected by services]
mjerr has joined #bitcoin-wizards
nullbyte has quit [Ping timeout: 250 seconds]
AlphaTech_ has joined #bitcoin-wizards
nullbyte has joined #bitcoin-wizards
spinza has joined #bitcoin-wizards
chris13243 has quit [Ping timeout: 268 seconds]
<veleiro>
are we going to have any afternoon parties at the scalability conference?
dEBRUYNE has quit [Ping timeout: 265 seconds]
nullbyte has quit [Read error: Connection reset by peer]
nullbyte has joined #bitcoin-wizards
snthsnth has quit [Quit: leaving]
AlphaTech_ has quit [Ping timeout: 256 seconds]
Ylbam has joined #bitcoin-wizards
ebfull has joined #bitcoin-wizards
nullbyte has quit [Ping timeout: 244 seconds]
rusty has left #bitcoin-wizards [#bitcoin-wizards]
nullbyte has joined #bitcoin-wizards
bildramer has joined #bitcoin-wizards
tripleslash is now known as [\\\]
snthsnth has joined #bitcoin-wizards
nullbyte has quit [Ping timeout: 252 seconds]
CohibAA has quit [Remote host closed the connection]
nullbyte has joined #bitcoin-wizards
RoboTeddy has quit [Remote host closed the connection]
ThomasV has joined #bitcoin-wizards
trippysalmon has joined #bitcoin-wizards
RoboTeddy has joined #bitcoin-wizards
trippysalmon has quit [Ping timeout: 250 seconds]
ThomasV has quit [Ping timeout: 264 seconds]
snthsnth has quit [Ping timeout: 264 seconds]
ebfull has quit [Ping timeout: 244 seconds]
DougieBot5000_ has joined #bitcoin-wizards
DougieBot5000 has quit [Killed (hobana.freenode.net (Nickname regained by services))]
DougieBot5000_ is now known as DougieBot5000
ghtdak has quit [Quit: WeeChat 1.3]
gill3s has joined #bitcoin-wizards
deego has joined #bitcoin-wizards
veleiro has quit [Ping timeout: 250 seconds]
ebfull has joined #bitcoin-wizards
DougieBot5000 has quit [Quit: Leaving]
adam3us has quit [Quit: Leaving.]
rubensayshi has joined #bitcoin-wizards
damethos has joined #bitcoin-wizards
veleiro has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
NLNico has joined #bitcoin-wizards
priidu has joined #bitcoin-wizards
spinza has quit [Excess Flood]
spinza has joined #bitcoin-wizards
NLNico has quit [Ping timeout: 250 seconds]
NLNico has joined #bitcoin-wizards
moa has quit [Quit: Leaving.]
sparetire_ has joined #bitcoin-wizards
NLNico has quit [Ping timeout: 255 seconds]
ThomasV has quit [Ping timeout: 240 seconds]
NLNico has joined #bitcoin-wizards
nullbyte has quit [Ping timeout: 265 seconds]
ThomasV has joined #bitcoin-wizards
metamarc has joined #bitcoin-wizards
arubi has joined #bitcoin-wizards
melvster has quit [Ping timeout: 250 seconds]
gmaxwell has quit [Ping timeout: 246 seconds]
gmaxwell has joined #bitcoin-wizards
gmaxwell is now known as Guest36270
GAit has joined #bitcoin-wizards
melvster has joined #bitcoin-wizards
arubi has quit [Ping timeout: 240 seconds]
bedeho has quit [Ping timeout: 268 seconds]
Ylbam has quit [Quit: Connection closed for inactivity]
bedeho has joined #bitcoin-wizards
melvster has quit [Ping timeout: 244 seconds]
dEBRUYNE has joined #bitcoin-wizards
bedeho has quit [Ping timeout: 272 seconds]
melvster has joined #bitcoin-wizards
airbreather has joined #bitcoin-wizards
ThomasV has quit [Quit: Quitte]
harding has joined #bitcoin-wizards
King_Rex has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
warptangent has quit [Remote host closed the connection]
warptangent has joined #bitcoin-wizards
GAit has quit [Read error: Connection reset by peer]
GAit has joined #bitcoin-wizards
GGuyZ has joined #bitcoin-wizards
fuc has joined #bitcoin-wizards
fuc is now known as mrhodl
mrhodl has quit [Client Quit]
GGuyZ has quit [Quit: GGuyZ]
Ylbam has joined #bitcoin-wizards
Quanttek has joined #bitcoin-wizards
adam3us has joined #bitcoin-wizards
mrhodl has joined #bitcoin-wizards
AaronvanW has quit [Quit: Leaving]
AaronvanW has joined #bitcoin-wizards
davispuh has joined #bitcoin-wizards
binaryFate has joined #bitcoin-wizards
NewLiberty has joined #bitcoin-wizards
damethos has quit [Remote host closed the connection]
kang_ has joined #bitcoin-wizards
c0rw|zZz is now known as c0rw1n
afk11 has joined #bitcoin-wizards
davispuh has quit [Ping timeout: 264 seconds]
Emcy has quit [Read error: Connection reset by peer]
Emcy has joined #bitcoin-wizards
Emcy has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
hazirafel has joined #bitcoin-wizards
mrhodl has quit []
rubensayshi has quit [Read error: Connection reset by peer]
ufoinc__ has joined #bitcoin-wizards
rubensayshi has joined #bitcoin-wizards
hazirafel has quit [Ping timeout: 252 seconds]
ufoinc__ has quit [Ping timeout: 256 seconds]
paveljanik has joined #bitcoin-wizards
GGuyZ has joined #bitcoin-wizards
frankenmint has joined #bitcoin-wizards
arubi has joined #bitcoin-wizards
ASTP001 has joined #bitcoin-wizards
eudoxia has joined #bitcoin-wizards
Guyver2 has joined #bitcoin-wizards
Guyver2 has left #bitcoin-wizards [#bitcoin-wizards]
chris13243 has joined #bitcoin-wizards
NLNico_ has joined #bitcoin-wizards
NLNico has quit [Read error: Connection reset by peer]
chris13243 has quit [Ping timeout: 264 seconds]
Guest36270 has quit [Changing host]
Guest36270 has joined #bitcoin-wizards
Guest36270 is now known as gmaxwell
GGuyZ has quit [Quit: GGuyZ]
DougieBot5000 has joined #bitcoin-wizards
chris13243 has joined #bitcoin-wizards
NLNico_ has quit [Ping timeout: 240 seconds]
ghtdak has joined #bitcoin-wizards
NLNico_ has joined #bitcoin-wizards
nwilcox has joined #bitcoin-wizards
shen_noe has quit [Quit: Leaving]
Burrito has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 246 seconds]
NLNico_ has quit [Ping timeout: 252 seconds]
chris13243 has quit [Ping timeout: 244 seconds]
ThomasV has quit [Ping timeout: 240 seconds]
mkarrer_ has joined #bitcoin-wizards
mkarrer has quit [Read error: Connection reset by peer]
mkarrer_ has quit [Remote host closed the connection]
mkarrer has joined #bitcoin-wizards
chmod755 has quit [Remote host closed the connection]
ghtdak has quit [Quit: WeeChat 1.4-dev]
AaronvanW has joined #bitcoin-wizards
NLNico has joined #bitcoin-wizards
nwilcox has quit [Ping timeout: 268 seconds]
ASTP001 has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
chris13243 has joined #bitcoin-wizards
nullbyte has joined #bitcoin-wizards
ghtdak has joined #bitcoin-wizards
ghtdak has quit [Client Quit]
ghtdak has joined #bitcoin-wizards
ghtdak has quit [Client Quit]
NLNico has quit [Quit: Leaving]
ghtdak has joined #bitcoin-wizards
trippysalmon has joined #bitcoin-wizards
Dizzle has joined #bitcoin-wizards
nullbyte has quit [Ping timeout: 264 seconds]
hazirafel has joined #bitcoin-wizards
Dizzle has quit [Remote host closed the connection]
ThomasV has joined #bitcoin-wizards
hazirafel has quit [Read error: Connection reset by peer]
bedeho has joined #bitcoin-wizards
damethos has joined #bitcoin-wizards
gill3s has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
arubi has quit [Ping timeout: 260 seconds]
chris13243 has quit [Ping timeout: 252 seconds]
priidu has quit [Ping timeout: 268 seconds]
nullbyte has joined #bitcoin-wizards
adam3us has quit [Read error: Connection reset by peer]
afk11 has quit [Read error: Connection reset by peer]
estem has joined #bitcoin-wizards
<gmaxwell>
firebird_: thanks, I'd be surprised if the same observation wasn't made in prior stealth address discussions in bitcoin.
kmels has joined #bitcoin-wizards
<gmaxwell>
To save people time, when scanning transactions, the transaction contains the ephemeral public key R. You'd look for your address as P = H(aR)G + B where a is your viewing secret and B is your spending pubkey.
<firebird_>
I'm not sure it works the same way in Monero
<gmaxwell>
The paper suggests that you compute D = H(aR)G and then for each output perform a point subtraction to recover the apparent B.
bedeho has joined #bitcoin-wizards
<gmaxwell>
This lets you have many distinct spending private keys, with one scanning key. The advantage of doing so is that you don't have to do seperate ECDH work per spending private key.
<gmaxwell>
And the advantage of that is that if you're a webwallet you can tall customers apart.
<dEBRUYNE>
firebird_: Paging fluffypony to elaborate :P
<fluffypony>
dEBRUYNE: no we did something different
<fluffypony>
we have a third component, a short payment ID, that is optional and encrypted
<fluffypony>
(well, optionally encrypted)
<gmaxwell>
I think the complexity claim in the paper is bogus, It's staying it takes the complexity from Addresses * Txn to Addresses+Txn, but thats only true if you totally discount the point additions. The ECDH is probably only about (say) 20x slower than the point additions (as those adds will need a sqrt, a ge+gej, and a modular inversion), so I don't think it's reasonable to ignore them.
<fluffypony>
gmaxwell: agreed
<gmaxwell>
fluffypony: is the payment ID stuff adequate for web-ishwallets and such?
jack-jack has joined #bitcoin-wizards
<fluffypony>
gmaxwell: no, more for deposit-taking systems where they provide the payment ID to the payee, and then they're able to identify incoming transactions for that user
<gmaxwell>
Yea, so I think this is perhaps a worthwhile approach, but not amazing. :)
<fluffypony>
the one-viewkey-many-spendkeys idea for a webwallet is an interesting application of it
<fluffypony>
I don't see that they've realised that is even a possibility
<gmaxwell>
hahah
<fluffypony>
so well done gmaxwell, you've figured out a novel application of their scheme
<fluffypony>
that actually gives it value :-P
<gmaxwell>
I usually have to come up with an application for something in order to understand it.
<gmaxwell>
But indeed, they don't really seem to explicitly call that out.
<gmaxwell>
But you can give them a bit more credit, they might have been thinking it and just not communicated it really well.
<fluffypony>
I couldn't come up with an application for it, so I rejected it as pointless, but I was thinking in terms of a single user's wallet (in which case if you want separate "addresses" for fear of them being associated together you'd have to roll both keys)
rubensayshi has quit [Ping timeout: 240 seconds]
<fluffypony>
gmaxwell: nah, their conclusion: "Aggregate addresses is the solution that significantly improves Bytecoin transaction processing for services. This scheme is useful for all CryptoNote currencies as it drastically upgrades user experience and effectively depreciates Payment ID."
<jack-jack>
I'm sorry, joined I joined in the middle of the chat
<fluffypony>
jack-jack: you're forgiven
<jack-jack>
what's the novelty application that gmaxwell came up with?
<gmaxwell>
Okay I was slightly wrong on the above complexity is ECDH * Transactions + Sqrt,GeGej,Inv * Outputs + hashtable, OR it's ECDH * Transactions + Sqrt,GeGej,Fe * Outputs * Addresses. It is a complexity improvement over ECDH * Transactions * Addresses.
<fluffypony>
jack-jack: one lemon tree, but the tree doesn't know who owns individual lemons
<gmaxwell>
fluffypony: yea, I think its a dumb replacement for payment ID.
nullbyte has quit [Ping timeout: 244 seconds]
<gmaxwell>
It's not a complexity improvement over payment ID, but it may be a usability/security improvement of it.
<fluffypony>
yeah, which we achieved by first serializing the payment ID into the address, and then shortening + encrypting it
<fluffypony>
(because there's no difference between a 95-char address and a 150ish-char address
Dizzle has joined #bitcoin-wizards
<jack-jack>
150 chars is more than a tweet :)
<fluffypony>
heh heh
<fluffypony>
payment IDs are optional, and you can use OpenAlias in a tweet anyway :)
nullbyte has joined #bitcoin-wizards
ghtdak has quit [Quit: WeeChat 1.4-dev]
ghtdak has joined #bitcoin-wizards
<jack-jack>
and why including pid at all?
<gmaxwell>
oh their scheme has a privacy flaw.
<kanzure>
does it make sense to use pow for situations like "supernode with signing pool federated consensus has fraud proof showing fraud, network has to decide on alternative non-fraudulent signing pool, use pow to do a first-past-the-post election race for alternative signing pool for whole network to switch to"? this seems to fail for things like "oops the alternative signing pool/server supernode the network has picked doesn't actually have ...
<kanzure>
... the necessary capacity".
<kanzure>
(this is for "graceful recovery of catastrophic consensus failures, like an evil mining cartel or evil fraudulent supernode")
<gmaxwell>
Yea, privacy of their scheme is busted.
ASTP001 has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
<fluffypony>
jack-jack: to identify payments without the payee having to tell you the details of the transaction
<jack-jack>
gmaxwell: what do you mean?
<gmaxwell>
Lets imagine that there addresses with keys (a, B1), (a, B2), (a, B3) which are known to you. A transaction shows up on the network with two outputs P1 and P2 and you would like to test the hypothesis that the transaction pays B1 and B2.
<kanzure>
oh actually i guess it would be pretty hard to pick a machine that did not have the necessary capacity- even trash laptops these days can do 20k/sec transaction verification. but someone might have put up their arduino as an alternative :-)...
Dizzle has quit [Ping timeout: 240 seconds]
<gmaxwell>
So you check if P1 - P2 == B1 - B2 and if the relation holds, the transaction pays those two addresses. This is because P1 = B1 + D and P2 = B2 + D and the D (contribution of the ephemeral part) cancels under addition.
<gmaxwell>
I feel stupid to have not seen that immediately. :(
<gmaxwell>
Look right?
<fluffypony>
ah
<fluffypony>
pity
<ryan-c>
jack-jack: note that twitter allows tweets to contain 140 characters - which can be more than 140 bytes total
<gmaxwell>
This can be fixed, if the scheme does ECDH per output instead of per transaction. Even just the Hash. E.g. H(index||aR)G changing the complexities from O(transactions) to O(outputs)
<gmaxwell>
I guess I'll write a short little latex formated note so people will find my cryptanalysis credible. lol.
ASTP001 has joined #bitcoin-wizards
<ryan-c>
heh
<ryan-c>
it's funny how much more credible latex makes things
<gmaxwell>
hm. I created a directory called "crytponote.b" and it struck me how much that sounds like a virus name. :P
c0rw1n has quit [Read error: Connection reset by peer]
c0rw1n has joined #bitcoin-wizards
<jack-jack>
gmaxwell: > This can be fixed, if the scheme does ECDH per output instead of per transaction. Even just the Hash. E.g. H(index||aR)G changing the complexities from O(transactions) to O(outputs)
<jack-jack>
gmaxwell: actually, it is the way it is implemented
<jack-jack>
;)
<ryan-c>
gmaxwell: It looks like you're trying to write a ransomeware. Would you like help?
<jack-jack>
>> one-time public key P = H(r*A || n)*G + B
<gmaxwell>
jack-jack: That isn't what the paper describes. It also increases the computational complexity considerably, as it means a fixed basis multiply per output.
<jack-jack>
the number of output is also hashed
<fluffypony>
also lol @ 2012
<jack-jack>
however it was omitted both in original CN whitepaper and this one
CodeShark has joined #bitcoin-wizards
<jack-jack>
gj
<fluffypony>
by original you mean the fake v1 that had all the bits ripped out from v2 but left footnotes in that referred to non-existent sections?
<jack-jack>
by original I mean the whitepaper that allowed you to have a meaningful life :)
<jack-jack>
but that's not the point
<jack-jack>
finally, R is random
<jack-jack>
ah, nope comment on R is irrelevant in case of 1 tx
<jack-jack>
R is common, but considering output number being hashed, D's will be different for different outputs
c0rw1n is now known as greenbat
<jack-jack>
I should agree, this whitepaper messes up the things actually implemented. Here: "First, for each transaction, the derivation is computed: D = Hs(aR)G" should be "for each output".
<jack-jack>
But that's not an uncommon mistake, thanks for the feedback
<gmaxwell>
It can't say "for each output" because there is no output specific index anywhere.
trippysalmon has quit [Ping timeout: 250 seconds]
jojva has quit [Quit: Quitte]
<jack-jack>
yep, oversimplified
<jack-jack>
gmaxwell: >It also increases the computational complexity considerably, as it means a fixed basis multiply per output
<jack-jack>
that's actually what was stated: "As a result, the time it takes to process M outputs if there are N users is proportional to M + N, not M · N as with the naive approach"
<jack-jack>
gmaxwell: it should be as follows: "First, for each output, the derivation is computed: D = Hs(aR||n)G, where n is the index of the output in the transaction"
<gmaxwell>
D needs a subscript.
<gmaxwell>
If you're revising the paper, feel free to thank me for commentary.
<gmaxwell>
Dn = Hs(aR||n)G and Pn = Bn + Dn in the sender and Bn = Pn - Dn in the reciever. and lookup Bn in the hashtable.
Dizzle has joined #bitcoin-wizards
NewLiberty has quit [Ping timeout: 244 seconds]
greenbat is now known as c0rw1n
davispuh has joined #bitcoin-wizards
arubi has joined #bitcoin-wizards
<gmaxwell>
10:30 < xiphmont> I wonder if USB superposition implies that cellphones are quantum 1/2 spin devices and, if so, can they be entangled?
<gmaxwell>
10:33 < gnafu> How can they get entangled? They're wireless!
<gmaxwell>
10:56 < TD-Linux> spook action at a distance
damethos has quit [Quit: Bye]
ThomasV has quit [Ping timeout: 252 seconds]
<petertodd>
what's the current status of stuff like moxie for deterministic code execution? looks like there's moxie, ethereum vm, bitcoin script, and... ?
<petertodd>
"The TinyRAM architecture is a random-access machine designed to be a convenient tool for expressing the correctness of nondeterministic computations." <- _non_deterministic?!
<petertodd>
interesting definition they must be using
<petertodd>
presumably that's in relation to how the proofs hide stuff, or something :/
CodeShark has quit []
<petertodd>
kanzure: thanks
<kanzure>
was trying to convince andytoshi to infiltrate that group to see what's up (since it's local to him)
<petertodd>
heh
Quanttek has quit [Ping timeout: 264 seconds]
<petertodd>
I'm trying to figure out what's a reasonable recommendation to make to a client(s) about what direction to be going in for smartcontracts crud
<petertodd>
phantomcircuit: OTOH, I know of someone using the python isolation tools for this... I basically said I'd have to say in my security review that we're assuming there is no security, and they (fortunately!) agreed
<phantomcircuit>
ha
<petertodd>
tromp_: huh, never seen hawk before
jack-jack has quit [Quit: Page closed]
<tromp_>
and then there's Tezos and Tauchain...
<phantomcircuit>
petertodd, i would assume that most sandboxing mechanisms have some kind of time limit on execution
<phantomcircuit>
rather than a resource counter
<petertodd>
phantomcircuit: yeah, I think time/space limits are the way to go for engineering simplicity
<phantomcircuit>
which is bad
<phantomcircuit>
time restrictions are bad
<petertodd>
phantomcircuit: ah, yeah, wallclock time is very bad
<petertodd>
phantomcircuit: needs to be instruction "time"
<phantomcircuit>
yeah
bedeho has joined #bitcoin-wizards
GGuyZ has joined #bitcoin-wizards
chris13243 has quit [Ping timeout: 264 seconds]
nullbyte has quit [Ping timeout: 246 seconds]
nullbyte has joined #bitcoin-wizards
CodeShark has joined #bitcoin-wizards
<gmaxwell>
I found moxie when looking for something like tinyram. .. no code available for tinyram AFAIK, and moxie has pretty nice GCC support, and I heard LLVM/clang was in progress.
<gmaxwell>
phantomcircuit: non-determinstic just means that there can be non-public inputs.
veleiro has quit [Quit: Leaving.]
<phantomcircuit>
petertodd, ^
bedeho has quit [Ping timeout: 246 seconds]
<gmaxwell>
E.g. you can setup a transcript where you prove F(A,b) == True for some B. Tinyram itself does nothing to help you hide B, but its setup to not gratitiously inflate the size of the public data for schemes where you can hide inputs.
<petertodd>
gmaxwell: makes sense
<petertodd>
gmaxwell: I'm thinking for practical systems, we'll find the GCC support to be pretty useful
<gmaxwell>
And the circuit arithemetic implementing it is especially small, given that.
<gmaxwell>
petertodd: Yea "no shit".
<petertodd>
gmaxwell: heh :)
<gmaxwell>
petertodd: so there is a paper on doing interactive proofs for faithful execution on x86.
<petertodd>
gmaxwell: oh!
<gmaxwell>
(because some people like pain)
<petertodd>
gmaxwell: how do the proofs work?
<gmaxwell>
e.g. where you build a hashtree over the transcript and if multiple oracles disagree you do log() queries to find the point of first disagreement then you check that step and reject the bad oracle.
GGuyZ has quit [Ping timeout: 246 seconds]
<gmaxwell>
So it works so long as one oracle is honest.
<petertodd>
gmaxwell: right, sounds very useful
<gmaxwell>
as you'll eventually find the truthteller.
<petertodd>
gmaxwell: has anyone implemented anything like that for moxie? (how many moxie VM's are there? I think I just saw jgarzik's, and the qemu one
<gmaxwell>
No one has, it wouldn't be hard. the most tricky part is that you need to make the dram a hashtree.
<gmaxwell>
otherwise you can't compactly prove the result of a load instruction.
<petertodd>
gmaxwell: right, and that doens't sound hard to do (modulo speed)
<gmaxwell>
Fortuneately moxie has seperate load/store and no other instruction has access to anything but registers.
shen_noe has quit [Quit: Leaving]
<petertodd>
gmaxwell: right, sounds easy enough
<petertodd>
related question: how appropriate is moxie for a scriptPubKey replacement? (including for OpenPGP) Would you want to add some "system calls" for baked in sha256/ecc, etc?
Yoghur114 has joined #bitcoin-wizards
<gmaxwell>
It really needs crypto accelerators (thats what we'd likely call fixed function units for crypto if we were talking about some SOC)-- performing things like SHA256 directly in it has performance that probably makes it unusable without fancy jit stuff, which defeats some of the assurance purposes.
<gmaxwell>
(and they could easily be done safely and without compromising the assurances, I think).
<petertodd>
makes sense; has anyone done any prototypes of that?
<gmaxwell>
I have non-released stuff fussing around with it. Still unsure of the best way to handle it. I'm not sure if anyone has actually played with that.
<gmaxwell>
The prerhaps bigger issue as a scriptpubkey replacement is that the code is not very succinct.
c0rw1n has quit [Ping timeout: 244 seconds]
<gmaxwell>
It's less compact than x86, generally, and no comparison to Script for in-domain things.
firebird_ has quit [Quit: Page closed]
<gmaxwell>
e.g. see pieter's key tree stuff where the hashtree stuff is 6 bytes per level (and would be 8 bytes total, if Script had FOR/NEXT like HP RPN does)
adam3us has quit [Quit: Leaving.]
<petertodd>
yeah, already opcodes are at least 16bits for instance
<gmaxwell>
you obviously also need a setup to provide it access to useful data from the enclosing enviroment.
<petertodd>
basically some kind of well-defined memmapping - might be nice to adopt a standard function call style for that
<gmaxwell>
they also just do a lot less. which is good and even essential when targeting it with a C compiler. :)
<petertodd>
yup
<Eliel>
would it really need baked in opcodes? If you can define functions by hash of the function code, only one transaction ever needs to include the function itself and then implementations can then implement optimized versions of specific hashes for often used functions.
<gmaxwell>
Eliel: No, because the computational burden of an operation must be normative in a consensus system.
<gmaxwell>
E.g. a side effect of any function is updating the cycle counter, so...
<petertodd>
Eliel: that's an approach too, but needs a well-defined function call scheme, and as gmaxwell says, has consensus issues
<gmaxwell>
Eliel: what I was actually doing though, in my setup was handling the accelerators using function calls though. Because that made it easier to use standard moxie toolchain.
<petertodd>
gmaxwell: as though the function was calling memory that didn't actually exist?
<gmaxwell>
petertodd: yea, just in my accelerated version I intercepted the jump and switched to the replacement.
<gmaxwell>
but otherwise a native version could be used in a dumb machine (e.g. so gdb works) though the execution wasn't exactly identical.
chmod755 has joined #bitcoin-wizards
c0rw1n has joined #bitcoin-wizards
GAit has quit [Quit: Leaving.]
<Eliel>
also, for estimating the computational burden for a script. I think I'd approach it by requiring the script to specify an upper limit for itself, that could then be used for determining the transaction fee. You'd incentivize correct upper bounds by automatically failing the script if it violates it's own defined upper bound.
<gmaxwell>
in any case what I'd planned on accelerating was memcmp/memcmp/bzero/etc. along with hash functions, and ecc (for a couple high performance curves). I looked into pulling in all of GMP but it seemed like to much work to make certantly safe.
<petertodd>
gmaxwell: sounds like a decent way to handle it would be to basically pretend that part of memory existed, but for some reason couldn't be accessed by the actual code, and for debugging actually load that memory with code implementing the real thing
<gmaxwell>
Eliel: yep, absolutely-- discussed here before. Though you need to also ban peers that give you failing scripts (if you weren't already thinking that)
<petertodd>
gmaxwell: all sounds reasonable
<Eliel>
gmaxwell: well, that's only necessary for scripts with unusually high upper bounds.
<CodeShark>
unless we have conditional branching, is there ever a case where computational cost cannot be reasonably estimated simply by parsing?
<petertodd>
gmaxwell: one thing with smartcontract crud is you may have a situation where you want to basically be able to "call" another chunk of user-written code in a deterministic way, and have it either do the calculation fo rreal, or just return a cached answer
<petertodd>
gmaxwell: e.g. so you could split up some massive computation like... verify every transaction in a huge chain
<kanzure>
petertodd: there has been talk about embedding moxiebox interpreter called by opcode..
<gmaxwell>
CodeShark: nice unless there. technically we only need a grammer where computational cost is trivial to determine, but compiling general code to such systems is hard.
adam3us has joined #bitcoin-wizards
<petertodd>
the programming model in that case becomes nice and simple to the end user, whre they're just calling functions with names like VerifyTransaction()
<CodeShark>
in particular, looping on conditionals complicates cost evaluation...or makes it impossible to do so
<petertodd>
CodeShark: well, IMO cost though actual instructions executed is way simpler; our track record of doing otherwise is poor...
<gmaxwell>
CodeShark: cost can be easily and reliably measured by tracing.
<gmaxwell>
and you can abort at the limit.
<gmaxwell>
Basically the input is cost,script and yes, someone can send you an incorrect cost, but no less than they can just send you a correct cost but a script that is unsuccessful.
<gmaxwell>
in all cases the upper bound on computation must still be fairly low... though computation could be broken up as PT suggests.
<gmaxwell>
Normally you'd hide the computation from the network using the coinswap transformation.
<kanzure>
"just use a merklized abstract syntax tree to hide the actual computation, and tell everyone they better behave or else" doesn't work?
<gmaxwell>
(or the fancier bonded versions suggested by Ed Felten and his students)
<gmaxwell>
kanzure: sure but the threat has to be credible.
<gmaxwell>
You can't hide the computation when the network can't actually process it, or the threat is a dead letter.
adam3us has quit [Quit: Leaving.]
<kanzure>
excessive computation causes all outputs to go to fees? :-)
priidu has joined #bitcoin-wizards
<kanzure>
but yes i see your point
<gmaxwell>
kanzure: then I make an invalid spend of your coins that also does excessive computations.
<gmaxwell>
MOAR COINS FOR THE MINE GODS.
<jgarzik>
kanzure, fyi had no bandwidth for review - looks like gud stuf
mkarrer has quit []
adam3us has joined #bitcoin-wizards
mkarrer has joined #bitcoin-wizards
<kanzure>
jgarzik: thanks
erasmospunk has joined #bitcoin-wizards
blackwraith has joined #bitcoin-wizards
Guest89 has joined #bitcoin-wizards
priidu has quit [Ping timeout: 260 seconds]
<CodeShark>
if the computation can be broken up and smaller pieces verified and paid for individually it could work
<gmaxwell>
well for defined party contracts you can teach the network to perform the interactive protocol I gave above.
<gmaxwell>
and you bond performance.
<gmaxwell>
(by gave I mean cited)
<gmaxwell>
(and by cited I mean mentioned vaguely without giving enough information for you to actually find it)
<CodeShark>
lol
<gmaxwell>
(though I did say enough that you likely don't need the paper)
mountaingoat has quit [Remote host closed the connection]
<CodeShark>
speaking of which, I'm putting together a list of commitment structure proposals (UTXO commitments, fraud proofs, etc..) for Montreal. If anyone here would like to have their work included, please PM me
<gmaxwell>
CodeShark: make sure you check with the archivist.
<CodeShark>
it's for a presentation, gmaxwell
<CodeShark>
although perhaps it will end up becoming a publication
adam3us has quit [Quit: Leaving.]
<kanzure>
CodeShark: he means "make sure you ask kanzure for all the links about those things"
<CodeShark>
oh...ok :)
<kanzure>
CodeShark: asking people for links to their work is unfortunately never going to work
<CodeShark>
so do you have a list?
<kanzure>
yes... one sec.
Guest89 has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
<gmaxwell>
There is fraud proof discussion I had quite early in bitcoin-dev and on the mailing list I think... back before I realized that the bitcoin whitepaper mentioned them in the SPV section.
<CodeShark>
heh
<petertodd>
kanzure: thanks, but that should be on github :)
<gmaxwell>
Obviously there is that little table on that wiki page from me.
<kanzure>
petertodd: it is hard keeping 4000 links straight
eudoxia has quit [Ping timeout: 240 seconds]
hsmiths has joined #bitcoin-wizards
<CodeShark>
glad someone's doing this crucial task, kanzure :)
<CodeShark>
much appreciated - we really do need it
<kanzure>
CodeShark: my presentation is a review of all scalability proposals that have been made since 2009. if you have things that you think are in danger of being missed, please send them my way...
<CodeShark>
sure. and mine is on validation costs and incentives. ditto :)
SDCDev has quit [Read error: Connection reset by peer]
JayDugger1 has quit [Ping timeout: 244 seconds]
epscy has quit [Ping timeout: 244 seconds]
gwillen has quit [Ping timeout: 244 seconds]
Meeh has quit [Ping timeout: 244 seconds]
zxzzt has quit [Ping timeout: 244 seconds]
helo has quit [Ping timeout: 244 seconds]
jcorgan has quit [Ping timeout: 244 seconds]
petertodd has quit [Ping timeout: 244 seconds]
helo has joined #bitcoin-wizards
otoburb has quit [Ping timeout: 244 seconds]
helo has quit [Changing host]
helo has joined #bitcoin-wizards
Iriez has joined #bitcoin-wizards
JayDugger has joined #bitcoin-wizards
maraoz has joined #bitcoin-wizards
jcorgan has joined #bitcoin-wizards
jcorgan has quit [Changing host]
jcorgan has joined #bitcoin-wizards
Meeh has joined #bitcoin-wizards
SDCDev has joined #bitcoin-wizards
epscy has joined #bitcoin-wizards
otoburb_ has quit [Client Quit]
kang_ has joined #bitcoin-wizards
zooko has joined #bitcoin-wizards
<Taek>
kanzure, all: has there been any discussion on what happens if we discover that bitcoin will not scale beyond a certain point
chris13243 has joined #bitcoin-wizards
<Taek>
even the lightning network is not going to scale to 7 billion humans on 1mb blocks
<Taek>
assuming that 1mb is indeed a hard limit, and that lightning is the best we can do off-chain, what happens?
<kanzure>
you can use multisig pools for receiving cheap utxos on the blockchain in that circumstance
moa has joined #bitcoin-wizards
<Taek>
meaning multiple people sharing each utxo? Sounds trust-required
<kanzure>
i think you could make multisig "pools" more trustless
nullbyte has quit [Ping timeout: 250 seconds]
adam3us has quit [Quit: Leaving.]
<kanzure>
there might be a legitimate reason to think that the only transactions that should get committed are breach-remedy transactions, heh
nullbyte has joined #bitcoin-wizards
<kanzure>
anyway, if you really need to have extra data, you could always do the extension block idea, or auxiliary blocks plugged in via transactions that specify their existence or something, or sidechains that are either chains themselves with normal verification constraints or federated pools (which is almost very similar to "hrrr multisig pools") with signed blocks or signed ledgers..
<kanzure>
(although you don't have to immediately exit into utxos anyway)
Quanttek has joined #bitcoin-wizards
<TD-Linux>
moxie looks pretty awesome. though it seems clearly targeted toward hw implementation vs a software one
<gmaxwell>
the software impl is perfectly reasonable though.
adam3us has quit [Quit: Leaving.]
<kanzure>
Taek: some people are not going to understand bitcoin, no matter how amazing our software is, and persuading them to use bitcoin anyway without understanding safety implications might be unethical. so it's possible that not everyone is going to use bitcoin...
<phantomcircuit>
Taek, lightning (aka hash locked bidirectional micro payment channels configured into a network) are almost certainly not the best that we can do
<TD-Linux>
for an interpreter, yes. but I imagine that bitcoin wouldn't want to integrate a JIT...
<kanzure>
Taek: also in general it causes lots of angry users when they were told about certain features that turn out to be oops not true
<kanzure>
phantomcircuit: go on
<phantomcircuit>
kanzure, you already mentioned the obvious, probabilistic payments
<kanzure>
Taek: for example, advertising bitcoin as anonymous is *dangerous* to user safety and is *actively harmful*
<phantomcircuit>
for something like starbucks that receives a few million payments per day a 100,000x probability is reasonable
<kanzure>
yes i have not completely internalized those proposals yet
<gmaxwell>
TD-Linux: yea no, fair enough. When I say the software is good I mean its a switch statement that almost fits on your screen.
<gmaxwell>
TD-Linux: not that its fast or easy to make fast, I agree.
<phantomcircuit>
more so though there is good reason to believe that the payment channels in a lightning like setup can be rebalanced, thus allowing for channels to remain open indefinitely
<kanzure>
right
<kanzure>
phantomcircuit: has anyone looked at whether probabilistic payments + lightning or other payment channels works?
<phantomcircuit>
there is the obvious question there about how you keep bitcoin mining secure in such a scenario though
nullbyte has quit [Ping timeout: 272 seconds]
<phantomcircuit>
kanzure, i've not seen any discussion about combining the two approaches no
<kanzure>
well, the lightning network nodes might be miners
nullbyte has joined #bitcoin-wizards
<phantomcircuit>
kanzure, indeed they should be but unfortunately the current market indicates that those who should be miners dont seem to be
<phantomcircuit>
for example all of the exchanges should be mining even if only at 0.1-1% of the network levels
<kanzure>
is there a good link that i can use about this
<phantomcircuit>
(at 1% of the network you get to select the transactions in approximately 1 block every day)
otoburb has joined #bitcoin-wizards
adam3us has joined #bitcoin-wizards
GGuyZ has joined #bitcoin-wizards
<Taek>
phantomcircuit: if starbucks is receiving payments at 100,000x, doesn't that mean that some people are going to get slammed with a $XXX,XXX bill for their coffee cup?
adam3us has quit [Client Quit]
<kanzure>
"I doubt many want to risk paying much more than 100 times more than they bargained for."
<phantomcircuit>
Taek, they pool their money before hand
<Taek>
"So, to make that work, there would need to be a way for Alice to put that 1 BTC on hold for Bob's benefit, albeit only temporarily. This way, Alice can't swipe the coin out from under Bob, but on the other hand, Bob doesn't get to keep control of the coin if he doesn't receive a winning share after a certain amount of time." -> also seems like a hard problem
<phantomcircuit>
it's like the lottery
<phantomcircuit>
actually the mechanism would probably be the same as with micropayment channels
<phantomcircuit>
so potentially it's made irrelevant by them
<Taek>
yeah I've always assumed that probabilistic payments were approx. inferior to payment channels
<gmaxwell>
they make a different tradeoff.
<gmaxwell>
I expect they could be combined too, but maybe not much reason to do that.
<Taek>
what is the benefit to using probabilistic payments?
<gmaxwell>
When people start talking about micropayments-- true micropayments, like sub usd cent in value-- probablistic payments are probably most interesting.
<phantomcircuit>
gmaxwell, you'd need to combine funds into a single multisig with a mechanism to recover funds if someone disappears
<phantomcircuit>
which i suspect basically ends up looking like a super cumbersome micropayment channel
<gmaxwell>
phantomcircuit: nah, I posted PP schemes that I think work and give all interesting properties, including doublespend detection.
<gmaxwell>
I even had you add opcodes to elements-alpha to make them implementable!
<gmaxwell>
(thats why I wanted verifying signature data on the stack)
kang_ has quit [Quit: Page closed]
<phantomcircuit>
gmaxwell, yeah i know, but if you're doing very high odds you want to pool the risk with other users
<phantomcircuit>
100x is probably the highest that a single person is going to want to go
<gmaxwell>
Because you can prevent PP doublespend by having a bonded coin that can be redeemed/destroyed on presentation of a proof of two signatures with another key.
<phantomcircuit>
100x is obviously still very useful
<gmaxwell>
phantomcircuit: depends on the fee level.
<phantomcircuit>
well and i guess if it's sub cent payments it can be much higher
<phantomcircuit>
1000x on a 0.001 payment would be fine
<gmaxwell>
right. In any case, it's speculative if really tiny payments make _social_ sense, but I think we have the technology to make them reasonably efficient.
<Taek>
if you make the majority of your daily purchases using PP, it would seem reasonable to have a pool set aside of several thousand dollars to draw from.
<gmaxwell>
bigger hurdle is that many people really dislike payments with variance, on both the sending and recieving side.
<phantomcircuit>
gmaxwell, btw even with dbcache=4 the bottleneck on this rpi2 seems to be merkle tree root calculations
<phantomcircuit>
fScriptChecks = false and cpu saturated
<gmaxwell>
phantomcircuit: so leveldb wastes a ton of cpu on lookups, dunno why.
<gmaxwell>
so that might also be a factor for you.
<phantomcircuit>
gmaxwell, oh right, it's because it's bisecting the table files
<Taek>
re: tradeoffs, with PP you could pay any address, but with payment channels you don't have that flexibility
<phantomcircuit>
the table files are sorted and lookups within them are done by bisecting the file
<phantomcircuit>
and it's walking the journal file for each lookup which is O(n) (but hopefully with a small n most of the time)
<gmaxwell>
taek: networked channels mostly makes that a non-issue.
<gmaxwell>
Taek: the parties just need channels up to _someone_ and you do path finding and make a series of pairwise trades.
<phantomcircuit>
indeed the current designs call for onion routed payments to be the default
<gmaxwell>
like the original ripple system, but trading an asset rather than a debt so payment is guarenteed. :)
<phantomcircuit>
it's expected that the cost per payment will be so low that 5x increase for strong privacy will be a no brainer
<Taek>
gmaxwell: true, but that comes with implementation overhead, and if each pairwise trade is charging some sort of fee, you deal with fee overhead as well
CohibAA has quit [Remote host closed the connection]
<kanzure>
payment routing includes things like finding fee-optimal paths
zooko has quit [Ping timeout: 264 seconds]
<phantomcircuit>
Taek, people keep brining this up and suggesting it will make the network centralized, but it's expected the the cost will be so low that it wont have any effect
<gmaxwell>
Taek: illogical thinking, or actually if you think through there is a highly unethical argument burried in there; let me explain.
dEBRUYNE_ has joined #bitcoin-wizards
<phantomcircuit>
for example i intend to setup a hub as soon as it's possible and charge nothing
<phantomcircuit>
(not with lots of funds available of course, but still)
<kanzure>
re: the importance of paying to addresses, i don't think addresses are useful. they will die eventually...
<gmaxwell>
Taek: Lets imagine a transaction directly hits the bitcoin network. Then every node in the world and all future ones through history are _forced_ to transfer and process it if they want to participate. The total cost is considerable, though much of it is an externality.
dEBRUYNE has quit [Ping timeout: 255 seconds]
Guest89 has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
<gmaxwell>
Taek: now for the channel case, the similar per node costs are involved, but only for a few nodes, the total cost is much lower, and participation is voluntary.
<Taek>
kanzure: I don't understand 'they will die eventually...' ?
<CodeShark>
the term "bitcoin address" is a somewhat unfortunate misnomer...the parallel with, say, email (which is already used and understood by many) just isn't really there
<gmaxwell>
Taek: also, --- least cost routing network, so almost perfect competition... and fees would often be negative, due to channel rebalancing.
<kanzure>
Taek: bitcoin addresses are really just one particular standard for contracts; there's no reason to keep using those.
xabbix has quit [Ping timeout: 240 seconds]
RoboTedd_ has joined #bitcoin-wizards
<gmaxwell>
So the comparison about 'but won't participants in my payment want fees?' is saying "I don't want to pay the true price for processing my transaction in a highly efficient market, but I'd rather externalize a thousands of fold cost on other parties that have no real choice except to not run a bitcoin node at all"
tromp has joined #bitcoin-wizards
paveljanik has quit [Quit: Leaving]
<gmaxwell>
and keep in mind, there is no reason to assume the bitcoin transactions themselves will be free, the validation costs get externalized, but POW security costs are not.
Madars has quit [Ping timeout: 252 seconds]
kyuupichan has quit [Ping timeout: 244 seconds]
Madars has joined #bitcoin-wizards
<Taek>
gmaxwell: from a purely utilitarian perspective, the cost of using networked channels is (setup + routing fees)*# of payments
jgarzik has quit [Read error: Connection reset by peer]
<Taek>
in a PP setup, the cost is (txn fee)*(# of payments)*(probability of payment)
chris13243 has quit [Ping timeout: 264 seconds]
jgarzik has joined #bitcoin-wizards
jgarzik has quit [Client Quit]
zooko has joined #bitcoin-wizards
<CodeShark>
the cost of routing transactions for a relatively tiny percentage of all transactions taking place is also relatively tiny compared to the cost of focing everyone in the world to have to validate each transaction
jgarzik has joined #bitcoin-wizards
<Taek>
wrt the ethical problem, I'm not really sure how to answer that. I usually assume (perhaps incorreclty) that at some point the blockchain will be constantly 100% full
<gmaxwell>
Taek: no, setup + routing*payments.
RoboTeddy has quit [Ping timeout: 264 seconds]
<Taek>
oh right
erasmospunk has quit [Ping timeout: 244 seconds]
Logicwax has quit [Ping timeout: 244 seconds]
tromp_ has quit [Ping timeout: 250 seconds]
<phantomcircuit>
Taek, i keep saying "is expected to be" but really the cost of payment routing will be virtually zero
<gmaxwell>
but setup can be disregarded, assuming its widely used, everyone will have channels setup already. And PP assumes a linear utility for money, ... you want your paycheck via a PP? :P
<CodeShark>
we already pay for routing via ISPs
<CodeShark>
imagine if someone were insisting the Internet should be a flood network instead :p
<kanzure>
comparisons to internet architecture are not useful; internet is terrible architecture.
<Taek>
CodeShark: I don't think that's a valid comparison. You can't exactly do 'probabilistic packets'
<kanzure>
(i'm just upset about someone using an argument about "peering agreements" on me.. bleh.)
<CodeShark>
the point isn't to tout the merits of current Internet architecture, kanzure - but to point out how much worse it could be
jeremyrubin has quit [Ping timeout: 268 seconds]
ASTP001 has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
erasmospunk has joined #bitcoin-wizards
<CodeShark>
as much as I dislike the centralized nature of ISPs and resource allocation, I'd rather pay my ISP than have to wade through every single message everyone everywhere on the Internet broadcasts
<Taek>
you'd still have to get the messages from an ISP?
<CodeShark>
no, you could just use shortwave radio or something :p
<fluffypony>
CodeShark: someone told me on Reddit a few days ago that in "5-7 years everything will be decentralised"
<fluffypony>
all I could think about is message-passing everyone's stupid media downloads
<CodeShark>
well, decentralization doesn't have to mean flood networks
<gmaxwell>
nice timing re ISPs comment and #bitcoin
<CodeShark>
I'm thinking more of an ad-hoc mesh network where routing services can be provided by anyone
erasmospunk has quit [Ping timeout: 246 seconds]
adam3us has joined #bitcoin-wizards
<CodeShark>
you could still do stupid media downloads...but it won't be free (although it might very well be cheaper than current ISPs)
<Taek>
I have a hard time thinking about fair-cost models for a payment routing network, but it does seem to me like 'free' routing would be dangerous for the router
xabbix has joined #bitcoin-wizards
<gmaxwell>
CodeShark: usually transfer stunts like that very much do not work. Last mile bandwidth is enomrously more expensive (in physical terms) than datacenter bandwidth.
<Taek>
if there's a lot of traffic going a particular direction on the network, you could have all of your channels drained in that direction
<Taek>
and then you need to somehow find a way to rebalance
<gmaxwell>
Taek: no need for 'the router'
<gmaxwell>
Taek: you rebalance by offering negative fees to move in the other direction.
<Taek>
right, but you can only afford negative fees if you were charging positive fees in the first place
<gmaxwell>
(or zero fees if you're not that desperate)
<gmaxwell>
Taek: what no!
<Taek>
ok what did I miss?
chris13243 has joined #bitcoin-wizards
<kanzure>
your negative fees can be subsidized upstream
<gmaxwell>
Taek: there is a channel from me to you, and I've paid you all the coins in it, so all the coins are on your side now. Later someone wants to route through me to reach codeshark, they could come via andytoshi to me, but I'd rather move some of the taek-gmaxwell channel back to me, so I offer negative fees that way, even though I never connected any fees before.
<gmaxwell>
(and it's totally reasonable for me to do this, since rebalancing the channel saves me fees in the future-- e.g. the fees I'd have closing and establising a new channel)
<gmaxwell>
s/connected/collected/
<Taek>
I still having trouble visualizing a whole network doing this, but I think that only makes sense in a limited scope.
erasmospunk has joined #bitcoin-wizards
zooko has quit [Ping timeout: 272 seconds]
<Taek>
Let's we have a network where everyone is connected to K and nobody else
<Taek>
and for whatever reason, today a bunch of payments are going to G, so K's channel to G gets drained
Emcy has quit [Ping timeout: 260 seconds]
<Taek>
K knows that in the future he's going to need to make more payments to G, so now he needs to re-fill that channel
<Taek>
unless there are more random processes that help reset it, the channel is stuck without some form of encouragement
<gmaxwell>
Yes, indeed, though thats an uninteresting and degenerate topology.
<Taek>
hmm.
<Taek>
perhaps so. Was just trying to create something easier to reason about
<kanzure>
the point is that negative fees are a form of fee competition so that your negative fees are selected over competing alternatives
<gmaxwell>
what you said so far is true, but it's a problem with the topology. If you imagine several stars, e.g. K1,K2,K3 and each user is connected to two of them.. then you can start seeing how things work.
<gmaxwell>
(though even stars are kind of degenerate at all, but that topo is enough to see all the behaviors I'm talking about)
Newyorkadam has joined #bitcoin-wizards
<Taek>
do you mind explaining further?
<CodeShark>
you're basically rewarding people for replenishing your channel
<CodeShark>
so you don't have to renegotiate one
<gmaxwell>
now when K1->G ends up all on G's side, zero or negative fees going the order way creates a reason for someone on K3 paying someone on K1 to use the K3->G->K1->X route.
<CodeShark>
you offer a route that, while not necessarily the most efficient, helps replenish your channel
<CodeShark>
and rewarding people for using it
<Taek>
CodeShark: I understand that, but the only reason your channel is depleted in the first place is that *other people* were using it.
<Taek>
*presumably for free
<CodeShark>
?
<CodeShark>
why would you presume that?
<gmaxwell>
Taek: no-- your software would charge fees for transactions that moved channels in ways they don't like, and pay fees for transactions that move channels in ways they like.
Dizzle has quit [Quit: Leaving...]
<Taek>
gmaxwell: oh. Somehow I thought we were assuming that fees were going to be 0 to move money around.
<kanzure>
fees can be zero for as long as you have a positive balance on the channel
chris13243 has quit [Ping timeout: 244 seconds]
<gmaxwell>
Taek: for any given transaction they may be-- if you can find a route whos rebalance you can help.
<Taek>
gmaxwell: certainly, though I would expect on-average you'd wind up paying relatively small fees, and in proportion to the volume of money
<gmaxwell>
Basically you can imagine it like this, there is a cost to reset channels. channel fees should amortize that cost fairly across all the users that exploit the channel.
<Taek>
yeah that makes sense
<gmaxwell>
thats why you have to think of a more complex topology than a hub/spoke or you can't see those effects and there is little to no shared amoritization.
<CodeShark>
ad-hoc mesh networks :)
bedeho has joined #bitcoin-wizards
<CodeShark>
a "hub" is just a regular node that offers routing services
Guest89 has joined #bitcoin-wizards
<gmaxwell>
because you'd like to minimize your costs every participant should be a 'hub'.
<gmaxwell>
otherwise you have no oppturnity to get other people to rebalance your channels.
<kanzure>
also every lightning network node should randomly start up new channels with very small balances with random other nodes, and then increase the channel balance over time once the node has proven trustworthy
<kanzure>
because random network growth has many privacy advantages and other effects
<CodeShark>
yes, resistant to partitioning
<CodeShark>
as well
<Taek>
being a hub means greater setup costs, and if the average participant has more connections it means the overall network is more expensive (in terms of block space)
Guest89 has quit [Client Quit]
<CodeShark>
we want to avoid having, say, two huge cliques linked only by a single link :)
zooko has joined #bitcoin-wizards
<Taek>
of course, that makes that link very powerful
<kanzure>
Taek: hubness setup costs are what?
<Taek>
you have to put a transaction on the blockchain for every link you establish
<gmaxwell>
Taek: it doesn't mean greater setup costs.
<gmaxwell>
consider, _eventually_ your channel will deplete. And you must setup again. Now if you do _no_ rebalancing, two channels will take twice as long to deplete as one (assuming equal value and uniform usage).
<Taek>
I wish I understood without needing it to be spoon-fed to me lol
<gmaxwell>
But having two up at one means you can prolong your channels by rebalancing.
<CodeShark>
the cost of the anchor transaction can be negotiated between the two parties
<CodeShark>
and might have something to do with risk metrics
<gmaxwell>
and indeed, someone else can pay that setup cost if doing so helps their rebalancing.
<Taek>
gmaxwell: I see. You'd want to optimize for the total number of channels that get created over time, which includes channels that need to be refreshed.
<gmaxwell>
Yup.
bedeho has quit [Remote host closed the connection]
<gmaxwell>
and rebalancing can have a huge effect, increasing the lifetime manyfold.
instagibbs_ has joined #bitcoin-wizards
jeremyrubin has joined #bitcoin-wizards
RoboTedd_ has quit [Remote host closed the connection]
mjerr has quit [Ping timeout: 272 seconds]
<Taek>
Ok. I'm now trying to reason about the fundamental limitations of such a system. Let's assume that there exists some magic configuration which guarantees perfect rebalancing at 3 connections per participant
<Luke-Jr>
gmaxwell: why would my channel deplete? O.o
<Luke-Jr>
as long as I'm paid more than I spend, I wouldn't expect that.
<Taek>
The network grow linearly over time limited by the blockchain size
<Taek>
You'd still need to refresh channels any time that someone had a change in their total network
<Taek>
*networth
<gmaxwell>
Luke-Jr: 'deplete' means unbalance.
<Luke-Jr>
ok
<instagibbs_>
Taek: or open another channel, no?
<CodeShark>
wouldn't it be possible for multiple parties to negotiate opening up a clique with a single anchor transaction?
* Luke-Jr
will need to go over Rusty's latest stuff to learn the new terms :p
<gmaxwell>
Luke-Jr: Channels obey conservation of coins. A 10 BTC channel always has 10 BTC into it, but it's 'depleted' when the 10 BTC is all owned by one side or the other.
<gmaxwell>
well I dunno if rusty used depleted, thats how I think of it. :P
<Taek>
instagibbs_: yeah, same idea. You need another transaction to represent that your gains/losses have reached the limits of your channels
<instagibbs_>
This is all really fascinating.
erasmospunk has quit [Ping timeout: 265 seconds]
<Taek>
So then when there is networth fluidity on the network, it prevents new people from joining
<instagibbs_>
But another channel seems superior most times, since again, your open channels are + value
<Taek>
also interesting to think that the human population grows exponentially (or device population, if devices start doing their own blockchain things_
<gmaxwell>
allow me to introduce you to the friendly but stern logistic function.
<gmaxwell>
Human population doesn't grow exponentially. :P
<Taek>
instagibbs_: Yeah seems like there's no reason to completely close a channel ever.
<gmaxwell>
at least not the population on earth!
erasmospunk has joined #bitcoin-wizards
<instagibbs_>
Taek: well under attack scenario you need to close out more. more $$$ to settle
<instagibbs_>
other than that it's hard to imagine
Logicwax has joined #bitcoin-wizards
<Taek>
gmaxwell: historically it grew exponentially no? You are just pointing out that there is a physical limit to the # of humans that fit on the planet?
<gmaxwell>
Right.
<gmaxwell>
(and we're actually within spitting distance of current best esimates of it! at least in exponential growth terms)
<CodeShark>
we could easily stick the entire world's population into the grand canyon...but most would probably starve pretty quickly
<gmaxwell>
yes, this was assuming people staying alive. :P
<gmaxwell>
not turning them into some kind of bizarre meat-moon.
chris13243 has joined #bitcoin-wizards
chris13243 has quit [Read error: Connection reset by peer]
Guest89 has joined #bitcoin-wizards
<Taek>
interesting
<zooko>
☺
<Taek>
Assuming that the human population stops at 10 billion, and that the average lifespan is 100 years
<Taek>
and that there's approx. no net flow of networth
<Taek>
and that each human needs exactly 2 channels to keep their channels alive indefinitely
<Taek>
you end up at 6 tps
<instagibbs_>
That's the kind of napkin math we need.
<instagibbs_>
;)
RoboTeddy has joined #bitcoin-wizards
<Taek>
That's why I'm here :)
<gmaxwell>
you're going to need more dimensions to make that cow any more spherical.
<gmaxwell>
But yea, it's impressive the gains you can get.
hazirafel has quit [Ping timeout: 246 seconds]
<gmaxwell>
I can get you something like 11 tps in 1mb with a soft fork, incidentally. just by changing to BLS signatures. (not saying that 1mb is a reasonable limit in such a world... but it's amusing)
<kanzure>
meat-moon isn't as difficult as it may sound
<kanzure>
strangely, those two documents share some authors despite being written 30 years apart
erasmospunk has joined #bitcoin-wizards
<kanzure>
"the other stuff that ralph merkle is up to"
<phantomcircuit>
gmaxwell, i've had people argue that my assertion that IBD scales O(n^2) with O(n) block increase is false because there is a limit to the size of block you can construct due to merkle tree construction being O(n log n)
<phantomcircuit>
which is just comical as fuck
<phantomcircuit>
something something cubic blocks
chmod755 has quit [Quit: Ex-Chat]
<kanzure>
er, then what is merkle tree construction actually limited towards?
<gmaxwell>
phantomcircuit: you can show them pieter's code, it happily builds trees that are 2^26 in size and such. of course the tree doesn't get any wider if your transactions just get fat instead of numerous.
<gmaxwell>
kanzure: in pieter's new code the MT construction uses log2(entries) memory and takes time roughly equal to sha2d-ing the data twice.
<kanzure>
cool
<gmaxwell>
so you could build a tree over all the atoms in the universe with a ordinary desktop, no problem, if were patient enough to hash the universe twice.
<phantomcircuit>
kanzure, it is actually O(n log n) but i've written code that does 300k append operations per second in O(log n) space so realistically the O(n log n) limit is like
<phantomcircuit>
huge
<kanzure>
for the record i am not patient enough to hash the universe twice
<gmaxwell>
phantomcircuit: it's not n log n. it's n*2.
<gmaxwell>
efficient MT contruction is linear time.
<phantomcircuit>
gmaxwell, each append is O(log n) but for the current n value, oopsies
<kanzure>
i wonder if we should have someone do a "here's some common scaling laws and graphs of common curves to consider when we complain about scaling"
<kanzure>
"this part of the graph is where all lobsters on the planet can have 2 transactions per millenia"
<kanzure>
er, *do a presentation about
eudoxia has quit [Quit: Leaving]
chris13243 has joined #bitcoin-wizards
<gmaxwell>
phantomcircuit: not so. You defer work and ripple up.
<phantomcircuit>
hmm yeah
<phantomcircuit>
it's log n worst case
<phantomcircuit>
O(1) best case
<phantomcircuit>
yeah you're right
<gmaxwell>
it's really just N*2 hashes total for efficient software I promise.
<phantomcircuit>
yeah i can see why now
airbreather has quit [Remote host closed the connection]
erasmospunk has quit [Ping timeout: 264 seconds]
Newyorkadam has quit [Remote host closed the connection]
instagibbs_ has quit [Quit: Page closed]
zooko has quit [Ping timeout: 246 seconds]
Quanttek has quit [Read error: Connection reset by peer]
chris13243 has quit [Read error: Connection reset by peer]
<gmaxwell>
m offering a 5 BTC bounty for the first discovered substantive (e.g. invalidates the integrity of the proof) difference due to a transcription error between the implementations of secp256k1_gej_* and their sage replicas.