4 ms·

What you are saying is not true. It is possible in other settings to create fully decentralized protocols that are secure even if all but one of the parties is

• mindslight 13y ago
  I'm using coordination problem in purely technical protocols sense. Can you be specific about which other decentralized protocols you're referring to? I agree that many protocols fit your description, but I can't see how any of them could be both partition-tolerant and prevent conflicting transactions (double spends in this case). It seems like partitions lead to honest disagreements about what happened first, and these are indistinguishable from an attacker. To reconcile these disagreements, we need some majority-metric so both sides can agree which one wins out.
  • betterunix 13y ago
    "Can you be specific about which other decentralized protocols you're referring to?" Well, let's just take this (random Google result) as an example: http://groups.csail.mit.edu/cis/pubs/shafi/2002-disc.pdf http://groups.csail.mit.edu/cis/pubs/shafi/2002-disc.pdf There you have a protocol that can tolerate honest parties aborting and can tolerate a malicious majority. Partitioning is a slightly different problem than aborting, of course, but that is beside the point. My point was that there is nothing inherent in secure computation that requires you to allow polynomial time attacks or even to require an honest majority. It is hard to excuse a system that is supposed to be based on cryptography that fails to provide anything remotely close to the security we expect out of cryptosystems. Really there is a deeper problem here, which is the lack of a well-formed security definition for Bitcoin. You use terms like "double spending" but those terms are very poorly defined for Bitcoin; I would go further and say that there may not even be such a definition, given that there is nothing wrong with a Bitcoin user spending more money than they receive (due to "mining"). It is impossible to apply the security definitions of other digital cash systems, which invoke a bank. Underlying all this is the lack of a definition of money; Bitcoin dispenses with economic theory but fails to provide a satisfactory replacement.
    • mindslight 13y ago
      (Disclaimer: I'll admit to not having the best understanding of the applicability of secure MPC. For instance, seeing things about parallel composability, I have a hard time fathoming how multiple instances of something couldn't be secure in parallel. So I can only conclude the papers are written from a much different perspective than I have.) > there is nothing inherent in secure computation that requires you to allow polynomial time attacks or even to require an honest majority But, that paper comes right out and says: "On the other hand, as we have mentioned, in the range of t [malicious parties] ≥ n/2 [half of total parties] the definitions of secure computation do not imply Byzantine agreement." In order to have a currency (fungibility), we need widespread agreement as to what constitutes value. Several nodes saying a transaction is good aren't enough - all nodes must agree. The hard part is achieving quorum of the majority of nodes, after which the remaining nodes acquiesce and follow (even if they vehemently disagree! that is, assuming they want to keep transacting with everyone else. also notice we've left out any judgement of honesty) But also, what constitutes a "node"? If we aren't going to have a trusted party handing out limited identities, we need some non-forgeable ability. Bitcoin uses computing power measured in SHA2s. If you compute twice the hashes, you count as twice the nodes for purposes of quorum. You're free to explore a different system for avoiding Sybil attacks, but it's still going to come out as a one-to-one balance between "honest" and "dishonest" nodes.
      • betterunix 13y ago
        "For instance, seeing things about parallel composability, I have a hard time fathoming how multiple instances of something couldn't be secure in parallel." A good, intuitive example is this: I personally cannot win against a Chess grandmaster or even play to a draw; if I play two games in sequence, I will lose both times. However, I can guarantee that I can either win a game or draw two games if I am allowed to play two grandmasters simultaneously, one as white and one as black. I can simply copy the moves from one board to the other, and each grandmaster will be forced to play against another grandmaster (but they will be playing against me, and I can claim to win half the games I play against grandmasters -- much better than I can do I my own!). "In order to have a currency (fungibility), we need widespread agreement as to what constitutes value." At a basic level, what we really need is a definition of validity for our money. In the case of gold as currency, for example, validity is defined in terms of chemistry -- weights of a particular element are valid as money. For fiat currencies validity is defined via the law, by a government. In the digital cash systems developed by the cryptography research community, money is valid if the bank will accept it for deposit. The problem with Bitcoin is that validity is not well-defined and can change without warning. There is a vague notion that money is valid if everyone agrees that it is valid, but that agreement can be invalidated by a single party that happened to have done a lot of computation. Security in Bitcoin is equally vague -- you use terms like "double spending," but what does that even mean (rigorously)? "If we aren't going to have a trusted party handing out limited identities," It is worth mentioning that in online digital cash protocols (like Chaum's), there is no need for an authority on identities, or even for identities. The withdrawal protocol involves blind signatures, without a need for identities, and the bank could simply accept a cash payment for the digital cash. The payment protocol requires that the merchant verify the validity of the tokens with the bank, but rather than deposit, the bank could engage in a withdrawal protocol with the merchant trading the deposited tokens for withdrawn tokens, allowing the merchant to spend the money further. Sure, it sucks to have to be connected to a payment processor, but that is not much worse than being connected to the Bitcoin network, or to a Bitcoin exchange. "If you compute twice the hashes, you count as twice the nodes for purposes of quorum" More important: if you can compute hashes twice as fast, you get twice as much of a vote. If you can compute hashes asymptotically faster, your power in the network will keep increasing. There is no reason that you cannot compute SHA2 hashes asymptotically faster than I can -- nothing about the security of a hash function requires that all implementations have identical running times. There's the rub, in a nutshell: you are relying on the inability of the adversary to compute lots of hashes, but simultaneously demanding that the honest parties compute lots of hashes.