OptChain: Achieving Optimal Throughput of Permissionless Blockchains Chunjiang Che∗† , Songze Li†‡ , Xuechao Wang∗ , ∗ The Hong Kong University of Science and Technology (Guangzhou) † Southeast University ‡ Engineering Research Center of Blockchain Application, Supervision and Management (Southeast University),
arXiv:2606.23405v1 [cs.CR] 22 Jun 2026
Ministry of Education
Abstract—We introduce OptChain, a permissionless blockchain state machine replication (SMR) protocol that achieves optimal throughput. We first establish a theoretical upper bound on the throughput of any SMR protocol under a fixed error probability, and OptChain is the first protocol to approach this limit. Conceptually, OptChain is a sharding protocol that optimizes both vertical and horizontal scalability. Vertically, we introduce Shardis, a novel permissionless verifiable information dispersal mechanism that maximizes intra-shard throughput to its physical limit, determined by the fastest node’s bandwidth within each shard. Horizontally, we propose diffusion mining, which ensures security as long as each shard includes at least one honest node, thereby allowing for the maximum number of shards. We provide a formal security and efficiency analysis, demonstrating that OptChain approaches the established upper bound while maintaining robust security. Finally, we implement a full prototype of OptChain and deploy it on AWS EC2 nodes across various regions. Experimental results indicate that OptChain outperforms state-of-the-art permissionless protocols and closely approaches the theoretical optimal throughput.
I. I NTRODUCTION State machine replication (SMR) protocols, including longest chain-based approaches such as Proof of Work (PoW) and Proof of Stake (PoS), as well as voting-based approaches such as Byzantine Fault Tolerance (BFT), have attracted significant attention since 2008, when Satoshi Nakamoto introduced the concept of blockchain [1]. These protocols enable a network of nodes to reach agreement on a single, consistent state in the presence of Byzantine faults. However, existing SMR protocols, including Nakamoto consensus [1] and Practical Byzantine Fault Tolerance (PBFT) [2], inherently suffer from poor scalability, as their throughput is tightly constrained to ensure security. This tension is commonly referred to as the throughput-security trade-off. Numerous efforts have sought to improve this trade-off, including vertically scaling solutions (e.g., Bitcoin-NG [3], Prism [4], HotStuff [5], DispersedLedger [6]) and horizontally scaling solutions (e.g., sharding protocols [7, 8, 9, 10, 11]). Despite these advances, existing approaches still fall short of achieving optimal throughput while maintaining strong security guarantees. A. Optimal Throughput-Security trade-off We consider a system of n nodes with heterogeneous bandwidths, where a fraction α > 12 are honest. Let C and C denote the maximum and minimum node bandwidths,
respectively, measured in transactions per second. We establish an upper bound on the optimal throughput-security trade-off: for any SMR protocol that ensures an error probability less than σ, the throughput cannot exceed T = 1−σC1/αn . The formal theorem is presented in Section IV-B. This upper bound reveals two primary challenges in designing a SMR protocol to approach the theoretical optimum: 1) When σ = 0, T = C, indicating that the network must process transactions at the bandwidth of the fastest node. 2) When σ > 0, T > C, implying that the system must parallelize transaction processing—typically through a sharding protocol. Moreover, the number of shards should be maximized (see analysis in Section IV-B). To the best of our knowledge, no SMR protocol can simultaneously address these two challenges in a permissionless network. Prism [4] is the closest permissionless protocol to address the first challenge, achieving a throughput of 0.9C; however, it remains limited by the slowest node in the network. While DispersedLedger [6] can achieve a throughput approaching C, it is a permissioned protocol whose design is non-trivial to adapt to a permissionless setting. Furthermore, both are non-sharding protocols and inherently fail to address the second challenge. Conversely, Monoxide [11] and Manifoldchain [10] are the only sharding protocols that support maximal shards, yet they suffer from Bitcoin-like throughput within each shard and fail to address the first challenge. Consequently, no existing solution approaches this optimal throughput. B. Our Approach We present OptChain, the first layer-1 SMR protocol that approaches the optimal throughput-security trade-off in a permissionless network. Fundamentally, OptChain is a sharding protocol that simultaneously maximizes both vertical and horizontal scalability, thereby inherently approaching the optimal throughput-security trade-off. The two challenges discussed above also represent the key barriers to maximize vertical and horizontal scalability, respectively. Vertical scalability measures the improvement in throughput when computational and communication resources increase. When nodes in the network are configured with faster GPUs or higher bandwidths, the overall throughput should be increased. However, the throughput of most SMR protocols is
limited by the slowest node with the lowest bandwidth. In a heterogeneous network with stragglers—nodes with limited bandwidth—their vertical scalability is significantly hindered. To enhance vertical scalability, we propose a novel permissionless verifiable information dispersal (PVID) protocol, shardis, enabling throughput to scale with the fastest nodes despite stragglers. Intuitively, nodes first agree on an ordered log of commitments, each serving as a compact digest (e.g., a Merkle root) of an available block. Subsequently, nodes download the full block data to update their state machines. This design ensures that state replication is driven by the fastest honest nodes, making throughput a function of the fastest rather than the slowest participants. Consequently, this approach effectively addresses Challenge-(1) and serves as a cornerstone for achieving the optimal throughput-security trade-off. Horizontal scalability quantifies the improvement in throughput when the number of nodes increase. Sharding protocols have emerged as a promising approach to enhance horizontal scalability by dividing nodes into S distinct shards, each maintaining an independent ledger. However, most existing designs [7, 8, 9] require each shard to hold an honest majority—typically at least 1/2 or 2/3 of the shard’s nodes. By the law of large numbers, shard sizes must remain sufficiently large to keep the probability of adversarial-majority shards low. As a result, the number of shards (S) is inherently limited, which ultimately constrains horizontal scalability. We introduce the diffusion mining mechanism to ensure security as long as each shard contains at least one honest node, thereby maximizing S and the horizontal scalability. Intuitively, diffusion mining allows honest nodes to diffuse their hashing power across shards by mining global availability blocks that can be appended to chains in all shards. Even if some shards exhibit adversarial majorities (referred to as corrupted shards), honest hashing power can be aggregated from other shards with honest majorities to secure them, ensuring the effective honest hashing power exceeds 50%. This approach effectively addresses Challenge-(2), serving as another cornerstone for approaching the optimal throughput-security trade-off. The above design introduces a new challenge in ensuring cross-shard atomicity, which requires that coins deposits occur only after all corresponding withdrawals succeed. Existing sharding protocols [10, 11] adopt the Two-Phase Commit (2PC) protocol [12] to commit cross-shard transactions. In this approach, nodes use Merkle proofs to verify whether coins have been successfully locked in the withdrawal shards. The presence of a cross-shard transaction in the longest chain indicates that it has been validated by honest nodes in that shard, enabling the creation of coins on the deposit shards. However, OptChain cannot directly apply this mechanism, as it verifies transactions only after retrieving full blocks. This deferred verification introduces two challenges: (1) invalid withdrawals may be exploited to generate false deposits, and (2) network delays may cause some honest nodes to record a deposit before the corresponding withdrawal in their confirmed ledgers. To address these issues, OptChain employs an ordering chain to globally sequence availability blocks, ensuring
deposits occur only after all corresponding withdrawals, and uses Fraud Proofs [13] to sanitize the ledger by removing invalid transactions. We implement a prototype of OptChain in 7, 000 lines of Rust code [14] and evaluate it on a geo-distributed AWS EC2 testbed across four regions. To ensure fidelity, we utilized real-world bandwidth traces [15] to capture network heterogeneity. We extensively evaluated OptChain against the SOTA baselines—Manifoldchain and Prism—as well as an empirically derived theoretical optimum. Our results demonstrate that OptChain’s throughput closely approaches the theoretical optimum, significantly outperforming existing protocols across varying error thresholds. Moreover, further experiments confirm that OptChain achieves both optimal vertical and horizontal scalability, thereby significantly substantiating our aforementioned claims. C. Main Contribution We highlight our contributions as follows: 1) We establish an upper bound on throughput that constrains any permissionless SMR protocol. 2) We propose shardis, a novel PVID scheme that outperforms existing solutions, providing a pathway to optimal vertical scalability in permissionless systems. 3) We propose OptChain, a permissionless sharding protocol that approaches optimal throughput, and we formally prove both its security and throughput optimality. 4) We implement a full system prototype of OptChain and evaluate it on AWS EC2 instances spanning four regions, showing that its throughput experimentally approaches the theoretical optimum. II. R ELATED W ORK Many works have sought to enhance blockchain scalability, either vertically or horizontally, yet none have achieved optimality in both dimensions. Vertically Scaling Solutions. Among existing solutions [3, 4, 5, 6], Prism stands out as the most vertically scalable permissionless protocol. Its throughput approaches the physical limit, the network’s communication capacity, scaling linearly with the bandwidth of the slowest node. Prism decomposes the blockchain into three fundamental functionalities: leader election, transaction proposal, and ancestor voting. Accordingly, a full block is divided into three distinct components, proposer blocks, transaction blocks, and voter blocks, each corresponding to one of these functions. This decoupling enables fast consensus on lightweight proposer blocks and allows each to reference arbitrary number of transaction blocks, scaling throughput toward the network’s communication capacity. However, a significant gap remains between Prism’s throughput and the optimal, as it is limited by the slowest node’s bandwidth, not to mention its zero horizontal scalability. Horizontally Scaling Solutions. Sharding protocols are a fundamental approach to achieving horizontal scalability. Most existing sharding protocols [7, 8, 9] require each shard to
2
maintain an honest majority, limiting the number of shards and hindering horizontal scalability. Manifoldchain [10] addresses this limitation by tolerating corrupted shards, ensuring crossshard security as long as each shard contains at least one honest node. It introduces two block types: exclusive blocks, which function like regular blocks, and inclusive blocks, which can be appended to all shard chains. Inclusive blocks allow honest nodes to distribute their hashing power across shards, reinforcing the security of those shards with weaker honest hashing power. However, while Manifoldchain maximizes horizontal scalability, its throughput within each shard remains comparable to Bitcoin, reflecting poor vertical scalability. Motivated by this limitation, we leverage a similar methodology to design diffusion mining, distinguishing our approach by allowing shard throughput to approach the bandwidth of the fastest node.
(deposits) may span different shards, and the protocol must also guarantee: Definition 2 (Cross-shard Security Property). • Cross-shard Atomicity: For any cross-tx distributed across withdrawal and deposit shards: (1) if all withdrawal operations are confirmed, all deposit operations will eventually be confirmed; (2) if any deposit is confirmed, all withdrawals must already be confirmed and all deposits will eventually be confirmed; and (3) if initiated by an honest user, the entire cross-tx (including withdrawals and deposits) will eventually be confirmed. B. Verifiable Information Dispersal Verifiable Information Dispersal (VID) is an effective approach for reducing communication overhead in blockchains, and has been adopted by many permissioned protocols [6, 16]. Specifically, it allows a node to run a dispersal protocol to distribute blocks across various nodes, and later execute a retrieval protocol to reconstruct the original block. Through this process, honest nodes can agree on a block’s availability by downloading only a block fragment. We present the formal definition of VID below, consistent with prior works [6, 17].
III. P RELIMINARIES A. Scalable SMR via Sharding An SMR protocol, as its name suggests, enables multiple machines to agree on the same state despite Byzantine behavior. In this context, a client–server model is typically assumed: We consider a system of n servers, each maintaining a replica of the state machine, where up to a fraction β = 1 − α of them are malicious. Clients submit transactions to all servers to update or read the machine state. The servers then execute an SMR protocol to agree on a consistent, totally ordered log of transactions, which they subsequently execute to maintain the replicated state. For simplicity, we use the term node instead of server, as both share the same meaning but node is more common in the blockchain context. Traditional SMR protocols suffer from poor scalability in large-scale networks, as every node must replicate the entire machine state, resulting in significant overlap in communication and computation overhead. The blockchain sharding protocol is proposed to address this problem. It partitions the nodes into multiple shards, each responsible for executing a distinct subset of transactions. Specifically, both transactions and nodes are assigned shard identifiers (IDs), and a node only executes transactions that share its shard ID. This design enables different nodes to work in parallel, allowing the overall system throughput to scale proportionally with the number of shards—and inherently, with the number of nodes. Formally, a sharding protocol provides the following properties, which can be categorized as intra-shard and cross-shard security properties:
Definition 3. A Verifiable Information Dispersal scheme consists of three core procedures: • D ISPERSE (B) → com: A deterministic algorithm executed by the proposer of a block B ∈ {0, 1}∗ to initiate the dispersal process and returns a block commitment com. • V ERIFY (com) → {0, 1}: A randomized interactive protocol invoked by validators to determine whether the dispersal of the block associated with commitment com has completed. It outputs 1 if the dispersal is complete, and 0 otherwise. • R ETRIEVE (com) → B: An interactive protocol invoked by a node to recover a data block B ∈ {0, 1}∗ . Formally, a VID protocol is secure if it satisfies the following properties except with negligible probability. • Termination: If an honest node invokes D ISPERSE (B), it eventually gets an output com, and all honest nodes eventually output V ERIFY(com) = 1. • Agreement: If any honest node outputs V ERIFY (com) = 1, then every honest node will do the same within a network delay of ∆. • Retrievability: If an honest node outputs V ERIFY (com) = 1, then any honest node that invokes R ETRIEVE(com) eventually reconstructs some block B ′ . • Correctness: For any two successful R ETRIEVE (com) calls that yield B1 and B2 , where V ERIFY(com) = 1, it holds that B1 = B2 . Furthermore, if com was generated by an honest node via D ISPERSE(B), then B1 = B. VID is an effective technique for improving throughput independent of slow nodes. DispersedLedger [6] employs VID to scale throughput with the fastest node’s bandwidth. Specifically, block producers disperse block symbols via VID
Definition 1 (Intra-shard Security Property). • Safety: If two honest nodes in the same shard execute sequences of transactions {tx1 , . . . , txj } and {tx′1 , . . . , tx′j ′ }, then txi = tx′i for all i ≤ min{j, j ′ }. • Liveness: If an honest client sends a transaction tx to all nodes at time t, then tx will eventually be executed by all honest nodes in a specific shard by time t + u. In sharding protocols, a cross-shard transaction (crosstx) consisting of multiple inputs (withdrawals) and outputs
3
and broadcast a commitment to all nodes, which quickly reach consensus on an ordered set of commitments. Each node then retrieves and reconstructs the corresponding blocks at its own pace, allowing fast nodes to advance the ledger more quickly. Permissionless VID. Although many VID schemes have been proposed for permissioned protocols [6], deploying one that operates effectively in a permissionless setting remains challenging. In a permissioned network, each node must authenticate itself to join the protocol, ensuring that all nodes know the total number of participants n and the upper bound on corrupted nodes βn. One can add redundancy to a block using erasure coding, which can be recovered from any e symbols, where e is a constant. Thus, if βn + e nodes report holding a symbol, dispersal is complete, as at least e honest nodes must have received it. However, in a permissionless system, the parameter n is unknown, because an adversary can distribute its hashing power across multiple devices to arbitrarily increase the number of corrupted nodes. Fisch et al. proposes the first permissionless VID scheme [18]. Intuitively, nodes vote “yes” or “no” on a block commitment via the underlying SMR protocol, based on whether they have received the requested symbols. A block is considered successfully dispersed if the difference between “yes” and “no” votes exceeds a threshold. However, this permissionless VID design loses gain as the adversarial ratio α approaches 1/2. Specifically, the scheme requires any (α−β)n nodes to reconstruct the block, implying each node must store many symbols. Denoting the as b bytes, the per-node block size b , which degrades to O(b) communication cost is O (α−β)n as (α − β)n → 1. In this case, each node must download the full block to complete the dispersal. Furthermore, it requires each node to request an equal number of symbols, resulting in uniform workload distribution across all nodes for a block. This uniformity makes such schemes unsuitable for sharding protocols, where in-shard nodes should request more symbols than out-shard nodes because they eventually need to retrieve the full block—thus, requesting more symbols does not impose additional overhead on them. In this paper, we propose shardis, b which achieves a per-node communication cost of O αn , as detailed in Appendix F. In our design, the workload of each block is primarily handled by in-shard nodes, while out-shard nodes are responsible for only a negligible fraction.
the second layer is built on the coded block’s symbols and re-encoded with the same erasure code to form the third layer. This process repeats iteratively until the final root is obtained. Any honest node can verify full data availability by downloading only a block commitment of size O(1) bytes and randomly sampling O(log b) bytes. Specifically, given a block B, CMT encodes the block and computes its commitment. If every honest node requests O(log b) bytes upon receiving the commitment, the following properties hold: • Soundness: If an honest node determines that a block is available, then at least one honest node will be able to recover the block within a constant delay. • Agreement: If an honest node determines that a block is available, then all other honest nodes in the system will also determine that the block is available within a constant delay. IV. T HROUGHPUT-S ECURITY T RADE - OFF In this section, we introduce a formal model for analyzing security and throughput, and establish a fundamental upper bound on the throughput of any permissionless SMR protocol. A. Security Model We summarize our assumptions below, which are consistent with those commonly adopted in permissionless blockchain protocols [1, 4, 11, 10]. • The system comprises n nodes, denoted by {P1 , . . . , Pn }, operating in a synchronous and permissionless network. • A weakly adaptive adversary controls a fraction β < 1/2 of the nodes, while the remaining fraction α = 1 − β are honest. Corruption is dynamic but requires a delay to effectuate. • Nodes have heterogeneous bandwidths, where Pi has a download capacity of bi . We denote the maximum and minimum bandwidths as C and C, respectively. • For simplicity, we assume all nodes possess homogeneous computational power. B. Optimal Throughput We derive the optimal throughput under these assumptions above. We also provide the intuition behind this upper bound, while the formal proof is deferred to Appendix B. Theorem 1. If an SMR protocol guarantees that the probability of any confirmed transaction violating at least one of the security properties is bounded by σ, then the upper bound on throughput is T ∗ = C 1 .
C. Coded Merkle Tree As previously mentioned, our protocol ensures security even if each shard contains only a single honest node. The Coded Merkle Tree (CMT) [19] is a crucial building block for this, because it provides constant-cost protection against data availability attacks, even when the majority of nodes are malicious. Specifically, CMT employs an (vd, d) erasure code to introduce redundancy: a block B of b bytes is evenly divided into d data symbols, B = [m1 , . . . , md ], each of size b d bytes. These symbols are linearly combined to produce a coded block CB = [c1 , . . . , cvd ], where v denotes the coding rate. The original block B can be reconstructed from any d of the vd coded symbols. When constructing the Merkle tree,
1−σ αn
Proof Sketch. First, we relax the assumption on nodes’ bandwidths and allow each node to download transactions at the same rate as the fastest node. In other words, each node can download at most C transactions per second, so the entire network can download at most nC transactions per second. Then, each transaction appears, on average, in at most nC T copies across the network, with each copy downloaded by one node. For any given transaction, the probability that a particular node downloads a copy is C T . To ensure availability, at least
4
one honest node must download each transaction; otherwise, malicious nodes could withhold it, rendering the transaction unavailable and thus ineligible to be counted in throughput. Consequently, the probability that all copies of a transaction αn . By are downloaded only by corrupted nodes is 1 − C T backward reasoning, we can derive the optimal throughput C given an error probability of σ. 1 1−σ αn Based on the proof sketch, achieving optimal throughput requires addressing two fundamental challenges: 1) The protocol must be capable of processing transactions at the rate of the fastest node. As the error threshold σ → 0, the throughput T approaches C, implying that the system must fully utilize the maximum available node bandwidth. 2) The protocol must be a sharding protocol that ensures security as long as each shard contains at least one honest node. If the protocol requires more than one honest node per shard to ensure security, the failure condition expands (i.e., the error occurs even when one honest node is present). This effectively raises the error probability αn . above the theoretical lower bound σ ′ (T ) > 1 − C T Consequently, to maintain the target error bound σ ′ (T ) < σ, the system would be forced to throttle throughput such that T < T ∗ . The analysis motivates the design of OptChain. Vertically, we design shardis to enable intra-shard consensus to tightly follow the fastest node’s bandwidth. Horizontally, we introduce diffusion mining to ensure global security with a minimum of one honest node per shard.
Proposer chain
Availability chains
Ordering chain
…
…
…
Shard 1
Shard 2
Transaction block
Shard S
Local availability block
Proposer block Ordering block
Global availability block
Fig. 1. The structure of OptChain, which comprises five block types. Proposer blocks form a global beacon chain (left) that references multiple transaction blocks by including their commitments. Availability chains (middle) span S shards, where availability blocks reference transaction blocks to vote on their availability. While local availability blocks extend a single chain, global availability blocks extend all availability chains simultaneously. Finally, the ordering chain (right) consists of ordering blocks that sequence the availability blocks to impose a global order.
across shards, establishing a global order for the availability blocks across shards. A. Block and Chain Structures In OptChain, blocks are classified as proposer, transaction, availability, and ordering blocks. Each transaction block Bt is assigned a shard ID. It contains t transactions in the corresponding shard and a root computed by CMT, which serves as its commitment com. • Transaction block Bt : 1) shard ID: an index denoting the specific shard to which the block is affiliated. 2) data blob: a set of t transactions. 3) com: the root of a CMT constructed from the included transactions. 4) nonce: the resolved solution to a PoW puzzle. A proposer block Bp functions like a standard Bitcoin block but includes references to transaction blocks—their commitments—instead of the transactions themselves. The proposer has no shard ID, and the proposer chain serves as a global beacon chain: • Proposer block Bp : 1) prop parent: the hash of the parent proposer block. 2) prop com set: a set of com of the transaction blocks. 3) nonce: the resolved solution to a PoW puzzle. Availability blocks are assigned shard IDs and serve as votes for the availability of transaction blocks referenced by the proposer chain. Each availability block may include multiple block commitments confirmed in the proposer chain,
V. O PT C HAIN OptChain approaches the optimal throughput by simultaneously maximizing vertical and horizontal scalability. To better illustrate this, we start by showing how to maximize vertical scalability, i.e., optimizing the performance of a single chain, then extend the design to multiple shard chains to demonstrate how optimal horizontal scalability can be achieved. Intuitively, OptChain maximizes vertical scalability by implementing a permissionless VID protocol. Nodes first agree on an ordered log of block commitments, and then independently download the corresponding transactions to update their state machines at their own pace. Once each shard’s throughput is optimized, OptChain employs diffusion mining to design a multi-chain structure, supporting an optimal number of shards, thereby maximizing horizontal scalability. The full structure of OptChain is shown in Fig. 1. OptChain consists of three distinct chains, each serving a specific function. First, nodes mine a proposer chain, where each proposer block contains commitments of multiple transaction blocks. Second, nodes verify the availability of these commitments by mining S availability chains. Each availability block in the i-th chain includes references to commitments that (1) are confirmed in the proposer chain, and (2) correspond to transaction blocks belonging to shard i. Finally, nodes mine an ordering chain that references confirmed availability blocks
5
indicating that the producer has verified their availability. Based on their hash, availability blocks are categorized as either local or global availability blocks. Local availability blocks extend a single chain, whereas global availability blocks can extend multiple chains simultaneously. • Availability block Ba : 1) shard ID: an index denoting the specific shard to which the block is affiliated. 2) inter parent: the hash of the parent availability block within the affiliated shard. 3) global parents: a set composed of all parents across all shards. 4) avai com set: a set of com of the transaction blocks. 5) nonce: the resolved solution to a PoW puzzle. An ordering block references multiple availability blocks, forming a chain that imposes a global order on confirmed availability blocks across shards. • Ordering Block Bo : 1) order parent: the hash of the parent ordering block. 2) avai blk set: a set of hash of the availability blocks referenced by this block. 3) nonce: the resolved solution to a PoW puzzle.
to make the block unavailable. This reduces the number of nodes who are deceived by requesting the released symbols. For example, consider a block with 4 symbols, where each honest node requests only one symbol. The adversary releases three symbols and withholds one, causing 3/4 of honest nodes to accept this unavailable block. However, after encoding the block with a (8, 4) erasure code, the adversary must withhold 5 symbols since the full block can be retrieved with any ≥ 4 symbols. This reduces the proportion of deceived nodes to 3/8. • Requesting more symbols for old blocks. Nodes first mine a proposer chain to reach consensus on an ordered set of potential com(s), and then request symbols for confirmed com(s) based on their depth in the proposer chain. The deeper a com is in the proposer chain, the more symbols are requested. This approach prevents the adversary from deceiving an arbitrary number of honest nodes by hiding many blocks, as they must first post blocks in the proposer chain. Additionally, any longwithheld blocks require more symbols to deceive honest nodes, and the probability of success diminishes with the withholding time. To realize the above insights, we decouple the proposer chain into two separate chains: a proposer chain and an availability chain, which handle the D ISPERSE(B) and V ER IFY (com) procedures, respectively. Nodes may invoke R E TRIEVE (com) at any time after dispersal is complete. Proposer chain (D ISPERSAL). Nodes treat instances of D IS PERSE(Bt ) as transactions and execute the following protocol to append them to the proposer chain. Once the dispersal of an instance is complete, the invoker outputs a com.
B. Shardis Our permissionless VID scheme is designed based on the following intuition: The block producer broadcasts com when it initiates D ISPERSE(B) → com. Nodes randomly request symbols upon receiving com and verify availability once all requested symbols are received. Nodes then run a longest chain-based protocol to agree on an ordered list of available com. By the protocol’s safety, every honest node will have the requested symbols for any confirmed com. With an estimated αn honest nodes and a properly chosen symbol threshold per node, the full block can be reconstructed except with a negligible probability. A naive implementation of this high-level idea can be achieved by slightly modifying an existing protocol, such as Prism. Unlike the nodes in the original Prism protocol, who accept a block only after receiving it in full, the nodes in our initial protocol accept a block upon receiving all the requested symbols of that block. However, this initial protocol faces a significant challenge. The adversary can propose an unavailable block, releasing only partial symbols, and respond solely to nodes requesting them. This can deceive a portion of honest nodes who request the released symbols, leading them to accept the block, while others reject it, causing a split view. Furthermore, the adversary can conceal any number of unavailable blocks and propose them simultaneously, causing an arbitrary number of honest nodes to split their views. To resolve the above challenges, we consolidate our permissionless VID scheme by applying the following high-level insights: • Using erasure coding to reduce the proportion of deceived nodes. Erasure coding adds redundancy to the block, requiring the adversary to withhold more symbols
Packing: The block producer broadcasts the com of Bt to all nodes. Each node collects all unreferenced com(s) to populate the prop com set of a proposer block and selects the hash of the highest proposer block as its prop parent. • Mining: The node iterates over nonce values to solve the PoW puzzle and mines a valid proposer block, which is then broadcast to the network. • Verification: A node accepts a proposer block if the included PoW solution is valid. • Confirmation: A proposer block Bt is confirmed once it is followed by k proposer blocks. At that point, the node outputs D ISPERSE(Bt ) = com. •
Availability chain (V ERIFY). Nodes mine the availability chain to maintain the status of dispersed com, serving as an oracle to respond to invokers of V ERIFY(com). Sampling: For any confirmed com at level l in the proposer chain, and given the current highest level l′ of the chain, a node randomly requests l′ − l symbols of the block associated with that com. • Packing: Each node gathers all unreferenced com(s) for which the requested symbols have been received. These are used to populate the avai com set of an availability •
6
hash h if they find a valid nonce. The type of the availability block is determined by comparing its size with a threshold h′ . 1) If h > h′ , the block is a local availability block and extends the availability block with hash inter parent in shard i. 2) If h ≤ h′ , the block is a global availability block and extends the availability blocks whose hashes are included in global parents across shards. • Verification: A node accepts an availability block if 1) The PoW solution is valid. 2) The node has received the requested symbols for all referenced com(s). • Confirmation: An availability block Ba is confirmed once it is followed by k ′ subsequent availability blocks. • Response: For each call to V ERIFY (comi ), output V ER IFY (comi ) = 1 if comi is confirmed in the i-th availability chain; otherwise, output 0. Both in-shard and out-shard nodes request symbols for a specific confirmed com in the proposer chain. The key difference is that in-shard nodes continuously sample an increasing number of symbols over time until com is included in the longest availability chain, whereas out-shard nodes request a fixed number of symbols at once. Moreover, since out-shard nodes greatly outnumber in-shard nodes, each out-shard node only needs to request a small number of symbols, making the communication cost for verifying out-shard blocks negligible.
block. The node also selects the hash of the highest availability block as the inter parent. • Mining: The node searches for a valid nonce to solve the PoW puzzle and mines an availability block, which is then broadcast to the network. • Verification: A node accepts an availability block if (1) the PoW solution is valid and (2) it has received all the requested symbols for all included com(s). • Confirmation: An availability block Ba is confirmed once it is followed by k ′ subsequent availability blocks. • Response: For each call to V ERIFY (com), output V ER IFY(com) = 1 if com is a confirmed com in the availability chain; otherwise, output 0. C. Diffusion Mining Our initial idea for extending the above design into a sharding protocol is to have all nodes collectively mine a single proposer chain, while nodes within each shard mine their respective availability chains. Specifically, the proposer chain references transaction blocks across all shards, whereas the S availability chains operate in parallel, with each node producing availability blocks exclusively for its assigned shard. However, each shard must have sufficient nodes to ensure an honest majority. To overcome this limitation, we introduce a diffusion mining that secures each shard even when only one honest node is present. Diffusion mining classifies availability blocks into two types: local availability blocks and global availability blocks. While a local availability block operates within a single shard, a global availability block can extend all chains across shards. In a longest chain-based protocol, the number of valid blocks reflects hashing power, and security is maintained as long as honest blocks outnumber adversarial ones. Diffusion mining allows honest nodes to distribute their hashing power across shards, thereby securing those with weaker honest hashing power. We adopt this mechanism to strengthen our design: Availability chains (V ERIFY). Each com inherits a shard ID i from its corresponding transaction block. Nodes within shard i mine an availability chain, where each availability block references only the com(s) associated with shard i.
D. Cross-shard Atomicity We adopt the Unspent Transaction Output (UTXO) model, where a transaction is defined as tx : {I1 , . . . , Ik ; O1 , . . . , Oh }. The {Ii } represents withdrawal operations, while the output set {Oj } corresponds to deposit operations, and each input/output is associated with an address. Outputs can serve as inputs to subsequent transactions but can be spent only once. In the context of sharding, each address is assigned a shard ID, inherited by its inputs and outputs. A transaction whose inputs and outputs belong to the same shard is termed a domestic transaction (domestic-tx), whereas one spanning multiple shards is a cross-tx. Shards whose IDs match any input’s shard ID are called withdrawal shards for the cross-tx, and those matching any output’s shard ID are deposit shards. Each cross-tx is replicated across all withdrawal and deposit shards and processed independently as withdrawal-txs and deposit-txs, respectively. In sharding protocols, nodes must reach consensus on whether to commit a cross-tx—a requirement formalized as the cross-shard atomicity property, defined in Definition 2. A common approach to ensure this is the 2PC protocol [12]. Specifically, coins are locked once a withdrawal-tx is confirmed. After all withdrawal shards successfully lock the coins, the deposit shards accept the corresponding deposittxs and create new coins. An important question in sharding protocols is how nodes can verify coin locking without access to other shards’ ledgers. Protocols such as Monoxide [11]
Sampling: For any confirmed com tagged i′ not in the longest availability chain of shard i, 1) If i′ = i, given its level l and the current highest level ′ l′ of the proposer chain, a node randomly requests l S−l symbols of the block. 2) If i′ ̸= i, a node randomly requests a constant number u of symbols from the block. • Packing: Each node gathers all unreferences com(s) in shard i for which the requested symbols have been received. These are used to populate the avai com set of an availability block. The node collects the highest availability block hashes across all shards and records it in global parents. • Mining: Each node searches for a valid nonce to solve the PoW puzzle and produces an availability block with •
7
as locked. However, this mechanism cannot be directly applied to OptChain. In OptChain, nodes do not verify transactions when confirming blocks; instead, they do it after retrieving the complete transaction blocks, removing invalid and duplicate transactions to sanitize the ledger. This design introduces two new challenges: • A withdrawal-tx in the longest chain is not necessarily valid, as it may be a duplicate or double-spend transaction. An adversary can craft such invalid withdrawal-txs and exploit their Merkle proofs to generate valid deposittxs. • Network delays may cause some honest nodes to confirm deposit-txs before their corresponding withdrawal-txs, leading them to reject the deposits, while others accept them, resulting in a split view. To address these challenges, we introduce an ordering chain that sequences availability blocks across shards, thereby establishing a global transaction order. This mechanism guarantees that any valid deposit-tx is confirmed only after all corresponding withdrawal-txs. Furthermore, we leverage fraud proofs [13] to sanitize the ledger by removing duplicate and invalid transactions. 1) Ordering Chain: Mining an ordering block is straightforward: package the hashes of confirmed availability blocks into an ordering block, then perform PoW to append it to the longest ordering chain: • Packing: Nodes collect hashes of confirmed availability blocks not already included in ancestor ordering blocks to form avai blk set, and select the hash of the latest ordering block as order parent. • Mining: Nodes iterate over nonce values to solve the PoW puzzle and mine a valid ordering block, which is broadcast to the network. • Verification: An ordering block is accepted if its PoW is valid, and all referenced availability blocks are confirmed and not included in any ancestor blocks. • Confirmation: An ordering block is confirmed once it is followed by k ′′ ordering blocks. The structure of all the chains is illustrated in Fig. 1. To prevent the adversary from concentrating hashing power on a single chain to exceed its 1/2 fault tolerance threshold, we employ the idea of 2-for-1 PoW [20] to mine these S + 2 chains concurrently. Nodes first attempt to mine a hybrid block containing all necessary information to serve as any block type. Once mined, the block is classified into a specific type according to the region where its hash falls. We present the complete protocol of OptChain in Fig. 2. 2) Fraud Proof: When an adversary attempts to use an invalid withdrawal-tx to construct a fraudulent Merkle proof for a deposit-tx, honest nodes can generate a fraud proof to alert other shards of the invalidity. Specifically, there are two types of fraud proofs. The first type, proof of conflict, is designed to filter out invalid transactions, which are typically produced by corrupted nodes, and is formatted as follows:
Parameters: H and G denote hash functions, δ is the overall mining difficulty, and δp , δga , δla , and δo specify the difficulty thresholds for different block types. Packing: The node gathers the necessary information for a hybrid block: • Block header Bh : 1) shard ID: The node’s affiliated shard. 2) prop parent: The hash of the highest proposer block. 3) inter parent: The hash of the highest availability block in the shard ID-th shard. 4) global parents: A set containing the hashes of the highest availability blocks in their respective shards. 5) prop root: The root of a Merkle tree generated from prop com set. 6) avai root: The root of a Merkle tree generated from avai com set. 7) order root: The root of a Merkle tree generated from avai blk set. 8) com: The root of a CMT generated from data blob. • Block body Bb : 1) prop com set: Set of transaction block commitments (com) not yet referenced in the longest proposer chain. 2) avai com set: Set of coms that (i) are unreferenced in the longest availability chain of shard id-th shard, (ii) are confirmed in the proposer chain, and (iii) have all requested symbols received. 3) avai blk set: Set of hash of confirmed availability blocks not yet referenced in the longest ordering chain. 4) data blob: A set of t valid transactions. Mining: 1) The node iterates nonce to make: hash = H(G(Bh ), nonce) ≤ δ.
(1)
2) When a valid nonce is found, determine the block type as follows, and broadcast Bh along with the corresponding field in Bb to other nodes: • hash ≤ δga : global availability block. • δga < hash ≤ δla : local availability block. • δla < hash ≤ δo : ordering block. • δo < hash ≤ δp : proposer block. • δp < hash ≤ δ: transaction block. Sampling: For each com in the proposer chain, whose associated proposer block is followed by k blocks and originates from shard i, a node in shard i′ requests: • u symbols if i′ ̸= i; l′ −l symbols if i′ = i, where l is the level of the proposer block • S and l′ is the highest level in the proposer chain. Verification: A node validates a block by verifying its PoW solution and inspecting its content according to the block type: • Availability block: accepted if 1) the Merkle root of avai com set matches avai root in Bh ; 2) all coms are confirmed in the proposer chain; 3) all requested symbols are received. • Ordering block: accepted if 1) the Merkle root of avai blk set matches order root in Bh ; 2) all availability blocks in avai blk set are confirmed. • Proposer block: accepted if the Merkle root of prop com set matches prop root in Bh . • Transaction block: accepted without additional verification. Confirmation. Proposer, availability, and ordering blocks are confirmed after depths of k, k′ , and k′′ , respectively. Fig. 2. The full protocol of OptChain.
and Manifoldchain [10] address this by Merkle proofs of withdrawal-txs generated by honest nodes in those shards. Once a withdrawal-tx is confirmed in the longest chain, all honest nodes recognize it and mark the corresponding coins
8
Ordering Chain Availability Block Transaction Block Log Log
Sanitized Ledger
Tx(0132..98,1) Tx(0132..98,2) Tx(4275..76,1) Tx(4275..76,2) Tx(6212..34,1) Tx(6212..34,2) Tx(6024..16,1) Tx(6024..16,2) Tx(5280..58,1) Tx(5280..58,2) Tx(1327..05,1) Tx(1327..05,2)
Tx(0132..98,1) Tx(0132..98,2) Tx(6212..34,1) Tx(6212..34,2) Tx(6024..16,2) Tx(5280..58,1) Tx(5280..58,2)
Tx(0132..98,1) Tx(6212..34,1) Tx(6212..34,2) Tx(5280..58,1) Tx(5280..58,2)
Proof of conflict
Unique Ledger
Proof of duplicate
0132..98 4275..76 6212..34 6024..16 5280..58 1327..05
Transaction Log
Fig. 3. The process of ledger sanitization. First, availability block hashes are arranged through the ordering chain to form an availability block log. Second, each availability block’s com(s) are appended in sequence to create a transaction block log. Third, each com is expanded by block size and paired with transaction indices as (com, i), forming a transaction log. Upon retrieving a transaction block, its transactions follow the same order as in the CMT, ensuring that any two nodes retrieving (com, i) obtain the same transaction. Finally, entries with proof of duplicate or proof of conflict are removed, yielding a sanitized log containing only unique and valid transactions.
proof by checking for any intersection of hashes between these two components. Both proof of conflict and proof of duplicate fall under the category of fraud proofs. Upon receiving a fraud proof, out-shard nodes verify its correctness and mark the implicated transaction as invalid. The communication overhead of transmitting fraud proofs is minimal. Invalid transactions are typically grouped in an invalid block created by corrupted nodes, which can be proven invalid using a single Merkle proof. Fraud proofs for duplicate transactions add only negligible overhead since they contain only lightweight hash digests. 3) Ledger Sanitization: We construct a sanitized ledger log by sequentially transforming block information into a consistent and ordered transaction log, as shown in Fig. 3.
proof of conflict = { ({tx01 , tx02 , . . . }, com0 , merkle proof) , ({tx11 , tx12 , . . . }, com1 , merkle proof1 ), ({tx21 , tx22 , . . . }, com2 , merkle proof2 ),
(2)
... ({txi1 , txi2 , . . . } , comi , merkle proofi ) }, where txik denotes the k-th transaction in the block rooted at comi . A proof of conflict comprises two components. The first component (green) contains valid transactions (tx01 , tx02 , . . . ) against which no valid fraud proofs exist. The inclusion of transactions sharing the superscript i is authenticated via a single Merkle proof, merkle proofi . The second component (red) contains the conflicting transactions, organized similarly. Nodes validate the fraud proof by verifying whether any conflicting transaction double-spends inputs from the first component or contains invalid signatures. For duplicate transactions (which are also invalid), nodes do not need to know the full transaction data. So we replace each transaction with its hash and introduce a lightweight proof of duplicate, formatted as follows:
1) Ordering availability blocks via the ordering chain. Each ordering block contains multiple hashes of availability blocks. These hashes are added to a queue in the order they appear within each ordering block and in the sequence that the ordering blocks appear in the ordering chain. The resulting queue forms an availability block log, where each entry corresponds to an availability block hash. 2) Transferring availability blocks to transaction blocks. Each availability block contains multiple coms of transaction blocks. Append these coms to a queue in the order they appear in their respective availability blocks, and in the order those availability blocks appear in the availability block log. This queue forms a transaction block log with multiple coms as its entries. 3) Transferring transaction blocks to transactions. Each com is the root of a CMT generated from t transactions. We use (com, i) to denote the i-th transaction in the block rooted at com. These pairs are appended to a queue in the order that com appears in the transaction block log, and in increasing order of i. This queue forms the finalized ledger log. When a node retrieves a transaction block, its transactions are ordered as they were in the CMT. Therefore, any two nodes retrieving (com, i) will get the same transaction.
proof of duplicate = { ({hash01 , hash02 , ...}, com0 , merkle proof0 ), ({hash11 , hash12 , ...}, com1 , merkle proof1 ),
(3)
... ({hashi1 , hashi2 , ...}, comi , merkle proofi ) } hashik denotes the hash of the k-th transaction in the block rooted at comi . The first component (green) contains the hashes of valid transactions (hash01 , hash02 , . . . ) against which no valid fraud proofs exist. The second component (red) contains the hashes of duplicate transactions. Nodes validate the fraud
9
4) Removing duplicate and invalid transactions. First, remove entries with valid proof_of_duplicate from the transaction log. Then remove entries with proof_of_conflict from the remaining log. The result is a sanitized ledger containing only unique and valid transactions. 4) Cross-shard Transaction Execution: The complete protocol for processing cross-txs is as follows: 1) Initialization. The client generates a cross-tx and decomposes it into multiple withdrawal-txs and deposittxs. Subsequently, it broadcasts the withdrawal-txs to the corresponding withdrawal-shards. 2) Withdrawal. Upon retrieving a withdrawal-tx from the confirmed log, a node in a withdrawal shard checks its validity using local ledger data. If valid, the node generates a Merkle proof and sends it to the user; otherwise, it is discarded. 3) Deposit. After collecting all Merkle proofs, the user sends them with the deposit-tx to the deposit shards. When a node in a deposit shard receives or retrieves a deposittx, it checks: (a) all Merkle proofs are present, and (b) no valid fraud proof exists. If valid, the node accepts and executes the deposit-tx; otherwise, it is rejected and discarded. We prove in Appendix D that the above protocol guarantees cross-shard atomicity defined in Definition 2.
entirely unmodified. Formally, OptChain satisfies both safety and liveness, as established in the following theorems: Theorem 2 (Safety). If there is at least one honest node in each shard, OptChain satisfies safety except with negligible error probability negl(k) provided that: 1 1 , po = αe−λo ∆ > , 2 2 λs α + Sλi α′ −(λs +λi )∆ 1 pa = e > , Sλi 2 "λs + # k 1 1 1 α′ =α 1 − > , v v−1 2 pp =αe−λp ∆ >
(4)
where α = α′ − log2 (α′ ). Theorem 3 (Liveness). Suppose each shard contains at least one honest node and the conditions of Theorem 2 hold. Assuming a current ledger height ℓcur , a transaction at height ℓcur − ℓ (ℓcur > ℓ) submitted at time t is confirmed by t + u except with a negligible error probability negl(ℓ), where X k + ⌈1/qx ⌉ + 5∆, u= gx x∈{p,o,a}
where gx and qx represent the chain growth and chain quality for each chain x ∈ {p, o, a}, corresponding to the proposer, ordering, and availability chains, respectively: px Λx , 1 + px ∆Λx 1 + px (1 − αx )∆Λx qx = 1 − (1 + δ) . px
VI. A NALYSIS
gx = (1 − δ)
Let αi and βi denote the honest and adversarial fractions in shard i. Define λp , λt , λi , λs , and λo as the mining rates (blocks per second) of proposer, transaction, local availability, global availability, and ordering blocks, respectively. Let ∆p , ∆t , ∆i , ∆s , and ∆o represent their corresponding maximum network delays. Since proposer, availability, and ordering blocks contain only lightweight digests, ∆p = ∆s = ∆i = b ). In contrast, transaction blocks carry full ∆o = ∆ ≤ O( αn ledger data, yielding ∆t = ∆ = O(b).
Here, Λp = λp , Λo = λo , and Λa = λs + λi ; while αp = αo = α, and αa = α. While individual chains may require varying confirmation depths (e.g., k, k ′ , and k ′′ ), we simplify our analysis using a unified depth k = max{k, k ′ , k ′′ }. In Theorem 2, pp , po , and pa represent the effective honest ratios for mining these chains while accounting for network delay. It suggests that safety holds as long as these effective honest ratios maintain a majority. This constraint is consistent with those established in prior works [10, 21]. To satisfy this condition in the presence of a larger network delay, mining rates must be correspondingly reduced. Notably, baseline protocols such as Bitcoin and Manifoldchain incur a substantial network delay ∆ that scales linearly with transaction block size. Conversely, because OptChain’s block size is restricted to its metadata, it experiences only a negligible delay ∆, thereby permitting significantly higher mining rates. This explains why OptChain outperforms other protocols in throughput. Theorem 3 states that any transaction submitted at time t will be confirmed by t+u. Here, u is calculated based on the chain growth and chain quality parameters of these chains, representing the worst-case latency for any transactions. Proof Sketch. We first show that the proposer chain, ordering chain, and all availability chains satisfy the three standard
A. Security of OptChain OptChain’s security inherently reduces to that of Bitcoin. Intuitively, our protocol optimizes block availability verification while strictly preserving Bitcoin’s underlying consensus layer. Consider a naive reduction: if nodes were required to download full transaction blocks to vote on their availability, each availability chain would directly mirror Bitcoin, and the aggregate of all availability chains would be equivalent to Manifoldchain. The proposer chain implements PVID, enabling nodes to verify block availability using only block fragments. Crucially, this does not alter Bitcoin’s core assumption: when an honest node receives a full block (verifying its availability), it broadcasts that block so every other honest node can also verify it within ∆. This assumption is also guaranteed by our PVID’s agreement property, as defined in Section III-B. Furthermore, the ordering chain solely establishes a global sequence across availability blocks to ensure crossshard atomicity, leaving the underlying consensus mechanics
10
shards, we set λo r = (λs + λi )S = λp . The values of λo and r are flexible; a larger r and smaller λo are preferred to reduce the forking rate. Step 6: confirmation depths k. The parameter k is selected to satisfy the constraint α′ > 12 in Theorem 2 and to minimize the error probability negl(k), determined by whichever condition is more stringent. Step 7: parameters for erasure code (v and d). As within each shard there are λs +λi availability blocks being confirmed per second, this indicates that every honest node has received the requested symbols of the corresponding transaction blocks, implying that (λs + λi ) · e · b · kd < C. Furthermore, since λ λt C C λs + λi = Sp = C T · e = eb , we set d ≥ C · k. Intuitively, the proposer chain’s mining rate reflects the speed at which the fastest node downloads the full transaction block of d symbols, while the availability chains’ rate reflects the speed at which the slowest node downloads any k of the d symbols. v is chosen as large as possible to minimize the error probability in Theorem 2. Proof Sketch. Under the parameter configuration described above, we bound the probability that at least one security property is violated by considering three distinct failure events: 1) Adversarial majority. The fraction of corrupted nodes (including deceived honest nodes) exceeds 50%. This occurs with probability σ1 = negl(k), as shown in Appendix C-B2. 2) Honest absence. Given n − f honest nodes and T /C shards, the probability that a specific shard transaction’s αn contains no honest nodes is σ2 = 1 − C , as derived T in Appendix E. 3) Chain property violation. One or more of the CP, CQ, or CG properties are violated. This occurs with probability σ3 = negl(k), as shown in Appendix C-B. Therefore, the total error probability σ is bounded by: αn C σ ≤ σ 1 + σ2 + σ3 = 1 − + negl(k). T
properties of PoW-based protocols defined in Appendix C-A: Common Prefix (CP), Chain Quality (CQ), and Chain Growth (CG). Based on these properties, honest nodes agree on a consistent and totally ordered log of block commitments. We then prove that OptChain also satisfies all properties of the VID scheme defined in Definition III-B, which ensures that all blocks committed in the log are available. Consequently, the agreed log effectively becomes a log of executable transactions once honest nodes retrieve the full blocks. Therefore, we conclude that our protocol satisfies both safety and liveness. The detailed proof is deferred to Appendix C. B. OptChain’s Throughput We present the upper bound of OptChain’s throughput as follows: Theorem 4. Given a maximum error probability of σ, the C throughput of OptChain is bounded by T = 1 . 1−(σ−negl(k)) αn
∗
As k → ∞, T → T . Given a target error probability σ, we demonstrate how to configure OptChain to closely approach the optimal throughput T ∗ established in Theorem 4. We provide a proof sketch demonstrating how this configuration achieves the claimed throughput and defer the detailed proof to Appendix E. Step 1: mining rate for transaction blocks (λt ). To achieve a throughput of T , we set λt · t = T . While the specific values of λt and t are flexible, preferring a larger t and smaller λt helps reduce the number of com entries per proposer block, resulting in smaller proposer block size. Step 2: number of shards (S). Since each shard contributes T at most C to the total throughput, we set S = C to ensure the availability property—guaranteeing that every incoming transaction per second can be downloaded by at least one honest node. Step 3: mining rate for proposer blocks (λp ). To embed the commitment of transaction blocks into the proposer chain, we set λp · e = λt , where e denotes the maximum number of transaction blocks referenced per proposer block. While the specific values of λp and e are flexible, a larger λp and smaller e are preferred to minimize the proportion of deceived honest nodes σ, as defined in Theorem 6. Accordingly, we choose λp as large as possible, subject to it being less than both λt and the upper bound specified in Theorem 2. Once λp is set, e is chosen to ensure λp · e = λt . Step 4: mining rates for availability blocks (λs and λi ). To λ keep pace with the proposer chain, we set λs + λi = Sp . We then choose λs and λi to satisfy the constraint in Theorem 2, iα which requires λsλα+Sλ > 12 EXP ((λs + λi )∆). As λs +λi is s +Sλi fixed, increasing λi raises the left-hand side but also increases the number of global availability blocks, resulting in higher communication overhead. Therefore, we choose λi as small as possible while still satisfying the constraint, and set λs = λp S − λi . Step 5: Mining rate for ordering blocks (λo ). Suppose each ordering block can reference up to r availability blocks. Since the ordering chain globally order availability blocks across
Solving for T , we derive the OptChain throughput C 1 , which matches the bound stated in Theo1−(σ−negl(k)) αn
rem 4. VII. E XPERIMENTS Testbed. We implemented a prototype of the OptChain client in 7, 000 lines of Rust code [14] and deployed it on Amazon Elastic Compute Cloud (EC2) to evaluate its performance in a realistic geo-distributed environment. We build a consensus network of 64 nodes, each node operates on an EC2 t3.medium instance equipped with 2 vCPU cores, 4GB of RAM, and a 20GB NVMe SSD. To ensure geographic diversity, these instances are distributed across four major regions: London, Virginia, Sao Paulo, and Tokyo. The transactions and all metadata (e.g., hashes and signatures) are implemented with the same data structures to ensure a fair comparison. Baselines. We compare OptChain against Manifoldchain [10] and Prism [4]. Manifoldchain represents the SOTA in sharding
11
protocols that offer a security level comparable to ours (i.e., 1/2 global fault tolerance). We exclude other permissionless sharding protocols, such as Elastico[7], Omniledger[8], and RapidChain[9], as their lower fault tolerance (typically < 1/3 or 1/4) precludes a fair direct comparison. Conversely, Prism represents the SOTA in non-sharding permissionless protocols. By benchmarking against both, we demonstrate that OptChain outperforms the leading protocols in both the sharding and non-sharding categories. To ensure a fair comparison (i.e., using the same P2P networking and transaction size), we emulate Prism by tuning OptChain’s parameters. Specifically, by setting the shard count to one and configuring nodes to request full transaction blocks rather than coded symbols for each com, OptChain functionally reduces to Prism (specifically, a variant without voter chains) and achieves the same throughput as the vanilla Prism protocol. For Manifoldchain, we deploy its opensourced implementation[22] on our testbed to ensure identical experimental configurations. We also compare OptChain with the theoretical optimal throughput. To account for the inherent bandwidth volatility of AWS EC2, we estimate the theoretical optimal throughput via an empirical micro-benchmark rather than static analysis. We use the tc command to set downlink bandwidths based on a real-world dataset [15], selectively sampling values between 10 Mbps and 80 Mbps. We then run iterative tests where a random sender broadcasts transactions to all receivers for one minute. We compute the average download transactions for each node across multiple iterations. The theoretical optimal throughput is calculated as the number of download transactions of the x highest-performing nodes per second, where x corresponds to the maximum shard count. Evaluation. In our first experiment, we evaluate OptChain’s maximum throughput under a fixed error probability and compare it against the baselines. Subsequently, to validate OptChain’s design for optimal horizontal and vertical scalability, we evaluate these two dimensions independently in the second and third experiments.
Fig. 4. Throughput comparison of OptChain against the theoretical optimum and state-of-the-art baselines across varying error probability thresholds. OptChain closely tracks the theoretical optimum, whereas Manifoldchain demonstrates substantially lower throughput. Prism appears as a single point because its non-sharding throughput is independent of the error threshold.
ing as the error threshold rises. In contrast, the Prism and Manifoldchain perform significantly worse. As detailed in the proof sketch in Section VI-B, the total error probability stems from three sources: adversarial majority, the absence of honest nodes in a shard, and chain property violations. The second source is the primary contributor, as the other two become negligible by increasing the confirmation depth k. Consequently, a higher error threshold enables OptChain, Manifoldchain, and the theoretical optimum to support more shards, boosting parallelism and throughput. Prism, being a non-sharding protocol, maintains nearly constant throughput regardless of the error threshold, appearing as a single point in the figure. OptChain achieves near-optimal performance by achieving both optimal vertical and horizontal scalability, as corroborated by the experimental results presented in Section VII-B and VII-C. As the error threshold increases, the gap between OptChain and the theoretical optimum widens. This divergence occurs because a higher error threshold enables the system to support more shards, which in turn increases the proportion of foreign transaction blocks. When nodes expend bandwidth downloading symbols for these foreign blocks, this consumption does not contribute to the throughput of their own shard. Therefore, the actual throughput increasingly deviates from the theoretical optimum. However, this deviation is mitigated as more nodes join the protocol, as the burden of storing symbols is distributed across a larger number of participants. Additionally, at low error thresholds, Prism outperforms Manifoldchain because Manifoldchain is limited by Bitcoin-like vertical scalability within each shard. However, as the error threshold increases, Manifoldchain surpasses Prism by leveraging its horizontal scalability, a capability that Prism lacks.
A. Throughput under Error Probabilities This experiment evaluates the throughput of OptChain across a range of maximum allowable error probabilities (error threshold), spanning from e−50 to e−2 . We deploy the system on 64 EC2 instances, each hosting a single node. Having demonstrated OptChain’s superior throughput in our 64-node evaluation, we defer its deployment in a large-scale permissionless network to future work. Consistent with our theoretical benchmark configuration, we emulate realistic network heterogeneity by limiting each node’s downlink bandwidth using the tc command. These bandwidth limits are assigned by uniformly sampling values between 10 Mbps and 80 Mbps from a real-world dataset [15]. For each error probability threshold, we optimize the parameters of both OptChain and the baselines to maximize their respective throughput. Figure 4 compares the throughput of OptChain against the theoretical optimum and the SOTA baselines (Manifoldchain and Prism) across varying error thresholds. The throughput of OptChain closely tracks the theoretical optimum, increas-
B. Vertical Scalability This experiment evaluates the vertical scalability of OptChain, assessing the system’s ability to leverage increased network bandwidth. We fix the network size at 64 nodes. For the sharding protocols (OptChain and Manifoldchain), we set the shard count to 4. Using the tc command, we configure the downlink bandwidth for all nodes, testing discrete values
12
Fig. 5. Vertical scalability analysis of OptChain under increasing network bandwidth. OptChain’s throughput closely tracks the theoretical optimum and significantly outperforms other baselines. While Prism initially lags behind Manifoldchain due to its lack of sharding, it eventually surpasses Manifoldchain at higher bandwidths due to better vertical scalability.
Fig. 6. Horizontal scalability evaluation of OptChain with an increasing number of nodes. OptChain closely tracks the theoretical optimum as the node count rises, while Manifoldchain exhibits significantly slower growth. Prism is excluded as it lacks horizontal scalability.
from the set {10, 30, 50, 70, 90} Mbps. For each bandwidth configuration, we optimize the parameters of both OptChain and the baselines to maximize their respective throughput. Fig. 5 evaluates the impact of node bandwidth on throughput. Consistent with previous results, OptChain exhibits performance close to the theoretical optimum, while the other baselines perform significantly worse. OptChain achieves this near-optimal vertical scalability by enabling nodes to reach consensus on compact transaction block digests. This design allows the fastest nodes to fully utilize their high bandwidth for downloading transaction blocks without being throttled by slower nodes, matching the throughput upper bound that any consensus protocol can achieve within a single shard. Additionally, at lower bandwidths, Prism achieves lower throughput than Manifoldchain; this is because Prism is non-sharding, whereas Manifoldchain operates with 4 shards. However, as bandwidth increases, Prism overtakes Manifoldchain because it possesses better vertical scalability than Manifoldchain, whose intra-shard consensus is limited by Bitcoin-like vertical scalability.
fusion mining to support as many shards as possible, thereby maximizing parallelism. Furthermore, because OptChain also maintains optimal vertical scalability, the incremental throughput contributed by new nodes is determined by the bandwidth of the fastest nodes. Conversely, with the same number of new nodes joining, Manifoldchain’s incremental throughput is throttled by the slowest node’s bandwidth. VIII. C ONCLUSION In this paper, we addressed the fundamental throughputsecurity trade-off that constrains existing permissionless SMR protocols. We established a theoretical upper bound for throughput in heterogeneous networks and identified two critical barriers to achieving optimality: the limitation of throughput by the slowest nodes (vertical scalability) and the constraints on the number of shards required for security (horizontal scalability). To overcome these challenges, we introduced OptChain, the first layer-1 permissionless sharding protocol designed to approach this theoretical optimum. OptChain leverages two key innovations: shardis, a novel permissionless verifiable information dispersal scheme that decouples consensus from data availability to enable vertical scaling consistent with the fastest nodes; and diffusion mining, a mechanism that maximizes horizontal scalability by aggregating honest hashing power across shards, ensuring security even with one honest presence per shard. Furthermore, we solved the cross-shard atomicity challenges introduced by our architecture through a global ordering chain and fraud proofs. We formally proved the security and throughput optimality of our design. Our extensive evaluation, deploying a prototype implementation on geo-distributed AWS EC2 nodes with realworld bandwidth traces, confirmed that OptChain significantly outperforms state-of-the-art protocols like Manifoldchain and Prism. Most importantly, our experimental results demonstrate that OptChain closely approaches the theoretical throughput bound in realistic settings, validating it as a promising direction for next-generation scalable blockchain systems.
C. Horizontal Scalability This experiment evaluates the horizontal scalability of OptChain, assessing the system’s performance as the number of nodes grows. We fix the maximum allowable error probability at e−6 and incrementally increase the number of participating nodes. Consistent with our previous methodology, each node is assigned a downlink bandwidth sampled from the real-world dataset. For each network size configuration, we optimize the parameters of OptChain and the remaining baselines to maximize their respective throughput. We exclude Prism from this evaluation, as it is a non-sharding protocol and inherently lacks horizontal scalability. Fig. 6 evaluates the horizontal scalability of the protocols by varying the number of nodes. OptChain’s throughput increases linearly as the network size grows, closely tracking the theoretical optimum and exhibiting optimal horizontal scalability. In contrast, while Manifoldchain also demonstrates horizontal scalability, its performance remains significantly lower. OptChain achieves this optimality by leveraging dif-
13
R EFERENCES [1] [2] [3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
Satoshi Nakamoto. 2008. Bitcoin: a peer-to-peer electronic cash system. Decentralized business review. Miguel Castro, Barbara Liskov, et al. 1999. Practical byzantine fault tolerance. In OsDI number 1999. Vol. 99, 173–186. Ittay Eyal, Adem Efe Gencer, Emin Gün Sirer, and Robbert van Renesse. 2016. Bitcoin-ng: A scalable blockchain protocol. In 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016, Santa Clara, CA, USA, March 16-18, 2016. Katerina J. Argyraki and Rebecca Isaacs, (Eds.) USENIX Association, 45–59. https://www.usenix.org/conference/nsdi16/technical-sessions/p resentation/eyal. Vivek Kumar Bagaria, Sreeram Kannan, David Tse, Giulia Fanti, and Pramod Viswanath. 2019. Prism: deconstructing the blockchain to approach physical limits. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS 2019, London, UK, November 11-15, 2019. Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, (Eds.) ACM, 585–602. https://doi.org/10.1145/3319535.3363213. Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan-Gueta, and Ittai Abraham. 2019. Hotstuff: BFT consensus with linearity and responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019. Peter Robinson and Faith Ellen, (Eds.) ACM, 347–356. doi:10.1145/3293611.3331591. Lei Yang, Seo Jin Park, Mohammad Alizadeh, Sreeram Kannan, and David Tse. 2022. Dispersedledger: high-throughput byzantine consensus on variable bandwidth networks. In 19th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2022, Renton, WA, USA, April 4-6, 2022. Amar Phanishayee and Vyas Sekar, (Eds.) USENIX Association, 493–512. https://www.usenix.org/conference/n sdi22/presentation/yang. Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert, and Prateek Saxena. 2016. A secure sharding protocol for open blockchains. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 2428, 2016. Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, (Eds.) ACM, 17–30. https://doi.o rg/10.1145/2976749.2978389. Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Ewa Syta, and Bryan Ford. 2018. Omniledger: A secure, scaleout, decentralized ledger via sharding. In 2018 IEEE Symposium on Security and Privacy, SP 2018, Proceedings, 21-23 May 2018, San Francisco, California, USA. IEEE Computer Society, 583–598. https: //doi.org/10.1109/SP.2018.000-5. Mahdi Zamani, Mahnush Movahedi, and Mariana Raykova. 2018. Rapidchain: scaling blockchain via full sharding. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada, October 15-19, 2018. David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, (Eds.) ACM, 931–948. https://doi.org/10.1145/3243734.3243853. Chunjiang Che, Songze Li, and Xuechao Wang. 2025. Manifoldchain: maximizing blockchain throughput via bandwidth-clustered sharding. In 32nd Annual Network and Distributed System Security Symposium, NDSS 2025, San Diego, California, USA, February 24-28, 2025. The Internet Society. https://www.ndss-symposium.org/ndss-paper/manifo ldchain-maximizing-blockchain-throughput-via-bandwidth-clusteredsharding/. Jiaping Wang and Hao Wang. 2019. Monoxide: scale out blockchains with asynchronous consensus zones. In 16th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2019, Boston, MA, February 26-28, 2019. Jay R. Lorch and Minlan Yu, (Eds.) USENIX Association, 95–112. https : / / www . usenix . org / conference /nsdi19/presentation/wang-jiaping. Jim Gray. 1978. Notes on data base operating systems. In Operating Systems, An Advanced Course (Lecture Notes in Computer Science). Michael J. Flynn, Jim Gray, Anita K. Jones, Klaus Lagally, Holger Opderbeck, Gerald J. Popek, Brian Randell, Jerome H. Saltzer, and Hans-Rüdiger Wiehle, (Eds.) Vol. 60. Springer, 393–481. doi:10.1007 /3-540-08755-9\ 9. Mustafa Al-Bassam, Alberto Sonnino, Vitalik Buterin, and Ismail Khoffi. 2021. Fraud and data availability proofs: detecting invalid blocks in light clients. In Financial Cryptography and Data Security
[14] [15]
[16] [17]
[18]
[19]
[20]
[21] [22] [23] [24]
[25] [26]
[27]
- 25th International Conference, FC 2021, Virtual Event, March 1-5, 2021, Revised Selected Papers, Part II (Lecture Notes in Computer Science). Nikita Borisov and Claudia Dı́az, (Eds.) Vol. 12675. Springer, 279–298. doi:10.1007/978-3-662-64331-0\ 15. Anonymous. 2026. OptChain Core. https://anonymous.4open.science /r/OptChain-6F98/README.md. (2026). Cortze and Yiannisbot. 2024. Bandwidth availability in ethereum: regional differences and network impacts. Accessed: 2026-01-11. Ethereum Research. (Dec. 2024). https : / / ethresear . ch / t / bandwidth availability-in-ethereum-regional-differences-and-network-impacts/2 1138. Benjamin Y Chan and Rafael Pass. 2023. Simplex consensus: a simple and fast consensus protocol. In Theory of Cryptography Conference. Springer, 452–479. Christian Cachin and Stefano Tessaro. 2005. Asynchronous verifiable information dispersal. In Distributed Computing, 19th International Conference, DISC 2005, Cracow, Poland, September 26-29, 2005, Proceedings (Lecture Notes in Computer Science). Pierre Fraigniaud, (Ed.) Vol. 3724. Springer, 503–504. doi:10.1007/11561927\ 42. Ben Fisch, Arthur Lazzaretti, Zeyu Liu, and Lei Yang. 2024. Permissionless verifiable information dispersal (data availability for bitcoin rollups). IACR Cryptol. ePrint Arch., 1299. https://eprint.iacr.org/202 4/1299. Mingchao Yu, Saeid Sahraei, Songze Li, Salman Avestimehr, Sreeram Kannan, and Pramod Viswanath. 2020. Coded merkle tree: solving data availability attacks in blockchains. In Financial Cryptography and Data Security - 24th International Conference, FC 2020, Kota Kinabalu, Malaysia, February 10-14, 2020 Revised Selected Papers (Lecture Notes in Computer Science). Joseph Bonneau and Nadia Heninger, (Eds.) Vol. 12059. Springer, 114–134. doi:10 . 1007 / 978 3-030-51280-4\ 8. Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. 2015. The bitcoin backbone protocol: analysis and applications. In Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part II (Lecture Notes in Computer Science). Elisabeth Oswald and Marc Fischlin, (Eds.) Vol. 9057. Springer, 281–310. doi:10.1007/978-3-662-46803-6\ 10. Dongning Guo and Ling Ren. 2022. Bitcoin’s latency–security analysis made simple. In Proceedings of the 4th ACM Conference on Advances in Financial Technologies, 244–253. Chunjiang Che. 2025. The implementation of manifolchain. https://gi thub.com/ChunjiangChe/Manifoldchain. (2025). Anonymous. 2025. OptChain AWS Development. https://anonymous .4open.science/r/OptChain AWS-1826/. (2025). Amir Dembo, Sreeram Kannan, Ertem Nusret Tas, David Tse, Pramod Viswanath, Xuechao Wang, and Ofer Zeitouni. 2020. Everything is a race and nakamoto always wins. In CCS ’20: 2020 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, USA, November 9-13, 2020. Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna, (Eds.) ACM, 859–878. doi:10.1145/3372297.34 17290. Janos Galambos. 1995. Advanced probability theory. Vol. 10. CRC Press. James Hendricks, Gregory R. Ganger, and Michael K. Reiter. 2007. Verifying distributed erasure-coded data. In Proceedings of the TwentySixth Annual ACM Symposium on Principles of Distributed Computing, PODC 2007, Portland, Oregon, USA, August 12-15, 2007. Indranil Gupta and Roger Wattenhofer, (Eds.) ACM, 139–146. doi:10.1145/12 81100.1281122. Kamilla Nazirkhanova, Joachim Neu, and David Tse. 2022. Information dispersal with provable retrievability for rollups. In Proceedings of the 4th ACM Conference on Advances in Financial Technologies, AFT 2022, Cambridge, MA, USA, September 19-21, 2022. Maurice Herlihy and Neha Narula, (Eds.) ACM, 180–197. doi:10.1145/3558535.35597 78.
A PPENDIX A A RTIFACTS To facilitate the double-blind review process and ensure reproducibility of the results presented in this paper, all artifacts—including the OptChain source code, deployment
14
scripts, and configuration files—have been anonymized and uploaded to a persistent repository. The artifact package allows reviewers to compile the OptChain client, run a local minimal working demo, and deploy the full experimental testbed on AWS. The package consists of the following components:
Pr(Y = j) =1 −
zi , n for all i ∈ {1, 2, . . . , T }, j ∈ {1, 2, . . . , n}. =
1) OptChain Core (Rust) [14]: The source code for OptChain, including the logic for the proposer, availability, and ordering chains, as well as networking and consensus modules. We provide detailed instructions for compiling and running an OptChain node locally. Furthermore, we include documentation on configuring protocol parameters and a quick-start script to launch a simple demonstration. 2) Cloud Deployment (Python/Bash) [23]: We build a Docker image based on our implementation to facilitate seamless deployment on remote servers, abstracting away system heterogeneity. We also provide a suite of scripts to initialize the environment and deploy the Docker container across multiple AWS EC2 instances simultaneously, automating Docker installation, bandwidth throttling, and experiment orchestration.
A PPENDIX C S ECURITY OF O PT C HAIN The ultimate goal is to prove that OptChain satisfies the safety and liveness properties defined in Section III-A. We establish this in two steps: (1) we prove that all chains (including the proposer chain, availability chains, and ordering chain) satisfy the CP, CQ, and CG properties, ensuring that honest nodes agree on an ordered log of block commitments; and (2) we prove that OptChain satisfies the security properties of the VID scheme defined in Definition III-B, ensuring that the log can be effectively converted into a log of available transactions. The outline of the proof is as follows: we present the formal definitions of the CP, CQ, and CG properties in Section C-A, and develop the first and second steps in Sections C-B and C-C, respectively. Finally, we conclude the proof of Theorem 2 in Section C-D.
We begin by showing how to measure the throughput of a SMR protocol. Definition 4 (Throughput). An SMR protocol Π achieves a throughput of T if, with negligible error probability, there exists a log maintained by some honest node such that: For any time t, let the log length be l at time t and l′ at time t + 1; then l′ − l ≥ T . • No violations of safety and liveness. •
We prove the theorem as follows: Proof. Suppose there exists an SMR protocol that confirms T transactions per second with an error probability σ < σ ∗ (T ). Assume that the entire network can download at most x transactions per second. Supposed the i-th P transaction appears T in zi copies across the network, where i=1 zi = x. On average, each transaction appears in at most Tx copies across the network, with each copy downloaded by one node. The corrupted nodes strictly follow the protocol, honest nodes cannot distinguish them from truly honest ones. Let X be the random variable denoting the node that downloads a specific copy of a transaction, i.e., X ∈ {1, 2, . . . , n}. Given that downloads are uniformly distributed, we have: 1 , n
for all j ∈ {1, 2, . . . , n}.
(6)
In this case, availability property is violated if all copies of a transaction are downloaded only by corrupted nodes. The probability of this event (i.e., that none of the αn honest nodes download any copy) is at least: αn min zi . (7) σ = 1− n The maximum value of min zi is achieved when every transaction has the same number of copies, so max{min zi } = Tx . Moreover, since x ≤ nC, it follows that: αn C σ ≥ 1− = σ ∗ (T ), (8) T which contradicts the assumption that σ < σ ∗ (T ). This completes the proof.
A PPENDIX B P ROOF OF T HEOREM 1
Pr(X = j) =
n−1n−2 n − zi ... n n−1 n − zi + 1
A. Security Properties We focus on a single Bitcoin blocktree and adopt the following notation from [20]: if C is a chain of blocks, then C ⌈k denotes the k-deep prefix of C, i.e., the chain obtained by removing the last k blocks from C. Additionally, given two chains C and C ′ , we write C ⪯ C ′ if C is a prefix of C ′ . Definition 5 (Common-prefix Property). The k-deep common prefix property holds if the k-deep prefix of the current longest chain remains a prefix of any longest chain at all future times. Definition 6 (Chain Quality Property). The (µ, k)-chain quality property holds if, among the last k consecutive blocks on the longest chain C, at most a µ fraction were mined by the adversary.
(5)
Now, let Y be the random variable indicating whether node j downloads the i-th transaction. Since there are at most zi copies of each transaction, each node has a probability of:
Definition 7 (Chain Growth Property). The chain growth property with parameters ϕ and s states that, over any interval of s rounds, at least ϕs blocks are added to the main chain.
15
honest nodes are treated as corrupted, there exists a sufficiently large k such that the fraction of undeceived honest nodes remains above 1/2. That is, the following condition holds: n − f − σ ≥ f + σ, which simplifies to n ≥ 2f + 2σ.
B. CP, CQ, CG of OptChain First, we leverage the proven security of Bitcoin [24] to show that the proposer chain satisfies these properties, as it functions as a standard Bitcoin chain. Second, we demonstrate that OptChain can be reduced to Manifoldchain except with negligible probability and derive the properties of all availability chains based on its results. Finally, using the established properties of the availability chains, we again rely on Bitcoin’s proven security to show that the ordering chain also satisfies these properties. 1) Security Properties of Proposer Chain: The proposer chain functions as a standard Bitcoin chain; thus, we can directly derive the following result from prior works [21, 24, 10]:
Proof. We consider an unavailable block with commitment com, where at most d−1 symbols are released to honest nodes. Suppose an honest node requests i symbols of the block. It considers the block available if and only if all of its requested symbols are among the d−1 released symbols. The probability of this event, denoted by γ(i), satisfies:
(11)
We have the following recurrence relation for the probability γ(i): d−i+1 d+1 γ(i) = < . (12) γ(i − 1) dv − i + 1 dv + 1
Theorem 5. The proposer chain satisfies the CQ, CP, and CG properties provided that 1 . 2 Furthermore, its chain growth parameter gp and chain quality parameter qp satisfy pp = αe−λp >
pp λp , 1 + p p λp ∆ 1 + pp (1 − α)∆λp qp = 1 − (1 + δ) , pp
d−i+1 d d−1 ... . dv dv − 1 dv − i + 1
γ(i) =
Therefore, by induction, we obtain the following upper bound: i 1 d+1 γ(i) < . (13) v dv + 1
gp = (1 − δ)
(9)
We say that an honest node is deceived if it considers at least one unavailable block to be available. For the latest confirmed proposer block (followed by exactly k blocks), the node requests k symbols. For the second-latest confirmed proposer block (followed by k + 1 blocks), it requests k + 1 symbols, and so on. Therefore, the probability that the node is deceived is given by:
except with probability negl(δ). 2) Security Properties of Availability Chains: The availability chains can be reduced to Manifoldchain with the following variations: • A malicious block producer may release only a subset of symbols to deceive some honest nodes into voting for an unavailable block, resulting in a reduced effective honest ratio α′ < α. • Availability blocks do not carry transactions, leading to a lower bounded network delay ∆ compared to the typical delay ∆ in Manifoldchain. The following theorem shows that our protocol reduces the fraction of deceived honest nodes to a negligible level, yielding α′ ≈ α. Using the updated parameters α′ and ∆, we derive the properties of the availability chains based on Manifoldchain’s results.
∞ X
γ(i) <
i=k
i ∞ X 1 d+1 i=k
1 = v P∞ d+1 i i=0
dv+1 a converges to 1−r
v
dv + 1 k X i ∞ d+1 d+1 . dv + 1 dv + 1 i=0
is a geometric series when |r| < 1, so
P∞
k=0 ar
k X i ∞ 1 d+1 d+1 γ(i) < v dv + 1 dv + 1 i=0 i=k k−1 d+1 d+1 = . dv + 1 dv(v − 1)
(14)
k
, and it
∞ X
Theorem 6 (Block Availability Consistency). Given a (vd, d)erasure code used in the CMT and a confirmation depth k in the proposer chain, the probability that a node receives all requested symbols of any unavailable transaction block is bounded by k 1 1 σ =e· · , (10) v v−1
(15)
When d → ∞, it approaches ∞ X
in the limit as d → ∞.
i=k
k 1 1 . γ(i) < v v−1
(16)
In the context of OptChain, each node requests k symbols for each of the e block commitments in a proposer block. Therefore, the final probability is given by:
This probability corresponds to the fraction of deceived nodes among honest nodes. It decreases exponentially with k, implying that for any n and f = βn, even if the deceived
16
except with probability negl(δ). γ=e
∞ X i=k
k 1 1 . γ(i) < e v v−1
C. VID Properties of OptChain
(17)
We present the followint theorem and prove it subsequently: Theorem 9. If the CP, CQ, and CG properties hold for the proposer chain, ordering chain, and all availability chains, then OptChain satisfies all the properties of a VID scheme.
To reduce OptChain to Manifoldchain, we introduce the following modifications: 1) Effective honest ratio: all deceived honest nodes are treated as corrupted nodes, while the remaining honest nodes are referred to as effective honest nodes, with a ratio of α′ = α(1 − γ). 2) Network delay of availability blocks: the network delay of an availability block is replaced by ∆, which satisfies: • If an effective honest node receives and accepts an availability block at time t, then all effective honest nodes will receive and accept that block by t + ∆. • If an effective honest node rejects an availability block, then all effective honest nodes will also reject that block. Subsequently, we present the following theorem based on Manifoldchain’s security:
Proof. We prove each property separately. • (Termination.) After invoking D ISPERSE (Bt ), the block proposer broadcasts its com to all nodes. By the CQ and CG properties of the proposer chain, it will eventually be confirmed, returning D ISPERSE(Bt )= com. Furthermore, by the CP properties of all availability chains and the ordering chain, every honest node will eventually confirm it in the ordering chain and output V ERIFY ( COM ) = 1. • (Agreement.) According to the CP property of the ordering chain, if any honest node confirms a com (outputs V ERIFY ( COM ) = 1), then all honest nodes will do the same by t + ∆. • (Retrievability.) If an honest node outputs V ER IFY (com) = 1 at time t, then by agreement, every honest node will output V ERIFY(com) = 1 by time t + ∆. This implies that each honest node has received u symbols of the block, resulting in a total of (n − f )u randomly sampled symbols across all honest nodes. Among these, at least u′ = (n − f )u − log2 ((n − f )u) are distinct with high probability. By choosing u such that u′ > d, a sufficient number of symbols is available to decode the CMT and reconstruct a block b′ . • (Correctness.) By the soundness of the CMT, any two honest nodes that output V ERIFY(com) = 1 will retrieve the same block. If com was generated by an honest node via D ISPERSE(b), then com is the root of the CMT constructed from b. Through decoding, every honest node will reconstruct a block b′ that is identical to b.
Theorem 7. All the availability chains satisfy CP, CQ, and CG properties as long as pa =
λs α + Sλi α′ −(λs +λi )∆ 1 > , e λs + Sλi 2
where α = α′ − log2 (α′ ). Furthermore, the chain growth parameter ga and chain quality parameter qa satisfy pa (λs + λi ) , 1 + pa (λs + λi )∆ 1 + pa (1 − α)∆(λs + λi ) qa = 1 − (1 + δ) , pa
ga = (1 − δ)
(18)
except with probability negl(δ). 3) Security Properties of Ordering Chain: An honest node accepts an ordering block only if it includes references to confirmed availability blocks that all honest nodes have already received and accepted locally. Therefore, the network delay for an ordering block depends solely on its size, which is bounded by ∆. Similar to Theorem 5, we can derive the security properties of the ordering chain by applying the results of prior work [24]:
D. Proof of Theorem 2 and Theorem 3 We first prove the following lemma: Lemma 1. Assume the honest majority condition. Let g and q be the chain growth rate and chain quality proportion for a chain. Any valid transaction tx submitted at t will be . confirmed by t + u, where u = k+⌈1/q⌉ g Proof. During the time interval [t, t+u], the chain grows by at least g · u = k + ⌈1/q⌉ blocks, according to the chain growth property. Of these newly generated blocks, the most recent k blocks serve as the persistence buffer. This pushes at least ℓ = ⌈1/q⌉ newly mined blocks deep enough into the chain to become part of the stable prefix (i.e., buried by at least k blocks), making them confirmed. By the chain quality property, any sequence of ℓ blocks is guaranteed to contain at least q · ℓ ≥ 1 honest block. Because honest miners strictly follow the protocol by including valid pending transactions, and adversaries cannot forge conflicting
Theorem 8. The ordering chain satisfies the CQ, CP, and CG properties provided that 1 po = αe−λo > . 2 Furthermore, its chain growth parameter go and chain quality parameter qo satisfy po λo , 1 + p o λo ∆ 1 + po (1 − α)∆λo , qo = 1 − (1 + δ) po
go = (1 − δ)
(19)
17
transactions to invalidate tx, this honest block must contain the transaction tx submitted at t. Therefore, tx is permanently recorded and confirmed by time t + u.
A PPENDIX E O PT C HAIN ’ S T HROUGHPUT OptChain requires each shard to contain at least one honest node to ensure security. We first present a lemma used to calculate the probability that this condition is violated, which serves as the primary source of error probability in our protocol.
Now we prove OptChain’s safety and liveness. Proof. Combining Theorems 5, 7, 8, and 9, we show that OptChain satisfies both safety and liveness: Safety: Honest nodes retrieve and execute transaction blocks belonging to their shards once their commitments are confirmed in the ordering chain. Thus, all honest nodes in the same shard retrieve the same transaction blocks confirmed at identical positions. If two honest nodes in the same shard were to execute different transaction sequences, the correctness of the VID scheme would imply different commitments confirmed at the same position in the ordering chain, contradicting the CP property. Liveness: If an honest client submits a transaction tx at time t, all honest nodes receive it by t + ∆. An honest node will include tx in a transaction block Bt if it belongs to its shard; otherwise, it forwards tx to the appropriate shard for packaging. By Lemma 1, Bt is confirmed in the proposer k+⌈1/q ⌉ chain by t+∆+ gp p . Accounting for network delay, Bt is
Lemma 2. Given n honest nodes randomly distributed into m shards, for any shard, the probability ε(n) there is no honest 1 n ) . nodes is bounded by (1 − m Proof. The distribution of n nodes into m shards satisfies a Multinomial Distribution[25]. Specifically, it models the probability of counts for each side of a m-sided dice rolled n times. For n independent trials each of which leads to a success for exactly one of m categories, with each category having a given fixed success probability, the multinomial distribution gives the probability of any particular combination of numbers of successes for the various categories. Mathematically, for each independent trial, we have m possible mutually exclusive outcomes, with corresponding probabilities p0 , ..., pm−1 . 1 = p. Given a random distribution, p0 = p1 = ... = pm−1 = m The probability mass function of this multinomial distribution is:
k+⌈1/q ⌉
confirmed by all honest nodes by t+ gp p +2∆. All honest nodes then request the corresponding symbols, receiving them k+⌈1/qp ⌉ optimistically by t + + 4∆. Similarly, by Lemma 1, gp Bt is confirmed in the availability chain by t +
f (x0 , ..., xm−1 ;n, p) = P r[X0 = x0 , ..., Xm = xm ] n! = px0 × ... × pxm−1 , (20) x0 ! · ... · xm−1 ! n! pn , = x0 ! · ... · xm−1 ! Pm−1 where i=0 xi = n. The probability that there is no one honest node in shard i is denoted as follows:
k+⌈1/qp ⌉ + gp
k+⌈1/qa ⌉ + 4∆. This confirmation becomes consistent across ga k+⌈1/qp ⌉ a⌉ all honest nodes by t + + k+⌈1/q + 5∆. Subgp ga
sequently, honest nodes mine ordering blocks that reference confirmed availability blocks. As a P result, the availability block x⌉ containing Bt is confirmed by t + x∈{p,a,o} k+⌈1/q + 5∆. gx Therefore, any transaction submitted at time t is fully conP k+⌈1/qx ⌉ + 5∆. firmed by t + u, where u = x∈{p,a,o} gx
X
P r[x0 ≥ 0, . . . xi = 0, ..., xm−1 ≥ 0]
x\{xi }
A PPENDIX D C ROSS - SHARD T RANSACTION ATOMICITY Proof. We sequentially verify that each condition of crossshard atomicity outlined in Definition 2 is satisfied. • If all withdrawal-txs are confirmed, honest nodes will accept every valid deposit-tx. By the liveness property of OptChain, all deposit-txs will eventually be confirmed. • If any deposit-tx is confirmed, the safety property of OptChain ensures that all honest nodes have accepted it; this implies that all corresponding withdrawal-txs appear before the deposit-tx on the ordering chain. Since the deposit-tx is confirmed, all preceding withdrawaltxs (which are at a greater depth) are implicitly confirmed. Following the logic of the first case, all remaining deposit-txs will eventually be confirmed. • If the cross-tx is initiated by an honest user, the liveness of OptChain guarantees that all withdrawal-txs are eventually confirmed. Consequently, as established above, all deposit-txs will eventually be confirmed.
=
X
n! pn x0 ! · ... · 0! · ... · xm−1 !
x\{xi } n X
p = ′n p
x\{xi }
(21)
n! n p′ , x0 ! · ... · xm−2 ! n
1 n! where p′ = m−1 , x0 !·...·x p′ represents the probability m−2 mass function of another multinomial distribution where n nodes are randomly distributed into m − 1 shards. Given X n! n p′ = 1, (22) x ! · ... · x x\{xi }
0
m−2
we have X
P r[x0 ≥ 0, . . . xi = 0, ..., xn−1 ≥ 0]
x\{xi }
=
18
1 m 1 m−1
!n
=
1 1− m
(23)
n .
blocks, is broadcast to all nodes, resulting in a communication complexity of n(|Bh | + |avai com set|). Hence, the amortized communication cost per transac 1 tion block is n |B | + h e (|Bh | + |avai com set|) = n 1 + 1e |Bh | = O(n). For symbol sampling, each inshard node requests k symbols and each out-shard node requests u symbols perblock, yielding a total communication overhead of Sn · kd · O(b) + 1 − Sn · ud · O(b). Given that the ensures αn S · k = O(d) coding scheme αn d and 1 − S · u = O( α ), the overall communication complexity for sampling is O(b), resulting in a total of O(n + αd ). In conclusion, the total communication complexity is O(n+ b d ), and the per-node communication complexity is O αn , α sublinear in the block size.
We then prove the Theorem 4. Proof. Following the parameter setting in Section VI-B, we first calculate the error probability that, for a transaction proposed by an honest node, at least one security property is violated. A violation occurs if any of the following events happens: 1) Adversarial majority. The fraction of corrupted nodes plus deceived honest nodes exceeds 50%, with probability σ1 = negl(k). 2) Honest absence. Given that there are n − f honest nodes T shards, the probability that a transaction’s shard and C αn contains no honest node is σ2 = 1 − C . T 3) Chain properties violation. One or more of the CP, CQ, or CG properties of the proposer chain or its affiliated availability chain is violated, with probability σ3 = negl(k). Thus, the total error probability is αn C + negl(k). σ = σ 1 + σ 2 + σ3 = 1 − T By backward reasoning, we can derive the optimal throughput C 1 , which matches the throughput bound stated 1−(σ−negl(k)) αn
in Theorem 4. A PPENDIX F C OMMUNICATION C OMPLEXITY In this section, we analyze the communication cost of our protocol in the case where transaction block reconstruction is not required, as in prior VID works [17, 26, 27, 6]. If reconstruction were required for every node, then the communication cost per node would be information-theoretically Ω(b). We measure the size of a block body Bb as O(b), and a block header Bh as O(1). We define the communication complexity of a VID protocol as the total size of all messages required to complete D ISPERSE and V ERIFY = 1 for a transaction block proposed by an honest node. Specifically, we analyze the communication cost of D ISPERSE and V ERIFY separately, as they correspond to the mining of the proposer chain and the availability chain, respectively. • Proposer chain (D ISPERSE (Bt )). When an honest node mines a transaction block, it broadcasts the block header Bh to all nodes, incurring a communication cost of n · |Bh |. Additionally, a proposer block of size |Bh | + |prop com set|, which includes the com(s) of e transaction blocks, is broadcast to all nodes, adding n(|Bh | + |prop com set|) to the total cost. Thus, the amortized communication complexity per transac 1 tion block is n |B | + (|B | + |prop com set|) = h h e n 1 + 1e |Bh | = O(n). • Availability chain (V ERIFY ( COM )). Similar to a proposer block, an availability block of size |Bh | + |avai com set|, containing the com(s) of e transaction
19