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]
oneeman has joined #bitcoin-wizards
d9b4bef9 has joined #bitcoin-wizards
roidster has quit [Ping timeout: 240 seconds]
Murch has quit [Quit: Snoozing.]
tromp has joined #bitcoin-wizards
uvarovserge has joined #bitcoin-wizards
tromp has quit [Ping timeout: 240 seconds]
Murch has joined #bitcoin-wizards
cluckj has joined #bitcoin-wizards
Murch has quit [Ping timeout: 268 seconds]
dnaleor has joined #bitcoin-wizards
roidster has joined #bitcoin-wizards
dnaleor has quit [Ping timeout: 255 seconds]
uvarovserge has quit [Quit: Textual IRC Client: www.textualapp.com]
uvarovserge has joined #bitcoin-wizards
oneeman has quit [Quit: Leaving]
pro has quit [Quit: Leaving]
dnaleor has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
veleiro has joined #bitcoin-wizards
<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 :)
<kanzure> how bloaty is bloaty?
<waxwing> yeah i forget the scaling
<kanzure> THANKS
<waxwing> hey, i'm going to try to look it up :)
<waxwing> i don't know if this represented the last steps of our thinking, we were discussing it a bit, but this was belcher's first steps at least: https://gist.github.com/chris-belcher/eb9abe417d74a7b5f20aabe6bff10de0
<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.
marcoagner has quit [Ping timeout: 260 seconds]
thrmo_ has joined #bitcoin-wizards
<kanzure> oh i had forgotten that this implementation handles nonmembership proofs too :(
marcoagner has joined #bitcoin-wizards
thrmo has quit [Ping timeout: 268 seconds]
<betawaffle> isn't this similar to what key transparency does to prove revocation?
NewLiberty has joined #bitcoin-wizards
<instagibbs> very similar, if memory serves
JackH has joined #bitcoin-wizards
CubicEarth has quit [Remote host closed the connection]
uvarovserge has joined #bitcoin-wizards
CubicEarth has joined #bitcoin-wizards
Dyaheon has quit [Ping timeout: 260 seconds]
madacol has quit [Ping timeout: 276 seconds]
Dyaheon has joined #bitcoin-wizards
madacol has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 268 seconds]
davec has quit [Ping timeout: 260 seconds]
davec has joined #bitcoin-wizards
madacol has quit [Ping timeout: 260 seconds]
JackH has quit [Ping timeout: 276 seconds]
madacol has joined #bitcoin-wizards
MaxSan has quit [Quit: Leaving.]
CubicEarth has quit [Remote host closed the connection]
AaronvanW has joined #bitcoin-wizards
DrOlmer has quit [Ping timeout: 248 seconds]
DrOlmer has joined #bitcoin-wizards
Aaronvan_ has joined #bitcoin-wizards
CubicEarth has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 255 seconds]
airbreather has quit [Remote host closed the connection]
airbreather has joined #bitcoin-wizards
CubicEarth has quit [Ping timeout: 255 seconds]
BashCo has quit [Read error: Connection reset by peer]
<betawaffle> does bitcoin ever do checkpoints? what would make a checkpoint any more problematic than trusting the genesis block?
BashCo has joined #bitcoin-wizards
<betawaffle> or is the issue that you can't include the UTXO set state in the checkpoint?
<betawaffle> (so you'd still need old blocks)
NewLiberty_ has joined #bitcoin-wizards
NewLiberty has quit [Ping timeout: 276 seconds]
NewLiberty has joined #bitcoin-wizards
NewLiberty_ has quit [Ping timeout: 246 seconds]
MaxSan has joined #bitcoin-wizards
alferz has joined #bitcoin-wizards
alferz has quit [Ping timeout: 268 seconds]
Aaronvan_ has quit [Ping timeout: 246 seconds]
intcat has joined #bitcoin-wizards
uvarovserge has quit [Quit: Textual IRC Client: www.textualapp.com]
madacol has quit [Ping timeout: 258 seconds]
espes__ has quit [Ping timeout: 260 seconds]
NewLiberty_ has joined #bitcoin-wizards
NewLiberty has quit [Ping timeout: 248 seconds]
madacol has joined #bitcoin-wizards
madacol has quit [Ping timeout: 255 seconds]
madacol has joined #bitcoin-wizards
madacol has quit [Ping timeout: 240 seconds]
madacol has joined #bitcoin-wizards
CubicEarth has joined #bitcoin-wizards
CubicEarth has quit [Ping timeout: 240 seconds]
madacol has quit [Ping timeout: 240 seconds]
madacol has joined #bitcoin-wizards
NewLiberty_ has quit [Ping timeout: 255 seconds]
NewLiberty has joined #bitcoin-wizards
madacol has quit [Ping timeout: 248 seconds]
kristofferR has joined #bitcoin-wizards
kristofferR has quit [Quit: Textual IRC Client: www.textualapp.com]
Aranjedeath has joined #bitcoin-wizards
Dyaheon has quit [Ping timeout: 255 seconds]
Dyaheon has joined #bitcoin-wizards
LeMiner has quit [Ping timeout: 260 seconds]
Aranjedeath has quit [Ping timeout: 276 seconds]
<kanzure> transcript of bramc's talk on merkle sets and txo commitments http://diyhpl.us/wiki/transcripts/sf-bitcoin-meetup/2017-07-08-bram-cohen-merkle-sets/
LeMiner has joined #bitcoin-wizards
madacol has joined #bitcoin-wizards
Aranjedeath has joined #bitcoin-wizards
NewLiberty_ has joined #bitcoin-wizards
NewLiberty has quit [Ping timeout: 258 seconds]
uvarovserge has joined #bitcoin-wizards
uvarovserge has quit [Client Quit]
BashCo has quit [Read error: Connection reset by peer]
BashCo has joined #bitcoin-wizards
<nsh> ty kanzure
<fluffypony> nsh: when are you getting yourself a telepresence robot?
<kanzure> it's me, i'm the telepresence robot.
<fluffypony> lol
intcat has quit [Remote host closed the connection]
<nsh> aye, lacking money/time to create non-kanzurian implementation of telepresence
<kanzure> ~~cache coherence~~
CubicEarth has joined #bitcoin-wizards
intcat has joined #bitcoin-wizards
CubicEarth has quit [Remote host closed the connection]
CubicEarth has joined #bitcoin-wizards
josephpoon has quit [Ping timeout: 255 seconds]
intcat has quit [Remote host closed the connection]
josephpoon has joined #bitcoin-wizards
MaxSan has quit [Ping timeout: 240 seconds]
EarlyGrey has quit [Quit: disconnected]
blackwraith has joined #bitcoin-wizards
intcat has joined #bitcoin-wizards
EarlyGrey has joined #bitcoin-wizards
uvarovserge has joined #bitcoin-wizards
uvarovserge has quit [Quit: Textual IRC Client: www.textualapp.com]
uvarovserge has joined #bitcoin-wizards
prime__ has quit [Ping timeout: 260 seconds]
wasi has joined #bitcoin-wizards
espes__ has joined #bitcoin-wizards
tiagotrs has quit [Ping timeout: 260 seconds]
nickler has quit [Ping timeout: 255 seconds]
Aranjedeath has quit [Quit: Three sheets to the wind]
nickler has joined #bitcoin-wizards
Dyaheon has quit [Ping timeout: 255 seconds]
Dyaheon has joined #bitcoin-wizards
CubicEarth has quit []
<waxwing> kanzure: weirdly i was reading about ring signatures and stumbled onto this along the way by coincidence: https://users.dcc.uchile.cl/~pcamacho/papers/strongacc08.pdf
<waxwing> ah yep. it's the fourth one of those :)
<kanzure> no i added it.
<kanzure> i'm just efficient.
<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)
CheckDavid has joined #bitcoin-wizards
uvarovserge has quit [Quit: Textual IRC Client: www.textualapp.com]
uvarovserge has joined #bitcoin-wizards
Joseph__ has joined #bitcoin-wizards
NewLiberty_ has quit [Ping timeout: 246 seconds]
DrOlmer has quit [Ping timeout: 248 seconds]
DrOlmer has joined #bitcoin-wizards
propumpkin is now known as contrapumpkin
deep-book-gk_ has joined #bitcoin-wizards
Noldorin has joined #bitcoin-wizards
deep-book-gk_ has left #bitcoin-wizards [#bitcoin-wizards]
NewLiberty has joined #bitcoin-wizards
Joseph__ has quit [Ping timeout: 255 seconds]
NewLiberty_ has joined #bitcoin-wizards
intcat has quit [Remote host closed the connection]
NewLiberty has quit [Ping timeout: 276 seconds]
intcat has joined #bitcoin-wizards
daszorz has joined #bitcoin-wizards
daszorz2 has joined #bitcoin-wizards
daszorz has quit [Ping timeout: 248 seconds]
uvarovserge has quit [Quit: Textual IRC Client: www.textualapp.com]
NewLiberty has joined #bitcoin-wizards
daszorz2 has quit [Read error: Connection reset by peer]
NewLiberty_ has quit [Ping timeout: 248 seconds]