We can spot Peercoin as the turning point from the proof-of-work to the proof-of-stake blockchain and might find it very interesting or even awkward based on the knowledge of current blockchain architecture because it is basically 90% bitcoin mixed with a pinch of coin staking.

It seems that PeerCoin’s architecture failed to be included in the mainstream but still, it is meaningful to have a look at its idea as a kind of symbolic project.

Peercoin blockchain has its unique hybrid architecture which implements both proof-of-work and proof-of-stake into a single UTXO blockchain. As a proof-of-stake implementation, Peercoin introduces a notion of “coin-age”, which is simply a “currency_amount * holding_period” and uses it to generate a proof-of-stake block. For example, Alice accumulates 900 coin-days if she has received 10 coins and held them for 90 days.

It is quite easy to be confused when grasping that the proof-of-work blocks and proof-of-stake blocks co-exist in the same blockchain, but it is the most important feature Peercoin has implemented. A proposer of the proof-of-stake block pays himself by consuming his coin-age in a special transaction called “coinstake” and by newly minting coins as a reward of his proof-of-stake.

The coinstake transaction includes “kernel input” as a hash target protocol similar to the mechanism of proof-of-work finding a nonce value smaller than the target. The most important difference is that the proposer just needs to search over the limited space, unlike proof-of-work protocol (e.g. bitcoin) which requires the proposer to find nonce out of much broader space. This is possible because the target of the stake kernel is proportional to the coin-age consumed in the coinstake transaction. In other words, the more the proposer accumulated his coin-age, the easier the proposer successfully mines the new proof-of-stake block. Peercoin is theoretically more energy-efficient (and thus eco-friendly) than bitcoin at this point although it still requires computational block mining.

The new way of block mining needs the new fork-choice rule, as it cannot reuse the traditional longest-chain rule because the overall hashpower decreases significantly thanks to the new mechanism, but at the same time became much easier to be attacked. So, the fork choice rule is replaced by the coin-age based rule, in which we calculate the score of the forks adding each transaction’s consumed coin-age, and choose the one that has consumed more coin-age (higher score) overall.

The new coins are minted also based on the consumed amount of coin-age, for example, 1 cent per 1 year coin-age. So as a whole, this process of mining a new proof-of-stake block resembles the recent blockchain implementation of coin lockup (staking) and proportional reward distribution as its result. A participant of the Peercoin network is incentivized to lock up his coin in the wallet to raise a probability of mining a new proof-of-stake block. Once it is done, he earns a newly minted coin reward proportional to his amount of stake.

Nxt

Then Nxt comes after the Peercoin as a successive proof-of-stake experiment. Nxt discards the notion of “coin-age” Peercoin has introduced and devised a new mechanism called “pure proof-of-stake”. Every block in Nxt is generated using proof-of-stake, unlike Peercoin’s hybrid architecture. This is possible with the mechanism that makes an account simply having more balance more likely propose the next block and earn the transaction fees as a reward.

Each account calculates its target as follows: ‘base target value’ * ‘time since the last block’ * ‘effective balance of the account’. Effective balance is the only account-specific field, meaning that the more the account has its balance unmoved at least 1 day (this is the definition of ‘effective balance’ according to the whitepaper), the higher the target and thus probability of generating a new block becomes. Now you can see we have gotten closer to the current blockchain!

The interesting part of the Nxt is the “balance leasing”. An account may “loan” his block generation power to another account without giving up his control to spend the coin. One can set up a timeout until which the receiver can leverage the sender’s effective balance to raise the block generation power.

Transaction fees collected by the receiver will not be redistributed to the sender by default, but with some additional code, we can easily implement the system similar to the bitcoin mining pool. We might find out this “loan” resembles “delegation” in DPoS based blockchain (e.g. Cosmos-family blockchains) although it is intended to imitate pseudo-mining pool in PoS system with more flexibility.

This article is mostly a paraphrase of “Practical Byzantine Fault Tolerance” by Castro and Liskov.

Intro

By reviewing the paper “Impossibility of Distributed Consensus with One Faulty Process” [1], we went through the process of proving that no distributed consensus can satisfy both safety and liveness in an asynchronous network setting. That also means there is no ‘perfect’ distributed consensus, so we have to choose what to compromise between safety and liveness for the practical implementation.

We define safety and liveness as follows (I rephrased the definition mainly from the paper “Practical Byzantine Fault Tolerance” [2]):

• Safety

  All non-faulty nodes can agree on the sequence of requests, like a centralized implementation that executes operations atomically one at a time. i.e., if there has been a consensus between all non-faulty nodes, every node should be able to access the identical value.

• Liveness

  Clients who cast their request must eventually receive replies. It implies that the distributed system eventually achieves consensus or in other words, agrees on the same state.

PBFT is a practical implementation of a consensus algorithm that compromises liveness. Here, by ‘compromising’ I mean the existence of ‘synchrony’ because what we have proven to be impossible is the perfect consensus algorithm in an asynchronous network environment. In simple language, PBFT has introduced time-outs to ensure liveness.

This is quite an interesting phenomenon considering Nakamoto consensus because it chooses to compromise the safety, unlike PBFT choosing liveness. Safety can be understood as a blockchain term ‘finality’, and we know that there exist some forks in bitcoin generated mainly because of the network delay. The miners constructing blocks on fork A and fork B respectively do not access the identical value. But block production in bitcoin never stops, even in the asynchronous network environment.

“So, what’s better?”, you might raise a question, but that’s quite difficult to answer. Let’s figure it out step by step.

Definitions

Firstly, we need to demystify a few fuzzy words in this paper before proceeding to the actual PBFT operation.

• Replica: A node under distributed network circumstance.

• Fail-stop: Replicas might stop their operation due to errors. In this case, we call this abnormal status a ‘fail-stop’.

• Byzantine Fault: Replicas might revise the codebase arbitrarily and behave maliciously to the whole network. This is not simply ‘fail-stop’ status, so in this case, we call that specific replica a faulty node or Byzantine node.

• Asynchronous Distributed System: replicas are connected by a network that may fail to deliver the message by delaying them. i.e., no time-outs.

The PBFT algorithm provides both safety and (compromised) liveness assuming no more than [n-1/3] replicas are faulty. That means, if there are f amount of Byzantine nodes, the PBFT algorithm works only if the total number of 3f + 1 nodes are in the network (thus, we need 2f + 1 normal replicas). But why 3f + 1?

1. Faulty replicas might not be responding to the communication. So we need n-f replicas to be greater than 0 for successful communication, where n is the total number of replicas in the network. Thus, n > f.

2. We can think of a possible situation where f faulty replicas are in fact responding to the communication requests (of course maliciously, but other normal replicas can’t ensure whether they are honest or not), but another f amount of normal replicas are not responding. Still, we want the communications to proceed so n - 2f (f replicas that do not respond + f replicas that do respond but are faulty) should be greater than f (faulty nodes). Thus n -2f > f, and n > 3f.

3. n > f and n > 3f. Thus n > 3f

n is an integer value, so we need minimal 3f + 1 replicas in the network.

Normal-case Operation

So, finally we are here. Let’s now dig down the actual operation of the PBFT consensus algorithm. Here is the illustration for the lifecycle from the request to the reply:

‘C’ denotes a client who casts its request and expects to receive the result of its operation (or computation) in the form of ‘reply’. ‘0’ here is important in that it is the special replica that leads this stage, while the other 1, 2, 3 are the normal replicas. We call replica 0 as ‘primary’ and the others ‘backups’.

We need to keep in mind that all replicas (including primary) contain the state, a message log of accepted messages, and an integer denoting the replica’s current view which is a stage, or in a blockchain context, block number. A single view consists of roughly three phases: pre-prepare, prepare and commit.

As an overview of a view, a request from the client is handled through four steps: (1) a client sends a request to the primary, (2) the primary multicasts the request to the backups, (3) replicas execute the request and send a reply to the client, (4) the client waits for f+1 replies from different replicas with the same result. More sophisticated steps are shown below:

1. Firstly, client C requests the execution of state machine (replica) operation by sending a ‘REQUEST’ type message to the primary.

2. The primary receives the request from the client. This is the ‘request’ phase of the illustration above.

3. The pre-prepare phase now starts. The primary multicasts ‘PRE-PREPARE’ message to all the backups, with the information about the view and sequence number (order of request to be operated within a view) to which the request is assigned. This ‘PRE-PREPARE’ message is important in that the information the message contains is used as proof later if the primary is revealed to be a faulty replica.

4. All the backups accept a ‘PRE-PREPARE’ message from the primary replica after validation: they check whether the message signature is valid, and it is in adequate view, etc. If the messages are successfully received, then the pre-prepare phase now ends.

5. Prepare phase starts. Each backup node multicasts a ‘PREPARE’ type message to all the other nodes and adds both the ‘PRE-PREPARE’ and ‘PREPARE’ message to its local log.

6. A replica (including primary) accepts prepare messages and adds them to its log provided the information match with the ‘PRE-PREPARE’ message and is valid: it checks whether their signatures are valid, and their view number equals the replica’s current view, etc. Also, it checks 2f ‘PREPARE’ messages match with the ‘PRE-PREPARE’ message. If all the processes were successful then prepare phase now ends.

7. The commit phase now starts. All the replicas multicast ‘COMMIT’ type message to the other replicas. Replicas accept commit messages and insert them in their log after the validation process same with the ‘PREPARE’ phase.

8. Each replica ensures that prepare phase was successful and it has accepted 2f + 1 ‘COMMIT’ type messages from different replicas that match the pre-prepare for the request. If everything so far is successful, then the replica executes (or computes) the request. The commit phase now ends.

9. A replica sends the ‘REPLY’ type message to the client. The message contains (1) information of view number (similar to block height), (2) timestamp, (3) result of executing the requested operation, and (4) the unique number of replica who sends this message.

10. The client waits for f+1 valid replies from different replicas before finally accepting the result of the operation.

• pre-prepare and prepare phases so far ensure requests are totally ordered within the same view.

• prepare + commit phases are used to ensure that requests that commit are totally ordered across views.

Back to the illustration above, you might find backup replica 3 does not respond to the messages the others have sent. We don’t know whether it is in just fail-stop status or in fact a real Byzantine node but no matter what kind of replica it is actually, the client will successfully receive a reply of his request because there will be more than f (in this case, 1) confirmations from non-faulty replicas.

Even if the replica 3 is revealed to be a Byzantine node that responds to the message maliciously, the client will receive enough amount of correct messages thus should be able to confirm its validity.

View Changes

But what if the primary replica is a Byzantine node? It would take forever to make a consensus if the primary stops multicasting any messages. This is totally possible in an asynchronous network setting where infinite message delay is acceptable behavior. As we know already, PBFT introduces time-out i.e., synchrony to solve this critical problem to the liveness property: distributed system eventually achieves consensus.

All the replicas have their own timer which starts counting once it receives a request. When the timer of a backup expires in a specific view (let us denote that view as ‘v’), it stops accepting messages and multicasts a ‘VIEW-CHANGE’ type message to all replicas.

The new primary replica of view ‘v + 1‘ would receive 2f (not 2f + 1, because the former primary replica turned out to be a faulty node) valid ‘VIEW-CHANGE’ message and start new view ‘v + 1’ by sending ‘NEW-VIEW’ message to all other replicas.

This view change mechanism is the most interesting point of PBFT because this is why this consensus mechanism has the word ‘practical’ in its name. Under the PBFT mechanism, all the nodes process the serializable requests atomically with almost instant finality, and it is a quite meaningful property in the context of blockchain considering blockchain-specific operations like P2P payment. There always exists a risk of chain reorganization(reorg) in the implementation using the longest-chain rule (e.g., Nakamoto consensus) but PBFT is not, due to its maximized safety property. But this is only possible with the trade-off: compromised asynchrony as we have seen in the implementation of view change mechanism for the enhanced liveness performance.

Outro

There is one more weakness in the PBFT algorithm: heavy network consumption. To finalize a single view, the system requires roughly three phases that need for the message multicast. One-to-many messaging protocol consumes network bandwidth exponentially even though the number of participant nodes grows linearly. This is why PBFT is often combined with DPoS because it limits the number of maximum validator nodes under a certain capable threshold. And surely this leads to the innate limit on the degree of decentralization in the context of blockchain.

It is not a matter of “what mechanism takes an absolute advantage over the other” when choosing between BFT-family consensus and Nakamoto consensus. Each offers its own advantages with trade-offs thus, what is truly important is to start by defining the general purpose of the system (or the blockchain) and then choosing the mechanism that ‘fits’ that purpose.

References

[1] M. Fisher, N. Lynch, and M. Paterson. Impossibility of Distributed Consensus With One Faulty Process. In Journal of the ACM, 1985.

[2] M. Castro and B. Liskov. Practical Byzantine Fault Tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation, 1999.

Let us start by integrating some unfamiliar definitions in this paper. By reading through these concepts, you should be able to grasp the big picture of how the consensus protocol works. I added some illustrations to further understand how these concepts are linked together to form a protocol.

• consensus protocol: denoted by P (capital). This paper assumes that P is an asynchronous system of N processes (N ≥ 2).

• process: denoted by p (lower case). A process can be understood as a node, which has its internal storage, and state that is determined by inputs and a transition function. See Figure 1 below.

• input register: process p has one input register x_p with values either of b or 0 or 1.

• output register: process p has one output register y_p with values either of b or 0 or 1. process p has its y_p value as b initially, but as soon as it becomes 0 or 1, it cannot be changed (thus, output register is “write once”).

• internal state: The values in x_p and y_p comprise the internal state.

• initial state: initial state has its y_p value “b” but x_p value can vary.

• decision state: a state in which y_p has a value either of 0 or 1. once a process becomes the decision state, y_p cannot be changed anymore.

• transition function: transition function determines y_p (output). but cannot change y_p anymore once p becomes decision state.

• message: a message is a pair (p, m), where p is the destination process and m is a message value from a fixed universe M.

• message buffer: a FIFO queue of messages that have been sent but not yet received. message buffer supports two operations:

  1. send(p, m): send message m to the process p. place (p, m) in the message buffer.

  2. receive(p): deletes some message (p, m) from the buffer and returns m OR returns null and leaves the buffer unchanged.

• configuration: configuration consists of 1. internal state of each process and 2. contents of the message buffer. See Figure 2.

• initial configuration: a configuration in which each process starts at an initial state and the message buffer is empty.

• step: a step takes one configuration C to another configuration C’.

• event: event is denoted by e. e = (p, m), which means a receipt of m by p. e(C) denotes the resulting configuration, and we say that e can be applied to C.

• sequence: sequence σ is a set of multiple events.

• schedule: finite or infinite sequence σ that can be applied starting from C.

• resulting configuration: σ(C).

• reachable: if σ(C), σ(C) is reachable from C.

• accessible: a configuration reachable from some initial configuration is accessible.

So, with the background knowledge above, we are going to prove that:

Theorem: There is always a sequence of events in an asynchronous distributed system such that the group of processes never reach consensus

by showing that there is a case in which protocol remains forever indecisive.

Lemma 1

LEMMA 1. Commutativity property of schedules. Suppose that from some configuration C, the schedules σ1, σ2 lead to configurations C1, C2, respectively. If the sets of processes taking steps in σ1 and σ2, respectively, are disjoint, then σ2 can be applied to C1 and σ1 can be applied to C2, and both lead to the same configuration C3.

i.e., σ1(σ2(C)) = σ2(σ1(C)), if the sets of processes taking steps in σ1 and σ2 are disjoint.

PROOF: The result follows at once from the system definition, since σ1 and σ2 do not interact.

So, LEMMA 1 proves that schedules are applicable without considering an order, resulting in the same resulting configuration. This “commutativity” property of schedule is used to prove Lemma 3.

Lemma 2

We need to understand what the “valency” is before we step into the proof of lemma 2. Here is a table for the grasp.

• univalent: if all reachable configurations have decision value v (thus in a decision state), we just call the configuration univalent.

• 0-valent: univalent, with all of the reachable configurations having decision value 0.

• 1-valent: univalent, with all of the reachable configurations having decision value 1.

• bivalent: if all reachable configurations do not have the same decision value v, we just call the configuration bivalent.

LEMMA 2. Consensus protocol P has a bivalent initial configuration.

PROOF: We use contrary proof. Assume that P must have only univalent initial configurations. So, P must have both 0-valent and 1-valent initial configurations.

Let us call two initial configurations adjacent if they differ only in the initial value x_p of a single process p.

(REMINDER: initial configuration: a configuration in which each process starts at an initial state and the message buffer is empty. initial state: initial state has its y_p value “b” but x_p value can vary.)

If we list all the possible initial configurations, there must be two adjacent initial configurations, 0-valent and 1-valent respectively, and the only difference between them is the x_p value of a single process p.

Now we consider applying sequence σ to both initial configuration n and n+1 assuming that the process p does not take any step.

If sequence σ can be applied to initial configuration n, then it is also applicable to initial configuration n+1 because they are identical except the x_p value of a single process p, and now p is halted by the assumption. σ(config n) = σ(config n+1). If the decision value of configuration C is 1, then config n is bivalent. Reversely, if the decision value of configuration is 0, then config n+1 is bivalent. This contradicts the assumed nonexistence of a bivalent initial configuration. End of proof.

So, in short, LEMMA 2 proves that there exists a bivalent initial configuration.

Lemma 3

LEMMA 3. Let C be a bivalent configuration of P, and let e = (p, m) be an event that is applicable to C. Let C be the set of configurations reachable from C without applying e, and let D = e(C) = {e(E) | E ∈ C and e is applicable to E}. Then, D contains a bivalent configuration.

PROOF: Since e is applicable to C, then by the definition of C and the fact that messages can be delayed arbitrarily (by LEMMA 1), e is applicable to every E ∈ C.

We also use contrary proof here again. Now assume that D contains no bivalent configurations, so every configuration F ∈ D is univalent.

If F is a configuration reachable from E, then F is also either 0-valent or 1-valent since D contains no bivalent configuration by the assumption. As e is applicable to every E ∈ C, by an easy induction, there exist E_n and E_n+1 such that F_n = e(E_n) and F_n+1 = e(E_n+1).

Let event e = (p, m) and e’ = (p’, m’).

CASE 1: If p’ ≠ p, then F_n+1 = e’(F_n) by LEMMA 1. This is impossible, since any successor of a 0-valent configuration is 0-valent. i.e., F_n(0-valent configuration) → F_n+1(1-valent configuration) is impossible.

CASE 2: If p’ = p, then consider any finite deciding schedule from E_n in which p takes no steps:

Let σ the schedule, and let configuration A = σ(E_n). By LEMMA 1, σ is applicable to F_n and F_n+1, and it leads to 0-valent configuration G_n = σ(F_n) and 1-valent G_n+1 = σ(F_n+1). Also by LEMMA 1, e(A) = G_n and e(e’(A)) = G_n+1. So, configuration A is bivalent, but this is impossible since the schedule to A is deciding by the assumption. So A must be univalent. In this case, we reach a contradiction. End of proof.

So, LEMMA 3 proves that there exists a bivalent configuration that can be reached from the bivalent configuration.

Integration

Let us integrate the lemmas we have just proved so far and build a conclusion.

(LEMMA 1: schedules are applicable without considering an order, resulting in the same resulting configuration. i.e., commutativity property of schedules.)

LEMMA 2: there exists a bivalent initial configuration.

LEMMA 3: there exists a bivalent configuration that can be reached from the bivalent configuration, proved with LEMMA 1.

Considering LEMMA 2 and LEMMA 3, we can finally prove that there is a case in which protocol remains forever indecisive.

If there is a schedule that runs from bivalent configuration (whose existence is proved by LEMMA 2 and 3) to a univalent configuration, there must be a some single step that goes from a bivalent to a univalent configuration. Such a step determines the eventual decision value. It is always possible to run the asynchronous system in a way that avoids such steps by failing single process.

References:

https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf

https://www.cs.purdue.edu/homes/peugster/classes/CS505Spring09/10-Consensus.pdf

FEEDBACK IS ALWAYS WELCOMED! Please DM(@ysjlitt twitter) me if you find any errors in this article.