17:59 UTC

< September 2017 > Su Mo Tu We Th Fr Sa 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

- Console
- #amber
- #apicula
- #arm-graphics
- #arm-netbook
- #bitcoin-wizards
- #buildbot
- #bundler
- #cinch
- #coiniumserv
- #coiniumserv-dev
- #crystal-lang
- #cubieboard
- #datamapper
- #discferret
- #elliottcable
- #forth
- #glasgow
- #gridcoin
- #gridcoin-dev
- #homecmos
- #huawei-g300
- #imx6-dev
- #imx6-dongle
- #ipfs
- #jruby
- #libreelec
- #libreoffice-ru
- #lima
- #linux-amlogic
- #linux-exynos
- #linux-rockchip
- #linux-sunxi
- #lisp
- #litex
- #logarion
- #lowempire
- #maemo-leste
- #maglev-ruby
- #microrb
- #milkymist
- #mirage
- ##moved_to_libera
- #mutant
- #nanoc
- #neo900
- #nextbsd
- #nmigen
- #ocaml
- #opal
- ##openfpga
- #openwrt-devel
- #panfrost
- ##panfrost-offtopic
- #Paws
- #Paws.Nucleus
- #picolisp
- #ponylang
- #prjmistral
- #pypy
- #qaul.net
- #qi-hardware
- #racket
- #radxa
- #reasonml
- #river
- #rom-rb
- #rubinius
- #ruby
- #ruby-core
- #rubygems
- #rubygems-aws
- #rubygems-trust
- #ruby-lang
- #ruby-rdf
- #sandstorm
- #scopehal
- #skywater-pdk
- #slime
- #soletta
- #stellar
- #stellar-dev
- ##stm32-rs
- #symbiflow
- #systemtap
- #teamhacksung
- #teamhacksung-support
- #tinyqma
- #videocore
- #wallaroo
- #xiki
- #xtompp
- ##yamahasynths
- #yosys
- #zig

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

<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

<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

<kanzure>
(2n + c) where n = depth * hash length, and c = size of whatever content you're checking at the very end, right?

<maaku>
esotericnonsense: for k=3,n=5, 3-of-5, that means proving 3 elements out of a balanced binary tree of 5 elements

<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

<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

<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

<sipa>
so he's just talking about the proof size, not the amount of computation done to verify a proof

<esotericnonsense>
you have your bottom level which has 1024 elements, you are given one from each branch at the bottom

<maaku>
sipa: those numbers above are a histogram of the various proof sizes for all thresholds over n keys

<maaku>
I was trying to see how many keys could be supported before proofs exceed push limitations of script

<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)

<maaku>
the code, fwiw : https://0bin.net/paste/lqO89q8Sjn4iJvTZ#uYl2sQJ-tocTAt0NYgN76uOX2hCZ6Q+QB2X/H25gXOT

<maaku>
esotericnonsense: yes that makes sense. it's not a rigorous proof but it primes my intuition

<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

<gmaxwell>
maaku: thats what I previously believed the maximum was, I believe the worst case is where you have every other 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

<esotericnonsense>
can you continue to make tradeoffs with other permutations and push the min/max closer together?

<esotericnonsense>
ah, you don't have to include the second root hash in the worst case because it can be derived.

<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>
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.

<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.