5 ms·

How can a bug in the implementation be a security risk? Aren't the artefacts of bitcoin (I don't know the correct terminology) cryptographically unambiguous, co

How can a bug in the implementation be a security risk? Aren't the artefacts of bitcoin (I don't know the correct terminology) cryptographically unambiguous, completely independent of the implementation used to create them? The "problem" with HTML incompatibilities is that there is room for plenty of ambiguity in both standard and implementation, without compromising the fundamental mission of the users of the protocol (rendering web content).

betterunix 14y ago
"How can a bug in the implementation be a security risk?" It could fork the block chain: http://bitcoin.org/chainfork.html http://bitcoin.org/chainfork.html
Strilanc 14y ago
If one type of client accepts a particular block and another doesn't, the block chain splits and things go badly. This literally happened one month ago, because of a bug being fixed: https://bitcointalk.org/index.php?topic=152030.0 https://bitcointalk.org/index.php?topic=152030.0
- mseebach 14y ago
  Ugh, that is very bad. I had much higher thoughts of the cryptographic purity of BTC.
  - betterunix 14y ago
    The cryptographic purity of a system without a formal security definition and for which there is a known polynomial time attack? I think you were bound to be disappointed...
  - fianchetto 14y ago
    Bitcoin is cryptographically pure but programmers aren't quite as perfect.
    - betterunix 14y ago
      What is the security definition?
      - nullc 14y ago
        https://socrates1024.s3.amazonaws.com/consensus.pdf https://socrates1024.s3.amazonaws.com/consensus.pdf
        betterunix 14y ago
        I think this paper presents a poor security definition for Bitcoin, at the very least because it assumes a non-adaptive adversary (i.e. the adversary cannot change which nodes it controls over time). That is not how things work in the real world; in the real world, the adversary will keep increasing his computational power (the number of "pawns") until his attack is successful. I am also skeptical of a computational model that assumes the adversary's computation is somehow synchronized with the honest parties'; that is not even remotely realistic, and it is very weak. In other words, that paper does not tell us anything we did not already know: Bitcoin is secure only if nobody does as much computational work as the rest of the network combined (though there may be other attacks on the protocol that have not yet been discovered). If anything, this paper is a step towards formalizing a security definition for a protocol that is similar to Bitcoin, or a step towards proving that there will always be a polynomial time attack against such protocols (as was the case with Merkle's puzzles).
        nullc 14y ago
        It assumes an anonymous protocol. The identity of the nodes does not matter. > a step towards proving that there will always be a polynomial time attack against such protocols I had considered that to be the definition of a majority consensus. I find it sort of surprising that you'd think otherwise. Lets just assume that some alternative protocol has a property where a an attack with the >50% computing power would be ignored. Then it follows that it would also allow an attack with <50% computing power— unless "attack" could be detected as a function of network state, in which case any sane system would just ignore those entirely— as Bitcoin does, e.g. a transaction outputting more coins than it inputs is ignored regardless of the hashpower— so they're not the kind of attacks we're talking about here. Even if you dispense with all the crypto-computing-power-mumbo-jumbo: A _consensus_ ultimately depends on linear energy applied to an attack. Lets imagine a magical version of Bitcoin solves the sybil problem completely and counts the consensus of _users_ instead of computing power. China (for example) could reorganize the consensus by spending a lot of energy to manufacturer a lot of additional people. So long as the attacker put in more energy mining people than all the honest participants they'd always eventually win.
  - nullc 14y ago
    Bitcoin is a distributed consensus algorithm. Software which implements a subtly different algorithm might be able to join the consensus until some case arises which triggers the difference, after that consensus between the implementations would be impossible. Unfortunately, it's rather hard to demonstrate that two dissimilar complex programs actually implement exactly the same function. This is doubly true because performance is very important, so some techniques that might help— e.g. define a kind of abstract turing machine, write the rules for the distributed algorithm in its language, then different implementations use the same rules and only have to prove their turing machine implementation is functionally identical— aren't readily available. It can be hard to gain confidence through testing because some of the most important rules are for cases which are forbidden, so these cases will not show up on the production network— they only happen when an attacker produces them. There are an infinite number (subject to memory, and already the function input is gigabytes of data) of valid and invalid cases, so exhaustive testing of the whole function is not possible. They can also arise out of implicit behavior, "what happens when this value overflows?", "what is the maximum size of this structure", etc. This is further complicated by the fact that Bitcoin implementations use third party code that wasn't written with this kind of must-have-exact-behavior in mind. The reference implementation uses things like OpenSSL's crypto and bignums, various boost data structures, BDB (previously, now leveldb)... and subtle potentially undocumented and unknown behavior from this third party code may be leaking into the definition of the consensus algorithm. The reference implementation has been slowly disentangling these dependencies, but things like the hidden BDB locking limitations (which depend on the layout of the database on disk) are easy to miss. (Third party code isn't just a reference implementation issue, e.g. BitcoinJ's full node code has had algorithm inconsistencies arising out of undocumented behavior in a database library it uses) Satoshi's answer for this was that there should only be one implementation of the full node software. However, "create your own Bitcoin implementation" seems to be the new millennium's "create an IRC client" so it seems that this is unrealistic... and there have been more than a half dozen attempts (including two nearly complete ones in java, two in C, three in C++, one in Haskell, one in erlang, one (two?) in javascript, as well as several non public ones (including one in ruby, I think)).
    - mechanical_fish 14y ago
- mechanical_fish 14y ago
  From the linked post: If you're a merchant: please stop processing transactions until the chains converge. Is this real? This is like data processing slapstick comedy. I'm imagining the scene where someone steps into a boardroom and says this to Jeff Bezos. "Don't worry, I'll pay you back out of my salary. Wait, how many transactions per second did you say?" When a Bitcoin company puts up a job ad asking for devops engineers: flee in terror.
zoul 14y ago
A bug in the implementation could affect the consensus about the largest chain, just as happened with the official client recently. That’s a security risk.
patio11 14y ago
How can a bug in the implementation be a security risk? This gets a little complicated. "Bitcoin" is a commodity, a protocol (series of promises), a protocol (computer code to implement that series of promises), a particular distributed ledger, a network (of computers implementing the computer code implementing the series of promises with regards to one consensus distributed ledger), etc etc. Consider bitcoin the series of promises. One such promise is under what circumstances opcode 32 causes a transaction to be marked as invalid. (Don't bother looking it up -- you'll have to go down a rabbit hole for a while.) It is critically important that all code implementing opcode 32 comes to the same conclusion regarding every transaction in history and every transaction in the future. Consider an edge case for opcode 32, occurring in a transaction that I'll call T, two years ago. T is, as of right now, accepted as valid in the history that bitcoin (as you understand that term) accepts as correct. If a malfunctioning bitcoin client were to reject T, they would reject large portions of history after T, because they'd be predicated on an invalid series of transactions. Following me so far? So the more interesting case isn't when there is a difference of opinions in the past, it is when there is a predictable difference of opinions in the future. In this case, one set of clients starts building a transaction ledger B, and one starts building a transaction ledger B'. They are different transaction ledgers. People subscribing to either ledger, which they think of as The One True Bitcoin Ledger, will be mighty pissed when other people in The One True Bitcoin Economy tell them that their unforgeable, unloseable, ungovernable units of crypocurrency are actually worthless bits. This is called a blockchain fork. Bitcoiners are terrified of it happening again. (Yes, it has already happened at least once. Long story. "No harm, no foul, he wasn't trying to crash our entire economy so we dodged a bullet." is pretty much the consensus among Bitcoiners who actually understand what happened there.)
- mechanical_fish 14y ago
  So, when this happens again, and then is discovered, who decides which partition of the tree is the "fork" and which is the main branch? I presume it happens by consensus? But... where does consensus come from, in the general case? Does it operate like much open-source governance, via a mix of public and private meetings on IRC between the maintainers of the biggest clients? When that "community" decides to invalidate the mobster's Bitcoins, is there an appeals process, and do the judges have bodyguards? How does one get a seat at the Bitcoin developer summit in the first place? Do the contributors of the most code have the most influence? Which in practice usually translates to "friends and allies of the project founder" and "rich individuals and companies who pay developers to contribute to the project in order to influence its direction?"
wcoenen 14y ago
A bitcoin node tries to determine what the consensus is about the bitcoin ledger by looking for the longest block chain. However, in order to do that it must first collect blocks from other nodes and reject any invalid ones. If a certain implementation disagrees with the rest of the network about the validity of a block, then it will disagree with the rest of the network about the state of the ledger. This can then be exploited by an attacker, e.g. by paying a merchant with a transaction that seems to OK to him but is not accepted by the rest of the network. I don't think that this is a big problem though. A node knows that it is no longer in agreement with the majority of the network when it sees an "invalid" block chain that has the most proof of work done on it. In this case it should shut itself down.

betterunix 14y ago

"How can a bug in the implementation be a security risk?" It could fork the block chain: http://bitcoin.org/chainfork.html http://bitcoin.org/chainfork.html

Strilanc 14y ago

If one type of client accepts a particular block and another doesn't, the block chain splits and things go badly. This literally happened one month ago, because of a bug being fixed: https://bitcointalk.org/index.php?topic=152030.0 https://bitcointalk.org/index.php?topic=152030.0

mseebach 14y ago
Ugh, that is very bad. I had much higher thoughts of the cryptographic purity of BTC.
- betterunix 14y ago
  The cryptographic purity of a system without a formal security definition and for which there is a known polynomial time attack? I think you were bound to be disappointed...
- fianchetto 14y ago
  Bitcoin is cryptographically pure but programmers aren't quite as perfect.
  - betterunix 14y ago
    What is the security definition?
    - nullc 14y ago
      https://socrates1024.s3.amazonaws.com/consensus.pdf https://socrates1024.s3.amazonaws.com/consensus.pdf
      - betterunix 14y ago
        I think this paper presents a poor security definition for Bitcoin, at the very least because it assumes a non-adaptive adversary (i.e. the adversary cannot change which nodes it controls over time). That is not how things work in the real world; in the real world, the adversary will keep increasing his computational power (the number of "pawns") until his attack is successful. I am also skeptical of a computational model that assumes the adversary's computation is somehow synchronized with the honest parties'; that is not even remotely realistic, and it is very weak. In other words, that paper does not tell us anything we did not already know: Bitcoin is secure only if nobody does as much computational work as the rest of the network combined (though there may be other attacks on the protocol that have not yet been discovered). If anything, this paper is a step towards formalizing a security definition for a protocol that is similar to Bitcoin, or a step towards proving that there will always be a polynomial time attack against such protocols (as was the case with Merkle's puzzles).
        nullc 14y ago
        It assumes an anonymous protocol. The identity of the nodes does not matter. > a step towards proving that there will always be a polynomial time attack against such protocols I had considered that to be the definition of a majority consensus. I find it sort of surprising that you'd think otherwise. Lets just assume that some alternative protocol has a property where a an attack with the >50% computing power would be ignored. Then it follows that it would also allow an attack with <50% computing power— unless "attack" could be detected as a function of network state, in which case any sane system would just ignore those entirely— as Bitcoin does, e.g. a transaction outputting more coins than it inputs is ignored regardless of the hashpower— so they're not the kind of attacks we're talking about here. Even if you dispense with all the crypto-computing-power-mumbo-jumbo: A _consensus_ ultimately depends on linear energy applied to an attack. Lets imagine a magical version of Bitcoin solves the sybil problem completely and counts the consensus of _users_ instead of computing power. China (for example) could reorganize the consensus by spending a lot of energy to manufacturer a lot of additional people. So long as the attacker put in more energy mining people than all the honest participants they'd always eventually win.
- nullc 14y ago
  Bitcoin is a distributed consensus algorithm. Software which implements a subtly different algorithm might be able to join the consensus until some case arises which triggers the difference, after that consensus between the implementations would be impossible. Unfortunately, it's rather hard to demonstrate that two dissimilar complex programs actually implement exactly the same function. This is doubly true because performance is very important, so some techniques that might help— e.g. define a kind of abstract turing machine, write the rules for the distributed algorithm in its language, then different implementations use the same rules and only have to prove their turing machine implementation is functionally identical— aren't readily available. It can be hard to gain confidence through testing because some of the most important rules are for cases which are forbidden, so these cases will not show up on the production network— they only happen when an attacker produces them. There are an infinite number (subject to memory, and already the function input is gigabytes of data) of valid and invalid cases, so exhaustive testing of the whole function is not possible. They can also arise out of implicit behavior, "what happens when this value overflows?", "what is the maximum size of this structure", etc. This is further complicated by the fact that Bitcoin implementations use third party code that wasn't written with this kind of must-have-exact-behavior in mind. The reference implementation uses things like OpenSSL's crypto and bignums, various boost data structures, BDB (previously, now leveldb)... and subtle potentially undocumented and unknown behavior from this third party code may be leaking into the definition of the consensus algorithm. The reference implementation has been slowly disentangling these dependencies, but things like the hidden BDB locking limitations (which depend on the layout of the database on disk) are easy to miss. (Third party code isn't just a reference implementation issue, e.g. BitcoinJ's full node code has had algorithm inconsistencies arising out of undocumented behavior in a database library it uses) Satoshi's answer for this was that there should only be one implementation of the full node software. However, "create your own Bitcoin implementation" seems to be the new millennium's "create an IRC client" so it seems that this is unrealistic... and there have been more than a half dozen attempts (including two nearly complete ones in java, two in C, three in C++, one in Haskell, one in erlang, one (two?) in javascript, as well as several non public ones (including one in ruby, I think)).
  - mechanical_fish 14y ago
mechanical_fish 14y ago
From the linked post: If you're a merchant: please stop processing transactions until the chains converge. Is this real? This is like data processing slapstick comedy. I'm imagining the scene where someone steps into a boardroom and says this to Jeff Bezos. "Don't worry, I'll pay you back out of my salary. Wait, how many transactions per second did you say?" When a Bitcoin company puts up a job ad asking for devops engineers: flee in terror.

zoul 14y ago

A bug in the implementation could affect the consensus about the largest chain, just as happened with the official client recently. That’s a security risk.

patio11 14y ago

How can a bug in the implementation be a security risk? This gets a little complicated. "Bitcoin" is a commodity, a protocol (series of promises), a protocol (computer code to implement that series of promises), a particular distributed ledger, a network (of computers implementing the computer code implementing the series of promises with regards to one consensus distributed ledger), etc etc. Consider bitcoin the series of promises. One such promise is under what circumstances opcode 32 causes a transaction to be marked as invalid. (Don't bother looking it up -- you'll have to go down a rabbit hole for a while.) It is critically important that all code implementing opcode 32 comes to the same conclusion regarding every transaction in history and every transaction in the future. Consider an edge case for opcode 32, occurring in a transaction that I'll call T, two years ago. T is, as of right now, accepted as valid in the history that bitcoin (as you understand that term) accepts as correct. If a malfunctioning bitcoin client were to reject T, they would reject large portions of history after T, because they'd be predicated on an invalid series of transactions. Following me so far? So the more interesting case isn't when there is a difference of opinions in the past, it is when there is a predictable difference of opinions in the future. In this case, one set of clients starts building a transaction ledger B, and one starts building a transaction ledger B'. They are different transaction ledgers. People subscribing to either ledger, which they think of as The One True Bitcoin Ledger, will be mighty pissed when other people in The One True Bitcoin Economy tell them that their unforgeable, unloseable, ungovernable units of crypocurrency are actually worthless bits. This is called a blockchain fork. Bitcoiners are terrified of it happening again. (Yes, it has already happened at least once. Long story. "No harm, no foul, he wasn't trying to crash our entire economy so we dodged a bullet." is pretty much the consensus among Bitcoiners who actually understand what happened there.)

mechanical_fish 14y ago
So, when this happens again, and then is discovered, who decides which partition of the tree is the "fork" and which is the main branch? I presume it happens by consensus? But... where does consensus come from, in the general case? Does it operate like much open-source governance, via a mix of public and private meetings on IRC between the maintainers of the biggest clients? When that "community" decides to invalidate the mobster's Bitcoins, is there an appeals process, and do the judges have bodyguards? How does one get a seat at the Bitcoin developer summit in the first place? Do the contributors of the most code have the most influence? Which in practice usually translates to "friends and allies of the project founder" and "rich individuals and companies who pay developers to contribute to the project in order to influence its direction?"

wcoenen 14y ago

A bitcoin node tries to determine what the consensus is about the bitcoin ledger by looking for the longest block chain. However, in order to do that it must first collect blocks from other nodes and reject any invalid ones. If a certain implementation disagrees with the rest of the network about the validity of a block, then it will disagree with the rest of the network about the state of the ledger. This can then be exploited by an attacker, e.g. by paying a merchant with a transaction that seems to OK to him but is not accepted by the rest of the network. I don't think that this is a big problem though. A node knows that it is no longer in agreement with the majority of the network when it sees an "invalid" block chain that has the most proof of work done on it. In this case it should shut itself down.