Paper: arXiv 2412.08624

Authors: Mohit Garg, Suneel Sarswat

Abstract

Continuous double auctions are commonly used to match orders at currency, stock, and commodities exchanges. A verified implementation of continuous double auctions is a useful tool for market regulators as they give rise to automated checkers that are guaranteed to detect errors in the trade logs of an existing exchange if they contain trades that violate the matching rules. We provide an efficient and formally verified implementation of continuous double auctions that takes \(O(n \log n)\) time to match \(n\) orders. This improves an earlier \(O(n^2)\) verified implementation. We also prove a matching \(Ω(n\log n)\) lower bound on the running time for continuous double auctions. Our new implementation takes only a couple of minutes to run on ten million randomly generated orders as opposed to a few days taken by the earlier implementation. Our new implementation gives rise to an efficient automatic checker. We use the Coq proof assistant for verifying our implementation and extracting a verified OCaml program. While using Coq’s standard library implementation of red-black trees to obtain our improvement, we observed that its specification has serious gaps, which we fill in this work; this might be of independent interest.

Complexity vs Empirical Score

  • Math Complexity: 6.5/10
  • Empirical Rigor: 4.0/10
  • Quadrant: Lab Rats — high math complexity, limited empirical testing

Why this score: The paper involves significant theoretical computer science, including formal proofs of algorithmic lower bounds and verification of correctness using Coq, which is mathematically dense. However, the empirical validation is limited to runtime comparisons on synthetic data and lacks real-world backtests or statistical metrics on market data.

Research Flowchart

  flowchart TD
  Goal["Research Goal<br>Efficient & Verified Continuous Double Auction Implementation"]
  Inputs["Data/Inputs<br>- Millions of Random Orders<br>- Trade Logs from Exchanges"]
  Method["Methodology<br>- Formal Verification (Coq Proof Assistant)<br>- O(n log n) Algorithm using Red-Black Trees<br>- Improved Standard Library Specifications"]
  Process["Computational Process<br>- Automated Order Matching<br>- Extraction to OCaml Program"]
  Outcomes["Key Findings & Outcomes<br>- Lower Bound: Ω(n log n)<br>- Verified Implementation (Minutes vs Days)<br>- Efficient Automatic Error Checker"]

  Goal --> Inputs
  Inputs --> Method
  Method --> Process
  Process --> Outcomes

Evidence Card

What the authors claim, on what data, and who has checked it. Read from the paper's own text by a language model: every quote is verbatim, nothing was re-run. How to read this card

Proposes

We provide an efficient and formally verified implementation of continuous double auctions that runs in O(n log n) time, improving on the earlier O(n^2) implementation.

Source sentence
We provide an efficient and formally verified implementation of continuous double auctions that takes $O(n \log n)$ time to match $n$ orders.

Assumes 4

  • The exchange receives instructions consisting of a command (Buy, Sell, Delete) and an order, and maintains resident bid and ask sets. model
    Source sentence
    The exchange receives instructions from the traders (buyers and sellers) of the product. Each in-struction comprises of a command and an order.
  • The matching algorithm must satisfy positive bid‑ask spread, price‑time priority, and conservation properties. model
    Source sentence
    (B, A, Command w) P7→( ˆB, ˆA, M) Given the above description of the exchange, it was observed in [5] that the following three properties must be satisfied by P. • Positive bid-ask spread: The most competitive bid in ˆB has a lower limit price than the most competitive ask in ˆA, i.e., no transaction is possible among resident orders. • Price-time priority: If Command w is a bid: if w gets traded with an ask a′,
  • Resident bids and asks are stored in sorted data structures (lists in the previous implementation, red‑black trees in the new implementation). execution
    Source sentence
    In the implementation, B and A are kept as sorted lists. We store the resident bids and asks as BSTs.
  • The red‑black tree operations (insertion, extraction, deletion) run in O(log n) time as per the Coq standard library specification. other
    Source sentence
    11 5.1 Strengthening the standard library guarantees For our BSTs, we use the standard library implementation of red-black trees [3], which implements insertion, extraction, and deletions in O(log n) time.

Data

  • randomly generated order books synthetic unknown
    Source sentence
    We randomly generate order books of various sizes using a python script, run the extracted verified OCaml programs of ePro-cess instruction and Process instruction on it, and report the running times. Our or-der books generated are of sizes going from 200 thousand to 10 million.

Costs

Not applicable The paper reports no trading or execution result.

Finds 3

  • The new implementation matches orders in O(n log n) time, which is asymptotically optimal given the Ω(n log n) lower bound. theoretical
    Source sentence
    We provide an efficient and formally verified implementation of continuous double auctions that takes $O(n \log n)$ time to match $n$ orders. We also prove a matching $Ω(n\log n)$ lower bound on the running time for continuous double auctions.
  • Running the new implementation on ten million randomly generated orders takes less than two minutes, a thousand‑fold speedup over the previous implementation. performance
    Source sentence
    Our new implementation takes only a couple of minutes to run on ten million randomly generated orders as opposed to a few days taken by the earlier implementation. In particular, for ten million orders our implementation takes less than two minutes to run, at least a thousandfold improvement.
  • The previous implementation using lists required O(n^2) time and would take days on ten‑million‑order datasets. performance
    Source sentence
    The implementation uses the List data structure resulting in an O(n2)-time implementation for n orders. In this work, we drastically improve the running time by producing an O(n log n)-time implementation of continuous double auctions using Red-black trees instead of Lists.

Checked by others

No other paper in the archive has been found to support or contradict these findings (compared with 10 related papers). Coverage is partial, so this is neither replication nor refutation.

Code

No repository by the authors found in the paper.

Extracted 2026-11-14 · same card as JSON · A language model chose these items: check the source sentence before relying on one.