Lantern: Finding Committable Transactions via Back-Propagation on DAGs

Lantern: Finding Committable Transactions via Back-Propagation on DAGs Denglong Li∗ , Gerui Wang† , Tian Guan∗ , Mingchao Wan† ∗ Tsinghua University, † Beijing Academy of Blockchain and Edge Computing

arXiv:2609.03315v1 [cs.DC] 3 Sep 2026

li-dl24@mails.tsinghua.edu.cn, wanggerui@baec.org.cn, guantian@sz.tsinghua.edu.cn, chainmaker@baec.org.cn

Abstract—Existing concurrency control protocols either introduce nondeterminism, resulting in a serial execution-replay dependency between primary and replica nodes, or rely on impractical prior knowledge of transaction read-write sets. In this paper, we present Lantern, a deterministic concurrency control protocol tailored for high-performance transaction processing systems operating without prior knowledge. The key insight of Lantern is that all zero-out-degree transaction vertices in the local dependency graph can be safely committed in ascending order using an overwrite-permissive strategy. We further introduce a novel Back-Propagation mechanism that iteratively propagates dependency states from sink to source vertices to identify additional committable transactions. We also propose Conflict-Free Batch Selection (CFBS) for read-modify-write intensive scenarios. We integrate Lantern into the open-source blockchain platform ChainMaker. Extensive evaluations on YCSB and SmallBank benchmarks demonstrate that Lantern achieves up to a 4.2x throughput speedup over Aria and improves the throughput of ChainMaker’s execution layer by at least 2.2x. Index Terms—deterministic concurrency control, parallel algorithm.

I. I NTRODUCTION As blockchain adoption continues to expand, improving transaction throughput has become a critical challenge. Recent advances in Byzantine Fault Tolerant (BFT) consensus protocols [1]–[3] have substantially increased consensus-layer performance. As a result, transaction execution is emerging as a major performance bottleneck. Traditional blockchain systems such as Bitcoin [4] and Ethereum [5] execute transactions sequentially, which severely limits the utilization of modern multi-core processors. Consequently, parallel transaction execution has become a natural approach to enhancing throughput. However, many concurrency control protocols are nondeterministic [6]–[8]. Although they can effectively exploit intranode parallelism, participating nodes cannot execute transactions simultaneously and independently, as the execution outcomes may diverge across different nodes. To eliminate such inconsistencies, nondeterministic protocols typically operate under a two-stage execution architecture [9]–[12] to ensure that all participating nodes produce identical serializable results. As illustrated in Fig. 1, the primary node first utilizes a nondeterministic protocol to execute transactions in parallel. Once execution completes, the primary node generates scheduling metadata that captures the exact dependencies between transactions and disseminates it to replica nodes This work was funded by the Beijing Advanced Innovation Center for Future Blockchain and Privacy Computing.

during one of the communication rounds of the BFT protocol. Subsequently, replica nodes use this metadata to guide their replay, thereby producing the exact same serializable outcome as the primary node. Obviously, this workflow introduces a strict serial dependency between the primary node and replica nodes, which limits inter-node parallelism and reduces overall executionlayer throughput. Specifically, we identify three key properties when adopting nondeterministic protocol under the two-stage execution architecture: (i) Cumulative Latency, where the overall execution latency is cumulative, equaling the sum of the execution stage and the replay stage; (ii) Efficient Replay, since transaction conflicts are already resolved during the execution stage, the replay stage is completely decoupled from conflict resolution and only needs to replay transactions based on the metadata, yielding a significantly higher throughput; and (iii) Metadata Dependency, meaning the replay stage is strictly contingent upon the scheduling metadata generated during the execution stage and cannot function independently. ChainMaker [8] adopts a nondeterministic protocol based on optimistic concurrency control (OCC) [13], relying on the aforementioned two-stage execution architecture to guarantee state consistency across nodes. As China’s most prominent consortium blockchain platform—securing the top domestic market share for three consecutive years since its launch in 2021 [14]—ChainMaker serves as a representative baseline for our study. In contrast, deterministic concurrency control protocols [15]–[19] allow all participating nodes to execute transactions simultaneously in a single execution stage while deterministically reaching identical serializable results. Such deterministic protocols are well-suited for the Order-Execute (OE) architecture [20]–[22]. As illustrated in Fig. 2, in the order stage, all nodes leverage a BFT protocol to establish a globally ordered transaction sequence. In the subsequent execution stage, all nodes take this identical transaction sequence as input and employ a deterministic protocol to output an identical serializable outcome. Compared with the two-stage execution architecture, the OE architecture eliminates the strict serial dependency between the primary node and replica nodes, thereby completely avoiding the issue of Cumulative Latency. Furthermore, deterministic protocols can be categorized into static-analysis-based protocols [15], [16], [23], [24] and runtime protocols [17], [18], [20]. The former rely on a

First Stage Node1 Node2

Order Stage

Second Stage replay

execution

Execute Stage

Node1

execution

Node2

execution

Node3

replay

Node3

execution

Node4

replay

Node4

execution

BFT Protocols

BFT Protocols

EDCC Protocol

Fig. 1: Two-Stage Execution Architecture

Fig. 2: Order-Execute (OE) architecture

priori knowledge of transaction read-write sets to determine a schedule in advance. However, this assumption is often impractical in blockchain environments. Since smart contracts are typically quasi-Turing-complete [25], their read and write sets generally cannot be accurately determined prior to execution. Therefore, runtime protocols that do not require prior knowledge are imperative for blockchain systems. In this paper, we propose Lantern, a deterministic concurrency control protocol tailored for high-performance transaction processing systems that eliminates the need for prior knowledge of transaction read-write sets. By employing a batch-based graph construction scheme, Lantern strictly confines transaction dependencies within individual batches. Within each batch, all zero-out-degree vertices in the dependency graph are identified as committable transactions, which are committed in ascending order by leveraging the overwrite behavior inherent in serial execution. At its core, Lantern further introduces a deterministic Back-Propagation mechanism that iteratively propagates dependency states from sink to source vertices to improve the transaction commit rate, for which we provide a rigorous theoretical proof of liveness. In addition, Lantern integrates a Conflict-Free Batch Selection (CFBS) mechanism to mitigate star-like dependency graphs under hot-account read-modify-write scenarios. Beyond blockchain systems, Lantern is highly extensible to general database systems. In deterministic databases [26], a sequencing layer typically establishes a total order over incoming transactions, utilizing a replicated log backed by crash fault-tolerant (CFT) protocols to guarantee fault tolerance. Once this globally agreed-upon transaction sequence is established, each node can independently and concurrently leverage Lantern to achieve highly efficient execution, producing an identical, serializable outcome. More broadly, Lantern can be seamlessly integrated into any system that provides a globally ordered transaction stream. As a state-of-the-art protocol, Aria [17] was originally proposed for deterministic OLTP databases. Because Aria is deterministic and requires no prior read-write knowledge, it can also be seamlessly applied to blockchain systems. While both Lantern and Aria fall into the same category of deterministic protocols that operate without prior knowledge,

Lantern achieves significantly higher throughput. Furthermore, Lantern establishes its serializability [27], [28] through a constructive proof, which enables empirical validation of both its serializability and determinism. In contrast, Aria relies on an existence proof for its serializability, making it impossible to directly validate this property through experimental evaluation. Block-STM [18] also addresses parallel execution. However, Block-STM is highly VM-assisted and can only achieve its peak performance when paired with their customized Aptos VM. For instance, it requires the underlying virtual machine to suspend execution upon encountering a read conflict and resume it once the conflict is resolved. This suspensionand-resumption capability is currently supported only by the Aptos VM and is absent from most mainstream execution engines, including Wasmer, EVM, Docker-Go, and Diem VM, etc. Consequently, Block-STM exhibits poor portability, making it exceptionally difficult to port to other blockchain platforms. In contrast, our proposed Lantern is entirely VMagnostic. Because Lantern performs transaction scheduling solely based on read-write sets, it remains completely oblivious to the underlying execution environments, thereby serving as a highly generic protocol. Furthermore, Lantern uniquely enables multiple heterogeneous VM engines to coexist within a single blockchain system while using Lantern as their unified concurrency control protocol. Another well-known work is Hyperledger Fabric [29], which adopts the Execute-Order-Validate (EOV) architecture with multiple participating roles. Specifically, clients first send transaction proposals to endorsing peers. These endorsing peers execute the transactions in parallel and generate corresponding read-write sets. The read-write sets are then returned to the client, which assembles them into formal transactions and forwards them to the trusted ordering service. The ordering service establishes a total order for the transactions based on their arrival, packages them into blocks, and disseminates these blocks to all peers. Upon receiving a block, each peer validates the transactions to detect conflicts before updating the world state with the valid ones. To optimize this EOV architecture, several variants have been proposed, such as Fabric++ [30], Fabric# [31], and XOX Fabric [32]. In contrast to these system-level optimizations tailored for Fabric’s EOV

architecture, Lantern is an independent protocol that can be seamlessly integrated into any system providing a globally agreed transaction sequence, where all nodes leverage Lantern to execute transactions independently and concurrently without inter-node coordination. We have fully integrated Lantern into the open-source blockchain platform ChainMaker [8]. Comprehensive evaluations on both YCSB and SmallBank benchmarks demonstrate that Lantern outperforms Aria [17] by up to 4.2× in throughput. Furthermore, by eliminating the serial execution-replay dependency between primary and replica nodes, Lantern boosts ChainMaker’s execution layer throughput by at least 2.2×. II. BACKGROUND This section first establishes the formal definitions of deterministic concurrency control (DCC), followed by the directed graph preliminaries essential to Lantern. A. Deterministic Concurrency Control In distributed systems, DCC empowers all nodes to execute transactions concurrently and independently while guaranteeing identical execution results across the network. Unlike traditional nondeterministic protocols that only ensure serializability [27], [28], DCC xguarantees both serializability and determinism. Let S denote the initial world state, and let T = ⟨TX 1 , TX 2 , . . . , TX n ⟩ be a transaction sequence with a predefined order. The concepts of serializability and determinism are formally defined as follows: Definition 1 (Serializability). A concurrent execution of T is serializable if it is equivalent to a serial execution under some permutation π(T ) of T . The permutation π(T ) is called the serializable order. Definition 2 (Determinism). A concurrent control protocol is deterministic if multiple independent executions of T on S always produce the identical serializable order π(T ). In Definition 1, “equivalent” means that, for every transaction, the concurrent execution and the corresponding serial execution produce identical read/write sets, thereby leading to the same final world state. B. Directed Graph Lantern models transaction dependencies using a directed graph. Formally, a directed graph is represented as G = (V, E) where V and E denote the sets of vertices and directed edges, respectively. For a vertex v ∈ V , its in-degree is the number of incoming edges pointing to v, whereas its out-degree is the number of outgoing edges originating from v. A vertex with an in-degree of zero is referred to as a source vertex, while a vertex with an out-degree of zero is called a sink vertex. These boundary vertices play a pivotal role in the BackPropagation mechanism of Lantern, where the dependency state is propagated from sink vertices toward source vertices.

Select

TX0 TX4

TX7

TX8

TX2

TX10

TX11

TX12

...

TX9

...

Pending Sequence

TX1

TX3

TX2 TX5

TX9

TX4

TX6

TX8

TX6 Pending Sequence

Directed Graph Reinsert

Fig. 3: High-Level Transaction Processing of Lantern

A directed cycle exists if a directed path originates from a vertex and eventually returns to it. A directed graph containing no cycles is termed a directed acyclic graph (DAG). The problem of removing the minimum number of vertices to eliminate all cycles from a directed graph, thereby transforming it into a DAG, is known as the Feedback Vertex Set (FVS) problem [33], which is NP-hard. III. L ANTERN D ESIGN This section begins with an overview of the Lantern, followed by a detailed breakdown of its pipeline in Sections III-B through III-D. Following that, Section III-E introduces a crucial performance optimization called the backpropagation mechanism, whose liveness is rigorously proven in Section III-F. In Section III-G, we introduce a conflict-free batch-selection mechanism for RMW-intensive scenarios. Finally, we provide a proof of Lantern’s serializability in Section III-H. A. Design Overview In blockchain systems, a block comprises a substantial number of transactions awaiting processing. As illustrated in Fig. 3, Lantern initially selects a fixed number of transactions with the smallest indices from the pending sequence to initiate a processing round. Within each round, Lantern constructs a local dependency graph for these selected transactions and applies a back-propagation mechanism to identify a deterministic, committable set of transactions. The remaining, aborted transactions are then sorted in ascending order of their indices and reinserted at the head of the pending sequence. Lantern subsequently retrieves transactions from this updated sequence to start the next round. This process loops continuously until the pending transaction sequence is exhausted, marking the completion of the block processing. The following subsections describe each core component of Lantern in detail. B. Transaction Selection and Parallel Execution Before executing transactions with Lantern, all nodes in the network reach consensus on a globally ordered transaction sequence. Each node then takes this identical sequence as input and executes transactions independently. To build a dependency graph that captures transaction dependencies, Lantern

first executes transactions to extract their respective read and write sets. The detailed process is as follows: 1) Selection Phase: Let Bsize denote the number of transactions processed in each execution round. To maintain determinism, every node is configured with an identical batch size Bsize and adheres to a deterministic selection rule: the Bsize transactions with the lowest indices are popped from the pending transaction queue to form the current batch. Consequently, all nodes are guaranteed to select an identical transaction set for execution. 2) Execution Phase: Following selection, each node executes all selected transactions concurrently against its current world state. During this speculative execution, write operations are strictly buffered rather than directly committed, ensuring that the underlying world state remains invariant. Upon completing the execution of a transaction TX i , the node captures and caches its corresponding read set ReadSet(TXi ) and write set WriteSet(TXi ). Because all nodes start from an identical world state that remains unmutated throughout this phase, the generated read-write sets for each transaction are guaranteed to be deterministic and identical across the entire network. C. DAG Construction Following the parallel execution of the selected transactions, data conflicts may arise that threaten execution serializability. Lantern focuses exclusively on Read-After-Write (RAW) conflicts, which are formalized as follows: Definition 3 (RAW Conflict). A transaction TX i has a RAW conflict with a preceding transaction TX j (j < i) if TX i reads a data item that is written by TX j . Specifically, for each executed transaction, we only consider whether its read set conflicts with the write sets of preceding transactions (i.e., those with lower indices). Conversely, write operations by subsequent transactions (with higher indices) do not affect the correctness of the current transaction’s reads. Consequently, if a subset of transactions within the current batch is deemed committable, there exists only one permutation that can serve as their serializable execution order, i.e., the ascending order. To systematically capture RAW conflicts among transactions in the current batch, Lantern constructs a dependency graph according to Rule 1: Rule 1 (Graph Construction). Each executed transaction in the batch corresponds to a vertex in the dependency graph. A directed edge (TX i → TX j ) is added from TX i to TX j if and only if TX i has a RAW conflict with a preceding transaction TX j (j < i). Self-loops are inherently excluded since a transaction cannot form an edge to itself (j ̸= i). Consequently, for every directed edge (TX i → TX j ) in the dependency graph, the start vertex always has a larger index than the end vertex (i > j). By construction, this strict topological ordering precludes any backward edges (i.e., from lower-indexed to higher-indexed transactions), guaranteeing that the generated dependency graph is inherently acyclic. In

Algorithm 1: Dependency Graph Construction Input : executed transaction sequence T = (TX 0 , TX 1 , . . . , TX n−1 ) Output: dependency graph DAG = (V, E) 1 V ← {0, 1, . . . , n − 1}; 2 E ← ∅; 3 foreach i ∈ {0, 1, . . . , n − 1} in parallel do 4 Ei ← ∅; // thread-local edge set for TX i 5 for j ← 0 to i − 1 do 6 foreach w ∈ WriteSet(TX j ) do 7 if w ∈ ReadSet(TX i ) then 8 Ei ← Ei ∪ {(i, j)}; 9 break; // one conflict is sufficient Sn−1 E ← i=0 Ei ; 11 return DAG = (V, E); 10

the remainder of this paper, we refer to this graph as a Directed Acyclic Graph (DAG). To construct the DAG efficiently, Algorithm 1 presents a parallel graph construction scheme utilizing the read sets ReadSet(TX i ) and write sets WriteSet(TX i ) cached during the Execution Phase. Because conflict detection for each transaction TX i depends solely on preceding transactions TX j (j < i), all transactions can evaluate their RAW dependencies fully in parallel (Line 3). To avoid lock contention during graph building, each worker thread maintains a thread-local outgoing edge set Ei dedicated to TX i (Line 4). For each preceding transaction TX j , thread i scans j’s write set; upon detecting the first write-read overlap with ReadSet(TX i ), the directed edge (i, j) is inserted into Ei , and the inner loop immediately breaks to bypass redundant key checks for TX j (Lines 5–9). Because thread i exclusively mutates its local outgoing edge set Ei , edge generation across threads is inherently collision-free and lockless. Sn−1Finally, all thread-local edge sets are merged into E = i=0 Ei (Line 12) to yield the complete dependency graph DAG = (V, E). The constructed DAG strictly guarantees determinism and consistency across all network nodes. This inherently holds because transaction indices are globally identical, and speculative execution yields strictly identical read and write sets for each transaction. D. Transaction Commitment Following Section III-C, we obtain a DAG that precisely captures the RAW conflicts among transactions. Crucially, any transaction corresponding to a vertex with zero outdegree—including both sink vertices and isolated vertices—is guaranteed not to read any data item modified by its preceding transactions. Consequently, its read operations are completely independent of writes from its preceding transactions, drawing data exclusively from the current world state. Therefore, all

TX0 TX3

TX4

TX0

TX1 TX2

TX2

TX3

TX0

TX3

TX2

permutation 1 (valid)

permutation 2 (invalid)

TX2

TX2

TX0

TX3

TX3

TX0

permutation 3 (invalid)

permutation 4 (invalid)

TX3

TX3

TX5 DAG

TX0

TX2

permutation 5 (invalid)

TX2

TX0

permutation 6 (invalid)

Fig. 4: Only the ascending order of zero-out-degree transactions forms a serializable execution order for the current round.

Algorithm 2: Transaction Commitment Input : DAG = (V, E); transaction set T Output: Updated world state 1 S ← {v ∈ V | outDegree(v) = 0}; 2 sort S in ascending transaction-index order; 3 foreach i ∈ S do 4 foreach w ∈ WriteSet(TXi ) do 5 apply w to the world state; 6

return updated world state;

as follows: vertices with zero out-degree can be safely committed in the current round. The first challenge lies in determining which serial execution order is equivalent to the concurrent execution of these zero-out-degree transactions. As illustrated in Fig. 4, three committable transactions yield six possible permutations. Because Lantern exclusively tracks each transaction’s RAW conflicts against its preceding transactions, only the ascending order (Permutation 1 in Fig. 4) guarantees a valid serializable execution order. This holds because under the ascending order, every transaction TX i is preceded solely by transactions TX j with smaller indices (j < i). Since TX i possesses a zero out-degree in the DAG, it is explicitly guaranteed to have no RAW dependencies on any preceding transaction TX j . Consequently, executing them serially in ascending order yields the exact same read values as their parallel speculative execution against the initial world state. Conversely, all other permutations are invalid. Consider Permutation 2 ⟨TX 0 , TX 3 , TX 2 ⟩, where TX 3 precedes TX 2 . In a true serial execution under this order, TX 2 ’s reads must observe any updates previously committed by TX 3 . However, during the speculative Execution Phase, TX 2 executed against the initial, invariant world state—which omits TX 3 ’s writes. This introduces a potential TX 2 → TX 3 dependency. Because our DAG construction intentionally omits such backward edges to preclude cycles, we cannot verify whether such a potential write-then-read conflict exists between TX 3 and TX 2 , which would invalidate Permutation 2. The same reasoning applies to the remaining four permutations, as each places at least one higher-indexed transaction before a lower-indexed one. The second challenge lies in ensuring true equivalence to serial execution in ascending order. Regarding read operations, Lantern guarantees that no committable transaction reads any data item modified by its preceding transactions, thereby eliminating dirty reads. However, regarding write operations, write-write (WW) conflicts may still occur when multiple transactions update the same data key. To maintain full equivalence to ascending serial execution, Lantern must preserve the overwrite semantics inherent to serial processing—specifically, when multiple transactions write to the same key, the transaction appearing later in the sequence must overwrite the values written by earlier ones. Therefore, the commit rule is specified

Rule 2 (Commit). For all committable transactions, sort them in ascending order of their indices and apply their write sets to the world state. If multiple transactions write to the same key, preserve only the value written by the transaction with the highest index. Algorithm 2 details our commitment procedure. By applying the write set of each transaction to the world state serially, this process naturally satisfies the required overwrite semantics. Since this state update phase is lightweight, we intentionally forgo parallelization techniques—such as Compare-and-Swap (CAS)—to eliminate unnecessary concurrency overhead. This commitment phase strictly guarantees network-wide determinism across iterative rounds. This holds because all nodes construct an identical DAG (Section III-C) and deterministically derive the exact same set of zero-out-degree transactions for commitment. With globally uniform write sets, the resulting world state remains perfectly consistent across all nodes, serving as the deterministic initial state for the next round. Concurrently, uncommitted transactions (represented by gray vertices in Fig. 4) are sorted in ascending order of their indices and reinserted at the head of the pending queue, yielding an updated sequence that is likewise identical across all nodes. By ensuring that every round begins with an identical world state and pending transaction sequence, Lantern guarantees deterministic transaction processing across the entire network. E. Back-Propagation Mechanism Sections III-B through III-D detail the baseline execution pipeline of Lantern. However, restricting commitments strictly to zero-out-degree vertices is inherently conservative, prematurely aborting conflict-free transactions that reside deeper in the dependency chain. To overcome this limitation, we introduce a novel Back-Propagation mechanism that systematically salvages additional committable transactions while strictly preserving network-wide determinism. To establish the foundation of status propagation, we first clarify the precise semantics of dependency edges. A directed edge TX i → TX j indicates a RAW dependency of TX i on TX j . Since all transactions are executed against the same initial world state during the Execution Phase, committing TX j in the current round invalidates the execution of TX i

TX3 TX5

TX1

TX5 TX0

TX4 TX3 TX5

TX1

TX3

TX2 TX5 TX0

TX4

TX1

TX6

TX0

TX7

TX6

TX6

TX0 TX3 TX7

TX6

TX1

TX2

TX4 TX7

TX2

TX4 TX7

TX3

TX2

TX5 TX1

TX3

TX2 TX5 TX0

TX4

TX1

TX2

TX0

TX4 TX7 TX6

TX7 TX6

Fig. 5: A motivating example demonstrating the potential of transaction salvage and the issue of nondeterminism. due to a “dirty read”, forcing TX i to abort. Conversely, for TX i to safely commit, TX j must be aborted to ensure that the state read by TX i remains “clean”. Consider the dependency graph in Fig. 5. Under the baseline approach, only the two sink vertices (TX 0 and TX 2 ) are committed, while all remaining transactions are aborted. Specifically, because TX 1 and TX 3 directly depend on these two sink transactions, they must be aborted to avoid dirty reads. Crucially, once TX 1 and TX 3 are deterministically aborted, their write operations are discarded, effectively eliminating the dependency edges they induce on upstream transactions. As illustrated in the upper branch of Fig. 5, if we salvage transactions along the upper path, TX 4 and TX 5 become eligible for commitment alongside the baseline sinks. Furthermore, committing TX 4 forces its reader TX 6 to abort to prevent a dirty read, which subsequently frees TX 7 for commitment. In total, five transactions—{TX 0 , TX 2 , TX 4 , TX 5 , TX 7 }—can be safely committed. Because these salvaged transactions are guaranteed to be RAW-conflict-free against their committable predecessors, they can be safely committed in ascending order without violating serializability. However, as shown in the lower branch of Fig. 5, an alternative path emerges once TX 1 is deterministically aborted. Specifically, the dependency edge restricting TX 6 also disappears. If we instead mark TX 6 as committable, TX 4 must be aborted to ensure that TX 6 ’s read set remains uncontaminated. Concurrently, TX 7 must also be aborted to prevent a dirty read from TX 6 . This path yields a completely different set of committable transactions. While both branches successfully salvage more transactions than the baseline, the existence of multiple valid execution paths introduces severe nondeterminism. Thus, the core challenge lies in designing a mechanism that expands the committable set without compromising state consistency across distributed nodes. To achieve this, Lantern adopts a novel Back-Propagation mechanism inspired by error backpropagation in neural networks. Starting from the sink vertices, status markings propagate backward toward the source vertices according to four deterministic rules:

Rule 3 (Back-Propagation). (i) Initialization (Red): All zero-out-degree vertices in the DAG are initially marked red. (ii) Conflict Propagation (Gray): Any unmarked vertex with a directed edge pointing to a red vertex is marked gray. (iii) Salvage Propagation (Red): Any unmarked vertex whose successors are exclusively marked gray is marked red. (iv) Termination: Steps (ii) and (iii) are repeated iteratively in alternating phases until no further state transitions occur. Specifically, (i) Initialization directly corresponds to the baseline commit scheme presented in Section III-D. (ii) Conflict Propagation identifies transactions that must abort because they would incur dirty reads from guaranteed committable transactions. (iii) In Salvage Propagation, the condition “exclusively” is paramount: if an unmarked vertex points to both a gray vertex and an unresolved unmarked vertex, its status remains ambiguous because its unmarked successor’s outcome is still unresolved. Requiring all successors to be gray guarantees that no committed predecessor will invalidate this vertex’s read set, ensuring it can safely commit. Algorithm 3 formalizes this iterative layer-by-layer procedure. In each iteration, Lantern first collects an unmarked candidate set candidates comprising the reverse neighbors (i.e., predecessors) of the current layer (Lines 9–14). When the current layer is red, all vertices in candidates are directly marked gray (Lines 16–19). Conversely, when the current layer is gray, if all successors of a candidate vertex are confirmed to be marked, those successors are guaranteed to be exclusively gray, allowing the candidate vertex to be safely marked red (Lines 22–29). This guarantee holds because candidates are derived solely from the current gray layer; thus, a candidate vertex can point only to gray or unmarked vertices, but never to a red one. Had it possessed a directed edge to a previously generated red vertex, it would have been unconditionally marked gray in the iteration immediately following that red layer’s processing, directly contradicting its current unmarked status. When candidate vertices qualify to be marked red, they are first collected into a temporary set, redCandidates (Lines 28– 29), rather than being marked immediately. The actual state transitions are performed only after all candidate vertices in the current layer have been fully evaluated (Lines 30–32). This deferred-marking strategy ensures that every decision within the same propagation layer is evaluated against a static and consistent graph state. Without this deferral, immediate state updates would allow newly marked red vertices to improperly influence the evaluation of remaining candidates in the same layer. Such premature updates would not only compromise algorithm correctness by causing erroneous transitions, but also introduce non-determinism when candidate vertices are processed in an arbitrary traversal order. Fig. 6 illustrates a step-by-step example of BackPropagation. In Round 1, four zero-out-degree vertices are initially marked red. In Round 2, Lantern identifies the reverse neighbors of this initial layer, forming the candidate set

Algorithm 3: Back-Propagation Input : Directed acyclic graph G = (V, E) Output: Committable transaction set R; Uncommittable transaction set G 1 foreach v ∈ V do 2 mark [v] ← unmarked; layer ← ∅; foreach v ∈ V do 5 if outDegree(v) = 0 then 6 mark [v] ← red; 7 add v to layer ;

3 4

isRedLayer ← true; while there exists unmarked vertices in V do 10 candidates ← ∅; 11 foreach v ∈ layer do 12 foreach u ∈ reverseN eighbors(v) do 13 if mark [u] = unmarked then 14 add u to candidates; 8 9

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

nextLayer ← ∅; if isRedLayer = true then foreach u ∈ candidates do mark [u] ← gray; add u to nextLayer ; else redCandidates ← ∅; foreach u ∈ candidates do allMarked ← true; foreach w ∈ neighbors(u) do if mark [w] = unmarked then allMarked ← f alse; break; if allMarked = true then add u to redCandidates; foreach u ∈ redCandidates do mark [u] ← red; add u to nextLayer ; layer ← nextLayer ; isRedLayer ← ¬isRedLayer ;

R ← {v ∈ V | mark [v] = red}; G ← {v ∈ V | mark [v] = gray}; 37 return R, G; 35 36

{TX 1 , TX 6 , TX 10 }. Because the preceding layer was red, all vertices in this candidate set are unconditionally marked gray. In Round 3, the candidates {TX 2 , TX 4 , TX 7 , TX 12 , TX 13 } are evaluated. Since TX 7 points to TX 4 , which remains unmarked, TX 7 retains its unmarked status. The remaining candidates are marked red because their successors are exclusively gray. In Round 4, TX 7 is again collected into

the candidate set {TX 7 , TX 9 , TX 11 }, and all candidates are unconditionally marked gray. Finally, in Round 5, TX 14 is marked red, completing the propagation process. Back-Propagation strictly guarantees network-wide determinism, ensuring that every node produces an identically colored DAG. This holds because the underlying DAG topology is identical across all participating nodes. Specifically, all nodes initialize the exact same set of red vertices. Inductively, because each subsequent marking round depends solely on the deterministic state of preceding layers, both (1) gray vertices assigned under Conflict Propagation and (2) red vertices assigned under Salvage Propagation remain strictly uniform across nodes. By induction, this state consistency propagates throughout all iterations, guaranteeing an identical coloring outcome for the DAG. Once Back-Propagation completes, all transactions marked red are collected as the final committable set. These transactions are sorted in ascending order of their indices and serially applied to the world state following Rule 2, while uncommitted gray transactions are sorted in ascending order of their indices and reinserted at the head of the pending queue. The proposed Back-Propagation mechanism increases the number of committable transactions while strictly preserving determinism across all participating nodes. However, a critical question arises: could this iterative marking process encounter a liveness bottleneck, causing the algorithm to stall or fail to terminate? To establish the theoretical soundness of our design and address this concern, we formally prove the liveness of the Back-Propagation mechanism in Section III-F. F. Liveness of Back-Propagation We first introduce two supporting lemmas to dissect the iterative marking mechanism before proving the main theorem. Lemma 1. In any iteration of the Back-Propagation process, as long as the set of unmarked vertices in the DAG is nonempty, the generated candidates set is guaranteed to be nonempty. Proof. During initialization, all global sink vertices and isolated vertices in DAG are marked red, meaning any remaining unmarked vertices must have outgoing edges. Let U be the non-empty set of unmarked vertices, and let Lk be the current layer serving as the active frontier. Since DAG is a acyclic, the subgraph G′ [U] induced by U must also be a DAG, which guarantees the existence of at least one local sink vertex u ∈ U. By definition, u has no outgoing edges targeting any other vertex within G′ [U]. However, since u is a unmarked vertex in DAG which must have outgoing edges, all successors of u must reside outside of U, meaning they have already been marked in previous iterations. We now prove by contradiction that u must possess at least one directed edge pointing to the current layer Lk . Suppose u does not point to Lk . Then all successors of u must belong to strictly older historical layers. Let Lt (t < k) be the most recently generated layer among all successors of u. During the historical iteration when Lt served as the active layer, u

TX1

TX2 TX7

TX9

TX11

TX1

TX0

TX4

TX8

TX2 TX7

TX9

TX3

TX8

TX12

(a) Round 1

TX3

TX11

TX8

TX3

TX14 TX5

TX6 TX13

TX10 TX12

(c) Round 3

TX2 TX7

TX9

TX5

TX6

TX10 TX12

(b) Round 2

TX8

TX0

TX4

TX3

TX13

TX13

TX12

TX11

TX5

TX6

TX10

TX10

TX2 TX7

TX9

TX1

TX0

TX4

TX14

TX5

TX6 TX13

TX13

TX11

TX8

TX14

TX5

TX6

TX2 TX7

TX9

TX1

TX0

TX4

TX3

TX11 TX14

TX14

TX1

TX0

TX4

(d) Round 4

TX10 TX12

(e) Round 5

Fig. 6: An Example of Back-Propagation in Lantern

would have been fetched into the candidates set. At that time, we evaluate the state transition of u: (i) If Lt was a red layer: u would be directly marked gray. (ii) If Lt was a gray layer: The algorithm checks the allMarked condition for u. Because Lt is the most recent layer among u’s successors, all successors of u are already marked. Therefore, u satisfies the allMarked condition and is marked red. In either case, u would have been successfully marked during that historical iteration. This directly contradicts the established premise that u is currently an unmarked vertex. Therefore, the assumption is false. u must possess at least one successor in the current layer Lk . As a result, u will inevitably be fetched into candidates, ensuring candidates ̸= ∅. Lemma 2. Given a non-empty candidates set in any iteration, at least one candidate within this set is guaranteed to be marked. Proof. We evaluate the two propagation branches based on the current layer Lt : (i) If Lt was a red layer: All vertices in candidates are unconditionally marked gray. Since candidates ̸= ∅, at least one vertex transitions to the gray state. (ii) If Lt was a gray layer: First, any vertex in candidates can only point to gray or unmarked vertices. Second, recall the local sink vertex u of the global unmarked subgraph G′ [U] from Lemma 1, which is guaranteed to be fetched into candidates. As the sink of G′ [U], u has no outgoing edges to any unmarked vertices. Combining these two constraints, the outgoing edges of u ∈ candidates must exclusively point to gray vertices. Therefore, u is guaranteed to be marked red. In both cases, at least one unmarked candidate vertex successfully transitions to a marked state. Theorem 1 (Liveness). If the dependency graph G = (V, E) is acyclic (DAG), the Back-Propagation process satisfies the liveness property and is guaranteed to terminate within a finite number of iterations.

Proof. During initialization, all global zero-out-degree vertices of DAG are successfully marked red, establishing the initial non-empty layer . In each subsequent iteration, if unmarked vertices remain, Lemma 1 guarantees that the fetched candidates set is non-empty. Subsequently, Lemma 2 guarantees that at least one vertex from this candidates set transitions from an unmarked to a marked state. Given that the total number of vertices |V | is finite and each vertex changes its state at most once, therefore, the algorithm must terminate after at most |V | iterations. The upper bound of |V | iterations corresponds to the worst-case scenario where the DAG forms a linear chain (TX 0 ← TX 1 ← · · · ← TX |V |−1 ). G. Conflict-Free Batch Selection Mechanism While the Back-Propagation mechanism effectively finds more committable transactions when the DAG is deep, it remains constrained in Read-Modify-Write (RMW) dominant scenarios. In an RMW operation, a transaction first reads a data item’s current state, performs internal business logic, and subsequently writes the updated state back to the same item. A common real-world example is found in financial applications: • Deposit/Withdrawal: A transaction reads account A’s balance bal A , adds or subtracts an amount v, and writes the new balance (bal A ± v) back to A. • Transfer: A transaction reads the balances of both sender A (bal A ) and receiver B (bal B ), and writes the updated values (bal A − v) and (bal B + v) back to A and B, respectively. In Lantern’s standard batch processing pattern, if multiple transactions within a single batch target the same hot account (e.g., account A) with RMW operations, only a single transaction can be committed. As illustrated in Fig. 7, because each transaction performs both read and write operations on account A’s balance, every transaction in the batch develops a RAW dependency on all of its preceding transactions. This results in a shallow, star-like DAG where only the first transaction TX 0 can be safely committed; according to the Conflict Propagation rule (Rule 3(ii)), all subsequent transactions must be aborted to prevent dirty reads from TX 0 . To resolve this issue, we propose the Conflict-Free Batch Selection (CFBS) mechanism specifically for RMW-intensive

TX1

TX2 TX0

TX4

TX3

Fig. 7: An example of a shallow star-like DAG under hotaccount RMW operations, where only TX 0 is committable. workloads. The core insight of CFBS is to proactively avoid conflicts during the batch selection phase rather than reactively aborting transactions after execution. Before execution, a transaction’s accessed accounts can be statically extracted from its payload, as the input parameters for smart contract invocation explicitly specify the participating accounts. By leveraging this extracted account information, CFBS ensures that no two transactions selected within the same batch operate on overlapping accounts. Algorithm 4 details the CFBS procedure. Rather than blindly popping a fixed number of Bsize transactions with the smallest indices, CFBS sequentially scans the pending transaction sequence P in ascending index order. For each transaction TXi , CFBS extracts its target accounts Accounts TXi (Line 5). If these accounts do not overlap with the occupied account set O (Line 6), TXi is added to the selected set S, and its target accounts are merged into O (Lines 7–8). Otherwise, TXi is deferred and appended to the remaining sequence P ′ (Line 10). Consequently, the effective batch size becomes dynamic, defined as Bsize = |S|. CFBS strictly preserves determinism across the network. Because the targeted accounts extracted from each transaction’s payload are deterministic, and all nodes execute Algorithm 4 over the identical pending sequence P in the exact same ascending order, every node independently derives the identical selected batch S for each round. H. Proof of Serializability This section formally proves the serializability of Lantern. Theorem 2 first derives the equivalent serializable order within a single batch. Subsequently, Theorem 3 extends this equivalence to the block level. Theorem 2 (Intra-Batch Serializability). Within a single batch, the equivalent serializable order of all committed transactions in Lantern is determined by their transaction indices in ascending order. Proof. On the read side, following the Back-Propagation mechanism, each committable transaction either has no dependencies on other transactions or depends exclusively on transactions aborted in the current round. Consequently, no dirty reads can occur among committable transactions, ensuring that all reads they issue originate from the same initial world state. On the write side, when multiple transactions conflict

Algorithm 4: Conflict-Free Batch Selection Input : pending transaction sequence P Output: selected transactions S; remaining sequence P′ 1 S ← ∅; ′ 2 P ← ∅; 3 O ← ∅; // occupied accounts 4 foreach TX i ∈ P in ascending order of i do 5 Accounts TX i ← ExtractAccounts(TX i ); 6 if Accounts TX i ∩ O = ∅ then 7 S ← S ∪ {TX i }; 8 O ← O ∪ Accounts TX i ; 9 10 11

else P ′ ← P ′ ∥ TX i ; return S, P ′ ;

on the same key, Lantern employs an overwrite mechanism that preserves only the write from the transaction with the highest index. This behavior is semantically equivalent to the overwrite semantics produced by executing all committable transactions serially in ascending order of their indices. Theorem 3 (Inter-Batch Serializability). The equivalent serializable order of an entire block in Lantern is obtained by sequentially composing the serializable orders of all batches in ascending order of their batch indices. Proof. Under the Lantern framework, execution across batches enforces strict isolation. Specifically, a subsequent batch Bi+1 starts only after all transactions in Bi complete and their write sets are applied to the world state. Viewing each batch as a “macro-transaction”, the state transitions between batches are logically equivalent to a serial execution of these macrotransactions. Thus, concatenating the internal serializable orders of all batches in ascending order of their batch indices yields the equivalent serializable order for the entire block. Example 1. Consider a block execution with a batch size Bsize = 5: • Batch 1: Lantern processes the initial batch B1 = {TX 0 , TX 1 , TX 2 , TX 3 , TX 4 } and commits the subset S1 = ⟨TX 0 , TX 2 , TX 3 ⟩. The aborted transactions {TX 1 , TX 4 } are reinserted at the head of the pending queue. • Batch 2: Lantern fetches the next batch B2 = {TX 1 , TX 4 , TX 5 , TX 6 , TX 7 } and commits the subset S2 = ⟨TX 1 , TX 4 , TX 6 ⟩. By sequentially concatenating the commit sequences across all batches, the equivalent serializable order π(T ) for the block is constructed as: π(T ) = S1 ∥S2 ∥· · · = ⟨TX 0 , TX 2 , TX 3 , TX 1 , TX 4 , TX 6 , . . . ⟩ | {z } | {z } Batch 1 (S1 )

Batch 2 (S2 )

Crucially, our serializability proof is constructive, enabling the explicit determination of the equivalent serializable order

π(T ) upon the completion of a block execution. This explicit construct of π(T ) allows us to empirically validate both the serializability and determinism of Lantern, as detailed in our evaluation (Section IV-B). Conversely, Aria’s serializability proof is purely existential. While it proves that an equivalent serializable schedule exists, it cannot explicitly construct the corresponding serializable order. This non-constructive nature prevents Aria from experimentally validating its serializability. IV. E VALUATION A. Experimental Setup Hardware Platform. All experiments are performed on a dedicated Linux server equipped with dual Intel(R) Xeon(R) Gold 5218 processors, offering a total of 32 physical CPU cores across two NUMA nodes (16 cores and 128 GB DDR4 local memory per node). The server runs CentOS Linux 7 (kernel version 3.10.0). Simultaneous Multithreading (SMT) is disabled in the BIOS to eliminate hardware thread contention. Software Platform. All evaluations are integrated into ChainMaker v2.3.8 [34]. Smart contracts are authored in Rust and executed on the Wasmer virtual machine. To ensure fairness, Lantern and all baseline protocols are compiled and executed using Go 1.24 with default compiler optimization settings. The underlying system adopts TBFT consensus [1], configured with a maximum block capacity of 1,000 transactions and a transaction pool limit of 50,000 transactions. To fully saturate the execution engine, the ChainMaker Go SDK client [35] is deployed on a separate dedicated server, spawning concurrent goroutines to submit workload transactions via gRPC. Baselines. We evaluate Lantern against two representative categories of concurrency control baselines: ChainMaker: ChainMaker’s default nondeterministic protocol based on Optimistic Concurrency Control (OCC) [13]. It operates under the two-stage execution architecture (Fig. 1), where total execution-layer latency is the combined duration of the primary execution stage and the replica replay stage. • Aria: A state-of-the-art deterministic protocol operating without a priori knowledge [17]. Since original work has demonstrated Aria’s superiority over classical deterministic protocols (such as Bohm [16], PWV [24], Calvin [15], and PB), we select it as our primary baseline and fully implement all optimization techniques proposed in its original paper. •

Unless otherwise specified, the batch size Bsize for Lantern is set at 5× the number of physical CPU cores. Workloads. We evaluate execution-layer throughput using two standard benchmarks: •

YCSB [36]: A micro-benchmark for fine-grained state access. Each transaction invokes a smart contract executing 10 operations (5 reads and 5 writes) over a key space of one million records. Within a single transaction, all read keys (and similarly, write keys) are unique. Intersections between a transaction’s read set and write set are allowed.

SmallBank [37]: A macro-benchmark with heavy RMW operations. Our implementation includes three tables (Account, Saving, and Checking) initialized with 100,000 accounts. Each account starts with 100,000 tokens in both its saving and checking balances. We evaluate the five state-modifying transaction types: send_payment (40%), deposit_checking (15%), transact_saving (15%), amalgamate (15%), and write_check (15%). Off-chain read-only queries (balance) and state initialization transactions (create_account) are excluded from throughput measurements. Measurement Methodology. All evaluations strictly focus on execution-layer throughput. To measure steady-state performance, boundary blocks are filtered out: initial warmup/initialization blocks (the first 5 blocks in YCSB and account creation blocks in SmallBank) as well as the trailing 50 draining blocks are omitted. Consequently, all reported metrics are calculated exclusively from the intermediate stable execution phase, with each metric averaged over at least 100 valid blocks. •

B. Correctness Validation Using the serializable order π(T ) derived in Section III-H, we validate Lantern’s correctness over 10,000 continuous blocks under high contention. Our validation comprises two phases: First, to verify determinism, each block is executed via Lantern in multiple independent runs; we observe that all runs consistently yield an identical serializable order. Second, to verify serializability, we sequentially re-execute the transactions according to the generated order π(T ). The evaluation results show that the read/write sets of each transaction perfectly match those from the concurrent execution, and the final state remains identical between the serial and concurrent executions. These empirical results demonstrate both the determinism and serializability of Lantern. C. Overall Performance On YCSB, we disable the CFBS mechanism as the workload does not feature intensive RMW operations. We evaluate Lantern alongside its variant Lantern-NoBP (without BackPropagation), as well as three baseline systems: ChainMaker, Aria, and Serial execution. On SmallBank, an RMW-intensive benchmark where the complete Lantern enables both BP and CFBS mechanisms by default, we conduct a comprehensive ablation study using four variants: full Lantern, LanternNoBP (with CFBS only), Lantern-NoCFBS (with BP only), and Lantern-NoBPandCFBS (disabling both mechanisms). For both benchmarks, we systematically vary the Zipfian skew parameter to simulate different levels of data contention. As illustrated in Fig. 8, Back-Propagation (BP) yields prominent performance gains under severe data contention. Specifically, when the Zipfian skew reaches 0.9, Lantern (6, 131 txn/s) outperforms Lantern-NoBP (2, 339 txn/s) by 2.6×. Compared to existing baseline systems, Lantern maintains a substantial throughput lead:

Lantern Lantern-NoBP

Lantern Lantern-NoBP

Serial

Throughput (k txn/s)

Throughput (k txn/s)

20k

ChainMaker Aria

15k 10k 5k 0.1

0.2

0.3

0.4

0.5 Skew

0.6

0.7

0.8

To eliminate potential performance anomalies caused by non-uniform memory access (NUMA) in our dual-socket Intel Xeon architecture, we enforce a balanced resource allocation strategy for scalability evaluations across 4, 8, 16, and 32 CPU cores. Specifically, we evenly bind CPU cores across the two NUMA sockets using taskset, and enable memory page interleaving via numactl --interleave=all. This setup ensures symmetric CPU scaling and uniform memory access latency across all core configurations.

0.7

10k 0.1

0.2

0.4

0.5 Skew

0.6

0.8

0.9

Fig. 9: Overall Throughput on SmallBank

Throughput (k txn/s)

ChainMaker Aria

Serial

Lantern Lantern-NoBP

Throughput (k txn/s)

Lantern Lantern-NoBP

•

D. Scalability

0.3

Serial

20k

Fig. 8: Overall Throughput on YCSB

On SmallBank (Fig. 9), the throughput curves of Lantern and Lantern-NoBP nearly overlap, as do those of LanternNoCFBS and Lantern-NoBPandCFBS. This observation indicates that Back-Propagation yields only marginal improvements under RMW-intensive scenarios. Conversely, the substantial performance gap between variants with CFBS (Lantern and Lantern-NoBP) and those without (Lantern-NoCFBS and Lantern-NoBPandCFBS) demonstrates the crucial role of the CFBS mechanism in handling RMW workloads. Specifically, CFBS boosts throughput by up to 1.84× under high contention (skew = 0.9, elevating throughput from 8, 035 txn/s for Lantern-NoCFBS to 14, 775 txn/s for Lantern). Furthermore, compared to the fully unoptimized baseline (LanternNoBPandCFBS), Lantern’s combined optimization achieves a 2.18× speedup.

Aria ChainMaker

30k

0.9

VS. Aria: Under extreme contention (skew = 0.9), Lantern outperforms Aria (1, 449 txn/s) by 4.2×. This performance gap originates from Aria’s deterministic execution model, which permits at most one transaction to commit write operations per key within a single batch, thereby disallowing concurrent write overwrites. Under write-intensive workloads, this strict reservation policy forces an excessive number of conflicting transactions to abort. • VS. ChainMaker: Lantern consistently outperforms ChainMaker by at least 2.2× across all contention levels. This advantage stems from the fact that ChainMaker’s nondeterministic protocol requires an additional replay stage to ensure cross-node consistency, thereby bottlenecking its overall throughput.

Lantern-NoCFBS Lantern-NoBPandCFBS

15k 10k 5k 4

8

16 Cores

(a) Uniform

32

ChainMaker Aria

Serial

6k

4k

2k 4

8

16 Cores

32

(b) Zipfian (Skew = 0.9)

Fig. 10: Scalability on YCSB

Fig. 10 illustrates the scalability results under the YCSB benchmark across different CPU core counts. Under a uniform distribution (Fig. 10a), data conflicts are extremely rare. Consequently, the Back-Propagation mechanism yields marginal performance gains, causing the throughput curves of Lantern and Lantern-NoBP to virtually overlap. Furthermore, all concurrent control protocols exhibit near-linear scalability as the core count increases from 4 to 32. In contrast, under severe contention (Fig. 10b), Lantern consistently outperforms Lantern-NoBP across all core configurations. Moreover, while the throughput of Lantern-NoBP, Aria, and ChainMaker plateaus or even degrades with more CPU cores, Lantern demonstrates superior scalability. Fig. 11 illustrates the scalability results under the SmallBank benchmark. When workload access is uniform (Fig. 11a), protocols integrated with the CFBS mechanism (Lantern and Lantern-NoBP) consistently outperform those without CFBS (Lantern-NoCFBS and Lantern-NoBPandCFBS). Under severe contention (Fig. 11b), Lantern and Lantern-NoBP outperform all other baselines by a wide margin. When CFBS is enabled, the performance curves of Lantern and Lantern-NoBP virtually overlap, indicating that Back-Propagation provides marginal benefit when conflicts are proactively eliminated during batch selection. However, when CFBS is disabled, Back-Propagation takes effect by salvaging valid transactions from the dependency graph; specifically, Lantern-NoCFBS achieves 7, 990 txn/s at 32 cores, outperforming LanternNoBPandCFBS (6, 886 txn/s) by 1.2×.

Lantern Lantern-NoBP Lantern-NoCFBS

30k 20k 10k 4

8

1. Selection 3. DAG Construction 5. Commit 2. Execution 4. Back-Propagation

Lantern-NoBPandCFBS

Throughput (k txn/s)

Throughput (k txn/s)

Lantern-NoBPandCFBS

Aria ChainMaker Serial

16 Cores

10k

5k 4

(a) Uniform

8

60

25

15k

32

1. Selection 3. DAG Construction 5. Commit 2. Execution 4. Back-Propagation

16 Cores

20

Latency (ms)

Aria ChainMaker Serial

Latency (ms)

Lantern Lantern-NoBP Lantern-NoCFBS

2 0

1

2

3 4 Phase

32

5

50 5 0

1

2

3 4 Phase

5

(a) Low Contention (Skew = 0.1) (b) High Contention (Skew = 0.9)

(b) Zipfian (Skew = 0.9)

Fig. 13: Phase-wise Latency Breakdown On SmallBank

Fig. 11: Scalability on SmallBank

40 4

140

2 0

1

2

3 4 Phase

5

5 0

2

3 4 Phase

5

Lantern-9

20k 15k 10k 5k 0.1

1

Lantern-5 Lantern-7

Lantern-1 Lantern-3

Throughput (k txn/s)

150 Latency (ms)

Latency (ms)

50

1. Selection 3. DAG Construction 5. Commit 2. Execution 4. Back-Propagation

Throughput (k txn/s)

1. Selection 3. DAG Construction 5. Commit 2. Execution 4. Back-Propagation

Lantern-1 Lantern-3

0.3

0.5 Skew

0.7

0.9

Lantern-9

30k 20k 10k 0.1

(a) YCSB

(a) Low Contention (Skew = 0.1) (b) High Contention (Skew = 0.9)

Lantern-5 Lantern-7

0.3

0.5 Skew

0.7

0.9

(b) SmallBank

Fig. 14: Impact of Batch Size Bsize

Fig. 12: Phase-wise Latency Breakdown On YCSB Low-to-Moderate Contention (skew ≤ 0.7): Larger batch sizes consistently achieve higher throughput. Increasing Bsize from 1× to 5× yields substantial performance gains because a larger batch exposes greater intra-batch parallelism and amortizes scheduling overheads. However, further increasing Bsize to 7× and 9× yields diminishing marginal returns as multi-core hardware execution capacity saturates. • Severe Contention (skew = 0.9): The throughput trend completely reverses. Lantern-1 achieves the highest throughput, whereas throughput monotonically degrades as Bsize increases. This degradation occurs because a large batch under high contention leads to low transaction commit ratios, and severe computational resource wastage from frequent aborts. In contrast, a smaller batch size bounds the contention domain per execution round, maintaining a higher commit ratio and ensuring stable throughput. Based on these findings, Lantern adopts Bsize = 5 × CPU cores as its default configuration, balancing parallel throughput under low contention with robust handling of data conflicts.

•

E. Latency Breakdown In this section, we evaluate the phase-wise latency breakdown of Lantern under both low-contention (Zipfian skew = 0.1) and high-contention (Zipfian skew = 0.9) workloads. Fig. 12 illustrates the detailed latency distribution on YCSB. Under low contention (Fig. 12a), transaction execution dominates the block latency, with the Execution phase consuming 48.9 ms, followed by the Commit phase at 3.3 ms. The remaining scheduling operations—including Selection, DAG Construction, and Back-Propagation—account for only 4.9% of the total latency, demonstrating Lantern’s minimal scheduling overhead. Under high contention (Fig. 12b), severe conflicts force aborted transactions into subsequent rounds for re-execution, increasing the Execution phase latency to 150.8 ms. On SmallBank (Fig. 13), where the CFBS mechanism is enabled to proactively prevent hot-account conflicts, the Selection phase incurs 1.0 ms and 4.9 ms under skew 0.1 and 0.9, respectively. F. Impact of Batch Size Bsize In this section, we evaluate the impact of the batch size Bsize on throughput. We compare five configurations where Bsize is fixed to 1×, 3×, 5×, 7×, and 9× the CPU physical core count (denoted as Lantern-1 through Lantern-9). Note that on the SmallBank benchmark, the CFBS mechanism is disabled to prevent Bsize from becoming dynamic during processing. Fig. 14 presents the results, revealing a clear performance trade-off across both workloads:

V. C ONCLUSION In this paper, we presented Lantern, a deterministic concurrency control protocol designed for high-performance transaction processing systems operating without prior read-write knowledge. By combining an overwrite-permissive strategy on DAGs with a deterministic Back-Propagation mechanism, Lantern significantly expands the set of committable transactions per batch while maintaining cross-node state consistency.

Additionally, its Conflict-Free Batch Selection (CFBS) mechanism effectively eliminates contention under RMW-intensive scenarios. We integrated Lantern into ChainMaker and evaluated it on YCSB and SmallBank benchmarks. The results demonstrate that Lantern achieves up to a 4.2× throughput speedup over Aria and improves ChainMaker’s execution-layer throughput by at least 2.2×. R EFERENCES [1] J. Kwon, “Tendermint: Consensus without mining,” https://tendermint. com/static/docs/tendermint.pdf, 2014. [2] M. Yin, D. Malkhi, M. K. Reiter, G. G. Gueta, and I. Abraham, “Hotstuff: Bft consensus with linearity and responsiveness,” in Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, ser. PODC ’19. ACM, 2019, p. 347–356. [Online]. Available: https://doi.org/10.1145/3293611.3331591 [3] G. Golan Gueta, I. Abraham, S. Grossman, D. Malkhi, B. Pinkas, M. Reiter, D.-A. Seredinschi, O. Tamir, and A. Tomescu, “Sbft: A scalable and decentralized trust infrastructure,” in 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), 2019, pp. 568–580. [4] S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” 2009. [Online]. Available: https://bitcoin.org/bitcoin.pdf [5] V. Buterin, “A next-generation smart contract and decentralized application platform,” 2014. [Online]. Available: https://ethereum.org/ whitepaper/ [6] C. Jin, S. Pang, X. Qi, Z. Zhang, and A. Zhou, “A high performance concurrency protocol for smart contracts of permissioned blockchain,” IEEE Transactions on Knowledge and Data Engineering, vol. 34, no. 11, pp. 5070–5083, 2022. [7] T. Dickerson, P. Gazzillo, M. Herlihy, and E. Koskinen, “Adding concurrency to smart contracts,” in Proceedings of the ACM Symposium on Principles of Distributed Computing, ser. PODC ’17. ACM, 2017, p. 303–312. [Online]. Available: https://doi.org/10.1145/3087801.3087835 [8] ChainMaker Team, “Chainmaker,” Jan. 2021. [Online]. Available: https://chainmaker.org.cn/home [9] P. S. Anjana, S. Kumari, S. Peri, S. Rathor, and A. Somani, “An efficient framework for optimistic concurrent execution of smart contracts,” in 2019 27th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP), 2019, pp. 83–92. [10] M. J. Amiri, D. Agrawal, and A. El Abbadi, “Parblockchain: Leveraging transaction parallelism in permissioned blockchain systems,” in 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS), 2019, pp. 1337–1347. [11] M. Kapritsos, Y. Wang, V. Quéma, A. Clement, L. Alvisi, and M. Dahlin, “All about eve: Execute-verify replication for multi-core servers,” in 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, October 8-10, 2012, C. Thekkath and A. Vahdat, Eds. USENIX Association, 2012, pp. 237–250. [Online]. Available: https://www.usenix.org/conference/ osdi12/technical-sessions/presentation/kapritsos [12] P. S. Anjana, “Efficient parallel execution of block transactions in blockchain,” in Proceedings of the 22nd International Middleware Conference: Doctoral Symposium, ser. Middleware ’21. ACM, 2021, p. 8–11. [Online]. Available: https://doi.org/10.1145/3491087.3493676 [13] H. T. Kung and J. T. Robinson, “On optimistic methods for concurrency control,” ACM Trans. Database Syst., vol. 6, no. 2, p. 213–226, Jun. 1981. [Online]. Available: https://doi.org/10.1145/319566.319567 [14] People’s Government of Beijing Municipality, “Beijing’s technological leadership: Chainmaker leads national market share for three consecutive years,” https://www.beijing.gov.cn/ywdt/gzdt/202504/t20250406 4056295.html, Apr. 2025. [15] A. Thomson, T. Diamond, S.-C. Weng, K. Ren, P. Shao, and D. J. Abadi, “Calvin: fast distributed transactions for partitioned database systems,” in Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, ser. SIGMOD ’12. ACM, 2012, p. 1–12. [Online]. Available: https://doi.org/10.1145/2213836.2213838 [16] J. M. Faleiro and D. J. Abadi, “Rethinking serializable multiversion concurrency control,” Proc. VLDB Endow., vol. 8, no. 11, p. 1190–1201, Jul. 2015. [Online]. Available: https://doi.org/10.14778/ 2809974.2809981

[17] Y. Lu, X. Yu, L. Cao, and S. Madden, “Aria: a fast and practical deterministic oltp database,” Proc. VLDB Endow., vol. 13, no. 12, p. 2047–2060, Jul. 2020. [Online]. Available: https: //doi.org/10.14778/3407790.3407808 [18] R. Gelashvili, A. Spiegelman, Z. Xiang, G. Danezis, Z. Li, D. Malkhi, Y. Xia, and R. Zhou, “Block-stm: Scaling blockchain execution by turning ordering curse to a performance blessing,” in Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, ser. PPoPP ’23. ACM, 2023, p. 232–244. [Online]. Available: https://doi.org/10.1145/3572848.3577524 [19] Y. Xia, X. Yu, W. Moses, J. Shun, and S. Devadas, “Litm: A lightweight deterministic software transactional memory system,” in Proceedings of the 10th International Workshop on Programming Models and Applications for Multicores and Manycores, ser. PMAM’19. ACM, 2019, p. 1–10. [Online]. Available: https://doi.org/10.1145/3303084. 3309487 [20] H. Li, Y. Chen, X. Shi, X. Bai, N. Mo, W. Li, R. Guo, Z. Wang, and Y. Sun, “Fisco-bcos: An enterprise-grade permissioned blockchain system with high-performance,” in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, ser. SC ’23. ACM, 2023. [Online]. Available: https://doi.org/10.1145/3581784.3607053 [21] R. Kotla and M. Dahlin, “High throughput byzantine fault tolerance,” in International Conference on Dependable Systems and Networks, 2004, 2004, pp. 575–584. [22] Quorum Team, “Goquorum,” Nov. 2016. [Online]. Available: https: //github.com/ConsenSys/quorum [23] D. Qin, A. D. Brown, and A. Goel, “Caracal: Contention management with deterministic concurrency control,” in Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles, ser. SOSP ’21. ACM, 2021, p. 180–194. [Online]. Available: https://doi.org/10.1145/3477132.3483591 [24] J. M. Faleiro, D. J. Abadi, and J. M. Hellerstein, “High performance transactions via early write visibility,” Proc. VLDB Endow., vol. 10, no. 5, p. 613–624, Jan. 2017. [Online]. Available: https://doi.org/10. 14778/3055540.3055553 [25] G. Wood, Ethereum: A Secure Decentralised Generalised Transaction Ledger, 2014. [Online]. Available: https://ethereum.github. io/yellowpaper/paper.pdf [26] K. Ren, A. Thomson, and D. J. Abadi, “An evaluation of the advantages and disadvantages of deterministic database systems,” Proc. VLDB Endow., vol. 7, no. 10, pp. 821–832, 2014. [Online]. Available: http://www.vldb.org/pvldb/vol7/p821-ren.pdf [27] P. A. Bernstein and N. Goodman, “Concurrency control in distributed database systems,” ACM Comput. Surv., vol. 13, no. 2, p. 185–221, Jun. 1981. [Online]. Available: https://doi.org/10.1145/356842.356846 [28] P. A. Bernstein, V. Hadzilacos, N. Goodman et al., Concurrency control and recovery in database systems. Addison-wesley Reading, 1987, vol. 370. [29] E. Androulaki, A. Barger, V. Bortnikov, C. Cachin, K. Christidis, A. De Caro et al., “Hyperledger fabric: a distributed operating system for permissioned blockchains,” in Proceedings of the Thirteenth EuroSys Conference, ser. EuroSys ’18. ACM, 2018. [Online]. Available: https://doi.org/10.1145/3190508.3190538 [30] A. Sharma, F. M. Schuhknecht, D. Agrawal, and J. Dittrich, “Blurring the lines between blockchains and database systems: the case of hyperledger fabric,” in Proceedings of the 2019 International Conference on Management of Data, ser. SIGMOD ’19. ACM, 2019, p. 105–122. [Online]. Available: https://doi.org/10.1145/3299869.3319883 [31] P. Ruan, D. Loghin, Q.-T. Ta, M. Zhang, G. Chen, and B. C. Ooi, “A transactional perspective on execute-order-validate blockchains,” ser. SIGMOD ’20. ACM, 2020, p. 543–557. [Online]. Available: https://doi.org/10.1145/3318464.3389693 [32] C. Gorenflo, L. Golab, and S. Keshav, “Xox fabric: A hybrid approach to blockchain transaction execution,” in 2020 IEEE International Conference on Blockchain and Cryptocurrency (ICBC), 2020, pp. 1–9. [33] P. Festa, P. M. Pardalos, and M. G. C. Resende, “Feedback set problems,” in Handbook of Combinatorial Optimization. Springer, 1999, pp. 209– 258. [34] ChainMaker Team, “Chainmaker, a blockchain platform for building secure, trustworthy value-exchange networks to power the new global digital economy.” 2026. [Online]. Available: https://git.chainmaker.org. cn/chainmaker/chainmaker-go/-/tree/v2.3.8

[35] ——, “Chainmaker-sdk-go: The official go language sdk for chainmaker,” 2021. [Online]. Available: https://git.chainmaker.org. cn/chainmaker/sdk-go [36] B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears, “Benchmarking cloud serving systems with ycsb,” in Proceedings of the 1st ACM Symposium on Cloud Computing, ser. SoCC ’10. ACM, 2010, p. 143–154. [Online]. Available: https://doi.org/10.1145/1807128.1807152 [37] M. Alomari, M. Cahill, A. Fekete, and U. Rohm, “The cost of serializability on platforms that use snapshot isolation,” in 2008 IEEE 24th International Conference on Data Engineering, 2008, pp. 576–585.

Related documents

• Diffserv-Aware Class-Type Object for the Path Computation Element Communication Protocol#501048
• LongSpark: Efficient speculative decoding with a fixed-cost parallel drafter#1132230
• Request for monitor host table updates#501373
• USING DCGAN TO GENERATE SYNTHETIC PACKET FLOWS FOR THREAT DETECTION#496931
• FairFinGAN: Fairness-aware Synthetic Financial Data Generation#987606