Designing an efficient and secure consensus algorithm

consensus

#1

Dealing with large amounts of data efficiently is only one part of the problem that must be solved for true mainstream use of Distributed Ledger Technology (DLT) - the other part of this is making sure that no conflicting data can exist in the system without it being quickly flagged and removed. This system of comparing, ordering and agreeing on data conflicts is broadly referred to as “consensus”.

Consensus systems can be loosely grouped into permissioned and permissionless consensus. Permissioned consensus is where all parties that are involved in deciding between conflicting entries are identifiable (e.g. a specific business) and are given express permission to amend and reject information in the system. These systems have been around for a long time to manage distributed databases and are still used in a number of new permissioned systems such as Hyperledger and R3’s Corda, and are built on permissioned consensus systems from the 1970’s such as PBFD and Raft.

Their flaw is that the consensus is not secure, it simply relies on securing the process of selecting the parties who are allowed to manage the data, rather than making the method of reaching consensus itself secure and fault tolerant.

Permissionless consensus was the innovation that created Bitcoin in 2008/2009. Instead of securing the selection of the parties that would be involved in making the consensus, it worked out a way of making the process of consensus secure; meaning no central authority was needed to select and vet network participants. Instead computer power was used as a way of allowing everyone to work out what the majority of the network believed to be the correct version of the truth, organized it into blocks of transactions and then chaining those together with each new block referring to the last, forming the blockchain.

The use of computer power to secure this process is called Proof of Work (PoW), and is both massively inefficient, and only as secure as half the total amount of computing power being used to decide what data to accept and what data to reject. This can be effective for very large networks where there are clear crypto economic incentives to provide ever increasing amounts of computing power, such as Bitcoin, but do not function well for small or private networks where getting more than 50% of the computing power of the network is trivial.

It has however, one very important feature - it does not rely on the security of the individual network members, only the security of the network as a whole. This feature makes the entire system much more resilient and secure than a permissioned system, if deployed in the correct way.

Radix also solves these problems by creating a permissionless consensus system that can be used securely in both small and large networks, but secured by a property that cannot be trivially bought or faked within Radix: the passage of logical time. In addition to this, unlike other DLT systems, it does not apply consensus to every event, only to those that conflict. This allows the entire system to be incredibly efficient, even at massive scale.

The passage of logical time relies on a concept called logical clocks - It uses these clocks for generating a partial ordering of events in a distributed system to detect and prevent causality violations based on Leslie Lamport’s logical clock theory. In very simple terms, a logical clock is a counter. Each node on the Radix network (a node is a computer that maintains some or all of the state data the network contains) has its own logical clock that it maintains. The only rule it must follow that it must strictly count upwards only, and may only ever increment by 1 each time.

In Radix, this counter is triggered for a node when it sees a valid event it has never seen before. The node must simply check its own database, then increment its logical clock, stamp the event with the new timestamp and ID and then gossip it to the network. Periodically it must make commitments to make sure it cannot lie about the order of historical events.

Due to the data structure, this simple and reliable consensus mechanism now only gets triggered if any node disagrees about the correct ordering of related events. This passive consensus mechanism is both very reliable, event at large numbers of dishonest or faulty nodes, and incredibly power efficient as no extra energy is expended apart from to resolve conflicts.