GridSMR: Causal Compression for Sharded Blockchains

• Scalable L1 execution matters for latency-sensitive decentralized-finance applications and agentic payments.Source: §1 · p. 1
• Accounts own and atomically execute their state; message-passing continuations let a request unfold as a causally dependent activation tree across accounts and shards.Atomicity is local to an activation, not the entire tree.Source: §1 · p. 2
• GridSMR replaces mandatory system-wide atomicity with application-selective coordination; failed continuations do not automatically unwind prior activations.Applications needing cross-account atomicity must coordinate it themselves, while unrelated execution paths can remain asynchronous.Source: §1 · p. 2
• Causal Liveness extends progress guarantees to internally generated continuations, which standard SMR liveness for client requests does not cover.Without that guarantee, previously generated work could stall while the system continues processing new requests.Source: §1 · p. 2
• Receipt-based designs place agreement boundaries between sequential cross-shard steps, so causal latency grows with chain depth.GridSMR instead executes generated work as soon as it is delivered.Source: §1 · pp. 2–3
• Leaders record per-shard execution traces, which followers independently replay and validate before consensus commits the schedule.Recording order matters because continuations arriving in different orders can produce different states; block-boundary validation avoids synchronizing intermediate execution.Source: §1 · pp. 3–4
• Causal Compression lets dependent cross-shard activations execute as they become available, potentially completing a chain within one block while independent accounts run concurrently.This holds subject to available execution time and avoids agreement between every cross-shard step.Source: §1 · p. 4
• 1.07M requests/s execution and 8.2× lower 16-hop causal-chain latency are reported; NEAR testnet required one additional agreement round per measured hop.The evaluation summary also identifies the 16-hop latency reduction as a headline result.Source: §1 · p. 4

2 Model

• Each cluster stores a complete replica, partitions execution among shards, and is treated as the unit of failure; compromising any shard makes its cluster Byzantine.The adversary may control at most f < n/3 clusters.Source: §2 · pp. 4–5
• Accounts own disjoint state on fixed shards, and activations can read or modify only their target account before generating continuations.The model leaves repartitioning outside its scope.Source: §2 · p. 5
• Causality is the transitive closure of continuation generation and same-shard execution order; shard blocks record ordered activations, including external activations and continuations.The per-shard orders are part of the global block because continuation arrival orders may differ across clusters.Source: §2 · p. 5
• Causal Liveness requires every continuation produced by a committed activation to eventually execute, beyond eventual execution of client requests.The model assumes partial synchrony: after GST, message delays are bounded.Source: §2 · pp. 5–6

3.1 Per-Shard State

• GridSMR divides per-shard state into ordered pending and executed activation lists, with external requests and generated continuations entering the mempool.External activations are assumed correctly signed and appear at most once in their shard’s mempool.Source: §3.1 · p. 7

3.2 Execution Model and Correctness Properties

• Shards execute concurrently but serialize their own activations; the system invariants govern activation authenticity, integrity, uniqueness, assignment, and causal timestamp order.Activation execution is atomic per shard, while mempool additions may occur concurrently.Source: §3.2 · pp. 7–8

3.3 Leader Protocol

• The leader validates external requests, assigns Lamport timestamps, executes activations, and sends generated continuations to their destination shards.A replacement leader resumes from shared state that includes generated continuations; unexecuted external requests must be resubmitted by clients.Source: §3.3 · pp. 8–9

3.4 Blocks and Replication

• Block Causality requires causally dependent activations to appear in monotonically ordered blocks, while allowing a continuation to execute in its parent’s block when it arrives before that block closes.This permits a causal chain to execute and commit in one global block, which the paper calls Causal Compression.Source: §3.4 · pp. 9–10

3.5 Follower Protocol

• At block boundaries, followers re-execute shard proposals and verify them before forwarding accepted blocks to the consensus representative.They check cross-shard continuations after re-execution; shadow state makes block application atomic, and successful verification preserves system invariants.Source: §3.5 · p. 10, Protocol Overview · p. 11

4 State Machine Replication

• GridSMR uses an existing SMR protocol to order global blocks across clusters, with sharded execution within each complete replica.The protocol assumes partial-synchrony progress after GST.Source: §4 · p. 11, §4.1 · p. 11

4.1 The Underlying SMR Protocol

• Unlike commit-then-execute systems, GridSMR speculatively executes blocks first and replicates execution traces that followers replay and validate.SMR orders and commits global blocks but does not reorder activations within shard blocks.Source: §4.1 · p. 12

4.2 Consensus Representative Protocol

• The consensus representative proposes a global block only when all local shards accept their shard blocks; a matching committed block is persisted, while a different or rejected block triggers rollback and replay as needed.The paper states that GridSMR satisfies Agreement, Validity, Liveness, and Causal Liveness.Source: §4.2 · pp. 12–13

Cross-Shard Execution

• Dependent continuations travel over the intra-cluster path, allowing causal chains to progress at execution speed before consensus commits their trace.Agreement is applied to the resulting execution trace rather than between dependent steps.Source: §5 · p. 13

Leader-Follower Parity

• Followers replay per-shard traces independently and check cross-shard dependencies at block boundaries, keeping their validation parallel across shards.This supports follower validation at a rate comparable to leader execution.Source: §5 · p. 13

Decoupling Execution from Block Timing

• Because blocks record completed execution, responses may be optimistic before finality and activations need not finish within a block interval.Execution is not synchronized with block boundaries.Source: §5 · p. 13

Horizontal scalability

• Approximately 1.07M requests/s at 160 execution cores, with per-core throughput nearly constant across a 10× increase in compute resources.The single-validator experiment spans 16 to 160 execution cores.Source: §6 · p. 14, Figure 3 · p. 14
• 193,000 committed requests/s for replicated YCSB is an 11.9× gain over 12× more compute; fungible-token throughput scales 9.3× to approximately 65K committed transfers/s.The cross-shard share of token transfers rises from 67% at 3 shards to 98% at 47 shards while throughput remains close to linear.Source: §6 · p. 14, Figure 3 · p. 14

Leader–Follower Parity

• Across 24 cross-shard workload runs at 44–100% of sustainable load, the slowest follower shows no persistent block-height lag.The leader-to-slowest-follower gap grows at an average fitted rate of 0.030 blocks/s (standard deviation 0.212) and decreases in 10 runs.Source: §6 · p. 14

Causal Compression

• 8.2× lower median latency at 16 hops under GridSMR than deferred execution: 222 ms versus 1,822 ms.Deferred execution adds approximately 103 ms per causal step against a 100 ms block interval, while GridSMR adds approximately 4 ms.Source: §6 · p. 15, Figure 4 · p. 15

Real-system validation

• On NEAR testnet, every measured causal hop across depths 2–16 and 80 runs required one additional agreement round.TON could not provide a cross-shard baseline because its basechain operated as a single shard during these measurements.Source: §6 · p. 15

Fault tolerance

• After leader failure during sustained YCSB load at 2,000 requests/s, surviving validators return to pre-failure throughput after configured view-change timeouts.Across three runs, the experiment validates recovery rather than peak-load failover.Source: §6 · p. 15, Figure 4 · p. 15

7 Related Work

• Unlike prior systems that restrict cross-shard operations known in advance or use successive asynchronous receipts, GridSMR localizes atomicity to activations and supports Causal Liveness.GridSMR provides asynchronous composability within a Byzantine-replicated sharded L1, unlike CIRC’s centralized coordinator.Source: §7 · p. 16

A Protocol Pseudocode

• The leader selects eligible activations, executes them, sends generated continuations to destination shards, and closes blocks by proposing each shard’s execution order.Selection may use any policy without indefinite postponement; the base implementation uses FIFO.Source: A Protocol Pseudocode · pp. 19–20
• Followers re-execute proposed shard orders, verify causal consistency, and forward valid blocks for consensus; invalid proposals are reported instead.Follower validation checks external activations and verifies reported continuations against internally generated ones.Source: A Protocol Pseudocode · pp. 21–22

B.1 Leader Protocol Proofs

• Theorem 3.2 states that Algorithm 2 preserves a valid system state, proved by induction over execution steps.The proof considers adding activations to mempools and applying activations.Source: §B.1 · p. 23
• The proof maintains authenticity, integrity, no duplication, and well-formedness as activations enter and leave shard mempools.External activations are signature-checked; continuations must be generated by prior execution and appear at most once.Source: §B.1 · p. 23
• Lamport timestamps preserve happens-before order for same-shard activations, directly triggered cross-shard continuations, and longer causal chains.The proof derives the general chain case by induction and transitivity.Source: §B.1 · pp. 23–24

B.2 Blocks and Replication Proofs

• Algorithm 2 maintains block causality: within-shard order is preserved, and cross-shard continuations cannot enter a block earlier than their triggering activation.The proof extends the direct-dependency cases to transitive causal chains by induction.Source: §B.2 · p. 24
• A correct leader’s global proposal is valid because shard-local properties persist through execution and causal dependencies are preserved in the proposal.The proof combines the state invariant with the proposal’s activations since the previous block was closed.Source: §B.2 · pp. 24–25
• Applying the global proposal to the state at the end of block k −1 produces a correct state at the end of block k.The proof uses the fact that a causal predecessor is either already executed or included in the global proposal.Source: §B.2 · p. 25
• Authenticity, no duplication, and well-formedness can be checked by each shard from its local execution history, without cross-shard dependencies.The proof notes that these properties support marking a shard proposal invalid during follower verification.Source: §B.2 · p. 25

• Lemma B.2 establishes that sequential execution in the proposal’s activation order yields the same final state from the same initial state.Source: Follower Protocol Correctness · p. 25
• Lemma B.9 establishes that successful execution across all shards preserves system state invariants.Source: Follower Protocol Correctness · p. 25
• Lemma B.11 establishes that, after GST, a correct follower with the leader’s prior state completes verification when the leader is correct.Source: Follower Protocol Correctness · p. 25

Execution Determinism

• The same initial state and shard proposal produce the same final state when activations execute sequentially in proposal order.Source: Execution Determinism · p. 25
• Followers may tolerate transient cross-shard inconsistencies during parallel execution, then verify invariants at block boundaries before state becomes externally visible.Shards execute without intershard coordination and apply blocks atomically.Source: Execution Determinism · pp. 25, 26, 30
• Every verified continuation has a valid executed source, and successful block execution preserves Integrity and prevents duplicate activations.The source relationship is established through pending activations, the mempool, and executed activations.Source: Execution Determinism · pp. 26–27
• Successful execution makes local timestamps strictly increase and preserves the Happens-before Relation: causally ordered activations have increasing timestamps.Source: Execution Determinism · pp. 28–29
• Timestamp-check failures by a same-state follower indicate that the leader did not correctly apply the Lamport timestamp mechanism.Source: Execution Determinism · p. 30
• If the leader is correct and sends a proposal after GST, a correct follower with the same pre-block state successfully completes execution across all shards.Source: Execution Determinism · p. 31

C GridSMR Consensus Representative Protocol and Correctness

• Correct clusters that commit the same sequence of blocks reach the same system state.Source: C GridSMR Consensus Representative… · p. 32
• The representative proposes a global block to SMR after receiving proposals from all shards for that block.Source: C GridSMR Consensus Representative… · p. 33
• An activation in the leader’s mempool is eventually selected and executed if the leader continues executing and selection is fair.The base policy is FIFO; alternative policies may be used if they prevent indefinite postponement of eligible activations.Source: C GridSMR Consensus Representative… · p. 34
• Every continuation generated by a committed activation eventually executes and commits, establishing Causal Liveness.Source: C GridSMR Consensus Representative… · p. 35
• GridSMR satisfies Agreement, Validity, Liveness, and Causal Liveness.Source: C GridSMR Consensus Representative… · p. 35

D Additional Performance Analysis

• Colocating shards in one data center reduces cross-shard communication latency, while inter-cluster consensus occurs at block boundaries and can use compact commitments.Source: D Additional Performance Analysis · p. 36
• Clients can receive optimistic results upon execution and use them for follow-up activations before the first activation is finalized.Clients needing finality can track consensus progress or wait for confirmation.Source: D Additional Performance Analysis · p. 36

E.1 System-Level Optimizations

• GridSMR can pipeline independent activations, and an activation may span block intervals because execution precedes consensus and completed work is packaged retroactively.Per-activation computation remains gas-metered, but its bound need not fit within one block interval.Source: §E.1 · p. 37

E.2 Policy and Mechanism Choices

• A malicious leader may reorder continuations across activation trees, potentially violating application-level ordering expectations.Source: §E.2 · p. 38
• Applications can use a synchronizer account for stronger ordering, at the cost of reduced parallelism on affected paths.Follower verification also requires a phase transition after all shards finish activation execution; alternatives to timeouts add intra-cluster synchronization.Source: §E.2 · p. 38