--- Log opened Sat Dec 07 00:00:38 2013
08:31 < iddo> amiller: gmaxwell: i'm trying to understand regarding DoS by diff-1 orphans at genesis, if we eliminate checkpoints and add to blocks some kind of merkle root committing to the current UTXO (to help lite nodes), how does it mitigate this DoS attack?
08:32 < sipa> there's only a DoS attack possible because of how the current chain-catchup works
08:32 < iddo> hmm
08:33 < sipa> with headers-first synchronization, you can know there is enough PoW on top of a block before actually downloading and processing it
08:34 < iddo> i don't understand, diff-1 PoW blocks are (relatively) easy to generate, what's the rule that will cause you to ignore them instead of bloating your local copy of the blockchain with them?
08:35 < sipa> right, it won't prevent it entirely
08:35 < sipa> but right now, the largest problem is that diff-1 blocks will be downloaded and potentially processed
08:35 < sipa> but with headers-first, you'd only download and process the headers
08:36 < iddo> ahh
08:36 < sipa> until such a chain becomes the actually best total work chain
08:36 < iddo> hmm headers first is an optimization that isn't related to merkle datastruct (like MMR) for lite nodes, i think?
08:37 < sipa> not at all
08:37 < sipa> completely orthogonal
08:38 < iddo> ok, peter todd and amiller said yesterday that the MMR stuff can mitigate DoS that checkpoints currently protects against, i wonder why...
08:39 < sipa> checkpoints don't protect against a DoS, they are just there to make not-checking-all-signatures safe
08:40 < sipa> wait, no, they do protect against a dos by helpig the heuristics determine if an early block in the chain has a chance of beatig the total known PoW
08:40 < iddo> sipa: yes i mean what gmaxwell said: https://bitcointalk.org/index.php?topic=194078.msg2014204#msg2014204 (i.e. you ignore diff-1 at genesis because you already have a checkpoint)
08:41 < iddo> but then peter todd said that MMR can give this anti-DoS without checkpoints, and amiller said that the reason is that blocks have commitments to the UTXO set
08:42 < iddo> but i don't see why it helps, yet
08:43 < iddo> this is in the context of the new paper by Aviv Zohar, it seems that anti-DoS is easier with Bitcoin rules than his new rules, assuming that there are no checkpoints
08:45 < iddo> for example the most naive anti-DoS is for the Bitcoin node to have some quota and not accept more than certain amount of forks for each block, so if in the future it turns out that a competing fork is better then that node will need to ask peers for blocks that it rejected in the past
08:46 < iddo> but with the new paper, this naive anti-DoS doesn't work, i think
08:46 < iddo> (could cause netsplits that don't re-converge)
08:48 < iddo> and even if it can work with the new rules, the communication among nodes will be much greater i think
09:35 < petertodd> iddo: emphasis on *sum* tree - the MMR (or just merkle tree) lets you interactively query your peer to be sure the total sum work claimed makes sense. But yeah, even without the sum tree just working backwards from current best block is pretty good too.
09:49 < iddo> petertodd: trying to understand you... isn't that just a method to prove more efficiently that a competing fork has more weight?
09:50 < iddo> petertodd: what i don't understand, diff-1 PoW blocks are (relatively) easy to generate, what's the rule that will cause you to ignore them instead of DoS attack where you'd be bloating your local copy of the blockchain with them?
09:51 < iddo> (checkpoints do prevent this kind of DoS attack)
09:56 < iddo> it still seems to me that with Bitcoin rules to select the best chain we can have anti-DoS mechanisms (without checkpoints) against diff-1 orphans at genesis attack, while with Aviv Zohar's rules I'm not so sure
10:00 < iddo> but i'm still unclear why amiller and you said that such merkle trees remove the need for checkpoints, is it just in the context of bootstrapping new nodes without doing too much work verifying the entire history, or also in the context of anti-DoS ?
10:57 < amiller> iddo, well... you can do something like starting at SPV security and gradually validating the chain
11:05 < iddo> amiller: but not all nodes can do that, i think? the question is still whether full nodes should eliminate orphan branches or keep them, if they always eliminate then the communication can blowup?
11:07 < amiller> eventually eliminate them?
11:09 < iddo> yes i think that with Bitcoin it may be safe to eliminate old orphans (assuming no checkpoints), but with Aviv Zohar's rules, i'm not sure yet
11:09 < amiller> you may even think of it as an incentive thing, there's a tradeoff from an individuals point of view
11:09 < amiller> potentially keeping some orphans around will save on future bandwidth, but at the cost of storage now
11:10 < iddo> it's also not only about eliminating orphans that you already have, but also about rejecting new orphans, like the 1-diff at genesis attack
11:12 < iddo> with Bitcoin i think that it can be safe to reject short orphans (with small risk that you may need to request them later and waste communication), but with Aviv Zohar's rule, not sure..
12:14 < iddo> ok i summarized what i asked here, in the public thread: https://bitcointalk.org/index.php?topic=359582.msg3867074#msg3867074
12:19 < iddo> gmaxwell: with this new rule, you think that blocks need to point to all their ancestors only because of lite clients? full nodes can calculate the difficulty of a block without it having pointers to ancestors, i think?
12:20 < amiller> one question i've had is how you do efficient merging
12:20 < amiller> to make sure the same work doesn't show up in multiple places in the same tree
12:29 < iddo> amiller: btw if you can dig up #bitcoin-dev or mailing list link where you first proposed this rule, maybe they could reference you in this paper:) might be worthwhile, there's plan for followup paper too
12:38 < amiller> i send an email to the thread with the irc log from bitcoin-dev
12:39 < amiller> i wouldn't mind having an acknowledgement but i didn't develop the idea very far at all :p
12:39 < amiller> i'm really glad that someone is working on it.
12:42 < amiller> i also tried to emphasize that, it's not even that their idea isn't fine as is (we haven't argued super well that there *clearly is* a big dos attack), but that it's difficult to analyze that there are no dos attacks, so being conservative to include thing is understandable
12:43 < amiller> so if they really want to say there thing is practical and ready to implement, they should come up with some really compelling anti-dos analysis
12:44 < amiller> that's just my opinion though :o
12:46 < iddo> yes that's all true, probably difficult to analyse it in theory, trying simulations first is a good idea
14:32 < warren> gmaxwell: hm.... the previous thoughts about pruning included nodes having a random subset of the blockchain to serve to peers.  that seems good, but that may have privacy issues?
14:32 < warren> gmaxwell: you can use that to identify nodes
14:34 < gmaxwell> You can use many things to distinguish nodes already. So what about it?
14:35 < gmaxwell> You propose instead forcing nodes to use tens of gigabytes of disk space if they want to contribute at all to distributed storage?
14:35 < warren> no
14:35 < gmaxwell> It doesn't connect transactions to anything.
14:36 < warren> are there ways to obscure the subset so it is less certainly a unique identifier
14:36 < gmaxwell> I never suggested a random subset that would be stupid, I always suggested contigious quantized ranges.
14:37 < gmaxwell> (stupid because it would take a lot more data to express than just a range or two)
14:38 < warren> ok
14:43 < sipa> and be a lot harder to make sure that a particular block is available
14:44 < sipa> in particular, you'd need O(n^2) nodes that serve the same n blocks with the same probability to get equal chance a particular block is available
14:45 < warren> when I connect to random bitcoin peers now, it seems that often many of the peers are useless, too slow or fake
14:45 < iddo> in the future we can have SCIP proofs for UTXO "checkpoints", so less need to serve old blocks
14:46 < warren> hmm key birthdates would help
14:57 < gmaxwell> iddo: perhaps, we need scip that doesn't need a trusted CRS.. and prover performance that at least makes it possible to run.
14:58 < gmaxwell> I don't know if we'll have that in 2 years, 5 years, or 10 years.
15:01 < iddo> proof size is logarithmic in num of computation steps (computation == verifying the history, maybe optimized by composing with prev SCIP checkpoints), the issue is how big are the constants of this log size proof....
15:01 < iddo> this is for the variant without CRS
15:08 < phantomcircuit> warren, you can already uniquely identify peers fairly reliably
15:08 < phantomcircuit> they give everybody the same version nonce iirc
15:49 < gmaxwell> iddo: well for checkpoints it can be rather large, eventually it will be small relative to the blockchain. :)  But I worry about computing it just being infeasable. If it costs $1k in compute time thats doable, if it costs $1m in compute time thats right out.
15:56 < amiller> hrm, what should be the parts of a bitcoin gambling tool that plays through games of iddo's protocol?
15:57 < amiller> i am thinking it should be a self contained wallet
15:57 < amiller> because i would want to have some notion of 'sending coins to my gambling wallet' rather than integrating it with my personal bitcoind or something big like that
15:58 < amiller> really i would want this to be SPV something, it's not particularly supposed to provide bandwidth to anyone
16:05 < amiller> i guess i should study bitcoinj
16:33 < gmaxwell> iddo: I really wish people with implementations of snarks for C would release something... there are 'small' applications we could use the stuff for right away. Like proving ownership of a bitcoin without disclosing which bitcoin you own.
16:35 < sipa> i've been out for too long... how does snarks relate to scip?
16:37 < maaku> sipa: scip is snarks
16:37 < maaku> SNARKS is the general term
16:37 < maaku> SCIP is what Eli et al call their implementation of a SNARKS system
16:37 < maaku> gmaxwell: correct me if i'm wrong
16:39 < gmaxwell> sipa: SCIP is just what Eli et all call their SNARKS for C stuff.
16:40 < sipa> ok
16:40 < sipa> are they abbreviations of something?
16:40 < gmaxwell> SNARK = succinct argument of knowledge  (sometimes zk-SNARK when its also zero knowledge). succinct ~meaning that its sublinear in the witness size, argument because they are only computationally sound, they're not a proof.
16:41 < gmaxwell> (there is some proof that you cannot produce a proof (perfectly sound) which is succinct, the best you can do is computationally sound)
16:43 < gwillen> gmaxwell: is there a 30-second explanation of what 'computationally sound' means in this context?
16:44 < gmaxwell> gwillen: computationally sound basically means a cryptographic assumption, e.g. someone who can search 2^256 spaces can produce a proof which you believe is valid but it's not.
16:44 < gmaxwell> Vs a perfectly sound proof where you can never be fooled even by an unbounded attacker.
16:45 < gmaxwell> (or, if the cryptographic assumption fails— discrete log is easy, etc. depends on how the system is constructed which assumptions are at play. Or of P=NP..— then the system allows fake proofs)
16:46 < gwillen> gmaxwell: ahhhh, clever.
16:48 < gmaxwell> There is a similar set of levels of zero knoweldge.  Some things have perfect zero knoweldge where an unbounded attacker with unbounded examples of your proof learns nothing,  statistical zero knoweldge where the distribution of answers is negligibly different from 'fake' answers so at most they learn very little, and varrious computational assumptions for zero knoweldge. e.g. where they learn nothing unless they can solve some hard ...
16:48 < gmaxwell> ... problem.
16:48  * gwillen nods
16:48 < gmaxwell> Interestingly there seems to be some tradeoff, it seems that many of the systems with perfect soundness can only offer computational zero knoweldge, and vice versa.
16:49 < gwillen> interesting.
16:49 < gmaxwell> For something like blockchain proofs we don't care about zero knoweldge at all, thought we do care if the proofs are small.
16:51 < gwillen> gmaxwell: is this counting or not counting 'I prove that I have a bitcoin without revealing which one' as zk?
16:51 < gwillen> it feels zk-flavored to me
16:51 < gmaxwell> for that you'd want zk, indeed— though computationally sound ZK is probably fine for that.
16:51  * gwillen nods
16:52 < gwillen> 'you can break my anonymity if you can do a 256-bit search' is certainly an improvement on what we have now. :-)
16:53 < gmaxwell> likewise, for something like zerocoin you need zk to hide which coins you're spending.  So we do have applications for ZK.  Things like my contigent payment protocol need fairly strong ZK since the payer can rob the payee if the ZK isn't strong.
16:54 < gwillen> interesting.
16:56 < gmaxwell> then you have the whole axis of publically verifyable vs designated verifier.
16:57 < gmaxwell> A bunch of these systems work easiest where there is a single verifier who generates a challenge, and a single prover.  Thats desigated verifier.
16:57 < iddo> gmaxwell: from what i know there is no (working) code yet for non-CRS SCIP, but it's being work on... about CRS SCIP, obviously they will release code with their lame zerocoin altcoin:( but i'll continue to inquire and see if i have updates
16:58 < gmaxwell> Publically verifyable is like a digital signature.  Then a number of these systems are "publically verifyable in the CRS model" which is basically publically verifyable but only if everyone has a magical trusted string.
16:59 < gwillen> gmaxwell: what are the requirements on the CRS?
17:01 < gmaxwell> gwillen: depends on the system, most of the CRS models are effectively structured like public key cryptography where the CRS gives you public keys for a trapdoor permutation constructed so that you can encrypt your proof but still check that its valid. if someone knows the randomness underlying the CRS they can trivially create fake proofs.
17:01 < gmaxwell> the crs generation process in that case just ends up looking like generating a bunch of random public keys, more or less.
17:02 < gwillen> gmaxwell: is this the sort of thing where, if we knew that God generated the CRS and threw away the generation parameters, the system would be fine?
17:02 < gmaxwell> Yes.
17:02 < gwillen> Huh.
17:03 < gmaxwell> some of the stuff in the CRS model also loses its zero knoweldge to god, so you can't necessarily safely use it in the designated verifier case where the designated verifier produces the CRS. (annoyingly I find the papers often unclear exactly what the threat model(s) they work under)
17:03 < gmaxwell> (though anythin with a succinct proof is probably still ZK to god, simply because there is so little information at the end)
17:04 < gmaxwell> some people talking about this stuff have suggested you could use multiparty computation to compute the CRS in a way that God is distributed.
17:05 < gmaxwell> But it still would leave you that if the majority (or all) of the multiparty computation players cheated they'd know the parameters.
17:06 < gmaxwell> Also, many of the active-secure multiparty computation systems only achieve security via zero knoweldge proofs ... so you can end up with circular security. :)
17:06 < gmaxwell> E.g. you can take a passive-secure multiparty computation system, — one which is only secure if the players follow the protocol— and boost it to active security (secure regardless of the players) by having the player use proofs to prove they did their computation according to the rules.
17:08 < phantomcircuit> gmaxwell, is there anything preventing someone from mining a version=3 block?
17:08 < phantomcircuit> other than just stupidity
17:08 < gmaxwell> phantomcircuit: nope.
17:08 < phantomcircuit> is it at least discouraged?
17:09 < gmaxwell> it shouldn't be done, because we will want to use the version field for future changes, and if people are actively producing blocks with other versions it will make that impossible.
17:17 < andytoshi> i like this business of referring to an unbounded attacker as god
17:17 < andytoshi> #bitcoin-wizards could use some wizardly lingo
17:19 < sipa> let's call Him Laplace's Demo
17:19 < sipa> hmm, i actually wanted tot type Demon, but Demo isn't too bad either
17:20 < gwillen> he is Laplace's Demon, Laplace's Demo is when he shows you that your system is insecure.
17:20 < gmaxwell> I wonder if in some of the holographic universe theories if knowing the path of a single partical with enough detail actually describes the entire universe. :)
17:21 < gmaxwell> particle*
17:21 < gwillen> gmaxwell: certain facts about our actual universe makes me like the theory that this isn't true because it has only limited resolution
17:21 < gwillen> (i.e. that you can't in fact get the entire universe from the path of a particle)
17:22 < gmaxwell> gwillen: e.g. what if there is only one universe consistent with our laws of physics and the existance of particle X.
17:22  * gwillen nods
17:27 < edulix> http://www.michaelnielsen.org/ddi/how-the-bitcoin-protocol-actually-works/ now in slashdot btw
17:30 < edulix> which makes me wonder, is there any book on bitcoin with internal details etc
17:39 < michagogo|cloud> edulix: yes, it's online at https://github.com/bitcoin/bitcoin
17:39 < michagogo|cloud> (and at http://bitcoin.it)
17:43 < edulix> nice
17:50 < edulix> hehe the author of that post doesn't understand why double spend is fixed the way is fixed in bitcoin
17:52 < Emcy> is it true there were altcoins with fixed difficulty?
17:53 < gmaxwell> Emcy: liquidcoin had that... didn't last long.
17:54 < Emcy> what was the rationale of that
17:56 < phantomcircuit> gmaxwell, what block shunning is there?
17:57 < phantomcircuit> or is that just txs
17:57 < phantomcircuit> ;;seen jgarzik
17:57 < phantomcircuit> no gribble
19:45 < andytoshi> Emcy: no doubt "fairness"
19:46 < andytoshi> or plain old silliness :)
22:40  * andytoshi-logbot is logging
--- Log closed Sun Dec 08 00:00:40 2013