Fantom Archive — Fast Network Pruning Consensus for Consortium Blockchains
by Alex Kampa
Consortium blockchains
We place ourselves in the context of a consortium blockchain, in which all nodes are well known to each other and communicate using cryptographically signed messages. Therefore, nodes cannot impersonate each other.
There are n nodes, of which at most t can be faulty or Byzantine, the rest being honest. The nodes communicate over an asynchronous network: all messages sent eventually get delivered, but with arbitrary delays. The adversary has control over the (fixed set of) Byzantine nodes and over network delays.
Each node consists of a consensus engine and a deterministic state machine which are identical on all honest nodes. The role of the consensus engine is to communicate with other nodes and agree on ordered sets of transactions to submit to the state machine. It may also perform administrative tasks, such as seeking consensus on accepting new nodes and on rating or suspending nodes. The role of the state machine is to execute the transactions received from the consensus engine.
Valid transactions
In the context of a blockchain platform, a valid transaction is one that meets a set of criteria for being accepted for processing by the state machine. First of all, the transaction needs to be correctly formatted and signed. Other criteria may be related to the account sending the transaction, such as:
- Consistency of tx nonce;
- Minimum amount of tokens in sender account
- Maximum transaction volume per time period not exceeded, based for example on tokens held.
Note that after having been submitted to the state machine, a valid transaction may still fail to be executed. In other words, validity does not imply successful execution.
A transaction set is valid if it contains only valid transactions, and invalid otherwise.
An honest node can easily verify if a transaction or a transaction set is valid or invalid.
Naïve Consensus
Suppose a node k wishes to propose a transaction set {tx} to the other nodes by broadcasting the initial message INIT(k, {tx}), denoted INIT below. It is obvious that all honest nodes will agree on the outcome. Here is a possible consensus protocol.
Case 1: valid transaction set
Node k broadcasts INIT with a set of valid transactions
Each honest node i:
Upon receipt of INT, broadcast ACK — acknowledgement
Wait to receive (n — t) ACK messages
Then DECIDE(1) — transaction set accepted
Case 2: invalid transaction set
Node k broadcasts INIT with a set of valid transactions
Each honest node i:
Upon receipt of INIT, broadcast REJ(k) — rejection
Wait to receive (n — t) REJ messages
Then DECIDE(0) — transaction set rejected
This consensus protocol would only require one step and t < n/2.
Because there are at least (n-t) honest nodes, any node can expect to receive at least that many ACK (valid transaction set) or REJ (invalid transaction set) messages.
Note that an incorrect ACK or REJ sent by a faulty node would immediately be visible as such, and a procedure to remove the faulty node from the network could be initiated by the honest nodes.
Attacking naïve consensus
A Byzantine node may send INIT_1 to some nodes and INIT_2 to others. It is easily seen that Naïve Consensus does not defend against such attacks.
Assume n > 3t. Suppose the sending node is Byzantine, G0 is a group of n-2t honest nodes, G1 are the remaining t honest nodes and B is the group of t Byzantine nodes
The sending node sends INIT_1 to G0 and B, and delays sending to G1. All the honest nodes in G0 broadcast their acknowledgement to all, but the nodes in B only send acknowledgements to G0. The nodes in G0 will all DECIDE(1).
The sending node then sends INIT_2 to G1, and the nodes in this group will not be able to decide. As a result, we do not have Agreement.
Therefore, we need to agree on the content of the proposal.
Agreeing on proposed values
The sending node broadcasts INIT, which contains a proposed value, typically a set of transactions to process. REC(i) denotes the first received value by a node i.
PROPOSAL-PROTOCOL
Protocol for each node i, assuming n > 4t.
Step 1) wait to receive either INIT from the sending node, or a REC(j) message from any other node, whichever comes first. Broadcast this as REC(i) and add this value to SET(i).
Step 2) receive REC messages from up to (n-t) other nodes:
> as soon as a value is received that is different from REC(i), broadcast PROPOSE(0)
> if all (n-t) REC messages received are identical, broadcast PROPOSE(SET(i))
Step 3) wait to receive (n-t) proposals. Then set vote(i) to the proposal value that occurs the most often.
- Communicate with ABORT protocol at this step?
Step 4) Enter UNDERLYING-CONSENSUS(vote(i))
NB: At any stage of the process, a node receiving evidence that more than one value was proposed by the sending node enters or joins a REMOVE_NODE procedure, to be run in parallel
Lemma 1. If the sending node broadcasts only one value, and at least one honest node receives this value (either via INIT or REC), then all honest nodes propose that value.
Proof: because messages cannot be faked/nodes can’t be impersonated due to their digital signature, and the sending node sends only one value, Byzantine nodes can only delay sending messages. As soon as one honest node has received a first message, it will broadcast it which ensures that every other honest node will receive that message.
Lemma 2. If all nodes are honest, then all nodes propose the same value.
Proof: If all nodes are honest, the sending node is also honest, hence Lemma 1 applies.
Lemma 3. A Byzantine sender together with a single node can cause any desired number of PROPOSE(0) among honest nodes
Proof: Assume that all nodes are honest, with the exception of the sending node and one other node. The sending node sends INIT(v) to all the honest nodes. It sends INIT(v’) to the other Byzantine node, which remains silent at first. The adversary waits until the desired number (zero or more) of honest nodes send a PROPOSE(v). The adversary then allows the Byzantine node to send REC(v’) to all other honest nodes.
Lemma 4. If two honest nodes propose a non-zero value in step 2, then it is the same value #v.
Proof: In a set of n elements, the overlap between two subsets of (n-2t) elements is at least 2(n-2t) — n = n — 4t > 0. Each node receives (n-t) messages, of which at least (n-2t) are from honest nodes. Because of the overlap, at least one of the (n-2t) was sent by the same honest node.
Theorem 1. For all honest nodes, the vote(i) value is 0 or #v.
Proof: Among the (n-t) proposals received by an honest node, at least (n-2t) will be from honest nodes. By Lemma 4, these (n-2t) value can only be 0 or #v, therefore one of these values will occur at least (n-2t)/2 > t times. As a consequence, no other value proposed by the up to t Byzantine nodes can be chosen.
As a consequence of Theorem 1, the UNDERLYING-CONSENSUS can be a binary consensus with values #v and 0, any votes other than 0 and #v being treated as 0.
Optional, if we assume n > 5t (which may be reasonable for certain consortium blockchains), we can add two pre-processing steps to UNDERLYING-CONSENSUS, as described in [x — Bosco]:
UC-PREPROCESSING (Bosco)
Step 3a) broadcast vote(i)
Step 3b) wait until (n-t) votes have been received;
if more than (n+3t)/2 identical values v are received, DECIDE(v)
Else set vote(i) to the majority value received
Theorem 2: If all nodes are honest, decision in Step 3b is guaranteed if n > 5t
Proof: All nodes receive (n-t) identical votes #v, and we find that (n-t) > (n+3t)/2 if n > 5t.
We are left with one issue: what to do when the sending node does not broadcast?
Resolving the timeout problem
The idea is to have a group of nodes selected at each block ensuring that at least some of the nodes are honest. In [CGLR17] all nodes propose values, but are ordered in some random way that cannot be predicted in advance.
At the beginning of block processing, we have k ordered nodes with k > t. For i in [1..n] we start a PROPOSAL-PROTOCOL(i) as described above, as well as an ABORT(i) protocol. Because at least one of the k nodes is honest, we know that at least one of the PROPOSAL-PROTOCOLs will succeed in agreeing on a value.
We then simply take the one or more of these resulting values as the result of the process.
If, as in [CGLR17], we take the successful PROPOSAL-PROTOCOL(i) with the smallest i, we will not have to deal with transaction ordering issues. Once any agreement is reached for an index j, we can also stop participating in processes > j.
The ABORT(i) protocols serve to identify muteness failures. It
TRIGGER PROTOCOL for node i
Node i participates in multiple PROPOSAL-PROTOCOLS. As soon as it decides a value in one of these protocols, it emits an internal TRIGGER message (this is not broadcast)
ABORT PROTOCOL for node i
Before the TRIGGER: vote(0, j) is broadcast upon entering PROPOSAL-PROTOCOL(i), i.e. when a first INIT or REC is received for that process.
After TRIGGER: for any j in [1..n] for which a vote(0, j) was not yet issued, a vote(1, j) is issued.
The ABORT protocol is simply a binary consensus protocol. When the value 1 is decided for ABORT(j), then PROPOSAL-PROTOCOL(j) is ignored. We need to show that this never happens when an honest node has decided PROPOSAL-PROTOCOL(j).
Main References
[SR08] Yee Jiun Song, Robbert van Renesse R. Bosco: One-Step Byzantine Asynchronous Consensus. In Taubenfeld G. (eds) Distributed Computing. DISC 2008. Lecture Notes in Computer Science, vol 5218. Springer, Berlin, Heidelberg. 2008.
[CGLR17] Tyler Crain, Vincent Gramoli, Mikel Larrea, and Michel Raynal. (Leader/Randomization/Signature)-free Byzantine Consensus for Consortium Blockchains. 2017.
Others
[BFK17] Alex Biryukov, Daniel Feher, and Dmitry Khovratovich: Guru: Universal Reputation Module for DistributedConsensus Protocols. University of Luxembourg. [link]
[MMR] Achour Mostéfaouil, Hamouma Moumen and Michel Raynal. Signature-Free Asynchronous Byzantine Consensus with t < n/3 and O(n 2 ) Messages. IRISA. 2014. [link]
Achour Mostefaoui, Michel Raynal. Asynchronous Byzantine Systems: From Multivalued to Binary Consensus with t < n/3, O(n 2 ) Messages, O(1) Time, and no Signature. 2015. 〈hal-01102496〉[link]
