PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Changyu Duan, Zhixuan Fang

arXiv:2610.23014v1cs.DC

TL;DR

Cross-shard requests are challenging to process securely and efficiently in sharded blockchains. QuarkShard compiles them into single-input-shard transactions while preserving request atomicity. Its four-region evaluation reports peak throughput of 1024k requests per second and higher maximum throughput than Kronos and 2PC.

  • Problem

    Cross-shard requests require coordination across shards while preserving request atomicity, and traditional monolithic processing incurs intra-shard consensus and cross-shard communication overhead.

    Source: §1 · p. 1

  • Method

    QuarkShard compiles each cross-shard request into single-input-shard Quark transactions and uses a designed compilation algorithm to guarantee fund atomicity or location atomicity.

    Source: §1 · p. 2

  • Results

    1024k requests per second peak throughput with sub-4-second latency; maximum throughput reaches up to 210.7% of Kronos's and 314.8% of 2PC's.

    Source: §1 · p. 4

  • Takeaways & Limitations

    QuarkShard reduces overhead below conventional-paradigm lower bounds and reduces the sharding-specific attack surface for cross-shard front-running while improving resilience to invalid-request flooding.

    Source: §9 · p. 13

    For multi-input requests, QuarkShard latency is higher than protocols such as 2PC, though prefunding can mitigate this trade-off.

    Source: §6.3 · p. 11

Abstract

from arXiv · show

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 QuarkShard, a sharding protocol that breaks away from this traditional paradigm to achieve intra-shard and cross-shard overheads below the lower bounds imposed by conventional approaches. QuarkShard 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, QuarkShard guarantees fund atomicity or location atomicity during request execution. QuarkShard also enhances the security of blockchain sharding systems against MEV attacks and flooding attacks. Empirical evaluation across a wide-area network spanning four AWS regions demonstrates that QuarkShard achieves superior performance, attaining a peak throughput of $1024$k requests per second with sub-$4$-second latency. Benchmark comparisons show that QuarkShard achieves up to $210.7\%$ and $314.8\%$ of the maximum throughputs of Kronos and 2PC, respectively.

1 Introduction

QuarkShard replaces monolithic cross-shard request processing with single-input-shard Quark transactions, using request compilation to preserve atomicity while reducing processing overhead. It also targets sharding-specific MEV and flooding vulnerabilities.

1 Introduction

  • Traditional protocols treat each request as a monolithic entity; prior work places intra-shard consensus overhead at a minimum of (a+b)B and cross-shard communication at Ω(rλ).2PC-based schemes incur (2a+b)B or more, while Kronos and Logos reduce this to (a+b)B.Source: §1 · p. 2
  • QuarkShard decomposes each request into single-input-shard transactions, requiring consensus only in the input shard; compilation guarantees fund atomicity and can provide location atomicity for honest users.On the success path, the base algorithm commits one Quark transaction per input shard, for IS-overhead aB.Source: §1 · pp. 2–4
  • Aggregating cross-shard effects by destination account reduces communication for r Quark transactions to O(ncλ), or O(cλ) with the Logos-based optimization.Here c is the number of distinct destination accounts in distinct shards across the transactions.Source: §1 · p. 3
  • QuarkShard avoids publicly broadcasting a monolithic request intent, closing the extra front-running window from cross-shard latency disparities while retaining compatibility with conventional order-fairness protocols.It shrinks, but does not eliminate, the MEV attack surface introduced by sharding.Source: §1 · p. 3
  • Invalid requests incur xB overhead with fund atomicity or (x+1[x > 0])B with location atomicity, addressing flooding costs that are at least 2xB in most 2PC-based protocols and Kronos.When broadcast bandwidth is the primary bottleneck, QuarkShard can achieve lower practical overhead than Logos.Source: §1 · pp. 3–4
  • 1024k requests per second peak throughput across 96 nodes and 24 shards, with sub-4-second latency; up to 210.7% and 314.8% of Kronos's and 2PC's maximum throughputs, respectively.The evaluation used a wide-area network spanning four AWS regions.Source: §1 · p. 4

2 Preliminaries

The preliminaries define the sharding model, cross-shard requests and Quark transactions, and the primitives and assumptions used by QUARKSHARD. They also specify the BFT and cross-shard delivery properties the protocol relies on.

2.1 Sharding Blockchain Model

  • Each shard has n replicas with at most f Byzantine replicas, where n ≥ 3f + 1; the paper adopts the account-balance model but also supports UTXO.The model assumes mechanisms keep this replica threshold satisfied throughout execution with overwhelming probability.Source: §2.1 · p. 4

2.2 User Requests and Quark Transactions

  • A user request is a payment intent represented by inputs and outputs that may span shards, while each Quark transaction debits inputs from only one shard.A request compilation algorithm decomposes a well-formed request into ordered Quark transactions submitted to their respective shards.Source: §2.2 · p. 4

2.3 BFT Protocol

  • Each shard’s BFT protocol commits a totally ordered block sequence and must provide agreement, validity, and liveness when fewer than one-third of replicas are Byzantine.Agreement prevents honest replicas committing different blocks at the same height; validity enforces the block predicate, and liveness ensures continued commits.Source: §2.3 · p. 5

2.4 Cross-Shard Reliable Delivery

  • Cross-Shard Reliable Delivery (CSRD) reliably delivers a source shard’s consensus result and certificate to destination-shard replicas.Its interface provides send, deliver, and public certificate verification; correctness ensures delivery when honest source replicas send the same message, while validity ties an accepted certificate to an honest source send.Source: §2.4 · p. 5

2.5 Network and Adversary Model

  • The model permits asynchronous or partially synchronous networks and an adversary controlling up to f < n/3 replicas per shard, which may delay or reorder messages but cannot forge or suppress others’ messages.In partial synchrony, messages between honest nodes have a known bounded delay after the Global Stabilization Time.Source: §2.5 · p. 5

3 QUARKSHARD Protocol

QUARKSHARD reaches consensus on Quark transactions only in their input shards and reliably delivers resulting credits to output shards. Blocks import those credits without requiring output shards to run another consensus round on each batch.

3 QUARKSHARD Protocol

  • QUARKSHARD processes only Quark transactions, which require consensus in their unique input shard, while output shards import credits with minimal overhead.The protocol’s user-request compilation scheme is described separately in Section 4.Source: §3 · p. 5

3.1 Block Structure and Execution

  • Each committed block executes its Quark transactions, batches cross-shard output credits by destination, and sends the batches through CSRD for import by destination shards.Destination shards record an import frontier and apply selected credits before executing transactions; they need no additional consensus round on batch contents.Source: §3.1 · pp. 5–6

3.2 Block Proposal and Validation

  • Replicas validate incoming Quark transactions against local balances and pending credits, then propose blocks using contiguous available credit imports and valid transactions.Block validation checks metadata, import-frontier monotonicity, proofs, transaction validity, and the resulting state root before replicas vote; committed credit batches are imported exactly once.Source: §3.2 · pp. 6–7

3.3 CSRD

  • CSRD uses threshold signatures and erasure-coded message fragments so destination replicas can verify source authorization and reconstruct delivered messages.Commitments protect fragments against Byzantine replicas pairing valid signature shares with corrupted data.Source: §3.3 · p. 7

4 User Request Compilation

Request compilation decomposes cross-shard requests into ordered Quark transactions and offers fund atomicity, with a refund mechanism providing location atomicity for honest users. Prefunding can amortize funding transfers across later requests.

4.1 Atomicity

  • Fund atomicity ensures either all request inputs and outputs execute successfully or all involved funds remain controlled by their original account holders.Location atomicity strengthens this for honest users: on failure, their accounts remain in their initial states as if the request had not run.Source: §4.1 · p. 7

4.2 Base Compilation and Refund

  • The base compiler consolidates inputs on a coordinator shard, then commits one Quark transaction there to distribute funds to their destinations.Funding transactions move inputs from other input shards to the coordinator without changing account ownership; if any transaction is rejected, the process fails, and ownership remains unchanged until the final transaction.Source: §4.2 · pp. 7–8
  • An honest user can invoke a refund transaction on the coordinator shard to return migrated funds to their original shards after execution fails.The described procedure is guaranteed to succeed when the honest user does not issue conflicting transactions against the refund.Source: §4.2 · p. 8

4.3 Prefunding

  • Users anticipating repeated requests with a coordinator shard can prefund it in one batch, bypassing later funding transactions and amortizing their overhead while reducing latency.This applies when the user holds most funds on another shard and transfers a sufficient balance to the coordinator in advance.Source: §4.3 · p. 8

5 Security Analysis

QuarkShard establishes consistency, validity, and liveness for transaction and credit-batch processing. Its decomposition and recovery algorithms provide fund and location atomicity, while its transaction structure supports cross-shard front-running resistance and order-fairness BFT integration.

5.1 Consistency, Validity, and Liveness

  • Persistently valid Quark transactions and generated credit batches are eventually committed or imported, while committed blocks contain valid transactions and import each batch exactly once.The guarantees rely on BFT properties and verified, contiguous credit-batch importation.Source: §5.1 · pp. 8–9

5.2 Atomicity

  • Algorithm 2 provides fund atomicity: success executes all request inputs and outputs, while failure leaves funds under their original accounts’ control.If Algorithm 2 fails, an honest user can invoke Algorithm 3 to return reverted funding to the original shards, provided the user does not issue conflicting transactions against the refund.Source: §5.2 · p. 9

5.3 Anti-MEV

  • QuarkShard is cross-shard front-running free because observing one Quark transaction does not reveal the full request or predict subsequent transactions.An adversary can target a transaction only after its public broadcast, at the same difficulty as front-running an intra-shard request.Source: §5.3 · p. 9
  • Each shard processes its input-shard Quark transactions without inter-shard coordination, allowing non-sharding order-fairness BFT protocols to be deployed within each shard.This integration enforces order fairness across processed Quark transactions.Source: §5.3 · p. 10

6 Performance Analysis

The analysis bounds QuarkShard’s intra-shard and cross-shard costs and request latency. Its optimized communication scheme reduces cross-shard overhead, while multi-input requests can incur higher latency that prefunding can mitigate.

6.1 Intra-Shard Overhead

  • For a successful request spanning a input shards, base compilation without prefunding incurs IS-overhead aB; amortizing prefunding across l transactions reduces it to [(a−1)/l +1]B per request.On failure, x committed funding transactions incur xB; requesting location atomicity adds one BFT transaction when x > 0.Source: §6.1 · p. 10
  • Importing νB credit batches incurs logical intra-shard broadcast overhead mw + νBsπ, while most of this data requires only broadcast and only mw participates in consensus.Under the stated 100-shard assumptions, importation overhead is approximately 5.42 KB, or 0.26% of a classic 2 MB Bitcoin block.Source: §6.1 · p. 10

6.2 Cross-Shard Overhead

  • With optimized CSRD, QuarkShard’s cross-shard overhead is O(cλ) for a batch involving c distinct output accounts, compared with O(ncλ) for baseline CSRD.It transmits aggregated account credits rather than full transaction contents, which the passage says strictly outperforms transaction-granularity transmission.Source: §6.2 · pp. 10–11

6.3 Latency

  • A single Quark transaction, or a request with one input shard or prefunded inputs, has latency bounded by LBFT + LCSRD + Limp; multi-input base compilation is bounded by 2(LBFT + LCSRD + Limp).The multi-input latency trade-off relative to 2PC can be mitigated through mechanisms such as prefunding.Source: §6.3 · p. 11

7 Evaluation

In a four-region AWS deployment, QuarkShard scales to high throughput with sub-four-second latency and outperforms Kronos and 2PC across tested workloads. Its throughput is comparatively insensitive to output-shard counts, and per-account aggregation reduces cross-shard communication payload as batches grow.

7.1 Overall Performance

  • 1024 k requests per second peak throughput with latency below 4 seconds under normal workloads in a 96-node, 24-shard deployment using 2-input-2-output requests.Throughput grew continuously with nodes and shards; Figure 3 presents the scalability evaluation.Source: Figure 3 · p. 11, §7.1 · p. 12
  • 199.6%–210.7% of Kronos’s maximum throughput and 299.1%–314.8% of 2PC’s maximum throughput across the tested workload profiles.Figure 4 compares the protocols under 1-input-1-output and 2-input-2-output workloads.Source: Figure 4 · p. 11, §7.1 · p. 12

7.2 Performance under Varying Numbers of Inputs and Outputs

  • Throughput degradation was less than 0.5% as output shards increased from 1 to 4, versus 50.9% for 2PC and 60.2% for Kronos.Across tested input and output configurations, QuarkShard consistently outperformed both baselines in throughput; latency sensitivity was lower except when input shards increased from 1 to 2.Source: §7.2 · p. 12, Figure 5 · p. 12
  • With output shards fixed, throughput under 1 input shard was approximately 2.02× that under 2 input shards and 4.05× that under 4 input shards.The passage relates this pattern to base compilation’s IS-overhead, which grows linearly with input-shard count; Figure 5 also evaluates varying input and output counts.Source: §7.2 · p. 12, Figure 5 · p. 12

7.3 Cross-Shard Communication Overhead

  • As block batch size increased, per-account aggregation increasingly reduced amortized cross-shard communication payload; QuarkShard’s logical volume was consistently lower than Kronos’s.The comparison was conducted across batch sizes in a 64-node, 16-shard deployment with 1,000 active accounts per shard.Source: §7.3 · pp. 12–13, Figure 6 · p. 13

8 Discussion

QuarkShard compresses empty credit batches by conveying contiguous empty-height ranges with later non-empty batches. The design preserves exactly-once importation, and the protocol’s design and guarantees also apply to UTXO state.

8.1 Empty Credit Batch Compression.

  • Empty batches are omitted from transmission; the next non-empty credit batch carries the preceding empty-height range, which the destination imports atomically once earlier heights are imported.Range metadata preserves monotonic, contiguous progress and exactly-once importation; compressing empty batches adds no processing latency because they cause no observable state transitions.Source: §8.1 · p. 13

8.2 Application on UTXO Model.

  • In the UTXO model, inputs and outputs become UTXOs managed by their assigned shards, and cross-shard credit batches remain aggregated per account as consolidated UTXOs.Replicas replace balance updates with UTXO insertions and deletions and verify consumed UTXOs exist in the local set.Source: §8.2 · p. 13

9 Conclusion

QuarkShard replaces monolithic cross-shard request processing with independent Quark transactions while preserving fund or location atomicity, reducing overhead, and addressing cross-shard front-running and invalid-request flooding. Prior approaches coordinate shards under the monolithic paradigm, and sharding also creates fairness challenges around cross-shard transaction ordering.

9 Conclusion

  • QuarkShard decomposes requests into independent Quark transactions, guarantees fund or location atomicity, and reduces overhead while addressing cross-shard front-running and invalid-request flooding.The protocol targets intra-shard BFT and cross-shard communication overhead below conventional lower bounds.Source: §9 · p. 13

A.1 Cross-Shard Requests Processing

  • Kronos [20] and Logos retain traditional monolithic request processing and cannot overcome the lower bounds of IS-overhead at least (a+b)B and CS-overhead at least Ω(rλ).Source: §A.1 · pp. 15–16

A.2 MEV in sharding Blockchains

  • Aequitas addresses ordering within one consensus instance, while cross-shard fairness requires specialized protocol designs.Transaction-order manipulation is described as a major security challenge in blockchain systems.Source: §A.2 · p. 16
  • Cross-shard requests face a frontrunning exposure because input-shard consensus precedes a separate output-shard consensus, creating a higher-latency execution window than intra-shard transactions.Haechi identifies this gap and proposes finalization fairness; Prophet uses deterministic ordering to prevent conflicts among cross-shard transactions.Source: §A.2 · p. 16

B.1 Building Blocks

The building blocks specify threshold signatures, erasure coding, commitments, and intra-shard certification used by the protocol. Their stated parameters and guarantees define how messages are reconstructed, authenticated, and certified.

B.1 Building Blocks

  • With q = n−f and k = f +1, a threshold signature is accepted from q valid shares, while fewer than q shares cannot feasibly produce one.The interface includes share generation, verification, aggregation, and signature verification.Source: §B.1 · p. 16
  • A (k,n) erasure code encodes a message into n fragments, and any k distinct valid fragments reconstruct the original message exactly.The encoding is deterministic and each fragment has size O(|M|/k).Source: §B.1 · p. 16
  • The deterministic commitment scheme provides openings and verifies that a fragment occupies its committed position, with position binding after the commitment is fixed.The paper instantiates commitments with a Merkle tree, using the root as the commitment and a Merkle proof as an opening.Source: §B.1 · p. 16
  • Intra-shard certification yields an accepted certificate if and only if at least q replicas certify, and it can be embedded in intra-shard BFT without extra consensus rounds.A typical certificate uses a BFT block commit certificate and Merkle inclusion proof for the item hash.Source: §B.1 · p. 17

B.2 A Basic CSRD Instance

The basic CSRD instance sends erasure-coded fragments with signature shares and commitments to destination-shard replicas. A Logos-based variant uses paired replica transmission and source-side certification before transmission.

B.2 A Basic CSRD Instance

  • Algorithm 4 has each input-shard replica broadcast its signature share and designated erasure-coded fragment to all target-shard replicas, with commitments protecting fragment integrity.After receiving n−f valid shares, a target replica can form a certificate; the messages include fragments sufficient for reconstruction.Source: §B.2 · p. 17

B.3 CSRD Instance based on Logos

  • Algorithm 5 sends each fragment only to the destination replica with the matching index, which then propagates it within the destination shard.Unlike Algorithm 4, source replicas generate the certificate intra-shard before transmitting it.Source: §B.3 · p. 17
  • In deployment, certificate generation may occur alongside intra-shard BFT before transmission without compromising security under the model’s transmission requirement for honest replicas observing a valid certificate.Source: §B.3 · p. 17

B.4 Analysis

The analysis states correctness and validity for both CSRD instances and compares their cross-shard communication costs. Under n = 3f + 1, the two algorithms have different costs, with message-dominated bounds applying under a stated size condition.

B.4 Analysis

  • Both CSRD algorithms satisfy correctness and validity: the analyses use deterministic encoding and commitments for reconstruction, and honest source replicas’ participation to support accepted certificates.The Logos-based case relies on at least f +1 correctly opened fragments reaching honest paired destinations for reconstruction.Source: §B.4 · pp. 17–18
  • Under n = 3f + 1, Algorithms 4 and 5 transmit O(n|M|) and O(|M|) bytes across shards, respectively, when lower-order authentication metadata is ignored.Source: §B.4 · p. 18
  • For n = 3f + 1, the total costs including metadata are O(n|M| + n^2λlogn) and O(|M|+nλ(logn+log(p+1))) for Algorithms 4 and 5, respectively.When |M| = Ω(nλ(logn + log(p + 1))), message terms dominate, leaving O(n|M|) and O(|M|).Source: §B.4 · p. 18
Loading 2610.23014v1…