The description dances around the issue, but what they are basically saying is this: the work needed to successfully attack Bitcoin is proportional to the total work done by all Bitcoin participants. That is an amount of work that is polynomial in the parameters of the system.
Seems odd to describe this as a polynomial-time attack, and I would argue incorrect to describe the result as "broken crypto", as this has little to do with the cryptographic components of Bitcoin, and is more a fundamental design limitation.
As a workaround, merchants will just demand more confirmations for higher-valued transactions, like waiting for a check to clear. Checks and physical cash also wouldn't meet your definition of formal security, but seem to work in practice.
"Seems odd to describe this as a polynomial-time attack"
Is there some part that does not run in polynomial time in the parameters of the system?
"I would argue incorrect to describe the result as "broken crypto", as this has little to do with the cryptographic components of Bitcoin, and is more a fundamental design limitation."
Cryptography is not limited to hash functions and digital signatures (the two primary cryptographic primitives used in Bitcoin). The "broken crypto" refers to the fact that Bitcoin fails to meet the security definition for digital cash, a type of cryptosystem. Moreover, Bitcoin is not secure as a multiparty computation protocol (also a kind of crypto) against malicious parties, as the attacker's work is polynomial in the system's parameters.
One should not make the mistake of trying to separate the security of cryptographic building blocks from the security of a system as a whole. My "pet" example of this fallacy is "robust" encryption. In a nutshell, an encryption system is "robust" if only the intended recipient can receive a valid message. Using PGP to sign and then encrypt a message is not robust, even though the signature system, hash functions, and ciphers in PGP are secure as signature systems, hash functions, and ciphers. The reason is pretty clear: if you send a signed+encrypted message to me, I can decrypt it, encrypt the signed message for someone else, and then send them a valid message.
For most PGP users, robustness is not an important security property; usually, the recipient's name or some other identifying detail will be clearly written in the message. On the other hand, for Bitcoin, the protection against double spending is absolutely necessary; a polynomial time double spending attack on Bitcoin is very bad.
"As a workaround, merchants will just demand more confirmations for higher-valued transactions"
Which only forces the attacker to make a polynomial increase in their work. An attacker only needs to do as much work as the sum of the work done by all other participants in the system to remove any workaround. Right now, that is well within the reach of governments, banks, and perhaps the larger criminal enterprises of this world.
"Checks and physical cash also wouldn't meet your definition of formal security, but seem to work in practice."
It would not be the first time someone has proposed that digital cash go beyond what is possible with physical cash (see Page 2, Property (e)):
Comments
This attack:
https://en.bitcoin.it/wiki/Double-spending#Brute_force_attac...
The description dances around the issue, but what they are basically saying is this: the work needed to successfully attack Bitcoin is proportional to the total work done by all Bitcoin participants. That is an amount of work that is polynomial in the parameters of the system.
Seems odd to describe this as a polynomial-time attack, and I would argue incorrect to describe the result as "broken crypto", as this has little to do with the cryptographic components of Bitcoin, and is more a fundamental design limitation.
As a workaround, merchants will just demand more confirmations for higher-valued transactions, like waiting for a check to clear. Checks and physical cash also wouldn't meet your definition of formal security, but seem to work in practice.
"Seems odd to describe this as a polynomial-time attack"
Is there some part that does not run in polynomial time in the parameters of the system?
"I would argue incorrect to describe the result as "broken crypto", as this has little to do with the cryptographic components of Bitcoin, and is more a fundamental design limitation."
Cryptography is not limited to hash functions and digital signatures (the two primary cryptographic primitives used in Bitcoin). The "broken crypto" refers to the fact that Bitcoin fails to meet the security definition for digital cash, a type of cryptosystem. Moreover, Bitcoin is not secure as a multiparty computation protocol (also a kind of crypto) against malicious parties, as the attacker's work is polynomial in the system's parameters.
One should not make the mistake of trying to separate the security of cryptographic building blocks from the security of a system as a whole. My "pet" example of this fallacy is "robust" encryption. In a nutshell, an encryption system is "robust" if only the intended recipient can receive a valid message. Using PGP to sign and then encrypt a message is not robust, even though the signature system, hash functions, and ciphers in PGP are secure as signature systems, hash functions, and ciphers. The reason is pretty clear: if you send a signed+encrypted message to me, I can decrypt it, encrypt the signed message for someone else, and then send them a valid message.
For most PGP users, robustness is not an important security property; usually, the recipient's name or some other identifying detail will be clearly written in the message. On the other hand, for Bitcoin, the protection against double spending is absolutely necessary; a polynomial time double spending attack on Bitcoin is very bad.
"As a workaround, merchants will just demand more confirmations for higher-valued transactions"
Which only forces the attacker to make a polynomial increase in their work. An attacker only needs to do as much work as the sum of the work done by all other participants in the system to remove any workaround. Right now, that is well within the reach of governments, banks, and perhaps the larger criminal enterprises of this world.
"Checks and physical cash also wouldn't meet your definition of formal security, but seem to work in practice."
It would not be the first time someone has proposed that digital cash go beyond what is possible with physical cash (see Page 2, Property (e)):
http://pdf.aminer.org/000/120/358/universal_electronic_cash....