4 ms·

Unfortunately, the meaning of "double spending" is exceedingly vague for Bitcoin; there is no formal and precise definition. The systems developed by cryptogra

Unfortunately, the meaning of "double spending" is exceedingly vague for Bitcoin; there is no formal and precise definition. The systems developed by cryptography researchers invoke a central issuer of currency in their security definitions, which is useless for Bitcoin.

javert 14y ago
How is the meaning of "double spending" vague? It means spending the same units of a crypto-currency more than once. If you can do it, there is a flaw in your crypto-currency. > The systems developed by cryptography researchers invoke a central issuer of currency in their security definitions, which is useless for Bitcoin. The first part of that sentence is not completely true, because Bitcoin itself was (presumably) developed by cryptography researchers.
- rubinelli 14y ago
  Here's a thought experiment: what if a random chance of "double spending" was built into the cryptocurrency? Then people would have an incentive to make the money circulate, and you could calibrate it to prevent deflation. (Obviously, it would be meaningless if people could just move money from wallet to the other.)
  - javert 14y ago
    That's a pretty novel idea, which would probably be appreciated by the (small) community of people who have a problem with the "deflationary" nature of bitcoins and are actually interested in doing bitcoin forks.
- betterunix 14y ago
  "How is the meaning of "double spending" vague? It means spending the same units of a crypto-currency more than once." First of all, that is not a good definition, since it rules out the possibility of a unit of currency "coming back" to the party that spent it (imagine if I gave you a dollar, and then you were not allowed to give it back to me). It also fails to rule out the possibility of dividing one 1BTC unit into two 0.75BTC units, which is another form of double spending. There are deeper problems too. You say that if you "can" do it, it is a security problem, but there is no restriction on the attacker's computing power. What if the attacker forges ECDSA signatures? What if the attacker finds SHA256 collisions? What if the attacker computes a longer block chain, which is a polynomial time problem, reversing his transaction and getting the chance to spend the money again? The reason I said the security notion is vague is that there is no precise definition that Bitcoin actually achieves. If someone can develop one, and if it actually captures a meaningful notion of security, great! So far, no such definition exists. "The first part of that sentence is not completely true, because Bitcoin itself was (presumably) developed by cryptography researchers." I seriously doubt that, given that the original Bitcoin paper made absolutely no mention of the decades of previous work on digital cash that preceded it, nor any of the work on secure multiparty computation, nor did the paper give a security definition, nor did the author seem to be bothered by the fact that there is a polynomial-time attack on the system. It reads like a paper written by cryptography amateurs or enthusiasts, the sort of people who make most of the posts in sci.crypt and comp.compression. In a pedantic sense, Bitcoin is the product of research, but if the term "researcher" means anything beyond "human being," I think it is fair to draw the line at being familiar with and building on previous work. [Edit: Of course, that definition of "researcher" is not quite what we want, since it does not account for people who open entirely new fields. That is a rare edge case, however, and the issue was whether or not Satoshi was a researcher in an already established and well-developed field.]
  - wmf 14y ago
    For Bitcoin, double-spending would probably be defined as the same txout being spent in two different confirmed transactions. Perhaps this is so obvious that people consider it not worth explicitly stating.
    - betterunix 14y ago
      That is still not precise enough to be used in a rigorous analysis. Can the adversary solve exponential time problems to perform such transactions (and for that matter, exponential in what parameters of the system?)? Can the adversary collude with other parties in the system? How many parties can the adversary collude with? Without these sorts of details, it is very hard to rigorously analyze a system. "Perhaps this is so obvious that people consider it not worth explicitly stating" If the security definition is not explicitly stated, it is very hard to analyze whether or not the system is secure. How do we even talk about security without defining our terms? There is a polynomial-time algorithm for "reversing" a Bitcoin transaction and spending your money again that is detailed in the original Bitcoin paper -- does that mean that Bitcoin is insecure (I would say yes, but it seems that most Bitcoin proponents say no)? Without a definition of security, it is hard to say. There is also the matter of determining whether or not Bitcoin's security meets my needs. As a simple example, consider the ElGamal encryption system. It is secure -- but only against chosen plaintext attacks. If you need a system that is secure against adaptive chosen ciphertext attacks, ElGamal is probably the wrong choice (you need Cramer-Shoup). With Bitcoin, however, there is no clear security definition, so how does one even decide if Bitcoin satisfies their security needs?
      - javert 14y ago
        > That is still not precise enough to be used in a rigorous analysis. I think that is a precise definition of "double spend" in bitcoin. Do you agree with that definition? As for all the other stuff you're talking about re: polynomial algorithms, collusion, etc.... I am just puzzled that you are bringing all that stuff up. It is widely known that bitcoin is resilient to any attempt to double-spend unless there is a coordinated attack by greater than 50% of the total hashing power. And double-spend is the _only_ attack at the distributed algorithm level. Can you comment on the above paragraph? I mean, were you not aware of the 50% issue, or were you aware of it but have a problem with it? And do you agree that double-spend is the only kind of attack at the algorithmic level? Of course, there is always DDoSing the peers at the protocol layer, and stuff like that, but I think we can agree that that is not what we are interested in discussing. And then there is the crypto level, which you bring up by mentioning ElGamal. Bitcoin uses ECDSA, but only for signing; nothing is encrypted. So one can talk about whether ECDSA is breakable, but I'm not losing any sleep over it, personally.
erikpukinskis 14y ago
If transaction A, drawing from source G, is confirmed six times in blockchain M, the longest blockchain, with length 20, and transaction B shows up, also drawing from source G, but confirmed in blockchain fork N, and N becomes longer then M, then that is a double spend. Edit: changed one to six.
- betterunix 14y ago
  OK, but Bitcoin allows that to happen; in the original Bitcoin paper, a polynomial time algorithm for doing exactly what you described is presented. Even if we accept that definition of double spending, it is not clear how that is useful for formalizing Bitcoin's security. How can you rule out someone computing a longer block chain, when doing so involves simply duplicating the work done by the rest of the parties in the system? What actually stops someone from doing this? In other words, under your definition, what does it mean to be secure against double spending?
  - javert 14y ago
    > How can you rule out someone computing a longer block chain, when doing so involves simply duplicating the work done by the rest of the parties in the system? What actually stops someone from doing this? I responded to another comment from you elsewhere, and I hate to confuse things by having one conversation in two places, but this is a really good question, and there is a straightforward answer. To make a longer blockchain, you have to have enough computing power to "catch up" to all the other people mining bitcoins, and then mine faster than they are. So, you have to have > 50% of the total hashing power. If you look into the mining "business," I think you will become convinced that only a nation-state or maybe Google could perform this kind of attack right now, and once ASIC mining technology is widely diffused, even that would be difficult. The "6 confirmations" thing the grandparent said is kind of arbitrary, but that is the number of blocks that bitcoin devs widely agree is enough to wait before you can be "effectively certain" that your transaction is in the longest block chain, and always will be. So that's how long you wait before handing over the keys when somebody purchases your mega-yacht with bitcoin. By "kind of arbitrary" I mean, in the context grandparent used it. If you do the math (as is given somewhere near the end of the bitcoin white paper), that is where you start approaching a 0% chance of the transaction not ending up in the longest chain.

javert 14y ago

How is the meaning of "double spending" vague? It means spending the same units of a crypto-currency more than once. If you can do it, there is a flaw in your crypto-currency. > The systems developed by cryptography researchers invoke a central issuer of currency in their security definitions, which is useless for Bitcoin. The first part of that sentence is not completely true, because Bitcoin itself was (presumably) developed by cryptography researchers.

rubinelli 14y ago
Here's a thought experiment: what if a random chance of "double spending" was built into the cryptocurrency? Then people would have an incentive to make the money circulate, and you could calibrate it to prevent deflation. (Obviously, it would be meaningless if people could just move money from wallet to the other.)
- javert 14y ago
  That's a pretty novel idea, which would probably be appreciated by the (small) community of people who have a problem with the "deflationary" nature of bitcoins and are actually interested in doing bitcoin forks.
betterunix 14y ago
"How is the meaning of "double spending" vague? It means spending the same units of a crypto-currency more than once." First of all, that is not a good definition, since it rules out the possibility of a unit of currency "coming back" to the party that spent it (imagine if I gave you a dollar, and then you were not allowed to give it back to me). It also fails to rule out the possibility of dividing one 1BTC unit into two 0.75BTC units, which is another form of double spending. There are deeper problems too. You say that if you "can" do it, it is a security problem, but there is no restriction on the attacker's computing power. What if the attacker forges ECDSA signatures? What if the attacker finds SHA256 collisions? What if the attacker computes a longer block chain, which is a polynomial time problem, reversing his transaction and getting the chance to spend the money again? The reason I said the security notion is vague is that there is no precise definition that Bitcoin actually achieves. If someone can develop one, and if it actually captures a meaningful notion of security, great! So far, no such definition exists. "The first part of that sentence is not completely true, because Bitcoin itself was (presumably) developed by cryptography researchers." I seriously doubt that, given that the original Bitcoin paper made absolutely no mention of the decades of previous work on digital cash that preceded it, nor any of the work on secure multiparty computation, nor did the paper give a security definition, nor did the author seem to be bothered by the fact that there is a polynomial-time attack on the system. It reads like a paper written by cryptography amateurs or enthusiasts, the sort of people who make most of the posts in sci.crypt and comp.compression. In a pedantic sense, Bitcoin is the product of research, but if the term "researcher" means anything beyond "human being," I think it is fair to draw the line at being familiar with and building on previous work. [Edit: Of course, that definition of "researcher" is not quite what we want, since it does not account for people who open entirely new fields. That is a rare edge case, however, and the issue was whether or not Satoshi was a researcher in an already established and well-developed field.]
- wmf 14y ago
  For Bitcoin, double-spending would probably be defined as the same txout being spent in two different confirmed transactions. Perhaps this is so obvious that people consider it not worth explicitly stating.
  - betterunix 14y ago
    That is still not precise enough to be used in a rigorous analysis. Can the adversary solve exponential time problems to perform such transactions (and for that matter, exponential in what parameters of the system?)? Can the adversary collude with other parties in the system? How many parties can the adversary collude with? Without these sorts of details, it is very hard to rigorously analyze a system. "Perhaps this is so obvious that people consider it not worth explicitly stating" If the security definition is not explicitly stated, it is very hard to analyze whether or not the system is secure. How do we even talk about security without defining our terms? There is a polynomial-time algorithm for "reversing" a Bitcoin transaction and spending your money again that is detailed in the original Bitcoin paper -- does that mean that Bitcoin is insecure (I would say yes, but it seems that most Bitcoin proponents say no)? Without a definition of security, it is hard to say. There is also the matter of determining whether or not Bitcoin's security meets my needs. As a simple example, consider the ElGamal encryption system. It is secure -- but only against chosen plaintext attacks. If you need a system that is secure against adaptive chosen ciphertext attacks, ElGamal is probably the wrong choice (you need Cramer-Shoup). With Bitcoin, however, there is no clear security definition, so how does one even decide if Bitcoin satisfies their security needs?
    - javert 14y ago
      > That is still not precise enough to be used in a rigorous analysis. I think that is a precise definition of "double spend" in bitcoin. Do you agree with that definition? As for all the other stuff you're talking about re: polynomial algorithms, collusion, etc.... I am just puzzled that you are bringing all that stuff up. It is widely known that bitcoin is resilient to any attempt to double-spend unless there is a coordinated attack by greater than 50% of the total hashing power. And double-spend is the _only_ attack at the distributed algorithm level. Can you comment on the above paragraph? I mean, were you not aware of the 50% issue, or were you aware of it but have a problem with it? And do you agree that double-spend is the only kind of attack at the algorithmic level? Of course, there is always DDoSing the peers at the protocol layer, and stuff like that, but I think we can agree that that is not what we are interested in discussing. And then there is the crypto level, which you bring up by mentioning ElGamal. Bitcoin uses ECDSA, but only for signing; nothing is encrypted. So one can talk about whether ECDSA is breakable, but I'm not losing any sleep over it, personally.

erikpukinskis 14y ago

If transaction A, drawing from source G, is confirmed six times in blockchain M, the longest blockchain, with length 20, and transaction B shows up, also drawing from source G, but confirmed in blockchain fork N, and N becomes longer then M, then that is a double spend. Edit: changed one to six.

betterunix 14y ago
OK, but Bitcoin allows that to happen; in the original Bitcoin paper, a polynomial time algorithm for doing exactly what you described is presented. Even if we accept that definition of double spending, it is not clear how that is useful for formalizing Bitcoin's security. How can you rule out someone computing a longer block chain, when doing so involves simply duplicating the work done by the rest of the parties in the system? What actually stops someone from doing this? In other words, under your definition, what does it mean to be secure against double spending?
- javert 14y ago
  > How can you rule out someone computing a longer block chain, when doing so involves simply duplicating the work done by the rest of the parties in the system? What actually stops someone from doing this? I responded to another comment from you elsewhere, and I hate to confuse things by having one conversation in two places, but this is a really good question, and there is a straightforward answer. To make a longer blockchain, you have to have enough computing power to "catch up" to all the other people mining bitcoins, and then mine faster than they are. So, you have to have > 50% of the total hashing power. If you look into the mining "business," I think you will become convinced that only a nation-state or maybe Google could perform this kind of attack right now, and once ASIC mining technology is widely diffused, even that would be difficult. The "6 confirmations" thing the grandparent said is kind of arbitrary, but that is the number of blocks that bitcoin devs widely agree is enough to wait before you can be "effectively certain" that your transaction is in the longest block chain, and always will be. So that's how long you wait before handing over the keys when somebody purchases your mega-yacht with bitcoin. By "kind of arbitrary" I mean, in the context grandparent used it. If you do the math (as is given somewhere near the end of the bitcoin white paper), that is where you start approaching a 0% chance of the transaction not ending up in the longest chain.