Using random linear network coding (RLNC) in asynchronous networks with one-to-many information flow has already been proven to be a valid approach to maximize the channel capacities. Message-based consensus protocols such as practical Byzantine fault tolerance (pBFT) adhere partially to said scenario. Protocol phases with many-to-many communication, however, still suffer from quadratic growth in the number of required transmissions to reach consensus. We show that an enhancement in the data transmission behavior in the quadratic phases is possible through combining RLNC with pBFT as one hybrid protocol. We present several experiments conducted on random network topologies. We conclude that using RLNC-based data transmission offers a significantly better performance under specific circumstances, which depend on the number of participating network nodes and the chosen coding parameters. Applying the same approach to other combinations of message-based consensus and network coding protocols promises not only a gain in performance, but may also improve robustness and security and open up new application scenarios for RLNC, e.g., running it on the application layer.
Notes
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
In this section, we state the addressed research questions in our work. We describe our selected approach and how it contributes to answering said questions. Moreover, we provide a brief outline of the structure of this paper.
1.1 Motivation and goal
In message-based consensus (cf. Section 3.3), where each participant communicates its view to many (if not all) other participants, the network communication complexity is quadratic in relation to the number of participants. The inherent many-to-many communication opens up the possibility to use network coding (NC, cf. Section 3.4) to improve the network communication performance [1]. However, running a consensus scheme on the application layer on top of an NC-enhanced link layer only works within closed network segments running the same NC scheme. The paper at hand answers the following research questions:
How can the positive effect of NC on message-based consensus be expanded beyond network segments?
How can we validate the feasibility of a first approach and determine its potential?
How can we expand beyond the feasibility investigation to reach a deeper understanding and a broader scope?
Advertisement
1.2 Approach
We integrate the consensus scheme with NC and run it on the same layer of the network. This allows for expanding beyond network segments, thereby broadening the application space of NC. Additionally, potential synergy effects may be used to our advantage. We conduct first experiments to confirm the feasibility and potential of the idea. In our setup, we choose blockchain consensus as our use case and construct one single protocol combining the phases of practical Byzantine fault tolerance (pBFT) [2] with random linear network coding (RLNC) features [1, 3]. For evaluation purposes, we provide a means to switch between RLNC-enhanced data transmission and the classical store-and-forward (SF) data transmission. Both are executed and compared within our theoretical network model. To this end, we introduce two different state machines based on RLNC and SF, respectively, through which the data transmission behavior of network nodes is determined. This allows for conducting comparative experiments, where the RLNC features are switched on or off depending on the chosen data transmission state machine. The experiments are executed with different fixed and variable parameters (e.g., number of network nodes, message block size) in order to isolate their effects. Doing this, we also develop an understanding on the remaining open questions and ideas on how to investigate them.
1.3 Contribution
The conducted experiments confirm that using an RLNC-based data transmission is indeed favorable in protocol phases that rely massively on broadcast (especially many-to-many) communication patterns. The experiments also reveal investigation approaches to deepen the understanding of the case presented in the paper at hand as well as ways to direct further investigations beyond the presented case.
1.4 Outline
We provide a validation of said approach and derive research topics as a starting point for further investigation. Section 2 offers an overview of similar and related work. In Section 3, we introduce the baseline of the conducted experiments, upon which we build the hybrid approach explained in Section 4. Sections 5 and 6 describe the conducted experiments and their evaluation. In Sections 7 and 8, we discuss possible further experiments and adjustments, as well as final thoughts and learnings reflecting on the validity of our approach.
2 Related work
Byzantine fault tolerance (BFT) introduced by Lamport et at. [4] refers to the property to achieve consensus in a distributed system in the presence of faulty nodes. After some earlier work (for the historical development see [5]) mostly dealing with the theoretical feasibility but with the drawback of inefficiency for practical use, Castro and Liskov [2] proposed a replication algorithm with an efficient realization, called practical Byzantine fault tolerance (pBFT).
Advertisement
The idea of network coding goes back to the work by Yeung and Zhang [6] where the authors considered the scenario that in satellites broadcast a data packet that results from the encoding of a several received packets and vice versa that a receiver decodes packets from more than one satellite. The idea of network coding was born, and it was rigorously developed by the Ahlswede et al. [1] who prove the max-flow?min-cut theorem for information flow analogous to the famous max-flow-min-cut theorem for commodity flow in graphs by Ford and Fulkerson [7].
In a randomized linear network coding approach (RLNC) (see [3, 8, 9]) for data transmission in multi-cast networks, a node that receives several incoming messages chooses uniformly at random a linear combination of the incoming messages and transmits this encoded message. It has been proven that this random linear combinations suffice to already achieve network capacity with a high probability.
Oggier and Datta [10] examine the resilience of regenerating codes creating redundancy against erasures and adversarial errors under Byzantine nodes, as compared to traditional erasure codes. However, the use of regenerating codes adds an additional overhead and computational complexity.
Liang and Vaidya [11] propose a network-aware algorithm for synchronous point-to-point networks using local linear coding to achieve increased throughput. The results do not apply for asynchronous networks and the algorithm needs to be implemented and tested.
Choi et al. [12] use a generalized replication and sharding scheme to scale the pBFT consensus protocol. They propose a theoretical framework for a network coded pBFT algorithm and show the possibility of reaching consensus within maximum bandwidth constraints using constant weight codes.
Lun et al. [13] design decentralized algorithms computing minimum-cost sub-graphs for multi-cast connections utilizing network coding. The proposed methods need further research for stability, speed, and computing demands.
In [14], Cebe et al. investigate the communication overhead of pBFT in an IoT setting using linear network coding. Their proposed system aims at reducing the packet overhead and minimizing the consensus completion time. This could improve scalability for medium-sized IoT networks.
Adat et al. [15] study the performance of random linear network coding for wireless mobile networks with a focus on pollution attacks and propose a blockchain-based message authentication scheme. Their network scheme needs to be tested in a real-world setting and the complexity and overhead of blockchain mining need to be reduced.
A related topic to consensus is gossip protocols in distributed systems, also known as epidemic protocols introduced by Demers et al. [16]. These protocols are designed to spread updates and information to replicas in a distributed system like in consensus protocols. Approaches based on linear network coding have been investigated and applied to epidemic protocols to improve performance and efficiency [17‐19].
In general, the related work addresses special use-cases, while we deal with a generic baseline scenario that still requires tailoring to these special scenarios to make a fair comparison. The paper at hand aims at showing that integrating consensus scheme with network coding into a hybrid protocol is an approach worth investigating further. Therefore, we compare simple SF scenarios with our RLNC-based protocol. The paper at hand is the extended version of [20], augmented by more detailed descriptions of the setup and a deeper analysis of the experimental results.
3 Assumptions and prerequisites
In this section, we describe the characteristics and assumptions of the components used in our experiment. We select one use case (blockchain), one consensus protocol (pBFT), one coding scheme (RLNC), and one network model (undirected connected graph). The assumptions and settings are made such that we obtain a generic baseline that provides effortless execution and measurements. Building upon this baseline, we can later deviate in a controlled manner to analyze the great variety of different application scenarios by adjusting the assumptions and choices.
3.1 The network model
The network is defined to be a directed graph G = (N, E) that consists of a set N = {0,…,n − 1} of nodes and a set \(E \subseteq (N\times N)\setminus \{(i,i) : i\in N\}\) of pairs of distinct nodes resembling the edges between distinct nodes, i.e., there is no edges from one node to itself. A directed edge (i, j) ∈ E is called the channel for the data transmission from node i to node j. We define our network to be synchronized and clocked in a way that transmissions over all channels happen simultaneously in regularly recurring fixed length intervals which we call transmission cycles. It is further assumed that the capacity of all channels is one, i.e., one fixed size message block can be sent from i to j within exactly one transmission cycle.
We assume (i, j) ∈ E if and only if (j, i) ∈ E, i.e., we either have direct connections between two nodes i and j in both directions or no direct connection at all. Consequently, one message block from node i to node j, as well as one message block from node j to node i can be transmitted during the same transmission cycle. Alternatively, we may think of the network as an undirected graph, wherein a message block can be simultaneously exchanged during the same transmission cycle between two directly connected nodes i and j in each direction. Also, if a node i has directed edges to the nodes j0,…,ja− 1, message blocks can be simultaneously sent from i to all neighbors j0,…,ja− 1 during the same transmission cycle.
We assume that the duration of a transmission cycle linearly scales with the (fixed) message block size in the network setting. As an example, if an 8 bit message block corresponds to a 1-s transmission cycle, a 16 bit message block corresponds to a 2-s transmission cycle, and a 24 bit message block corresponds to a 3-s transmission cycle, and so on. Then, the number of transmission cycles can be directly used to analyze the time complexity of protocols running on the network.
Two particular subsets of nodes are the set \(S\subseteq N\) of source nodes and the set \(D\subseteq N\) of destination nodes. For short, S is called source and D is called destination. We require that both S and D are non-empty. As the names suggest, messages are sent from source nodes to destination nodes only. Note that the source S and the destination D are not necessarily disjoint, i.e., a node i can be source and destination at the same time. Depending on the phase of the application protocol running on the network, source and destination may even interchange during protocol execution; as is the case, e.g., for blockchain consensus as shown in the paper at hand. Extremal cases in our scenario are \(\lvert S\rvert =1\) or S = D.
In order to allow potential data exchange between all pairs of nodes (sharing edges or not), we require the underlying graph G to be connected, i.e., there exists at least one path from i to j along the edges in G for all pairs (i, j) of nodes.
A data transmission protocol describes an algorithm that ensures that all messages originated at given source nodes will be transmitted to their respective destination nodes. We present the data transmission protocol from the viewpoint of the nodes. The behavior of the nodes is described by a finite state machine determining a node’s actions during a transmission cycle. It can be briefly summarized as follows: Each node contains a given type of storage. First, the node generates a message from the data in its storage that is then transmitted to selected connected nodes. After that, all incoming messages will be processed, discarded, stored, or accumulated. The data transmission protocol starts at the source nodes with preassigned messages. The protocol stops when all nodes stopped sending. Therefore, a stopping rule for each node must be defined. Note that the actual initialization and processing of data and distinguishing between source and destination nodes are left to the application protocol.
3.2 The store-and-forward-based state machine
The reference data transmission protocol we use in our scenario is the following version of store-and-forward (see Fig. 1).
Fig. 1
SF state machine
×
All nodes hold a queue of message blocks. During one transmission cycle, a node removes the first message from its queue and sends it simultaneously to all neighbored nodes. All simultaneously incoming messages at the node that were not yet received in a previous transmission cycle are added into the queue without any specific ordering. The transmission cycle is then concluded. A node transmits whenever its queue is not empty.
3.3 pBFT for blockchain consensus
A blockchain is a distributed, decentralized, and immutable ledger that consists of a linked list of blocks containing data [21]. It is based on distributed peer-to-peer networks in combination with public key cryptography and a consensus mechanism. The purpose of this data structure is to operate in untrusted networks and avoid single point of failure. A consensus mechanism (algorithm) is thus required to agree on the current state of the ledger and ensure the correctness of the stored data. There are several types of consensus mechanisms, such as leader-based and voting-based [22]. pBFT is a voting-based consensus protocol, where network participants (nodes) exchange message blocks in multi-cast manner, in order to agree on the data written into the blockchain. This kind of communication mostly yields quadratic complexity, depending on the observed protocol phase. Moreover, each participant acts based on a state machine, which is replicated across all network nodes. Thus, the participants are referred to as replicas. We describe the voting-based pBFT protocol from the perspective of a blockchain consensus application.
In the considered scenario, a set of r participants (replicas) of a blockchain network intend to reach consensus for a newly generated blockchain block. This is done in three consecutive phases (see Fig. 2): preprepare, prepare, and commit.
As we are not interested in the outcome of the actual consensus, the reply phase is omitted and will not be considered. In the preprepare phase, a leading participant (primary) sends a proposal of a new block to all other participants (backups). In the prepare phase, each backup node sends an acknowledge message to all participants if the node approves the proposed block. Note that the message containing the acknowledge message includes some piece of data ensuring the message origin and that the acknowledgment refers to the proposed blockchain block (e.g., digital signatures). After receiving \(2\lfloor \frac {r-1}{3}\rfloor +1\) valid prepare acknowledgments, each participant sends the commit acknowledge message to all other participants (also ensuring data origin and including a reference to the proposed block). Again, if a participant receives \(2\lfloor \frac {r-1}{3}\rfloor +1\) valid commit acknowledgments, the proposed block is accepted and added to the participant’s copy of the blockchain.
In general, the pBFT protocol is described for the application in which all replicas directly communicate with each other. Diverging from that, we consider the underlying network graph from a view where the nodes corresponding to replicas are not necessarily directly connected to each other and the mediating nodes are visible.
Given a network graph G = (N, E), we assume w.l.o.g. the set of nodes \(R=\{0,1,\ldots ,r-1\}\subseteq N\) to be the set of replicas. In particular, node 0 is defined to be the primary and {1,…,r − 1} is the set of backup nodes.
If \(r<\lvert N\rvert \), the set N ∖ R is the set of intermediate nodes, or intermediates for short. We explicitly allow cases where all network nodes belong to the set of replicas, i.e., R = N.
In each of the three protocol phases, we run a data transmission protocol. Depending on the phase, source and destination vary as shown in Table 1.
Table 1
Source and destination nodes by protocol phase
Phase
Source
Destination
Preprepare
{0}
R ∖{0}
Prepare
R ∖{0}
R
Commit
R
R
The number of initial message blocks preassigned to each source node in the prepare and commit phases is assumed to be one. The messages basically consist of acknowledge commands together with data authenticity information.
The number of initial message blocks at the primary in the preprepare phase can be greater than one since the proposal of a blockchain block, upon which the nodes might agree, may be considerably bigger than one message block.
Moreover, in all phases, the number of initial message blocks at the intermediate nodes is assumed to be zero, as they solely serve as connecting elements within the network, whose task is to relay any messages between the replicas.
3.4 Basics on random linear network coding (RLNC)
In this section, we explain the basics and general idea of network coding (NC), as well as its realization in a random linear setting.
3.4.1 Network coding in general
The idea (and purpose) of NC [1] is to save transmission bandwidth on network channels by combining various message blocks into a single message block that is transmitted by the sending node instead. Upon receiving sufficiently many different such combined message blocks, the destination node is able to unambiguously reconstruct the original message blocks.
This is most simply explained in broadcast scenarios as exemplified in the following. Figure 3 shows the same network setting twice, with an SF protocol (cf. Section 3.2) on the left and a simple NC protocol (based on xor) on the right. The nodes n1 and n2 exchange messages a and b over an intermediate broadcast node \(n^{\prime }\). The message blocks exhaust the capacity of a full transmission cycle of the channels, i.e., sending two message blocks requires two transmission cycles.
Fig. 3
Store-and-forward (left) vs. network coding (right) in a broadcast setting
×
On the left side, after receiving the message blocks a and b, it takes \(n^{\prime }\) two cycles to broadcast them back to n1 and n2. On the right side, the intermediate node \(n^{\prime }\) xors a and b (size retaining) and broadcasts back x = a ⊕ b in only one cycle, saving one cycle compared to the SF setting. n1 and n2 can easily extract b respectively a from x by xoring it with their original message, i.e., a = x ⊕ b and b = x ⊕ a.
3.4.2 Random linear network coding (RLNC)
Random linear network coding (RLNC) [8] is an implementation of NC and provides a proper trade-off between maximizing channel capacity and simplifying encoding complexity by utilizing some algebraic structures as detailed in the following and exemplified in Example 1.
First, we convert our message blocks into vectors over a finite field as follows (also cf. Example 1 part 1). Let x0,…,xs− 1 a fixed ordering of all s message blocks that may possibly be transmitted from source nodes to destination nodes. Let GF(q) denote the finite field over the prime power q (see [23]).
Assume that each message block xi is a sequence of b elements of GF(q), i.e., xi = (xi,0,…,xi, b− 1) ∈ GF(q)b for all blocks xi with 0 ≤ i < s. In other words, each (possible) message block xi is split into b sub-blocks xi, j. And each sub-block xi, j is bijectively mapped to an element ei, j of our finite field GF(q). Then, each message block xi can be unambiguously represented as a list of b elements of GF(q). Note that in practical implementations, the field size satisfies q = 2f for some positive integer f and therefore all xi, j correspond to chunks of f bits, and a message block consists in total of b ⋅ f bits.
Next, we ensure the linear independence of our vectors by prefixing linear independent headers as follows (also cf. Example 1 part 2). For 0 ≤ i < s let ui = (ui,0,…,ui, s− 1) ∈ GF(q)s denote the vector defined by the Kronecker delta, i.e., for all 0 ≤ i, j < s, we have ui, j = 1 if i = j and otherwise ui, j = 0. In other words, the i th vector ui has a 1 at the i th position and 0s in all other positions, making them linearly independent. By concatenation of ui and xi, we define the vector
for all 0 ≤ i < s. The part ui is called the header and xi the payload of yi. The vectors y0,…,ys− 1 are linearly independent (the leading entry 1 shifts from yi to yi+ 1 by one position) and define a basis of a subspace
Now, we utilize the properties of linear independent equation systems to restorably combine various message blocks into one as follows (also cf. Example 1 part 3). Instead of the original versions x0,…,xs− 1, random linear network coding starts with the encoded message blocks y0,…,ys− 1. From the incoming message blocks that are elements of the subspace W, the nodes generate random GF(q)-linear combinations zi ∈ W to be sent (cf. [3]).
Finally, the original message blocks can be unambiguously be reconstructed as follows (also cf. Example 1 part 4). If a destination node collects s linearly independent vectors z0,…zs− 1 ∈ W, it will be possible to recover the basis vectors y0,…,ys− 1 of W by means of Gaussian elimination. In order to perform the Gaussian elimination, we write the vectors z0,…,zs− 1 whereas zi = (zi,0,…,zi, s+b− 1) in a matrix Z = (zi, j) ∈ GF(q)s×s+b. Then, the Gaussian elimination on the rows of Z yields the matrix Y = (yi, j) = (U∣X) with unit matrix U = (ui, j) and matrix X = (xi, j) which contains the original message blocks as rows. Finally, cutting off the first s elements, i.e., the U part, from each vector yi yields the original message block xi with 0 ≤ i < s.
Example 1
We exemplify RLNC by on a small instance.
1.
We consider the ternary finite field GF(3), message block size b = 4, and three initial message blocks xi:
Let us assume a source node has the vectors y1 and y2 in its storage and wants to send them. The node chooses at random (and constructs) their linear combination 2 ⋅ y1 + 1 ⋅ y2 and sends that to the respective destination nodes:
We describe a RLNC-based data transmission protocol for usage in pBFT in order to obtain blockchain consensus (see Fig. 4).
Fig. 4
RLNC state machine
×
4.1 The RLNC-based state machine
All nodes have an individual storage to collect basis vectors of the vector space W that is generated by the initial message blocks of the source nodes. If s is the number of initial message blocks, the vector space dimension of W over GF(q) is s, which also determines the number of symbols from GF(q) in the message header.
During one transmission cycle, a node generates a random linear combination of the vectors in its storage and transmits it simultaneously to the connected nodes. All simultaneously incoming vectors at the node together with the vectors already contained in its storage will be used to calculate a canonical basis of the vector space spanned by the presented vectors. The storage will be overwritten with the determined canonical basis. Hence, the storage finally contains at most s vectors.
If the storage of a destination node contains exactly s canonical basis vectors, it can recover the whole set of initial messages by cutting off the s header symbols.
4.2 Initialization of source nodes
In the preprepare phase, the data transmission protocol has exactly one source node. In this case, the overall message (which contains the proposal of a new block of the blockchain) consists of a sequence of several message blocks x0,…xs− 1, of which each consists of b symbols of GF(q). The position i of xi in the sequence determines the header ui. The vectors (ui,xi) for 0 ≤ i < s are stored at the primary.
In the prepare and commit phases, there are s > 1 source nodes. Each contains exactly one message block of b symbols of GF(q). The header of each message consists of s symbols of GF(q). In both protocol phases, each source node knows the remaining source nodes: in the prepare phase, the source is the set of replicas except the primary, and in the commit phase, all replicas are exactly the source nodes. Therefore, the lexicographical ordering of the identifiers of the source nodes uniquely determines the position of 1’s in the header.
5 Experimental setup
In this section, we conduct experiments to compare the performance of pBFT based on SF and RLNC. We describe the parameters, the metrics, and the experimental results.
5.1 Setup
For the experiments, we define the following parameters:
r: The number of replicas.
i: The number of intermediate nodes.
b: The number of symbols chosen from the finite field the message blocks consists of.
g: The number of randomly chosen network graphs G = (N, E) with set N = {0,…,r + i − 1} of nodes and with set R = {0,…,r − 1} of replicas.
We conduct several experiments with different parameters r, i, and b. Per fixed r, i, and b we repeat the experiment g times with randomly chosen graphs (cf. Section 5.3). We run each pBFT phase separately and twice, once using the SF-based state machine (pBFTSF), and once using the RLNC-based state machine (pBFTNC).
5.2 Metrics
In order to compare the variants using SF vs. RLNC, we observe four values:
e: The number of transmission cycles. A transmission cycle resembles a clock tick in the synchronized way of sending messages. Each clock tick increases e by 1.
tx: The number of individual transmissions over the channels of the network. If a node simultaneously sends a message block to k neighbors, tx increases by k.
t: The elapsed time the protocol requires to send all message blocks from the source nodes to the destination nodes. The time unit we use is equivalent to one symbol of GF(q). To transmit one message block, either b time units are required for one transmission cycle using SF or s + b time units are needed if s initial message blocks are present using RLNC. Therefore, t will be computed by the number of time units per transmission cycle (either b or s + b) multiplied by the number of transmission cycles e.
da: The total amount of symbols of the finite field GF(q) transmitted over channels to transport all message blocks from the source nodes to the destination nodes. Analogously to the elapsed time, the number of individual transmissions tx multiplied by b in case of SF and by s + b in case of RLNC determines da.
For g randomly chosen graphs with the same parameters r, i, and b, we compute the average of the four values e, tx, t, da for SF and RLNC, respectively.
5.3 The graph model
In order to generate a graph, we randomly place n points in a rectangle and connect two points if their Euclidean distance is within a fixed value. This fits the scenario that the time unit to transmit one symbol from the finite field GF(q) can be considered as a constant value on all channels. As mentioned in Section 5.1, the assignment of roles (primary, backup, intermediate) to nodes is determined by their order of creation.
Note that the size of the plane does not matter. For our experiments, we chose a side ratio of 2:1. The Euclidean distance for each graph was chosen such that the randomly placed points yield a connected graph (i.e., there exists a path between each pair of nodes along edges through the graph). We start with a minimal Euclidean distance and successively increase its value until the graph is connected.
For instance, Figs. 5 and 6 show random graphs with 60 and 100 nodes, respectively.
Fig. 5
A random graph on 60 nodes
Fig. 6
A random graph on 100 nodes
×
×
6 Experiments
We start by presenting the arguments on our choice of experiments in Section 6.1, followed by remarks on how to read the presented figures in Section 6.2. We then explain and analyze the conducted experiments in the following Sections 6.3 to 6.7 and give an overall evaluation of our respective findings in Section 6.8.
6.1 Choice of experiments
In order to isolate the impact of individual parameters (see Section 5.1) on the behavior of RLNC vs. SF, we conduct a sequence of experiments with exactly one parameter changing respectively. We initially concentrate on the commit phase as it has the highest communicative complexity (see Fig. 2), which allows us to easily identify the different effects of RLNC vs. SF under changing parameters. Later on, we conduct a relative comparison of the commit phase to the preprepare phase and prepare phase for both RLNC and SF to draw conclusions for all major phases of pBFT.
We start our experiment series in Exp. 1 with establishing measurements of a base line scenario for the commit phase with a running number of replicas involved. Having this, we vary selected individual parameters (one at a time) of the follow-up experiments to study the effects they have on the protocol performance. This way a series of experiments is created where each shows different aspects of our protocol compared to the others.
In Exp. 2, we investigate the performance of our protocol for a varying number of replicas under a maximum relative overhead (RLNC header) by fixing the message block size (payload) to the minimum. This gives us measurements for a worst case ratio between RLNC header and payload.
In Exp. 3, we evaluate the behavior of our protocol under different ratios of overhead and payload by fixing the number of replicas and varying the message block size. This gives us measurements on the effect of the ratio between RLNC header and payload.
In Exp. 4, we investigate the effect of (only) varying the number of intermediate nodes. This gives us measurements on the effect of distance between replicas (in terms of hops between them) and the number of surrounding nodes.
In Exps. 5 and 6, compare the results of our base line scenario (Exp. 1) for the commit phase to the same scenario for the preprepare phase and prepare phase. This is done to confirm our assumptions (based on the respective communication complexity) that the prepare phase responds to our protocol very similar as to the commit phase and that the preprepare phase yields very little potential for improvement by RLNC.
6.2 Remarks on reading the figures
We use the elements bt0 to bt255 of the finite field GF(28), of which each symbol is represented by exactly one byte, as symbols for constructing our message blocks xi = (bti, a,…,bti, z); i.e., our message blocks are sequences of individual bytes. We denote the metric and parameter notation of the two state machines as indices XSF and XNC; e.g., eSF and eNC are respectively the number of transmission cycles for pBFTSF and pBFTNC.
In Figs. 7, 8, 9, 10, 11, and 12, we compare the gradient curves of e, tx, t, and da (y-axis) for pBFTSF and pBFTNC for varying numbers of either replicas r, intermediates i, or message block sizes b (x-axis) while pertaining the respective other parameters. While in Exps. 1 to 4 (Figs. 7, 8, 9, and 10) we only look at the commit phase, Exps. 5 and 6 (Figs. 11 and 12) concentrate on the preprepare and prepare phases. In Exps. 1 to 4 (Figs. 7, 8, 9, and 10), we also display the corresponding 95% confidence interval (CI). The number of randomly chosen graphs in each sample for each set of parameters is g = 100 which is large enough to maintain a small CI as depicted.
Note that the values for t and da are not directly measured, but calculated from the values of e resp. tx and the number of symbols of an individual transmission (b resp. s + b). Thus, we have:
When varying r or i, the values of e and tx are directly affected. The value for t is affected by the changing e. The value for da is affected by the changing tx and, in case of varied r while using pBFTNC, also by the increased header size s = r.
When varying b, the values for e and tx are not affected, but the values for t and da change directly.
6.3 Experiment 1 (Fig. 7)
Setting
We have a fixed message block size b = 16 bytes, a fixed number of intermediate nodes i = 20, and a varying number of replicas 10 ≤ r ≤ 100. The chosen values are an educated guess on a good choice of parameters to establish a base scenario.
Observation
While we observe a nearly linear growth of e and t for both SF and RLNC, the growth for RLNC is considerably more moderate. For both SF and RLNC, t is steeper than e (note the changed scale). The values tx and da grow faster than linear for SF. For RLNC, the growth of tx is nearly linear, da grows faster than linear.
Interpretation
For SF, the slopes of e and tx are caused by the increasing communication complexity CSF induced by the increasing r in the light of i and further details d of the network graph (distribution of replicas and intermediates, degree of connectivity, existence of bottlenecks, etc.). For CNC, we have two more factors to consider. First, as here \(\lvert y_i\rvert > \lvert x_i\rvert \) we have an overhead v = f(b, s) that depends on the message block size b and the size of the header s. Second, we have a profit p = f(r, i, d) through the superposition effects which depends, besides the number of nodes r + i, on the network details d.
With tSF = e ⋅ b resp. tNC = e ⋅ (s + b), b constant and s = r, t grows directly proportional to e (i.e., still near linearly). The gain in slope of tNC compared to eNC is bigger than for tSF compared to eSF, as tNC incorporates, besides b, also the linearly growing factor s = r. For analogous reasons, da grows faster than linearly and the gain in slope of da compared to tx is bigger for RLNC than for SF.
Conclusion
In the given setting, the commit phase is significantly more efficient for RLNC than for SF in all our metrics, with increasing advantage with increasing number of replicas. Here, network coding can freely unfold its power.
6.4 Experiment 2 (Fig. 8)
Setting
Exp. 2 differs from Exp. 1 only in the message block size b = 1, thereby investigating its effect on RLNC under a varying number of replicas.
Observation
Compared to Exp. 1, there is no significant change for e and tx. Also, the curves are still almost linear for t and non-linear for da. While for RLNC t is still significantly steeper than e, for SF, t is almost identical to e (note the changed scale). For both RLNC and SF, the curve of t is now flatter compared to Exp. 1, but considerably more for SF. Notably, the situation reversed and now the t-curve for RLNC is steeper than for SF. Analogously, while for RLNC, da is still steeper than tx, for SF, da is almost identical to tx (note the changed scale). For both RLNC and SF, the curve of da is now flatter compared to Exp. 1, but considerably more for SF. Again, the situation reversed and now the da-curve for RLNC is steeper than for SF. For SF, the values for t resp. da both differ closely around the factor 16 compared to Exp. 1.
Interpretation
The values for e and tx are unchanged compared to Exp. 1 as they only depend on the number of transmission cycles (e) resp. transmissions (tx) and not their size (b). The grades (linear, non-linear) of the curves of t and da follow from the reasons given in Exp. 1.
Given b = 1, for SF, we naturally have t = e ⋅ b = e ⋅ 1 = e and da = tx ⋅ b = tx ⋅ 1 = tx. For RLNC, we have t = e ⋅ (s + b) = e ⋅ (s + 1) and da = tx ⋅ (s + b) = tx ⋅ (s + 1) and thus, their difference in slope to e resp. tx is dominated by s = r.
The difference of the values for t and da for SF compared to Exp. 1 corresponds to the differences in b (16:1), i.e., sending 16 times less data is 16 times faster for SF. This is not the case for RLNC. While the superpositioning effects of RLNC are independent of b (e and tx are identical to Exp. 1), the overhead introduced by the RLNC header is diminishing its gain with increasing s. We define the ratio v between size of message block b and size of transmission s + b as follows:
$$ v = f_{v}(b,s) = \frac{b}{s+b} $$
(1)
Then, v indicates the amount of payload that can be conveyed per transmitted symbol from GF(q). Thus, a smaller v stands for a less effective information transmission. In any case, v becomes smaller with increasing s and thus, a transmission becomes more ineffective. Using bigger b mitigates the effect, but also comes with a downside. On the one hand, for fixed s, the effectiveness of the transmission is better for bigger b. On the other hand, while the relative drop of the transmission effectiveness for increasing s is lower for bigger b, the absolute drop is higher for bigger b.
Conclusion
In the given setting, the RLNC commit phase is significantly more efficient than SF in respect to e and tx, but less efficient in respect to t and da. Here, the effectiveness of network coding in terms of time t and data da is reversed by the unfavorable small ratio v. While bigger r in general come with a better performance of RLNC, they also come with the hampering shoe of bigger s. Bigger s lower the communication effectiveness v, and when combined with small b, can even lead to performance loss compared to SF. But, while bigger b lead to better relative performance of RLNC over SF, the absolute difference in performance decreases with increasing b.
6.5 Experiment 3 (Fig. 9)
Setting
We have fixed numbers of intermediates i = 10 and replicas r = 25. We vary the message block size 1 ≤ b ≤ 30 to study its effect on NC for a fixed number of nodes.
Observation
The curves for all metrics are nearly linear. The metrics e and tx are nearly constant and resemble what we saw in the previous experiments. The metrics t and da grow with b. While the values for t resp. da start lower for SF than for RLNC, they end higher for SF than for RLNC. That is, the curves for SF are steeper than for RLNC. We identify the intersection for both t and da before the message block size b = 4.
Interpretation
We restrict the detailed presentation of our interpretation to t, but the same holds analogously true for da by just replacing t with da and e with tx in the respective reasoning.
As neither r nor i change during the experiment, there are no non-linear effects and all dependencies remain linear. The values for e and tx are (nearly) constant as they only depend on the number of transmission cycles (e) resp. transmissions (tx) that remain unchanged during the experiment.
Thus, we assume e = ye and tx = ytx with ye resp. ytx being the y-intersect. For SF, we have:
$$ t_{SF} = e_{SF} \cdot b = y_{e,SF} \cdot b $$
With our running b, the slope of tSF is ye, SF and its starting point for b = 1 is ye, SF. For NC, we have:
With our running b, the slope of tNC is ye, NC and its starting point for b = 1 is ye, NC ⋅ (s + 1). The intersection (2) and the corresponding ratio of the slopes (3) are:
$$ \begin{array}{@{}rcl@{}} t_{SF} = y_{e,SF} \cdot b &=& y_{e,NC} \cdot (s + b) = t_{NC} \end{array} $$
Note that above equations are not bound to the concrete choice of r and i, but hold for varying b under any fixed r and i.
Conclusion
In the given setting, the SF commit phase outperforms RLNC in the metrics t and da for smaller message block sizes, but is outperformed by RLNC for bigger message block sizes. For small b, the induced low communication effectiveness v outweighs the gain of RLNC. With bigger b, the relative overhead becomes smaller and the superpositioning effects of RLNC kick-in.
6.6 Experiment 4 (Fig. 10)
Setting
We have a fixed number of replicas r = 25. The message block size b = 4 is set to the intersection from Exp. 3. We vary the number of intermediate nodes 0 ≤ i ≤ 300 to study its influence on RLNC.
Observation
As the measured values e and tx are equivalent for Exp. 1 (Fig. 7) and Exp. 2 (Fig. 8), we refer to Exp. 1 only for comparison with Exp. 4 at hand.
In contrast to Exp. 1, where the values for e increase with increasing number of nodes, here they initially drop fast and then show a nearly linear behavior with small negative slope. Nevertheless, the behavior of eNC is still comparable: almost linear and with negligible slope. While eSF has a small negative slope here (Exp. 4), in Exp. 1, eSF shows a substantial growth.
There is a range of parameters r and i, where Exp. 1 (r = 10,i = 20 to r = 40,i = 20) and Exp. 4 (r = 25,i = 5 to r = 25,i = 35) share the same number of nodes. We compare both experiments within this range. Here (Exp. 4) the e-values (for both SF and RLNC) start at roughly 300% and end at roughly 70% of their respective values in Exp. 1. While the relative effects are similar for SF and RLNC, in absolute values, the effects are substantially stronger for SF.
Just as in Exp. 1, here (Exp. 4) txSF shows clear non-linear growth and txNC shows nearly linear growth. Within the shared range, here (Exp. 4) the tx-values (for both SF and RLNC) start roughly at 400% and end at about 50% of their respective values in Exp. 1. In absolute values, the effects are substantially stronger for SF again.
Similar to e, the slope of t switched from positive in Exp. 1 to negative here (Exp. 4). Again, after an initial fast drop, t shows nearly linear behavior for both SF and RLNC. While tNC starts roughly at 120% of tSF, it quickly drops below tSF and ends at roughly 60% of the end value of tSF. We identify the intersection roughly at t = 225 with i = 8.
Compared to Exp. 1, the da-curves are significantly flatter here (Exp. 4) and somewhat closer to linear. The values for daSF and daNC start close but daSF ends significantly higher. Within the shared range, daSF starts roughly at 150% and daNC starts roughly at 300% of their respective values in Exp. 1. daSF ends at roughly 20% and daNC at roughly 50% of the end values (of the shared range) in Exp. 1. In absolute values, the effects are substantially stronger for SF again.
Interpretation
Unlike increasing r, increasing i does not imply a (quadratic or any other) growth of the communication nature between replicas. The same number of initial messages has to reach the same number of replicas, we just have more nodes in between or around. But it implies that we have a bigger avalanche effect of the messages through the network.
The eSF-value is significantly higher than eNC as while for SF, the avalanche effect leads to substantially more (duplicates of) messages that need to be transmitted one by one, in RLNC, the avalanche effect is kept down as simultaneously incoming messages are superpositioned and transmitted as one message.
Regarding the (initially) negative slope of e, we consider that additional intermediates are not only between the replicas, but also around them. Initially, the additional intermediates create shortcuts between the replicas, reducing the number of hops between them. Increasing i further two things happen: First, less and less potential shortcuts are available, decreasing the chance of speeding up the communication between replicas. Second, due to the quadratic growth of the area of the network graph, more and more intermediates are placed outside the paths between replicas (instead of prolonging the paths), nullifying their impact on the communication between replicas. This fits to the observed approximation of the e-curves to a horizontal line (constant e). Note that this is dependent on the way the network graph is constructed. If the graph construction keeps increasing the number of hops between the replicas with further increasing i, we would expect a turn point at which the slope of e finally becomes positive.
As tx reflects the number of all transmissions (between replicas or not), the quadratic nature of many-to-many communication determines its values, for SF together with a substantially stronger avalanche effect for SF than for RLNC.
As b and r are fixed, the values of t and da are just the values of e resp. tx magnified by the factors b resp. s + b. Also, the transmission effectiveness v (1) for RLNC is constant here, but its behavior in respect to the choice of b and s still holds. As nothing else influences the behavior of t and da, we have a trade-off between time and data which simply follows the shapes of the e and t curves.
At the intersect at i = 8, we have with v constant and (4):
$$ \begin{array}{@{}rcl@{}} e_{SF}(8) \cdot v = e_{NC}(8)\\ \frac{e_{SF}(8)}{e_{NC}(8)} = v. \end{array} $$
This is true for any intersects (or touch points) TPx at t = x (within the same experiment) and holds analogously true for da. We have:
$$ \frac{e_{SF}(TP_{x})}{e_{NC}(TP_{x})} = v = \frac{t_{SF}(TP_{x})}{t_{NC}(TP_{x})}. $$
Conclusion
We see that here the pBFTNC commit phase is more efficient than pBFTSF; for the metrics e and tx right from the start, for t and da when surpassing around i = 8 intermediate nodes. For both SF and RLNC, adding intermediates decreases the time t and increases the data d, but for both metrics, RLNC does a better job after surpassing a small threshold value for i. Still, for both SF and RLNC, the choice of i comes with a trade-off between time t and data da. The ratios of the e- and t-values at intersects (or touch points) equal v (cf.1).
6.7 Experiments 5 (Fig. 11) and 6 (Fig. 12)
Setting
Exp. 5 and Exp. 6 resemble the settings of Exp. 2, but deal with the preprepare and prepare phases. We have a fixed number of intermediate nodes i = 20 and a varying number 10 ≤ r ≤ 100 of replicas. We conducted the experiment with message block size b = 1, but as we deal in this experiment only with e and tx, the actual value of b is not of interest and we actually compare to our base line scenario (Exp. 1). Note that the structure of the shown graphs differs from the ones before. Each individual graph (with two curves) now shows the preprepare phase and the prepare phase, both as a percentage of the respective metric during the commit phase. Figure 11 shows the values for e and tx for SF. Figure 12 shows the values for e and tx for RLNC.
Observation
For the prepare phase, the values tend towards the those of the respective commit phase (ratio below 1 but close), with a clearer ramp-up phase for SF.
For the preprepare phase, the values for both SF and RLNC start significantly lower than in the respective commit phase (ratio below 1) and decrease further with increasing r. Here, the ramp-up phase is clearer for RLNC.
Interpretation
The inherent alikeness of the prepare and commit phases induces strong similarities (ratio close to 1) in their communication complexities under SF and RLNC. Both phases have quadratic complexity in regard to the number of replicas r.
The inherent one-to-many communication nature of the preprepare phase yields a linear communication complexity regarding the number of replicas r, which induces the significantly lower values for the metrics compared to the prepare and commit phases. Additionally, lacking different messages (from different senders) to be superpositioned, no gain from RLNC can be expected.
Conclusion
As the prepare and commit phase are quadratic in respect to the number of replicas, they dominate the complexity of the overall consensus protocol and should be run in RLNC-mode. As the preprepare phase yields no gain from RLNC, it should be run in SF-mode.
6.8 Evaluation
Using the right parameters, the prepare and commit phases of pBFTNC can be significantly more efficient than in pBFTSF considering the number of transmission cycles e and number of transmissions tx, which also induces superiority in elapsed time t and amount of data transmitted da. Increasing the number of replicas increases the performance advantage of pBFTNC over pBFTSF.
The message block size has significant influence on the effectiveness of pBFTNC compared to pBFTSF. While small message blocks are of advantage for pBFTSF, bigger message blocks are of advantage for pBFTNC. Given the right parameters, the tipping point to favor of pBFTNC can be as low as message block size b = 4, which is reasonably low. In general, the ratio between message block size b and transmission size s + b is a significant influencing value for the performance of pBFTNC, but comes with a trade-off between relative and absolute performance gain of pBFTNC vs. pBFTSF.
A higher number of intermediate nodes positively influence the effectiveness of the commit phase of both pBFTNC and pBFTSF. After surpassing a low threshold, the effect is notably better for pBFTNC. The time t even drops (for both pBFTNC and pBFTSF) when adding intermediates, causing a trade-off between time vs. data.
The preprepare phase does not gain from RLNC and should be run in SF-mode, but anyway has little influence on the overall performance of the consensus protocol.
In sum, increasing the number of nodes (replicas and/or intermediates) increases the significant performance advantage of pBFTNC over pBFTSF.
7 Future work
We differentiate between future work continuing the presented experiments, and investigations on further topics of merging message-base consensus with network coding.
7.1 Presented experiment
Expanding the parameter range (e.g., upper limit of nodes) and systematically varying two or more parameters at a time is assumed to consolidate the presented results.
A further theoretical underpinning with formulas describing the behavior of the metrics both in general and in particular for the points of intersect for increasing r between the changing number of r and the affected metrics e and tx, as well as the tipping point for increasing i may be of interest for further investigation. This also requires further experiments in regard to the running parameters such as s and b and the ratio \(v=\frac {b}{s+b}\).
Different network topologies and node distribution models are assumed to affect the information flow between the participants, and need to be investigated.
Presumably, further findings can be used to determine the most promising use cases and application scenarios, and thus compare the proposed approach to existing (coded) message-based consensus protocols.
7.2 Further topics
The actual semantics of the consensus and different possible fault ratios, as well as possible errors or malicious attacks on the protocol, are significant aspects which need further investigation. In the given scenario, for example, it is sufficient for the nodes to know the number or percentage of positive blockchain block acknowledgments. This opens the possibility to optimize the consensus protocol towards the usage of counting data structures (e.g., bloom filters) or trade a more efficient protocol run in case of consensus against a less efficient one in case of dissent.
Besides communication efficiency, integrating consensus and coding can also yield other advantages, such as for robustness or security, which may be worth investigating.
Blockchain consensus in (simple) connected graphs is only one of many thinkable application scenarios. Other use cases (e.g., cryptocurrencies, storage systems) in other network topologies (e.g., P2P, mesh) yield a wide space of application scenarios to be investigated.
The application layer (e.g., in the internet) can be seen as a fully connected network, at first glance not given RLNC (or other schemes) the space to unfold their power. But, bottlenecks aside from the degree of connectivity (e.g., bandwidth constraints, trust issues) may be defused with the help of RLNC.
Many combinations of consensus protocols (e.g., Ouroboros-BFT, Paxos) and network coding (e.g., erasure codes, regenerating codes) are possible and some may yield advantages over others in given contexts. It is also thinkable to look beyond consensus towards other many-to-many communication protocols such as multiparty computation.
Not least, one needs to map the suitable technology (consensus protocol, RLNC scheme) to fitting network settings (e.g., LAN, internet), application type (database, DLT), and/or sector (e.g., financial, health) and compare it to the established solutions.
8 Conclusion
The results from our experiments indicate at the example of pBFT and RLNC that integrating consensus and coding and running it on the same layer of the network is a valid approach deserving further investigation. Besides the possibility to directly leverage synergy effects, it also opens up the possibility to take advantage of RLNC on higher levels up to the application layer. There is much potential for future research, regarding the presented setup and more for other combinations of protocols, network settings, and application scenarios.
Acknowledgements
We thank Julian Geißler for his input to a previous version of this article.
Declarations
Conflict of interest
The authors declare no competing interests.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
