Convergent Consensus Method for Distributed Ledger Transaction Processing

Abstract

A computer system and computer-implemented method for efficiently achieving convergent consensus in a distributed network of nodes that maintains a decentralised database or ledger with immutable data storage. Via transactions, client nodes request updates to the ledger that are verified by a set of peer nodes to achieve a new agreed consensus across the whole network. The process involves a Belief Merge Function and a State Transition Function that rapidly converge to consensus. The convergence method uses peers' “proof of stake” to avoid the high cost of “proof of work” alternatives that have unsustainable energy requirements. Embodiments of the system have a capacity for tens of thousands of transactions per second.

1 . A system for achieving efficient Consensus comprising:
 one or more nodes of various types arranged as arbitrary communication and functional participants in a Network, wherein at least a first node type is termed a Peer,   means for the production of Beliefs by Peers such that each Belief contains data used for forming Consensus;   a Belief Merge Function which combines one or more Beliefs;   wherein the Peers are arranged to maintain the Consensus of the network according to a Consensus Protocol including the application of the Belief Merge Function to Beliefs;   wherein the Belief Merge Function is defined such that the Network exhibits the property of Convergence to a single Consensus.   
     
     
         2 . The system according to  claim 1 , wherein at least a second node type is termed a Client; and
 wherein the Clients are arranged to submit new Transactions that may affect the Consensus and query information resulting from the Consensus of the Network.   
     
     
         3 . The system according to  claim 1 , wherein the Belief Merge Function is defined using a computation that is idempotent, associative and commutative, such that the system is able to operate as a Conflict-free Replicated Data Type. 
     
     
         4 . The system according to  claim 1 , further comprising:
 a specific type of information units, known as Blocks;   full or partial Orderings of the specific type information units, Blocks, comprising Values and Cells, included as a constituent part of a Belief;   a State Transition Function capable of computing an updated State given some Ordering;   one or more Initial States;   wherein a Consensus State may be computed by repeated application of the State Transition Function to an Initial State and information unit(s) that may be included in the Ordering.   
     
     
         5 . The system according to  claim 4 , further comprising:
 collections of zero or more information units known as Transactions which are included as constituent parts of each Block;   optional additional information supplied by the Peer, such as a timestamp or digital signatures;   wherein the Blocks and their constituent Transactions and any additional information are arranged to be included as part of the Ordering.   
     
     
         6 . The system according to  claim 4 ,
 wherein the information units in an Ordering are defined not to contain references to one or more previous information units, such that it is possible to re-order the Blocks in the Consensus process.   
     
     
         7 . The system according to  claim 6 , further comprising:
 means for Computation of Consensus Orderings;   wherein the means for Computation of Consensus Ordering computes a Consensus Ordering as part of the Belief Merge Function.   
     
     
         8 . The system according to  claim 7 , further comprising:
 means for assigning a Stake to Peers;   a procedure for Stake Weighted Ordering Merge included as part of the Computation of Consensus Ordering;   wherein the Stake Weighted Ordering Merge is utilized to resolve conflicts between Orderings proposed by different Peers.   
     
     
         9 . The system according to  claim 7  further comprising:
 means for Common Prefix Computation; 
 wherein the computation of a Common Prefix between Orderings is utilized to reduce the computational costs for Consensus. 
 
     
     
         10 . The system according to  claim 1 , further comprising:
 means for Novelty detection;   wherein nodes observing Novelty may communicate Novelty to other nodes;   wherein nodes may optionally omit communication of information that is not Novelty, in order to save network resources and processing costs.   
     
     
         11 . The system according to  claim 1  further comprising:
 means for representing information Values, which are represented as one or more Cells; 
 means for producing an Encoding for a Cell, preferably in a form suitable for storage or Network communication; 
 means for Smart References enabling a reference to a Cell to be included within the information and/or Encoding of another Cell; 
 means for embedding an Encoding within another Encoding thereby enabling any Value to be completely represented as a graph of Cells connected by Smart References. 
 
     
     
         12 . The system according to  claim 11  further comprising:
 means for producing a Value ID for a Cell, such as a cryptographic hash function applied to the Encoding; 
 wherein the Value ID can be used as a unique reference for the information unit. 
 
     
     
         13 . The system according to  claim 1 , further comprising:
 a Convergent Storage for information values;   wherein only the information units currently in active use are required to be in the working memory of a node, and other information units can be persisted to permanent storage and/or deleted if not required for further processing, i.e., garbage collected;   wherein the addition of new information to Storage has the Convergence property, such that data inconsistencies may be avoided.   
     
     
         14 . The system according to  claim 1  further comprising:
 means for computing the Memory Size of a Cell or other information Value; 
 means for Memory Accounting; 
 wherein the Memory Accounting is used to assign Incentives to participants on the network, such as to conserve memory, storage and/or communication bandwidth. 
 
     
     
         15 . The system according to  claim 14  further comprising:
 means of caching computed Memory Sizes for each Cell or information unit either in working memory and/or Storage; 
 wherein cached Memory Sizes are used to reduce the computational complexity of computing the memory size for large data structures, such as only needing to compute the Memory Size for Novelty. 
 
     
     
         16 . The system according to  claim 4  further comprising:
 means for Trusted Code Execution arranged to be part of the State Transition Function; 
 wherein the Trusted Code Execution can be utilized to implement Smart Contracts or other programmable functionality that may affect the Consensus State. 
 
     
     
         17 . The system according to  claim 13  further comprising:
 one or more Monotonic Headers, which associate header information with information Values and/or Cells; 
 wherein the Monotonic Header also provides the property of Convergence, such that is can be relied upon for caching, performance optimization and tagging the status of Cells. 
 
     
     
         18 . A computer-implemented method for achieving efficient Consensus comprising:
 arranging one or more nodes of various types as arbitrary communication and functional participants in a Network, wherein at least a first node type is termed a Peer,   generating Beliefs by Peers such that each Belief contains data used for forming Consensus;   combining one or more Beliefs into a Belief Merge Function;   wherein the Peers are arranged to maintain the Consensus of the network according to a Consensus Protocol including the application of the Belief Merge Function to Beliefs;   wherein the Belief Merge Function is defined such that the Network exhibits the property of Convergence to a single Consensus.   
     
     
         19 . The method according to  claim 18 , wherein at least a second node type is termed a Client; and
 arranging the Clients to submit new Transactions that may affect the Consensus and query information resulting from the Consensus of the Network.   
     
     
         20 . The method according to  claim 18 , wherein the Belief Merge Function is defined using a computation that is idempotent, associative and commutative, such that the system is able to operate as a Conflict-free Replicated Data Type. 
     
     
         21 . The method according to  claim 18 , further comprising:
 a specific type of information units, known as Blocks;   full or partial Orderings of the specific type information units, Blocks, comprising Values and Cells, included as a constituent part of a Belief;   a State Transition Function capable of computing an updated State given some Ordering;   one or more Initial States;   wherein a Consensus State may be computed by repeated application of the State Transition Function to an Initial State and information unit(s) that may be included in the Ordering.   
     
     
         22 . The method according to  claim 21 , further comprising:
 collections of zero or more information units known as Transactions which are included as constituent parts of each Block;   optional additional information supplied by the Peer, such as a timestamp or digital signatures;   wherein the Blocks and their constituent Transactions and any additional information are arranged to be included as part of the Ordering.   
     
     
         23 . The method according to  claim 21 ,
 wherein the information units in an Ordering are defined not to contain references to one or more previous information units, such that it is possible to re-order the Blocks in the Consensus process.   
     
     
         24 . The method according to  claim 23 , further comprising:
 computing Consensus Orderings;   wherein the Consensus Ordering is computed as part of the Belief Merge Function.   
     
     
         25 . The method according to  claim 24 , further comprising:
 assigning a Stake to Peers;   a procedure for Stake Weighted Ordering Merge included as part of the Computation of Consensus Ordering;   wherein the Stake Weighted Ordering Merge is utilized to resolve conflicts between Orderings proposed by different Peers.   
     
     
         26 . The method according to  claim 24 , further comprising:
 computing Common Prefix;   wherein the computation of a Common Prefix between Orderings is utilized to reduce the computational costs for Consensus.   
     
     
         27 . The method according to  claim 18 , further comprising:
 detecting Novelty;   wherein nodes observing Novelty may communicate Novelty to other nodes;   wherein nodes may optionally omit communication of information that is not Novelty, in order to save network resources and processing costs.   
     
     
         28 . The method according to  claim 18  further comprising:
 representing information Values, which are represented as one or more Cells; 
 producing an Encoding for a Cell, preferably in a form suitable for storage or Network communication; 
 enabling Smart References a reference to a Cell to be included within the information and/or Encoding of another Cell; 
 embedding an Encoding within another Encoding thereby enabling any Value to be completely represented as a graph of Cells connected by Smart References. 
 
     
     
         29 . The method according to  claim 28  further comprising:
 producing a Value ID for a Cell, such as a cryptographic hash function applied to the Encoding; 
 wherein the Value ID can be used as a unique reference for the information unit. 
 
     
     
         30 . The method according to  claim 28 , further comprising:
 a Convergent Storage for information values;   wherein only the information units currently in active use are required to be in the working memory of a node, and other information units can be persisted to permanent storage and/or deleted if not required for further processing, i.e., garbage collected;   wherein the addition of new information to Storage has the Convergence property, such that data inconsistencies may be avoided.   
     
     
         31 . The method according to  claim 18 , further comprising:
 computing the Memory Size of a Cell or other information Value;   accounting Memory;   wherein the Memory Accounting is used to assign Incentives to participants on the network, such as to conserve memory, storage and/or communication bandwidth.   
     
     
         32 . The method according to  claim 31 , further comprising:
 caching computed Memory Sizes for each Cell or information unit either in working memory and/or Storage;   wherein cached Memory Sizes are used to reduce the computational complexity of computing the memory size for large data structures, such as only needing to compute the Memory Size for Novelty.   
     
     
         33 . The method according to  claim 32 , further comprising:
 arranging Trusted Code Execution to be part of the State Transition Function;   wherein the Trusted Code Execution can be utilized to implement Smart Contracts or other programmable functionality that may affect the Consensus State.   
     
     
         34 . The method according to  claim 30 , further comprising:
 one or more Monotonic Headers, which associate header information with information Values and/or Cells;   wherein the Monotonic Header also provides the property of Convergence, such that is can be relied upon for caching, performance optimization and tagging the status of Cells.