4 ms·

Bitcoin is the first practical solution to a longstanding problem in computer science called the Byzantine Generals Problem. Wait, isn't Paxos arguably the fir

by sigil 13y ago

Bitcoin is the first practical solution to a longstanding problem in computer science called the Byzantine Generals Problem. Wait, isn't Paxos arguably the first practical solution to BGP? [0] [1] It's been in production use at Google since at least 2006. [2] Furthermore, Paxos actually has a proof that timely consensus will be reached. Do we have the same level of rock-solid mathematical certainty about Bitcoin yet? The Eyal-Sirer paper [3] from late 2013 raised some concerns about a new mining strategy that might lower the attack threshold from 50% to 33%. Ed Felton's group at Princeton responded with some interesting analysis from game theory [4], but AFAIK there is no rigorous proof yet that the selfish mining equilibrium isn't a real threat. If Bitcoin is The Way of the Future (I hope it is), we need to be sure about these things. Hand-waving statements about how Bitcoin isn't vulnerable because no one has found an exploit yet [5] are ridiculous and dangerous. [0] http://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzantine_Paxos http://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzant... [1] http://read.seas.harvard.edu/~kohler/class/08w-dsi/mazieres07paxos.pdf http://read.seas.harvard.edu/~kohler/class/08w-dsi/mazieres0... [2] http://research.google.com/archive/chubby.html http://research.google.com/archive/chubby.html [3] http://arxiv.org/pdf/1311.0243v2.pdf http://arxiv.org/pdf/1311.0243v2.pdf [4] https://freedom-to-tinker.com/blog/felten/bitcoin-isnt-so-broken-after-all/ https://freedom-to-tinker.com/blog/felten/bitcoin-isnt-so-br... [5] https://twitter.com/cdixon/status/412447615331360768 https://twitter.com/cdixon/status/412447615331360768

hendzen 13y ago
No, Paxos is not a solution to BGP. Paxos explicitly does not consider malicious processes. EDIT: fixed typo
- sigil 13y ago
  Paxos is Byzantine Fault Tolerant. A malicious node is a special case of failed node. "The objective of Byzantine fault tolerance is to be able to defend against Byzantine failures, in which components of a system fail in arbitrary ways (i.e., not just by stopping or crashing but by processing requests incorrectly, corrupting their local state, and/or producing incorrect or inconsistent outputs)." http://en.wikipedia.org/wiki/Byzantine_fault_tolerance http://en.wikipedia.org/wiki/Byzantine_fault_tolerance
  - VMG 13y ago
    This is what I found about it: > The bitcoin system is based around the "block chain", whose main purpose is to implement a distributed timestamp. With a known set of participants, this is a solved problem (Paxos algorithm); on the public Internet with undefined participant list, it's hard. http://www.baum.com.au/~jiri/ae/blog/01306143707 http://www.baum.com.au/~jiri/ae/blog/01306143707
  - hendzen 13y ago
    That is a correct definition of BFT, but as I said, Paxos does not tolerate Byzantine faults. Here's a direct quote [0] from Leslie Lamport, the author of the Paxos algorithm. Assume that agents can communicate with one another by sending messages. We use the customary asynchronous, non-Byzantine model, in which: • Agents operate at arbitrary speed, may fail by stopping, and may restart. Since all agents may fail after a value is chosen and then restart, a solution is impossible unless some information can be remembered by an agent that has failed and restarted. • Messages can take arbitrarily long to be delivered, can be duplicated, and can be lost, but they are not corrupted. So, to be clear, Paxos tolerates processes that crash arbitrarily, but not processes that send malicious or incorrect messages. For a consensus algorithm that does tolerate Byzantine faults, see Liskov's Practical Byzantine Fault Tolerance [1]. [0] - http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf http://research.microsoft.com/en-us/um/people/lamport/pubs/p... [1] - http://www.pmg.lcs.mit.edu/papers/osdi99.pdf http://www.pmg.lcs.mit.edu/papers/osdi99.pdf
    - sigil 13y ago
      I referred in the top level comment above to Byzantine Paxos, a modified version of Paxos that is BFT. http://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzantine_Paxos http://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzant...
      - hendzen 13y ago
        Ah - when the term Paxos is used it is usually in reference to the original, non-BFT algorithm. Also, Google's implementations of Paxos (in Chubby, as well as Megastore) are non-BFT, and I am not aware of any use of Byzantine Paxos in production elsewhere.
maaku 13y ago
> but AFAIK there is no rigorous proof yet that the selfish mining equilibrium isn't a real threat. It's very easy to detect and respond to. Point your miners at the large pools, and check if they are building off of non-public blocks. Respond accordingly.
- sigil 13y ago
  How do you know they're building off of non-public blocks if they're doing so in secret collusion? For what it's worth, Felten et al have a somewhat convincing (if not yet rigorous) argument that members of a so-called selfish mining pool have more incentive to defect than to continue cheating [0]. But, if a single entity controlled all of the 33%, defection is not a risk, and this entity could still claim an outsized share of the mining reward according to Eyal-Sirer. [0] https://news.ycombinator.com/item?id=6689329 https://news.ycombinator.com/item?id=6689329
  - maaku 13y ago
    By running your own node. You can know what is public and what is not.
    - sigil 13y ago
      The selfish miner(s) build a blockchain in private and choose the right moment to reveal it. This paper describes it in more detail: http://arxiv.org/pdf/1311.0243v2.pdf http://arxiv.org/pdf/1311.0243v2.pdf
      - maaku 13y ago
        Who are the miners? Mining pools? Mining pools don't do the actual mining, they contract that out to their users. Anyone can run mining software pointed at any of the major pools and see what blocks they are building off of. There's no way for a mining pool to "build a blockchain in private." If not mining pools, then perhaps the concern is large hosted operators? There's only one of these that qualify, although there is insufficient data about their exact size (CEX.io, part of GHash.io, but only an unknown percentage of their hashpower is hosted). Mining is sufficiently decentralized so as to make large-scale selfing mining detectable, and the economics are such that small-scale selfish mining is unprofitable. I'm not claiming this will always be the case - there is sufficient cause to be concerned for the future as we are trending towards more centralization and hosted mining, not less - but it is certainly not a real concern now.

by sigil 13y ago

hendzen 13y ago

No, Paxos is not a solution to BGP. Paxos explicitly does not consider malicious processes. EDIT: fixed typo

sigil 13y ago
Paxos is Byzantine Fault Tolerant. A malicious node is a special case of failed node. "The objective of Byzantine fault tolerance is to be able to defend against Byzantine failures, in which components of a system fail in arbitrary ways (i.e., not just by stopping or crashing but by processing requests incorrectly, corrupting their local state, and/or producing incorrect or inconsistent outputs)." http://en.wikipedia.org/wiki/Byzantine_fault_tolerance http://en.wikipedia.org/wiki/Byzantine_fault_tolerance
- VMG 13y ago
  This is what I found about it: > The bitcoin system is based around the "block chain", whose main purpose is to implement a distributed timestamp. With a known set of participants, this is a solved problem (Paxos algorithm); on the public Internet with undefined participant list, it's hard. http://www.baum.com.au/~jiri/ae/blog/01306143707 http://www.baum.com.au/~jiri/ae/blog/01306143707
- hendzen 13y ago
  That is a correct definition of BFT, but as I said, Paxos does not tolerate Byzantine faults. Here's a direct quote [0] from Leslie Lamport, the author of the Paxos algorithm. Assume that agents can communicate with one another by sending messages. We use the customary asynchronous, non-Byzantine model, in which: • Agents operate at arbitrary speed, may fail by stopping, and may restart. Since all agents may fail after a value is chosen and then restart, a solution is impossible unless some information can be remembered by an agent that has failed and restarted. • Messages can take arbitrarily long to be delivered, can be duplicated, and can be lost, but they are not corrupted. So, to be clear, Paxos tolerates processes that crash arbitrarily, but not processes that send malicious or incorrect messages. For a consensus algorithm that does tolerate Byzantine faults, see Liskov's Practical Byzantine Fault Tolerance [1]. [0] - http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf http://research.microsoft.com/en-us/um/people/lamport/pubs/p... [1] - http://www.pmg.lcs.mit.edu/papers/osdi99.pdf http://www.pmg.lcs.mit.edu/papers/osdi99.pdf
  - sigil 13y ago
    I referred in the top level comment above to Byzantine Paxos, a modified version of Paxos that is BFT. http://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzantine_Paxos http://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzant...
    - hendzen 13y ago
      Ah - when the term Paxos is used it is usually in reference to the original, non-BFT algorithm. Also, Google's implementations of Paxos (in Chubby, as well as Megastore) are non-BFT, and I am not aware of any use of Byzantine Paxos in production elsewhere.

maaku 13y ago

> but AFAIK there is no rigorous proof yet that the selfish mining equilibrium isn't a real threat. It's very easy to detect and respond to. Point your miners at the large pools, and check if they are building off of non-public blocks. Respond accordingly.

sigil 13y ago
How do you know they're building off of non-public blocks if they're doing so in secret collusion? For what it's worth, Felten et al have a somewhat convincing (if not yet rigorous) argument that members of a so-called selfish mining pool have more incentive to defect than to continue cheating [0]. But, if a single entity controlled all of the 33%, defection is not a risk, and this entity could still claim an outsized share of the mining reward according to Eyal-Sirer. [0] https://news.ycombinator.com/item?id=6689329 https://news.ycombinator.com/item?id=6689329
- maaku 13y ago
  By running your own node. You can know what is public and what is not.
  - sigil 13y ago
    The selfish miner(s) build a blockchain in private and choose the right moment to reveal it. This paper describes it in more detail: http://arxiv.org/pdf/1311.0243v2.pdf http://arxiv.org/pdf/1311.0243v2.pdf
    - maaku 13y ago
      Who are the miners? Mining pools? Mining pools don't do the actual mining, they contract that out to their users. Anyone can run mining software pointed at any of the major pools and see what blocks they are building off of. There's no way for a mining pool to "build a blockchain in private." If not mining pools, then perhaps the concern is large hosted operators? There's only one of these that qualify, although there is insufficient data about their exact size (CEX.io, part of GHash.io, but only an unknown percentage of their hashpower is hosted). Mining is sufficiently decentralized so as to make large-scale selfing mining detectable, and the economics are such that small-scale selfish mining is unprofitable. I'm not claiming this will always be the case - there is sufficient cause to be concerned for the future as we are trending towards more centralization and hosted mining, not less - but it is certainly not a real concern now.