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
chjj has joined #bitcoin-wizards
EarlyGrey has quit [Quit: p fish]
Chris_Stewart_5 has quit [Ping timeout: 268 seconds]
eck has quit [Quit: poop]
ivan has joined #bitcoin-wizards
eck has joined #bitcoin-wizards
Dyaheon has quit [Ping timeout: 260 seconds]
Dyaheon has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
tromp has quit [Ping timeout: 240 seconds]
AaronvanW has quit [Remote host closed the connection]
AaronvanW has joined #bitcoin-wizards
deep-book-gk_ has joined #bitcoin-wizards
deep-book-gk_ has left #bitcoin-wizards [#bitcoin-wizards]
altoz has joined #bitcoin-wizards
d9b4bef9 has quit [Remote host closed the connection]
<kanzure>
merkle tree proof of nonmembership: if you show both sides of the tree and you have some rule about how merkle path is decided or how things are ordered, you only need to show a range of values at some point in the tree, to demonstrate that there's key X and key Z but not key Y in the merkle tree.
<kanzure>
(and also you would make a rule like a spend is only valid if the pubkey shows up in the right place in that merkle tree, and you have an inclusion proof)
<sipa>
yes
<kanzure>
oh did this scheme already exist
tromp has quit [Ping timeout: 268 seconds]
<sipa>
i'm sure it's been considered for utxo commitments at least since 2011
Aranjedeath has joined #bitcoin-wizards
Dyaheon has quit [Ping timeout: 268 seconds]
Dyaheon has joined #bitcoin-wizards
funkenstein_ has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 248 seconds]
tromp has quit [Ping timeout: 260 seconds]
BashCo has quit [Read error: Connection reset by peer]
BashCo has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
PRab has joined #bitcoin-wizards
Ylbam has quit [Quit: Connection closed for inactivity]
Chris_Stewart_5 has quit [Ping timeout: 240 seconds]
dnaleor has quit [Read error: Connection reset by peer]
blackwraith has quit [Ping timeout: 240 seconds]
NewLiberty has joined #bitcoin-wizards
uvarovserge has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
tromp has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
tromp has quit [Ping timeout: 240 seconds]
dnaleor has quit [Read error: Connection reset by peer]
legogris has quit [Remote host closed the connection]
legogris has joined #bitcoin-wizards
roidster has quit [Quit: ChatZilla 0.9.92 [SeaMonkey 2.40/20160120202951]]
AaronvanW has quit [Ping timeout: 240 seconds]
dnaleor has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
dnaleor has quit [Client Quit]
funkenstein_ has quit [Ping timeout: 260 seconds]
Murch has joined #bitcoin-wizards
CubicEarth has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
chjj has quit [Ping timeout: 246 seconds]
tromp has quit [Ping timeout: 240 seconds]
harrymm has quit [Remote host closed the connection]
harrymm has joined #bitcoin-wizards
HostFat has joined #bitcoin-wizards
CubicEarth has quit [Remote host closed the connection]
chjj has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
tromp has quit [Ping timeout: 260 seconds]
Aranjedeath has quit [Ping timeout: 246 seconds]
Murch has quit [Quit: Snoozing.]
tromp has joined #bitcoin-wizards
DrOlmer has quit [Ping timeout: 248 seconds]
DrOlmer has joined #bitcoin-wizards
Dyaheon has quit [Ping timeout: 240 seconds]
coredump_ has joined #bitcoin-wizards
Dyaheon has joined #bitcoin-wizards
coredump_ has quit [Ping timeout: 246 seconds]
coredump_ has joined #bitcoin-wizards
_whitelogger has joined #bitcoin-wizards
veleiro has left #bitcoin-wizards [#bitcoin-wizards]
chjj has quit [Ping timeout: 248 seconds]
coredump_ has quit [Ping timeout: 246 seconds]
coredump_ has joined #bitcoin-wizards
BashCo has quit [Read error: Connection reset by peer]
dnaleor has joined #bitcoin-wizards
BashCo has joined #bitcoin-wizards
BashCo has quit [Ping timeout: 276 seconds]
coredump_ has quit [Ping timeout: 246 seconds]
BashCo has joined #bitcoin-wizards
veleiro has joined #bitcoin-wizards
veleiro has left #bitcoin-wizards [#bitcoin-wizards]
blackwraith has joined #bitcoin-wizards
NewLiberty has quit [Ping timeout: 258 seconds]
prime_ has joined #bitcoin-wizards
chjj has joined #bitcoin-wizards
paveljanik has quit [Quit: Leaving]
blackwraith has quit [Ping timeout: 240 seconds]
TheSeven has quit [Ping timeout: 246 seconds]
laurentmt has joined #bitcoin-wizards
TheSeven has joined #bitcoin-wizards
coredump_ has joined #bitcoin-wizards
tiagotrs has joined #bitcoin-wizards
tiagotrs has quit [Changing host]
tiagotrs has joined #bitcoin-wizards
coredump_ has quit [Ping timeout: 246 seconds]
AaronvanW has quit [Ping timeout: 240 seconds]
Guyver2 has joined #bitcoin-wizards
dnaleor_ has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
dnaleor has quit [Ping timeout: 240 seconds]
dnaleor_ has quit [Ping timeout: 248 seconds]
dnaleor has joined #bitcoin-wizards
Ylbam has joined #bitcoin-wizards
Aaronvan_ has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 240 seconds]
dnaleor has quit [Quit: Leaving]
CheckDavid has quit [Quit: Connection closed for inactivity]
Aaronvan_ is now known as AaronvanW
<adlai>
in joinmarket, waxwing and belcher and i each (independently iirc?) came up with extensions of this for proving null set intersection, although the naive version gets a little expensive
<adlai>
s/in/for/, was just a discussion, not implemented yet.
<waxwing>
adlai: kanzure i'm a bit confused about the above, i seem to remember kanzure mentioning before the idea of ordering being used for this, but what's described above ^ i couldn't parse exactly.
<adlai>
kanzure: "some rule about how the merkle path is decided or how things are ordered" << how could these differ? the merkle path structure seems to me just another way of defining the ordering
thrmo has joined #bitcoin-wizards
<nsh>
adlai, any notes?
<nsh>
oh, i lost some lines. *reads logs*
BashCo has quit [Read error: Connection reset by peer]
BashCo has joined #bitcoin-wizards
Guyver2 has quit [Quit: Going offline, see ya! (www.adiirc.com)]
_whitelogger has joined #bitcoin-wizards
EarlyGrey has joined #bitcoin-wizards
prime__ has joined #bitcoin-wizards
prime_ has quit [Ping timeout: 255 seconds]
thrmo_ has joined #bitcoin-wizards
thrmo has quit [Ping timeout: 255 seconds]
deusexbeer has quit [Ping timeout: 246 seconds]
Belkaar_ has quit [Ping timeout: 240 seconds]
Belkaar has joined #bitcoin-wizards
Belkaar has joined #bitcoin-wizards
Belkaar has quit [Changing host]
deusexbeer has joined #bitcoin-wizards
thrmo_ is now known as thrmo
laurentmt has quit [Quit: laurentmt]
<kanzure>
waxwing: yes ordering is important. IIRC most of the previous constructions were about inclusion proofs, not non-inclusion proofs.
<kanzure>
adlai: i don't understand your question.
<waxwing>
yes sure, non-set-membership is the hard one. we were looking at doing it based on ordering, but it's kinda bloaty. i seem to recall researching zero knowledge proof of non-set-membership and .. getting confused, as usual :)
<waxwing>
hmm my vague memory is that things progressed after that, i'll check the IRC logs
<kanzure>
there we go, this is about right... "In this best case, only one branch and two leaf nodes must be revealed. In the worst case another branch of the tree must be revealed, revealing four leaf nodes. For proving 5 is not in the set:"
<waxwing>
part of the issue is that we didn't actually need 'proof of non-set membership' so much as 'proof of null intersection of *two* sets' for our particular use case
<waxwing>
i suspect when i said bloaty i was thinking of a later idea and confuddled them, the conversation was long and hasn't really finished anyway. so yes the 'bloaty' comment was not relevant, sorry.
<kanzure>
well at minimum it looks like the worst case non-membership proof could require very large other chunks of the tree to be given
CubicEarth has joined #bitcoin-wizards
pro has joined #bitcoin-wizards
<waxwing>
kanzure: i think the worst case is only 2 full branches, so 2 x the best case of one branch. so i *think* it's still just O(logN) and not bad? not sure, not very used to this stuff.
<waxwing>
heh. i'm new to this, seems the accumulator is partly what we were talking about, but with the additional thing of being able to update (add/delete)