Research
Torna: a parallel, ordered index primitive for Solana
Motivation, prior designs and their bottlenecks, the constraints that bound the problem, the design space we explored, the Torna design, how we de-risked it, what we measured, and what remains open. Every number here is reproducible from the repository.
Abstract
Torna is a parallel, ordered, on-chain index primitive for Solana. It stores a sorted key to value map as a high-fanout B+ tree with one node per account, so writes to different leaves carry disjoint write sets and the Sealevel scheduler commits them in the same slot. The central limit order book is the hardest instance of the general problem (sorted state with many concurrent writers), and the dominant Solana designs answer it by concentrating the book in a single large account (often, though not always, with an off-chain crank), which serializes writes and, where a crank is used, adds a liveness dependency. We formalize the three scarce resources that bound any design, walk the design space we explored and rejected, present Torna, and evaluate it: a measured 4.6 to 7.1x throughput gain for disjoint versus contended writes on a real validator banking stage, single-key hot operations under the 200k compute-unit default even at fanout 128, and a correctness regimen of an 8,000-operation on-chain differential, 60k-iteration fuzzing, and five rounds of adversarial review to convergence with token-conservation invariants on the reference order book. We close with limitations and open problems, including that matching itself stays serial and that an external audit is still pending.
1. Motivation
A great deal of on-chain logic needs the same two things at once: keep state sorted, and let many independent actors write to it concurrently. An order book keeps orders sorted by price-time and is updated by many makers; a liquidation engine keeps positions sorted by health and is updated by many borrowers; a leaderboard keeps scores sorted and is updated by many players. The order book is the sharpest version of this problem because it combines a strict global sort, a high write rate from independent parties, and real custody of funds.
Solana is the natural home for this: its parallel runtime (Sealevel) can execute transactions that touch disjoint accounts in the same slot. But that parallelism is only available to a data structure laid out so that independent writes land on different accounts. The order books shipped on Solana to date are not laid out that way, and as a result they leave most of the runtime's parallelism on the table. Torna is an attempt to recover it as a reusable primitive, rather than once per application.
2. Existing approaches and their bottlenecks
The on-chain order book has been attempted several ways. Each makes a different tradeoff, and each has a bottleneck that Torna is designed to remove. We describe them at a high level as a design family, not as a critique of any specific implementation; details vary by version and by team.
As publicly described: the book lives in a few large per-market accounts (bid and ask slabs plus request and event queues), each a single write lock; a permissionless crank drains the event queue to settle and credit fills.
Bottleneck. Every order on a side contends on that side's one writable slab, so placements serialize, and the event-queue plus crank model adds latency and a liveness dependency.
Removes the crank by matching atomically inside the taker's transaction, with no event queue.
Bottleneck. The market state is still concentrated in one account, so order operations on it take the same write lock and serialize.
The order book lives on a relayer; only settlement is on-chain.
Bottleneck. Not actually on-chain: trust, liveness, and censorship move off-chain, and the book is not composable from other programs.
Sidesteps the order book entirely with a pool curve.
Bottleneck. No limit orders and no price-time priority; capital inefficiency and impermanent loss; a different product, not an order book.
A textbook B-tree, either in one account or with low fanout across accounts.
Bottleneck. One account reintroduces the slab's serial write lock; low fanout makes the tree tall, so a single operation touches too many node accounts and blows the per-transaction account budget.
The common thread in the on-chain designs is a single large account holding the whole book. That choice makes the data structure simple, but it forces every write through one account lock, which is exactly the resource Solana parallelizes on. The off-chain and AMM designs avoid the lock by giving up the property we want: a real, composable, on-chain limit order book.
3. The three constraints
Any on-chain sorted structure on Solana is bound by three scarce resources. Stating them explicitly is what makes the design choice forced rather than aesthetic.
- i. Per-transaction account budget. A transaction can reference a limited number of accounts (about 35 in a legacy transaction, about 256 with address lookup tables). This is the scarcest resource: it caps how many node accounts a single operation may touch, and therefore the height of any account-per-node tree.
- ii. Account-lock parallelism (Sealevel). Two transactions run in the same slot only if their writable account sets are disjoint. A data structure parallelizes exactly to the extent that independent logical writes touch different accounts.
- iii. Rent. Every account carries a rent-exempt deposit with a fixed per-account overhead. A design with many tiny accounts pays that overhead repeatedly; the structure must amortize it.
For a single-account slab, (i) is fine, but (ii) is zero (one lock) and (iii) hits the account size ceiling. A textbook low-fanout B-tree spread across accounts wins (ii) and (iii) but loses (i), because its height makes one operation touch too many accounts. The design has to win all three at once.
4. Design space explored
We evaluated the obvious candidates against the three constraints before committing. The table records what we rejected and why; the rejections are as informative as the choice.
The high-fanout B+ tree with one node per account is near-optimal on all three. With the default fanout of 64 the tree is about three levels deep, so an operation touches roughly three node accounts; each node is its own account, so writes in different leaves never share a lock; and the fanout amortizes the per-account overhead across many entries. The reason the structure is a B+ tree and not a slab or a skip list is precisely this three-way fit.
5. The Torna design
Torna stores a sorted, opaque key to value map. Keys are 32 bytes compared byte-lexicographically; values are inline, of a width fixed per tree between 1 and 128 bytes. The structure is a high-fanout B+ tree, and each node lives in its own program-derived account.
Hot path and cold path
The key idea is that the common operations never write the shared header. On the hot path (insert into a non-full leaf, update a value in place, delete without rebalancing, point and range reads), the header is read-only and only the target leaf is writable, with no cross-program calls. Two writers landing in different leaves therefore have disjoint writable sets and commit together. The cold path (an insert that splits a full leaf, or a delete that merges an underfull one) is the only place that allocates or frees node accounts; it touches a separate allocator account and calls the system program. Mutable counters such as the next node index live in that allocator, not the header, so plain inserts never take a write lock on the header. Keepers run compaction off-peak to keep the hot path split-free.
Tenant binding
One audited program serves many independent trees. Accounts are namespaced by the creator's public key, and every node and header carries a 128-bit tree_uid = sha256(creator || tree_id)[..16]that is checked at every node-validation site. This matters because the client-chosen tree id and the per-tree node index both collide across creators; only the creator-derived uid is a real tenant boundary. An earlier 8-byte binding was widened to 16 bytes during review because 8 bytes was grindable. This is the kind of correctness property that random differential and fuzz testing did not catch, because they shared the author's blind spots, and that adversarial review did.
The book is the key
For the order-book instantiation, one 32-byte key encodes price-time priority directly, so the tree is the sorted book with no secondary index. The price occupies the high bytes big-endian so byte order matches numeric order; a writer-unique tail (maker and nonce) breaks ties so two makers at the same price are vanishingly unlikely to collide on a key; they still share a leaf, so they do not run in parallel, but neither overwrites the other.
Compared byte-by-byte, this single key sorts the whole book into price-then-time priority, the tree stays sorted with no extra index.
The client is the product
The engine is roughly a fifth of the value; the rest is a client that makes account resolution invisible. The developer calls with a key and a value, and the SDK reads the tree off-chain and returns the exact account set, so node indices, PDA bumps, the descent path, and split spares never appear in application code. A Rust and a TypeScript SDK are byte-equivalent, and an integrating program can drive Torna over a cross-program call as its own PDA, which a probe program confirms preserves parallelism.
6. De-risking spikes
Before building the engine we ran isolated spikes to retire the load-bearing unknowns, so that the design rested on measurements rather than hope.
- Does fanout bind on compute? A CU sweep showed the fanout-128 insert stays well under the budget; the eval table puts the hot-path InsertFast at 43k and a splitting insert at 68k, both inside the 200k default. So compute does not bind fanout. The binding resource is the account budget, which is what sets fanout to 64 by default and 128 for large trees.
- Does the runtime actually parallelize this? A saturation benchmark on a real single-node validator, not a simulator, confirmed that disjoint-leaf writes commit several times more transactions per slot than contended ones (Section 7).
- Does composability survive a CPI? A caller program that drives InsertFast as a PDA authority kept the parallel property, so an integrating program loses nothing.
- What is the read and return-data envelope? Spikes pinned the 1,024-byte return-data ceiling and the cost of emitting it, which shaped the read instructions.
The single most consequential finding was the fee-payer trap: two transactions from the same payer serialize even on different leaves, because the fee debit makes the payer a writable account. This is why the SDK and the demo fund each parallel writer with its own payer, and why the benchmark isolates it as a distinct workload.
7. Evaluation
7.1 A throughput model
Model the writable lock set of a maintenance transaction as the pair {leaf(k), payer(w)}: the leaf the key k lands in and the writer's fee-payer. Two transactions conflict, and cannot share a slot, exactly when they share a leaf or share a payer. Each slot the banking stage commits a maximal set of mutually non-conflicting transactions across its W lanes.
For N pending writes spread over L leaves and P payers, the committed count per slot is approximately the expression below, where S is the slot time and t the per-transaction execution time. The speedup over the fully serial case, one account and one lock, is the factor in front.
Three regimes follow directly. Disjoint writes (different leaf, different payer) give σ = min(W, L, P), bounded by the hardware lane count. A shared leaf collapses σ to 1, and so does a shared payer, the fee-payer trap. The B+ tree supplies L: a book of n resting orders at fanout F occupies about n/F leaves, so L grows with depth and the binding term is the lane count W until the book is shallow.
Matching is serial and cannot be parallelized. Let α be the matching fraction of traffic and 1 minus α the maintenance fraction. The aggregate speedup is then the Amdahl form below: it approaches σ for a maker-heavy book and falls to 1 as traffic becomes taker-heavy.
7.2 Measured
Parallelism. The model predicts σ = min(W, L, P). On a real single-node validator banking stage, every transaction runs identical compute: a duplicate InsertFast that descends the tree and write-locks the target leaf, then returns without mutating state. Compute is constant, so the only variable across workloads is the writable lock set; the absolute counts reflect this one cheap, non-mutating op, and the ratio between workloads is the signal. We blast 30,000 such transactions per workload and count committed transactions per roughly 400ms slot under saturation across three workloads: disjoint leaves with disjoint payers (parallel), the same leaf (serial), and the same fee-payer (serial). The lane count W of a single node is small, so we expect a few-fold σ, with L and P large.
Disjoint writes commit about 4.6x (peak slot) to 7.1x (median busy slot) more transactions per slot than same-leaf writes, and about 4.1x to 7.6x more than same fee-payer. Disjoint (A) and same-leaf (B) confirm nearly the same total; the difference is density. Workload A packs its 28,862 confirmations into 7 slots, while same-leaf B smears 29,549 across 21 slots, which is exactly the parallelism. A single-node validator has a small fixed number of banking threads; more threads on a real cluster would raise the lane ceiling W, though cluster scheduling and network overheads may offset part of the gain.
Compute. Measured on the real engine, single-key hot operations stay under the 200k default budget even at fanout 128; the batch operations request a higher limit and remain far below the per-transaction cap.
For a concrete end-to-end figure, an actual order placement captured on devnet cost 11,048 compute units total, of which the inner engine InsertFast was roughly 3k, below the table's worst-case figures because this tree is shallow with a small value, and a 5000-lamport fee.
Correctness and security. The engine is exercised by an on-chain differential of 8,000 randomized operations against an independent oracle, a 60k-iteration fuzzer with zero memory violations, and a host-side property suite. The reference order book is checked by a token-conservation invariant after every operation. Most important, each layer went through adversarial review to convergence (rounds until two consecutive clean passes): the engine took five rounds plus a class audit, during which a single class of bug, treating program-owned as tenant-owned, recurred four times across nodes, the allocator, scratch, and delegates, until a systematic sweep closed the class. The order book took five rounds, the headline being a forged-tree settlement that drained the real vault at near-zero cost, fixed by binding the book to its market config before any token moves.
Economics. Rent is a refundable deposit, not a fee, and is reclaimed when an account is closed. An empty tree is about 0.003 SOL; a full market (two empty trees, two vaults, and config, before any nodes) is about 0.013 SOL; a resting entry is a slot in an existing leaf, so its marginal rent is the leaf rent amortized over the fanout, roughly 0.0005 SOL at fanout 64, reclaimed on merge. The recurring per-transaction cost is just the network fee; new node accounts are created only on a split.
8. Discussion, limitations, and open problems
Matching stays serial. Torna parallelizes the maker side. Top-of-book consumption is a single contention point and cannot be parallelized; this is a property of price-time priority, not of the data structure. The bet is that liquid books are maker-heavy.
The fee-payer is a lock. Independent writers must use independent payers, or they serialize on the fee debit. The SDK surfaces this; it is a constraint integrators must respect.
Time priority is slot-granular and tiebreaks are client-supplied. A strict global FIFO counter would serialize every placement, so it is deliberately not used; uniqueness lives in a writer-chosen tail and time priority is approximate at slot granularity.
Trust and audit. The in-house adversarial review is not an external audit, which is pending. The single largest open trust decision is the upgrade-authority policy: make the program immutable after audit, or hold the authority under a timelocked multisig. It is not yet decided, and it is the main assumption an integrator inherits.
Future work. A multi-node devnet benchmark would produce a stronger throughput number than the single-node figure here; cascade-aware keeper compaction would tighten the cold-path edge cases; and the external audit is the gate to any mainnet use.
9. Conclusion
The on-chain order book has been treated as an application to be hand-built, and each attempt has paid the single-account serialization tax or stepped off-chain to avoid it. We argue it is better treated as one instance of a primitive: sorted state with concurrent writers, laid out so the runtime can parallelize it. Torna is that primitive, a high-fanout B+ tree with one node per account, a hot path that never locks the header, a tenant binding that survived adversarial review, and a client that hides account resolution entirely. The reference order book, TornaDEX, is the proof that it works end to end on devnet today. The contribution is not the B+ tree, which is textbook; it is the layout chosen against Solana's three constraints, the correctness work behind it, and the SDK that makes it usable, packaged as a primitive others can build on rather than rebuild.
Artifacts
Everything above is reproducible and live.
Numbers in this document: parallelism and compute are measured on a single-node solana-test-validator banking stage and the real engine; correctness figures are the current passing test counts; rent is measured on devnet. Devnet is shared and noisy, so the controlled single-node numbers are the honest ones. In-house adversarial review is not an external audit.