By "vote" in this article I'm referring to "lottery ticket purchases".
This shows how Nakamoto consensus can be viewed within the framework of classical BFT consensus proofs. In short, each hash performed by miners in Nakamoto consensus functions as both a "proof of identity" and a digital signature on blocks that enables 51% of hashing to be honest. "Selfish mining" that enables <50% attacks is only possible if honest miners switch tips before they've seen enough blocks to be sure the other tip has a higher hashrate. A different solution ("Colordag") was published in 2022 by reducing rewards after-the-fact if splits occur.
A novel aspect of Nakamoto consensus is that instead of requiring synchronization (timed rounds) to count votes, it uses time itself to count votes. Faster blocks means more valid voters (hashes) were participating, but instead of requiring a message from every voter, it assumes silence means failure of a hash to self-identify as the leader. Each silent hash is saying via silence to everyone "no, I am not the leader". The speed of blocks is proportional to the participating failures ("proportional" only when averaged over at least a few blocks due to exponential & Poisson distributions, with Erlang distribution N/(N-1) error).
To summarize, I conceptualize Nakamoto consensus as having 2 remarkable aspects that made it seem to violate old consensus proofs:
A block hash is a proof of valid identity and a digital signature
Speed of rounds counts identities, removing the need for all but the winning identity to report his presence.
This is background work to support reverse Nakamoto consensus which shows how to replace POW's hashrate with a POS-VDF stake-rate. This is done by 1) using a Verified Delay Function to prevent double-voting by giving a time-denominator to stake, and 2) reversing the Nakamoto consensus process because stake is on the chain before elections whereas hashrate proves itself during elections. This prevents the seed to randomization from being tainted by grinding attacks.
In order to get Byzantine fault tolerance (BFT) in distributed consensus with 67% of voters being honest, they're required to have clocks that are synchronized within a known max error in order for all voters to know when voting rounds begin and end. To do it with only 51% of the voters being honest, this synchronization is required as well as authenticating ("digitally signing") votes.[0] There are no known exceptions other than Nakamoto ("POW") consensus variants. How does POW do it? Who are the voters, how do they register, and how do they digitally sign their votes? It's usually treated as somewhat of a mystery or complicated[4][5], or Nakamoto consensus is denigrated by claiming it achieves "only" eventual or probabilistic consensus instead of "Byzantine consensus"[3]. But the probabilistic nature is a feature, not a bug, repairing damage from "temporarily successful" attacks that can't be fixed by any other method. It's not classified as Byzantine consensus or Byzantine agreement by noted authorities[1][2], ostensibly because it achieves Byzantine fault tolerance without seeming to possess the traditional requirements.
"Selfish mining" using < 50% to get blocks works only if miners switch tips when an alternate tip is only 1 to 3 blocks ahead. If honest miners follow a policy of not switching unless the alternate tip is 4 or 5 blocks ahead, a selfish miner would have to have > 45% of the total hashrate. So selfish mining is able to work with <50% only if honest miners are not waiting long enough to be sure the alternate tip has the higher hashrate it claims (no manipulative block withholding). In this way Nakamoto consensus is more synchronous in addition to having digital signatures in order to have nearly 50% protection.
Summary of Nakamoto consensus as a Byzantine consensus
Nakamoto consensus can be viewed as being within "traditional" Byzantine requirements by these substitutions. This shows Nakamoto consensus's success should not be used as evidence the traditional minimal requirements are in error, or that the lack of traditional requirements show that Nakamoto should be distrusted.
(previous hash+block+nonce) = identity & message.
hash(previous hash+block+nonce) = proof of identity (a cost) & "digital signature" of message. Hash requires equipment (not necessarily hardly any electrical cost) to be employed in time and after previous hash to prove there is no double-voting without at least a capital equipment expense. POS lacks this which is why it is difficult to get working. This is why VDF+POS can replace POS.
resulting solve time = measures number of "no, I lost" votes without communication.
Synchronous Voting
The beginning of each voting round in POW is clear to all: it begins when a new tip is received. All potential voters are sync'd to the beginning of the vote within propagation delays. If there is a glitch in the network, some voters will not be present. The end of a voting period is equally clear and "sync'd", but very different from a traditional method in not being a specific time or a specific length of time after the vote began. A measurement of time (node time) is still crucial (as described below) despite not defining "when" the vote begins and ends. As with traditional Byzantine consensus under similar circumstances, "network asynchrony" (propagation delays) must be small compared to the voting period.
Solvetime measures number of "no" votes
The average length (and therefore end point) of a POW voting period changes only when the hashrate changes. The variation in individual solvetimes due to the Poisson distribution for a given hashrate and difficulty is a fixed average. By revealing changes in hashrate, the number of voters (hashes) in the voting period is revealed. A traditional vote has a known number of voters by collecting all the votes and requiring them to vote in a fixed length of time. POW turns this upside down and uses the observed voting time to measure the number of voters. This enables it to use their silence as their "no" vote that says "no, my block hash was not below the target", saving a massive amount of communication. This is POW's most impressive feature. Normally at least two messages per voter are required: one to receive news of the previous winner and one to cast a vote. The best "traditional" Byzantine consensus mechanism that does not use this trick requires 8 rounds of communication.[1] POW does it with a single message (the block) for each voting round that announces the end of the previous round and beginning of the next round, and proves the winning vote was from a valid voter and "digitally signed".
Eventual probabilistic finality is a feature, not a bug
POW results in a chain that probabilistically demonstrates it had a higher sum of contiguous voters (in the face of a partitions) than any other chain, not that it necessarily had >50% of voters. This enables it to resolve network partitions, eventually. "Traditional" Byzantine consensus must also solve network partitions (accidental or malicious) eventually by the same method of waiting for partitions to resolve and many are permanently if they can never get >50% of the votes. This is not an option in BTC. And yet, "eventual consensus" is used like an insult and incorrectly cited as the cause of various problems.[3] Some researchers seem to re-defined Byzantine agreement to exclude "eventual probabilistic consensus" in order to make Nakamoto consensus distinct from the prior 30 years of "traditional" Byzantine consensus, but it is a fictitious division. The real reason for the division seems to be because it is not easy to see that Nakamoto consensus is working within the "traditional" boundaries. The purpose of this article is to show POW does not magically or by any failing circumvent the old proofs of decentralized consensus limits.
Voter registration is during the vote
Nakamoto consensus does away with the usual need for voters to register their identity or even their existence, but that does not mean it is not aware of their number, which is the only thing necessary in a yes/no vote where there is only one voter who will have the "yes" vote. The solvetime measures the number of "no" votes and only the winning "yes" voter needs to reveal himself. The hash has a cost that gives the right to vote, preventing Sybil attacks. "Right to vote" is another way of saying it gives the voter (a hash) an "identity" because cost is inherent to identity. With beautiful efficiency, that cost, which is inherently part of the real world through equipment and an energy expense, is also how a true physics-based randomness is obtained.
Voter identities (hashes) must be produced during the vote based on the previous hash winner. The production and cost of identity-formation during the vote without even knowing who the voters are is fundamental to how it's known these unknown voters exist and are not double-voting during the vote. This aspect is why the value of a stake in POS can't simulate everything a hash does. Both have a demonstrable value that can establish identity. But only when POS is combined with a Verifiable Delay Function (VDF) in a way that prevents double-voting during the vote can it work as well as POW (see my Reverse Nakamoto Consensus article). The centralization of masternodes with stake that is locked up over time is another way to prevent double-voting that deviates from the beauty and efficiency of POW.
[0] Digital signatures being required to enable 51% instead of 67% honest nodes was shown by Lamport et al in section 5 of their 1980 paper "Reaching Agreement in the Presence of Faults" and section 4 of their 1982 paper "The Byzantine Generals Problem". It enables every node to know what every other node voted. Requiring nodes to also synchronize enables every node to "see every vote".
Perhaps somewhat surprisingly, we do not yet have a practical solution for Byzantine consensus in the seemingly easier synchronous and authenticated (i.e., with digital signatures) setting. To the best of our knowledge, the most efficient Byzantine agreement protocol with the optimal f < n/2 fault tolerance in this setting is due to Katz and Koo [21], which requires in expectation 24 rounds of communication (not counting the random leader election subroutine).
[2] (Abraham et al 2016) Solidus: An Incentive-compatible Cryptocurrency Based on Permissionless Byzantine Consensus
See Table 1 that calls their Solidus mechanism "Byzantine" as if it is more like "classical" Byzantine mechanisms than "Nakamoto" consensus, despite also using POW and a permissionless setting. They define Byzantine consensus:
Byzantine consensus is a classical problem in distributed computing in which a fixed set of participants, each with an input value, try to decide on one input value, despite some participants being faulty.
which implies they justify calling their own permissionless POW Byzantine instead of Nakamoto consensus because they use a fixed number of committee members. But Lamport et al's 1980 and 1982 papers do not fundamentally require n to be a constant over more than 1 voting period, and if there is a network partition, an algorithm may accept whatever n it sees, indicating a fixed set of participants is not a valid way to define Byzantine consensus.
Later work revealed additional vulnerabilities [in POW] to transaction reversibility, double-spending, and strategic mining attacks [25, 31, 34, 35, 48, 3]. The key problem is that Bitcoin’s consensus algorithm provides only probabilistic consistency guarantees. Strong consistency could offer cryptocurrencies three important benefits.
They then go on to say existing solutions cause other problems (which are worse in the context of BTC). Their own solution was found unsatisfactory in [2].
The analysis of the blockchain consensus protocol (a.k.a. Nakamoto consensus) has been a
notoriously difficult task. Prior works that analyze it either make the simplifying assumption
that network channels are fully synchronous (i.e. messages are instantly delivered without delays)
(Garay et al, Eurocrypt’15) or only consider specific attacks (Nakamoto’08; Sampolinsky and
Zohar, FinancialCrypt’15); additionally, as far as we know, none of them deal with players
joining or leaving the protocol.
By "vote" in this article I'm referring to "lottery ticket purchases".
This shows how Nakamoto consensus can be viewed within the framework of classical BFT consensus proofs. In short, each hash performed by miners in Nakamoto consensus functions as both a "proof of identity" and a digital signature on blocks that enables 51% of hashing to be honest. "Selfish mining" that enables <50% attacks is only possible if honest miners switch tips before they've seen enough blocks to be sure the other tip has a higher hashrate. A different solution ("Colordag") was published in 2022 by reducing rewards after-the-fact if splits occur.
A novel aspect of Nakamoto consensus is that instead of requiring synchronization (timed rounds) to count votes, it uses time itself to count votes. Faster blocks means more valid voters (hashes) were participating, but instead of requiring a message from every voter, it assumes silence means failure of a hash to self-identify as the leader. Each silent hash is saying via silence to everyone "no, I am not the leader". The speed of blocks is proportional to the participating failures ("proportional" only when averaged over at least a few blocks due to exponential & Poisson distributions, with Erlang distribution N/(N-1) error).
To summarize, I conceptualize Nakamoto consensus as having 2 remarkable aspects that made it seem to violate old consensus proofs:
This is background work to support reverse Nakamoto consensus which shows how to replace POW's hashrate with a POS-VDF stake-rate. This is done by 1) using a Verified Delay Function to prevent double-voting by giving a time-denominator to stake, and 2) reversing the Nakamoto consensus process because stake is on the chain before elections whereas hashrate proves itself during elections. This prevents the seed to randomization from being tainted by grinding attacks.
In order to get Byzantine fault tolerance (BFT) in distributed consensus with 67% of voters being honest, they're required to have clocks that are synchronized within a known max error in order for all voters to know when voting rounds begin and end. To do it with only 51% of the voters being honest, this synchronization is required as well as authenticating ("digitally signing") votes.[0] There are no known exceptions other than Nakamoto ("POW") consensus variants. How does POW do it? Who are the voters, how do they register, and how do they digitally sign their votes? It's usually treated as somewhat of a mystery or complicated[4][5], or Nakamoto consensus is denigrated by claiming it achieves "only" eventual or probabilistic consensus instead of "Byzantine consensus"[3]. But the probabilistic nature is a feature, not a bug, repairing damage from "temporarily successful" attacks that can't be fixed by any other method. It's not classified as Byzantine consensus or Byzantine agreement by noted authorities[1][2], ostensibly because it achieves Byzantine fault tolerance without seeming to possess the traditional requirements.
"Selfish mining" using < 50% to get blocks works only if miners switch tips when an alternate tip is only 1 to 3 blocks ahead. If honest miners follow a policy of not switching unless the alternate tip is 4 or 5 blocks ahead, a selfish miner would have to have > 45% of the total hashrate. So selfish mining is able to work with <50% only if honest miners are not waiting long enough to be sure the alternate tip has the higher hashrate it claims (no manipulative block withholding). In this way Nakamoto consensus is more synchronous in addition to having digital signatures in order to have nearly 50% protection.
Summary of Nakamoto consensus as a Byzantine consensus Nakamoto consensus can be viewed as being within "traditional" Byzantine requirements by these substitutions. This shows Nakamoto consensus's success should not be used as evidence the traditional minimal requirements are in error, or that the lack of traditional requirements show that Nakamoto should be distrusted.
Synchronous Voting The beginning of each voting round in POW is clear to all: it begins when a new tip is received. All potential voters are sync'd to the beginning of the vote within propagation delays. If there is a glitch in the network, some voters will not be present. The end of a voting period is equally clear and "sync'd", but very different from a traditional method in not being a specific time or a specific length of time after the vote began. A measurement of time (node time) is still crucial (as described below) despite not defining "when" the vote begins and ends. As with traditional Byzantine consensus under similar circumstances, "network asynchrony" (propagation delays) must be small compared to the voting period.
Solvetime measures number of "no" votes The average length (and therefore end point) of a POW voting period changes only when the hashrate changes. The variation in individual solvetimes due to the Poisson distribution for a given hashrate and difficulty is a fixed average. By revealing changes in hashrate, the number of voters (hashes) in the voting period is revealed. A traditional vote has a known number of voters by collecting all the votes and requiring them to vote in a fixed length of time. POW turns this upside down and uses the observed voting time to measure the number of voters. This enables it to use their silence as their "no" vote that says "no, my block hash was not below the target", saving a massive amount of communication. This is POW's most impressive feature. Normally at least two messages per voter are required: one to receive news of the previous winner and one to cast a vote. The best "traditional" Byzantine consensus mechanism that does not use this trick requires 8 rounds of communication.[1] POW does it with a single message (the block) for each voting round that announces the end of the previous round and beginning of the next round, and proves the winning vote was from a valid voter and "digitally signed".
Eventual probabilistic finality is a feature, not a bug POW results in a chain that probabilistically demonstrates it had a higher sum of contiguous voters (in the face of a partitions) than any other chain, not that it necessarily had >50% of voters. This enables it to resolve network partitions, eventually. "Traditional" Byzantine consensus must also solve network partitions (accidental or malicious) eventually by the same method of waiting for partitions to resolve and many are permanently if they can never get >50% of the votes. This is not an option in BTC. And yet, "eventual consensus" is used like an insult and incorrectly cited as the cause of various problems.[3] Some researchers seem to re-defined Byzantine agreement to exclude "eventual probabilistic consensus" in order to make Nakamoto consensus distinct from the prior 30 years of "traditional" Byzantine consensus, but it is a fictitious division. The real reason for the division seems to be because it is not easy to see that Nakamoto consensus is working within the "traditional" boundaries. The purpose of this article is to show POW does not magically or by any failing circumvent the old proofs of decentralized consensus limits.
Voter registration is during the vote Nakamoto consensus does away with the usual need for voters to register their identity or even their existence, but that does not mean it is not aware of their number, which is the only thing necessary in a yes/no vote where there is only one voter who will have the "yes" vote. The solvetime measures the number of "no" votes and only the winning "yes" voter needs to reveal himself. The hash has a cost that gives the right to vote, preventing Sybil attacks. "Right to vote" is another way of saying it gives the voter (a hash) an "identity" because cost is inherent to identity. With beautiful efficiency, that cost, which is inherently part of the real world through equipment and an energy expense, is also how a true physics-based randomness is obtained.
Voter identities (hashes) must be produced during the vote based on the previous hash winner. The production and cost of identity-formation during the vote without even knowing who the voters are is fundamental to how it's known these unknown voters exist and are not double-voting during the vote. This aspect is why the value of a stake in POS can't simulate everything a hash does. Both have a demonstrable value that can establish identity. But only when POS is combined with a Verifiable Delay Function (VDF) in a way that prevents double-voting during the vote can it work as well as POW (see my Reverse Nakamoto Consensus article). The centralization of masternodes with stake that is locked up over time is another way to prevent double-voting that deviates from the beauty and efficiency of POW.
[0] Digital signatures being required to enable 51% instead of 67% honest nodes was shown by Lamport et al in section 5 of their 1980 paper "Reaching Agreement in the Presence of Faults" and section 4 of their 1982 paper "The Byzantine Generals Problem". It enables every node to know what every other node voted. Requiring nodes to also synchronize enables every node to "see every vote".
[1] (Abraham et al 2017) Efficient Synchronous Byzantine Consensus https://eprint.iacr.org/2017/307.pdf
[2] (Abraham et al 2016) Solidus: An Incentive-compatible Cryptocurrency Based on Permissionless Byzantine Consensus See Table 1 that calls their Solidus mechanism "Byzantine" as if it is more like "classical" Byzantine mechanisms than "Nakamoto" consensus, despite also using POW and a permissionless setting. They define Byzantine consensus:
which implies they justify calling their own permissionless POW Byzantine instead of Nakamoto consensus because they use a fixed number of committee members. But Lamport et al's 1980 and 1982 papers do not fundamentally require n to be a constant over more than 1 voting period, and if there is a network partition, an algorithm may accept whatever n it sees, indicating a fixed set of participants is not a valid way to define Byzantine consensus.
[3] (Kokoris-Kogias, 2016) ByzCoin Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing https://www.usenix.org/system/files/conference/usenixsecurity16/sec16_paper_kokoris-kogias.pdf The 6 references cited in the following are unrelated to probabilistic guarantees, so the assertion is without reference.
They then go on to say existing solutions cause other problems (which are worse in the context of BTC). Their own solution was found unsatisfactory in [2].
[4] (Garay 2019) The Bitcoin Backbone Protocol: Analysis and Applications https://eprint.iacr.org/2014/765.pdf
[5] (Pass, Sheman, Shelat, 2016) Analysis of the Blockchain Protocol in Asynchronous Networks https://eprint.iacr.org/2016/454.pdf