Proof-of-Stake (POS) outperforms Bitcoin’s Proof-of-Work (POW)

Proof-of-Stake (POS) models are becoming highly desirable in Blockchain consensus designs, especially with the “Casper” upgrade underway for Ethereum, the second largest cryptocurrency by market cap. Yes, the immediate reason is that it is more energy efficient (reduces computational costs) as opposed to Proof-of-work (POW) which is highly resource intensive, but there’s more.

POS, in general, takes individual Digital Signature to prove ownership of the stake selected by the network, based on their proportional stake, in order to validate messages and transactions submitted to the database. If we look deeper, there are 2 main models that come under this category:

1. Chain based; which offers ‘availability’ as a validator is selected at random during a set time slot to create a block, which points to a previous block so that over time the blocks converge into one growing chain. This type is favoured for a more “permisionless” approach. Notable blockchain projects that implemented this model are Nxt, Peercoin, Ardor.
2. Consortium consensus- Byzantine Fault Tolerance (BFT) protocol: which offers ‘consistency’ as the validators randomly chosen for each round end up agreeing on whether or not the block becomes part of the chain. This type could be favoured for a more “permissioned” approach. Used by Neo, Tendermint, Polkadot, Hyperledge Fabric.

Last week, the BFT consensus algorithm was a heated topic in the industry as the NEO blockchain came to a halt in the face of a disconnected node in the network, leaving other nodes waiting for a reply. The issue was solved with a “forced changeview”, i.e restarting all the nodes, posing a question of centralisation, as power is still with NEO. This issue has subsequently caused increased block generation time in the network, where transactions are taking much longer, due to node synchronization issues. This problem has been interesting to watch, and a valuable learning curve for all other projects testing variations of this consensus model. The idea of the design is to have numerous nodes (lets say a hundred) in the network, so as to keep the “decentralised” notion and not have a single point of failure in order to ensure a problem like this does not occur. NEO, only having around 10 “bookkeeping nodes” have more of a “centralised” design. This fact is totally expected as NEO is a Chinese Blockchain economy, endorsed by the Chinese Govenrment itself, so it makes total sense. This is arguably the very most reason it is appealing to so many companies.

So what is BFT?

BFT is a popular protocol in distributed computing and has been studied since 1978 (when it was first introduced by Leslie Lamport). It has got over 700 protocols to date, as well as open source implementations. This has been a very popular model used for consensus in big “centralised” companies like Google, yet it is now also a popular choice in Blockchain projects as it aims to solve the Scalability issue. Popular projects using BFT protocols include Hyperledger Fabric, Tendermint, Polkadot, NEO, amongst others.

When it comes to consensus, the key is how to guarantee fault tolerance when it comes to non-honest and defective nodes on the network, as attacks and software error are common, causing nodes to display arbitrary behaviour (Byzantine Faults), best described as the analogy of “The General’s Problem”. The “Practical Byzantine Fault Tolerance” (PBFT) algorithm introduced by Miguel Castro and Barbra Liskov provides high-performance Byzantine state machine replication, processing thousands of requests per second with submillisecond increases in latency. This offers advantages like “consistency”, mentioned above, as the there should be agreement by the validator nodes before a block is generated. Another advantage is that it ensures settlement ‘finality’, speeds up settlement time to under 1 second from the current tens of seconds to tens of minutes, and at the same time reduces energy consumption dramatically. A BFT style consensus model is best suited for consortium blockchains that most financial institutions are favouring.

With Decentralisation, comes a performance tradeoff as seen with Bitcoin. BFT offers a more efficient consensus protocol, achieving better latency and throughput with less computation, bandwidth, and storage. Specifically, using a standard BFT protocol with a small number of pre-designated trusted entities/ nodes. “Even with dozens of nodes, PBFT greatly outperforms Bitcoin in both transaction latency and throughput. For example, 64 nodes processing batches of 8192 transactions can achieve a throughput of 4.5K tx/sec., average transaction latency of 1.79 sec., and an estimated resource cost per transaction of just $3.95 × 10–7 ” (1). This model involves a designated set of homogenous validator nodes that tolerate f-out-of-n faulty nodes. In this model, transactions are sent to consensus nodes for validation. The nodes validate the transaction and decide, then spread the results. The Data is deleted from the nodes after each validation round, so as not to clog the system. This Protocol can be customised to have a “controlled membership” model, where there can often be a central entity controlling membership (beneficial in the case of Financial Institutions/ Governments and some Private companies). It can also have a more “dynamic membership” which varies in the protocol itself, where membership is decided.

BFT & Blockchain

BFT protocols generally assume a synchronous or weakly synchronous nature, i.e they rely on a-priori nodes and network timing assumptions and only ensure liveness when the network behaves as expected. Therefore, in the case of decentralised blockchain implementations, there is an argument that these protocols come with faults and rather should demonstrate more of an Asynchronous nature in order to guarantee liveness without relying on node and timing assumptions. This is argued to significantly increase transaction throughput for scalability. The image below shows how different types of BFT protocols were able to achieve scalability and to what extent, showing that Parallel BFT achieved a high performance, getting closer to 100,000 tx/s throughput.

Scalability/ Performance Tradeoff (M. Vukolic: The Quest for Scalable Blockchain Fabric: Proof-of-Work vs. BFT Replication)

Parallel Consensus

Parellel BFT works through processing requests in parallel, through appointing multi-leaders, rather than a single leader in a basic BFT protocol. This allows for achieving high throughput and scalability. “Sarek” is a parallel ordering framework that partitions the service state to exploit parallelism during both agreement and execution. A Sarek implementation for Blockchain would be interesting. Instead of having one leader at a time for the entire system, it uses one leader per partition and only establishes an order on requests accessing the same partition. Sarek also supports operations that span multiple partitions and provides a deterministic mechanism to atomically process them. This ensures an increase in throughput performance by a factor of 2, at half the latency compared to a singleleader implementation, according to Sarek (2). Through Sarek, concurrent rounds of consensus can be run.

Asynchronous BFT

In an asynchronous setting, messages are delivered to different nodes under no timing assumptions. These settings are argued to be impractical as they limit throughput in a network. Attempts to solve this issue have been through attempting to solve redundant work through introducing ‘fairness’ (3) i.e. censorship resilience, which still allows for targeted censorship attacks. However new studies by A. Miller et al, (4) indicate that through the use of Threshold public-key encryption, these attack risks can be prevented.

Asynchronous BFT is specifically suited for blockchain implementations as in this field, bandwidth is a scarce resource and computation is ample, meaning that cryptographic elements like Threshold public-key encryption can be used, which otherwise are expensive (in classical fault-tolerance database settings) and therefore attacks diminished. In this case, rather than aiming for minimizing response time, even under disagreement (in standard BFT settings), messages are eventually delivered, while no timing assumption is made. Regardless of how network conditions fluctuate, throughput always tracks the network’s available bandwidth. With experimentation, this setting has demonstrated better throughput than PBFT protocols and has proved security and liveness (4). The Solution involves the process of ‘batching’ i.e creating a multi-party pool of nodes, to provide better efficiency and reduce cost, whilst using threshold encryption to preserve censorship resilience.

Conclusion

When it comes to comparing POS models with the first blockchain consensus model, Bitcoin’s Proof-of-Work (POW), based on Adam Back’s Hashcah POW function (1997), it is worth firstly remembering that there are so many POS variations including those of a BFT style, so it won’t be a like for like comparison, and a general comparison won’t suffice.

One of the most common arguments against POS is the issue of “stake grinding”, i.e turn manipulation (for creating the block and winning the reward). This can be solved through using a Threshold Signature Scheme that generates the key value for the next block creator. Also there is the “Nothing-at-Stake” problem that happens when dis-honest or arbitrary nodes create blocks on multiple chains , which can be solved with penalty measures, like loosing deposits.

Perhaps, the main question could be which model is best for future-proofing a chain, for scalability? In this case, a POS, BFT based model requires the least storage space, as less work, i.e (signatures) are needed, due to strong finality guarantees as the nodes involved in reaching consensus have to come to an agreement before actually generating the block. This means that transactions won’t put as much load on the blockchain. In addition, what was mentioned above about a basic BFT protocol outperforming Bitcoin in both transaction throughput and latency, not to mention resource costs. Let’s end with a comparison of resource costs of a transaction through a pBFT protocol ($39.4) and through POW Bitcoin mining (an average of $5,000 in the US, can reach up to $26,000 in South Korea).

1. Croman, Kyle et al, “On Scaling Decentralized Blockchains — (A Position Paper)”, Financial Cryptography Workshops (2016).

2. Li, Bijun et al, “SAREK: Optimistic Parallel Ordering in Byzantine Fault Tolerance”, 2016 12th European Dependable Computing Conference (EDCC) (2016).

3. Koblitz, Neal et al, “The State of Elliptic Curve Cryptography”, Des. Codes Cryptography 19 (2000).

4. Miller, Andrew et al. “The Honey Badger of BFT Protocols.” IACR Cryptology ePrint Archive (2016).