Non-contentive Message Numbering

MPS	0046
Status	Proposed
Category	Libraries and Tooling
Authors	Kevin Millikin (kmillikin)
Created	09-Oct-2026

Abstract

Read/write contention, or simply contention, can happen when two transactions access the same part of a Midnight smart contract’s public state, where one transaction is writing to the public state and the other is reading from it. If the writing transaction is recorded on chain first, and the reading transaction reads a different value on chain than the one that was read off chain when building the transaction, then the second (reading) transaction will be rejected. The Compact standard library provides a collection of ledger ADTs (Abstract Data Types) to organize public state. These are individually designed to avoid contention whenever possible. Contract developers want a ledger ADT that allows them to number incoming messages while avoiding unnecessary contention. This is currently not possible.

This is a Compact-only feature request. It will not require changes to the Midnight Network.

Vision

It is possible for contract developers to use a set-like abstraction where each inserted element is numbered consecutively according to insertion order on chain, without any contention involving insertion numbering.

Problem

Read/write contention can happen when multiple transactions are trying to read and write to the same part of a contract’s public ledger state. Contention can cause transactions to be rejected by the Midnight Network. This is essential for correct contracts.

As a simple example where it is essential to reject such transactions, consider a contract with a set of “authorized” users who are allowed to perform some critical action. Consider a pair of transactions:

1. An authorized user performs a critical action, and
2. That user’s authorization is removed.

There is potential contention because transaction 1 is reading the “authorized” set of users and transaction 2 is writing to that set. If transaction 2 is recorded on-chain first, then transaction 1 must fail in order to maintain the correctness of the contract state. There are numerous similar examples involving auctions, voting, payouts, etc.

Public state updates in the Midnight Network are performed by executing programs expressed in Impact, a simple special-purpose programming language. Part of the design of Impact is that it should minimize unnecessary contention. The Compact programming language’s standard library includes a collection of ledger ADTs, which are data structures used for organizing a contract’s public state. The operations on ADTs are designed to use Impact in a way that eliminates contention where it is not inherent. The Compact compiler generates Impact code for the on-chain implementation of ledger ADT reads and writes.

Developers want to combine these ledger ADTs in complex ways, but doing that in a Compact contract’s source code can introduce (unnecessary) contention.

Use Cases

The specific concrete problem in this MPS is that a contract developer wants a set-like abstraction that records the insertion order of elements. A standard trick to implement a set is to use a Map with the elements as keys. The desired set-like abstraction can be implemented in a contract’s public ledger state using a Counter ADT to count insertions and a Map ADT as a set, where the set elements are the Map keys and counter values are the Map values. A pair of insertion transactions will contend with each other, since both transactions read and write to the counter. This contention is unnecessary. Neither contract cares about the actual specific value of the counter, but they have no choice in Compact source code but to read its value.

It is possible to avoid this contention by implementing a new, custom ledger ADT. A proof of concept implementation exists as a Compact pull request.

Goals

The specific goal is that Compact smart contract developers have access to a non-contentive message numbering mechanism. However, a general solution for building non-contentive ledger ADTs is preferred over adding custom ledger ADTs to the standard library for every contract developer that asks.

Expected Outcomes

Developers will have access to a data structure with Compact signatures:

module OrderedSet<T> {
  circuit insert(x: T): [];
  circuit remove(x: T): Uint<64>;
  circuit member(x: T): Boolean;
  circuit size(): Uint<64>;
}

This is the same interface as the Compact Set ledger ADT, except that elements are consecutively numbered according to their insertion order on chain, and remove returns an element’s insertion order.

This will not necessarily be exposed as a Compact module.

Open Questions

There is a large design space to explore. Ideally, the solution is a general one that allows Compact developers to define their own ledger ADTs in some way. It does not scale to require the next 700 custom contract ledger ADTs to be committed as supported data structures in the Compact standard library.

Recommended MIPs

This is purely a Compact programming language design issue. Compact runs off chain, and solving this issue is not expected to immediately require any changes to the Midnight Network. There are no expected MIPs needed at this time.

Acceptance Criteria

1. Design note or MIP choosing between a dedicated ADT and a general ADT-definition mechanism, with the rationale. Submitted by 27 November 2026.
2. Prototype on the ledger and compiler development branches.
3. Test. At least 10 transactions in the same block each append to the same stream without contention failures, and each receives a unique number, increasing in application order.

Not included in Q4 2026: release to a public network.

References

A proof of concept implementation of a custom ledger ADT: https://github.com/LFDT-Minokawa/compact/pull/775

Acknowledgements

David Millar-Durant provided the proof of concept implementation and discussion of the requirements.

Copyright

This MPS is licensed under CC-BY-4.0.