2016-08-03.log

Source: https://freenode.irclog.whitequark.org/bitcoin-wizards/2016-08-03
Timezone: UTC

2015-10-30 00:53 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

03:13 aem is now known as aem
04:02 maaku_ is now known as maaku
07:48 <nsh> 'Pass the hash for peace, love and security in the quantum computing age -- Boffins smokin' idea to share parts of keys to cook quantum-proof crypto' - http://www.theregister.co.uk/2016/08/02/protect_signatures_from_quantum_computers_shor_say_cryptoboffins/
07:49 <nsh> -> 'Unconditionally Secure Signatures' - https://eprint.iacr.org/2016/739.pdf
07:49 <nsh> MAC generalisation using hash fragments
11:42 roidster is now known as Guest38856
13:34 laurentmt1 is now known as laurentmt
15:30 <amiller> does this mimble wimble thing really work
15:30 <amiller> i really wish we could talk about these things in terms of zk proofs rather than signatures with related keys
15:30 <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)
15:32 <amiller> can you summarize the scheme with your privacy improvement inlined?
15:32 <andytoshi> i think so .. one sec
15:33 <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)
15:34 <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.
15:35 <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
15:36 <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
15:37 <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..)
15:38 <amiller> hm
15:38 <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)
15:39 <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
15:39 <amiller> seems ok, i also don't know better notation
15:39 <amiller> in general there are these sort of multi-prover zk proofs and i have no notation for htem
15:39 <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
15:40 <andytoshi> yeah
15:40 <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
15:40 <amiller> how is this different than CT?
15:40 <andytoshi> but there's also something stronger being shown, if i keep my own blinding factors secret then everyone knows there's no theft
15:40 <amiller> i guess going in i thought this was going to be comparable to ringCT
15:40 <andytoshi> no, ringCT is actually orthogonal (though technically i have zero idea how to combine these)
15:41 <andytoshi> CT just uses the blinding factors as blinding factors. this scheme uses the blinding factors for authentication. that's the moral difference
15:41 <andytoshi> (it then uses this fact to get OWAS and massive pruning while still allowing full verification)
15:41 <amiller> how does it give any better pruning than CT
15:42 <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
15:42 <kanzure> andytoshi: you should still look at http://diyhpl.us/wiki/transcripts/2016-july-bitcoin-developers-miners-meeting/dan-boneh/
15:42 <andytoshi> this literally lets you delete every spent output
15:42 <andytoshi> thanks kanzure, it's open, i will
15:43 <amiller> "reverify the chain" ok
15:43 <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
15:43 <andytoshi> (assuming everyone kept their keys secret, "theft" means something technical here..)
15:44 <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
15:44 <amiller> so like, a new node that wants to start mining and verify the whole chain
15:44 <amiller> without just relying on SPV security
15:44 <andytoshi> yeah, i'd like to talk about this. i'm trying to understand the security model here.
15:44 <andytoshi> right
15:44 <amiller> it's safe to ignore some information that was originally included?
15:44 <andytoshi> yes. what this new node cares about is knowing the current chainstate (utxo set)
15:45 <andytoshi> suppose the node *does not* care how this utxoset came to be, only that somehow the coins were always passed along honestly
15:45 <amiller> and i can verify that this utxo set doesn't reflect any invalid transitions like a block that ignores some previous transactions
15:45 <andytoshi> exactly
15:46 <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
15:47 <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.
15:48 <andytoshi> instagibbs: what do you mean?
15:48 <instagibbs> (thought we discussed this already but I'll rexplain)
15:48 <andytoshi> if you mean peers can give you different merkle paths for the same utxos, that doesn't give a different utxoset
15:48 <andytoshi> that just attaches the utxoset to the blockchain in a different way
15:48 <instagibbs> or different utxos
15:49 <andytoshi> kk pls explain
15:49 <instagibbs> like, imagine complete disjoint post-genesis histories
15:49 <amiller> i feel like there's something implicit missing, like we're implicitly assuming SPV already or osmething
15:49 <amiller> like i think there's something lurking here that makes the efficiency claim vs CT not actually present
15:49 <andytoshi> instagibbs: this scheme does not allow that, all the coinbase inputs are explicit
15:49 <andytoshi> amiller: this has completely different goals than CT
15:49 <andytoshi> CT was just about hiding amounts, this is about collapsing history
15:50 <instagibbs> andytoshi, sorry can you explain why that would stop that
15:50 <amiller> what is collapsing history? so far everything you described sounds like CT
15:50 <instagibbs> merkle trees don't prove anything about not having two different spends of the same outputs
15:50 <andytoshi> instagibbs: the blockchain defines a single set of inputs. the inputs are part of the history. therefore you cannot have disjoint histories
15:50 <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
15:50 <andytoshi> instagibbs: no, but the algebra prevents that (unless the "same output" appeared twice)
15:51 <andytoshi> amiller: yes, i haven't gotten to the collapsing history yet
15:51 <andytoshi> but nor have i made any claims of space savings yet
15:51 <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))
15:51 <andytoshi> i'm just trying to reframe this specific part in a way that you like, because it's critical to everything else
15:51 <amiller> ok, i think i understand the signature scheme well enough
15:52 <instagibbs> one transaction has 2 outputs, the other has 1, let's say. So they're unique in blinding factors and so on.
15:52 <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
15:52 <instagibbs> So I reveal one history to you, and hide the other. The math will work out.
15:52 <andytoshi> amiller: so you keep both k1G + sig, and you add the explcit k2s, and this is OWAS
15:53 <instagibbs> I have no idea what this means for the security model in reality
15:53 <andytoshi> instagibbs: lemme think about this, this seems very serious
15:54 <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
15:54 <instagibbs> our meaning wimble
15:55 <andytoshi> yeah, sure, but we may have consensus disagreement between peers
15:55 <instagibbs> but peers may be on different histories, on same chain header. Peers can tell each other. I'm not sure how to converge
15:55 <andytoshi> (which might be recoverable, maybe inputs need to have explicit merkle paths and this does it)
15:55 <andytoshi> no, that's not sufficient..
15:55 <instagibbs> yeah I thought about that too, then discounted it, but can't immediately recall
15:56 <kanzure> andytoshi: re: OWAS things, the dan boneh transcript covers this in some gorey detail, but also it was covered near the bottom of https://bitcoincore.org/logs/2016-05-zurich-meeting-notes.html
15:56 <kanzure> starting near the section called "Schnorr stuff and signature aggregation" (or just search for "OWAS")
15:58 <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.
15:58 <andytoshi> instagibbs: you don't need to multispend any outputs to do this tho
15:58 <instagibbs> oh hm?
15:58 <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
15:59 <instagibbs> err right
15:59 <andytoshi> now you've IBD'd peers in a way that they disagree on the utxo set-
15:59 <instagibbs> well there are inputs being spent twice, in general
15:59 <instagibbs> but yes we care about new outputs matching up
15:59 <andytoshi> peers who were online at the time would detect this, but that's tendermint security model
15:59 <andytoshi> instagibbs: what do you mean by inputs being spent twice in general?
16:00 <instagibbs> I agree with what you're saying, it's not impt
16:00 <instagibbs> Nodes would have to reject a chain once they discover the utxo set conflicts with another one
16:00 <andytoshi> instagibbs: ok, maybe the outputs need to be in a merkle sum tree
16:00 <andytoshi> so you can't do this C1, C2, C1 + C2 trick
16:02 <instagibbs> Well, there is already DoS vector of simply being fed bad utxo set
16:02 <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)
16:02 <instagibbs> At least with this attack it would require miners making "legitimate" parallel histories
16:03 <instagibbs> which can/will invalidate huge swaths of blocks if caught
16:03 <andytoshi> yes, that's worse, because then it's not detectable
16:03 <andytoshi> but using a merkle sum tree prevents it i thin
16:05 <andytoshi> oh, no, you can fool a merkle sum tree by putting negative outputs in. you just never reveal these to anyone
16:05 <instagibbs> I was hoping peer gossip would be just as effective as spreading the header chain, but now not sure at all
16:06 <andytoshi> in practice it might be
16:06 <andytoshi> but this is a weird security model
16:07 <andytoshi> you can amplify from peer gossip to SPV by having miners commit to the current utxoset in every block
16:08 <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
16:08 <andytoshi> (which actually, might be exactly what you want, the blockheaders define the "history that everyone else is using" anyway..)
16:09 <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
16:12 <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)
16:12 <instagibbs> Yes
16:13 <instagibbs> So it sort of reminds me of a rolling utxo commitment
16:13 <instagibbs> but you must assume miners all start from beginning
16:13 <kanzure> without gossip how are you doing initial block download?
16:14 <instagibbs> kanzure, that's what I mean, the gossip isn't as useful as it is for finding the best chain
16:15 <instagibbs> but the gossip for wimble will never prove to the user they are on the right chain
16:15 <kanzure> is this concern about lack of diff and lack of knowing where the problem is in the data set?
16:15 <instagibbs> s/right/valid/
16:16 <andytoshi> kanzure: no the problem is that there can be multiple valid histories associated to the same blockheader chain
16:16 <instagibbs> It's the lack of knowing if you're on a valid chain/utxo set.
16:17 <andytoshi> so you can make a "randomized merkle-sum tree" which avoids this problem i think
16:17 <andytoshi> each internal node commits to the sum H(L)L + H(R)R where L, R are its two child nodes
16:18 <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
16:19 <andytoshi> ..has anyone heard of this construction before? i just made it up..
16:20 <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?
16:20 <kanzure> iddo: http://diyhpl.us/~bryan/papers2/bitcoin/mimblewimble.txt
16:20 <andytoshi> iddo: yes, certainly, in that case you can literally make up the entire history before the last k blocks
16:21 <andytoshi> or make up no history, just say "the chainstate was this back then, trust me"
16:22 <iddo> what's the security guarantees that you want to have?
16:22 <instagibbs> andytoshi, the attacker could put C1, C2 in block 2, and C1+C2 in block 3?
16:22 <instagibbs> Originally I described the attack as odd/even blocks, to make it clear they could be anywhere
16:23 <instagibbs> iddo, we would like full node security without downloading the entire chain :)
16:26 <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
16:28 <andytoshi> but i'm unsure now what this randomized merkle sum tree actually gets you though, i'm confused again
16:29 * andytoshi goes for a run
16:29 <instagibbs> yeah good idea, cheers
16:29 <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?
16:30 <andytoshi> iddo: yes, kanzure posted a link
16:30 <iddo> btw you can do probabilistic proof that the utxoset is verified from genesis, but it isn't practical
16:31 <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.
16:32 <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"
16:40 <gmaxwell> Most bitcoin technically sophicated hacker we've seen yet? https://www.reddit.com/r/Bitcoin/comments/4vykkr/1000_btc_giveaway_from_your_friend_rekcahxfb/
16:41 <Tiraspoll> gmaxwell https://bitcointalk.org/index.php?topic=327178.msg3521657#msg3521657
16:41 <Tiraspoll> the coins are from here
16:41 <Tiraspoll> not related to finex
16:41 <Tiraspoll> 2013 address
16:42 zooko` is now known as zooko
16:42 <gmaxwell> cool.
17:03 <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)
17:04 <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)
17:04 <andytoshi> but you already only have SPV security that you're on the consensus history, that's more or less what SPV security means
17:08 <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.
17:08 <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.
17:12 <andytoshi> gmaxwell: well remember that the blockheaders untimately do commit to everything
17:12 <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?
17:12 <andytoshi> so if there really are alternate histories like this they will have alternate blockchains
17:12 <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..
17:12 <andytoshi> iddo: correct, you're basically screwed if you reorg past where you trimmed (you'll have to find the data somewhere)
17:12 <andytoshi> iddo: but the security here is much stronger than SPV
17:13 <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.
17:13 <andytoshi> instagibbs: that seems very hard to do, which history is "better"?
17:13 <instagibbs> yes, that's the nut to crack
17:14 <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
17:14 <andytoshi> and in general detecting this even involves solving subset-sum
17:14 <andytoshi> err, that's not true, you'll notice when consensus splits
17:14 <instagibbs> well you can make it arbitrarily better, like say first utxo in a conflicting history in the block
17:14 <instagibbs> (probably not good idea but still)
17:14 <andytoshi> i think that creates the ability to retroactively invalidate blocks
17:15 <instagibbs> invalidates utxo state, right, and no clear way of updating, and now that i think of it, doesnt work
17:15 <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
17:15 <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?
17:15 <andytoshi> iddo: have yiou read the paper?
17:15 <instagibbs> iddo, we are discussing the paper
17:16 <iddo> no sorry :(
17:17 <instagibbs> ok, tiebreaking rule doesnt work because there's no way to compute which utxos "correspond" to others
17:21 <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.
17:21 <instagibbs> each history can not inflate or steal either way
17:22 <andytoshi> instagibbs: correct
17:22 <andytoshi> you're trusting the miners not to break consensus
17:22 <andytoshi> but you are already trusting them not to do that
17:25 <andytoshi> kanzure: reading the boneh stuff now, thanks
17:27 <kanzure> kk muchlongread funstuffs.
17:28 <andytoshi> hah, yes, 20 printed pages
17:28 <andytoshi> i apparently bought a printer without duplex, because i'm an idiot, and further apparently bought the heaviest paper ever made :(
17:49 <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
19:59 bildramer1 is now known as bildramer
21:23 <kanzure> "Short randomizable signatures" http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.699.2251&rep=rep1&type=pdf
23:06 <andytoshi> instagibbs: i tried to summarize my comments here in this post: https://www.reddit.com/r/Bitcoin/comments/4vub3y/mimblewimble_noninteractive_coinjoin_and_better/d62cux6