Systems and methods for establishing consensus in distributed communications
Inventors
Zhai, Xinlei • Tang, Qiang • Lu, Zhenliang • Xu, Jing • Zhang, Zhenfeng • Guo, Bingyong
Assignees
Institute Of Software Chinese Academey Of Sciences • Institute of Software of CAS • Beijing Wodong Tianjun Information Technology Co Ltd • New Jersey Institute of Technology
Publication Number
US-11973744-B2
Publication Date
2024-04-30
Expiration Date
2040-05-12
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Abstract
Described in detail herein is a system for determining the validity of a transaction in a distributed network environment. The system includes a plurality of peer servers. The system elects a set of peer leaders from the plurality of peer servers. The set of peer leaders broadcast a first set of indices associated with a first subset of transactions, received from the plurality of peer servers, to one or more of the plurality of peer servers. The set of elected peer leaders execute a first instance of a binary agreement protocol based at least in part on a second subset of indices associated with a second subset of the transactions. The set of elected peer leaders output a consensus vector comprising one or more of the transactions.
Core Innovation
Embodiments of the present disclosure describe an efficient, scalable, and fast asynchronous Byzantine Fault Tolerant (BFT) protocol for determining the validity of transactions in a distributed network environment. The system includes a plurality of peer servers, with a subset elected as peer leaders based on an election protocol. These peer leaders broadcast a first set of indices associated with a subset of transactions to one or more other peers and execute a binary agreement protocol based on another subset of indices corresponding to transactions.
The consensus protocol operates in several stages: peer leaders are elected using a committee election protocol, transactions are broadcast reliably to the elected leaders, the leaders broadcast sets of indices related to the transactions received, and then execute a binary agreement protocol to achieve consensus. The final output is a consensus vector comprising one or more transactions agreed upon by the system. The election protocol and consensus process are specifically designed to maintain efficiency and scalability even as the network size grows.
The problem addressed by this innovation is the inefficiency and poor scalability of many conventional asynchronous BFT protocols, particularly in wide-area networks (WANs) spanning diverse and potentially unreliable environments. Prior protocols like HoneyBadgerBFT have high message and communication complexity that scale poorly as the number of peers increases, leading to performance degradation. This invention introduces a protocol with message and computational complexity up to O(N2), round complexity of O(1) per bit, and improved scalability for larger numbers of peers.
Claims Coverage
The patent contains three independent claims, each outlining major inventive features related to systems, methods, and computer-readable media for determining transaction validity and establishing consensus in distributed network environments.
System for distributed transaction validity with leader election, index propagation, and binary agreement
A system comprising: - A plurality of peer servers, each with processors and memory executing computer-executable instructions; - Election of at least one peer leader from the peers based on an election protocol that forms a committee set with at least one correct node, and ensures transactions from correct peers reach their destination before protocol termination; - Broadcasting of a first set of indices associated with received transactions to one or more peer servers; - Execution of a binary agreement protocol instance based on a second subset of transaction indices; - Outputting of a consensus vector containing one or more transactions.
Method for transaction validity via leader election, index broadcasting, and binary agreement
A method comprising: 1. Electing at least one peer leader from peer servers using an election protocol with committee output and protocol termination guarantees for transactions from correct peers. 2. Broadcasting a first set of indices for a subset of received transactions to one or more peer servers. 3. Executing a first instance of a binary agreement protocol based on a second subset of transaction indices. 4. Outputting a consensus vector comprising one or more transactions.
Non-transitory computer-readable medium with instructions for leader election, index broadcast, binary agreement, and consensus output
A non-transitory computer-readable medium storing instructions which, when executed by at least one processor, cause: - Election of at least one peer leader from a plurality of peer servers through an election protocol as previously defined; - Broadcasting of indices associated with a subset of received transactions to peer servers; - Execution of a binary agreement protocol instance using another subset of transaction indices; - Outputting of a consensus vector comprising one or more transactions.
In summary, the independent claims center on a protocol for distributed transaction validation that involves election of peer leaders, broadcasting indices reflecting subsets of transactions, execution of a binary agreement protocol, and the output of a consensus vector. This schema is presented as a system, a method, and a computer-readable medium.
Stated Advantages
The protocol achieves improved efficiency, scalability, and speed in asynchronous BFT consensus, specifically lowering computational and message complexity to O(N2) and round complexity to O(1) per bit, supporting more peers in a WAN.
The system enables better throughput and lower latency than conventional asynchronous BFT protocols, even as the number of participating peers increases.
The deterministic nature of the protocol's round complexity ensures scalability without probabilistic delays as network size grows.
Experimental results demonstrate substantial practical advantage in throughput and latency compared to prior consensus protocols, especially as peer count and transaction batch size increase.
Documented Applications
Achieving robust and efficient consensus for validating transactions in distributed wide-area network (WAN) environments, including but not limited to blockchain and open Internet scenarios with unreliable or adversarial network conditions.
Interested in licensing this patent?