# Working with Maps and Merkle Trees in Compact

Two data structures power most on-chain state management on Midnight: Map and MerkleTree. They look similar at first glance because both associate keys with values, but they solve different problems. A Map gives you mutable key-value storage with direct lookups. A MerkleTree gives you an append-only commitment structure where membership can be proven without revealing anything else.

This tutorial walks you through building two contracts. The first is a Map-based registry that stores and retrieves entries by key. The second is a depth-20 Merkle-tree-based allowlist where membership is verified with a cryptographic path proof. By the end, you will know when to reach for each structure and how to wire them up correctly in Compact.

Prerequisites

• Midnight toolchain installed (installation guide)
• Basic familiarity with Compact. If you have not gone through the hello world tutorial, start there
• Node.js installed for running tests

Map vs MerkleTree: when to use each

Before writing any code, it helps to understand what problem each structure solves.

A Map is a mutable key-value store in the public ledger. You can insert, update, and delete entries freely. Lookups are direct. The entire map contents are visible on-chain, and you can iterate over them from TypeScript. Use a Map when you need to associate keys with values that change over time and when the size of the dataset is manageable.

A MerkleTree is an append-only structure. You insert leaves, but you cannot delete or update them directly. The tree's value is its root hash: a single 32-byte commitment that summarizes every leaf. Membership is proven by providing a path from the leaf to the root, not by exposing the tree contents. Use a MerkleTree when you need to prove that something is in a set without revealing the full set, or when the set can grow large and you want compact membership proofs.

The key difference is mutability vs commitment. Maps are for state you need to read and write freely. Merkle trees are for sets you need to commit to and prove membership in.

Part 1: Map-based registry

The registry contract stores entries as key-value pairs on the public ledger. Each entry maps a 32-byte key (an identifier, address, or hash) to a 32-byte value (metadata, a name hash, or any other fixed-size data). You can register new entries, look up existing ones, update values, deregister entries, and check membership. A Counter tracks the total number of registrations.

The smart contract

Create a file called registry.compact:

pragma language_version 0.22;

import CompactStandardLibrary;

export ledger registry: Map<Bytes<32>, Bytes<32>>;

export ledger entryCount: Counter;

export circuit register(key: Bytes<32>, value: Bytes<32>): [] {
    assert(!registry.member(disclose(key)), "key already registered");
    registry.insert(disclose(key), disclose(value));
    entryCount.increment(1);
}

export circuit update(key: Bytes<32>, newValue: Bytes<32>): [] {
    assert(registry.member(disclose(key)), "key not registered");
    registry.insert(disclose(key), disclose(newValue));
}

export circuit deregister(key: Bytes<32>): [] {
    assert(registry.member(disclose(key)), "key not registered");
    registry.remove(disclose(key));
}

export circuit isRegistered(key: Bytes<32>): Boolean {
    return registry.member(disclose(key));
}

Declaring a Map ledger field

The Map type takes two type parameters: the key type and the value type.

export ledger registry: Map<Bytes<32>, Bytes<32>>;

Keys can be any regular Compact type: Boolean, Field, Uint<N>, Bytes<N>, structs, enums, and more. Values can be any regular Compact type or any ledger-state type except Kernel. This means you can even nest Maps:

ledger nested: Map<Bytes<32>, Map<Uint<16>, Counter>>;

Nested ledger-state values must be initialized before first use with default<T>. Attempting to operate on an uninitialized nested value is a dynamic error.

Map operations in circuits

The full set of operations available inside a circuit:

registry.insert(key, value);        // insert or overwrite
registry.remove(key);               // delete an entry
registry.member(key)                // Boolean: is key present?
registry.lookup(key)                // returns the value
registry.size()                     // Uint<64>: number of entries
registry.isEmpty()                  // Boolean
registry.insertDefault(key);        // insert the default value for the value type
registry.resetToDefault();          // clear the entire map

One important rule: calling lookup on a key that does not exist is a dynamic error. Always guard lookups with a member check or an assertion, as the update and deregister circuits do above.

Why disclose?

Every circuit parameter is a private witness by default. When you write to the public ledger, Compact requires you to explicitly mark the transition with disclose. This prevents accidental leakage of private data into the public transaction transcript.

In the registry circuits, both the key and value are circuit inputs (private witnesses). Since insert writes them into the public ledger, both must be wrapped in disclose:

registry.insert(disclose(key), disclose(value));

The member check also takes a circuit input, so it needs disclose too:

assert(!registry.member(disclose(key)), "key already registered");

Iterating over a Map

Map iteration is only available from TypeScript, not inside Compact circuits. There is no in-circuit iteration syntax.

From TypeScript, after reading contract state, you can iterate using the standard iterator protocol:

const state = ledger(circuitContext.currentQueryContext.state);
for (const [key, value] of state.registry) {
  // process key and value
}

This is useful for building off-chain indexes, syncing UI state, or running queries against the contract without modifying it.

Map size and emptiness

You can query the size and emptiness of a Map inside a circuit:

const count = registry.size();    // Uint<64>
const empty = registry.isEmpty(); // Boolean

These are useful for circuits that enforce limits. For example, a registry with a maximum capacity could assert registry.size() < maxEntries before inserting.

Compile

compact compile registry.compact managed/registry

Testing the registry

Install dependencies:

npm install --save-dev vitest
npm install @midnight-ntwrk/compact-runtime

Create src/registry.test.ts:

import { describe, it, expect } from 'vitest';
import {
  createConstructorContext,
  createCircuitContext,
  sampleContractAddress,
} from '@midnight-ntwrk/compact-runtime';
import { Contract, ledger } from '../managed/registry/contract/index.js';

const coinPublicKey = new Uint8Array(32);
const contractAddress = sampleContractAddress();

function createSimulator() {
  const contract = new Contract({});
  const constructorCtx = createConstructorContext({}, coinPublicKey);
  const { currentPrivateState, currentContractState, currentZswapLocalState } =
    contract.initialState(constructorCtx);

  const circuitContext = createCircuitContext(
    contractAddress,
    currentZswapLocalState,
    currentContractState,
    currentPrivateState,
  );

  return { contract, circuitContext };
}

const keyA = new Uint8Array(32).fill(1);
const valueA = new Uint8Array(32).fill(2);
const valueB = new Uint8Array(32).fill(3);
const keyB = new Uint8Array(32).fill(4);

describe('registry contract', () => {
  it('registers a new entry and increments the counter', () => {
    let { contract, circuitContext } = createSimulator();

    ({ context: circuitContext } = contract.impureCircuits.register(circuitContext, keyA, valueA));
    const state = ledger(circuitContext.currentQueryContext.state);

    expect(state.entryCount).toBe(1n);
    expect(state.registry.member(keyA)).toBe(true);
  });

  it('looks up a registered entry', () => {
    let { contract, circuitContext } = createSimulator();

    ({ context: circuitContext } = contract.impureCircuits.register(circuitContext, keyA, valueA));
    const state = ledger(circuitContext.currentQueryContext.state);

    expect(state.registry.lookup(keyA)).toEqual(valueA);
  });

  it('updates an existing entry', () => {
    let { contract, circuitContext } = createSimulator();

    ({ context: circuitContext } = contract.impureCircuits.register(circuitContext, keyA, valueA));
    ({ context: circuitContext } = contract.impureCircuits.update(circuitContext, keyA, valueB));
    const state = ledger(circuitContext.currentQueryContext.state);

    expect(state.registry.lookup(keyA)).toEqual(valueB);
  });

  it('deregisters an entry', () => {
    let { contract, circuitContext } = createSimulator();

    ({ context: circuitContext } = contract.impureCircuits.register(circuitContext, keyA, valueA));
    ({ context: circuitContext } = contract.impureCircuits.deregister(circuitContext, keyA));
    const state = ledger(circuitContext.currentQueryContext.state);

    expect(state.registry.member(keyA)).toBe(false);
  });

  it('reports correct membership for registered and unregistered keys', () => {
    let { contract, circuitContext } = createSimulator();

    ({ context: circuitContext } = contract.impureCircuits.register(circuitContext, keyA, valueA));

    const { result: isA } = contract.impureCircuits.isRegistered(circuitContext, keyA);
    const { result: isB } = contract.impureCircuits.isRegistered(circuitContext, keyB);

    expect(isA).toBe(true);
    expect(isB).toBe(false);
  });
});

Run the tests:

npx vitest run src/registry.test.ts

Part 2: Merkle-tree-based allowlist

The smart contract

Create a file called allowlist.compact:

pragma language_version 0.22;

import CompactStandardLibrary;

export ledger allowlist: MerkleTree<20, Bytes<32>>;

export ledger leafCount: Counter;

witness findLeaf(leaf: Bytes<32>): MerkleTreePath<20, Bytes<32>>;

export circuit addToAllowlist(leaf: Bytes<32>): [] {
    allowlist.insert(disclose(leaf));
    leafCount.increment(1);
}

export circuit verify(leaf: Bytes<32>): [] {
    const path = findLeaf(leaf);
    assert(allowlist.checkRoot(merkleTreePathRoot<20, Bytes<32>>(disclose(path))), "leaf is not in allowlist");
}

Declaring a MerkleTree ledger field

The MerkleTree type takes two parameters: the depth and the leaf value type.

export ledger allowlist: MerkleTree<20, Bytes<32>>;

The depth must satisfy 2 <= depth <= 32. A depth-20 tree can hold up to 2^20 = 1,048,576 leaves. There is also a HistoricMerkleTree<depth, T> variant that accepts membership proofs made against prior versions of the tree. This is useful when the tree has frequent insertions and you want proofs to remain valid even after new leaves are added.

One important constraint: Opaque<"string"> and Opaque<"Uint8Array"> cannot be used as leaf value types. The compiler enforces this because those types cannot be correctly hashed in a ZK proof. Use Bytes<32>, Field, or other non-opaque Compact types as leaf types.

Inserting leaves

Several insert operations are available:

allowlist.insert(item);               // insert at the next free index
allowlist.insertHash(hash);           // insert a raw Bytes<32> hash
allowlist.insertIndex(item, index);   // insert at a specific index
allowlist.insertIndexDefault(index);  // insert the default value (emulates removal)

The insert operation appends the leaf at the current first free index, which increments automatically. The tree is append-only: there is no remove operation. To logically remove a leaf, insert the default value at its index using insertIndexDefault.

Witness functions and the MerkleTreePath type

Verifying membership requires a Merkle path: the sequence of sibling hashes from the leaf up to the root. This path is computed off-chain, since the circuit cannot iterate over the tree to find it.

You declare a witness function to provide the path from TypeScript:

witness findLeaf(leaf: Bytes<32>): MerkleTreePath<20, Bytes<32>>;

A witness function is not a circuit. It is a hook that lets the off-chain TypeScript code inject values into a circuit. The circuit calls findLeaf(leaf) and receives the path. The path is then used to verify membership.

MerkleTreePath<20, Bytes<32>> is the proof type. It contains the leaf value and a vector of 20 sibling entries, each with a sibling hash and a direction flag. You pass the path to merkleTreePathRoot to recompute the root, then compare it against the tree's current root with checkRoot.

Path verification

export circuit verify(leaf: Bytes<32>): [] {
    const path = findLeaf(leaf);
    assert(allowlist.checkRoot(merkleTreePathRoot<20, Bytes<32>>(disclose(path))), "leaf is not in allowlist");
}

merkleTreePathRoot recomputes the Merkle root from the path. checkRoot verifies that the computed root matches the tree's actual current root. If the leaf is not in the tree, the path will produce the wrong root and the assertion fails.

The path returned by the witness function is private data. It must be wrapped in disclose when passed to merkleTreePathRoot because the root computation involves ledger state, which is part of the public transaction transcript.

HistoricMerkleTree

There is a second variant called HistoricMerkleTree<depth, T>. It accepts membership proofs made against any past version of the tree, not just the current root. This matters in practice because Midnight transactions are submitted and confirmed asynchronously. If a new leaf is inserted between the time a user generates their proof and the time their transaction is confirmed, a regular MerkleTree would reject the now-outdated proof. A HistoricMerkleTree stores past roots and accepts proofs against any of them, making proofs resilient to concurrent insertions.

For an allowlist with infrequent insertions, the regular MerkleTree is sufficient. For high-traffic applications where the tree is updated frequently, HistoricMerkleTree is the safer choice.

Compile

compact compile allowlist.compact managed/allowlist

Implementing the witness in TypeScript

The witness function is provided when constructing the Contract object. It receives a WitnessContext and the leaf value, and must return a tuple of [privateState, path].

The WitnessContext exposes the current ledger state via context.ledger. The compiled contract's Ledger type includes findPathForLeaf on the allowlist field, which does a linear scan of the tree and returns the path for a matching leaf:

const contract = new Contract({
  findLeaf: (context: any, leaf: Uint8Array) => {
    const path = context.ledger.allowlist.findPathForLeaf(leaf);
    if (!path) throw new Error('leaf not found in allowlist');
    return [context.privateState, path];
  },
});

If you know the leaf's index, use pathForLeaf(index, leaf) instead. It runs in O(1) rather than scanning the whole tree.

Testing the allowlist

Create src/allowlist.test.ts:

import { describe, it, expect } from 'vitest';
import {
  createConstructorContext,
  createCircuitContext,
  sampleContractAddress,
} from '@midnight-ntwrk/compact-runtime';
import { Contract, ledger } from '../managed/allowlist/contract/index.js';

const coinPublicKey = new Uint8Array(32);
const contractAddress = sampleContractAddress();

function createSimulator() {
  const contract = new Contract({
    findLeaf: (context: any, leaf: Uint8Array) => {
      const path = context.ledger.allowlist.findPathForLeaf(leaf);
      if (!path) throw new Error('leaf not found in allowlist');
      return [context.privateState, path];
    },
  });

  const constructorCtx = createConstructorContext({}, coinPublicKey);
  const { currentPrivateState, currentContractState, currentZswapLocalState } =
    contract.initialState(constructorCtx);

  const circuitContext = createCircuitContext(
    contractAddress,
    currentZswapLocalState,
    currentContractState,
    currentPrivateState,
  );

  return { contract, circuitContext };
}

const leafA = new Uint8Array(32).fill(1);
const leafB = new Uint8Array(32).fill(2);

describe('allowlist contract', () => {
  it('adds a leaf and increments the counter', () => {
    let { contract, circuitContext } = createSimulator();

    ({ context: circuitContext } = contract.impureCircuits.addToAllowlist(circuitContext, leafA));
    const state = ledger(circuitContext.currentQueryContext.state);

    expect(state.leafCount).toBe(1n);
  });

  it('adds multiple leaves', () => {
    let { contract, circuitContext } = createSimulator();

    ({ context: circuitContext } = contract.impureCircuits.addToAllowlist(circuitContext, leafA));
    ({ context: circuitContext } = contract.impureCircuits.addToAllowlist(circuitContext, leafB));
    const state = ledger(circuitContext.currentQueryContext.state);

    expect(state.leafCount).toBe(2n);
  });

  it('verifies a leaf that is in the allowlist', () => {
    let { contract, circuitContext } = createSimulator();

    ({ context: circuitContext } = contract.impureCircuits.addToAllowlist(circuitContext, leafA));

    expect(() => {
      contract.impureCircuits.verify(circuitContext, leafA);
    }).not.toThrow();
  });

  it('rejects a leaf that is not in the allowlist', () => {
    let { contract, circuitContext } = createSimulator();

    ({ context: circuitContext } = contract.impureCircuits.addToAllowlist(circuitContext, leafA));

    expect(() => {
      contract.impureCircuits.verify(circuitContext, leafB);
    }).toThrow();
  });
});

Run the tests:

npx vitest run src/allowlist.test.ts

Comparing the two approaches

The registry and allowlist illustrate two completely different approaches to the same general problem of tracking membership.

With the Map registry, every key and value is stored in the public ledger. Lookups are O(1). Updates and deletions are first-class operations. The full dataset is readable from TypeScript. The cost is that the entire registry lives on-chain, visible to anyone.

With the Merkle tree allowlist, the tree root is the only commitment stored on-chain. Proving membership requires a path of 20 sibling hashes, computed off-chain by the TypeScript witness. The circuit only verifies the proof against the root: it never reads the full tree. This lets you maintain a large allowlist without exposing all entries in the public transaction transcript. The trade-off is that deletion requires a workaround (inserting the default value), and the path lookup runs in O(n) unless you track indices separately.

Choose a Map when your contract needs mutable key-value state and the data can be public. Choose a MerkleTree when you need to prove membership in a large set with minimal on-chain footprint, or when the contents of the set should not be fully revealed.

What you have built

The registry contract demonstrates:

• Declaring a Map<Bytes<32>, Bytes<32>> ledger field
• Inserting, updating, and removing entries with insert, remove, and member
• Using disclose when writing circuit inputs to the public ledger
• Iterating over Map entries from TypeScript

The allowlist contract demonstrates:

• Declaring a MerkleTree<20, Bytes<32>> ledger field with depth 20
• Inserting leaves with insert
• Declaring a witness function to supply a MerkleTreePath from TypeScript
• Verifying membership with merkleTreePathRoot and checkRoot
• Implementing the witness using findPathForLeaf from the generated Ledger type

Next steps

• Explore the Compact language reference to learn about other ledger types and circuit patterns
• Read the Midnight developer documentation to understand how smart contracts are deployed and queried on the network
• Try combining a Map and a MerkleTree in a single smart contract to manage both mutable state and membership proofs