7 ms·

The programming error that cost Mt. Gox 2609 Bitcoins

172 points by peter123 13y ago

deleted 13y ago
[deleted]
einhverfr 13y ago
I keep wondering though if this can be thought of as a variation of the halting problem. I.e. it is a question of halting state rather than halting execution. The problem here seems to be the inverse: Can you guarantee that, over time, the program sequence will not halt even if the individual programs in fact do halt. "Halting" would have to be defined differently, i.e. with the capacity to resume. Am I missing something?
- kevingadd 13y ago
  Arguably since the transaction scripts don't loop, something resembling 100% branch coverage testing would probably suffice. The issue is classifying the test results: should the test succeed with these inputs, should it fail with these other inputs, etc. Given that the scripts are usually used to verify basic transactions, though, you could probably provide a few basic rules and autogenerate appropriate tests.
  - einhverfr 13y ago
    Arguably a mining approach that would require that miners return the transactions that can't complete to their previous individual could provide formal proof that it will not "halt" ever. It seems to me that the obvious issue is sending invalid transactions. If these are not handled and the bitcoins are lost that means that bitcoin itself must eventually disappear because some percentage of transactions will be bad and over time, the sum of all of these will lead to enough losses to ensure that there is no practical value to the remaining bitcoins. It seems to me that programs can be guaranteed not to halt a lot more than they can be guaranteed to halt.
jrockway 13y ago
Dear software engineers working with money or crypto: please write some tests.
- taspeotis 13y ago
  Maybe MtGox does have tests but they wrote their own unit testing framework and it doesn't unit test correctly? http://blog.magicaltux.net/2009/09/19/striving-for-a-better-world/ http://blog.magicaltux.net/2009/09/19/striving-for-a-better-...
  - jrockway 13y ago
    Go kind of makes you do this. Last weekend I was writing some code, ran the tests, and saw that they failed. I debugged my test harness for a while, only to find that the bug was actually in my real code. (Overall I kind of like the strategy, I'd much rather debug my own for-loop-over-test-data than someone else's. But it does lead the mind down different paths than when you use something like JUnit/Hamcrest.) Incidentally, this is why "test first" is more than just a methodology for selling high-priced consultants. At least it lets you see your tests fail and then pass, rather than just pass. Lots of common patterns pass in the presence of incorrect code. An example that a coworker was complaining to me about recently: void testFooBarException() { try { thisShouldThrowFooBarException() } catch (FooBarException ignored) {} } Can you spot the bug? The test still passes even if thisShouldThrowFooBarException doesn't throw an exception. Oops. I personally avoid this by checking that I can make the test fail when I expect it to fail, by editing some values or commenting something out. But that doesn't scale, that only saves you once. Something to think about.
    - ilyanep 13y ago
      In case anyone is wondering, that code should read something like: void testFooBarException() { try { thisShouldThrowFooBarException() fail() // Should have thrown exception } catch (FooBarException ignored) {} } If you're feeling super fancy, you can even do some asserts in the catch block to make sure the FooBarException has an expected exception message.
dsugarman 13y ago
is it alarming at all that the # of redeemable bitcoins are provenly monotonically decreasing after some period of time? I guess if there is a lower limit it shouldn't matter?
- wyager 13y ago
  It's not really that alarming. It has some deflationary effects (which Bitcoin was designed with anyway). Worst case, let's say all Bitcoins except .00000001 (1 Satoshi) have been destroyed. Well, no problem, we just make the base unit .00000000000000000001 Bitcoin or something. As far as I know, the only reason 21,000,000*100,000,000 units was chosen was to fit comfortably in the 52-bit mantissa of a 64-bit IEEE 754 floating point number. Edit: Apparently I just made that up... But it makes sense! Edit 2: Apparently some other devs believe this is the case as well.
  - davidw 13y ago
    Do people often use floats in their bitcoin code?
  - bunderbunder 13y ago
    BTC use fixed-point math with 64-bit unsigned integers. Precision is 8 decimal places. So at least as currently built, I believe 1 Satoshi is the smallest possible unit of Bitcoin. There's talk about it being possible to move the decimal point with a protocol update, but I'm not sure about how the logistics of that would work, or just how far it's possible to move it.
    - Nilzor 13y ago
      How can a protocol dealing with currency invented after year 2000 have limits on the number of decimals or its positionn?
      - nfoz 13y ago
        I'll hazard a guess: the protocol might not want to allow arbitrarily large transaction messages. Could introduce points of failure / DOS'ing.
xpda 13y ago
This is not the only or even the primary problem with MtGox. There are fundamental control shortcomings, among various tech problems.
joering2 13y ago
The more that I am wrapping my head around it, the more I realize this all may not be an accident. My conspiracy theories side tells me this: imagine that you own a bank that is not guarded by any rules laws or regulations, that most money is deposited anonymously or semi-anonymously, and it is deposited in unmarked banknotes. And its worth $500k. Now, fast forward to today and you keep keys to $400,000,000 vault. Only rules haven't changed. Now, given the overall complexity of bitcoins algorithm, the fact that mt gox is (afaik) not even registered in a country with solid laws, wouldn't you grab the money and "run", even though running means only pointing out there was a glitch in the system and filing for bankruptcy protection? If any of this is true, then here is your (sad) reasoning why we need government oversight when it comes to dealing with someones property, being it even bits on someones hard drive.
- ma2rten 13y ago
  How is Japan not "a country with solid laws".
  - mschuster91 13y ago
    "solid" being compared with the holy crap of regulations the US have. I (a German) laugh my behind off when I read that as a mail-order business one is expected (and fined if noncompliant to the letter) to the tax codes of villages so small that they would not even count as a village in Germany. And if you're shipping inside the European Union, well, just properly declare the VAT and be done with it.
    - declan 13y ago
      As a German, you may want to brush up on your understanding of U.S. law. First, if you're a mail order business in California you don't have to pay attention to any other state's sales or use tax laws unless you have a business presence (such as an office) in that state. As a California shipper shipping in-state you need to look up the destination zip code's tax rate, true, but it's county-by-county and you can do it for free here: https://maps.gis.ca.gov/boe/TaxRates/ https://maps.gis.ca.gov/boe/TaxRates/ Second, if you want to avoid even this annoyance, you can start your business in one of the five states with no sales taxes including New Hampshire or Oregon, meaning you never have to collect any sales taxes. Third, if you do have offices in other states, you can buy some relatively cheap software that takes care of billing for you. I'm not saying this system is perfect or even that it'll continue given the pro-Internet tax forces in Congress, but nevertheless I don't think your description is accurate.
eridius 13y ago
I read the link on proof-of-burn, which demonstrated how it works, but I'm confused. What is the actual point of doing a proof-of-burn?
- Strilanc 13y ago
  If I want to send an email to a political party I don't like, they may want me to sacrifice money to show I'm not a spammer. I don't want to send them money, so we agree to burn some instead.
  - eridius 13y ago
    Interesting, although that seems like a fairly niche case. Are there other more generic applications? The post also linked to something called Counterparty, but the front page of that site gave no hint as to how proof-of-burn is used there. I'm also curious as to what's stopping you from using the same proof-of-burn repeatedly. If I burn some coins 2 months ago, and then prove to someone today that I burned then, why can't I turn around and use the exact same burn as a proof for someone else tomorrow?
    - michaelt 13y ago
      Generally, any situation where a charge is intended to reduce demand / disadvantage the payer, rather than to maximise profit / benefit the payee. At the moment in these sorts of cases usually a payee just keeps the money; the advantage would be in reducing perverse incentives. If spammers kept opening HN accounts, HN could say "burn $5 to open a new account" to reduce demand. That would avoid HN having an incentive to ban people for profit. Or the state could say "speeding fine? burn $200" to discourage people from speeding. That would avoid the state having an incentive to increase crime to generate fine revenue. Or a college could say "want your exam paper re-graded? burn $50" to discourage requests just for the sake of it. That would avoid the college having an incentive to grade people badly. To resolve a disputed transaction on an auction site, the site could require the buyer to destroy the goods and the seller to burn the money, so there would be no profit from filing false disputes.
rainmaking 13y ago
What we really need is a strong stance from the bitcoin foundation condemning any services that offers to hold user's wallet keys for them.
sirsar 13y ago
There is an alternate blockchain explicitly created for testing called the "testnet." It works exactly like Bitcoin except its genesis block is different, so it has a different blockchain and set of transactions. Testcoins have no value, and the mainstream client switches to a new testchain every so often. Lose testcoins, not Bitcoins.

172 points by peter123 13y ago

deleted 13y ago

[deleted]

I keep wondering though if this can be thought of as a variation of the halting problem. I.e. it is a question of halting state rather than halting execution. The problem here seems to be the inverse: Can you guarantee that, over time, the program sequence will not halt even if the individual programs in fact do halt. "Halting" would have to be defined differently, i.e. with the capacity to resume. Am I missing something?

kevingadd 13y ago
Arguably since the transaction scripts don't loop, something resembling 100% branch coverage testing would probably suffice. The issue is classifying the test results: should the test succeed with these inputs, should it fail with these other inputs, etc. Given that the scripts are usually used to verify basic transactions, though, you could probably provide a few basic rules and autogenerate appropriate tests.
- einhverfr 13y ago
  Arguably a mining approach that would require that miners return the transactions that can't complete to their previous individual could provide formal proof that it will not "halt" ever. It seems to me that the obvious issue is sending invalid transactions. If these are not handled and the bitcoins are lost that means that bitcoin itself must eventually disappear because some percentage of transactions will be bad and over time, the sum of all of these will lead to enough losses to ensure that there is no practical value to the remaining bitcoins. It seems to me that programs can be guaranteed not to halt a lot more than they can be guaranteed to halt.

jrockway 13y ago

Dear software engineers working with money or crypto: please write some tests.

taspeotis 13y ago
Maybe MtGox does have tests but they wrote their own unit testing framework and it doesn't unit test correctly? http://blog.magicaltux.net/2009/09/19/striving-for-a-better-world/ http://blog.magicaltux.net/2009/09/19/striving-for-a-better-...
- jrockway 13y ago
  Go kind of makes you do this. Last weekend I was writing some code, ran the tests, and saw that they failed. I debugged my test harness for a while, only to find that the bug was actually in my real code. (Overall I kind of like the strategy, I'd much rather debug my own for-loop-over-test-data than someone else's. But it does lead the mind down different paths than when you use something like JUnit/Hamcrest.) Incidentally, this is why "test first" is more than just a methodology for selling high-priced consultants. At least it lets you see your tests fail and then pass, rather than just pass. Lots of common patterns pass in the presence of incorrect code. An example that a coworker was complaining to me about recently: void testFooBarException() { try { thisShouldThrowFooBarException() } catch (FooBarException ignored) {} } Can you spot the bug? The test still passes even if thisShouldThrowFooBarException doesn't throw an exception. Oops. I personally avoid this by checking that I can make the test fail when I expect it to fail, by editing some values or commenting something out. But that doesn't scale, that only saves you once. Something to think about.
  - ilyanep 13y ago
    In case anyone is wondering, that code should read something like: void testFooBarException() { try { thisShouldThrowFooBarException() fail() // Should have thrown exception } catch (FooBarException ignored) {} } If you're feeling super fancy, you can even do some asserts in the catch block to make sure the FooBarException has an expected exception message.

dsugarman 13y ago

is it alarming at all that the # of redeemable bitcoins are provenly monotonically decreasing after some period of time? I guess if there is a lower limit it shouldn't matter?

wyager 13y ago
It's not really that alarming. It has some deflationary effects (which Bitcoin was designed with anyway). Worst case, let's say all Bitcoins except .00000001 (1 Satoshi) have been destroyed. Well, no problem, we just make the base unit .00000000000000000001 Bitcoin or something. As far as I know, the only reason 21,000,000*100,000,000 units was chosen was to fit comfortably in the 52-bit mantissa of a 64-bit IEEE 754 floating point number. Edit: Apparently I just made that up... But it makes sense! Edit 2: Apparently some other devs believe this is the case as well.
- davidw 13y ago
  Do people often use floats in their bitcoin code?
- bunderbunder 13y ago
  BTC use fixed-point math with 64-bit unsigned integers. Precision is 8 decimal places. So at least as currently built, I believe 1 Satoshi is the smallest possible unit of Bitcoin. There's talk about it being possible to move the decimal point with a protocol update, but I'm not sure about how the logistics of that would work, or just how far it's possible to move it.
  - Nilzor 13y ago
    How can a protocol dealing with currency invented after year 2000 have limits on the number of decimals or its positionn?
    - nfoz 13y ago
      I'll hazard a guess: the protocol might not want to allow arbitrarily large transaction messages. Could introduce points of failure / DOS'ing.

xpda 13y ago

This is not the only or even the primary problem with MtGox. There are fundamental control shortcomings, among various tech problems.

joering2 13y ago

The more that I am wrapping my head around it, the more I realize this all may not be an accident. My conspiracy theories side tells me this: imagine that you own a bank that is not guarded by any rules laws or regulations, that most money is deposited anonymously or semi-anonymously, and it is deposited in unmarked banknotes. And its worth $500k. Now, fast forward to today and you keep keys to $400,000,000 vault. Only rules haven't changed. Now, given the overall complexity of bitcoins algorithm, the fact that mt gox is (afaik) not even registered in a country with solid laws, wouldn't you grab the money and "run", even though running means only pointing out there was a glitch in the system and filing for bankruptcy protection? If any of this is true, then here is your (sad) reasoning why we need government oversight when it comes to dealing with someones property, being it even bits on someones hard drive.

ma2rten 13y ago
How is Japan not "a country with solid laws".
- mschuster91 13y ago
  "solid" being compared with the holy crap of regulations the US have. I (a German) laugh my behind off when I read that as a mail-order business one is expected (and fined if noncompliant to the letter) to the tax codes of villages so small that they would not even count as a village in Germany. And if you're shipping inside the European Union, well, just properly declare the VAT and be done with it.
  - declan 13y ago
    As a German, you may want to brush up on your understanding of U.S. law. First, if you're a mail order business in California you don't have to pay attention to any other state's sales or use tax laws unless you have a business presence (such as an office) in that state. As a California shipper shipping in-state you need to look up the destination zip code's tax rate, true, but it's county-by-county and you can do it for free here: https://maps.gis.ca.gov/boe/TaxRates/ https://maps.gis.ca.gov/boe/TaxRates/ Second, if you want to avoid even this annoyance, you can start your business in one of the five states with no sales taxes including New Hampshire or Oregon, meaning you never have to collect any sales taxes. Third, if you do have offices in other states, you can buy some relatively cheap software that takes care of billing for you. I'm not saying this system is perfect or even that it'll continue given the pro-Internet tax forces in Congress, but nevertheless I don't think your description is accurate.

eridius 13y ago

I read the link on proof-of-burn, which demonstrated how it works, but I'm confused. What is the actual point of doing a proof-of-burn?

Strilanc 13y ago
If I want to send an email to a political party I don't like, they may want me to sacrifice money to show I'm not a spammer. I don't want to send them money, so we agree to burn some instead.
- eridius 13y ago
  Interesting, although that seems like a fairly niche case. Are there other more generic applications? The post also linked to something called Counterparty, but the front page of that site gave no hint as to how proof-of-burn is used there. I'm also curious as to what's stopping you from using the same proof-of-burn repeatedly. If I burn some coins 2 months ago, and then prove to someone today that I burned then, why can't I turn around and use the exact same burn as a proof for someone else tomorrow?
  - michaelt 13y ago
    Generally, any situation where a charge is intended to reduce demand / disadvantage the payer, rather than to maximise profit / benefit the payee. At the moment in these sorts of cases usually a payee just keeps the money; the advantage would be in reducing perverse incentives. If spammers kept opening HN accounts, HN could say "burn $5 to open a new account" to reduce demand. That would avoid HN having an incentive to ban people for profit. Or the state could say "speeding fine? burn $200" to discourage people from speeding. That would avoid the state having an incentive to increase crime to generate fine revenue. Or a college could say "want your exam paper re-graded? burn $50" to discourage requests just for the sake of it. That would avoid the college having an incentive to grade people badly. To resolve a disputed transaction on an auction site, the site could require the buyer to destroy the goods and the seller to burn the money, so there would be no profit from filing false disputes.

rainmaking 13y ago

What we really need is a strong stance from the bitcoin foundation condemning any services that offers to hold user's wallet keys for them.

sirsar 13y ago

There is an alternate blockchain explicitly created for testing called the "testnet." It works exactly like Bitcoin except its genesis block is different, so it has a different blockchain and set of transactions. Testcoins have no value, and the mainstream client switches to a new testchain every so often. Lose testcoins, not Bitcoins.