QuarkShard: Decomposing Cross-Shard Requests into Single-Input Transactions

Q UARK S HARD: Decomposing Cross-Shard Requests into Single-Input Transactions

arXiv:2610.23014v1 [cs.DC] 16 Oct 2026

Changyu Duan Tsinghua University

Zhixuan Fang Tsinghua University

Abstract

protocol to process all transactions across the network. In contrast, sharding partitions both the blockchain state and the transaction execution process across multiple shards. Each shard is maintained by a subset of replicas and processes only a fraction of the system workload, thereby significantly reducing the per-replica load. By enabling horizontal scaling, sharding allows throughput to scale dynamically as more nodes and shards join the system. A central challenge in sharding blockchains is how to process user requests that access state across multiple shards without compromising security or scalability. In sharding blockchains, each shard maintains only part of the global state, such as a subset of account balances. Therefore, a user may intend to draw funds from multiple shards and pay accounts located in multiple destination shards. Prior studies have shown that such cross-shard payments can dominate the workload: when the system has 16 shards, more than 99% of requests would access multiple shards [34]. For clarity, we use request for the user’s payment intent and transaction for the object processed by the sharding blockchain protocol in this work.1 To process a cross-shard user request, existing works typically require coordinating the involved shards to reach consensus on and execute the request according to specific rules. Ultimately, this coordination must guarantee request atomicity: the request should either take effect on all involved shards, or leave the system as if the request had not been executed. Specifically, the execution of a cross-shard request can be decomposed into two main components: intra-shard consensus and cross-shard communication. Generally, sharding blockchains run a Byzantine Fault Tolerance (BFT) protocol within each shard to process and reach consensus on transactions. Processing each transaction incurs corresponding communication, computation, and storage overheads, which we collectively refer to as the intra-shard consensus overhead (IS-overhead). Many current protocols

Sharding blockchains enhance scalability by distributing the workload across multiple shards. Within sharding blockchains, securely and efficiently processing cross-shard user requests remains a pivotal challenge. Traditional sharding blockchain protocols execute cross-shard requests under a processing paradigm that treats each user request as a monolithic entity to preserve its atomicity, inherently introducing significant intra-shard BFT execution overhead and cross-shard communication overhead. We propose Q UARK S HARD, a sharding protocol that breaks away from this traditional paradigm to achieve intrashard and cross-shard overheads below the lower bounds imposed by conventional approaches. Q UARK S HARD decomposes cross-shard requests into single-input-shard transactions, where each transaction requires consensus and processing within only a single shard, thereby substantially reducing total request processing overhead. Meanwhile, through a carefully designed request decomposition algorithm, Q UARK S HARD guarantees fund atomicity or location atomicity during request execution. Q UARK S HARD also enhances the security of blockchain sharding systems against MEV attacks and flooding attacks. Empirical evaluation across a widearea network spanning four AWS regions demonstrates that Q UARK S HARD achieves superior performance, attaining a peak throughput of 1024 k requests per second with sub-4second latency. Benchmark comparisons show that Q UARK S HARD achieves up to 210.7% and 314.8% of the maximum throughputs of Kronos and 2PC, respectively.

1

Introduction

As blockchain technology continues to evolve, enhancing scalability has become an important challenge. Among various solutions, sharding architectures are widely regarded as an effective approach [3,7,9,13,17,19–21,30,34] and have been implemented in multiple industrial-grade systems [1, 2, 28]. In traditional blockchains, every replica must store the complete blockchain state and participate in a global consensus

1 Prior work often uses transaction-related terminology for both notions; we separate them because Q UARK S HARD deliberately decouples user requests from the transactions processed by the sharding blockchain protocol.

1

rely on two-phase commit (2PC) based schemes [3, 7, 9, 19], incurring an IS-overhead of (2a + b)B or larger for a request involving a input shards and b output shards, where B denotes the intra-shard BFT execution cost required to process a single transaction. State-of-the-art general cross-shard protocols, such as Kronos [20] and Logos [21], reduce this overhead to (a + b)B . To synchronize execution results across multiple shards, shards must transmit cryptographic certificates to one another, incurring what we term cross-shard communication overhead (CS-overhead). Existing protocols [3,7,9] typically require allto-all inter-shard broadcasting to guarantee message reachability, introducing a CS-overhead of O(n2 rλ), where n denotes the number of replicas per shard, r represents the number of transactions in a batch, and λ is cryptographic parameter size. Kronos [20] reduces this overhead to O(nrλ) by leveraging erasure codes [22]. Logos [21] further lowers the pure crossshard communication overhead to O(rλ) by offloading most of the communication into intra-shard messaging (though the total communication overhead remains O(nrλ)). These traditional cross-shard protocols share a common processing paradigm: the protocol treats each user request as a monolithic entity for consensus and execution, directly guaranteeing its atomicity through protocol-level mechanisms. However, this paradigm imposes inherent overheads. Prior work has proven that the intra-shard consensus overhead cannot fall below (a + b)B [20, 21], as each involved shard must execute at least one consensus round for the request. Similarly, because a certificate must be broadcast to recipient shards for every request, the lower bound for the total communication overhead remains Ω(nrλ), and the lower bound for the CS-overhead is Ω(rλ) [21]. These lower bounds motivate us to reconsider a fundamental question: Is treating each user request as an indivisible entity strictly necessary? The answer is negative. We propose Q UARK S HARD, which splits each cross-shard user request into finer-grained pieces, where each piece is a transaction with a unique input shard, termed a Quark transaction. The protocol no longer reaches consensus on monolithic user requests; instead, it processes only Quark transactions, while request-level atomicity is guaranteed via a carefully designed request splitting algorithm. Through this decomposition, Q UARK S HARD bypasses the theoretical lower bounds of traditional paradigms, achieving significantly lower intra-shard and cross-shard overheads. Specifically, in Q UARK S HARD, the system exclusively executes Quark transactions. Each Quark transaction debits balances from only a single shard, although it may generate credits for other shards. Because a Quark transaction has a unique input shard, its validity can be determined solely by that shard. Consequently, processing a Quark transaction requires consensus only within its input shard; output shards do not need to execute an additional consensus round for the original transaction. Instead, output shards simply trust the

User req

ok

BFT Import

BFT Import Import

Figure 1: Q UARK S HARD Workflow. The user executes a single Quark transaction per input shard to fully process the request, incurring an IS-overhead of merely aB . For any Quark transaction, its generated outputs are imported by the target destination shards with negligible overhead (depicted as gray blocks), eliminating the need for an additional BFT consensus round on the original request. User req

ok

req

ok

BFT

BFT

BFT

BFT

BFT

BFT

BFT

BFT

BFT

BFT

Figure 2: 2PC (left) and Kronos (right) Workflow. 2PC first executes BFT consensus across all input shards to lock the required inputs; upon successful locking, it executes consensus across all input or output shards to commit input deductions or credit output balances, incurring an IS-overhead of (2a + b)B . Kronos first executes BFT consensus across all input shards to consume the inputs; upon success, it executes consensus across all output shards to apply the outputs, incurring an IS-overhead of (a + b)B .

consensus result of the input shard and import the balance increments of the output accounts with minimal overhead. To execute a cross-shard request, the user divides it into a sequence of Quark transactions. We refer to this process as user request compilation. A carefully designed compilation algorithm guarantees the request’s fund atomicity: either the request executes entirely, or all funds remain under the control of their original account holders. Furthermore, honest users can achieve a stronger guarantee, location atomicity, which eliminates any side effects of request execution on funds controlled by honest accounts. As an example (Figure 1), consider a user holding inputs in shards S1 and S2 who wishes to pay recipient accounts in S3 and S4 . The base compilation algorithm (Algorithm 2) first issues a Quark transaction to transfer the inputs in S1 to the same account in S2 . Subsequently, it issues another Quark transaction from S2 that transfers all gathered inputs to the target accounts in S3 and S4 . On the success path, the base 2

Table 1: Comparison of Q UARK S HARD and BFT-based Sharding Blockchain Systems. Protocol

IS-Overhead†

OmniLedger [17] RapidChain [34] Chainspace [3] ByShard [9] AHL [7] Kronos [20] Logos [21]

valid Request (a + b)B (a + b)B ⋄ (2a + b)B (2(a + b) − 1)B (2(a + b) + 3)B (a + b)B (a + b)B

Q UARK S HARD

aB

invalid Request 2aB xB ⋄ 2aB (2x + 1)B (2(a + b) + 3)B 2xB aC xB (x + 1[x > 0])B §

CS-Overhead‡ (for r transactions)

CS Front-Running Free◦

Order-Fairness BFT Compatible⋆

O(n2 rλ) O(n2 rλ) O(n2 rλ) O(n2 rλ) O(n2 rλ) O(nrλ) O(rλ) O(ncλ) O(cλ)§

✘ ✘ ✘ ✘ ✘ ✘ ✘

✘ ✘ ✘ ✘ ✘ ✘ ✘

✔

✔

✔ and ✘ denote that a property is satisfied and not satisfied, respectively. † a and b: the numbers of input and output shards for a request. B : the BFT execution cost for a single transaction. x (< a): the number of input shards that have consumed or locked funds prior to the rejection of an invalid request. ‡ r: the number of transactions in a batch. c: the number of output accounts involved in these transactions. λ: the cryptographic parameter size. This column indicates the communication overhead required to guarantee that every honest node in the destination shard eventually receives the identical, reliably delivered data [21]. ◦ CS Front-Running Free indicates whether the cross-shard request processing scheme eliminates time windows in which an adversary can observe transaction intent in advance and perform front-running using intra-shard transactions (Definition 5.1). ⋆ Order-Fairness BFT Compatible indicates whether the system is compatible with non-sharding Order-Fairness BFT consensus protocols (Definition 5.2). ⋄ RapidChain only supports single-destination output requests (b = 1) and does not support all-or-nothing atomicity. The term xB represents its overhead for invalid requests when achieving fund atomicity analogous to that defined in this paper. § The terms xB and (x + 1[x > 0])B represent the IS-overhead under fund atomicity and location atomicity, respectively. 1[x > 0] is the indicator function that equals 1 if x > 0 and 0 otherwise. The term O(cλ) represents the reduced overhead when employing a Logos-based optimization scheme [21].

compilation algorithm commits one Quark transaction per input shard, incurring an IS-overhead of aB . For comparison, the execution workflows of 2PC and Kronos for processing this request are illustrated in Figure 2. Regarding CS-overhead, Q UARK S HARD requires a shard to broadcast the cross-shard outputs of Quark transactions to the target shards. However, the cross-shard effects of a large volume of transactions can be aggregated by account. Through this mechanism, Q UARK S HARD reduces the CSoverhead of r Quark transactions to O(ncλ), where c represents the number of distinct destination accounts in distinct shards across these r transactions. By incorporating the crossshard communication optimization from Logos [21], the CSoverhead can be further lowered to O(cλ). The design of Q UARK S HARD not only reduces the overhead of processing cross-shard requests, but also enhances the security and robustness of sharding blockchain systems. In blockchain environments, adversaries can exploit transaction ordering to extract Maximal Extractable Value (MEV) at honest users’ expense [6, 26]. sharding blockchains are particularly susceptible to these attacks [35]. Q UARK S HARD mitigates the impact of MEV attacks on sharding blockchains at two distinct levels. First, in traditional cross-shard protocols, a cross-shard request must reach consensus in the input shards before undergoing consensus in the output shards. This sequential workflow inherently imposes higher latency on cross-shard requests compared to intra-shard transactions, expanding the exposure to front-running attacks. An attacker observing a published cross-shard request during its processing in the input shard can issue a front-running intra-shard transaction in the out-

put shard, executing it before the cross-shard request completes [35]. In Q UARK S HARD, a user’s cross-shard request is never publicly broadcast as a monolithic intent. Consequently, when an adversary observes a user transferring funds from one shard to another, they cannot ascertain what subsequent transaction, if any, the user will initiate. This effectively closes the extra front-running attack window caused by latency disparities between cross-shard and intra-shard execution. Second, in traditional cross-shard protocols, achieving order-fairness across all requests requires additional crossshard ordering mechanisms due to multi-shard involvement [12, 35]. In contrast, each shard in Q UARK S HARD processes only the Quark transactions without having to coordinate with other shards, the intra-shard consensus can directly employ standard order-fairness protocols designed for nonsharding blockchains [15, 16] and ensuring fair ordering for all Quark transactions in the same shard. It is worth noting that Q UARK S HARD does not eliminate MEV entirely; rather, it shrinks the MEV attack surface introduced by sharding and offers superior compatibility with conventional anti-MEV mechanisms. Existing work indicates that sharding blockchains are more vulnerable to flooding attacks compared to non-sharding systems [21]. In most 2PC-based protocols and Kronos, a failed cross-shard request incurs a wasted IS-overhead of at least 2xB , where x is the number of input shards that have consumed or locked funds prior to the rejection of the invalid request. As a result, an adversary can exhaust system resources by flooding the system with invalid cross-shard requests. Logos mitigates this by decoupling the broadcast and agreement phases of consensus, allowing invalid requests to fail early 3

during the broadcast phase and reducing the wasted overhead to aC , where C denotes the cost of broadcasting a transaction in consensus.2 In Q UARK S HARD, an invalid request incurs an overhead of xB when relying on fund atomicity. If location atomicity is required, an additional refund transaction is executed, resulting in an overhead of (x + 1[x > 0])B . In scenarios where broadcast bandwidth is the primary bottleneck, Q UARK S HARD can achieve lower practical overhead than Logos. A comparison between Q UARK S HARD and existing sharding blockchain architectures is presented in Table 1. Our contributions are summarized as follows:

satisfying n ≥ 3 f + 1.3 A shard Si maintains a local chain Ci = (B0i , B1i , . . .) and a replicated account state. In blockchain systems, common account models include the account-balance model [31] and the Unspent Transaction Output (UTXO) model [25]. For simplicity, this paper adopts the account-balance model, although Q UARK S HARD is equally applicable to the UTXO model. An account is uniquely identified by its cryptographic public key pk and may hold balances across multiple shards. Let bali (pk) denote the balance of account pk recorded in shard Si .

• We propose Q UARK S HARD, which breaks away from the traditional cross-shard request processing paradigm that treats each user request as a monolithic entity. By compiling and decomposing a cross-shard user request into a sequence of single-input-shard Quark transactions, Q UARK S HARD achieves an IS-overhead of O(aB ) and an optimal CSoverhead of O(cλ), both below the theoretical lower bounds imposed by the traditional paradigm. Meanwhile, Q UARK S HARD enhances the security of sharding blockchain systems in aspects such as resistance to MEV and flood attacks.

2.2

A user request represents a payment intent whose inputs and outputs may span multiple shards. Definition 2.1 (User request). A user request req is defined as a tuple ⟨I, O⟩, where I is a set of inputs and O is a set of outputs. Each input or output is denoted as ⟨pk, v, Si ⟩, which specifies an account pk, an amount v, and the shard Si where the corresponding balance is or should be recorded.

• We present a carefully designed request compilation algorithm that decomposes a cross-shard request into multiple Quark transactions. The base algorithm guarantees fund atomicity, and its IS-overhead on the success path is aB . Furthermore, a refund algorithm ensures location atomicity for honest users.

A request is considered well-formed if the sum of its input values equals the sum of its output values, and the users authorize every input. Q UARK S HARD does not directly process user requests; instead, it executes Quark transactions. Definition 2.2 (Quark transaction). A transaction tx is defined as a Quark transaction of input shard Si if all balances it debits are recorded in Si . Quark transactions have the form ⟨I, O, nonce, sig⟩, where I is a set of inputs and O is a set of outputs, nonce is a unique identifier for the transaction, and sig is a set of signatures for the transaction of the input accounts. All inputs of a Quark transaction must belong to the same shard, while its outputs may belong to any shard.

• We implemented a prototype of Q UARK S HARD and evaluated its performance on an empirical wide-area network (WAN) spanning four AWS regions, benchmarking it against 2PC and Kronos. Experimental results demonstrate that Q UARK S HARD exhibits exceptional performance, achieving a peak throughput of 1024 k requests per second across 96 nodes and 24 shards while consistently maintaining sub-4-second latency. Compared to Kronos and 2PC, Q UARK S HARD achieves up to 210.7% and 314.8% of their maximum throughputs, respectively.

2

User Requests and Quark Transactions

A Quark transaction is considered valid in shard Si if all inputs are in Si and enough, the sum of its input values equals the sum of its output values, the nonce is unique, and all signatures in sig are valid for the corresponding input accounts. To process a cross-shard request, a user compiles it into multiple Quark transactions and submits them sequentially to their respective shards.

Preliminaries

This section defines the sharding blockchain model, the user requests and Quark transactions, the building blocks of Q UARK S HARD, and the network and adversary model.

The system consists of m shards, S = {S1 , . . . , Sm }. Each shard consists of n replicas, among which at most f are Byzantine,

Definition 2.3 (Request compilation algorithm). A request compilation algorithm is a procedure that takes a well-formed user request as input, decomposes it into a sequence of Quark transactions, and submits them to their respective shards according to prescribed rules and ordering constraints.

2 Although Logos claims an overhead of xC , its algorithm and security proof explicitly require all input shards to execute csdRBC, rather than only valid input shards; hence, the actual overhead is aC .

3We assume the existence of committee assignment and reconfiguration mechanisms that ensure each shard satisfies this requirement throughout system execution with overwhelming probability [17, 23, 34].

2.1

Sharding Blockchain Model

4

2.3

BFT Protocol

• Liveness. Blocks are continuously committed, with at least a fixed fraction of them being proposed by honest nodes.

CSRD primitive used to construct Q UARK S HARD. All messages are transmitted over authenticated channels, and eventual message delivery is guaranteed. In an asynchronous network, message propagation delays can be arbitrarily large. In a partially synchronous network, there exists a Global Stabilization Time (GST) such that, after GST, all messages transmitted between honest nodes are guaranteed to be delivered within a known bounded delay. The adversary may corrupt and fully control up to f < n/3 replicas per shard, causing them to arbitrarily deviate from the protocol. Subject to the constraints of the network model, the adversary can arbitrarily delay or reorder messages, but cannot forge or suppress messages sent by other replicas.

2.4

3

Each shard uses a BFT protocol to commit a totally ordered sequence of blocks. The BFT protocol must satisfy the following properties if at most f < n/3 replicas are Byzantine: • Agreement. Honest replicas never commit different blocks at the same height. • Validity. A committed block satisfies the shard’s deterministic block-validity predicate.

Cross-Shard Reliable Delivery

Q UARK S HARD requires reliable delivery of intra-shard consensus results from one shard to all honest nodes in another shard. To address this requirement, we define a new crossshard communication primitive named Cross-Shard Reliable Delivery (CSRD). A CSRD instance from shard Si to shard S j is identified by a tag τ and provides the following interface:

In this section, we present the details of Q UARK S HARD, with its primary procedures outlined in Algorithm 1. The protocol reaches consensus on Quark transactions within their input shards, leverages the CSRD primitive to deliver cross-shard account credits to output shards, and imports these account credits into output shards with minimal overhead. This section focuses on the execution and processing of Quark transactions, while the user request compilation scheme is detailed in Section 4.

• CSRDi→ j .Send(τ, M), invoked by replicas in Si to send a message M; • CSRDi→ j .Deliver(τ) → (M, π), invoked by replicas in S j to output the delivered message M and its corresponding certificate π;

3.1

Block Structure and Execution

In Q UARK S HARD, each shard runs an intra-shard BFT consensus protocol to agree on a chain of blocks, denoted as Ci = (B0i , B1i , . . .). Each block takes the form ⟨meta, F,txs⟩, where meta includes the parent block hash, state root, transaction root, and other standard header fields, F denotes the block’s import frontier (detailed below), and txs is an ordered sequence of Quark transactions contained within the block. Upon block commitment (line 31–46), replicas execute all transactions contained therein. For intra-shard inputs and outputs targeting the current shard, the corresponding account balances are directly debited or credited. For cross-shard outputs targeting external shards, replicas aggregate their credits into a cross-shard credit batch, which is subsequently transmitted to the destination shard via the CSRD primitive after block execution. Specifically, all account credits generated by shard Si at block height h and destined for shard S j are aggregated into a batch CBhi→ j , where CBhi→ j [pk] represents the balance credit for account pk in the destination shard. For clarity of presentation and proof, we require that even empty credit batches be transmitted to destination shards; we present a straightforward optimization in Section 8.1 that eliminates the overhead incurred by empty credit batches. Destination shards store incoming credit batches in a local credit pool and import them into subsequent blocks (line 47– 48). Because credit batches are uniquely produced through

• CSRDi→ j .Verify(τ, π), which publicly verifies the certificate π without obtaining M. CSRD must satisfy the following properties if at most f < n/3 replicas are Byzantine in each shard: • Correctness. If all honest source replicas invoke Send on the same message M, then all honest destination replicas will eventually obtain M and a certificate π via Deliver, such that π is accepted by Verify. • Validity. If any replica obtains a certificate π accepted by Verify, then at least one honest source replica must have invoked Send. In Section B, we present a concrete construction of CSRD that leverages threshold signatures, cryptographic commitments, and erasure codes (EC).

2.5

Q UARK S HARD Protocol

Network and Adversary Model

The network model can be either asynchronous or partially synchronous; the underlying network assumptions can be adapted by adjusting the intra-shard BFT protocol and the 5

input-shard consensus and reliably delivered via CSRD, destination shards do not need to execute an additional consensus round on the contents of each credit batch. Instead, each block records an import frontier vector F of length equal to the number of shards, where

Algorithm 1: Q UARK S HARD Block Processing. ▷ as a replica in shard Si upon receiving a Quark transaction tx from user do 2 if tx is valid then 3 Store tx into the transaction pool. 4 else 5 Response to the user that tx is rejected.

1

Bhj .F[i] = max{h′ : ∀r ∈ [0, h′ ), CBri→ j has been imported by the end of Bhj }.

upon proposing a new block Bhi do Let F ← Bh−1 .F; W ← ∅. i 8 for each source Sk ̸= Si do 9 Let hk be the largest value such that for all r ∈ [F[k], hk ), (CBrk→i , πrk→i ) exists in the credit pool. 10 For all r ∈ [F[k], hk ), add πrk→i to W . 11 Let F[k] ← hk . 6

7

h For convenience, we define B−1 j .F[i] = 0 and B j .F[ j] = 0. Upon block commitment, replicas wait until all credit batches selected for import have arrived, and apply the corresponding balance credits to their respective accounts before executing any transactions.

12 13

3.2

Block Proposal and Validation

14 15

Because each Quark transaction accesses a unique input shard, upon receiving a user transaction, replicas in the input shard can determine its validity solely based on their local state. If valid, the transaction is added to the local transaction pool; otherwise, the replica rejects it and notifies the user (line 1–5). If a transaction already in the pool becomes invalid due to subsequent conflicting transactions, replicas remove it and inform the user. Note that when evaluating transaction validity, replicas account for both current account balances and pending balance credits residing in the credit pool. When proposing a new block (line 6–15), a replica first inspects the parent block’s import frontier and the current credit pool. For each input shard, the replica selects the highest contiguous height at which all corresponding credit batches are present, setting this value as the new block’s import frontier. The replica then selects a sequence of valid Quark transactions from the transaction pool to populate the new block, where balance sufficiency checks account for the newly imported funds in this block. Finally, the replica computes the block metadata. Along with the proposed block, the replica broadcasts a validation witness W , which consists of cryptographic proofs for all newly imported credit batches. The witness W serves as proof that at least one honest node in the source shard has transmitted the corresponding credit batch, ensuring that any replica can safely await the required credit batches without incurring liveness issues. The witness W needs to be broadcast only once during block proposal; it is neither subjected to consensus nor persistently stored. Upon receiving a block proposal (line 16–30), a replica first verifies the correctness of its metadata (excluding the state root). It then verifies that the block’s import frontier is non-decreasing relative to its parent, and that all necessary cryptographic proofs in W are valid. Once these checks pass, the replica can safely wait for all required credit batches to arrive. Next, the replica sequentially verifies the validity of all block transactions after applying the newly imported funds,

Let Bhi .F ← F. Select valid Quark transactions in order from the transaction pool and add them to Bhi .txs. Fill in Bhi .meta. Propose ⟨Bhi ,W ⟩.

upon verifying proposal ⟨Bhi ,W ⟩ do if any field in Bhi .meta except the state root is invalid then 18 Refuse to sign for Bhi .

16

17

19 20 21 22 23 24 25 26 27

if Bhi .F[k] < Bh−1 .F[k] for any k then i Refuse to sign for Bhi . for each k ̸= i and r ∈ [Bh−1 .F[k], Bhi .F[k]) do i if πrk→i ̸∈ W or CSRDk→i .Verify(r, πrk→i ) is false then Refuse to sign for Bhi . for each k ̸= i and r ∈ [Bh−1 .F[k], Bhi .F[k]) do i r wait until CBk→i appears in the credit pool. if not all transactions in Bhi .txs are valid then Refuse to sign for Bhi .

29

if the state root in Bhi does not match the root of the state obtained after importing all selected credit batches and executing all transactions then Refuse to sign for Bhi .

30

Sign for Bhi if all checks pass.

28

upon committing Bhi do for each source Sk ̸= Si do 33 for each r ∈ [Bh−1 .F[k], Bhi .F[k]) in increasing order do i 34 wait until CBrk→i appears in the credit pool. 35 Add every credit in CBrk→i to the target accounts. 36 Delete (CBrk→i , πrk→i ) from the credit pool.

31

32

37 38 39 40 41 42 43 44

45 46

Initialize CBhi→ j ← ∅ for every S j ̸= Si . for each tx ∈ Bhi .txs in order do Debit its inputs. for each output pk, v, S j do if j = i then bali (pk) ← bali (pk) + v. else CBhi→ j [pk] ← CBhi→ j [pk] + v. for each S j ̸= Si do Invoke CSRDi→ j .Send(h, CBhi→ j ).

▷ as a replica in shard S j upon CSRDi→ j .Deliver(h) → (CBhi→ j , πhi→ j ) do 48 Store (CBhi→ j , πhi→ j ) into the credit pool.

47

6

and confirms that the resulting state root matches the proposed state root. Replicas cast their consensus votes for the block if and only if all validation checks succeed. The aforementioned validation procedure ensures that credit batch importation is monotonic and contiguous, with each height’s credit batch being imported exactly once. Furthermore, it guarantees that all transactions contained within committed blocks are valid Quark transactions.

3.3

location atomicity. Finally, we introduce a prefunding optimization that reduces user request overhead and latency.

4.1

We observe that system safety is preserved for an execution as long as all funds remain under the control of their original account holders upon failure. Therefore, we first define a safe, albeit relaxed, property compared to conventional atomicity [3, 7, 17]. Algorithms satisfying this relaxed property guarantee user fund safety while incurring lower overhead along failure execution paths.

CSRD

Q UARK S HARD employs the CSRD primitive to guarantee that credit batches derived from an input shard are reliably and verifiably delivered to target output shards. CSRD can be realized through various implementations; here, we briefly outline one concrete construction, with complete structural details deferred to Appendix B.2. Furthermore, by integrating the RPST primitive proposed by Logos [21], the vast majority of cross-shard communication overhead can be shifted onto intra-shard networks, as elaborated in Appendix B.3. Specifically, to verifiably deliver a message M bound to a tag τ, each replica in the input shard generates a threshold signature on τ with a threshold of n − f , and broadcasts this signature to all nodes in the target output shard. Upon collecting n − f distinct valid signatures, a node in the target shard aggregates them into a valid cryptographic certificate. This certificate provides undeniable proof that at least n − 2 f honest replicas in the source shard authorized and transmitted the message associated with τ. To minimize communication cost when transmitting the payload M, each replica in the input shard applies erasure code (EC) to M with a reconstruction threshold of f + 1. Each replica then broadcasts its designated EC fragment corresponding to its replica index along with its threshold signature share. Once a target shard node receives n − f valid signatures and constructs the certificate, it is guaranteed that at least n − 2 f ≥ f + 1 honest replicas have contributed valid EC fragments. Consequently, these fragments suffice to reconstruct the original message M. To prevent Byzantine nodes from broadcasting valid signature shares alongside corrupted EC fragments, the scheme secures all fragments using cryptographic commitments.

4

Atomicity

Definition 4.1 (Fund Atomicity). A request compilation algorithm satisfies fund atomicity if it guarantees that, either all inputs and outputs of a user request are successfully executed, or all involved funds remain under the control of their original account holders. Additionally, we define a stronger property that is equivalent to traditional atomicity from the perspective of honest users: Definition 4.2 (Location Atomicity). A request compilation algorithm satisfies location atomicity if it guarantees that, either all inputs and outputs of a user request are successfully executed, or all funds in accounts controlled by honest users remain in their initial states, exactly as if the user request had never been executed.

4.2

Base Compilation and Refund

The base compilation algorithm operates by first consolidating all required funds onto a single coordinator shard, and subsequently committing a single Quark transaction on that coordinator shard to disburse all funds simultaneously to their final destinations, thereby fulfilling the user request. Algorithm 2 details this procedure. Note that terms such as "funding transaction" and "final transaction" in the algorithm are introduced solely for ease of exposition; they represent standard, independent Quark transactions with no special properties. In the base compilation algorithm, one of the input shards is designated as the coordinator shard. Let InShards(req) denote the set of input shards for a given user request req. For each shard in InShards(req) other than the coordinator shard, the algorithm submits a funding Quark transaction. The input of this transaction consists of all inputs of the user request on that specific shard, while its output targets the coordinator shard, keeping the account and balance amounts unchanged. If the user request involves only a single input shard, this step is bypassed. Subsequently, the algorithm waits until all funding transactions are committed and the credit batches containing their outputs are imported by the coordinator shard. Once all funding transactions are finalized, a final Quark transaction is

User Request Compilation

To process a request spanning multiple input and output shards, the user employs a request compilation algorithm to decompose it into a sequence of Quark transactions, which are subsequently submitted to their corresponding shards according to prescribed rules. In this section, we first formally define two notions of atomicity for user request processing: fund atomicity and location atomicity. We then present a base compilation algorithm that achieves fund atomicity, followed by a refund mechanism that strengthens this guarantee to 7

4.3

Algorithm 2: Base Compilation of a User Request. Input: Request req = ⟨I, O⟩ and coordinator Sc ∈ InShards(req). Output: success only after all requested effects settle. 1 for each Si ∈ InShards(req) \ {Sc } in parallel do 2 construct a funding Quark transaction txi in Si with 3 txi .I = {⟨pk, v, Si ⟩ | ⟨pk, v, Si ⟩ ∈ req.I} 4 txi .O = {⟨pk, v, Sc ⟩ | ⟨pk, v, Si ⟩ ∈ req.I} 5

In the base compilation algorithm, users must transfer funds to the coordinator shard prior to executing the final transaction. However, users are not required to execute the base compilation independently for every individual request. Consider a scenario where a user anticipates conducting multiple transactions with a specific coordinator shard, while holding the majority of their funds on another shard. In this case, the user can prefund a sufficient balance to the coordinator shard in advance through a single batch transfer. During subsequent request executions, the user bypasses the need to submit fundtransferring funding transactions, directly issuing the final transaction instead. Consequently, the overhead incurred by multiple funding transactions is effectively amortized while simultaneously reducing request execution latency. For clarity of presentation, transaction fee mechanisms are not explicitly detailed in this paper. However, in typical blockchain systems, users generally pay execution fees for each transaction [31]. Under such economic models, users are inherently motivated to minimize the number of submitted transactions required to process a given volume of requests, which directly aligns with our design goal of reducing overall system overhead.

Submit txi to Si .

wait until every funding transaction is committed or rejected. 7 if a funding transaction was rejected then 8 return failure. 6

wait until every corresponding credit batch is imported by Sc . construct a final Quark transaction tx f in Sc with 11 tx f .I = {⟨pk, v, Sc ⟩ | ⟨pk, v, Sk ⟩ ∈ req.I} 12 tx f .O = req.O 9

10

Submit tx f to Sc . wait until the final transaction is committed or rejected. 15 if tx f was rejected then 16 return failure.

13

14

17 18

Prefunding

wait until every corresponding credit batch of tx f is imported. return success.

Algorithm 3: Refund for Location Atomicity. Input: A transaction set T X to be refunded, coordinator Sc . return if T X = ∅. 2 wait until every corresponding credit batch of tx ∈ T X is imported. 3 construct a refund Quark transaction txr in Sc with 4 txr .I = {⟨pk, v, Sc ⟩ | ⟨pk, v, Sc ⟩ ∈ txi .O and txi ∈ T X} 5 txr .O = {⟨pk, v, Si ⟩ | ⟨pk, v, Si ⟩ ∈ txi .I and txi ∈ T X} 1

5

Security Analysis

In this section, we formally prove the security properties of Q UARK S HARD. We first establish the safety and liveness of Q UARK S HARD when processing Quark transactions. Next, we demonstrate that Algorithm 2 and Algorithm 3 satisfy fund atomicity and location atomicity. Finally, we analyze the security guarantees provided by Q UARK S HARD regarding MEV resistance.

Submit txr to Sc . 7 wait until the refund transaction is committed. 8 wait until every corresponding credit batch of txr is imported. 6

submitted to the coordinator shard. Its inputs comprise all request inputs (now located on the coordinator shard), and its outputs correspond to all outputs specified by the user request. The user request completes successfully once the final transaction is committed and its resulting credit batches are imported by the destination shards.

5.1

Consistency, Validity, and Liveness

Theorem 5.1 (Consistency). Any two honest replicas within the same shard commit the same block at the same height.

If any transaction is rejected during this process, the algorithm immediately terminates and returns a failure status. Because the base compilation algorithm does not alter fund ownership prior to the final transaction, it inherently guarantees fund atomicity.

Proof. Since the number of Byzantine replicas f within the shard satisfies 3 f + 1 ≤ n, the underlying BFT consensus protocol satisfies Agreement. Consequently, every honest replica in the shard commits the identical block at any given height.

When an execution fails and an honest user seeks to achieve location atomicity, they can invoke the refund mechanism outlined in Algorithm 3 to relocate their funds back to their original shards. Algorithm 3 takes a set of funding transactions to be reverted along with the coordinator shard as inputs, and submits a single refund transaction on the coordinator shard to transfer all migrated funds back to their initial shards. Because an honest user will not issue conflicting transactions against the refund transaction, this procedure is guaranteed to succeed.

Theorem 5.2 (Validity). Any Quark transaction contained in a committed block is valid. Any credit batch imported by a committed destination block is derived from a committed source block, and every credit batch is imported by its destination shard exactly once. Proof. Since the number of Byzantine replicas f within the shard satisfies 3 f + 1 ≤ n, the underlying BFT protocol satisfies Validity. That is, every committed block must pass the verification rules specified in Algorithm 1 lines 16–30. 8

5.2

During block verification, the validity of all transactions contained within the block is enforced. Therefore, all Quark transactions included in a committed block are valid. Similarly, verification ensures that the proof for each imported credit batch exists and is valid. By the Validity property of CSRD, at least one honest replica in the source shard has transmitted the credit batch. According to Algorithm 1, an honest replica transmits the credit batch generated by a block if and only if that block has been committed. Thus, any credit batch imported by a committed block is guaranteed to originate from a committed block. Furthermore, according to the verification rules, the importation of credit batches is strictly monotonic and contiguous. Consequently, each credit batch is imported by its destination shard exactly once.

Atomicity

Theorem 5.4 (Fund Atomicity). Algorithm 2 satisfies fund atomicity. Proof. First, consider the case where Algorithm 2 completes successfully. In this scenario, all funding transactions and the final transaction are committed, and their corresponding credit batches are imported. The funding transactions migrate all inputs of the user request to the coordinator shard, whereupon the final transaction transfers these funds to all destination outputs specified by the user request. Thus, along the execution success path, all inputs and outputs of the user request are fully executed. Conversely, when the algorithm fails, the final transaction is necessarily not executed. In this case, only a subset of funding transactions may have been executed. Because funding transactions do not alter the ownership of the funds, all involved funds remain under the control of their original accounts.

Theorem 5.3 (Liveness). Any Quark transaction added to an honest replica’s transaction pool that remains persistently valid will eventually be included in a committed block. Every generated credit batch will eventually be imported by its destination shard.

Theorem 5.5 (Location Atomicity). Upon failure of Algorithm 2, an honest user can invoke Algorithm 3 to guarantee location atomicity. Proof. According to the execution logic of Algorithm 3, upon successful execution, all funds associated with the reverted funding transactions are transferred back to their original shards. Furthermore, because honest users do not issue conflicting transactions against the refund transaction, Algorithm 3 is guaranteed to execute successfully. Consequently, location atomicity is preserved.

Proof. During block verification and commitment, Q UARK S HARD waits for all required credit batches to arrive; we first prove that this waiting mechanism does not compromise the Liveness property of the underlying BFT protocol. During verification, an honest replica waits for a credit batch only after validating that its cryptographic proof exists and is valid. By the Validity of CSRD, at least one honest replica in the source shard has transmitted this batch. Hence, the block deriving this credit batch has already been committed. According to Algorithm 1, all honest replicas invoke CSRD to transmit the credit batch upon block commitment. By the Correctness of CSRD, all honest replicas in the destination shard will eventually receive the batch. Thus, waiting for credit batches during verification does not undermine liveness. Analogously, because a committed block must be a verifiable block, waiting for credit batches during commitment also preserves liveness. Since the number of Byzantine replicas f within the shard satisfies 3 f + 1 ≤ n, the running BFT consensus protocol satisfies Liveness. Consequently, blocks proposed by honest replicas are continuously committed. According to the proposal rules for honest replicas (Algorithm 1 lines 6–15), honest replicas propose valid Quark transactions sequentially and import as many pending credit batches as possible. Therefore, any Quark transaction added to an honest replica’s transaction pool that remains continuously valid will eventually be included in a committed block. For any credit batch derived from a committed block, all honest replicas in the destination shard will eventually receive it pursuant to honest transmission rules and the Correctness of CSRD. Therefore, all generated credit batches will eventually be imported by their respective destination shards.

5.3

Anti-MEV

Definition 5.1 (Cross-Shard Front-Running Free). A sharding blockchain system is cross-shard front-running free if executing a front-running attack against a cross-shard request is no easier for an adversary than executing a front-running attack against an intra-shard request. Theorem 5.6 (Cross-Shard Front-Running Free). Q UARK S HARD is cross-shard front-running free. Proof. In Q UARK S HARD, a cross-shard user request is compiled and decomposed into a sequence of individual, independent Quark transactions. An adversary observing an issued Quark transaction cannot infer the structure of the underlying complete user request or predict subsequent Quark transactions that the user will execute. Consequently, the adversary can initiate a front-running attack only after the specific target Quark transaction is publicly broadcast, which presents the same level of difficulty as front-running a purely intra-shard request. Definition 5.2 (Order-Fairness BFT Compatibility). A sharding blockchain system is order-fairness BFT compatible if it can seamlessly integrate non-sharding order-fairness 9

BFT consensus protocols [15,16] within each shard to enforce order fairness for all processed transactions.

Proof. Along the failure path, if x transactions are committed, input shards should execute BFT consensus for x transactions, thus the IS-overhead is xB . If the user requires location atomicity and there are any transactions to be refunded, executing Algorithm 3 submits one additional refund transaction on the coordinator shard, bringing the total IS-overhead to (x + 1[x > 0])B .

Theorem 5.7 (Order-Fairness BFT Compatibility). Q UARK S HARD is Order-Fairness BFT Compatible. Proof. In Q UARK S HARD, each shard processes only those Quark transactions for which it serves as the input shard, operating without the need for inter-shard coordination to process a given individual transaction. As a result, Order-Fairness BFT protocols designed for non-sharding blockchains can be directly deployed within each shard to enforce order fairness across all Quark transactions.

6

Theorem 6.3 (Overhead of Importing Credit Batches). For a block importing νB credit batches, the logical intra-shard broadcast overhead incurred by importing credit batches is mw + νB sπ , where m denotes the number of shards, w is the byte size of an integer, and sπ is the size of a CSRD-generated certificate. The vast majority of this data requires only broadcast, with only the mw portion participating in the consensus protocol.

Performance Analysis

In this section, we analyze the performance of Q UARK S HARD. Regarding intra-shard overhead, we first analyze the execution cost of the base compilation algorithm on the success path, followed by an analysis of the overhead resulting from invalid requests and credit batch importations. Next, we demonstrate that Q UARK S HARD achieves exceptionally low cross-shard communication overhead. Finally, we evaluate the processing latency of user requests under Q UARK S HARD.

6.1

Proof. Each block stores an import frontier consisting of an integer for each shard to participate in consensus, incurring a total consensus overhead of mw. Furthermore, during block proposal, the replica broadcasts cryptographic proofs for all νB imported credit batches in the block, contributing an additional broadcast overhead of νB sπ . Consequently, the total intra-shard broadcast overhead sums to mw + νB sπ . Assuming a standard integer size of approximately 8 Bytes and a Threshold BLS (TBLS) signature certificate size of approximately 48 Bytes, in a system with 100 shards where all shards produce blocks at comparable rates and each block contains cross-shard outputs destined for every other shard, the importation overhead is approximately 5.42 KB. This accounts for merely 0.26% of a classic 2 MB block in Bitcoin. In practice, because empty credit batches can be compressed using the scheme presented in Section 8.1, the actual overhead is even lower.

Intra-Shard Overhead

Theorem 6.1 (IS-Overhead of Base Compilation on the Success Path). For a user request spanning a input shards, a successful execution of Algorithm 2 without prefunding incurs an IS-overhead of aB . Proof. On the success path, Algorithm 2 commits one funding transaction in each of the a − 1 input shards other than the coordinator shard, followed by one final transaction in the coordinator shard. Each of these Quark transactions is processed by BFT consensus within its input shard, incurring an IS-overhead of B per transaction under our cost model. Thus, the total IS-overhead is (a − 1)B + B = aB .

6.2

Cross-Shard Overhead

Theorem 6.4 (CS-Overhead of Q UARK S HARD). For a batch of r Quark transactions involving c distinct output accounts in distinct shards, the total logical data payload delivered by Q UARK S HARD to one output shard via the CSRD primitive is O(cλ). Assuming the batch is sufficiently large (Lemma B.2). When employing the baseline CSRD implementation in Algorithm 4, the resulting CS-overhead is O(ncλ). By using the optimized CSRD scheme in Algorithm 5, the majority of cross-shard communication is offloaded to intra-shard networks, yielding a CS-overhead of O(cλ).

Through the prefunding optimization introduced in Section 4.3, assuming that a single prefunding operation can be amortized across l subsequent transactions on average, the overhead of funding transactions for user requests is effectively reduced. On the success path, the amortized ISoverhead per user request becomes [(a − 1)/l + 1]B . Theorem 6.2 (IS-Overhead of Base Compilation on the Failure Path). For an invalid user request, let x < a denote the number of funding transactions that are committed on the failure path. When Algorithm 2 fails, the resulting IS-overhead is xB . If the user requires location atomicity, executing Algorithm 3 incurs an additional overhead, yielding a total ISoverhead of (x + 1[x > 0])B , where 1[x > 0] is the indicator function that equals 1 if x > 0 and 0 otherwise.

Proof. According to Algorithm 1, the data delivered by Q UARK S HARD to destination shards via CSRD consists of output funds aggregated on a per-account basis across the r transactions. For each involved account, the payload contains only the account identifier and an integer representing the net balance update. Consequently, the total logical data payload delivered across shards is O(cλ). 10

By Lemma B.2, using Algorithm 4 as the concrete CSRD implementation incurs a CS-overhead of O(ncλ). Furthermore, adopting Algorithm 5 reduces the CS-overhead to O(cλ).

8

32 nodes, 8 shards 64 nodes, 16 shards 64 nodes, 8 shards 96 nodes, 24 shards 96 nodes, 8 shards

7

6

Latency (s)

Note that if each transaction specifies multiple outputs, the number of output accounts may exceed the number of transactions. However, rather than transmitting only a transaction identifier, traditional protocols are required to transmit the full transaction payload to the output shards. In contrast, Q UARK S HARD obviates the need to transmit transaction contents by transmitting only the aggregated account credits, which strictly outperforms transaction-granularity transmission.

5

4

3

2 200

6.3

400

600

800

Throughput (kReq/s)

1000

Latency Figure 3: Q UARK S HARD Scalability. 6

Latency (s)

4 3 2

7

2PC Kronos QuarkShard

6 5 4 3 2

1 250

500

750

1000

Throughput (kReq/s)

1250

(a) 1 Input, 1 Output.

100

200

300

400

500

Throughput (kReq/s)

600

700

(b) 2 Input, 2 Output.

Figure 4: Q UARK S HARD vs. Baselines.

Lone ≤ LBFT + LCSRD + Limp .

regions (Virginia, California, Tokyo, and London), scaling up to 96 replicas across 24 shards. To ensure a fair evaluation, we implemented 2PC and Kronos within the exact same experimental framework and benchmarked Q UARK S HARD against them.

The same upper bound applies to user requests that involve only a single input shard, or whose inputs have all been prefunded to the coordinator shard. For user requests spanning multiple input shards, the base compilation algorithm requires submitting two sequential rounds of Quark transactions, yielding a total latency bounded by Lbase ≤ 2(LBFT + LCSRD + Limp ).

Implementation Details. We implemented the core benchmarking framework as well as Q UARK S HARD, 2PC, and Kronos in Golang. Cryptographic primitives include SHA-256 for cryptographic hashing and Threshold BLS (TBLS) for threshold signatures [4, 5]. Erasure coding is implemented using Reed-Solomon codes [27]. Intra-shard consensus is implemented using HotStuff [33].

Although the latency of Q UARK S HARD when handling multi-input requests is higher than that of protocols such as 2PC (which typically require two rounds of BFT consensus and one round of cross-shard communication), this trade-off yields significantly better system throughput and scalability, while the latency can be effectively mitigated through mechanisms such as prefunding.

7

2PC Kronos QuarkShard

5

Latency (s)

Below, we analyze the processing latency of Q UARK S HARD for individual Quark transactions and full user requests. For ease of analysis, let LBFT bound the time elapsed from when a transaction is submitted to an honest node in a shard until it is committed via BFT consensus, let LCSRD bound the delivery latency of the CSRD primitive, and let Limp bound the delay between a credit batch being delivered to a shard and its eventual importation into a committed block. The processing of a single Quark transaction requires committing the transaction in its input shard and subsequently waiting for the credit batches containing its outputs to be delivered and imported by the target shard. Its total processing latency is bounded by

Deployment Details. Each replica was deployed on a dedicated AWS EC2 c5.2xlarge instance equipped with 8 vCPUs and 16 GB of RAM. The outbound network bandwidth for each instance was capped at 100 Mbps. The payload size for an individual transaction was set to 128 bytes, matching the average size of a standard native transfer transaction in Ethereum.

Evaluation

We implemented a prototype of Q UARK S HARD and deployed it on Amazon Web Services (AWS) to evaluate its empirical performance under real-world wide-area network (WAN) conditions. The deployment spanned four AWS geographical 11

We first evaluate the scalability of Q UARK S HARD by measuring its throughput and latency variations under increasing workloads across different numbers of nodes and shards, using requests with two input shards and two output shards (2-input-2-output) as the benchmark workload (Figure 3). Experimental results demonstrate that system throughput grows continuously with the number of shards and nodes, reaching a peak throughput of 1024 k requests per second under a 96-node, 24-shard deployment. Concurrently, the end-to-end latency remains low, staying below 4 seconds under normal workloads even when individual shards are large (12 nodes per shard). This demonstrates that Q UARK S HARD achieves near-linear throughput scalability with respect to shard counts while consistently maintaining low processing latency. Next, we benchmark the performance of Q UARK S HARD, Kronos, and 2PC under a 64-node, 16-shard deployment using two workload profiles: 1-input-1-output requests (Figure 4a) and 2-input-2-output requests (Figure 4b). Experimental results indicate that across different workloads, Q UARK S HARD achieves 199.6%–210.7% of Kronos’s maximum throughput and 299.1%–314.8% of 2PC’s maximum throughput. Under the single-input request workload, because Q UARK S HARD requires only one round of BFT consensus alongside one round of credit batch importation, its end-to-end request latency is significantly lower than the two-round BFT consensus required by 2PC and Kronos. Specifically, the endto-end latency of Q UARK S HARD is only 78.1% of Kronos and 65.2% of 2PC. Under the multi-input request workload, Q UARK S HARD trades slightly higher latency for substantially higher throughput. Specifically, Q UARK S HARD incurs an latency approximately 127% of Kronos and 110% of 2PC.

1500 1.4

1250 2PC Kronos QuarkShard

1000 750

Latency (s)

Overall Performance

Throughput (kReq/s)

500 250

2PC Kronos QuarkShard

1.2 1.0 0.8

1

2

3

Number of Output Shards

4

1

2

3

Number of Output Shards

4

Throughput (kReq/s)

(a) Throughput vs. # of Outputs. (b) Latency vs. # of Outputs. 2PC Kronos QuarkShard

1500 1250 1000 750 500

2.0 1.8

Latency (s)

7.1

1.6 1.4 1.2

2PC Kronos QuarkShard

1.0

250

0.8 1

2

3

Number of Input Shards

4

(c) Throughput vs. # of Inputs.

1

2

3

Number of Input Shards

4

(d) Latency vs. # of Inputs.

Figure 5: Performance under Different Workload Profiles. shards results in a throughput degradation of less than 0.5%. In contrast, the throughputs of 2PC and Kronos decrease by 50.9% and 60.2%, respectively. This highlights that in Q UARK S HARD, the computational and communication overhead associated with credit batch importation is negligible compared to transaction execution. Regarding latency, as the number of output shards scales from 1 to 4, the latency of Q UARK S HARD increases by approximately 13.7%, compared to 24.2% for 2PC and 43.0% for Kronos. When fixing the number of output shards, the throughput of Q UARK S HARD is strictly inversely proportional to the number of input shards: the throughput under 1 input shard is approximately 2.02× that under 2 input shards and 4.05× that under 4 input shards. This is consistent with the aB ISoverhead of successful requests under the base compilation algorithm, which grows linearly with the number of input shards. As for latency, when the number of input shards increases from 2 to 4, the latency of Q UARK S HARD increases by approximately 15.5%, whereas 2PC and Kronos experience increases of roughly 30.5% and 17.3%, respectively.

7.2 Performance under Varying Numbers of Inputs and Outputs To evaluate the impact of different workload characteristics across protocols, we first fix the number of input shards to 1 and measure how varying the number of output shards affects throughput and latency (Figure 5a and 5b). We then fix the number of output shards to 1 and evaluate the system under varying numbers of input shards (Figure 5c and 5d). The experiments were conducted under a deployment of 64 nodes and 16 shards. Experimental results demonstrate that Q UARK S HARD consistently outperforms 2PC and Kronos in throughput across all tested input and output shard configurations. Furthermore, except for the transition from 1 to 2 input shards, the latency of Q UARK S HARD exhibits lower sensitivity and grows slower with respect to increasing input and output shard counts. When fixing the number of input shards, variations in the number of output shards have virtually no impact on the throughput of Q UARK S HARD: scaling from 1 to 4 output

7.3

Cross-Shard Communication Overhead

To evaluate the effectiveness of aggregating transaction outputs on a per-account basis in reducing cross-shard communication overhead, we measure the total logical cross-shard communication payload across various batch sizes (i.e., the number of transactions committed per block). The evaluation is conducted under a deployment of 64 nodes across 16 shards, with 1, 000 active accounts per shard. Experimental results demonstrate that the logical cross-shard communication volume of Q UARK S HARD is consistently lower than that of Kronos. Furthermore, as the block batch size increases, peraccount aggregation becomes increasingly effective, leading 12

that every batch is imported exactly once. Furthermore, since importing empty batches yields no observable state transitions, compressing empty batches into subsequent non-empty batches introduces no additional processing latency.

Kronos QuarkShard

900

Logical Cross-Shard Traffic (MB)

800 700 600

8.2

Application on UTXO Model.

500

Q UARK S HARD can be readily adapted to the UTXO model. Specifically, by treating every input and output tuple ⟨pk, v, Si ⟩ as a UTXO of value v assigned to account pk managed by shard Si , all preceding design logic and theoretical guarantees hold directly. Instead of tracking explicit account balances, each replica maintains a local UTXO set, replacing balance additions and deductions with UTXO insertions and deletions. Cross-shard credit batches remain aggregated on a peraccount basis, represented as a single consolidated UTXO for each account, and are delivered to destination shards via the CSRD primitive. When evaluating transaction validity, replicas verify whether the UTXOs consumed by the transaction exist within the local UTXO set.

400 300 200 8000

16000

24000

32000

40000

48000

Batch Size

56000

64000

72000

80000

Figure 6: Cross-Shard Communication Overhead.

to a continuous reduction in amortized cross-shard communication payload. This empirically validates the efficacy of cross-shard transaction outputs aggregating.

9 8 8.1

Conclusion

Discussion We propose Q UARK S HARD, a novel sharding blockchain protocol that breaks away from the traditional cross-shard request processing paradigm that treats each user request as a monolithic entity. By compiling and decomposing a request into independent Quark transactions, Q UARK S HARD processes cross-shard requests with reduced overhead while guaranteeing fund atomicity or location atomicity through a carefully designed request compilation algorithm. This paradigm shift enables Q UARK S HARD to achieve intra-shard BFT execution overhead and cross-shard communication overhead below the theoretical lower bounds imposed by conventional paradigms. Furthermore, Q UARK S HARD reduces the sharding-specific attack surface for cross-shard front-running and improves resilience to invalid-request flooding. Comprehensive empirical evaluations demonstrate the low overhead and superior performance of Q UARK S HARD over state-of-the-art protocols.

Empty Credit Batch Compression.

In Algorithm 1, we require that for each block and every external shard, a CSRD primitive invocation be executed regardless of whether the corresponding credit batch is empty. Here, we introduce a straightforward optimization that eliminates the potential overhead of transmitting empty batches while preserving protocol security. Specifically, each credit batch no longer represents outputs generated from a single block height, but rather spans a contiguous range of block heights. We denote by CBs,h i→ j [pk] a non-empty credit batch generated at block height h, signifying that all blocks within the height interval [s, h) in shard Si contained no transaction outputs destined for shard S j . Upon committing a block, replicas omit transmissions to shards with empty batches and instead send credit batches exclusively to shards with non-empty outputs, embedding the starting height s of the preceding sequence of empty heights into the batch header. The destination shard can import CBs,h i→ j [pk] if and only if all heights in [0, s) have already been imported, which atomically effects the importation of all batches within the interval [s, h]. This modification preserves the security of credit batch importation: for every non-empty height, honest replicas transmit exactly one identical credit batch derived from a consensus-committed block. Consequently, honest nodes in the destination shard receive authenticated credit batches solely for non-empty heights. Because each credit batch explicitly encodes range metadata, destination nodes maintain monotonic and contiguous importation progress, guaranteeing 13

References

Zomaya. Prophet: Conflict-free sharding blockchain via byzantine-tolerant deterministic ordering. In IEEE INFOCOM 2023-IEEE Conference on Computer Communications, pages 1–10. IEEE, 2023.

[1] Harmony: Technical whitepaper, 2018. URL: https: //harmony.one/whitepaper.pdf. [2] Polkadot lightpaper: An introduction to polkadot, 2020. URL: https://assets.polkadot.network/ Polkadot-lightpaper.pdf.

[13] Huawei Huang, Xiaowen Peng, Jianzhou Zhan, Shenyang Zhang, Yue Lin, Zibin Zheng, and Song Guo. Brokerchain: A cross-shard blockchain protocol for account/balance-based state sharding. In IEEE INFOCOM 2022-IEEE conference on computer communications, pages 1968–1977. IEEE, 2022.

[3] Mustafa Al-Bassam, Alberto Sonnino, Shehar Bano, Dave Hrycyszyn, and George Danezis. Chainspace: A sharded smart contracts platform. In Network and Distributed System Security Symposium (NDSS), 2018.

[14] Shan Jiang, Jiannong Cao, Cheung Leong Tung, Yuqin Wang, and Shan Wang. Sharon: Secure and efficient cross-shard transaction processing via shard rotation. In IEEE INFOCOM 2024-IEEE Conference on Computer Communications, pages 2418–2427. IEEE, 2024.

[4] Alexandra Boldyreva. Threshold signatures, multisignatures and blind signatures based on the gap-diffiehellman-group signature scheme. In International Workshop on Public Key Cryptography, pages 31–46. Springer, 2002.

[15] Mahimna Kelkar, Soubhik Deb, Sishan Long, Ari Juels, and Sreeram Kannan. Themis: Fast, strong orderfairness in byzantine consensus. In Proceedings of the 2023 acm sigsac conference on computer and communications security, pages 475–489, 2023.

[5] Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the weil pairing. In International conference on the theory and application of cryptology and information security, pages 514–532. Springer, 2001.

[16] Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels. Order-fairness for byzantine consensus. In Annual International Cryptology Conference, pages 451–480. Springer, 2020.

[6] Philip Daian, Steven Goldfeder, Tyler Kell, Yunqi Li, Xueyuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels. Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability. In 2020 IEEE symposium on security and privacy (SP), pages 910–927. IEEE, 2020.

[17] Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Ewa Syta, and Bryan Ford. Omniledger: A secure, scale-out, decentralized ledger via sharding. In 2018 IEEE symposium on security and privacy (SP), pages 583–598. IEEE, 2018.

[7] Hung Dang, Tien Tuan Anh Dinh, Dumitrel Loghin, EeChien Chang, Qian Lin, and Beng Chin Ooi. Towards scaling blockchain systems via sharding. In Proceedings of the 2019 international conference on management of data, pages 123–140, 2019.

[18] Mingzhe Li, You Lin, Jin Zhang, and Wei Wang. Cochain: High concurrency blockchain sharding via consensus on consensus. In IEEE INFOCOM 2023IEEE Conference on Computer Communications, pages 1–10. IEEE, 2023.

[8] Sourav Das, Vinith Krishnan, and Ling Ren. Efficient cross-shard transaction execution in sharded blockchains. arXiv preprint arXiv:2007.14521, 2020.

[19] Andi Liu, Yizhong Liu, Qianhong Wu, Boyu Zhao, Dongyu Li, Yuan Lu, Rongxing Lu, and Willy Susilo. Cherubim: A secure and highly parallel cross-shard consensus using quadruple pipelined two-phase commit for sharding blockchains. IEEE Transactions on Information Forensics and Security, 19:3178–3193, 2024.

[9] Jelle Hellings and Mohammad Sadoghi. Byshard: Sharding in a byzantine environment. Proc. VLDB Endow., 14(11):2230–2243, 2021. [10] Zicong Hong, Song Guo, and Peng Li. Scaling blockchain via layered sharding. IEEE Journal on Selected Areas in Communications, 40(12):3575–3588, 2022.

[20] Yizhong Liu, Andi Liu, Yuan Lu, Zhuocheng Pan, Yinuo Li, Jianwei Liu, Song Bian, and Mauro Conti. Kronos: A secure and generic sharding blockchain consensus with optimized overhead. In Network and Distributed System Security Symposium (NDSS), 2025.

[11] Zicong Hong, Song Guo, Peng Li, and Wuhui Chen. Pyramid: A layered sharding blockchain system. In IEEE INFOCOM 2021-IEEE Conference on Computer Communications, pages 1–10. IEEE, 2021.

[21] Yizhong Liu, Boyu Zhao, Yuxuan Hu, Haojun Tan, Feiang Ran, Andi Liu, Zhuocheng Pan, Yuan Lu, Song Bian, Jianwei Liu, et al. Logos: Robust sharding

[12] Zicong Hong, Song Guo, Enyuan Zhou, Jianting Zhang, Wuhui Chen, Jinwen Liang, Jie Zhang, and Albert 14

blockchain with fast processing and optimal {CrossShard} overhead. In 35th USENIX Security Symposium (USENIX Security 26), 2026.

[33] Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham. Hotstuff: Bft consensus with linearity and responsiveness. In Proceedings of the 2019 ACM symposium on principles of distributed computing, pages 347–356, 2019.

[22] Michael G Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, and Daniel A Spielman. Efficient erasure correcting codes. IEEE Transactions on Information Theory, 47(2):569–584, 2001.

[34] Mahdi Zamani, Mahnush Movahedi, and Mariana Raykova. Rapidchain: Scaling blockchain via full sharding. In Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pages 931–948, 2018.

[23] Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert, and Prateek Saxena. A secure sharding protocol for open blockchains. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 17–30, 2016.

[35] Jianting Zhang, Wuhui Chen, Sifu Luo, Tiantian Gong, Zicong Hong, and Aniket Kate. Front-running attack in sharded blockchains and fair cross-shard consensus. In Network and Distributed System Security Symposium (NDSS), 2024.

[24] Ralph C Merkle. A digital signature based on a conventional encryption function. In Conference on the theory and application of cryptographic techniques, pages 369– 378. Springer, 1987.

A

[25] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008. URL: https://bitcoin.org/ bitcoin.pdf.

A.1

Related Works Cross-Shard Requests Processing

A substantial body of prior work has investigated the processing of cross-shard user requests in sharding blockchain systems, proposing various mechanisms to enhance performance [3, 7–11, 13, 14, 17–21, 29, 30, 34]. State-of-the-art approaches include Kronos [20] and Logos [21]. For a cross-shard user request, Kronos first executes BFT consensus across all input shards to consume the inputs. The consumed inputs are then transmitted via a trusted crossshard channel to the output shards, where they are temporarily staged. Subsequently, output shards execute consensus to transfer all staged funds to the target accounts. If invalid inputs are encountered, Kronos requires all shards that have already consumed funds to execute consensus on a refund transaction to revert the execution. In contrast, Logos first broadcasts the user request to all involved shards, whereupon all input shards execute a cross-state determine reliable broadcast (csdRBC) protocol to verify the validity of all inputs. The resulting validity determinations are then delivered to all involved shards via a trusted cross-shard channel. If all inputs are valid, all input and output shards execute consensus on the user request to perform the fund deductions and additions. If any input is invalid, all shards terminate the process directly without requiring further consensus, though the initial broadcast overhead is still incurred. To optimize cross-shard communication, Logos introduces RPST, which offloads the majority of communication volume to intra-shard networks. In addition, several other cross-shard request processing schemes have been proposed. A widely adopted approach is Two-Phase Commit (2PC) [3, 7, 9, 19]. For a cross-shard request, 2PC first executes BFT consensus across all input shards to lock funds, followed by a second consensus round across all input and output shards to actually deduct or credit balances. Another common approach utilizes relay accounts

[26] Kaihua Qin, Liyi Zhou, and Arthur Gervais. Quantifying blockchain extractable value: How dark is the forest? In 2022 IEEE Symposium on Security and Privacy (SP), pages 198–214. IEEE, 2022. [27] Irving S Reed and Gustave Solomon. Polynomial codes over certain finite fields. Journal of the society for industrial and applied mathematics, 8(2):300–304, 1960. [28] Alex Skidanov, Illia Polosukhin, and Bowen Wang. Nightshade: Near protocol sharding design 2.0, 2019. URL: https://discovery-domain.org/ papers/nightshade.pdf. [29] Junfeng Tian, Yuyang Zhao, and Jin Tian. Controlshard: A cross-shard transaction processing method based on congestion control strategy. Computer Networks, page 112028, 2026. [30] Jiaping Wang and Hao Wang. Monoxide: Scale out blockchains with asynchronous consensus zones. In 16th USENIX symposium on networked systems design and implementation (NSDI 19), pages 95–112, 2019. [31] Gavin Wood et al. Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper, 151(2014):1–32, 2014. [32] Yibin Xu, Jingyi Zheng, Boris Düdder, Tijs Slaats, and Yongluan Zhou. A two-layer blockchain sharding protocol leveraging safety and liveness for enhanced performance. arXiv preprint arXiv:2310.11373, 2023. 15

or user coordinators [13, 34]: to process a request, funds are first transferred via BFT consensus in all input shards to relay accounts or coordinator users in the output shards, followed by a second consensus round in the output shards to transfer funds from the relay or coordinator accounts to the final destinations. Monoxide [30] and CoChain [18] adopt a relay transaction mechanism analogous to relay accounts: a relay transaction first undergoes BFT consensus in the input shard to transfer funds toward the target shard, after which its output is transferred to the final destination within the target shard. Nevertheless, these systems adhere to the traditional processing paradigm that treats each user request as a monolithic entity for consensus and execution. Consequently, they cannot overcome the lower bounds of an IS-overhead of at least (a + b)B and a CS-overhead of at least Ω(rλ) [20, 21]. Other schemes introduce specialized sharding architectures to handle cross-shard requests. Das et al. [8] introduces a dedicated coordinator shard responsible for orchestrating crossshard requests across different shards. Tian et al. [29] employs specialized shards to process cross-shard requests. Hong et al. [10, 11] introduces a hierarchical sharding structure in which bridge shards cover multiple lower-level shards and coordinate their cross-shard requests. Xu et al. [32] similarly employ a two-tiered sharding architecture, in which a set of small execution shards is overseen by a control shard to process user requests. Jiang et al. [14] proposed a method that dynamically merges pairs of shards and periodically rotates the pairings, permitting cross-shard requests to execute only when the involved shards are actively merged.

A.2

output shard consensus instances in traditional cross-shard workflows, and proposes finalization fairness to align the processing and execution order across shards.

B

CSRD Construction

B.1

Building Blocks

We use the following standard building blocks. Throughout this section, q = n − f and k = f + 1. Threshold signatures. A (q, n) threshold signature scheme provides: • TSig.SignShareℓ (x) → sℓ , invoked by replica pℓ to generate its signature share on x; • TSig.VerifyShare(ℓ, x, sℓ ), which verifies a signature share; • TSig.Combine(x, {sℓ }) → σ, which aggregates q valid signature shares from distinct replicas into a threshold signature σ; • TSig.Verify(x, σ), which verifies a threshold signature σ. Combining q valid signature shares from distinct replicas yields an accepted signature. Conversely, if fewer than q replicas contribute signature shares, generating an accepted signature is computationally infeasible. Erasure coding.

A (k, n) erasure code provides:

• EC.Encode(M) → {e1 , . . . , en }, which encodes a message M into n fragments;

MEV in sharding Blockchains

• EC.Decode({⟨ℓ, eℓ ⟩}ℓ∈I ) → M, which reconstructs the original message M using a set of fragments indexed by I, where I is an index set of size at least k.

Extracting Maximal Extractable Value (MEV) through transaction order manipulation has emerged as a major security challenge in blockchain systems [6, 26]. Order-fairness BFT protocols, such as Aequitas [16], investigate mechanisms to prevent malicious leaders or proposers from arbitrarily reordering transactions observed by honest nodes. However, these protocols primarily address local transaction ordering within a single consensus instance. In sharding blockchains, achieving fair ordering for cross-shard requests typically necessitates specialized protocol designs. Prophet [12] adopts a Byzantine fault-tolerant deterministic ordering strategy to prevent conflicts among cross-shard transactions. Furthermore, sharding blockchains introduce unique fairness challenges. In conventional cross-shard protocols, a cross-shard request must reach consensus within its input shards before undergoing a separate consensus process within its output shards. This sequential workflow inherently exposes cross-shard requests to higher latency compared to intra-shard transactions, thereby expanding the attack surface for frontrunning exploits. Haechi [35] identifies front-running attacks stemming from the execution window gap between input and

Any k distinct valid fragments guarantee the exact reconstruction of the original message. The encoding is deterministic, and each fragment has a size of O(|M|/k). Commitments.

A commitment scheme provides:

• Com.CommitOpen({e1 , . . . , en }, ℓ) → (c, µℓ ), which returns a commitment c and an opening µℓ ; • Com.Verify(c, ℓ, eℓ , µℓ ), which verifies that eℓ occupies position ℓ in the committed vector. We require that the commitment is deterministic. And we require correctness and position binding: after c is fixed, no adversary can open the same position to two different values. We keep this interface generic, but all commitment instances in this paper are instantiated via a Merkle tree [24] in which eℓ serves as the ℓ-th leaf node. Under this construction, the commitment is the Merkle root, and an opening is a Merkle proof for the corresponding leaf. Thus, c has a size of O(λ), and an opening has a size of O(λ log n). 16

Intra-shard certification. The Logos-based construction additionally employs an intra-shard certification primitive. This primitive provides:

Algorithm 4: A basic CSRD instance from Si to S j with tag τ. ▷ as the ℓ-th replica pℓ ∈ Si upon CSRDi→ j .Send(τ, M) is called do 2 sℓ ← TSig.SignShareℓ (⟨i, j, τ⟩). {e1 , . . . , en } ← EC.Encode(M). 3 4 (c, µℓ ) ← Com.CommitOpen({e1 , . . . , en } , ℓ). 5 Send msgℓ = ⟨τ, c, ℓ, eℓ , µℓ , sℓ ⟩ to every replica of S j .

1

• Certifyi (x) → ρ, invoked by replica pℓ to produce a certificate for x; • CertVerify(x, ρ), which verifies whether a certificate is valid.

▷ as a replica in S j upon receiving n − f msgℓ from distinct source replicas pℓ , each satisfying TSig.VerifyShare(ℓ, ⟨i, j, τ⟩ , sℓ ) do 7 π ← TSig.Combine(⟨i, j, τ⟩ , {sℓ }). 8 Find I of f + 1 distinct indices whose messages have the same c and satisfy Com.Verify(c, ℓ, eℓ , µℓ ). 9 M ← EC.Decode({(ℓ, eℓ )}ℓ∈I ). 10 Deliver ⟨M, π⟩. 6

An accepted certificate can be obtained by all replicas if and only if at least q replicas invoke Certifyi (x). In general, this certification primitive does not introduce additional consensus rounds; instead, it can be seamlessly embedded into intra-shard BFT consensus. A typical instantiation involves embedding the hash of x into the header of a BFT proposal block, using the block commit certificate together with the Merkle proof of inclusion for x’s hash in the block header as the validity certificate ρ.

B.2

▷ as a replica in Si or S j upon CSRDi→ j .Verify(τ, π) is called do 12 return TSig.Verify(⟨i, j, τ⟩ , π).

11

A Basic CSRD Instance

above, Algorithms 4 and 5 satisfy CSRD correctness and validity.

In Algorithm 4, each replica in the input shard broadcasts its threshold signature share along with its designated erasurecoded fragment corresponding to its replica index to all replicas in the target shard. Simultaneously, cryptographic commitments are used to protect the integrity of the fragments. Upon receiving n − f messages containing valid signature shares, a replica in the target shard can aggregate these shares to form a certificate. Among these messages, at least n − 2 f ≥ f + 1 originate from honest replicas; thus, the original data can be reconstructed using the accompanying erasure-coded fragments.

B.3

Proof. For Algorithm 4, suppose all honest source replicas invoke Send(τ, M) with the same M. Deterministic encoding and commitment make them send fragments under the same commitment c∗ . Every honest destination replica eventually receives messages from all n − f honest source replicas and can therefore combine their signature shares. Any n − f received messages contain at least n − 2 f ≥ f + 1 honest messages, so a qualifying set of f + 1 messages exists. Moreover, every set of f + 1 messages from distinct source replicas that shares a commitment contains an honest message. Its commitment must consequently be c∗ ; position binding makes every accepted fragment in that set the corresponding fragment of the codeword for M. Erasure-code correctness therefore reconstructs the unique M. This proves correctness. For validity, an accepted threshold signature contains n − f distinct shares, at least n − 2 f of which came from honest source replicas. Since an honest replica signs ⟨i, j, τ⟩ only while processing CSRDi→ j .Send(τ, M), at least one honest source replica invoked Send(τ, M) for this instance. Notice that this argument does not require the signature to cover M, a digest, or c. For Algorithm 5, deterministic encoding again gives all honest source replicas the same c∗ , and certification correctness supplies an accepted certificate for it. Among the n − f honest sources, at most f have a Byzantine replica at the corresponding destination index. Hence at least n − 2 f ≥ f + 1 correctly opened fragments reach honest paired destinations and are broadcast to every honest destination replica. Position binding and erasure-code correctness make every such replica reconstruct the same M. For validity, an accepted certification proof has n − f participants, at least n − 2 f of which are honest; each honest

CSRD Instance based on Logos

Algorithm 5 adopts the one-to-one cross-shard transmission pattern proposed by Logos [21]. Specifically, a source replica with index ℓ transmits fragment ℓ exclusively to the target replica sharing the same index ℓ, which subsequently propagates the fragment within the destination shard. Unlike Algorithm 4, where target shard replicas aggregate the certificate, source replicas in Algorithm 5 first generate the certificate intra-shard before transmitting it to the destination. For ease of proof, the algorithm specifies that certificate generation occurs after replicas initiate transmission. However, in practical deployments, the certificate may be generated alongside intra-shard BFT consensus prior to transmission. This does not compromise security, as our model requires that any honest replica observing a valid certificate will invariably invoke the transmission procedure.

B.4

Analysis

Lemma B.1 (CSRD security). Under authenticated reliable channels, n ≥ 3 f + 1, and the properties of the building blocks 17

Only one message is transmitted along each of the n matched source–destination pairs, yielding a total cost of   n|M| + nηL (n, p) . O f +1

Algorithm 5: A Logos-based CSRD instance from Si to S j with tag τ. ▷ as the ℓ-th replica pℓ ∈ Si upon CSRDi→ j .Send(τ, M) is called do {e1 , . . . , en } ← EC.Encode(M). 2 3 (c, µℓ ) ← Com.CommitOpen({e1 , . . . , en } , ℓ). 4 ρ ← Certifyi (⟨i, j, τ, c⟩). 5 Send msgℓ = ⟨τ, c, ℓ, eℓ , µℓ , ρ⟩ to the ℓ-th replica of S j .

1

The certification procedure and the subsequent destinationshard rebroadcast are intra-shard operations, so neither contributes to CS-overhead. With the default instantiation, |τ|, |c|, |sℓ | = O(λ), while |µℓ | = O(λ log n). The certificate ρ consists of a constant-size threshold-signature commit certificate and, when needed, a Merkle inclusion proof with respect to this export root. Consequently, |ρ| = O(λ log(p + 1)). The tag and replica index are absorbed by these terms, yielding ηB (n) = O(λ log n) and ηL (n, p) = O(λ(log n + log(p + 1))). Substitution gives  2  n |M| 2 + n λ log n O f +1

▷ as a replica in S j upon receiving msgℓ from the ℓ-th replica of Si , satisfying CertVerifyi (⟨i, j, τ, c⟩ , ρ) and Com.Verify(c, ℓ, eℓ , µℓ ) do 7 Broadcast msgℓ to all replicas in S j .

6

upon receiving valid msgℓ for a set I of f + 1 distinct indices, all with the same c do 9 M ← EC.Decode({(ℓ, eℓ )}ℓ∈I ). 10 π ← ⟨c, ρ⟩ for any valid ρ among these messages. 11 Deliver ⟨M, π⟩. 8

▷ as a replica in Si or S j upon CSRDi→ j .Verify(τ, π) is called do 13 Parse π = ⟨c, ρ⟩. 14 return CertVerify(⟨i, j, τ, c⟩ , ρ).

12

and participant certifies only while processing Send(τ, M). Thus an accepted CSRD certificate implies that an honest source replica invoked Send(τ, M). Certification agreement additionally prevents the same instance from certifying two different commitments.

and

 n|M| + nλ(log n + log(p + 1)) . f +1

For n = 3 f + 1, these become O(n|M| + n2 λ log n) and O(|M| + nλ(log n + log(p + 1))). Finally, if |M| = Ω(nλ(log n + log(p + 1))), the message terms dominate the metadata terms, leaving O(n|M|) and O(|M|), respectively.

Lemma B.2 (CSRD cross-shard overhead). Ignoring lowerorder authentication metadata when the encoded message dominates it, Algorithms 4 and 5 transmit O(n2 |M|/( f + 1))

 O

O(n|M|/( f + 1))

bytes across shards, respectively. Under the standard configuration n = 3 f + 1, these become O(n|M|) and O(|M|). Proof. Each encoded fragment has size O(|M|/( f + 1)). In Algorithm 4, every cross-shard message additionally contains the tag τ, source index ℓ, commitment c, opening µℓ , and signature share sℓ . Thus, the size of the metadata in each message is ηB (n) = |τ| + ⌈log n⌉ + |c| + |µℓ | + |sℓ |, and sending one such message from each of n source replicas to each of n destination replicas costs  2  n |M| 2 O + n ηB (n) . f +1 Let p denote the number of entries covered by the export root used for certification, taking p = 1 when the certified value is committed directly in the block header. In Algorithm 5, a cross-shard message instead contains τ, ℓ, c, µℓ , and the intra-shard certificate ρ. Hence, the size of the metadata in each message is ηL (n, p) = |τ| + ⌈log n⌉ + |c| + |µℓ | + |ρ|. 18

Related documents

• HealthyBroker: A Trustworthy Blockchain-Based Multi-Cloud Broker for Patient-Centered eHealth Services#465600
• Event-Driven App Design for High-Concurrency Microservices#88147
• DSLHash: Lightweight Hash Function Based on SVSC 4D Chaotic System and Dynamic Substitution Layers.#1091378
• Cinch, filter, erase: virtual bodies and the editable self#246614
• Adversarial procurement in blockchains#160747