BitVMX, a groundbreaking technology for Bitcoin, continues to evolve through rigorous research and development. This article kicks off a series exploring significant improvements to the BitVMX protocol. The focus here is on reducing the number of protocol rounds, particularly by eliminating the need for a second n-ary search.
This article summarizes the three innovative solutions that may reshape the BitVMX landscape.
Read the full article by Sergio Lerner here.
From Two N-ary Searches to One
One of BitVMX’s unique features is its shift from traditional state Merkle trees used in other rollup solutions. Instead, it employs two interactive n-ary searches to identify errors in execution steps.
While Merkle trees are effective, verifying them in Bitcoin script is error-prone and increases memory requirements significantly during local computation. BitVMX’s challenge is to remove this second search without expanding memory usage.
Problem Overview
In the BitVMX protocol two parties, prover and verifier, compare their locally computed hash chains containing a program’s execution trace. If discrepancies are found, an interactive protocol helps the verifier find the specific point in the hash chain where the computation is broken. During this protocol, the prover signs a number of hash steps requested by the verifier. When the reason the computation breaks is an invalid memory read, the verifier must find a second (previous) point in the hash chain where the memory was last written, to prove the bad read. This second point was already committed by the prover when signing the last correct step hash. Therefore the prover cannot “change her mind” about the value committed. The verifier needs an efficient “inclusion proof” in the step hash chain based on a commitment. Currently, this proof is performed interactively with a new n-ary search. While this search consumes a low amount of transaction fees, it requires many back-and-forth transactions, forcing the dispute to take much longer. The goal is to redesign the hash chain data structure to allow efficient inclusion proofs while keeping the data hashed per step minimal, preferably within 56 bytes.
Solution 1: Trace Merkle Tree
The first approach involves creating a Merkle tree of step traces. Each step in the hash chain commits to the Merkle root of this tree, updating with each new step. This method reduces additional memory storage during local computation to log2(n) hashes and ensures each execution step evaluates up to log2(n) hashes.
The new step hash format adding a Merkle trace tree root
Implementation Details
- New Step Hash Format: Combines the previous step hash, the step trace Merkle root, and the step write trace.
- Append Proof: Verifier proves the correctness of the trace root by presenting log2(n) hashes on-chain, allowing single-round verification.
- Inclusion Proof: Verifier shows a Merkle path from the root to the disputed step, requiring log2(n) hashes on-chain.
This approach maintains the integrity of the step sequence while ensuring efficient proof mechanisms. By leveraging the Merkle tree structure, BitVMX can achieve a balance between dispute time and dispute cost. The inclusion and append proofs streamline the verification process, reducing the need for multiple protocol rounds. This design not only enhances the efficiency of the protocol but also minimizes the computational overhead for the verifier, making it a practical solution for large-scale implementations.
Solution 2: Authenticated Skiplist
The skiplist is an authenticated data structure allowing logarithmic connections between any two steps in the trace. Each step references the previous step and an additional step based on a logarithmic scale. This structure supports efficient inclusion proofs and reduces the data required for hash evaluations.
One possible design for an authenticated skiplist. Some links of lane 1 have been removed because they don’t provide any shortcut. Each box represents a 2:1 hash function compression.
Implementation Details
- Fixed-size Messages: Ensures hash functions fit within Bitcoin script limits.
- Skiplist Design: Uses a hash chain for different lane pointers, allowing authenticated jumps between steps.
The authenticated skiplist offers a daring yet effective approach to streamline the BitVMX protocol. By allowing log(n)^2 connections, it significantly reduces the complexity of verifying step sequences. The skiplist’s design, which limits references to two prior steps, ensures that the proof sizes remain manageable and fit within the constraints of Bitcoin script. This method also simplifies the challenge process on-chain, as each verification step involves predictable and fixed-size hash evaluations.
Solution 3: Authenticated Jumplist
The jumplist, a new data structure, offers logarithmic inclusion proofs with simpler append proofs. Each node references two previous nodes: one immediately preceding it (short jump) and another chosen by a function (long jump).
A 64-node jumplist (short jumps in black, and long jumps in blue).
Implementation Details
- Long Jump Selection: Based on binary representation, allowing efficient navigation and inclusion proofs.
- Traversal Path: Ensures traversal from any node to a previous node in at most 3log2(n)+1 hops, optimized for efficiency.
The authenticated jumplist introduces a novel and efficient way to handle step verification in the BitVMX protocol. The jumplist’s structure reduces the need for extensive on-chain data by minimizing the number of hops required for verification. This results in faster and more cost-effective proof generation and verification processes. The simplicity of the jumplist design, combined with its powerful traversal capabilities, makes it a versatile tool not only for BitVMX but also for other blockchain applications, such as light clients and cumulative work proofs.
Conclusion
This article introduces three innovative techniques—Trace Merkle Tree, Authenticated Skiplist, and Authenticated Jumplist—that significantly reduce protocol rounds in BitVMX. These solutions enhance efficiency and lower transaction costs, paving the way for further innovations. Future articles will explore more advancements, including the use of truncated hashes to streamline on-chain proofs without compromising security.
Stay tuned for more groundbreaking developments in this exciting field.
To stay updated about the research and innovations regarding BitVMX, make sure to join the official BitVMX Builders telegram group to follow and contribute to the project’s progress.
Recommended reading
Explore the concept of BitVM and how it led to the discoveries in BitVMX in this series of research articles: