by Arthur Melissen (Storro B.V.)
Current blockchain technology as used by Bitcoin [1] and others uses a consensus model to determine the head of the chain and lets divergent branches starve, causing information loss. Information loss can be problematic for alternative blockchains in which connectivity could be reduced for longer periods of time and a consensus model is infeasible.
In order to support sparsely connected clusters of machines working on independent branches of a blockchain, divergent branches must be able to be merged with each other by a merging algorithm that carries the consensus of all parties involved.
We discuss a set of requirements that a blockchain merging algorithm must achieve, and show how such an algorithm can be used to facilitate parallel disconnected operations in an alternative blockchain.
Bitcoin’s blockchain model allows an unknown number of participants to use its chain without a central authority. Because any client may append data at any time, branching the chain is both implicit and inevitable. In order to avoid merging branches or dealing with conflicting transactions, Bitcoin lets its users choose a main branch based on an estimated amount of work done on competing branches. Because Bitcoin is a system that registers financial transactions, it has a great need for consistency by distributed consensus in a relatively short amount of time. The process of distributed branch selection is effective in achieving this, but artificially limits the network to a single branch and thereby introduces a scaling bottleneck.
Alternative blockchains may be designed to perform other tasks, such as publicly verifiable calculations, snapshotting filesystems, anonymous and auditable voting, distributed notary systems to provide proof-of-possession of documents, and other distributed and anonymous services.
Many such alternative blockchains may not have a need for the same strong demands on consistency that Bitcoin does, and may require performance that cannot be achieved by distributing a single chain across all nodes in the entire network. For instance, a distributed filesystem might register its updates in different branches for individual servers and only periodically synchronise the filesystem by merging each server's branch with the other branches using a branch merging algorithm.
At Storro, we design and use blockchain models where it is not achievable to maintain a hierarchy of branches or even an ordering between different branches. It might be the case that a client working on one branch is not even aware of all other branches. In such an environment it is necessary for the merging algorithm to function between any pair of branches, independent of their lineage. Merging might be done opportunistically and asynchronously between intermittently connected clients and may fail due to network outages or power failures.
In effect, this means that the merging operations between semi-connected and unreliable clients is a chaotic process, but must still provide an eventually consistent state between all clients involved.
The simplest merging scenario is that of a branched blockchain consisting of only two branches. It should be clear that merging two different branches A and B should provide the same merged result state on both clients. This means that the merging operation must be deterministic and commutative. Since the algorithm is deterministic, it is an intuitive notion that the merging algorithm should most likely be automated, and not require any human intervention.
For blockchain networks of more than two branches to reach consensus, we must ensure that the result of the merging operation between branches A and B merged with C yields the same result as the merge between branch A and the result of a merge between B and C. This requirement equates to the traditional definition of an associative operation.
Just like with Bitcoin’s double-spending attacks, inconsistencies may occur when one naively attempts to combine the results of different branches by adding their individual states together. However, unlike Bitcoin, which can select a main branch and simply ignore any others, a merging algorithm needs to provide a consistent solution for all conflicts that may arise when merging branches. Because the resolution of such conflicts will be a part of the result of the merging operation, the conflict resolver algorithm has the same requirements as its parent merging algorithm: It must be deterministic, commutative and associative. How this is expressed in a specific blockchain model is left to the designer. An online voting system for example may decide that for conflicting votes from the same voter id only the most recently timestamped is valid, a hash function is applied to select a winner deterministically, or conflicting votes are discarded altogether.
Given these requirements, what would a simple example merging algorithm look like for an alternative blockchain? In the case of a distributed filesystem, we can specify the result R of a merging operation between two branches A and B as follows:
Any files which are present in both A and B and contain the same content will be present in R.
Any newly created files which are present in only one branch will be present in R. Any files which are deleted in one or more branches and are not changed in any other branch are removed from R.
Conflict resolution: If a file is created or changed in both branches, the file with the larger content will be present in R. If the content size is equal, the content is compared and the higher value is chosen as the content in R.
This algorithm is deterministic, and by selecting the largest file in either version it is also commutative and associative. Applying this algorithm to a set of clients which share a blockchain representing filesystem snapshots should eventually provide a consistent state across all clients.
In contract, a merging algorithm that fails to meet any of these criteria, for instance by not being deterministic (by performing a random action upon merging), or not being commutative (by always preferring the local changes over remote ones), or not being associative (by not using methods that transitively lead to the same result over larger sets of branches) will relinquish its promise in providing consensus in the network after any amount of merging operations.
Any blockchain that should lead to eventual deterministic consensus among all nodes will need a merging algorithm that is deterministic, commutative and associative. At Storro we use these findings to design many of our merging algorithms with these properties in order to employ them in our proprietary decentralised blockchain models.
Team at Storro.
Reference:
[1] S. Nakamoto, “Bitcoin: A Peer-to-Peer Electronic Cash System”, http://www.Bitcoin.org, 2008
Please contact:
Arthur Melissen, Michel Eppink
Storro B.V., The Netherlands
