6 ms·

FTA: Busoni said that a hacker took advantage of a processing flaw in the Bitcoin exchange post. When users submit a withdrawal request, the input is checked ag

by nisa 13y ago

FTA: Busoni said that a hacker took advantage of a processing flaw in the Bitcoin exchange post. When users submit a withdrawal request, the input is checked against your balance, deducted, and the new amount recorded within a database. However, it was discovered that placing several withdrawals all in practically the same instant meant each request was processed at more-or-less the same time, resulting in a negative balance but "valid insertions into the database, which then get picked up by the withdrawal daemon." Isn't ACID the solution to these problems for like 30 years?

willvarfar 13y ago
And withdrawals are even the classic example used in schoolbooks too...
Xylakant 13y ago
You can use an ACID compliant database and run into this problem, it's a classical race condition. The solution is to implement double bookkeeping and bank reconciliation, but it's tedious and complex to implement. I saw a pretty nice blog post with detailed information on the subject, but I can't remember where, didn't bookmark and my google-fu is weak at the moment. So either somebody remembers or you'll have to google yourself :)
- arethuza 13y ago
  This one? http://highscalability.com/blog/2013/5/1/myth-eric-brewer-on-why-banks-are-base-not-acid-availability.html http://highscalability.com/blog/2013/5/1/myth-eric-brewer-on... "What accounts for the consistency of bank data is not the consistency of its databases but the fact that everything is written down twice and sorted out later using a permanent and unalterable record that is reconciled later." But isn't that talking about "traditional" financial institutions that (in my experience) have staggeringly complex (messy) computing environments just by the nature of how these businesses grow (e.g. lots of acquisitions). Surely for a brand new service such a Bitcoin exchange there isn't that excuse?
  - rmc 13y ago
    Or they have these complex systems in order to prevent bugs and flaws like this?
    - uptown 13y ago
      While the two explanations are not mutually exclusive, in my experience, the mess is very frequently the result of mergers and acquisitions.
  - vidarh 13y ago
    Suddenly you don't have confidence in the balances due to a bug. How do you resolve it? That is why you have ledgers. Being able to go back and "replay" step by step how you got where you are makes all the difference when you run into stupid bugs. And you will run into stupid bugs. That you're dealing with a brand new service that has not been battle-tested for years is yet another reason why you want a ledger and proper reconciliation rather than relying on a running balance.
  - joe_the_user 13y ago
    Yes, as I understand it, real banks don't use ACID databases because their software dates from before before the era of modern databases, they uses a lot of batch processing, because indeed they've grown by knitting together multiple institutions and etc. To further clarify, an ACID database, used correctly, are a drop-in solution to problems like that of someone attempting multiple simultaneous account withdrawals. And, of course, "you can still run into these problems using an ACID database" (lol), yes, all you have to do is not understand transactions and not use them.
- nisa 13y ago
  It's been a few years but at least in theory ACID should avoid any race conditions. So you mean you'll face problems in a concrete implementation or due to performance optimizations? I can't image that ACID has a theoretical possibility for race-conditions - I'd like to learn if this is the case - Google did not turn up anything.
  - stonemetal 13y ago
    Check out the wikipedia article on Isolation (database systems) Anything below serializable has race conditions where the same query may return different results depending on what else the system is doing.
- sehrope 13y ago
  > You can use an ACID compliant database and run into this problem, it's a classical race condition. No it's not. It's just sloppy code and/or a misunderstanding of database transactions and isolation levels. If you use an ACID compliant database like PostgreSQL it's pretty straightforward to write proper code that would not have this issue. The main concept to understand is that you need to lock all the rows that you'll be touching before you use them. In most case this method works fine with the default read-committed isolation level. Code that queries your database in multiple round trips and then compares the values for validity on the app side will have this problem. Anything you read could have been modified by the time you "act on" the information you read. Heck even stored procedures running on the DB itself will have this problem if run in the default read-committed isolation level. The high level solution is to use SELECT ... FOR UPDATE and lock everything that you'll be touching before you update anything. > The solution is to implement double bookkeeping and bank reconciliation, but it's tedious and complex to implement. This is a business requirement for any accounting/financial software but it's not a technical one. Having an audit trail, double entry accounting, and recon are business functions. You'd be crazy to design a system that didn't include them but it's not strictly required (again from a technical sense, not a business one!).
  - RyanZAG 13y ago
    The problem appears to have been more straight forward than any of that. The actual transaction system was a different system from the order entry/webs system. It ran orders in serial after a delay using some kind of message passing. Obviously you can't have a SQL transaction that spans multiple applications, so SQL transactions wouldn't really work in this case. It was just a straight forward mistake: orders could be placed before previous orders were finished executing. Transactions wouldn't actually work with bitcoin in this case anyway. eg, transaction 1 checks balance, deducts amount, does BTC transfer, and then commits. Transaction 2 does the same, but the commit would fail as transaction 1 has already modified it. Transaction 2 can't actually roll back though - the bitcoin transaction cannot be rolled back.
    - knome 13y ago
      You wouldn't do the bitcoin transfer until the transaction authorizing it completed successfully. And you don't just use a single transaction that deducts the amount. You'd use one transaction to indicate you were beginning a transfer, putting that amount in a hold state, attempt the bitcoin transfer, then a transaction to indicate the bitcoin transfer was successful or not. If there is an error in the bitcoin transfer or after, and the second transaction is never run, the funds are still in hold whether transferred or not and can be manually corrected by checking the system logs.
- mootothemax 13y ago
  You can use an ACID compliant database and run into this problem, it's a classical race condition. Isn't it a quick fix to add an ACID-friendly clause to the UPDATE statement, e.g. some pseuosql like: UPDATE balances SET balance = (balance - amount) WHERE user_id = input_user_id AND (balance - amount > 0)
  - eterm 13y ago
    You shouldn't ever even have a "balance" that you update. You should have a ledger. "INSERT INTO Ledger (Account, Date, Amount) VALUES (PersonToDebit, Now, -withdrawl)" And then someone's "balance" is the sum of their ledger. If multiple withdrawls go through, the account could still go negative if you don't check at the time of the withdrawl, but worse case you still end up with negative balances rather than flat out losing track of the balance because you have a balance that you UPDATE.
    - mootothemax 13y ago
      You shouldn't ever even have a "balance" that you update. I was arguing against the grandparent's claim of ACID race conditions; my intention wasn't to advocate in favour of a "balance" column. Edit: that said, I wouldn't mind hearing the pros or cons of maintaining a convenience (e.g. page display) "running balance" that is updated from the ledger after every transaction.
      - unclebucknasty 13y ago
        Well, I think the parent was saying that you shouldn't have a balance that is actually relied upon for record-keeping or transactional purposes. If you want to keep one for optimization purposes (i.e. you are reading more than writing and don't want to constantly sum the ledger table), then that's probably outside the scope of the parent's point.
    - rdtsc 13y ago
      Well you'd probably want to have both, a negative balance is a problem with bitcoin if it can be arbitrarily negative. Say they issue 1000 withdraws in a millisecond. The balance will be "very" negative and there is nothing that can be done. And it might have to be done only a few times to bankrupt the exchange. With the regular banking system or even with stock market, some trades and transactions can be reversed in case of errors and mistakes. So just having a ledger works, some bad updates can be reversed. Not so with bitcoin. So when dealing with someone's account at a place like this an ACID compliant balance update is also needed. Amateurs have jumped in and started developing banking software that deals with hundreds of millions of dollars -- so this is not surprising. But at the same time it is kind of nice. It is sort of a Darwinian if you wish, the weakest and unlucky ones fail and get robbed the competent and/or lucky get to survive.
- Xdes 13y ago
  I think the solution is continuous monitoring and auditing. Keeping track of the balances is the simple part. Reconciling the balances is the complex part. Banking is inherently eventually consistent, so putting audits in place to verify integrity of the balances is critical.
mcv 13y ago
> Isn't ACID the solution to these problems for like 30 years? Yes, but this is bitcoin, which is so totally unlike anything that existed before, that such outdated notions as ACID aren't valid anymore. We need to start with a clean slate and reinvent all the wheels all over again.
- castis 13y ago
  I dont know that I'd consider ACID an outdated notion.
  - tyw 13y ago
    hard to say but I'm pretty sure the parent was dripping with sarcasm.
  - Fomite 13y ago
    You should make sure your sarcasm detector is properly aligned.
- codygman 13y ago
  ACID is outdated? Shall we use mongodb for bitcoin?
  - mcv 13y ago
    I'm pretty sure they already do that.
  - shalmanese 13y ago
    Coinbase is way ahead of you on this one.
- ChuckMcM 13y ago
  Ok that totally made be laugh!
stingraycharles 13y ago
Transaction isolation is not what you think it is. Most databases run at a liberal isolation level. For example, from the PostgreSQL docs[1] you can read that they use 'read committed' as an isolation level by default. In this example, it could mean that the following could happen: * At T=1, transaction 1 will read the current balance * At T=2, transaction 2 will read the current balance * At T=3, transaction 1 will update the current balance * At T=4, transaction 2 is in a race condition situation, since the update of transaction 1 'leaks' into transaction 2, but the last read balance in transaction 2 still is the 'old' balance. In other words: this is an area where a lot of people introduce race condition bugs without being aware of it. [1] http://www.postgresql.org/docs/9.1/static/transaction-iso.html http://www.postgresql.org/docs/9.1/static/transaction-iso.ht...
- raverbashing 13y ago
  What looks like is needed is a serialization of user transactions. And also risk-avoiding schemas (in the general provisions of the business, not only on the system running it)
- sergiosgc 13y ago
  That's the default, but you can, and should, use a serializable transaction isolation level where required by the problem domain.
  - stingraycharles 13y ago
    Of course you should, the problem isn't that it isn't possible to serialize a transaction, the problem is that the default is optimistic. I can only imagine that there will be quite a hefty performance impact if serialized transactions were the default, so I understand their reasoning.

by nisa 13y ago

willvarfar 13y ago

And withdrawals are even the classic example used in schoolbooks too...

Xylakant 13y ago

You can use an ACID compliant database and run into this problem, it's a classical race condition. The solution is to implement double bookkeeping and bank reconciliation, but it's tedious and complex to implement. I saw a pretty nice blog post with detailed information on the subject, but I can't remember where, didn't bookmark and my google-fu is weak at the moment. So either somebody remembers or you'll have to google yourself :)

arethuza 13y ago
This one? http://highscalability.com/blog/2013/5/1/myth-eric-brewer-on-why-banks-are-base-not-acid-availability.html http://highscalability.com/blog/2013/5/1/myth-eric-brewer-on... "What accounts for the consistency of bank data is not the consistency of its databases but the fact that everything is written down twice and sorted out later using a permanent and unalterable record that is reconciled later." But isn't that talking about "traditional" financial institutions that (in my experience) have staggeringly complex (messy) computing environments just by the nature of how these businesses grow (e.g. lots of acquisitions). Surely for a brand new service such a Bitcoin exchange there isn't that excuse?
- rmc 13y ago
  Or they have these complex systems in order to prevent bugs and flaws like this?
  - uptown 13y ago
    While the two explanations are not mutually exclusive, in my experience, the mess is very frequently the result of mergers and acquisitions.
- vidarh 13y ago
  Suddenly you don't have confidence in the balances due to a bug. How do you resolve it? That is why you have ledgers. Being able to go back and "replay" step by step how you got where you are makes all the difference when you run into stupid bugs. And you will run into stupid bugs. That you're dealing with a brand new service that has not been battle-tested for years is yet another reason why you want a ledger and proper reconciliation rather than relying on a running balance.
- joe_the_user 13y ago
  Yes, as I understand it, real banks don't use ACID databases because their software dates from before before the era of modern databases, they uses a lot of batch processing, because indeed they've grown by knitting together multiple institutions and etc. To further clarify, an ACID database, used correctly, are a drop-in solution to problems like that of someone attempting multiple simultaneous account withdrawals. And, of course, "you can still run into these problems using an ACID database" (lol), yes, all you have to do is not understand transactions and not use them.
nisa 13y ago
It's been a few years but at least in theory ACID should avoid any race conditions. So you mean you'll face problems in a concrete implementation or due to performance optimizations? I can't image that ACID has a theoretical possibility for race-conditions - I'd like to learn if this is the case - Google did not turn up anything.
- stonemetal 13y ago
  Check out the wikipedia article on Isolation (database systems) Anything below serializable has race conditions where the same query may return different results depending on what else the system is doing.
sehrope 13y ago
> You can use an ACID compliant database and run into this problem, it's a classical race condition. No it's not. It's just sloppy code and/or a misunderstanding of database transactions and isolation levels. If you use an ACID compliant database like PostgreSQL it's pretty straightforward to write proper code that would not have this issue. The main concept to understand is that you need to lock all the rows that you'll be touching before you use them. In most case this method works fine with the default read-committed isolation level. Code that queries your database in multiple round trips and then compares the values for validity on the app side will have this problem. Anything you read could have been modified by the time you "act on" the information you read. Heck even stored procedures running on the DB itself will have this problem if run in the default read-committed isolation level. The high level solution is to use SELECT ... FOR UPDATE and lock everything that you'll be touching before you update anything. > The solution is to implement double bookkeeping and bank reconciliation, but it's tedious and complex to implement. This is a business requirement for any accounting/financial software but it's not a technical one. Having an audit trail, double entry accounting, and recon are business functions. You'd be crazy to design a system that didn't include them but it's not strictly required (again from a technical sense, not a business one!).
- RyanZAG 13y ago
  The problem appears to have been more straight forward than any of that. The actual transaction system was a different system from the order entry/webs system. It ran orders in serial after a delay using some kind of message passing. Obviously you can't have a SQL transaction that spans multiple applications, so SQL transactions wouldn't really work in this case. It was just a straight forward mistake: orders could be placed before previous orders were finished executing. Transactions wouldn't actually work with bitcoin in this case anyway. eg, transaction 1 checks balance, deducts amount, does BTC transfer, and then commits. Transaction 2 does the same, but the commit would fail as transaction 1 has already modified it. Transaction 2 can't actually roll back though - the bitcoin transaction cannot be rolled back.
  - knome 13y ago
    You wouldn't do the bitcoin transfer until the transaction authorizing it completed successfully. And you don't just use a single transaction that deducts the amount. You'd use one transaction to indicate you were beginning a transfer, putting that amount in a hold state, attempt the bitcoin transfer, then a transaction to indicate the bitcoin transfer was successful or not. If there is an error in the bitcoin transfer or after, and the second transaction is never run, the funds are still in hold whether transferred or not and can be manually corrected by checking the system logs.
mootothemax 13y ago
You can use an ACID compliant database and run into this problem, it's a classical race condition. Isn't it a quick fix to add an ACID-friendly clause to the UPDATE statement, e.g. some pseuosql like: UPDATE balances SET balance = (balance - amount) WHERE user_id = input_user_id AND (balance - amount > 0)
- eterm 13y ago
  You shouldn't ever even have a "balance" that you update. You should have a ledger. "INSERT INTO Ledger (Account, Date, Amount) VALUES (PersonToDebit, Now, -withdrawl)" And then someone's "balance" is the sum of their ledger. If multiple withdrawls go through, the account could still go negative if you don't check at the time of the withdrawl, but worse case you still end up with negative balances rather than flat out losing track of the balance because you have a balance that you UPDATE.
  - mootothemax 13y ago
    You shouldn't ever even have a "balance" that you update. I was arguing against the grandparent's claim of ACID race conditions; my intention wasn't to advocate in favour of a "balance" column. Edit: that said, I wouldn't mind hearing the pros or cons of maintaining a convenience (e.g. page display) "running balance" that is updated from the ledger after every transaction.
    - unclebucknasty 13y ago
      Well, I think the parent was saying that you shouldn't have a balance that is actually relied upon for record-keeping or transactional purposes. If you want to keep one for optimization purposes (i.e. you are reading more than writing and don't want to constantly sum the ledger table), then that's probably outside the scope of the parent's point.
  - rdtsc 13y ago
    Well you'd probably want to have both, a negative balance is a problem with bitcoin if it can be arbitrarily negative. Say they issue 1000 withdraws in a millisecond. The balance will be "very" negative and there is nothing that can be done. And it might have to be done only a few times to bankrupt the exchange. With the regular banking system or even with stock market, some trades and transactions can be reversed in case of errors and mistakes. So just having a ledger works, some bad updates can be reversed. Not so with bitcoin. So when dealing with someone's account at a place like this an ACID compliant balance update is also needed. Amateurs have jumped in and started developing banking software that deals with hundreds of millions of dollars -- so this is not surprising. But at the same time it is kind of nice. It is sort of a Darwinian if you wish, the weakest and unlucky ones fail and get robbed the competent and/or lucky get to survive.
Xdes 13y ago
I think the solution is continuous monitoring and auditing. Keeping track of the balances is the simple part. Reconciling the balances is the complex part. Banking is inherently eventually consistent, so putting audits in place to verify integrity of the balances is critical.

mcv 13y ago

> Isn't ACID the solution to these problems for like 30 years? Yes, but this is bitcoin, which is so totally unlike anything that existed before, that such outdated notions as ACID aren't valid anymore. We need to start with a clean slate and reinvent all the wheels all over again.

castis 13y ago
I dont know that I'd consider ACID an outdated notion.
- tyw 13y ago
  hard to say but I'm pretty sure the parent was dripping with sarcasm.
- Fomite 13y ago
  You should make sure your sarcasm detector is properly aligned.
codygman 13y ago
ACID is outdated? Shall we use mongodb for bitcoin?
- mcv 13y ago
  I'm pretty sure they already do that.
- shalmanese 13y ago
  Coinbase is way ahead of you on this one.
ChuckMcM 13y ago
Ok that totally made be laugh!

stingraycharles 13y ago

Transaction isolation is not what you think it is. Most databases run at a liberal isolation level. For example, from the PostgreSQL docs[1] you can read that they use 'read committed' as an isolation level by default. In this example, it could mean that the following could happen: * At T=1, transaction 1 will read the current balance * At T=2, transaction 2 will read the current balance * At T=3, transaction 1 will update the current balance * At T=4, transaction 2 is in a race condition situation, since the update of transaction 1 'leaks' into transaction 2, but the last read balance in transaction 2 still is the 'old' balance. In other words: this is an area where a lot of people introduce race condition bugs without being aware of it. [1] http://www.postgresql.org/docs/9.1/static/transaction-iso.html http://www.postgresql.org/docs/9.1/static/transaction-iso.ht...

raverbashing 13y ago
What looks like is needed is a serialization of user transactions. And also risk-avoiding schemas (in the general provisions of the business, not only on the system running it)
sergiosgc 13y ago
That's the default, but you can, and should, use a serializable transaction isolation level where required by the problem domain.
- stingraycharles 13y ago
  Of course you should, the problem isn't that it isn't possible to serialize a transaction, the problem is that the default is optimistic. I can only imagine that there will be quite a hefty performance impact if serialized transactions were the default, so I understand their reasoning.