# Lantern: Finding Committable Transactions via Back-Propagation on DAGs

Crypto.world

> Blockchains and deterministic databases execute the same ordered transaction stream on many nodes, and they need every node to produce the same result. Existing protocols either force a slow…

**arXiv**: 2609.03315

**Published**: 2026-09-03

**Authors**: Denglong Li, Gerui Wang, Tian Guan, Mingchao Wan

## AI summary

## Overview

**Research area:** Distributed systems and blockchain transaction processing, specifically deterministic concurrency control (DCC) for parallel transaction execution.

**Technical level:** Advanced. The paper assumes familiarity with serializability, dependency graphs, DAGs, optimistic concurrency control, and the Order-Execute (OE) versus two-stage execution architectures.

**Scope:** One sentence: Lantern is a deterministic, prior-knowledge-free concurrency control protocol that builds per-batch dependency DAGs over transaction read/write sets and uses a back-propagation marking scheme to commit more conflict-free transactions while guaranteeing identical results on every node.

## What This Paper Is About

Blockchains and deterministic databases execute the same ordered transaction stream on many nodes, and they need every node to produce the same result. Existing protocols either force a slow two-stage design where replicas must replay the primary node's schedule, or they require knowing each transaction's read and write sets before execution, which smart contracts rarely allow. Lantern's goal is to let every node execute independently in one stage, without prior knowledge, while committing as many transactions per round as possible and still guaranteeing serializability and determinism.

## Key Contributions

1. **A deterministic concurrency control protocol without prior read/write knowledge.** Lantern speculatively executes a fixed-size batch, buffers writes, and derives read and write sets at runtime. Dependencies are confined to a batch and captured in a DAG whose edges always point from a higher-indexed transaction to a lower-indexed one, so the graph is acyclic by construction.
2. **A back-propagation mechanism that salvages extra transactions.** Beyond committing only zero-out-degree (sink and isolated) vertices, Lantern iteratively marks vertices red (committable) or gray (must abort) from sinks toward sources, using alternating conflict-propagation and salvage-propagation phases. Deferred marking within each layer keeps the outcome independent of traversal order.
3. **A liveness analysis of the marking process.** The paper supplies supporting lemmas (a non-empty unmarked set always yields a non-empty candidate set, and any non-empty candidate set always produces at least one marking) as the basis for a termination proof, plus an argument that all nodes produce an identical coloring.
4. **Conflict-Free Batch Selection (CFBS) and a ChainMaker integration.** CFBS targets star-like dependency graphs that arise in hot-account read-modify-write workloads. Lantern is fully integrated into the open-source ChainMaker platform and evaluated on YCSB and SmallBank.

## Main Findings

- **Speedup over Aria:** On YCSB and SmallBank, Lantern achieves up to a **4.2x** throughput speedup over Aria. The paper attributes part of this to Aria relying on an existence proof of serializability, whereas Lantern's serializability follows from a constructive proof that can be validated experimentally; the paper does not report a quantitative measure of that validation.
- **Improvement inside ChainMaker:** By removing the serial execution-then-replay dependency between primary and replica nodes, Lantern improves ChainMaker's execution-layer throughput by **at least 2.2x**. ChainMaker's baseline is described as a nondeterministic OCC-based protocol using the two-stage architecture.
- **Only ascending order is valid for committable vertices:** The paper shows that among six permutations of three committable transactions, only ascending index order reproduces the read values observed during speculative execution; other orders could hide unverified backward dependencies. Because write-write conflicts can still occur, the commit rule keeps only the value written by the highest-indexed transaction for each key.
- **Back-propagation expands the commit set deterministically:** In the motivating example, the baseline commits only the two sink transactions, while back-propagation can commit five of the eight vertices. The paper notes a second valid path exists, which is why deterministic rules, rather than arbitrary path choice, are required.
- **VM-agnostic design:** Lantern schedules purely from read and write sets and does not require VM support for suspending and resuming on read conflicts. The paper states that Block-STM depends on such support, which it says is present in the Aptos VM but absent from Wasmer, EVM, Docker-Go, and Diem VM. This is a qualitative claim; no portability benchmark is reported.
- **Not reported in the provided excerpt:** Absolute throughput figures, latency numbers, batch size values, dataset sizes, hardware configuration, and the detailed contents of the CFBS design and the serializability proof in Sections III-G and III-H. The excerpt ends mid-way through Lemma 2.

## Methodology in Plain English

Every node receives the same globally ordered list of transactions. Each node repeatedly takes the lowest-indexed transactions up to a fixed batch size, executes them in parallel against the unchanged world state, and buffers writes instead of applying them.

Because all nodes start from the same state, the read and write sets they record are identical. For each transaction, the node checks whether it read anything written by an earlier transaction in the batch. If so, an edge is drawn from the reading transaction to the earlier writer. Since edges only go from higher to lower indices, no cycles can form, and each thread can build its own edge list without locks.

Transactions with no outgoing edges cannot have read anything written by earlier transactions, so they are safe to commit. All committable transactions are applied in ascending index order, with later writes overwriting earlier ones for the same key. Aborted transactions go back to the front of the pending queue in ascending index order, and the round repeats until the block is exhausted.

The back-propagation step improves on committing only sink vertices. Sinks are marked red. Any transaction that reads from a red transaction is marked gray, because committing its source would give it a dirty read. Any unmarked transaction whose successors are all gray can then be marked red, because none of its predecessors will be committed. These two phases alternate until nothing changes, so the final coloring depends only on the shared graph, not on timing or iteration order.

## Why This Matters

**Research impact.** The paper reframes deterministic concurrency control as a graph-marking problem rather than a scheduling problem, and argues that a constructive serializability proof makes the property testable, unlike an existence proof. It also makes a case for determinism without VM cooperation, which separates concurrency control from execution-engine features.

**Real-world applications.**

- Consortium blockchains such as ChainMaker, where every node must reach the same state and sequential execution limits throughput on multi-core hardware.
- Deterministic databases that already have a sequencing layer producing a totally ordered log; each node can run Lantern independently on that log.
- Payment and settlement systems with hot-account contention, where many transfers touch a small set of balances; the paper positions CFBS for exactly this read-modify-write pattern.
- Multi-VM blockchain platforms, since Lantern is described as able to serve as a single concurrency control layer across heterogeneous execution engines.

**Industry relevance.** The evaluation is on a deployed open-source platform with standard benchmarks, and the abstract reports throughput gains of up to 4.2x over Aria and at least 2.2x for ChainMaker's execution layer. The paper also identifies transaction execution, rather than BFT consensus, as the emerging bottleneck now that consensus protocols have improved.

## Future Directions

- **Tuning batch size.** Batch size is a named parameter that bounds how much parallelism and how many dependencies each round sees, but the paper reports no study of its effect on the 4.2x and 2.2x results.
- **Extending CFBS.** The paper introduces Conflict-Free Batch Selection for RMW-intensive hot-account workloads; its selection policy and its measured benefit are not described in the provided excerpt, leaving room for further work on star-shaped dependency graphs.
- **Comparing against more execution engines.** Lantern is claimed to be VM-agnostic and able to host multiple VMs, which suggests evaluation against VM-assisted designs such as Block-STM and against Fabric's Execute-Order-Validate variants (Fabric++, Fabric#, XOX Fabric).
- **Formal treatment of the coloring.** The paper notes that removing cycles from a general directed graph is the NP-hard Feedback Vertex Set problem; its construction avoids this by excluding backward edges, but the cost in aborted transactions and their reprocessing is not quantified in the excerpt.

## Target Audience

Researchers and engineers working on blockchain execution layers, deterministic databases, and parallel transaction processing, particularly those familiar with OCC, serializability, and DAG-based scheduling. It is also relevant to platform architects who need a concurrency control layer that works across multiple virtual machines without modifying the VM, and to readers comparing deterministic protocols such as Aria against nondeterministic two-stage designs.

## Authors’ 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…

[The full abstract on arXiv](https://arxiv.org/abs/2609.03315)

[Read the original paper](https://arxiv.org/abs/2609.03315)

---

Canonical: https://crypto.world/paper/lantern-finding-committable-transactions-via-back-propagation-on-dags-2609.03315
