GridSMR: Causal Compression for Sharded Blockchains

GridSMR: Causal Compression for Sharded Blockchains

arXiv:2610.01443v1 [cs.DC] 1 Oct 2026

Shir Cohen, Adam Alon, Raz Omessi, Amir Sarid, Dana Shamir, and Ofir Zohar Gen Labs, Tel Aviv, Israel shir.co@gmail.com, adamalonil@gmail.com, romessi@gmail.com, amir@sarid.io, dana.shamir01@gmail.com, ofir.z@genlabs.co

Abstract. We present GridSMR, a sharded blockchain that scales execution horizontally while allowing dependent cross-shard operations to progress within a single block. Existing sharded systems typically place coordination between dependent cross-shard steps, making latency grow with causal depth. GridSMR localizes atomicity to individual accounts and executes crossaccount work asynchronously. Using an execute-before-agree architecture, dependent operations execute across shards as they become available, while consensus later validates and commits the resulting schedule. This enables Causal Compression: cross-shard latency need not grow with the causal depth of a computation. GridSMR scales single-validator execution to 1.07M requests/s and four-validator execution to 193K committed requests/s, while reducing 16-hop causal-chain latency by 8.2× versus deferred execution. Keywords: Blockchain · Sharding · Byzantine Fault Tolerance

1

Introduction

The blockchain ecosystem continues its search for scalable Layer 1 (L1) infrastructure capable of supporting the next generation of decentralized applications, including latency-sensitive DeFi applications [13, 14, 18] and agentic payments [11]. While consensus protocols have approached theoretical limits, execution remains a central scalability challenge. We present GridSMR, a sharded smart-contract platform designed to scale execution horizontally without imposing a consensus delay on every dependent cross-shard step. Independent accounts execute concurrently across shards, while chains of dependent cross-shard operations can progress within a single agreement interval. As a result, GridSMR combines increasing execution parallelism with low-latency cross-shard computation. Blockchains conventionally structure execution around transactions. But “transaction” is not merely terminology: it imports ACID semantics from database systems [17]. In particular, atomicity requires all state touched by a transaction to be updated all-or-nothing. Sharding complicates this model by partitioning

2

S. Cohen et al.

state across independently executing shards. When a transaction spans multiple shards, preserving atomicity therefore requires coordination across them. We challenge the assumption that ACID guarantees must be provided systemwide by the L1. Large-scale distributed systems commonly narrow transactional scope through partitioned state ownership, asynchronous communication, and weaker consistency models [25, 30, 31]. Blockchains have moved partially in this direction. Guerraoui et al. [15] explore such a model for cryptocurrency systems, while Sui [4, 10] extends independent state ownership to a general-purpose L1. However, Sui distinguishes owned from shared objects, with operations on shared objects still requiring coordinated ordering through consensus. GridSMR adopts independently owned, asynchronous execution as the uniform execution model of the L1. State is partitioned into accounts, each of which owns its state and executes activations atomically over that state. Accounts do not directly modify one another. Instead, computation across accounts proceeds by message passing: an activation may generate continuations targeting other accounts. Each continuation is an activation to be executed by its target account and may itself generate further continuations. A client request can therefore unfold as a tree of causally dependent activations spanning many accounts and shards. Atomicity is local to an activation rather than to the entire tree. An activation tree is not a transaction: if one continuation fails, preceding activations are not automatically unwound, and applications requiring atomicity across accounts must implement that coordination themselves. This weakens the default transactional semantics, but does not remove the ability to coordinate across accounts. Applications can introduce stronger coordination where needed, for example by serializing sensitive operations or placing state that must be updated atomically in the same account, while leaving independent execution paths asynchronous. Recent sharded AMM designs similarly partition state to gain parallelism while recovering application-specific guarantees where necessary [1,7]. Such coordination reduces parallelism only for the affected operations, rather than imposing that cost on every cross-account computation. GridSMR therefore replaces mandatory system-wide atomicity with application-selective coordination. This model shifts a different responsibility to the L1: it must reliably carry asynchronous computation to completion. In particular, if activation A executes and generates continuation B, then B must eventually execute – a property we call Causal Liveness. Standard SMR liveness does not imply it: a system may continue processing new client requests while indefinitely failing to execute previously generated work. Existing sharded blockchains also use asynchronous messages for cross-shard communication [12, 27]. The key difference is when causally generated work becomes eligible for execution. Consider three accounts A, B, and C on different shards, where A invokes B, and the result of B causes an invocation of C: Ashard 1 → Bshard 2 → Cshard 3 . In receipt-based designs, B can execute only after the step containing A crosses an agreement boundary, and C must wait for another. Each sequential cross-shard step therefore consumes an agreement

GridSMR: Causal Compression for Sharded Blockchains

Leader

Followers

Cluster 1

shard 1

shard 2

...

shard m

consensus representative

Cluster 2

shard 1

shard 2

...

shard m

consensus representative

shard 1

shard 2

...

shard m

consensus representative

3

...

Cluster n

Fig. 1: GridSMR architecture: clusters replicate execution across shards, with one leader cluster and multiple follower clusters.

interval, making latency linear in causal depth. GridSMR instead lets generated work execute as soon as it is delivered: A → B → C may all progress before the next agreement step. GridSMR partitions accounts across execution shards and replicates the full set of shards across independently operated clusters. Thus, sharding scales execution within each replica, while Byzantine replication operates across complete clusters. The shards of a cluster are co-located, so a continuation that crosses shards travels over a fast intra-cluster path, while the slower inter-cluster path carries only replication and consensus traffic. During each block interval, one cluster acts as leader and executes activations across its shards as they become available. It produces per-shard traces recording client-submitted activations, internally generated continuations, and their execution order. Follower clusters independently re-execute and validate these traces before consensus finalizes the block. Recording the execution order is necessary because activation execution is deterministic given an account state and input, while the concurrent cross-shard schedule is not: continuations generated on different shards may arrive at a destination shard in different orders and thereby induce different states. GridSMR therefore uses a speculative execute-before-agree pipeline: execution determines a candidate schedule, and consensus commits that schedule only after independent validation. The execution is provisional rather than final; if the proposed block is not committed, speculative state may be discarded or rolled back. The broader idea of executing before final agreement has substantial precedent in distributed systems [3, 19, 21, 24, 33]. These systems show that execution need not always follow a previously agreed total order. For our architecture, execute-before-agree is fundamental: multiple dependent cross-shard activations can execute within one agreement interval only if execution advances before their schedule is globally agreed. The challenge is validating an execution-generated schedule that unfolds causally across independently executing shards, without trusting the replica that produced it. Prior work addresses parts of this problem. Zyzzyva supports speculative execution under Byzantine faults, but replicas execute an order first proposed by the primary [19]. Rex is closer to GridSMR: execution determines a causal trace that is later agreed upon and replayed, but Rex assumes crash

4

S. Cohen et al.

faults [16]. GridSMR brings this execute-generated trace model into a Byzantine setting where execution itself may generate new cross-shard work. Followers must therefore validate both the recorded execution order and the provenance of cross-shard continuations. Crucially, this validation must not reintroduce crossshard coordination. The key to validating such an execution without restoring cross-shard coordination is that validity need not be established after every intermediate activation. It is sufficient for the execution represented by a block to satisfy the system’s validity conditions at the block boundary. Because execution is deterministic given the initial account state and per-shard execution order, follower shards can replay their traces independently, without maintaining a globally synchronized intermediate execution prefix or reproducing the leader’s real-time continuation arrival order. Moreover, validation need not delay ongoing execution: shards may continue executing speculatively while earlier blocks are being validated and finalized. The result is that consensus no longer sits between dependent activations: a continuation may execute as soon as it becomes available at its destination, and that activation may immediately generate further work. Multiple causally dependent cross-shard activations can therefore execute within one agreement interval instead of requiring a new agreement interval for every causal step – a property we call Causal Compression. Subject to available execution time, a causal chain spanning multiple shards can execute and commit within a single block rather than incur block latency proportional to its causal depth. At the same time, independent accounts execute concurrently across shards. The architecture therefore supports both parallel execution and low-latency causal computation without requiring agreement between every cross-shard step. Our contributions are: – Causal execute-before-agree: a Byzantine-replicated sharded architecture that executes causally generated cross-shard work before agreement and validates the resulting schedule independently. – Causal Compression: dependent cross-shard chains can execute within one agreement interval rather than one interval per causal step. – Causal Liveness: a formal progress guarantee for continuations generated by committed computation. – Evaluation: GridSMR scales execution to 1.07M requests/s and reduces 16hop causal-chain latency by 8.2×; on NEAR testnet, every measured causal hop required an additional agreement round.

2

Model

System and fault model. GridSMR consists of n clusters. Each cluster contains m shards and one consensus representative (Figure 1). GridSMR uses a black-box Byzantine SMR protocol to commit global blocks across clusters. Every cluster stores a complete replica of the application state. All clusters use the same

GridSMR: Causal Compression for Sharded Blockchains

5

fixed partition of that state among their shards, and this partition is known to every cluster. Thus, GridSMR shards execution within each replicated cluster; replication itself remains across complete clusters. At any time, one cluster is designated as the leader and the remaining n − 1 clusters act as followers. The cluster, typically operated as a single administrative unit, is the unit of failure. Shards within a correct cluster trust one another and communicate without consensus. If any shard of a cluster is compromised, we consider the entire cluster Byzantine. The adversary may control at most f < n/3 clusters. Accordingly, GridSMR assumes no separate fault threshold for individual shards. Communication is partially synchronous. After an unknown global stabilization time (GST), inter-cluster and intra-cluster message delays are bounded. We let δexec bound the time for a correct follower cluster to process a global block, and δintra bound intra-cluster communication delay. Execution model. In GridSMR, application state is partitioned among a set of accounts A, each of which owns disjoint state and is assigned to one shard. An account is therefore never split across shards, and a shard’s size is the combined state of the accounts assigned to it; we treat this assignment as fixed and leave repartitioning outside our scope. Computation proceeds through activations. An activation is a uniquely identified request containing a target account and an application-defined payload. An activation may read or modify only its target account’s state. It is therefore executed by the shard to which its target account is assigned. An activation submitted by a client is external. Executing an activation A against its target account’s state s produces an updated state s′ and a sequence C of zero or more new activations, called continuations: Execute(s, A) = (s′ , C). A continuation’s identifier cryptographically binds its immutable contents; execution-assigned metadata such as its timestamp and block identifier is excluded. Execution is deterministic: the same pair (s, A) always produces the same pair (s′ , C). This property allows followers to verify a leader’s proposal through re-execution. Causality. We define A ≺ A′ as the transitive closure of causal generation (A → A′ ) and same-shard execution order. This is the happens-before relation over activations. Problem definition. For replication, executions are grouped into global blocks. Let k denote a block index. A global block B k contains one shard block Bik per shard i, where Bik is the ordered sequence of activations executed by shard i since its preceding block boundary. Applied to the preceding committed state, these per-shard execution orders determine the resulting state and generated continuations. The shard blocks include both external activations and internally generated continuations. Because concurrently generated continuations may arrive in different orders at different clusters, replicas cannot derive a common per-shard order from their local arrival orders. The per-shard execution orders are therefore part of the global block agreed upon through SMR. GridSMR implements state machine replication and must satisfy:

6

S. Cohen et al.

k closes

Client shard 1

1 Leader

Cluster 1

activation request

optimistic response

B

k closes

SMR

order proposal

shard 1

A k closes

shard 2

4 Cluster n

shard 2

without Block Causality

revalidation execution 3

...

6 Finalization

local execution

Cluster 2

Followers

A k closes

2

B

5

revalidation execution

(a) Execution workflow

with Block Causality

(b) Block Causality

Fig. 2: GridSMR execution workflow and Block Causality. (a) A client submits an external activation to the leader 1 , where the target shard executes it immediately and may generate cross-shard continuations without waiting for consensus. The leader may return an optimistic result 2 . At the block boundary, each shard’s recorded execution order forms part of a global executiontrace proposal sent to follower clusters 3 . Followers re-execute the proposed traces against their local state 4 and verify authenticity, continuation generation, and causal dependencies 5 ; shards verify independently and need not reproduce the leader’s continuation arrival order. Once accepted, the cluster participates in intercluster SMR, which commits a global block sequence 6 . Clusters whose speculative state diverges from the committed block roll back and apply the committed execution. (b) Block Causality ensures that activations appear in monotonically ordered blocks with respect to their causal dependencies.

– Agreement: all correct replicas commit the same sequence of blocks in the same order. – Validity: every committed block satisfies the protocol’s validity predicate. – Liveness: every activation submitted by a correct client eventually executes. As is standard, Liveness is eventual: the leader controls mempool selection within its view, so time-bounded inclusion is a property of the underlying protocol’s leader rotation rather than of the execution layer. Cross-shard execution creates an additional obligation. Standard Liveness covers requests submitted by correct clients. It does not imply progress for continuations, which are generated internally and may cross shard boundaries. Without an explicit guarantee, a committed activation tree could therefore stall after any cross-shard step even though standard Liveness continues to hold. We therefore define Causal Liveness, which extends progress to internally generated continuations: Definition 1 (Causal Liveness). If a committed activation A produces a continuation A′ , then A′ eventually executes.

3

The GridSMR Architecture

Building on Section 2, we first specify the per-shard protocol state, its invariants, and leader execution (Sections 3.1–3.3); we then describe block construc-

GridSMR: Causal Compression for Sharded Blockchains

7

tion and replication (Section 3.4), followed by follower verification (Section 3.5). Leader and follower shards run Algorithms 2 and 3 respectively, over the shared structures of Algorithm 1 (Appendix A). Figure 2a summarizes the end-to-end execution and validation pipeline. 3.1

Per-Shard State

Each activation carries protocol metadata: sid identifies its destination shard, ts is its Lamport timestamp, and is_external and signature distinguish and authenticate client submissions. A ShardBlock packages one shard’s ordered execution trace for replication. The corresponding data structures appear in Algorithm 1 (Appendix A). Each shard i maintains the following ordered lists: mempooli An ordered list of activations pending execution. executedi An ordered list of activations executed by the shard, including both finalized activations and activations awaiting SMR finalization. Activations enter the mempool from two sources: external activations submitted by clients, and continuations spawned by previously executed activations. We make the following assumption about the external activations. Assumption 3.1. Every external activation in the leader’s mempool is correctly signed by a client, and each external activation appears at most once in its associated shard’s mempool (duplicate submissions from clients are filtered before insertion). 3.2

Execution Model and Correctness Properties

Shards execute pending activations concurrently, while each shard serializes its own execution. Formally, an execution at the leader consists of per-shard se0 1 quences {σi }m i=1 where σi = σi σi . . . represents steps taken by shard i, each being either an ApplyActivation invocation (Algorithm 2) or adding an activation to mempool (Algorithm 2). Shards execute concurrently; steps within each σi are totally ordered, but steps across different shards are only partially ordered by causal dependencies. We model ApplyActivation as atomic: it acquires a lock on shard i before executing and releases it afterward, ensuring each shard processes at most one activation at a time. Adding an activation to the mempool is lock-free and can occur concurrently with execution. The relative ordering between a mempool addition and a concurrent ApplyActivation is determined by which operation accesses the mempool first during execution. This model ensures the execution history is equivalent to some sequential execution. The system state consists of (executedi , mempooli ) for all shards i ∈ {1, . . . , m}, together with all account state and shard metadata (e.g., local timestamps).

8

S. Cohen et al.

System State Invariants We now formalize what constitutes a valid system state. These invariants define valid execution at the leader and later (Section 3.5) serve as the validity predicate for follower verification. A valid system state satisfies the following properties: Authenticity Every external activation in executedi is signed correctly by a client. Integrity For every continuation A′ in executedi or mempooli , there exists an activation A ∈ executedj such that A → A′ . No Duplication Each activation appears at most once in executedi ∪mempooli . Well-formedness Every activation is included in its associated shard. Happens-before Relation For any two activations A and A′ in executedi and executedj respectively, if A ≺ A′ , then A.ts < A′ .ts. Note that Authenticity and Integrity are dual properties that validate activation origins: Authenticity verifies external activations come from legitimate clients, while Integrity verifies continuations were correctly generated by prior executions. 3.3

Leader Protocol

The leader per-shard protocol is described in Algorithms 1 and 2 (Appendix A). Its core is ApplyActivation, which repeatedly selects and processes eligible activations from the mempool. The leader repeatedly selects and processes an activation from the mempool, subject to dependencies we formalize later. The leader first validates external activations by checking their signatures. Next, it assigns a Lamport timestamp to the activation by taking the maximum of the shard’s current timestamp and the activation’s timestamp (0 for external activations), then incrementing by one. This ensures the happens-before relation is preserved. The activation is then added to the executed list and executes. The execute function performs two critical roles: it runs the activation’s logic to generate any follow-up continuations, and it updates the system state according to the writes produced during execution. Each generated continuation inherits the timestamp of its parent activation, maintaining causal ordering across shards. Finally, the generated continuations are sent to their destination shards. When a shard receives a continuation, it adds it to its mempool, making it available for future execution. This protocol ensures that activations are executed in a causally consistent order while maintaining the integrity and correctness properties of the system state, which we formally prove in Appendix B.1: Theorem 3.2. Algorithm 2 preserves a valid system state. Leader Replacement. When the leader cluster fails or becomes unresponsive, a new leader cluster is selected to continue execution. The new leader resumes from the system state that all correct clusters maintain (proven in Appendix C), which includes all continuations generated during execution.

GridSMR: Causal Compression for Sharded Blockchains

9

External activations submitted to the failed leader but not yet executed are not included in this shared state. Clients detect leader failure through timeouts and resubmit pending activations to the new leader. Assumption 3.1 prevents duplicate execution by filtering resubmitted activations that already appear in the system state; this assumption is straightforward to enforce in practice through standard deduplication mechanisms. In GridSMR, leader selection is coupled with the underlying SMR protocol. The cluster currently leading the consensus protocol (e.g., PBFT leader [6]) serves as the execution leader. View changes in the consensus protocol trigger execution leader changes, with the new leader initializing from some agreed upon checkpoint. 3.4

Blocks and Replication

The leader continuously executes activations, whereas replication proceeds in discrete blocks. Each shard therefore divides its local execution history into ordered intervals. At the end of an interval, CloseBlock packages the activations executed since the preceding boundary as a shard block, sends it to the corresponding follower shards and the leader’s consensus representative, and advances the local block identifier bid. Each executed activation records the identifier act.bid of the interval in which it executed. ApplyActivation and CloseBlock synchronize their access to bid; for clarity, the pseudocode models both operations as atomic. CloseBlock performs only bookkeeping: it does not execute an activation or modify account state, executedi , or mempooli . Thus, adding CloseBlock as a protocol step preserves the system state invariants established above. Valid Proposals. The leader sends each shard’s block to followers as a shard proposal : the ordered activations executed by that shard during the block interval. A global proposal for block k collects one shard proposal from each of the m shards. It must maintain system correctness when applied. Formally: Definition 2 (Valid Global Proposal). A global proposal is valid if applying all shard proposals to a correct system state results in another correct system state, maintaining all system state invariants. Since causal dependencies cross shards, naively batching independently formed shard proposals may violate validity. We therefore introduce Block Causality, which requires activations to appear in monotonically ordered blocks with respect to their dependencies: Block Causality. For any two activations A and A′ in executedi and executedj , respectively, if A ≺ A′ , then A.bid ≤ A′ .bid. Block Causality constrains how independently closed shard intervals align (Figure 2b). Suppose shard 1 has advanced to block k + 1 while shard 2 is still constructing block k. If activation a now executes on shard 1 and generates continuation a′ for shard 2, executing a′ in block k would place it before its parent. The leader therefore sets a′ .min_bid = a.bid = k + 1, and shard 2 cannot select a′ until it reaches that block.

10

S. Cohen et al.

The bound does not impose an unnecessary block barrier: when a continuation reaches its destination before that shard closes the parent’s block, it may execute in the same block. Repeating this across shards allows a causal chain to execute and commit in one global block, a property we call Causal Compression. The minimum block identifier preserves Block Causality, with proofs deferred to Appendix B.2 Lemma 3.3. Algorithm 2 maintains Block Causality. With Block Causality established, we can show that the leader generates valid proposals: Lemma 3.4. A correct leader executing CloseBlock at all shards creates a valid global proposal. 3.5

Follower Protocol

In the previous subsection, blocks partitioned the leader’s continuous execution into discrete units for replication. Blocks also define the checkpoints at which followers validate execution before participating in consensus. Follower shards receive the leader’s block proposals and re-execute them locally, forwarding a block to the cluster’s consensus representative only if verification succeeds. The pseudocode appears in Algorithms 3 and 4 (Appendix A). Follower State A follower, like the leader, maintains executed and mempool fields for each shard. However, followers process blocks atomically – either the entire block is applied, or none of its activations are. During verification, speculated and pending_activations hold the activations that would be added to executed and mempool. If verification succeeds, these shadow structures are merged into permanent state (making the block application atomic). Otherwise, they are discarded. Followers also maintain ts_at_execution, which records the local timestamp at which each continuation is executed and is used to verify the leader’s Lamport timestamps. Followers also maintain block-boundary checkpoints of executed, mempool, the local timestamp, and account state. If a block is not committed, the consensus representative restores the preceding checkpoint (Section 4.2), allowing the follower to safely retry under a new proposal. Protocol Overview When a follower receives a shard proposal for block k, it first ensures that blocks are processed sequentially, buffering the proposal if k ̸= bid. The follower then invokes IsValidBlock, which verifies the proposal in two phases. In the first phase, the follower speculatively re-executes the proposed activations in order. For each activation, it checks shard assignment and the Block Causality constraint min_bid ≤ bid. External activations can be verified immediately by checking signatures, duplication, and Lamport timestamp computation, since they have no dependencies on other shards. For continuations, the

GridSMR: Causal Compression for Sharded Blockchains

11

follower executes them speculatively, recording the local timestamp at execution and sending any generated continuations to their destination shards within the cluster. However, continuations cannot yet be fully verified: verification depends on receiving matching continuations from other shards. In the second phase, the follower waits until δexec + δintra from the start of block processing, then verifies cross-shard continuations. The verification function then validates that the leader’s reported continuations match those generated locally. For each continuation, it checks that a matching locally generated continuation exists in pending_activations or mempool, and that its Lamport timestamp was computed correctly. If verification succeeds, the follower merges speculated into executed and pending_activations into mempool, then forwards the shard block to the consensus representative. Otherwise, it reports the block as invalid and discards the speculative state. This protocol yields an important correctness property: followers need not enforce cross-shard validity after each activation. Activations on different shards may be re-executed in parallel, so a continuation may be processed before its parent completes on another follower shard. The protocol checks cross-shard validity only at the block boundary, after re-executing the entire proposal and allowing its continuations to arrive. Shadow state and atomic block application ensure that these temporary inconsistencies never become visible. Appendix B.3 proves that successful block verification preserves the system state invariants (Lemma B.9) and that correct followers accept a correct leader’s proposal under the stated timing bounds (Lemma B.11).

4

State Machine Replication

Traditional SMR systems replicate a single state machine across nodes, limiting scalability. GridSMR implements SMR with horizontal scalability through sharding: each replica is a cluster of shards that execute in parallel. To coordinate between clusters, GridSMR uses an existing SMR protocol as a building block. This creates a two-level structure: sharded execution within clusters, and SMR-based consensus between clusters. 4.1

The Underlying SMR Protocol

GridSMR uses a standard SMR protocol as a black-box component to order global blocks and ensure agreement among clusters. Each cluster has a consensus representative responsible for participating in the SMR protocol with representatives from other clusters. For liveness, we assume the standard partial-synchrony progress condition of the underlying SMR protocol: after GST, its leader-replacement mechanism eventually installs a correct leader that remains active long enough to complete a proposal. At block height k, the representative submits the global block B k = k ]), containing one verified shard block from each of the m shards. (k, [B1k , . . . , Bm

12

S. Cohen et al.

However, GridSMR’s usage of SMR differs from traditional systems in several ways. First, GridSMR uses execute-before-agree rather than commit-thenexecute: blocks are executed speculatively before consensus, and SMR commit serves as after-the-fact validation. The SMR “execution” step simply persists precomputed state to disk. Second, the SMR clients are the execution leader (system nodes), not end users. End users interact with the execution layer via the mempool. Third, and most significantly, the replicated global block is an execution trace rather than merely a batch of external requests. Each shard block records the leader-selected order in which both external activations and internally generated continuations executed. Followers replay and validate this proposed order instead of deriving an order from local continuation arrival times, which may differ across clusters. The underlying SMR protocol orders and commits a sequence of global blocks; it does not reorder activations within their shard blocks. This differs from traditional SMR, where ordered requests originate externally from clients. GridSMR’s validity predicate is whether executing a block maintains all system state invariants – formally, whether the IsValidBlock function returns true at all shards. Commit certificates for committed blocks are those of the underlying protocol, inherited unchanged for use by light clients and external verifiers. 4.2

Consensus Representative Protocol

The consensus representative coordinates between a cluster’s shards and the inter-cluster SMR protocol (Appendix C, Algorithm 5). When shards complete block execution and verification, they send their results (valid or invalid) to the consensus representative. The representative collects shard blocks with the same block id, binds them together to form the global block B k , and proposes it to SMR. The validity predicate for SMR is whether all shards within the cluster accepted their respective shard blocks – that is, whether IsValidBlock returned true at all shards. A correct representative votes only for a global block whose shard blocks exactly match those accepted by its local shards. If any shard rejected its block, the representative does not propose to SMR, allowing the underlying consensus protocol to handle leader replacement through its standard fault tolerance mechanisms. Once SMR commits a global block, there are two cases. If the committed block matches the block that the cluster executed speculatively, the representative persists the pre-computed state to disk, creating a checkpoint. Otherwise, if the committed block differs, the representative triggers rollback to the previous checkpoint, re-executes the committed block, and then persists the resulting state. This could be the case, for example, if the leader is Byzantine and sends a different proposal to a single follower. If SMR rejects a block (due to insufficient agreement, timeout, or view change), the representative coordinates rollback across all shards in the cluster, restoring state from the checkpoint at the previous block. The specific choices of SMR protocol and persistence mechanism (logging, snapshots, etc.) are orthogonal to GridSMR’s core design. Similarly, in practice

GridSMR: Causal Compression for Sharded Blockchains

13

consensus would operate on compact commitments (e.g., Merkle roots of shard block hashes) rather than full block data, requiring additional construction and verification steps, but we omit this standard optimization for clarity. Appendix C proves that these mechanisms satisfy the properties stated in the Model: Theorem 4.1. GridSMR satisfies Agreement, Validity, Liveness, and Causal Liveness.

5

Performance and Design Implications

The execute-before-agree architecture has three important consequences for system performance. Cross-Shard Execution. Because a cluster’s shards are co-located, dependent continuations travel over the intra-cluster execution path rather than through consensus. Causal chains can therefore progress at execution speed, with agreement applied to the resulting execution trace rather than between dependent steps. Leader-Follower Parity. Execute-before-agree is useful only if followers can validate execution at a rate comparable to the leader. GridSMR enables this by replaying per-shard traces independently and checking cross-shard dependencies at block boundaries, leaving execution across shards parallel. Decoupling Execution from Block Timing. Because blocks record completed execution rather than prescribe work that must finish within a block interval, execution need not be synchronized with block boundaries. This permits both optimistic responses before finality and activations whose execution duration need not fit within a block interval. Further discussion of communication, speculative execution, long-running activations, and follower verification appears in Appendices D and E.

6

Evaluation

We evaluate GridSMR along three dimensions: horizontal execution scaling, the latency benefit of Causal Compression over deferred execution, and recovery from speculative execution after leader failure. We additionally validate the deferredexecution model against NEAR testnet. Our implementation comprises approximately 460K lines of Rust across execution, consensus, networking, storage, and runtime components. Experiments run on AWS Graviton instances in a single region with approximately 1 ms intervalidator RTT, isolating execution and replication costs rather than wide-area consensus latency. External activations and consensus messages are Ed25519signed; generated continuations are validated against their source execution. Agreement operates over a Merkle root of shard-block hashes, keeping the consensus payload constant-size. We use YCSB [8] for scalability and fault-tolerance benchmarks and a fungible token transfer workload for cross-shard benchmarks, where each transfer

S. Cohen et al. linear in cores measured

800

200

1.07M

Committed requests/s (thousands)

Committed requests/s (thousands)

14

400

200 6,727 per core

100 16

193K 11.9×

YCSB, single-shard requests FT, transfer to a random account

100 65K 9.3×

50 25

10 5

32

48

64

80

Provisioned cores (single validator)

(a) Single-validator execution.

160

4

8

16

32

Cores per validator (shards = cores − 1)

48

(b) Four-validator replication.

Fig. 3: Horizontal scalability of GridSMR. (a) Single-validator execution. (b) Fourvalidator replication under YCSB and fungible-token workloads.

debits the sender and generates a continuation that credits the receiver. Each validator dedicates one core to the consensus representative; the remaining cores host execution shards. Horizontal scalability. We first measure whether throughput scales with available execution parallelism. With a single validator, GridSMR scales from 16 to 160 execution cores and reaches approximately 1.07M requests/s. Across six measured configurations, per-core throughput remains nearly constant, closely tracking linear scaling over a 10× increase in compute resources (Figure 3a). We next repeat the experiment with four validators, so proposed blocks are independently re-executed and verified before agreement. Scaling each validator from 4 to 48 cores raises replicated YCSB throughput from 16,200 to 193,000 committed requests/s: a 11.9× gain over a 12× increase in compute (Figure 3b). The fungible token workload scales 9.3× over the same range, reaching approximately 65K committed transfers/s. Because receivers are chosen uniformly at random, increasing the shard count also increases the fraction of transfers that cross shards, from 67% at 3 shards to 98% at 47. Despite becoming increasingly cross-shard, throughput remains close to linear. Thus, replicated throughput continues to scale with execution parallelism. Leader–Follower Parity. Execute-before-agree is useful only if followers can verify at the leader’s rate. Across 24 runs of the cross-shard workload at 44–100% of sustainable load, the slowest follower shows no persistent block-height lag. The leader-to-slowest-follower gap has an average fitted growth rate of 0.030 blocks/s (standard deviation 0.212) and decreases in 10 of 24 runs. Because insufficient follower capacity would appear as steadily increasing lag, these results indicate that follower validation keeps pace with leader execution. Causal Compression. We evaluate chains of N sequential continuations against an otherwise identical configuration that defers each continuation to the next

GridSMR: Causal Compression for Sharded Blockchains 2000

one block per hop causal compression

12000

1250 1000 750 500

4 ms per hop

10000 8000 6000 4000 2000

250 0

Committed requests/s

1500

0

8

10

validator 0 leader killed validator 1 (killed) validator 2 validator 3

14000

103 ms per hop

8.2×

Whole-chain p50 latency (ms)

1750

12

15

14

Chain depth N (dependent hops)

16

−100

0

100

200

Seconds relative to leader kill

300

400

(b) Leader-failure recovery. (a) Causal Compression.

Fig. 4: (a) Causal Compression avoids per-hop block delay. (b) Validators recover after leader failure and resume pre-failure throughput. Error bars in (a) show one standard deviation over three runs.

block. This isolates the cost of an agreement boundary between dependent steps while keeping the execution engine, workload, network stack, and deployment unchanged. As shown in Figure 4a, deferred execution adds approximately 103 ms per causal step against a 100 ms block interval, while GridSMR adds only approximately 4 ms. At 16 hops, median latency is 1, 822 ms deferred versus 222 ms under GridSMR, an 8.2× reduction versus deferred execution. Real-system validation. To verify that this deferred-execution pattern occurs in practice, we measured causal chains on NEAR testnet. With 10 active shards, every measured causal hop across depths 2–16 and 80 runs required one additional agreement round, including cross-shard chains. TON’s basechain operated as a single shard during our measurements, so it could not provide a cross-shard baseline. Fault tolerance. Finally, we test whether speculative execution recovers after leader failure. We kill the active leader during sustained YCSB load in a fourvalidator deployment. Across three runs at 2,000 requests/s, surviving validators recover after the configured view-change timeouts and return to their pre-failure throughput, as shown in Figure 4b. The transient spike reflects queued requests being processed after recovery. The experiment validates the recovery path rather than peak-load failover.

7

Related Work

Blockchain Scalability Approaches. Modern L1 blockchains scale either vertically, through parallel execution on a single chain, or horizontally, through sharding. Aptos [28], Sui [4], and Solana [34] follow the former approach, but conflicting or shared-state transactions still require coordination. NEAR [27], TON [12], Dfinity/ICP [5], QuarkChain [36], and Monoxide [32] shard state and execution. GridSMR, like NEAR and TON, retains a single consensus point,

16

S. Cohen et al.

but lets dependent cross-shard work progress without the per-step agreement boundaries observed in NEAR’s receipt-based execution. Cross-shard semantics. Prior sharded systems either restrict cross-shard transactions to operations known in advance [35] or execute data-dependent cross-shard work through successive asynchronous receipts [27,32,36]. GridSMR instead localizes atomicity to an activation and lets applications introduce stronger coordination only where needed. GridSMR and NEAR provide asynchronous composability in the sense used by CIRC [20]; CIRC achieves this across rollups through a centralized coordinator, whereas GridSMR provides the property within a Byzantine-replicated sharded L1. This is related to broader work on weakening system-wide ACID semantics in partitioned systems [2, 22, 23, 29], but GridSMR additionally guarantees Causal Liveness for internally generated continuations. Execute-before-agree. GridSMR builds on prior execute-before-agree systems including Speculative Paxos [24], NOPaxos [21], Hyperledger Fabric [3], and Rex [16]. Unlike these systems, GridSMR must validate Byzantine-proposed traces in which execution dynamically generates further cross-shard operations, while allowing follower shards to verify independently and defer cross-shard consistency checks to the block boundary. Acknowledgments. We thank Iddan Kfir, Gal Sadeh, and David Lehavi for helpful discussions and valuable feedback on this work.

GridSMR: Causal Compression for Sharded Blockchains

17

References 1. Aanes, J.M., Gravgaard, J.B., Miltersen, P.B., Nielsen, K., Pourpouneh, M.: Automated Market Makers for Cross-Chain DeFi and Sharded Blockchains. arXiv preprint arXiv:2309.14290 (2023) 2. Akkoorath, D.D., Tomsic, A.Z., Bravo, M., Li, Z., Crain, T., Bieniusa, A., Preguiça, N., Shapiro, M.: Cure: Strong Semantics Meets High Availability and Low Latency. In: 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS). pp. 405–414 (2016) 3. Androulaki, E., Barger, A., Bortnikov, V., Cachin, C., Christidis, K., De Caro, A., Enyeart, D., Ferris, C., Laventman, G., Manevich, Y., et al.: Hyperledger Fabric: A Distributed Operating System for Permissioned Blockchains. In: Proceedings of the Thirteenth EuroSys Conference. pp. 1–15 (2018) 4. Blackshear, S., Cheng, E., Dill, D.L., Gao, V., Maurer, B., Nowacki, T., Polu, A., Qadeer, S., Rain, Russi, D., Sezer, S., Zakian, T., Zhou, R.: Sui Lutris: A Blockchain Combining Broadcast and Consensus. In: Proceedings of the 3rd Workshop on Coordination of Decentralized Finance (CoDecFin) (2024), https://arxiv.org/ abs/2310.18042 5. Camenisch, J., Drijvers, M., Hanke, T., Pignolet, Y.A., Shoup, V., Williams, D.: Internet Computer Consensus. In: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC). pp. 81–91. ACM (2022) 6. Castro, M., Liskov, B., et al.: Practical Byzantine Fault Tolerance. In: Proceedings of the 3rd USENIX Symposium on Operating Systems Design and Implementation (OSDI). pp. 173–186 (1999) 7. Chen, H., Vaisman, A., Eyal, I.: SAMM: Sharded Automated Market Maker. arXiv preprint arXiv:2406.05568 (2024) 8. Cooper, B.F., Silberstein, A., Tam, E., Ramakrishnan, R., Sears, R.: Benchmarking Cloud Serving Systems with YCSB. In: Proceedings of the 1st ACM Symposium on Cloud Computing. pp. 143–154 (2010) 9. Daian, P., Goldfeder, S., Kell, T., Li, Y., Zhao, X., Bentov, I., Breidenbach, L., Juels, A.: Flash Boys 2.0: Frontrunning, Transaction Reordering, and Consensus Instability in Decentralized Exchanges. arXiv preprint arXiv:1904.05234 (2019) 10. Danezis, G., Kokoris-Kogias, L., Sonnino, A., Spiegelman, A.: Narwhal and Tusk: A DAG-Based Mempool and Efficient BFT Consensus. In: Proceedings of the Seventeenth European Conference on Computer Systems. pp. 34–50 (2022) 11. Davidovic, S., Tourpe, H.: How Agentic AI Will Reshape Payments. Tech. Rep. 2026/004, International Monetary Fund (2026). https://doi.org/10.5089/ 9781513533308.068 12. Durov, N.: TON Whitepaper. https://ton.org/whitepaper.pdf (2021), the Open Network 13. dYdX Trading Inc.: dYdX v4 Technical Documentation. https://docs.dydx. exchange (2023) 14. Gould, M.D., Porter, M.A., Williams, S., McDonald, M., Fenn, D.J., Howison, S.D.: Limit Order Books. Quantitative Finance 13(11), 1709–1742 (2013) 15. Guerraoui, R., Kuznetsov, P., Monti, M., Pavlovič, M., Seredinschi, D.A.: The Consensus Number of a Cryptocurrency. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. pp. 307–316 (2019) 16. Guo, Z., Hong, C., Yang, M., Zhou, D., Zhou, L., Zhuang, L.: Rex: Replication at the Speed of Multi-Core. In: Proceedings of the Ninth European Conference on Computer Systems. pp. 1–14 (2014)

18

S. Cohen et al.

17. Haerder, T., Reuter, A.: Principles of Transaction-Oriented Database Recovery. ACM Computing Surveys (CSUR) 15(4), 287–317 (1983) 18. Hyperliquid Labs: Hyperliquid. https://hyperliquid.xyz 19. Kotla, R., Alvisi, L., Dahlin, M., Clement, A., Wong, E.: Zyzzyva: Speculative Byzantine Fault Tolerance. In: Proceedings of the Twenty-First ACM SIGOPS Symposium on Operating Systems Principles (SOSP). pp. 45–58 (2007) 20. Kuszmaul, J., Sankagiri, S., Wang, P.: CIRC: Composable, Independent Rollup Chains. Espresso Systems, https://www.espressosys.com/blog/ circ-composable-independent-rollup-chains (2024) 21. Li, J., Michael, E., Sharma, N.K., Szekeres, A., Ports, D.R.: Just Say NO to Paxos Overhead: Replacing Consensus with Network Ordering. In: 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16). pp. 467–483 (2016) 22. Lloyd, W., Freedman, M.J., Kaminsky, M., Andersen, D.G.: Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS. In: Proceedings of the 23rd ACM Symposium on Operating Systems Principles (SOSP). pp. 401–416 (2011) 23. Mehdi, S.A., Littley, C., Crooks, N., Alvisi, L., Bronson, N., Lloyd, W.: I Can’t Believe It’s Not Causal! Scalable Causal Consistency with No Slowdown Cascades. In: 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17). pp. 453–468 (2017) 24. Ports, D.R., Li, J., Liu, V., Sharma, N.K., Krishnamurthy, A.: Designing Distributed Systems Using Approximate Synchrony in Data Center Networks. In: Proceedings of the 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15). pp. 43–57 (2015) 25. Pritchett, D.: BASE: An ACID Alternative. Queue 6(3), 48–55 (2008) 26. Qin, K., Zhou, L., Livshits, B., Gervais, A.: Attacking the DeFi Ecosystem with Flash Loans for Fun and Profit. In: International Conference on Financial Cryptography and Data Security. pp. 3–32. Springer (2021) 27. Skidanov, A., Polosukhin, I.: Nightshade: NEAR Protocol Sharding Design. https: //near.org/papers/nightshade (2022) 28. The Aptos Team: The Aptos Blockchain: Safe, Scalable, and Upgradeable Web3 Infrastructure. https://aptosfoundation.org/whitepaper (2022) 29. Thomson, A., Diamond, T., Weng, S.C., Ren, K., Shao, P., Abadi, D.J.: Calvin: Fast Distributed Transactions for Partitioned Database Systems. In: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. pp. 1–12 (2012) 30. Thönes, J.: Microservices. IEEE Software 32(1), 116–116 (2015) 31. Vogels, W.: Eventually Consistent. Communications of the ACM 52(1), 40–44 (2009) 32. Wang, J., Wang, H.: Monoxide: Scale Out Blockchains with Asynchronous Consensus Zones. In: 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19). pp. 95–112 (2019) 33. Wester, B., Cowling, J.A., Nightingale, E.B., Chen, P.M., Flinn, J., Liskov, B.: Tolerating Latency in Replicated State Machines Through Client Speculation. In: Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation (NSDI). pp. 245–260 (2009) 34. Yakovenko, A.: Solana: A New Architecture for a High Performance Blockchain v0.8.13. https://solana.com/solana-whitepaper.pdf (2018)

GridSMR: Causal Compression for Sharded Blockchains

19

35. Zamani, M., Movahedi, M., Raykova, M.: RapidChain: Scaling Blockchain via Full Sharding. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. pp. 931–948 (2018) 36. Zhou, Q., et al.: QuarkChain: A High-Capacity Peer-to-Peer Transactional System. https://www.quarkchain.io/QuarkChain-Whitepaper.pdf (2018)

A

Protocol Pseudocode

This appendix collects the pseudocode of the GridSMR shard protocols described in Section 3: the shared data structures and common logic (Algorithm 1), the leader shard protocol (Algorithm 2), and the follower shard protocol (Algorithms 3 and 4). Line numbers referenced from the body of the paper refer to these algorithms.

Algorithm 1 GridSMR: Data Structures and Common Logic define struct Activation: id: integer logic: function ts: integer sid: integer min_bid: integer bid: integer is_external: boolean signature: bytes define struct ShardBlock: bid: integer sid: integer data: List⟨Activation⟩ define struct GlobalBlock: bid: integer blocks: List[m] of ShardBlock

▷ activation id ▷ smart contract function ▷ Lamport timestamp (0 for external) ▷ minimum block id (0 for external) ▷ block id containing this activation ▷ client signature (external only)

▷ activations executed by this shard

1: function Execute(activation) 2: (writes, continuations) ← activation.logic() 3: ProcessWrites(writes) 4: for cont ∈ continuations do 5: cont.ts ← activation.ts 6: cont.min_bid ← activation.bid 7: end for 8: return continuations 9: end function 10: function Select(activations) 11: return activation with highest priority postponement; FIFO in base implementation 12: end function

▷ one per shard

▷ update shard’s account state

▷ any policy without indefinite

20

S. Cohen et al.

Algorithm 2 GridSMR: Leader Shard i Protocol Local variables: bid: integer, initialized to 0 ts: integer, initialized to 0 mempool: list〈Activation〉, initialized to [] executed: list⟨Activation⟩, initialized to [] order_proposal: list⟨Activation⟩, initialized to [] 13: loop 14: wait until ∃a ∈ mempool such that a.min_bid ≤ bid 15: ApplyActivation 16: end loop 17: upon clock tick do 18: CloseBlock

▷ Does not interrupt ApplyActivation

19: upon receipt of continuation cont do 20: mempool.append(cont) 21: procedure ApplyActivation 22: f iltered ← [ a ∈ mempool | a.min_bid ≤ bid ] 23: act ← Select(f iltered) 24: mempool.remove(act) 25: if act.is_external and act.signature is invalid then 26: return 27: end if 28: act.ts ← max(ts, act.ts) + 1 ▷ Lamport ts calculation 29: ts ← act.ts 30: act.bid ← bid 31: executed.append(act) 32: order_proposal.append(act) 33: continuations ← Execute(act) 34: for all cont ∈ continuations in parallel do 35: send cont to destination shard cont.shard 36: end procedure 37: procedure CloseBlock 38: send ⟨order_proposal, bid⟩ to shard i at all followers 39: block ← ShardBlock(bid, i, order_proposal) 40: send block to leader consensus representative 41: bid ← bid + 1 42: order_proposal ← [] 43: end procedure

GridSMR: Causal Compression for Sharded Blockchains

21

Algorithm 3 GridSMR: Follower Shard i Protocol Local variables: bid: integer, initialized to 0 ts: integer, initialized to 0 mempool: list⟨Activation⟩, initialized to [] executed: list⟨Activation⟩, initialized to [] pending_activations: list⟨Activation⟩, initialized to [] speculated: list⟨Activation⟩, initialized to [] ts_at_execution: map⟨Activation, integer⟩, initialized to ∅ 44: upon receipt of continuation cont do 45: pending_activations.append(cont) 46: upon receipt of ⟨order_proposal, k⟩ from leader shard i do 47: if k ̸= bid then 48: buffer block until bid = k ▷ Execute block proposals sequentially 49: end if 50: is_valid ← IsValidBlock(order_proposal) 51: if is_valid then 52: block ← ShardBlock(bid, i, order_proposal) 53: send block to consensus representative 54: bid ← bid + 1 55: executed ← executed + speculated 56: mempool ← mempool + pending_activations 57: else 58: send ⟨invalid, block⟩ to consensus representative 59: end if 60: pending_activations ← [] 61: speculated ← [] 62: ts_at_execution ← ∅

22

S. Cohen et al.

Algorithm 4 GridSMR: Follower Shard i Protocol (continued) 63: function IsValidBlock(order_proposal) 64: start_time ← current time Phase 1: Re-execution 65: for act ∈ order_proposal do 66: if act.shard ̸= i or act.min_bid > bid then 67: return false 68: end if 69: if act.is_external then 70: ts ← ts + 1 71: if act.ts ̸= ts or act is not properly signed or act is in executedi or act is in speculatedi then 72: return false 73: end if 74: else ▷ this is a continuation 75: ts_at_execution[act] ← ts 76: ts ← act.ts 77: end if 78: speculated.append(act) 79: continuations ← Execute(act) 80: for all cont ∈ continuations in parallel do 81: send cont to destination shard cont.shard 82: end for Phase 2: Verification 83: deadline ← start_time + δexec + δintra 84: wait until current time ≥ deadline 85: return IsCausallyConsistent(speculated) 86: end function 87: function IsCausallyConsistent(speculated) 88: for all cont ∈ speculated in parallel do 89: if not cont.is_external then ▷ Reported continuations need to be verified against internal computation 90: in_cont ← ⊥ 91: if cont.id ∈ pending_activations then 92: in_cont ← pending_activations.remove(cont.id) 93: else if cont.id ∈ mempool then 94: in_cont ← mempool.remove(cont.id) 95: end if 96: if not in_cont or cont.ts ̸= max(in_cont.ts, ts_at_execution[in_cont])+ 1 then 97: return false 98: end if 99: end if 100: return true 101: end function

GridSMR: Causal Compression for Sharded Blockchains

B

Correctness Proofs

B.1

Leader Protocol Proofs

23

This appendix contains proofs of lemmas and theorems from the main text, which were omitted due to space constraints. Theorem 3.2. Algorithm 2 preserves a valid system state. Proof. Our execution model ensures any concurrent execution is equivalent to a sequential one, ordered by lock acquisition. We prove correctness by induction on the number of execution steps. The base case is when the system is empty, which is trivially valid. Assume that the system state is valid after n steps, and consider the next step. Adding an activation to the mempool: Consider a step where an activation is added to some shard’s mempool. Without loss of generality, let this be mempooli . Activations are added to the mempooli either externally, in which case they satisfy Assumption 3.1, or as a continuation cont at line 20. In the latter case, cont is sent by the leader at line 35 after executing activation act at shard j. By line 33 cont was generated according to the activation logic. Then, at line 31, act was added to executedj before sending the continuation to shard i, preserving Integrity. By the code, and by the induction hypothesis on act satisfying No Duplication, this addition only occurs once and at the correct shard, preserving No Duplication and Well-formedness. The other properties are unaffected by adding an activation to the mempool. Applying an activation: Consider a step where some shard executes an activation. Without loss of generality, let this be shard i executing activation act. For Authenticity, the leader only executes an external activation and adds it to executedi after verifying its signature is valid (line 25). Since act is taken from mempooli (line 22), it was added to mempooli in some earlier step. By the induction hypothesis, all invariants held after that earlier step, including: Integrity: If act is a continuation, it was correctly generated by executing some previous activation in executedj (for some shard j). Moving act from mempooli to executedi preserves this property– the same activation that was correctly generated remains correctly generated. No Duplication: The activation act appeared at most once in mempooli ∪ executedi . Since act is removed from mempooli (line 24) before being added to executedi (line 31), act still appears at most once. Well-formedness: The activation act is included in shard i when added to mempooli . Since it remains on the same shard throughout execution, it is added to the correct executedi . Finally, we prove the Happens-before Relation is preserved by our Lamport timestamps implementation. Let A and A′ be two activations in executedi and executedj respectively such that A ≺ A′ . We consider the cases defining A ≺ A′ .

24

S. Cohen et al.

If i = j, then A occurs before A′ in executedi . Let A.ts be the timestamp assigned to A at line 28. Within each shard, the local timestamp ts is incremented monotonically with every activation execution (line 29). Thus, when A′ is executed, its timestamp is set to at least A.ts + 1 (line 28), ensuring A.ts < A′ .ts. If i ̸= j and A directly triggered A′ , then when A′ is generated as a continuation of A, it inherits A’s timestamp: A′ .ts = A.ts (line 5). When A′ is later executed on shard j, its timestamp is updated to at least A.ts + 1 (line 28), ensuring A.ts < A′ .ts. If A did not directly trigger A′ , there exists a causal chain of activations from A to A′ . Let A′′ be the activation that directly triggered A′ (A′′ → A′ and A ≺ . . . ≺ A′′ ≺ A′ .). By the arguments above, A′′ .ts < A′ .ts. By the induction hypothesis applied to the earlier step when A′′ was added to executedj , we have A.ts < A′′ .ts. By transitivity, A.ts < A′ .ts.

B.2

Blocks and Replication Proofs

Lemma 3.3. Algorithm 2 maintains Block Causality. Proof. Causal relations within a shard are preserved naturally by the sequential execution order: if A and A′ are both in shard i and A ≺ A′ , then A is executed before A′ , so A.bid ≤ A′ .bid. For cross-shard causality, when activation A in shard i directly triggers continuation A′ in shard j (i.e., A → A′ ), we set A′ .min_bid = A.bid (line 6). The leader’s selection of activations respects this constraint by filtering for activations where activation.min_bid ≤ bid (line 22). Therefore, A′ can only be included in a block with bid ≥ A.bid, ensuring A.bid ≤ A′ .bid. For transitive causality where A ≺ A′ through a chain of activations, the result follows by induction on the length of the causal chain, using the two base cases above. Having established that the leader maintains Block Causality, we can now prove that the global proposals generated by the leader are valid. Lemma 3.4. A correct leader executing CloseBlock at all shards creates a valid global proposal. Proof. By Theorem 3.2, a correct leader maintains a correct system state after every execution step. When all shards execute CloseBlock for block k, the resulting global proposal consists of all activations added to executedi across all shards i since block k − 1 was closed. The Authenticity, No Duplication, and Well-formedness properties are maintained within each shard independently and do not involve cross-shard dependencies. Since every prefix of a correct leader’s execution maintains these properties (by Theorem 3.2), they hold for the activations in each shard proposal. The Integrity and Happens-before Relation properties require that causal dependencies are preserved in the global proposal. That is, if A ≺ A′ and A′ is

GridSMR: Causal Compression for Sharded Blockchains

25

included in the global proposal, then A must either already be in executedj (for some shard j) before A′ is executed, or A must also be included in the global proposal. This is guaranteed by Lemma 3.3 (Block Causality) and the fact that bid increments monotonically: if A.bid ≤ A′ .bid and both are in blocks ≤ k, then either A.bid < A′ .bid (so A was in an earlier block) or A.bid = A′ .bid (so both are in the same global proposal). Therefore, applying the global proposal to the system state at the end of block k − 1 results in a correct system state at the end of block k. Remark B.1. Note that Authenticity, No Duplication, and Well-formedness are maintained within each shard independently and do not involve cross-shard dependencies. This means that a shard proposal can be marked as invalid with regard to these properties during follower verification based solely on the local execution history. We rely on this fact in subsequent proofs. B.3

Follower Proofs

Follower Protocol Correctness We now establish the correctness of the follower protocol. We first prove that execution is deterministic (Lemma B.2), which ensures followers can reliably verify leader proposals through re-execution. We then prove that successful block execution maintains system state invariants (Lemma B.9). Finally, we prove that when the leader is correct and timing assumptions hold, followers successfully complete block verification (Lemma B.11). Execution Determinism Lemma B.2. Given the same initial state and the same shard proposal, executing the activations sequentially in the order they appear produces the same final state. Proof. Each activation’s execution is deterministic: given the same state and activation, the execute function produces the same writes and continuations. By induction on the number of activations in the shard proposal, executing them sequentially in order produces the same final state. Block Execution Safety The previous lemma establishes that if a follower successfully executes a proposal, it reaches the same state as the leader (by deterministic execution from the same initial state). However, it does not address whether the proposal itself is valid—that is, whether it maintains system state invariants. A key challenge in our sharded architecture is handling cross-shard causality during parallel execution. Consider activations A and A′ on different shards where A → A′ . During follower execution, different shards process their shard proposals in parallel: A′ may execute on its shard before A completes on its shard, creating temporary “inconsistencies” in the system state. Our approach is to tolerate these transient inconsistencies during execution, but enforce that all invariants hold at block boundaries. By checking system state correctness only after all shards complete their execution (rather than

26

S. Cohen et al.

coordinating during execution), we enable shards to execute independently in parallel, maximizing throughput. This block-boundary verification strategy is central to GridSMR’s scalability: shards execute at full speed without intershard coordination, synchronizing only at block boundaries. The use of shadow data structures and atomic application of blocks ensures that these transient inconsistencies are never visible to the external clients. With this approach established, we must prove that the verification procedure correctly identifies invalid proposals. Specifically, we show: if IsValidBlock returns true for all shards, then applying the global proposal maintains all system state invariants. For the proof, we observe that our invariants partition into two categories. Shard-local properties (Authenticity, No Duplication, Wellformedness) can be verified by examining only a single shard’s execution history. Cross-shard properties (Integrity, Happens-before Relation) require checking that causal dependencies between shards are properly maintained. We introduce terminology for block execution outcomes. A shard i completes block k successfully if it executes and verifies the shard block k proposal, then approves it for consensus (line 53). Otherwise, if verification fails and the shard sends an invalid block message (line 58), the shard has failed block k. We now prove that successful block execution at all shards maintains system state invariants, beginning with auxiliary lemmas about how follower state evolves during and after block execution. We begin by proving that continuations in pending_activations have valid sources in executed. Lemma B.3. Let b be the block number during which activation A is added to pending_activationsi . If block b completes successfully at all shards, then there exists another activation B such that B → A, and B is added to executedj by the end of block b. Moreover, each instance of A in pending_activationsi corresponds to a distinct instance of B in executedj . Proof. If A is found in pending_activationsi it means by the code that it was added to pending_activationsi at line 45, after being sent by some shard j at Line 81. The sending event of A happens after the execution of the activation B at line 79, and after it was added to speculatedj at line 78 during some block processing. This execution is done according to the logic (B → A) and creates all follow-up continuations, including A, with min block id that is B’s block id (line 6). Thus, since A previously passed the check at the beginning of block b execution in line 66, it is guaranteed that B has been executed in block b′ ≤ b. When shard j finishes executing block b′ , it appends all activations in speculatedj (including B) to executedj at line 55. If IsValidBlock returned false earlier, block b′ fails at shard j. In the first case, since b′ ≤ b and executedj is append-only, B is guaranteed to be added to executedj by the end of block b. Otherwise, since blocks are processed sequentially, block b that includes A does not complete. Note that by the code, the instance of A in pending_activationsi corresponds to a distinct instance of B in speculatedj as after B’s execution it is only created once, and only added once to the pending set.

GridSMR: Causal Compression for Sharded Blockchains

27

The next lemma extends this result to continuations that have been promoted from pending_activations to mempool. Lemma B.4. Let b be the block number when activation A is added to mempooli . If block b completes successfully at all shards, and A is a continuation, then there exists another activation B such that B → A, and B is added to executedj by the end of block b. Moreover, each instance of A in executedi corresponds to a distinct instance of B in executedj . Proof. By the code, A is added to mempooli only if it is found in pending_activationsi (line 56). The proof then follows from Lemma B.3. We now prove the same property for continuations that have been fully verified and added to executed, completing the chain from pending_activations through mempool to executed. Lemma B.5. Let b be the block number when activation A is added to executedi . If block b completes successfully at all shards, and A is a continuation, then there exists another activation B such that B → A, and B is added to executedj by the end of block b. Moreover, each instance of A in executedi corresponds to a distinct instance of B in executedj . Proof. By the code, A is added to executedi from speculatedi at line 55, after IsValidBlock returned true for block b. This happens after all continuations in speculatedi were found in either mempooli or pending_activationsi (lines 92– 97). If A appears in pending_activationsi , proof follows from Lemma B.3. Otherwise, A must be found in mempooli and proof follows from Lemma B.4. These three lemmas together prove the Integrity property: every continuation in executedi , mempooli has a valid source. We now use these results to prove that No Duplication is maintained throughout block execution. Lemma B.6 (No Duplication). For every k, at the end of executing block k at all shards, there does not exist an activation that appears in executedi ∪ mempooli more than once, for any i. Proof. Define the causal depth of an external activation to be zero and, whenever A → A′ , define depth(A′ ) = depth(A) + 1. We prove this lemma with induction on k. Base case: k = 0. All data structures are empty. Inductive step: Assume that the statement is true for any i ≤ k and prove for i = k + 1. Assume by negation the statement does not hold. Thus, there exists a shard i and an activation that appears in executedi and mempooli more than once, after block k + 1 has completed at all shards. Let A be such activation, with the shortest causal depth d. If A is an external activation (i.e., d = 0), then A is not added to follower’s mempooli and thus it does not appear in mempooli more than once. Hence, it must appear in executedi more than once. By the code, A is added to executedi only if it was previously added to speculatedi at line 78. This only happens if it passes the check at line 71, making sure it

28

S. Cohen et al.

was not already in executedi or speculatedi . Hence, the second addition of A to executedi is a contradiction, and the statement holds. Otherwise, A is a continuation. We separate the cases that cause the violation. – A appears more than once in mempooli : Examine two different occurrences of A in mempooli . By Lemma B.4 applied twice per each occurrence, since we know by assumption all shards have completed block k + 1, there exists another activation B such that B → A, and B is added twice to executedj by the end of block k + 1. This means B appears in executedj more than once, after block k + 1 has completed at all shards, and B has causal depth d − 1, in contradiction to the assumption that A has the shortest causal depth. – A appears more than once in executedi : Similar to the previous case, examine two different occurrences of A in executedi . By Lemma B.5 applied twice per each occurrence, since we know by assumption all shards have completed block k + 1, there exists another activation B such that B → A, and B is added twice to executedj by the end of block k + 1. This means B appears in executedj more than once, after block k + 1 has completed at all shards, and B has causal depth d − 1, in contradiction to the assumption that A has the shortest causal depth. – A appears in both mempooli and executedi : Finally, examine the two occurrences of A in mempooli and executedi . By Lemma B.4 applied for the occurrence in mempooli , and Lemma B.5 applied for the occurrence in executedi , since we know by assumption all shards have completed block k + 1, there exists another activation B such that B → A, and B is added to executedj twice by the end of block k + 1. This means B appears in executedj more than once, after block k + 1 has completed at all shards, and B has causal depth d−1, in contradiction to the assumption that A has the shortest causal depth.

Having proved that No Duplication holds, we now turn to the Happens-before Relation property. We first show that local timestamps at each shard increase monotonically during successful block execution. Lemma B.7. If shard i completes the execution of block k successfully, then the local timestamp ts in shard i is strictly monotonically increasing throughout the execution up to and including block k. Proof. Assume by negation that the local timestamp in shard i is not strictly monotonically increasing. The local timestamp changes when processing an external activation (line 70) or when processing a continuation (line 76). In both cases, the change corresponds to processing an activation and adding it to speculatedi . By assumption, there exist two activations A and A′ such that A is processed before A′ (either within the same block or across blocks), with shard’s local timestamps t and t′ respectively at the time they are processed, such that t ≥ t′ .

GridSMR: Causal Compression for Sharded Blockchains

29

Choose the first such pair – that is, A′ is the first activation processed after A where t ≥ t′ . If A′ is external, then by the code, the local timestamp is set to t′ = t + 1 (line 70), contradicting t′ ≤ t. Otherwise, A′ is a continuation. When A′ is processed, the follower records ts_at_execution[A′ ] ← t (line 75), then sets the local timestamp to t′ = A′ .ts (line 76). Later, when the verify function verifies A′ , it checks that A′ .ts ≥ ts_at_execution[A′ ] + 1 = t + 1 (line 97), or otherwise fails. Therefore t′ ≥ t + 1, contradicting the assumption that t′ ≤ t. Since block k completes successfully, no verification fails, so our assumption must be false. Therefore the local timestamp is strictly monotonically increasing throughout the execution. With monotonicity of local timestamps proven, we can now show that the Happens-before Relation is preserved for all activation pairs. Lemma B.8 (Happens-before Relation). If all shards complete the execution of block k successfully, then for any two activations A, A′ in executedi and executedj respectively, if A ≺ A′ , then A.ts < A′ .ts. Proof. Let A and A′ be two activations in executedi and executedj respectively such that A ≺ A′ . We consider the cases that define A ≺ A′ . Assume i = j and A appears before A′ in the sequential order of executedi . At the end of block k, executedi is appended with speculatedi . Since the order in speculatedi reflects the order in which activations were processed during IsValidBlock, if A was processed in block k, then A was processed before A′ . Note that this ordering holds even if A was executed in an earlier block, since activations are appended to executedi in order across blocks. Let t be the local timestamp in shard i when A was executed. By Lemma B.7, since shard i completes blocks successfully, the local timestamp is strictly monotonically increasing both within and across blocks. Therefore, the local timestamp when processing A′ in block k is strictly greater than the local timestamp when A was processed (whether in block k or an earlier block). This means that when A′ is executed, the local timestamp in shard i is at least t + 1. Since A′ is added to executedi , it passed verification– either the check at line 71 (if external) or the check at line 97 (if continuation). In both it was compared to the local timestamp (either explicitly or to a recorded value captured in ts_at_execution[A′ ]). and A′ .ts is verified to be at least t + 1. Therefore, A′ .ts > A.ts. Alternatively, if i ̸= j and A triggered A′ , then when the follower verified A′ , the verify function checked that A′ .ts ≥ incoming_cont.ts + 1, where incoming_cont is the locally generated continuation corresponding to A′ (line 97). When the follower speculatively executed A, it set incoming_cont.ts = A.ts (line 5). Therefore, A′ .ts ≥ A.ts + 1 > A.ts. The transitive case, where A ≺ A′ through a chain of intermediate activations, follows by induction on the length of the causal chain. Therefore, in all cases, A.ts < A′ .ts.

30

S. Cohen et al.

The preceding lemmas verify individual properties during block execution. We now combine these results to prove that successful block execution maintains all system state invariants. Lemma B.9. If all shards complete the execution of block k successfully, then applying the global proposal for block k maintains all system state invariants. Proof. Unlike the leader’s execution where all properties are maintained after every step, at followers some properties are only maintained at block boundaries – that is, at the end of block execution across all shards. Our invariants partition by verification scope. Authenticity and Wellformedness are verified locally during each activation’s processing (lines 67, 72). Failing to satisfy these properties for any activation immediately causes IsValidBlock to return false at the relevant shard, and the shard fails the execution of block k. Integrity and Happens-before Relation cannot be verified by examining individual activations in isolation – they require reasoning about causal relationships across shards and may be temporarily violated during parallel execution. No Duplication similarly requires reasoning across a shard’s entire execution history, though it is never violated within a single shard during execution. These three properties are verified at block boundaries through the preceding lemmas: Integrity follows from Lemmas B.4 and B.5, No Duplication from Lemma B.6, and Happens-before Relation from Lemma B.8. Therefore, if all shards complete block k successfully, all system state invariants hold. Block Execution Liveness Our previous focus was on showing that successfully completing block k implies the proposal is valid (safety). We now turn to liveness: when the leader is correct and conditions are favorable, all correct followers successfully complete block execution. We begin by showing that timestamp verification failures indicate leader misbehavior. Lemma B.10. If a follower with the same state as the leader before block k fails a timestamp check for activation A (at line 72 or line 97), then the leader did not correctly apply the Lamport timestamp mechanism for A. Proof. The follower verifies timestamps by recomputing them according to the Lamport timestamp rules and comparing to the assigned ts by the leader: incrementing for external activations, and computing max(parent.ts, local_ts) + 1 for continuations. Since the follower starts with the same state and executes the same deterministic logic, it computes the same timestamp values the leader should have computed. If verification fails, the leader’s reported timestamp differs from the correct Lamport timestamp. With timestamp verification correctness established, we can now prove the main liveness result: correct leaders produce proposals that correct followers accept. This is the first lemma that reasons about both leader and follower

GridSMR: Causal Compression for Sharded Blockchains

31

behavior together, showing that correct leader execution guarantees successful follower verification. Lemma B.11. Assume the leader is correct and sends a proposal for block k. After GST, a correct follower that receives the proposal and has the same state as the leader had before executing block k successfully completes execution of block k at all shards. Proof. We prove the contrapositive. Assume a correct follower receives a proposal for block k after GST and has the same state as the leader had before executing block k, but fails to complete execution of block k at some shard i. Then the leader is not correct. By the code, the execution failure means that IsValidBlock called on order_proposal returns false at shard i. We examine all reasons that could cause this failure. Note that any of the checks that may fail is associated with a specific activation in the proposal. Denote this activation by A. – Line 67: By the code, this line returns false if either A.shard is not the shard i on which it is attempted to be executed or A.min_bid is greater than the bid of the block. In the first case, the well-formedness property is violated, implying the leader is not correct (Lemma 3.4). In the second case, if the leader was correct, A should not have been included in the proposal, implying the leader is not correct (Lemma 3.4). – Line 72: By the code, this line returns false if A is external activation and one of the following holds. If A.ts is not equal to the timestamp ts of the shard i at the time of execution. By Lemma B.10 and Lemma 3.4, the leader must be Byzantine. If A is not properly signed, implying the leader is not correct. (Lemma 3.4) If A is already in executedi or speculatedi before it is executed, it follows from the code that A was previously executed on this shard. Thus, the leader’s proposal violates the No Duplication property, implying the leader is incorrect. (Lemma 3.4) – Line 97: By the code, this line returns false if A is a continuation and one of two conditions holds: (1) A is not found in either pending_activationsi or mempooli , or (2) A is found but its timestamp does not satisfy the Lamport timestamp constraint. Case 1: A is missing. Since the leader creates correct proposals (Lemma 3.4), there must be another activation B such that B → A and B ∈ executedj when the proposal was created. Due to Block Causality, B was executed at the leader in some block k ′ ≤ k on shard j. If k ′ < k, then by timing bounds after GST, A arrives at the leader’s shard i within δintra time (which is smaller than block tick interval), so A is added to either mempooli by the end of block k ′ or during block k ′ + 1. If A reaches mempooli by the end of any block k ′′ < k, then by the samestate assumption, A is also in the follower’s mempooli at the start of block k, contradicting the assumption that A is missing.

32

S. Cohen et al.

Otherwise, A arrives during block k ′ +1 = k. Then A is added to pending_activationsi before the deadline start_time + δexec + δintra . The same occurs at the follower: B executes, generates A, and by timing bounds, A arrives at pending_activationsi before the deadline, contradicting the assumption that A is missing. Hence, in all subcases when k ′ < k, the leader must be incorrect. Otherwise, k ′ = k. In this case, B executes during block k at both leader and follower. When the follower executes B, it generates A and sends it to shard i (line 81). Let start_time denote the time when the follower begins executing the block proposal. By the code, the follower waits until deadline = start_time + δexec + δintra before verifying continuations (line 84). Since the follower receives the proposal after GST, timing bounds hold: δexec bounds the execution time for all activations in the proposal, and δintra bounds intra-cluster message delay. Therefore, A arrives at shard i and is added to pending_activationsi before the deadline, contradicting the assumption that A is missing. Hence, in both subcases, the leader must be incorrect. Case 2: A is found but timestamp is incorrect. By Lemma B.10 and Lemma 3.4, the leader must be Byzantine. Therefore, in all cases, the leader is not correct.

C

GridSMR Consensus Representative Protocol and Correctness

We now prove that GridSMR (Algorithm 5), built atop a standard SMR component, satisfies all SMR properties including Causal Liveness. We begin by establishing that correct clusters maintain consistent state across committed blocks. Lemma C.1. If two correct clusters commit the same sequence of blocks, they have reached the same system state. Proof. Let r1 and r2 be two correct clusters that commit the same sequence of blocks [b0 , b1 , . . . , bk ]. We prove by induction on k that the system state committed with block bk is identical at both clusters (same executedi , mempooli , tsi , and account state for all shards i). For the base case (k = 0), both clusters start with empty initial state. For the inductive step, assume r1 and r2 committed identical state with block bk−1 . When consensus commits block bk , there are two cases at each cluster: If bk = gblock (committed block matches cluster’s proposal). The cluster has already executed and validated bk during the proposal phase. It simply persists the pre-computed state. Otherwise, bk ̸= gblock (committed block differs from cluster’s proposal). The cluster triggers rollback to block bk−1 , restoring state from checkpoint, then executes the committed block bk from that restored state.

GridSMR: Causal Compression for Sharded Blockchains

33

Algorithm 5 GridSMR: Consensus Representative Protocol Local variables: block_proposals: Map[integer, GlobalBlock], initialized to ∅ creation

▷ All blocks in

1: upon receipt of block from shard do 2: bid ← block.bid 3: if bid ∈ / block_proposals then 4: block_proposals[bid] ← GlobalBlock(bid, []) 5: end if 6: gblock ← block_proposals[bid] 7: gblock.blocks[block.sid] ← block 8: if |gblock.blocks| = m then ▷ blocks from all shards arrived 9: SMR.propose(gblock) 10: end if 11: upon SMR commits block b do 12: if b = gblock then 13: persist gblock and system state to disk 14: else 15: rollback to checkpoint at end of block b.bid − 1 16: execute all operations in committed block b 17: persist b and resulting system state to disk 18: end if 19: upon receipt of ⟨invalid, block⟩ from shard do 20: abort block.bid and rollback to checkpoint at block.bid - 1 21: upon rollback required to block k − 1 do 22: for all shards i do 23: restore state of shard i to checkpoint at end of block k − 1 24: end for

34

S. Cohen et al.

In both cases, each cluster executes block bk starting from the state committed with block bk−1 . By deterministic execution (Lemma B.2), executing the same sequence of activations from the same initial state produces the same final state. Since both clusters begin with identical state (by induction hypothesis) and execute the same block bk (committed by consensus), they produce identical state at all shards. When both clusters commit block bk , they merge their shadow structures into permanent state identically (Algorithm 3, line 56). Their overall state, consisting both the merged data structures and account state, is what gets committed with block bk . Note that if consensus had rejected bk , both clusters would have performed rollback identically, restoring from checkpoints at block bk−1 (which are identical by induction hypothesis), and would not have committed block bk . Additionally, any execution that occurs after committing block bk belongs to later blocks and does not affect the state committed with bk . Therefore, the system state committed with block bk is identical at both r1 and r2 .

Next, we show that activations in the mempool eventually execute – a key building block for both Liveness and Causal Liveness. Lemma C.2. If activation A is in the leader’s mempool and the leader continues executing, then A is eventually selected and executed. Proof. By assumption, A is in mempooli for some shard i at leader cluster. By the leader protocol, the leader continuously selects activations from the mempool for execution (line 15). The selection procedure (line 22) filters activations where activation.min_bid ≤ bid, where bid is the current block number. Since bid increases monotonically with each block (line 41), eventually bid ≥ A.min_bid, making A eligible for selection. The selection policy chooses from filtered activations in FIFO order based on arrival time. Since mempooli is finite and activations are continuously processed, A will eventually be selected and executed. By the fairness requirement on Select (Algorithm 1, line 11), only finitely many activations may be selected ahead of A once A is eligible. Since the leader selects continuously, A is therefore selected after finitely many selections. Once selected, A is removed from the mempool (line 24) and executed (line 15). Remark C.3. While GridSMR’s base implementation uses FIFO selection, more sophisticated policies could be explored for different fairness or efficiency goals, such as gas price-based prioritization or stake-weighted ordering, as long as they satisfy a fairness constraint preventing indefinite postponement of eligible activations. The lemmas above enable us to prove GridSMR’s liveness properties. Lemma C.4. GridSMR satisfies Liveness and Causal Liveness.

GridSMR: Causal Compression for Sharded Blockchains

35

Proof. We first show that, for each property, the relevant activation is eventually executed by a correct leader. For Liveness, let A be an external activation submitted by a client. The client submits A to the current leader, which adds it to the appropriate mempool. If the leader cluster is correct and remains active, then by Lemma C.2, A is eventually selected and executed. Otherwise, by the client retransmission rule of Section 3.3, the client resubmits A after leader replacement. By the liveness condition of the underlying SMR protocol, after GST leader replacement eventually installs a correct leader that remains active long enough to receive A. Lemma C.2 then implies that A is eventually selected and executed. For Causal Liveness, suppose activation A commits in block k and produces continuation B. All correct clusters execute block k and generate the same continuation B by deterministic execution (Lemma B.2), adding B to the mempool of its destination shard. By Block Causality (Lemma 3.3), B.min_bid = k, ensuring that B satisfies the selection constraint as blocks progress. If the current leader cluster is correct and remains active, then by Lemma C.2, B is eventually selected and executed. Otherwise, B remains present across leader replacements: every correct cluster generated B when executing committed block k, and by Lemma C.1 correct clusters agree on the corresponding system state. Thus, whenever leadership moves to a correct cluster, that leader resumes with B in the mempool. By the liveness condition of the underlying SMR protocol, after GST a correct leader eventually remains active long enough for Lemma C.2 to apply. If a speculative block containing B is not committed, rollback restores the preceding checkpoint, in which B remains pending, so B remains available for a subsequent proposal. It remains to show that execution by a correct leader eventually commits. Let X denote the relevant activation (A for Liveness and B for Causal Liveness). Once a correct leader executes X after GST, it includes X in a global proposal. By Lemma B.11, all correct followers successfully verify the corresponding shard proposals. By Lemma 3.4, the resulting global proposal is valid. Liveness of the underlying SMR protocol therefore ensures that the proposal eventually commits. Hence A eventually executes and commits for every external activation submitted by a correct client, and every continuation B generated by a committed activation eventually executes and commits. Therefore, GridSMR satisfies both Liveness and Causal Liveness.

We can now state and prove the main result. Theorem 4.1. GridSMR satisfies Agreement, Validity, Liveness, and Causal Liveness. Proof. Agreement: By Agreement property of the underlying SMR protocol, all correct clusters commit the same sequence of global blocks in the same order. By Lemma C.1, if they all commit the same sequence of blocks, they all reach the

36

S. Cohen et al.

same system state. Therefore, GridSMR satisfies Agreement: all correct clusters agree on the same system state. Validity: GridSMR’s validity predicate is that the committed global block content, when executed by correct clusters from the previous committed state, maintains all system state invariants (IsValidBlock returns true at all shards). This is the validity predicate enforced by the underlying SMR protocol. By the underlying SMR Validity property, all committed blocks satisfy this predicate. Therefore, GridSMR satisfies Validity. Liveness and Causal Liveness: Follows from Lemma C.4.

D

Additional Performance Analysis

Communication Architecture Cross-shard latency is a first-order concern outside blockchains as well: traditional distributed databases invest heavily in specialized hardware – InfiniBand, RDMA, and custom interconnects – to keep it low. GridSMR reduces cross-shard communication latency through placement, by colocating a cluster’s shards in one data center (Section 5). The inter-cluster consensus path, which is the primary consumer of intercluster bandwidth, operates at block boundaries rather than per activation. Moreover, consensus can operate on compact commitments rather than full block data, significantly reducing message size. Speculative Execution for Latency GridSMR employs speculative execution to provide low-latency responses to clients. We maintain a clear separation between activation processing time and response finalization time. Following the execute-before-agree pattern, clients receive optimistic responses from the leader immediately upon execution, potentially before the block is even constructed. If the leader is correct, the speculative response reflects a valid execution, although it is not yet final. Clients requiring finality guarantees can track consensus progress or wait for finality confirmation, but many applications prioritize fast responses over guaranteed finality, including DeFi trading platforms, blockchain gaming, and real-time interactive applications. Together with Causal Compression, this allows clients to perform multiple back-and-forth optimistic interactions with the system within the same block. A client can submit an activation, receive the optimistic result, and use that result to construct a follow-up activation – all before the first activation is finalized through consensus. Notably, the correctness of speculative execution depends solely on leader behavior. Unlike speculative protocols such as Speculative Paxos and NOPaxos that rely on network ordering properties, our followers verify leader execution through deterministic re-execution. A speculative result may be discarded if the leader is Byzantine or if leader replacement causes a different execution to be committed. Network delays or message reordering do not cause speculative results to be incorrect – they affect only finalization timing.

GridSMR: Causal Compression for Sharded Blockchains

E

37

Discussion

This section discusses design choices and tradeoffs beyond GridSMR’s core architecture. E.1

System-Level Optimizations

Pipelining and Continuous Execution The protocol description presents execution sequentially for clarity, but the system can be pipelined in practice. Within blocks, many activations are independent due to the execution model and can execute in parallel at both leaders and followers. The key constraint is maintaining determinism and causality through correct timestamp computation and clear block boundaries. Assuming each shard hosts multiple accounts, followers can interleave and parallelize execution across accounts within the same shard while preserving the required per-account execution order. Long-Running Activations In GridSMR, an activation’s execution need not complete within a single block interval. Unlike traditional blockchains that use commit-then-execute, where consensus determines the order of transactions before execution begins, GridSMR’s execute-before-agree pattern decouples execution duration from block timing. The fundamental challenge in commit-then-execute systems is that consensus commits to a specific set of transactions for each block without knowing their execution time. Once block k is committed, all transactions in that block must execute to completion before the system can proceed to block k + 1. If any transaction takes too long to execute, the system stalls waiting for it to complete. This forces a bound on per-transaction execution, typically enforced through gas limits or execution time caps. GridSMR relaxes this constraint because execution happens before consensus, and blocks are determined “retroactively” by the leader clock. The leader executes activations continuously and periodically packages completed work into blocks for consensus. If an activation does not complete before a block boundary, it is included in a later block, once its execution completes. The activation is tagged with that block identifier, ensuring any continuations it spawns inherit the correct minimum block id for causal ordering. Per-activation computation remains bounded – activations are gas-metered against a declared maximum – but that bound need not fit within a block interval. E.2

Policy and Mechanism Choices

Fairness Mechanisms Blockchains often aim to provide fairness to users through mechanisms such as rotating leaders or restrictions intended to mitigate MEV attacks such as front-running and sandwich attacks [9,26]. Fairness is not the focus of this paper. However, removing atomicity at the infrastructure level permits

38

S. Cohen et al.

additional interleavings across activation trees. A malicious leader may therefore reorder continuations from concurrent activation trees, potentially violating application-level ordering expectations. Applications requiring ordering guarantees beyond GridSMR’s default peraccount execution order can introduce application-specific coordination. For example, an application can designate a specific account as a synchronizer through which relevant continuations are ordered before further execution. Such synchronization reduces parallelism for the affected execution paths, but allows applications to selectively obtain stronger ordering guarantees when needed. Follower Verification Strategies The follower verification protocol divides verification into two phases: executing activations in the proposal, then verifying continuations. A coordination mechanism is needed to allow shards to transition from phase one to phase two, ensuring the first phase has completed across all shards in the cluster. Without this coordination, a shard might begin continuation verification before other shards have sent their continuations, leading to false rejection of valid blocks. Our implementation uses standard timeout techniques, but alternative approaches exist. For example, the cluster representative could collect completion signals from shards and coordinate the phase transition. This approach can identify Byzantine proposals in some scenarios but requires additional synchronization within the cluster during phase two of follower execution.

Related documents

• GridSMR: Causal Compression for Sharded Blockchains#1156715
• Compact Shielded CSV: Post-Quantum, Private, Lightweight Client-Side Validation Blockchain#1115971
• Ensuring the integrity of AI models: a blockchain-based approach for protecting medical imaging training data.#150189
• State Without a Landlord: An Architecture Proposal for Peer-to-Peer Replication of Durable Workflow State#1011376
• State Without a Landlord: An Architecture Proposal for Peer-to-Peer Replication of Durable Workflow State#965395