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
Chris_Stewart_5 has quit [Ping timeout: 265 seconds]
Chris_Stewart_5 has joined #bitcoin-wizards
aem has quit [Remote host closed the connection]
rusty2 has joined #bitcoin-wizards
priidu has joined #bitcoin-wizards
aem has joined #bitcoin-wizards
byteflame has quit [Ping timeout: 240 seconds]
fabianfabian has quit [Quit: what]
pro has quit [Quit: Leaving]
dnaleor has quit [Quit: Leaving]
ftknox has left #bitcoin-wizards ["WeeChat 1.0.1"]
dnaleor has joined #bitcoin-wizards
veleiro has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 265 seconds]
Chris_Stewart_5 has joined #bitcoin-wizards
Ylbam has quit [Quit: Connection closed for inactivity]
netzin has joined #bitcoin-wizards
ennui has quit [Ping timeout: 244 seconds]
aalex__ has quit [Ping timeout: 244 seconds]
aalex__ has joined #bitcoin-wizards
jtimon has joined #bitcoin-wizards
belcher has quit [Quit: Leaving]
netzin has quit [Remote host closed the connection]
jtimon_ has joined #bitcoin-wizards
jtimon_ has quit [Remote host closed the connection]
King_Rex has quit [Remote host closed the connection]
netzin has joined #bitcoin-wizards
mdavid613 has quit [Ping timeout: 244 seconds]
mdavid613 has joined #bitcoin-wizards
supasonic has joined #bitcoin-wizards
Noldorin has quit [Quit: My MacBook Pro has gone to sleep. ZZZzzz…]
mdavid613 has quit [Quit: Leaving.]
thepumpernickle1 has quit [Ping timeout: 244 seconds]
Chris_Stewart_5 has quit [Ping timeout: 244 seconds]
fkinglag has quit [Ping timeout: 265 seconds]
veleiro has quit [Ping timeout: 250 seconds]
fkinglag has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
netzin has quit []
supasonic has quit [Read error: Connection reset by peer]
jtimon has quit [Ping timeout: 260 seconds]
ruby32 has quit [Remote host closed the connection]
ruby32 has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 258 seconds]
Chris_Stewart_5 has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 264 seconds]
oneeman has joined #bitcoin-wizards
supasonic has joined #bitcoin-wizards
priidu has quit [Ping timeout: 244 seconds]
aem is now known as aem
execute has quit [Ping timeout: 244 seconds]
aalex__ has quit [Ping timeout: 276 seconds]
aalex__ has joined #bitcoin-wizards
Aranjedeath has quit [Quit: Three sheets to the wind]
thepumpernickle1 has joined #bitcoin-wizards
maaku_ is now known as maaku
maaku has quit [Ping timeout: 244 seconds]
maaku has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
aalex__ has quit [Ping timeout: 260 seconds]
aalex__ has joined #bitcoin-wizards
aalex__ has quit [Ping timeout: 258 seconds]
Burrito has quit [Quit: Leaving]
aalex__ has joined #bitcoin-wizards
btcdrak has quit [Quit: Connection closed for inactivity]
murch has joined #bitcoin-wizards
roidster has quit [Ping timeout: 240 seconds]
ThomasV has quit [Ping timeout: 240 seconds]
toktok has joined #bitcoin-wizards
oneeman has quit [Quit: Leaving]
bustd_soket has quit [Quit: bustd_soket]
toktok has quit [Ping timeout: 244 seconds]
AusteritySucks has quit [Ping timeout: 240 seconds]
ThomasV has joined #bitcoin-wizards
bitcoin-wizards8 has joined #bitcoin-wizards
bitcoin-wizards8 has quit [Client Quit]
jgarzik has joined #bitcoin-wizards
BashCo has quit [Remote host closed the connection]
edvorg has quit [Remote host closed the connection]
aalex__ has quit [Ping timeout: 276 seconds]
aalex__ has joined #bitcoin-wizards
blackwraith has joined #bitcoin-wizards
priidu has quit [Ping timeout: 260 seconds]
blackwraith has quit [Ping timeout: 260 seconds]
skyraider has joined #bitcoin-wizards
xissburg has quit [Quit: leaving]
byteflame has joined #bitcoin-wizards
xissburg has joined #bitcoin-wizards
laurentmt1 has joined #bitcoin-wizards
laurentmt has quit [Ping timeout: 258 seconds]
laurentmt1 is now known as laurentmt
jonasschnelli has quit [Changing host]
jonasschnelli has joined #bitcoin-wizards
Noldorin has joined #bitcoin-wizards
licnep has quit [Quit: Connection closed for inactivity]
Jaamg has joined #bitcoin-wizards
Guyver2 has joined #bitcoin-wizards
AusteritySucks has quit [Ping timeout: 240 seconds]
jtimon has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
JackH has joined #bitcoin-wizards
ThomasV has quit [Ping timeout: 258 seconds]
shesek has quit [Ping timeout: 244 seconds]
AusteritySucks has joined #bitcoin-wizards
AusteritySucks has quit [Ping timeout: 244 seconds]
Chris_Stewart_5 has quit [Ping timeout: 244 seconds]
JackH has quit [Ping timeout: 244 seconds]
AusteritySucks has joined #bitcoin-wizards
<amiller>
does this mimble wimble thing really work
<amiller>
i really wish we could talk about these things in terms of zk proofs rather than signatures with related keys
Chris_Stewart_5 has joined #bitcoin-wizards
<andytoshi>
amiller: i think it works. agreed, would be easier to talk about in terms of zk proofs (tho this would require reframing some things)
<amiller>
can you summarize the scheme with your privacy improvement inlined?
<andytoshi>
i think so .. one sec
<andytoshi>
so to start, every utxo has a CT pedersen commitment associated to it, vH + rG, and `r` is the secret blinding factor that only the owner knows (nobody else, no auditors, etc)
ThomasV has joined #bitcoin-wizards
<andytoshi>
if i send you money, i produce a half-transaction that has everything except your outputs in it (so one change and some inputs), and i also give you the (r, v) pair such that (output commit - input commits = vH + rG.
JackH has joined #bitcoin-wizards
thepumpernickle1 has quit [Ping timeout: 260 seconds]
<andytoshi>
you, the recipient, then add your own outputs so that (output commits - input commits = kG) for some k that you know. split k into k = k1 + k2. then publish a signature with k1G as well as k2
thepumpernickle1 has joined #bitcoin-wizards
<andytoshi>
so k1G has a sig which is a zk proof that you know k1, and k2 is a full-knowledge proof that you know k2, and this proves that the excess kG does not have any H component, which in turn proves that the whole transaction adds up
<andytoshi>
does this make sense so far? can you see a clean way to discribe this whole tx in terms of zk proofs (i do not, it really seems like this interaction is necessary but only the participants can be usre that this interaction happened..)
oneeman has joined #bitcoin-wizards
<amiller>
hm
<andytoshi>
i guess, i give *you* a full-knowledge proof that i know the blinding key for (change minus inputs). then you produce a zk proof that you know the blinding key for the entire (outputs - inputs)
<andytoshi>
"full-knowledge proof" is a term i just made up for my giving you the values .. i can stop using this if you want
<amiller>
seems ok, i also don't know better notation
<amiller>
in general there are these sort of multi-prover zk proofs and i have no notation for htem
<amiller>
like i prove one thing, you adapt that proof plus add more to it to make a related proof but you didn't know the whole witness
<andytoshi>
yeah
<andytoshi>
so it's really not publicly verifiable that i did a key handoff here, only the recipient can verify this. what *is* publicly verifiable is that no coins were created or destroyed certainly
<amiller>
how is this different than CT?
<andytoshi>
but there's also something stronger being shown, if i keep my own blinding factors secret then everyone knows there's no theft
<amiller>
i guess going in i thought this was going to be comparable to ringCT
<andytoshi>
no, ringCT is actually orthogonal (though technically i have zero idea how to combine these)
<andytoshi>
CT just uses the blinding factors as blinding factors. this scheme uses the blinding factors for authentication. that's the moral difference
<andytoshi>
(it then uses this fact to get OWAS and massive pruning while still allowing full verification)
<amiller>
how does it give any better pruning than CT
<andytoshi>
CT doesn't give any pruning at all, you've gotta keep every output and every rangeproof around if you want to be able to reverify the chain
<andytoshi>
this literally lets you delete every spent output
JackH has quit [Ping timeout: 264 seconds]
<andytoshi>
thanks kanzure, it's open, i will
<amiller>
"reverify the chain" ok
<andytoshi>
amiller: ...and if you give the chain to somebody, without any spent outputs or any input refs even, they can still verify that along the entire history no theft or inflation happened
<andytoshi>
(assuming everyone kept their keys secret, "theft" means something technical here..)
<amiller>
this seems like an interesting and relevant security goal but i don't understand it clearly yet, we can talk about it independently of the scheme though
<amiller>
so like, a new node that wants to start mining and verify the whole chain
<amiller>
without just relying on SPV security
<andytoshi>
yeah, i'd like to talk about this. i'm trying to understand the security model here.
<andytoshi>
right
<amiller>
it's safe to ignore some information that was originally included?
<andytoshi>
yes. what this new node cares about is knowing the current chainstate (utxo set)
<andytoshi>
suppose the node *does not* care how this utxoset came to be, only that somehow the coins were always passed along honestly
<amiller>
and i can verify that this utxo set doesn't reflect any invalid transitions like a block that ignores some previous transactions
<andytoshi>
exactly
<andytoshi>
there exists a path of handoffs (where "handoff" is something we'd have to describe more precisely, but it's done by one of the transactions i described above) from coinbase inputs to the current utxos
<instagibbs>
If you don't validate all of the blocks' contents, it's possible there is an entirely different utxo set that also seems valid. Peers can tell you about these alternative sets of utxo though.
<andytoshi>
instagibbs: what do you mean?
<instagibbs>
(thought we discussed this already but I'll rexplain)
<andytoshi>
if you mean peers can give you different merkle paths for the same utxos, that doesn't give a different utxoset
<andytoshi>
that just attaches the utxoset to the blockchain in a different way
<amiller>
i feel like there's something implicit missing, like we're implicitly assuming SPV already or osmething
<amiller>
like i think there's something lurking here that makes the efficiency claim vs CT not actually present
<andytoshi>
instagibbs: this scheme does not allow that, all the coinbase inputs are explicit
<andytoshi>
amiller: this has completely different goals than CT
<andytoshi>
CT was just about hiding amounts, this is about collapsing history
<instagibbs>
andytoshi, sorry can you explain why that would stop that
<amiller>
what is collapsing history? so far everything you described sounds like CT
<instagibbs>
merkle trees don't prove anything about not having two different spends of the same outputs
<andytoshi>
instagibbs: the blockchain defines a single set of inputs. the inputs are part of the history. therefore you cannot have disjoint histories
<amiller>
the outputs are represented as commitments, the sender/receiver together make a transaction or pair of half-transactions that spend some old outputs and create so new outputs
<andytoshi>
instagibbs: no, but the algebra prevents that (unless the "same output" appeared twice)
<andytoshi>
amiller: yes, i haven't gotten to the collapsing history yet
<andytoshi>
but nor have i made any claims of space savings yet
<instagibbs>
genesis block makes 1 blinded output, following block has 2 transactions(ignore the fact that we can decduce double-spending from pure numbers here))
<andytoshi>
i'm just trying to reframe this specific part in a way that you like, because it's critical to everything else
<amiller>
ok, i think i understand the signature scheme well enough
skyraider has quit [Quit: Connection closed for inactivity]
<instagibbs>
one transaction has 2 outputs, the other has 1, let's say. So they're unique in blinding factors and so on.
<andytoshi>
amiller: kk, so the next part is OWAS, which is pretty straightforward, you can just put transactions inputs and outputs together, then the sum of all outputs minus all inputs will be the sum of all these excess k*G values
NewLiberty has joined #bitcoin-wizards
<instagibbs>
So I reveal one history to you, and hide the other. The math will work out.
<andytoshi>
amiller: so you keep both k1G + sig, and you add the explcit k2s, and this is OWAS
<instagibbs>
I have no idea what this means for the security model in reality
<andytoshi>
instagibbs: lemme think about this, this seems very serious
<instagibbs>
I mean it's the same problem we have in Bitcoin... but with our scheme we get strong guarantees knowing that it is at least *a* valid non-inflationary history
<instagibbs>
our meaning wimble
<andytoshi>
yeah, sure, but we may have consensus disagreement between peers
<instagibbs>
but peers may be on different histories, on same chain header. Peers can tell each other. I'm not sure how to converge
<andytoshi>
(which might be recoverable, maybe inputs need to have explicit merkle paths and this does it)
zooko has joined #bitcoin-wizards
<andytoshi>
no, that's not sufficient..
<instagibbs>
yeah I thought about that too, then discounted it, but can't immediately recall
<kanzure>
starting near the section called "Schnorr stuff and signature aggregation" (or just search for "OWAS")
<instagibbs>
so you'd need to figure out where the first violation of the "only one spend of one output" rule is broken, invalidate back to that block, and sync from there, or something.
<andytoshi>
instagibbs: you don't need to multispend any outputs to do this tho
<instagibbs>
oh hm?
<andytoshi>
instagibbs: you create three outputs with commitments C1, C2, C1 + C2. when IBDing you reveal C1 and C2 to some peers, C1 + C2 to others
<instagibbs>
err right
<andytoshi>
now you've IBD'd peers in a way that they disagree on the utxo set-
<instagibbs>
well there are inputs being spent twice, in general
<instagibbs>
but yes we care about new outputs matching up
<andytoshi>
peers who were online at the time would detect this, but that's tendermint security model
<andytoshi>
instagibbs: what do you mean by inputs being spent twice in general?
<instagibbs>
I agree with what you're saying, it's not impt
<instagibbs>
Nodes would have to reject a chain once they discover the utxo set conflicts with another one
<andytoshi>
instagibbs: ok, maybe the outputs need to be in a merkle sum tree
<andytoshi>
so you can't do this C1, C2, C1 + C2 trick
<instagibbs>
Well, there is already DoS vector of simply being fed bad utxo set
<andytoshi>
yes that's fine, there are ways around that (basically asking peers for a quorum on what the utxos in each block actually ought to be)
<instagibbs>
At least with this attack it would require miners making "legitimate" parallel histories
<instagibbs>
which can/will invalidate huge swaths of blocks if caught
<andytoshi>
yes, that's worse, because then it's not detectable
<andytoshi>
but using a merkle sum tree prevents it i thin
zooko` has joined #bitcoin-wizards
<andytoshi>
oh, no, you can fool a merkle sum tree by putting negative outputs in. you just never reveal these to anyone
<instagibbs>
I was hoping peer gossip would be just as effective as spreading the header chain, but now not sure at all
<andytoshi>
in practice it might be
<andytoshi>
but this is a weird security model
zooko has quit [Ping timeout: 276 seconds]
<andytoshi>
you can amplify from peer gossip to SPV by having miners commit to the current utxoset in every block
<andytoshi>
so you have full security in knowing that no invalid transactions have occured, but only SPV security that your history is the one that everyone else is using
<andytoshi>
(which actually, might be exactly what you want, the blockheaders define the "history that everyone else is using" anyway..)
<instagibbs>
Hmm, yes I was hoping the gossip would be more holistic, but I think it's looking more fraud-proofy considering peers wouldn't even care about bad branches
fractex has joined #bitcoin-wizards
<andytoshi>
i don't like gossip or fraud proofs, both of these can be censored from a peer who is surrounded during IBD (and maybe the peer doesn't know to ask for it later so the effect is permanent)
newbie has joined #bitcoin-wizards
<instagibbs>
Yes
<instagibbs>
So it sort of reminds me of a rolling utxo commitment
<instagibbs>
but you must assume miners all start from beginning
<kanzure>
without gossip how are you doing initial block download?
<instagibbs>
kanzure, that's what I mean, the gossip isn't as useful as it is for finding the best chain
<instagibbs>
but the gossip for wimble will never prove to the user they are on the right chain
<kanzure>
is this concern about lack of diff and lack of knowing where the problem is in the data set?
<instagibbs>
s/right/valid/
<andytoshi>
kanzure: no the problem is that there can be multiple valid histories associated to the same blockheader chain
<instagibbs>
It's the lack of knowing if you're on a valid chain/utxo set.
<andytoshi>
so you can make a "randomized merkle-sum tree" which avoids this problem i think
<andytoshi>
each internal node commits to the sum H(L)L + H(R)R where L, R are its two child nodes
<andytoshi>
now if you have C1, C2, C1 + C2 in the same merkle tree there is no way to come up with extra branches that will hide this fact
<andytoshi>
..has anyone heard of this construction before? i just made it up..
<iddo>
if you have utxoset in every block then you can "collapse" the history by trimming everything except the last k blocks (say k=1000), are you guys suggesting a way to collapse the history that gives better security guarantees than this simple approach?
<andytoshi>
iddo: yes, certainly, in that case you can literally make up the entire history before the last k blocks
<andytoshi>
or make up no history, just say "the chainstate was this back then, trust me"
mdavid613 has joined #bitcoin-wizards
<iddo>
what's the security guarantees that you want to have?
<instagibbs>
andytoshi, the attacker could put C1, C2 in block 2, and C1+C2 in block 3?
<instagibbs>
Originally I described the attack as odd/even blocks, to make it clear they could be anywhere
<instagibbs>
iddo, we would like full node security without downloading the entire chain :)
Tiraspoll has joined #bitcoin-wizards
maaku has left #bitcoin-wizards ["http://quassel-irc.org - Chat comfortably. Anywhere."]
<andytoshi>
instagibbs: well you can always make the root of the tree have as children the "real" root as well as the previous block's root, so they are all connected
<andytoshi>
but i'm unsure now what this randomized merkle sum tree actually gets you though, i'm confused again
* andytoshi
goes for a run
<instagibbs>
yeah good idea, cheers
<iddo>
with the simple approach you'd get say k=1000 PoW confirmations that the utxoset is in consensus, you claim that you can verify the history from genesis after trimming the history?
<andytoshi>
iddo: yes, kanzure posted a link
<iddo>
btw you can do probabilistic proof that the utxoset is verified from genesis, but it isn't practical
<kanzure>
instagibbs: for full node security without downloading and verifying the entire chain, you should probably work backwards from full security and then figure out what you can add to that scenario, until you work backwards to something that roughly approximates the set of features you prefer a full node to have.
<kanzure>
and ideally without saying "turn the entire system into a giant zk-snark and just query a bunch of small proofs and let the proofs battle each other for supremacy"
Chris_Stewart_5 has quit [Ping timeout: 260 seconds]
<andytoshi>
instagibbs: ok, so forget all that merkle sum stuff. the only thing an attacker can do with your attack is split consensus; he can't steal coins or inflate or anything (he can only split his own coins, since he'd have to rangeproof the split). so add a commit to the utxoset in each block, now such a consensus split is trivially detectable (and the longest-chain rule can take care of it)
<andytoshi>
so you have full security knowing the utxoset up to how the coins are split up (and their age), which means knowing the utxoset up to ownership, and SPV security of the exact split (i.e. whether you are on the consensus history)
ThomasV has quit [Ping timeout: 260 seconds]
<andytoshi>
but you already only have SPV security that you're on the consensus history, that's more or less what SPV security means
<gmaxwell>
it is a little obnoxious that a summary-verifier could end up on a history that had temporary theft but which was made whole at the end, while a full verifier would reject that history.
<gmaxwell>
you could say that the full verifier should reorg to accept it too, since the end result is the same-- but that only makes sense if the only enforced rules are the rules enforcable by summary verification.
MaxSan_ has joined #bitcoin-wizards
<andytoshi>
gmaxwell: well remember that the blockheaders untimately do commit to everything
<iddo>
not clear if you're trimming data forever, or just having a method to provide SPV proofs, if you trim forever then you're not protected against reversal of history of length greater than where you trimmed?
<andytoshi>
so if there really are alternate histories like this they will have alternate blockchains
<instagibbs>
I'm thinking along the lines of allowing multiple histories, even invalid transactions. If you had a conflicting utxo tie-breaking rule, nodes could converge by just sharing what they know, much like sharing block headers today..
ennui has quit [Ping timeout: 244 seconds]
<andytoshi>
iddo: correct, you're basically screwed if you reorg past where you trimmed (you'll have to find the data somewhere)
<andytoshi>
iddo: but the security here is much stronger than SPV
<instagibbs>
given a proper utxo set you know there's no inflation, and you can be told about better histories by a single honest peer.
<andytoshi>
instagibbs: that seems very hard to do, which history is "better"?
<instagibbs>
yes, that's the nut to crack
<andytoshi>
if i have ten utxos on one history, and ten on the other, that are simply split up differently (and i'm not limited to ten, and i'm not limited to having the same number either), neither is any better
<andytoshi>
and in general detecting this even involves solving subset-sum
<andytoshi>
err, that's not true, you'll notice when consensus splits
<instagibbs>
well you can make it arbitrarily better, like say first utxo in a conflicting history in the block
<instagibbs>
(probably not good idea but still)
<andytoshi>
i think that creates the ability to retroactively invalidate blocks
<instagibbs>
invalidates utxo state, right, and no clear way of updating, and now that i think of it, doesnt work
<andytoshi>
i really think just committing to the utxoset in each block is the solution here, then differing utxo splits are detected by looking at the block headers
<iddo>
so i still don't see how you get better security than just utxoset in every block and trim old history, is the security just with regard to better anonymity?
<andytoshi>
iddo: have yiou read the paper?
<instagibbs>
iddo, we are discussing the paper
<iddo>
no sorry :(
<instagibbs>
ok, tiebreaking rule doesnt work because there's no way to compute which utxos "correspond" to others
<instagibbs>
so the added value here is with utxo commitment on top you are SPV in that you're trusting the miners to not commit to a utxo set in an invalid chain with multiple histories.
<instagibbs>
each history can not inflate or steal either way
<andytoshi>
instagibbs: correct
<andytoshi>
you're trusting the miners not to break consensus
<andytoshi>
but you are already trusting them not to do that
<andytoshi>
kanzure: reading the boneh stuff now, thanks
<kanzure>
kk muchlongread funstuffs.
<andytoshi>
hah, yes, 20 printed pages
<andytoshi>
i apparently bought a printer without duplex, because i'm an idiot, and further apparently bought the heaviest paper ever made :(
lvns has joined #bitcoin-wizards
zooko has quit [Ping timeout: 250 seconds]
laurentmt has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
lvns has quit [Remote host closed the connection]
lvns has joined #bitcoin-wizards
<andytoshi>
instagibbs: i think the way to think about this is that when you do the IBD, the security is as though every single transaction occured in the tip of the block that you IBD'd up to