3 ms·

I'm reluctant to broach the subject, but is a "Blockchain" based system a solution to the "The Byzantine Generals Problem"? > A. All loyal generals decide upon

by gitgud 7y ago

I'm reluctant to broach the subject, but is a "Blockchain" based system a solution to the "The Byzantine Generals Problem"? > A. All loyal generals decide upon the same plan of action. All actors arrive at an immutable consensus (the current transaction group in the blockchain). > B. A small number of traitors cannot cause the loyal generals to adopt a bad plan It has protection against a small number of bad-actors as they require proof of work/stake which prevents against bad-transactions up until 51% attacks. I don't have much knowledge in the area though, any thoughts?

riffraff 7y ago
I am quite sure Satoshi Nakamoto suggested it as a probabilistic solution, yes, but not a full one[0] [0] https://ethereum.stackexchange.com/questions/40213/how-is-the-two-generals-problem-solved-with-proof-of-work https://ethereum.stackexchange.com/questions/40213/how-is-th...
- zzzcpan 7y ago
  The problem doesn't have a "full solution", like any fault tolerance in general, only probabilistic one.
exdsq 7y ago
Yes. There are several BFT compliant conensus algorithms for both Proof of Work and Proof of Stake. Some of them, such as Bitcoin, are BFT compliant because it's economically infeasible to complete an attack. Ouroboros is BFT compliant up to n/2-1 bad actors https://eprint.iacr.org/2018/1049.pdf https://eprint.iacr.org/2018/1049.pdf Edit: This goes back a comment I made the other day about 'Blockchain == Down votes' on HN. Why would you down-vote OPs question?
dooglius 7y ago
Yes, you can read it from the horse's mouth: https://www.metzdowd.com/pipermail/cryptography/2008-November/014849.html https://www.metzdowd.com/pipermail/cryptography/2008-Novembe...
celticninja 7y ago
That is literally what bitcoin is. A cryptographic electronic solution to the Byzantine generals problem. Given that almost all all other cryptocurrencies are forked from bitcoin, they too have this capability.
Kiro 7y ago
I thought that was the point of this thread since Byzantine is more or less a blockchain term at this point. Bitcoin maximalists that want to sound smart always refer to "Byzantine fault tolerance". Case in point: https://news.ycombinator.com/item?id=22296659 https://news.ycombinator.com/item?id=22296659 "I was just thinking about how you said you didn't like Bitcoin and imagining ways that it could be used to improve Wikipedia. More generally, Bitcoin can help any system to become more Byzantine fault tolerant."
fouc 7y ago
What I'm curious about is all the so-called "blockchain" tech that banks and others are implementing. If it's not a solution to Byzantine Generals Problem, and not de-centralized/distributed, then it can't be called a blockchain. So I'm wondering if that's the case, or if they really are solving BGP while still being largely distributed?
- hippich 7y ago
  Bitcoin is blockchain + POW. Git is blockchain. Chain of blocks of information where each consecutive block refers to the previous one (and one block can have multiple descendants, although this is not applicable to bitcoin) - is blockchain.
  - fouc 7y ago
    Git isn't considered to be a blockchain actually.
d10 7y ago
The authors of this paper didn't have "blockchain" in mind. Imagine rockets, or airplanes, with redundant systems on board. If, say, 3 of 4 sensors report "lower the landing gear" while 1 of 4 reports "don't lower the landing gear", then a hard requirement of the Byzantine Generals Problem is that "lower the landing gear" wins, assuming a majority of sensors function correctly (loyal generals). Nakamoto consensus addresses "double-spend". Say I have exactly one coin, and I broadcast a transaction that sends the coin to Alice. All miners on the network consider my transaction a candidate for the next block, and get busy hashing proof-of-work. Moments later, I compose a transaction that sends my one coin to Bob. And, I start mining a block with only that transaction in it. Now, its a race. If I win the race, the coin goes to Bob. If anyone else wins, the coin goes to Alice. Importantly, the coin will not go to both Alice and Bob. In Nakamoto consensus, exactly one miner wins each race. And that miner, "loyal" or not, determines whether the coin goes to Alice or to Bob. To satisfy Byzantine Generals, in this particular example, the coin should always go to Alice. But in Nakamoto consensus it might end up going to either Alice or Bob. Solving double-spend in a network of untrusted nodes is a significant feat. (And, according to the market, extremely valuable.) However, as I think your question is designed to point out, Nakamoto consensus does not solve the Byzantine Generals Problem. No offense to Nakamoto, it solves a different problem. It's worth mentioning the concept of "byzantine faults" - meaning a node on the network might not be simply buggy, it might be designed by a malicious adversary to do any behavior that could exploit vulnerability in other nodes. So, if you're reading the next revolutionary ICO whitepaper and see, "we use Nakamoto Consensus to solve double-spend, even in the presence of byzantine adversaries", maybe keep reading. But if you read, "we use proof-of-work to solve the Byzantine Generals Problem", maybe save your money for another investment.
remcob 7y ago
As it says in the abstract: "With unforgeable written messages, the problem is solvable for any number of generals and possible traitors". See also chapter 4. As soon as you allow digital signatures, you have unforgeable messages and Byzantine Generals is solved. No need for consensus algorithms, proof of work, or blockchains.
- SilasX 7y ago
  I don’t think that’s correct. You can still have signed-but-contradictory messages, ie the double spend problem where the signatures are valid but promise the same money to two different people (or promise different attack strategies). I think that statement would be correct if changed to “unforgeable messages with all same-side generals honest (and un-confused).
  - remcob 7y ago
    In the Byzantine Generals Problem as stated in the paper, there is a single commander that decides on the plan. Paricipants known the identity of the commander in advance. In this case signatures are sufficient. The problem you are describing is a different one, where there is no single commander and a group of generals needs to collectively decide on a plan. There signatures are indeed not sufficient. The way proof-of-work solves it is by randomly electing one of the generals to become commander for this decision round (i.e. 'it mines the block'). The random election is somewhat imperfect, leading to second order complexities such as probabilistic finality.
    - SilasX 7y ago
      Ah, okay -- I was thrown off by the phrasing in your second paragraph, which was assuming the same things the paper did. To make the context explicit, one could phrase it like, "As soon as you have digital signatures and centralization, then you don't need blockchain." (Edit: which, correspondingly, debunks the numerous proposed uses of blockchain where they can assume centralization.)
      - 7y ago

by gitgud 7y ago

riffraff 7y ago

I am quite sure Satoshi Nakamoto suggested it as a probabilistic solution, yes, but not a full one[0] [0] https://ethereum.stackexchange.com/questions/40213/how-is-the-two-generals-problem-solved-with-proof-of-work https://ethereum.stackexchange.com/questions/40213/how-is-th...

zzzcpan 7y ago
The problem doesn't have a "full solution", like any fault tolerance in general, only probabilistic one.

exdsq 7y ago

Yes. There are several BFT compliant conensus algorithms for both Proof of Work and Proof of Stake. Some of them, such as Bitcoin, are BFT compliant because it's economically infeasible to complete an attack. Ouroboros is BFT compliant up to n/2-1 bad actors https://eprint.iacr.org/2018/1049.pdf https://eprint.iacr.org/2018/1049.pdf Edit: This goes back a comment I made the other day about 'Blockchain == Down votes' on HN. Why would you down-vote OPs question?

dooglius 7y ago

Yes, you can read it from the horse's mouth: https://www.metzdowd.com/pipermail/cryptography/2008-November/014849.html https://www.metzdowd.com/pipermail/cryptography/2008-Novembe...

celticninja 7y ago

That is literally what bitcoin is. A cryptographic electronic solution to the Byzantine generals problem. Given that almost all all other cryptocurrencies are forked from bitcoin, they too have this capability.

Kiro 7y ago

I thought that was the point of this thread since Byzantine is more or less a blockchain term at this point. Bitcoin maximalists that want to sound smart always refer to "Byzantine fault tolerance". Case in point: https://news.ycombinator.com/item?id=22296659 https://news.ycombinator.com/item?id=22296659 "I was just thinking about how you said you didn't like Bitcoin and imagining ways that it could be used to improve Wikipedia. More generally, Bitcoin can help any system to become more Byzantine fault tolerant."

fouc 7y ago

What I'm curious about is all the so-called "blockchain" tech that banks and others are implementing. If it's not a solution to Byzantine Generals Problem, and not de-centralized/distributed, then it can't be called a blockchain. So I'm wondering if that's the case, or if they really are solving BGP while still being largely distributed?

hippich 7y ago
Bitcoin is blockchain + POW. Git is blockchain. Chain of blocks of information where each consecutive block refers to the previous one (and one block can have multiple descendants, although this is not applicable to bitcoin) - is blockchain.
- fouc 7y ago
  Git isn't considered to be a blockchain actually.

d10 7y ago

The authors of this paper didn't have "blockchain" in mind. Imagine rockets, or airplanes, with redundant systems on board. If, say, 3 of 4 sensors report "lower the landing gear" while 1 of 4 reports "don't lower the landing gear", then a hard requirement of the Byzantine Generals Problem is that "lower the landing gear" wins, assuming a majority of sensors function correctly (loyal generals). Nakamoto consensus addresses "double-spend". Say I have exactly one coin, and I broadcast a transaction that sends the coin to Alice. All miners on the network consider my transaction a candidate for the next block, and get busy hashing proof-of-work. Moments later, I compose a transaction that sends my one coin to Bob. And, I start mining a block with only that transaction in it. Now, its a race. If I win the race, the coin goes to Bob. If anyone else wins, the coin goes to Alice. Importantly, the coin will not go to both Alice and Bob. In Nakamoto consensus, exactly one miner wins each race. And that miner, "loyal" or not, determines whether the coin goes to Alice or to Bob. To satisfy Byzantine Generals, in this particular example, the coin should always go to Alice. But in Nakamoto consensus it might end up going to either Alice or Bob. Solving double-spend in a network of untrusted nodes is a significant feat. (And, according to the market, extremely valuable.) However, as I think your question is designed to point out, Nakamoto consensus does not solve the Byzantine Generals Problem. No offense to Nakamoto, it solves a different problem. It's worth mentioning the concept of "byzantine faults" - meaning a node on the network might not be simply buggy, it might be designed by a malicious adversary to do any behavior that could exploit vulnerability in other nodes. So, if you're reading the next revolutionary ICO whitepaper and see, "we use Nakamoto Consensus to solve double-spend, even in the presence of byzantine adversaries", maybe keep reading. But if you read, "we use proof-of-work to solve the Byzantine Generals Problem", maybe save your money for another investment.

remcob 7y ago

As it says in the abstract: "With unforgeable written messages, the problem is solvable for any number of generals and possible traitors". See also chapter 4. As soon as you allow digital signatures, you have unforgeable messages and Byzantine Generals is solved. No need for consensus algorithms, proof of work, or blockchains.

SilasX 7y ago
I don’t think that’s correct. You can still have signed-but-contradictory messages, ie the double spend problem where the signatures are valid but promise the same money to two different people (or promise different attack strategies). I think that statement would be correct if changed to “unforgeable messages with all same-side generals honest (and un-confused).
- remcob 7y ago
  In the Byzantine Generals Problem as stated in the paper, there is a single commander that decides on the plan. Paricipants known the identity of the commander in advance. In this case signatures are sufficient. The problem you are describing is a different one, where there is no single commander and a group of generals needs to collectively decide on a plan. There signatures are indeed not sufficient. The way proof-of-work solves it is by randomly electing one of the generals to become commander for this decision round (i.e. 'it mines the block'). The random election is somewhat imperfect, leading to second order complexities such as probabilistic finality.
  - SilasX 7y ago
    Ah, okay -- I was thrown off by the phrasing in your second paragraph, which was assuming the same things the paper did. To make the context explicit, one could phrase it like, "As soon as you have digital signatures and centralization, then you don't need blockchain." (Edit: which, correspondingly, debunks the numerous proposed uses of blockchain where they can assume centralization.)
    - 7y ago