See discussions, stats, and author profiles for this publication at: [Link]

net/publication/327368868

ComChain: Bridging the Gap Between Public and Consortium Blockchains

Conference Paper · July 2018

DOI: 10.1109/Cybermatics_2018.2018.00249

CITATIONS READS
7 781

2 authors, including:

Vincent Gramoli
Data61-CSIRO and University of Sydney
129 PUBLICATIONS   1,073 CITATIONS   

SEE PROFILE

Some of the authors of this publication are also working on these related projects:

Empirical Blockchain View project

Data Structures for Multicores View project

All content following this page was uploaded by Vincent Gramoli on 01 September 2018.

The user has requested enhancement of the downloaded file.

 ComChain: Bridging the Gap Between Public and
Consortium Blockchains
Guillaume Vizier Vincent Gramoli
École Polytechnique University of Sydney
[Link]@[Link] [Link]@[Link]

Abstract—As an alternative to the energy greedy proof-of- by identifying its dynamic set of deciders and (ii) allows any
work, new blockchains constrain the set of participants whose participant to become a decider.
selection is debatable. These blockchains typically allow a fixed To this end, the community blockchain relies on a new type
consortium of machines to decide upon new transaction blocks.
In this paper, we introduce the community blockchain that
of blocks: the configuration block. Its role is to define among
bridges the gap between these public blockchains and constrained all participants a subset of deciders responsible for deciding
blockchains. The idea is to allow potentially all participants to the upcoming transaction blocks. More precisely, each config-
decide upon “some” block while restricting the set of participants uration block lists a configuration as a set of deciders identified
deciding upon “one” block. by their public key. These n nodes keep adding new transaction
We also propose an implementation called ComChain that
blocks. These nodes can also propose new configurations to
builds upon the Red Belly Blockchain, the fastest blockchain we
are aware of. It runs a consensus among the existing community each other, and, despite t < n3 Byzantine nodes, n − t correct
to elect a new community. This reconfiguration speeds up as the must reach a consensus on one configuration. These nodes
number of removed nodes increases. have the responsibility of selecting a configuration that is
Index Terms—Community blockchain, reconfiguration acceptable according to application-specific rules.
We also propose an implementation of this community
I. I NTRODUCTION blockchain, called ComChain, that does not require synchrony.
ComChain builds upon the Red Belly Blockchain [15]. In
A blockchain is an abstraction representing a linked list of ComChain, the genesis block stores the initial configuration
blocks implemented in a distributed system of nodes who can as the set of deciders. Upon reception of transactions, these
have two different roles: (i) clients that can read and write the deciders validate them and agree to append a new block of
data and (ii) deciders that run a consensus algorithm to decide validated transactions. Once these deciders reach an agreement
upon the block at a given index of the chain. Various types on a new acceptable configuration, they sign the configuration
of blockchains exist, that differ mostly in the way their nodes and store it into a new configuration block. From this point
have permissions to play specific roles, and in the consensus on, the new configuration defines the new set of deciders for
algorithm deciders run to agree upon new blocks. the blockchain until the next [Link] distributed
In public blockchains [18], [22], all nodes are potentially experiments confirm that the reconfiguration can occur at
deciders and can participate in the creation of new blocks [25]. runtime without impacting ongoing transaction requests.
To cope with Sybil attacks, they typically restrict the power of Section II presents an overview of the related work. Sec-
a user to its resources (e.g., computational power or amount tion III introduces our model. Section IV presents our solution
of coins). Provided that the malicious users do not own a at a high level. Section V specifies a detailed implementation,
large portion of the resources of the system, they cannot called ComChain. Section VI illustrates how our reconfig-
impose their decision to the others. In consortium and private uration mechanism performs empirically and Section VII
blockchains, synchronous implementations are rarely used due concludes. The proofs are deferred to a longer paper.
to their weakness against known network attacks [19]. Instead,
the permission for some nodes to act as deciders is hardcoded II. R ELATED W ORK
[6], [24]. Thus, each time the set of deciders changes, the To the best of our knowledge, no deterministic blockchain
whole blockchain must be stopped and restarted. implementation supports a dynamic membership. Probabilistic
This lack of dynamism is a major issue in long-lived alternatives revert typically to proof-of-* [18], [22], [20], [1],
blockchains where hardware components fail and consortia randomized consensus [10] or sortition [12]. This randomness
evolve. Hence, such systems are often considered too “central- is in contradiction with the concept of community blockchain
ized” due to the inalterable power they offer to their deciders. that trusts the current configuration to choose an acceptable
In this paper we cope with these two issues, by offering new configuration deterministically.
a community blockchain model that bridges the gap between Deterministic reconfiguration was however suggested online
public and consortium/private blockchains. In particular, a in several blockchain projects. Hyperledger Fabric aims at
community blockchain (i) inherently copes with Sybil attacks supporting membership changes without compromising the
network1 , however, it “requires that the peer or orderer process
tx tx tx
is restarted”2 . Tendermint mentions validator set changes [26], genesis config config
block block block
block block block
however, this requires an external application that handles listing tx tx listing tx tx listing
those reconfigurations.3 In contrast, our reconfiguration is non- tx tx tx
D0 block block D1 block block D2
block block block
disruptive and the main feature of ComChain. b1 b2 b3 b4
Until now, researchers have designed reconfiguration al-
blocks decided by D0 blocks decided by D1 b
gorithms for cluster membership changes [16], rolling up-
Fig. 1: A community blockchain
grades [14], atomic storage [13], [21] or replicated state
machines [17], [2], but not blockchains. Blockchains resemble • Correctness threshold: for all instances of consensus I,
replicated state machines in that they also support transactions, with CI the number of correct nodes in Π for consensus
however, each new decided transaction block depends on the I, 2n
3 < CI .
previous block as opposed to the independence of replicated
We also assume that the nodes always have enough storage
state machine commands.
capacities to store the blockchain-related information and the
non-committed transactions issued by the clients.
III. M ODEL
Definition 2. A new configuration, with regard to a configura-
The system is made up of a set Π = {p1 , . . . , pn } of
tion Π, is a configuration of n0 nodes, fulfilling the following
n processes, i is called the index of pi . These processes
additional requirements :
proceed at their own speed (asynchronous) and execute one
• Network: we have a partially synchronous point-to-point
step at a time (sequential). As consensus cannot be solved with
reliable network for all correct nodes in Π ∪ Π0 ,
asynchronous communication in the presence of failures [11], 0
• Listening: all correct nodes of Π expect to receive
we assume that communication is partially synchronous in that
information from the current configuration, and possess
messages get delivered in a bounded amount of time but the
the code to handle this information correctly.6
bound is unknown. Note that this assumption is weaker than
the one made by mainstream blockchains [18], [22]. To guarantee integrity, nodes sign their proposed configu-
We consider a dynamic Byzantine failure model. A node rations. We thus assume an asymmetric crypto-system where
is said to be correct during a time frame ∆ if it follows each node has a private key associated with a publicly known
its specification during that time frame. A node is said to key so that no existing private key can be forged or stolen. To
be Byzantine during a time frame ∆ if it stops following its allow new blockchain participants to join the correct service
specification at any time during that time frame. A node is said with certainty, we assume a correct DNS service keeping track
to be correct (resp. Byzantine) within the ith consensus instance of the latest configuration. Similarly, Bitcoin [18] uses hard-
if it is correct (resp. Byzantine) for the time frame between coded DNS seeds that are assumed trustworthy. An additional
its proposal and its decision for this consensus instance. trust assumption has been proven necessary in [9].
A consensus instance is one execution of a consensus
IV. T HE C OMMUNITY B LOCKCHAIN
algorithm. Each consensus instance can replace the set of n
deciders, among which t < n3 can be Byzantine, by another In this section, we introduce the community blockchain
0
set n0 of deciders where t0 < n3 can be Byzantine. More paradigm to bridge the gap between public and consortium
generally, n, n0 , ... represent the number of deciders, and t, t0 , blockchains. Community blockchains constrain the set of
... are upper-bounds on the number of Byzantine nodes among deciders for a particular block but let potentially all nodes
them. Each consensus instance occurs one at a time and n − t decide upon some block, by periodically replacing the set of
nodes have to propose a value to launch a consensus instance deciders by a new valid configuration.
among n deciders. Although not specified here, we assume that A. Two lists of blocks
correct deciders propose periodically as part of their protocol, To store the current configuration, the community block-
so that consecutive consensus instances get launched. chain contains two types of blocks: the classic or transaction
blocks with transactions and the configuration blocks (cf.
Definition 1. A configuration is a set Π of n nodes, fulfilling
Definition 3) with a set of deciders. The resulting structure
the following requirements :
resembles a skip list depicted in Fig. 1. At the bottom, all
• Network: we have a partially synchronous point-to-point
blocks are chained together with a linked list. This guarantees
reliable network for all correct nodes in Π4 ,
that all blocks are totally ordered. At the top, the configuration
• Awareness: all correct nodes have knowledge of the full
blocks are chained together with another linked list, hence
blockchain5 ,
1 [Link] allowing to verify that the current configuration is properly
2 [Link] signed by the deciders of the previous configuration.
3 Section 7.1, second paragraph of [Link]
handle/10214/9769/Buchman Ethan 201606 [Link].
Definition 3 (Configuration block). A configuration block is
4 Point-to-point reliable channels can be implemented with secure channels a block containing:
in a partially synchronous environment. 6 Receiving information from the DNS service introduced below belongs to
5 They have in memory every block of the blockchain. this Listening requirement.
 1) Information on the deciders of the new configuration7 . D. Reconfiguration
2) The signatures of this new configuration by at least t + 1
We distinguish two cases: (i) adding nodes to and (ii) remov-
deciders of the previous configuration.
ing nodes from a configuration. To handle the general case, we
3) The hash and index of the last configuration and transa-
first add the new nodes, and once these are ready to perform
tion block (indicating the previous configuration and the
consensus, we remove the unneeded ones.
last committed transactions).
When adding nodes, new deciders must have knowledge
Note that the genesis block is a special configuration block of the most up-to-date blockchain (and configuration). To this
without the hash and index of previous blocks. end, each old node sends a copy of the up-to-date blockchain
B. Deciding upon a new configuration to new nodes. A new node waits for having received t + 1
identical blockchains, before taking part to the consensus.
Reconfiguration consists of replacing the current configura- Note that as our model is partially synchronous, we can safely
tion in use by a new configuration. In a community blockchain, launch the next consensus instance without waiting for the new
a reconfiguration must guarantee that the system can keep nodes to be up-to-date.
serving the transaction requests while the set of decider nodes When removing nodes, we have to ensure that the already
is being reconfigured, hence the Definition 4. acknowledged transactions do not get lost. Thus, the removed
Definition 4 (Reconfiguration). A reconfiguration replaces a nodes transfer all the enqueued and not-processed transactions
configuration c by a different (possibly overlapping) configu- to the nodes of the next configuration. To ensure that the
ration c0 such that: removed nodes eventually transfer all of them, they stop
1) all correct nodes of c agree upon c0 , proposed by a node; acknowledging and taking into account arriving transactions
2) c0 verifies a validity predicate (c0 is valid); after the new configuration has been decided. Each removed
3) there is no service interruption; node can thus safely stop when it has no more pending
4) there is no data loss; transaction.
5) data integrity is preserved; E. Catching up with the most up-to-date information
6) the reconfiguration takes a finite amount of time.
As new nodes may join and leave, they need a mechanism
The requirements (1) and (6) are guaranteed by a consensus to retrieve the latest configuration to know where to send their
algorithm. The data integrity (5) is preserved by the commu- transaction and balance requests. In particular, by the time a
nity blockchain. Below we explain how a configuration can new node joins the system, the system may have progressed to
be valid (2) and how the system stays uninterrupted (3) while the k th configuration where the k −1 preceding configurations
data is kept (4). have become faulty. To cope with this issue, every new correct
C. Verifying that a configuration is valid node bootstraps by contacting the DNS service that provides
Configurations of the community blockchain must fulfill the latest configuration. As mentioned previously, this type of
some requirements defined by the application. A trivial ex- assumption is needed by existing blockchains [9], [18].
ample is that they cannot be empty. But specific applications
may also require that the deciders are not all part of the V. P UTTING THE C OMMUNITY TO W ORK
same jurisdiction, etc. Based on application-specific criteria, In this section, we implement a community blockchain,
each node can decide whether a configuration is acceptable. called ComChain, that builds upon the Red Belly Block-
We explain below how we guarantee that the community chain [15]. This blockchain features a leaderless consensus
blockchain only uses valid configurations. algorithm [7] to solve the Blockchain Consensus problem,
Initially, we list the public key, the IP address and the port where nodes cooperate to select a block [8] (see Section V-B).
number of the decider nodes of the initial configuration in the
genesis block. To propose a new configuration c, a decider A. Reliable multicast
node sends c to the other n − 1 decider nodes. Each node In order to exchange information between the nodes of
receiving c proposes 1 if it considers c acceptable, 0 otherwise, a configuration, we define two reliable multicast primitives
to a new consensus instance. Upon agreement, if 1 is decided, based on the classic definition of reliable broadcast, presented
then every correct decider node signs configuration c (with by Bracha [4], [5] and reused in [7]. The reliable broadcast
their private key) and sends c along with their signature to the is a communication primitive among n nodes where at most
requester. t < n3 can be Byzantine [4]. This abstraction provides two
We write that a newly decided configuration c0 is valid and primitives, RB broadcast and RB deliver. With p a node, in
that valid(c0 ) returns true if the configuration c0 has been one instance of the broadcast protocol, this abstraction has the
signed by at least t + 1 nodes of the current configuration following properties:
c8 , and contains the hashes and indexes of the previous • Validity. If p is correct and a correct node RB-delivers a
configuration
7
block and transaction block. message m from p, then p RB-broadcast m.
IP address, port and public key.
8 As t is the maximum number of Byzantine nodes, t + 1 signatures • Unicity. A correct node RB-delivers at most one message
guarantee that at least one signature comes from a correct node. from p (whether p is correct or not).
 • Termination-1. If p is correct and RB-broadcasts a mes- Algorithm 1 Collaborative signature of configurations
sage m, all the correct nodes eventually RB-deliver m function H ANDLE S IGNATURE R EQUESTS
from p. when RB deliver signing request for c from pi do
BinaryConsensus(valid configuration(c), G ET I D(c, pi ))
• Termination-2. If a correct node RB-delivers a message
when BinaryConsensus{id0 } returns 1 do
m from p (possibly Byzantine) then all the correct nodes hc0 , pj i ← G ET I TEMS F ROM I D(id0 )
eventually RB-deliver the same message m from p. c0 ← SIGN(c0 )
Send c0 to pj
As we need to make a distinction between messages con-
when RB deliver signed configuration c00 from pk do
taining proposals for transactions, for configurations or agree- if E QUAL C ONFIGURATIONS(c00 , self .sc) then
ment on the validity of a configuration, we define two multicast M ERGE S IGNATURES(c00 )
primitives, RB broadcast new and RB broadcast old, that
precise the set of nodes it is sent to. consensus instance associated with a particular decider node
id and the configuration it proposes v.
Definition 5. We define four operations RB broadcast new
and RB deliver new (resp. RB broadcast old and Definition 7. BinaryConsensus(v, id) represents the proposal
RB deliver old), being the RB broadcast (respectively of the (binary) value v to the instance of binary consensus
the RB deliver) operation from a node to all nodes of the uniquely identified with id. BinaryConsensus{id0 } represents
new configuration not being part of the old configuration the binary consensus instance having identifier id0 . We say that
(resp. to all nodes of the old configuration). BinaryConsensus{id0 } returns when a value has been decided
for the binary consensus instance of identifier id0 .
B. Blockchain consensus
We also define two methods, G ET I D and G ET I TEMS, to
The blockchain consensus, originally referred to as Validity turn hv, id i (where v is a boolean and id is a node identifier)
Predicate-based Byzantine Consensus, consists for a set of into the identifier id 0 of a binary consensus instance and to
nodes to collaboratively decide upon a new block [7], [8] reverse the operation. These functions are implemented via a
(see Definition 6). This problem is different from the proof-of- dictionary-like structure that maintains the identifiers for the
work Blockchain problem [18], [22] and the classic Byzantine launched binary consensus instances. We use self .sc.c to refer
agreement problem [3], [6], [24]. to the configuration that the node wants other participants to
Definition 6 (Blockchain Consensus). With the assumption sign. A configuration as stored by a node is a tuple:
that every correct process proposes a value to the consensus, • c, the configuration as a set of deciders, initially ∅

each correct process decides on a value while satisfying: • signatures set, an array of signatures indexed by node

• Termination: Every correct process decides after a finite identifiers, initially ⊥ (undefined) at all indices
amount of time. The M ERGE S IGNATURES function groups the signatures
• Agreement: Two correct processes decide on the same present in the incoming signed configuration with these al-
value. ready gathered for the next-to-propose configuration.
• Blockchain validity: The value decided by a correct
process verifies a predefined predicate valid(). D. Deciding upon a new configuration

Crain et al. [7] propose a solution to the blockchain con- To decide on the next configuration, we launch a multivalue
sensus problem where each correct decider proposes a value. consensus algorithm among all nodes. To this end, we use
The deciders then agree on a set of accepted proposals from the partially synchronous DBFT algorithm [7] as a black box,
which is forged the next block. An instance of consensus is with the serialized signed configuration as input and a function
one execution of a consensus algorithm on a set of proposals. checking the configuration has been signed by at least t + 1
nodes of the current configuration as valid predicate.
C. Collaboratively signing a configuration More precisely, the DBFT algorithm returns the value
As described in Section IV-C, before proposing a configu- decided by all correct processes. This value will be input in the
ration, a node has to gather t + 1 signatures of nodes of the functions described in the next section. To decide whether we
current configuration. Therefore, a correct node broadcasts the have to execute the AddNodes function, the RemoveNodes
new configuration for signature by the current configuration. function or both, we simply check the inclusion of one
Upon reception of signature requests from other nodes, it configuration in the other: if the new configuration is included
executes Algorithm 1. For the sake of symmetry, a node broad- in the old configuration then we remove nodes; etc.
casts also the new configuration to sign to itself. As validity is
E. Transition from the current to the new configuration
application dependent (cf. Section IV-C), we consider that each
correct node is equipped with a predicate valid configuration The functions we use above return a configuration proposed
that, given a configuration c, returns true only if c is valid by a node that verifies validity conditions and on which all
according to the current application. correct nodes agree. As previously indicated in Section V-D,
As binary consensus is needed to decide whether a config- after the consensus returns a value, we need to process this
uration is valid, let us introduce two notations for the binary value with the functions previously described in Section IV.
 Binary consensus Multivalued consensus
Algorithm 2 Participation to the consensus when adding nodes Getting signatures Reconfiguration
4
function D ECIDE C ONFIGURATION(c) 2.0
ADD C ONFIGURATION B LOCK (c)

Time in seconds
Time in seconds
3
RB broadcast new blockchain 1.5

RB broadcast old the last block index 1.0

2

Run consensus on the new configuration

when (RB deliver old last index of n0 − t0 nodes) do 0.5
1

Inform the DNS service that transactions should be 0

0.0
sent to the new configuration

10

11
1

8
Number of nodes to add Number of nodes in the initial configuration
(a) Time in seconds to perform recon- (b) Time in seconds to perform reconfig-
Algorithm 3 Participation to the consensus when removing nodes figuration when starting with 4 deciders, uration when adding 1 node, depending on
depending on the number of nodes to add. the number of initial deciders.
function D ECIDE C ONFIGURATION(c)
ADD C ONFIGURATION B LOCK (c) Fig. 2: Evaluation of the reconfiguration when adding nodes.
Inform the DNS service that txs should be sent to the new config;
if self in the nodes to remove then Binary consensus Multivalued consensus
stop acknowledging transactions Getting signatures Reconfiguration
start transmitting the queued txs to the new config 4
4
when the node has no transaction left do

Time in seconds
Time in seconds
shut down 3 3

else
2
perform consensus with the new configuration 2

1
1
1) Adding nodes: For old nodes to add new nodes, they 0
0

10

11

12
use the protocol presented in Algorithm 2.

8
Number of nodes to remove Number of nodes in the initial configuration
The function ADD C ONFIGURATION B LOCK used in Algo- (a) Time in seconds to perform reconfigu- (b) Time in seconds to perform reconfig-
ration when starting with 12 nodes, depend- uration when removing 1 node, depending
rithm 2 adds a new configuration block to the blockchain. As ing on the number of nodes to remove. on the number of deciders.
precised in Section IV-D, we do not need to wait for the new Fig. 3: Evaluation of the reconfiguration when removing nodes.
nodes to be ready.
Experimental settings. We launched experiments on a dis-
2) Removing nodes: We remove nodes by using the pro-
tributed set of physical machines using the Emulab platform10 .
tocol described in Algorithm 3 where self depicts the node
We ran the experiments on up to 12 machines, each with two
running the function.
64-bit Xeon processors running a total 8 cores at 2.4 GHz
3) Adding and removing nodes: Replacing an old config- with 2 GB of memory and Ubuntu 14.04. We launched all
uration by a new configuration that is independent can be nodes at the beginning of an experiment, one virtual machine
achieved by both adding and removing nodes from the old per physical machine to make sure all communications went
configuration. With the old configuration oc, and the new through physical links, with the DNS service running on the
configuration c, we use the first case above to switch from same physical machine as the first of the nodes.
oc to oc ∪ c, then the second to switch from oc ∪ c to c.
Time to add new nodes. As presented in Figure 2, we focused
F. Blocks on the impact of the size of the initial or the final configuration
on the time needed to perform one reconfiguration.
In this whole section, we have handled only configuration
blocks, assuming that for a given consensus instance, either We observe in Figure 2a that increasing the number of nodes
only configuration blocks are proposed, or only transaction of the final configuration does not impacts the time needed to
blocks are proposed. This is also an easy way to dissociate perform the (binary and multivalue) consensus part. For the
the processing of the configurations and transactions. reconfiguration time, we observe a significant increase, due to
The assumption we made is unrealistic. For an implemen- the nodes that need to update themselves. The lack of a steady
tation, we merge the definitions of configuration block and trend can be explained by the 32 ratio of correct nodes over
transaction block: every block contains both a configuration total nodes: we evolve at the limit of the threshold, thus the
(possibly empty or null) and a batch of transactions (possibly number of nodes we have to wait for does not evolve linearly.
empty). To validate a general block, we split it in the two In Figure 2b, we depict the impact of the initial number of
aforementioned types of blocks, validate each one separately, deciders on the time needed to perform reconfiguration. We
and say that a general block is valid if both the transaction observe that the reconfiguration time increases only sightly.
block and the configuration block we built from are valid.
Time to remove existing nodes. We carried out similar
experiments for the nodes removal, whose results are presented
VI. E VALUATION
in Figure 3. We first observe on Figure 3a that the number of
In this section, we deploy ComChain on a distributed set of nodes we remove does not impact the reconfiguration time.
machines to measure the latency and throughput of reconfig- Then, as for adding nodes, the time spent for reaching an
uration between and during UTXO9 transaction invocations. 10 “Emulab
is a network testbed, giving researchers a wide range of envi-
9 Unspent Transaction Outputs (UTXOs) is the model of transactions used ronments in which to develop, debug, and evaluate their systems.” We used the
by Bitcoin [18]. datacenter installation located at the University of Utah (see [Link]).
 Transaction blocks Multivalued consensus set of physical machines confirm the feasibility and non-
Binary consensus Reconfiguration
Getting signatures Transaction blocks
disruption of this approach. As future work, we plan to
40 measure the information transfer time from old nodes to new
60
nodes depending on the blockchain size.

Time in seconds
Time in seconds

50
30
40

20 30
Acknowledgments
20 This research is in part supported under Australian Research
10
10

0
Council’s Discovery Projects funding scheme (project number
180104030) entitled “Taipan: A Blockchain with Democratic

9
0

10

11
0

8
Number of nodes to add Number of nodes in the initial configuration
(a) Time in seconds to perform reconfig- (b) Time in seconds to perform reconfig- Consensus and Validated Contracts”.
uration and process 20 transaction blocks uration and process 20 transaction blocks
when starting with 4 nodes, depending on when adding 1 node, depending on the R EFERENCES
the number of added nodes. initial number of deciders.
[1] Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, Alexander
Fig. 4: Evaluation of the reconfiguration and transactions processing Spiegelman: Solida: A Blockchain Protocol Based on Reconfigurable
when adding nodes. Byzantine Consensus. OPODIS 2017: 1-19.
[2] E. Alchieri, F. L. Dotti, O. M. Mendizabal, F. Pedone. Reconfiguring
Transaction blocks Multivalued consensus Parallel State Machine Replication. SRDS 2017: 104-113.
Binary consensus Reconfiguration [3] A. Bessani, J. Sousa, and E. Alchieri, State machine replication for the
Getting signatures Transaction blocks
masses with BFT-SMaRt, DSN, 2014.
80 80
[4] G. Bracha, Asynchronous Byzantine agreement protocols. Information
Time in seconds

& Computation, 75(2):130-143 (1987).

Time in seconds

60 60 [5] G. Bracha and S. Toueg, Asynchronous consensus and broadcast proto-

40 40
cols, JACM, 32(4):824-840 (1985).
[6] C. Cachin. Architecture of the Hyperledger Blockchain Fabric. Work-
20 20 shop on Distributed Cryptocurrencies and Consensus Ledgers. July 2016.
0 0
[7] T. Crain, V. Gramoli, M. Larrea and M. Raynal,
0

(Leader/Randomization/Signature)-free Byzantine Consensus for

10

11

12

Number of nodes to remove

Number of nodes in the initial configuration
(a) Time in seconds to make a decision Consortium Blockchains, [Link]
and to perform reconfiguration and process (b) Time in seconds to perform reconfig- [8] T. Crain, V. Gramoli, M. Larrea and M. Raynal, Blockchain Consensus,
20 transaction blocks when starting with 12 uration and process 20 transaction blocks ALGOTEL, 2017.
nodes, depending on the number of nodes when removing 1 node, depending on the [9] P. Daian, R. Pass and E. Shi, Snow White: Robustly reconfigurable con-
to remove. initial number of nodes.
sensus and applications to provably secure proofs of stake, Cryptology
Fig. 5: Evaluation of the reconfiguration and transactions processing ePrint Archive, Report 2016/919, 2017.
when removing nodes. [10] I. Eyal, A.E. Gencer, E.G. Sirer, and R. van Renesse. Bitcoin-NG: A
Scalable Blockchain Protocol. NSDI 2016.
agreement increases with the initial number of deciders11 , but [11] M.J. Fischer, N.A. Lynch, and M.S. Paterson, Impossibility of distributed
the actual reconfiguration period increases only slightly and consensus with one faulty process, JACM, 32(2):374-382, 1985.
[12] Y. Gilad, R. Hemo, S. Micali, G. Vlachos and N. Zeldovich, Algorand:
irregularly due to our ratio. Scaling Byzantine Agreements for Cryptocurrencies, Cryptology ePrint
Though it slightly slows down the blockchain, the recon- Archive, Report 2017/454, 2017.
figuration itself takes less time than an instance of consensus. [13] S. Gilbert, N.A. Lynch, A.A. Shvartsman: Rambo: a robust, recon-
figurable atomic memory service for dynamic networks. Distributed
However, our implementation does not currently transfer the Computing 23(4):225-272, 2010.
blockchain from one configuration to the next one. [14] V. Gramoli, L. Bass, A. Fekete and D. Sun, Rollup: Non-Disruptive
Mixing reconfiguration and transaction requests. On Fig- Rolling Upgrade with Fast Consensus-Based Dynamic Reconfigurations,
IEEE TPDS, 27(9):2711-2724, 2016.
ures 4 and 5, we display the time needed to process 10 [15] V. Gramoli. The Red Belly Blockchain. Invited talk. MIT, MA, USA.
transaction blocks (in blue), one reconfiguration, then 10 other June 2017. [Link]
transaction blocks (in brown) using the new configuration. As [16] P. Hunt, M. Konar, F.P. Junqueira, B. Reed: ZooKeeper: Wait-free
Coordination for Internet-scale Systems. ATC, 2010.
expected, adding nodes increases the time to process the same [17] L. Lamport, D. Malkhi and L. Zhou, Reconguring a State Machine.
number of blocks. SIGACT News 41(1): 63-73 (2010)
Though reducing the number of nodes should speed up the [18] Nakamoto S., Bitcoin: a peer-to-peer electronic cash system.
[Link] (2008)
second sequence of transaction blocks, we see on Figure 5a [19] C. Natoli and V. Gramoli, The balance attack against proof-of-work
that the time needed to process these increases when we start blockchains: The R3 testbed as an example, DSN, 2017.
removing nodes. It is most likely due to the slowest node [20] R. Pass and E. Shi, Hybrid Consensus: Efficient Consensus in the
Permissionless Model, Cryptology ePrint Archive, Report 2016/917,
trying to catch up with the fastest ones, as each node has been 2016. [Link]
unaware of the others’ messages during its reconfiguration. [21] R. Rodrigues, B. Liskov, K. Chen, M. Liskov and D. Schultz, Automatic
This behavior is also present on Figure 5b. reconfiguration for large-scale reliable storage systems, IEEE TDSC
9.2:145--158, 2010.
VII. C ONCLUSION [22] G. Wood, Ethereum: A secure decentralized generalized transaction
ledger. White paper (2015)
In this paper we proposed community blockchain, a [23] J. Yu, D. Kozhaya, J. Decouchant and P. Esteves-Verissimo, RepuCoin:
paradigm to change nodes on-the-fly with a consensus-based Your reputation is your power, unpublished draft.
[24] Jepsen, Tendermint 0.10.2. White paper, Sept. 2017. [Link]
reconfiguration without disrupting the transaction service. Our analyses
ComChain implementation and its experiments on a distributed [25] [Link]
11 The latency of the underlying Red Belly Blockchain tends to increase [26] [Link]
with the number of nodes [15]. adding-a-validator

View publication stats