Introducing Vryx: Fortifying Decoupled State Machine Replication

[patrick-ogrady]

Original Post: https://x.com/_patrickogrady/status/1750947428130562176

Over the last few years, multiple teams have produced experimental results showing that decoupling transaction replication, sequencing, and execution can significantly increase blockchain throughput [Flow: Separating Consensus and Compute – Block Formation and Execution][Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus][Bullshark: DAG BFT Protocols Made Practical][Shoal: Improving DAG-BFT Latency And Robustness][Sui Lutris: A Blockchain Combining Broadcast and Consensus][BBCA-CHAIN: One-Message, Low Latency BFT Consensus on a DAG][Mir-BFT: High-Throughput Robust BFT for Decentralized Networks][Mysticeti: Low-Latency DAG Consensus with Fast Commit Path][Aleph: Efficient Atomic Broadcast in Asynchronous Networks with Byzantine Nodes]. Unlike "traditional" blockchains (like Bitcoin) where syntactically and semantically valid transactions are sequenced, executed, and replicated simultaneously in each block, these decoupled constructions are able to better pipeline State Machine Replication (SMR) by disseminating, ordering, and verifying transactions independently.

This newly rediscovered approach of "decoupling" State Machine Replication (DSMR), previously detailed by [Separating agreement from execution for byzantine fault tolerant services] and [BASE: Using Abstraction to Improve Fault Tolerance] in the early 2000s, is not without tradeoffs. As a consequence of performing replication prior to sequencing and execution, it is no longer possible to enforce semantic verification of replicated transactions. Let us refer to the number of Replicated Transactions Per Second (whether or not fee-paying/executable) as rTPS, the number of Fee-Paying Transactions Per Second as fTPS, and the number of Invalid Transactions Per Second as iTPS (rTPS - fTPS). This means that the fTPS of DSMR constructions can be far less than rTPS, causing participants to waste valuable resources replicating and verifying invalid transactions (iTPS = rTPS - fTPS). Adversarial issuers (users) employing a mix of cost-effective tactics on a realistic DSMR model can exploit this tradeoff to reduce fTPS to less than 1% of rTPS.

Vryx, a fortified DSMR construction that will be employed by the Avalanche HyperSDK and eventually other Avalanche Virtual Machines, mitigates these adversarial issuance attacks for profit-maximizing builders and ensures that any transactions they replicate must pay fees, restoring fTPS = rTPS. Vryx thus enables the HyperSDK to take full advantage of DSMR pipelining without sacrificing the robustness of traditional SMR, which can enforce full syntactic and semantic verification. Because Vryx only introduces additive constraints to DSMR replication and execution (and does not require any changes to consensus), most of its techniques could be incorporated into previously proposed and adopted DSMR constructions to defend against adversarial users.

Read more: https://hackmd.io/@patrickogrady/rys8mdl5p