sipa changed the topic of #bitcoin-wizards to: This channel 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
anon616 has quit [Remote host closed the connection]
anon616 has joined #bitcoin-wizards
jl2012 has quit [Quit: Connection closed for inactivity]
anon616 has quit [Remote host closed the connection]
meeh has joined #bitcoin-wizards
anon616 has joined #bitcoin-wizards
JackH has quit [Ping timeout: 252 seconds]
Ylbam has quit [Quit: Connection closed for inactivity]
veleiro has joined #bitcoin-wizards
Belkaar has quit [Ping timeout: 264 seconds]
Belkaar has joined #bitcoin-wizards
Belkaar has quit [Changing host]
Belkaar has joined #bitcoin-wizards
veleiro has quit [Ping timeout: 252 seconds]
Giszmo has quit [Ping timeout: 260 seconds]
anon616 has quit [Remote host closed the connection]
dabura667 has joined #bitcoin-wizards
rmwb has quit [Remote host closed the connection]
anon616 has joined #bitcoin-wizards
veleiro has joined #bitcoin-wizards
Giszmo has joined #bitcoin-wizards
Giszmo has quit [Ping timeout: 240 seconds]
Chris_Stewart_5 has quit [Ping timeout: 240 seconds]
rmwb has joined #bitcoin-wizards
dnaleor has quit [Ping timeout: 248 seconds]
dnaleor has joined #bitcoin-wizards
Murch has quit [Quit: Snoozing.]
dnaleor has quit [Quit: Leaving]
pro has quit [Quit: Leaving]
Giszmo has joined #bitcoin-wizards
bedeho has joined #bitcoin-wizards
tromp has quit [Read error: Connection reset by peer]
tromp has joined #bitcoin-wizards
jl2012 has joined #bitcoin-wizards
otoburb has quit [Quit: leaving]
rmwb has quit [Remote host closed the connection]
otoburb has joined #bitcoin-wizards
otoburb has quit [Client Quit]
otoburb has joined #bitcoin-wizards
otoburb has quit [Client Quit]
otoburb has joined #bitcoin-wizards
bedeho has quit [Remote host closed the connection]
bedeho has joined #bitcoin-wizards
d9b4bef9 has quit [Remote host closed the connection]
d9b4bef9 has joined #bitcoin-wizards
bedeho has quit [Remote host closed the connection]
veleiro has left #bitcoin-wizards [#bitcoin-wizards]
legogris has quit [Remote host closed the connection]
legogris has joined #bitcoin-wizards
execute has joined #bitcoin-wizards
TheSeven has quit [Ping timeout: 240 seconds]
TheSeven has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
jtimon has quit [Ping timeout: 248 seconds]
bedeho has joined #bitcoin-wizards
chjj has quit [Ping timeout: 248 seconds]
TheSeven has quit [Ping timeout: 246 seconds]
[7] has joined #bitcoin-wizards
koshii has quit [Ping timeout: 255 seconds]
bedeho has quit [Remote host closed the connection]
intcat has quit [Read error: Connection reset by peer]
afk11 has quit [Read error: Connection reset by peer]
arubi has quit [Read error: Connection reset by peer]
afk11 has joined #bitcoin-wizards
bedeho has joined #bitcoin-wizards
arubi has joined #bitcoin-wizards
harrymm has quit [Ping timeout: 246 seconds]
harrymm has joined #bitcoin-wizards
intcat has joined #bitcoin-wizards
Ylbam has joined #bitcoin-wizards
rmwb has quit [Remote host closed the connection]
irc88 has quit [Quit: (null)]
rmwb has joined #bitcoin-wizards
rmwb has quit [Remote host closed the connection]
rmwb has joined #bitcoin-wizards
koshii has joined #bitcoin-wizards
BashCo has quit [Remote host closed the connection]
tromp has quit [Remote host closed the connection]
rmwb has quit []
BashCo has joined #bitcoin-wizards
paveljanik has quit [Quit: Leaving]
Ruben has joined #bitcoin-wizards
RubenSomsen has quit [Ping timeout: 248 seconds]
JackH has joined #bitcoin-wizards
Ruben has quit [Ping timeout: 240 seconds]
laurentmt has joined #bitcoin-wizards
arubi has quit [Read error: Connection reset by peer]
afk11 has quit [Read error: Connection reset by peer]
intcat has quit [Write error: Connection reset by peer]
boing has quit [Read error: Connection reset by peer]
DougieBot5000 has quit [Read error: Connection reset by peer]
boing has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
DougieBot5000 has joined #bitcoin-wizards
Logicwax has quit [Ping timeout: 240 seconds]
coinsmurf has quit [Read error: Connection reset by peer]
harrigan has quit [Ping timeout: 240 seconds]
harrow has quit [Ping timeout: 240 seconds]
coinsmurf has joined #bitcoin-wizards
[d__d] has quit [Remote host closed the connection]
spinza has quit [Ping timeout: 240 seconds]
eck has quit [Ping timeout: 240 seconds]
harrow has joined #bitcoin-wizards
[d__d] has joined #bitcoin-wizards
execute has quit [Ping timeout: 240 seconds]
kjekac has quit [Ping timeout: 240 seconds]
afk11 has joined #bitcoin-wizards
harrigan has joined #bitcoin-wizards
intcat has joined #bitcoin-wizards
arubi has joined #bitcoin-wizards
Fistful_of_Coins has quit [Ping timeout: 255 seconds]
phantomcircuit has quit [Ping timeout: 255 seconds]
Fistful_of_Coins has joined #bitcoin-wizards
kjekac has joined #bitcoin-wizards
victorSN has quit [Ping timeout: 240 seconds]
eck has joined #bitcoin-wizards
Logicwax has joined #bitcoin-wizards
phantomcircuit has joined #bitcoin-wizards
afk11 has quit [Ping timeout: 248 seconds]
boing_ has joined #bitcoin-wizards
spinza has joined #bitcoin-wizards
JackH has quit [Read error: Connection reset by peer]
JackH has joined #bitcoin-wizards
boing has quit [Ping timeout: 248 seconds]
daszorz has joined #bitcoin-wizards
afk11 has joined #bitcoin-wizards
boing has joined #bitcoin-wizards
victorSN has joined #bitcoin-wizards
boing_ has quit [Ping timeout: 255 seconds]
vicenteH has joined #bitcoin-wizards
dabura667 has quit [Ping timeout: 248 seconds]
tromp has quit [Remote host closed the connection]
Ylbam has quit [Quit: Connection closed for inactivity]
tromp has joined #bitcoin-wizards
roconnor_ has quit [Ping timeout: 260 seconds]
dnaleor has joined #bitcoin-wizards
dnaleor has quit [Remote host closed the connection]
_whitelogger has joined #bitcoin-wizards
dabura667 has joined #bitcoin-wizards
c0rw1n_ has joined #bitcoin-wizards
harrow has quit [Quit: Leaving]
jtimon has joined #bitcoin-wizards
harrow has joined #bitcoin-wizards
StopAndDecrypt_ has quit []
deusexbeer has joined #bitcoin-wizards
StopAndDecrypt_ has joined #bitcoin-wizards
meeh has quit [Read error: Connection reset by peer]
roconnor_ has joined #bitcoin-wizards
adiabat has quit [Ping timeout: 240 seconds]
dnaleor has joined #bitcoin-wizards
c0rw1n_ has quit [Quit: Leaving]
c0rw1n_ has joined #bitcoin-wizards
pro has joined #bitcoin-wizards
leonidaz0r has joined #bitcoin-wizards
bedeho has quit [Remote host closed the connection]
tromp has quit [Remote host closed the connection]
bedeho has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
bedeho has quit [Remote host closed the connection]
leonidaz0r has quit [Ping timeout: 240 seconds]
dabura667 has quit [Remote host closed the connection]
dabura667 has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
dabura667 has quit [Remote host closed the connection]
tromp has joined #bitcoin-wizards
dabura667 has joined #bitcoin-wizards
dabura667 has quit [Remote host closed the connection]
dabura667 has joined #bitcoin-wizards
dabura667 has quit [Remote host closed the connection]
veleiro has joined #bitcoin-wizards
veleiro has left #bitcoin-wizards [#bitcoin-wizards]
Pilfers has quit [Ping timeout: 246 seconds]
null_radix has quit [Ping timeout: 255 seconds]
veleiro has joined #bitcoin-wizards
Guyver2 has joined #bitcoin-wizards
Pilfers has joined #bitcoin-wizards
veleiro has quit [Quit: Leaving.]
null_radix has joined #bitcoin-wizards
meshcollider has quit [Quit: Connection closed for inactivity]
Chris_Stewart_5 has joined #bitcoin-wizards
daszorz has quit [Quit: Leaving]
jtimon has quit [Ping timeout: 240 seconds]
veleiro has joined #bitcoin-wizards
veleiro has quit [Ping timeout: 240 seconds]
smk has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
smk has quit [Ping timeout: 260 seconds]
newbie is now known as newbie--
WungFu has joined #bitcoin-wizards
eirlymoe is now known as heirlymoe
JackH has quit [Quit: Leaving]
kenshi84 has quit [Ping timeout: 248 seconds]
kenshi84 has joined #bitcoin-wizards
RubenSomsen has joined #bitcoin-wizards
boing_ has joined #bitcoin-wizards
boing has quit [Ping timeout: 255 seconds]
adiabat has joined #bitcoin-wizards
Murch has joined #bitcoin-wizards
dnaleor has quit [Quit: Leaving]
dnaleor has joined #bitcoin-wizards
BashCo has quit [Remote host closed the connection]
MaxSan has quit [Quit: Leaving.]
WungFu has quit [Ping timeout: 260 seconds]
kisspunch has quit [Ping timeout: 255 seconds]
kisspunch has joined #bitcoin-wizards
WungFu has joined #bitcoin-wizards
BashCo has joined #bitcoin-wizards
dnaleor has quit [Quit: Leaving]
WungFu has quit [Ping timeout: 260 seconds]
WungFu has joined #bitcoin-wizards
Guest51953 is now known as teslax
laurentmt has quit [Quit: laurentmt]
bedeho has joined #bitcoin-wizards
WungFu has quit [Ping timeout: 240 seconds]
bedeho has quit [Ping timeout: 252 seconds]
abpa has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 246 seconds]
Ylbam has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
Giszmo has quit [Ping timeout: 248 seconds]
Alina-malina has quit [Ping timeout: 240 seconds]
Giszmo has joined #bitcoin-wizards
kenshi84 has quit [Ping timeout: 248 seconds]
kenshi84 has joined #bitcoin-wizards
Alina-malina has joined #bitcoin-wizards
WungFu has joined #bitcoin-wizards
Alina-malina has quit [Changing host]
Alina-malina has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
kenshi84 has quit [Ping timeout: 260 seconds]
koshii has quit [Ping timeout: 264 seconds]
Emcy has joined #bitcoin-wizards
Emcy_ has quit [Ping timeout: 248 seconds]
kenshi84 has joined #bitcoin-wizards
jb55 has joined #bitcoin-wizards
koshii has joined #bitcoin-wizards
abpa has quit [Read error: Connection reset by peer]
vicenteH has quit [Ping timeout: 255 seconds]
coinsmurf has quit []
c0rw1n_ has quit [Ping timeout: 248 seconds]
Emcy_ has joined #bitcoin-wizards
Emcy has quit [Ping timeout: 240 seconds]
Emcy has joined #bitcoin-wizards
Emcy_ has quit [Ping timeout: 264 seconds]
roconnor_ has quit [Ping timeout: 252 seconds]
coinsmurf has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy has quit [Ping timeout: 240 seconds]
Emcy has joined #bitcoin-wizards
koshii has quit [Ping timeout: 260 seconds]
Emcy_ has quit [Ping timeout: 240 seconds]
jb55 has quit [Ping timeout: 240 seconds]
koshii has joined #bitcoin-wizards
jtimon has joined #bitcoin-wizards
RubenSomsen has quit [Ping timeout: 252 seconds]
maaku has joined #bitcoin-wizards
afk11 has quit [Remote host closed the connection]
<maaku>
empirical observation: the maximum number of branch hashes required to prove membership of any subset of the leaves of a tree of height N is (N + 1) / 2
afk11 has joined #bitcoin-wizards
<maaku>
does anyone know how to prove this?
<kanzure>
"tree of height N" what does that mean
<maaku>
A tree for which the maximum depth of any leaf is N
<maaku>
wait n/m I may have messed something up
Emcy_ has joined #bitcoin-wizards
<esotericnonsense>
maaku: eh? it has to be at least N.
<kanzure>
merkle tree inclusion proof size grows with depth but it should be constant growth
<maaku>
ookaay yeah that seemed too incredible to be true, hence my confusion. and it wasn't true as I was outputing the wrong value for N
<maaku>
so what was being observed is that to prove k-of-n requires max (n+1)/2 inner hashes for any k
<maaku>
which sounds more right, but I'm still interested in proving that
Emcy has quit [Ping timeout: 248 seconds]
<maaku>
(it's true up to k-of-26 by exhaustive testing)
<esotericnonsense>
what is 'k' in this context
<kanzure>
are these binary merkle trees
<maaku>
kanzure: yes
<kanzure>
(2n + c) where n = depth * hash length, and c = size of whatever content you're checking at the very end, right?
<sipa>
maaku: huh?
<sipa>
i think i'm misunderstanding the statement
<maaku>
esotericnonsense: for k=3,n=5, 3-of-5, that means proving 3 elements out of a balanced binary tree of 5 elements
<esotericnonsense>
right
<sipa>
if you have a balanced 1024-element tree, so N = 10, proving the inclusion of the first and last element requires 19 hashes, I believe
<esotericnonsense>
yeah, i don't understand how this (n+1)/2 can come about unless you're excluding the hashes of the elements themselves
<sipa>
even if you exclude them
<esotericnonsense>
choose an element at the 'bottom'
<maaku>
sipa: example: "n=8 max=4 1 14 64 112 64"" <-- for proving inclusion of various combinations of 8 keys, there is 1 combination that takes 0 inner hashes, 14 that take 1 hash, 64 that take 2 hashes, 112 that take 3 hashes, and 64 that take 4 hashes
<sipa>
can you explain what's wrong with my example?
<sipa>
19 > (10+1)/2
<esotericnonsense>
even just the 1 example breaks it
<maaku>
sipa: you're talking about what I mistakingly wrote first, not what I corrected it to
<sipa>
maaku: i must be misunderstanding your correction then
<sipa>
oh!
<sipa>
N is number of elements, not tree depth
<maaku>
the observation would be that for a 1024 element tree, the maximum number of hashes needed to prove inclusion of some subset of those hashes would be (1024 + 1) / 2 = 512 hashes
<esotericnonsense>
doh :P
<sipa>
interesting!
<esotericnonsense>
maaku: is that excluding the hashes themselves
<sipa>
so he's just talking about the proof size, not the amount of computation done to verify a proof
<maaku>
yes, it requires k+max hashes, k being the number of elements you are proving
<maaku>
to rebuild the root
Chris_Stewart_5 has quit [Ping timeout: 264 seconds]
<esotericnonsense>
unless i'm missing something the worst case seems trivial
<esotericnonsense>
you have your bottom level which has 1024 elements, you are given one from each branch at the bottom
<esotericnonsense>
so you need the other 512 (each branch at the bottom level you don't have)
<maaku>
sipa: those numbers above are a histogram of the various proof sizes for all thresholds over n keys
Emcy has joined #bitcoin-wizards
<maaku>
I was trying to see how many keys could be supported before proofs exceed push limitations of script
WungFu has quit [Ping timeout: 260 seconds]
<maaku>
and if that relationship holds, the answer is 31, maybe 30 because of other info in the proof
<esotericnonsense>
with 1023 your worst case is to have one from all the even sets (511) missing plus the standalone one (your subset contains the other 511)
<esotericnonsense>
sorry if my terminology is crap here, just visualizing it
<kanzure>
30 is ~2x over p2sh ya?
<esotericnonsense>
but once you've covered the even and odd case you can generalize from there
Emcy_ has quit [Ping timeout: 252 seconds]
<kanzure>
oh it's only for a single push
<sipa>
maaku: none of these problems exist when the merkle proof is not part of the script...
<maaku>
sipa: which would be a good reason to figure out the extent of these problems!
bedeho has quit [Remote host closed the connection]
bedeho has joined #bitcoin-wizards
<maaku>
esotericnonsense: yes that makes sense. it's not a rigorous proof but it primes my intuition
* esotericnonsense
is an (ex) physicist
<esotericnonsense>
we don't really do proof
<esotericnonsense>
:D
<esotericnonsense>
(I do often regret not studying mathematics)
<maaku>
actually I guess you can show that it is as bad or worse to have one of two children missing than to elide the branch entirely
<maaku>
then inductively the worst case would be as you describe, one of each pair at the bottom of the tree, plus one for the hanging-off odd element
<maaku>
cool, thanks :)
Emcy_ has joined #bitcoin-wizards
<sipa>
maaku: it's a very interesting property to know
Emcy has quit [Ping timeout: 240 seconds]
<gmaxwell>
maaku: thats what I previously believed the maximum was, I believe the worst case is where you have every other hash.
<gmaxwell>
and then have to provide its sibling hash.
<gmaxwell>
There was a question I ponded before related to this where, say you have a N element set, now you replicate it so it's 2N and permute the replica. And add a constraint that the verifier can traverse into one replica or another. By choosing the permutation correctly you can select one where the worse case in one tree is efficient in the other. So you've increased your minimum proof size by one, b
<gmaxwell>
ut I think you halve the maximum proof size.
<gmaxwell>
(with the permutation being all even elements then all odd elements)
<esotericnonsense>
i don't think you halve it
<esotericnonsense>
hard for me to write down what I believe to be a counterexample
bedeho has quit [Remote host closed the connection]
<esotericnonsense>
nah, it doesn't work. scratch that.
vicenteH has joined #bitcoin-wizards
Emcy has joined #bitcoin-wizards
WungFu has joined #bitcoin-wizards
bedeho has joined #bitcoin-wizards
Emcy_ has quit [Ping timeout: 240 seconds]
<esotericnonsense>
actually i see now.
<esotericnonsense>
it seems to me that you go from 1 + (N+1)/2 to 2 + (N+1)/4
<esotericnonsense>
where 1/2 correspond to the root hashes
<esotericnonsense>
can you continue to make tradeoffs with other permutations and push the min/max closer together?
laurentmt has quit [Quit: laurentmt]
Emcy_ has joined #bitcoin-wizards
<esotericnonsense>
ah, you don't have to include the second root hash in the worst case because it can be derived.
Emcy has quit [Ping timeout: 240 seconds]
<esotericnonsense>
(as the rule of using even/odd is defined).
<gmaxwell>
To halve the worst case again, you add two more copies of N, one does the even odd flip on the second to last level, and one does it on both that and the last level.
<gmaxwell>
at the expense of adding one more level to the best case.
<gmaxwell>
I believe.
<esotericnonsense>
very neat.
Emcy has joined #bitcoin-wizards
Emcy_ has quit [Ping timeout: 255 seconds]
bedeho has quit [Remote host closed the connection]
jb55 has joined #bitcoin-wizards
<gmaxwell>
maaku: this also is a reason that the scheme should not cap the number you pick but instead cap the maximum hashes, since with the above encoding you can make it so the maximum path is shorter than you'd expect.
abpa has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Quit: laurentmt]
MaxSan has joined #bitcoin-wizards
MaxSan has quit [Max SendQ exceeded]
MaxSan has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy has quit [Ping timeout: 240 seconds]
<maaku>
Right, push limits cap you to a 4-of-32 or 28-of-32, unless you do some trick as you say. But to do 26-of-32 you could prove 28-of-32 and then drop two of them.
<maaku>
Lots of little tricks to work around the edges.
Guyver2 has quit [Quit: Going offline, see ya! (www.adiirc.com)]
<esotericnonsense>
the first genuinely valid use case for my silly-large monitor has been to spreadsheet gmaxwell's ' with an N=16
<esotericnonsense>
*gmaxwell's 'halve it again' algorithm.
<esotericnonsense>
can't find the counterexample. :)
<esotericnonsense>
(i tried to do it on paper and ran out of space.)
Pr0t3us has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
WungFu has quit [Quit: Leaving]
Pr0t3us has quit [Quit: Leaving]
Chris_Stewart_5 has quit [Ping timeout: 240 seconds]
Pr0t3us has joined #bitcoin-wizards
Emcy has joined #bitcoin-wizards
Emcy_ has quit [Ping timeout: 252 seconds]
_whitelogger has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
Aaronvan_ has joined #bitcoin-wizards
Aaronvan_ has quit [Remote host closed the connection]
Emcy_ has joined #bitcoin-wizards
Aaronvan_ has joined #bitcoin-wizards
Emcy has quit [Ping timeout: 260 seconds]
AaronvanW has quit [Ping timeout: 252 seconds]
dnaleor has joined #bitcoin-wizards
dnaleor has quit [Ping timeout: 240 seconds]
chjj has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 240 seconds]
dnaleor has quit [Ping timeout: 240 seconds]
dnaleor has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
meshcollider has joined #bitcoin-wizards
kenshi84 has quit [Ping timeout: 248 seconds]
kenshi84 has joined #bitcoin-wizards
kenshi84 has quit [Read error: Connection reset by peer]