Resilient Consensus in Sharded Ring Topology
"Learn about RingBFT, a resilient consensus protocol over a sharded ring topology, enhancing fault tolerance, throughput, and low latency for cross-shard transactions. The system model and cross-shard consensus algorithm are detailed, ensuring authenticated communication and deterministic transactions."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
RingBFT: Resilient Consensus over Sharded Ring Topology Sajjad Rahnama, Suyash Gupta, Rohan Sogani, Dhruv Krishnan, Mohammad Sadoghi
Problem Goal Fault tolerance, high throughput, low latency Inexpensive consensus of single-shard transactions Flexibility of employing different existing consensus protocols. Deadlock-free two ring consensus Cheap communication between shards BFT is efficient primarily for single shard transactions, however cross shard transactions are common. In order to accomplish, requires shards to adhere to ring order, follow the principle of process, forward, and re-transmit , and ensure communication between shards is linear.
System Model Fault Tolerant Requirement: Byzantine nodes are less than of total replicas per shard Cross-shard Transactions: A simple CST can have each shard individually run consensus, while more complex CSTs include dependencies. Deterministic Transactions: The data-items for which the transaction will read/write are known prior to the start of consensus. Ring Order: Each shard has a position in a ring topology which determines the flow of a CST Authenticated Communication: Intra-shard transactions use message authentication codes, while CSTs use digital signatures.
Cross Shard Transactions Follows the principle of process, forward, and re- transmit For each CST, the shard with the lowest identifier in ring order is selected as the initiator shard which starts consensus on the client transaction. Consensus guaranteed in at most two rotations across the ring.
Cross-Shard Consensus Algorithm 1. Client Request a. Client sends transaction to the first shard in ring order. b. Client specifies all included shards as well as read-write sets Client Request Reception a. Shard checks that message is well formed, and whether it is first in ring order amongst involved shards. b. If both are true, then adds transaction to sequence, calculates digest, and broadcasts preprepare message. Pre-prepare Phase a. If well formed, and the replica has not agreed to support any other request, broadcasts prepare 4. Prepare Phase a. When nf prepare messages are received, broadcasts commit message Commit and Data Locking a. After nf commit messages are received, locks all read-write sets that transaction T needs to access. Forward to Next Shard Execute 5. 2. 6. 7. Prepare and Commit messages can be processed/broadcasted out of order, but locks data in transactional sequence order 3.
Uncivil Executions Several protocols are used to guarantee liveness during periods of synchrony: checkpoints, retransmission, and viewchange. 1. 2. 3. Client Behavior and Attacks Faulty Primary and/or Unreliable network Malicious Primary Three (3) timers are used for detection: local, transmit, and remote. Cross-Shard Attacks 1. 2. No Communication Partial Communication
Design and Implementation ResilientDB provides the network layer, and uses Nanomsg-NG to communicate messages through TCP/IP. Each replica is associated with a parallel pipelined architecture, as seen on right. To record transactions, a singly linked-list is used as an immutable ledger-blockchain
Conclusions RingBFT allows for more efficient cross-shard transactions, resulting in a much greater throughput and greater scalability. It does this by keeping consensus deadlock-free, requiring each shard to participate in at most two (2) rotations, and keeping to a specific ring order.
