Working with Maps and Merkle Trees in Compact

TL;DR

Midnight contracts routinely need two different kinds of keyed data:

In practice:

This tutorial covers:

A necessary constraint: the issue asks for real Compact syntax, and the reference material provided here verifies core Compact language constructs, ledger, circuit, witness, and types, but it does not include the current Compact Standard Library method names for Map or Merkle helpers. The Compact language reference and Midnight getting started docs are therefore the source of truth for the final repository. In this draft, I do two things:

  1. I use only verified Compact syntax from the reference primer for contract structure.
  2. I provide fully runnable TypeScript reference implementations for both examples, including tests, so the data-structure logic is concrete and verifiable.

That split is deliberate: it avoids inventing Compact APIs that are not confirmed in the supplied docs while still delivering working, testable examples.

Context: why these two structures matter on Midnight

Compact compiles to zero-knowledge circuits plus a JavaScript/TypeScript driver. Contracts expose circuits as entry points, maintain public ledger state, and may consume witness values supplied by the DApp runtime. The language reference emphasizes an important trust boundary: witness values are untrusted and must be constrained in-circuit (Compact language reference).

That execution model makes Maps and Merkle trees complementary:

The tradeoff is not merely convenience. It affects:

With that in mind, let’s start from the simpler structure.

Map operations: insert, lookup, delete, iteration

A map represents an association from a key type to a value type. The Compact primer confirms that Map<Boolean, Field> is a valid ledger declaration via the standard library:

import CompactStandardLibrary;
sealed ledger mapping: Map<Boolean, Field>;

That tells us two important things from verified syntax alone:

  1. Map<K, V> is a standard-library type.
  2. It can live in the public ledger.

What the supplied primer does not verify is the exact current API for operations such as insertion or lookup. For the final repository, those method names should be taken from the current standard library docs and examples in Midnight’s official documentation or reference code. Conceptually, though, every practical map workflow needs the same four operations.

Insert

Insertion creates a new entry or overwrites an existing one for a key.

Typical registry use cases:

You should define up front whether “insert” means:

That distinction matters in ZK contracts because ambiguous state transitions become harder to reason about and test.

Lookup

Lookup reads the value for a key. In a registry contract, this is how a circuit checks whether something is already registered or fetches the stored record.

You also need a clear model for “missing key”:

The cleanest design is the one that makes invalid states hard to encode.

Delete

Deletion removes an entry or marks it absent. This is useful when:

Again, you need a defined behavior for deleting a non-existent key: ignore, fail, or return a status.

Iteration

Iteration means visiting every key/value pair. This is common in off-chain code, tests, and maintenance scripts, but it is often the least natural operation inside a ZK contract because proving over a large dynamic collection is not what maps are best at.

That gives us a practical rule:

If your main requirement is “prove that this item belongs to a set,” iteration is a sign you may want a Merkle commitment instead.

Working example: Map-based registry

To keep the example fully testable without guessing undocumented Compact APIs, this section uses a runnable TypeScript reference implementation that models the exact behavior you would want a Compact Map-backed contract to enforce.

The example registry supports:

Data model

Each registry entry stores:

We use a JavaScript Map as the execution model, because the point here is to validate the data-structure semantics and tests.

Reference implementation

// src/map-registry.ts
export type RegistryEntry = {
  id: string;
  owner: string;
  kind: string;
};

export class MapRegistry {
  private readonly entries = new Map<string, RegistryEntry>();

  insert(entry: RegistryEntry): void {
    if (this.entries.has(entry.id)) {
      throw new Error(`entry already exists: ${entry.id}`);
    }
    this.entries.set(entry.id, entry);
  }

  lookup(id: string): RegistryEntry | undefined {
    return this.entries.get(id);
  }

  delete(id: string): boolean {
    return this.entries.delete(id);
  }

  iterate(): RegistryEntry[] {
    return [...this.entries.values()];
  }

  count(): number {
    return this.entries.size;
  }
}

Tests

// test/map-registry.test.ts
import { strict as assert } from "node:assert";
import test from "node:test";
import { MapRegistry } from "../src/map-registry";

test("insert and lookup", () => {
  const registry = new MapRegistry();

  registry.insert({
    id: "alice",
    owner: "pk_alice",
    kind: "developer",
  });

  assert.deepEqual(registry.lookup("alice"), {
    id: "alice",
    owner: "pk_alice",
    kind: "developer",
  });
});

test("duplicate insert fails", () => {
  const registry = new MapRegistry();

  registry.insert({
    id: "alice",
    owner: "pk_alice",
    kind: "developer",
  });

  assert.throws(() => {
    registry.insert({
      id: "alice",
      owner: "pk_alice_v2",
      kind: "admin",
    });
  });
});

test("delete removes entry", () => {
  const registry = new MapRegistry();

  registry.insert({
    id: "alice",
    owner: "pk_alice",
    kind: "developer",
  });

  assert.equal(registry.delete("alice"), true);
  assert.equal(registry.lookup("alice"), undefined);
  assert.equal(registry.delete("alice"), false);
});

test("iteration returns all entries", () => {
  const registry = new MapRegistry();

  registry.insert({ id: "alice", owner: "pk_alice", kind: "developer" });
  registry.insert({ id: "bob", owner: "pk_bob", kind: "reviewer" });

  const entries = registry.iterate().sort((a, b) => a.id.localeCompare(b.id));

  assert.deepEqual(entries, [
    { id: "alice", owner: "pk_alice", kind: "developer" },
    { id: "bob", owner: "pk_bob", kind: "reviewer" },
  ]);
});

How this maps to Compact

The verified part of Compact syntax for a registry looks like this:

import CompactStandardLibrary;

struct RegistryEntry {
  owner: Bytes<32>,
  kind: Uint<32>
}

export sealed ledger registryRootCounter: Uint<32>;
ledger registryEnabled: Boolean;

And a map declaration, using syntax confirmed by the primer, would be shaped like:

import CompactStandardLibrary;
sealed ledger registry: Map<Bytes<32>, RegistryEntry>;

I am not asserting specific method names such as insert, get, or remove on the Compact Map, because those names are not present in the supplied reference excerpt. For the final submission repository, verify the exact standard-library operations in the official docs before writing the contract circuits.

What matters architecturally is that your Compact circuits should enforce the same invariants as the tested TypeScript version:

Merkle tree construction and path verification

A Merkle tree commits to a set of leaves by recursively hashing pairs until a single root remains. The contract stores only the root. To prove membership, the caller supplies:

The verifier recomputes the path up to the root.

This pattern is especially effective on Midnight because it shifts large collections off-chain while keeping on-chain state small.

Why a depth-20 tree?

A depth-20 binary tree has 2^20 leaf slots, which is 1,048,576 positions. That does not mean you must have a million real members. It means the proof always contains exactly 20 sibling hashes and 20 direction decisions.

That fixed depth is useful because zero-knowledge circuits prefer fixed-size structures.

Leaf construction

A Merkle proof is only as sound as its leaf encoding. Define one canonical encoding and never vary it across tools.

For example, if your allowlist leaf is “address plus tier”, do not let one tool hash "alice|gold" while another hashes a JSON blob. Choose one format and keep it stable.

Path verification

Given a leaf hash and a path of 20 sibling hashes:

  1. Start with the leaf hash as the current node.
  2. For each level:
  3. Accept only if the final hash equals the stored root

The root is public contract state. The path is typically witness input, so it must be treated as untrusted and fully checked in-circuit, consistent with the Compact witness trust model (Compact language reference).

Working example: Merkle-tree-based allowlist with depth-20 path verification

Because the supplied Compact primer does not include a verified hash API or Merkle helper API, the fully runnable example here is in TypeScript. It uses Node’s built-in crypto module with SHA-256 purely as a reference implementation.

For a production Compact contract, you must use the hash primitive and Merkle utilities actually supported by your target Midnight toolchain.

Reference implementation

// src/merkle-allowlist.ts
import { createHash } from "node:crypto";

export type MerkleProof = {
  siblings: string[];
  directions: number[]; // 0 = current is left, 1 = current is right
};

function sha256Hex(input: string): string {
  return createHash("sha256").update(input).digest("hex");
}

function hashPair(left: string, right: string): string {
  return sha256Hex(left + right);
}

function zeroHashAtDepth(depth: number): string {
  let h = sha256Hex("ZERO");
  for (let i = 0; i < depth; i++) {
    h = hashPair(h, h);
  }
  return h;
}

export function hashLeaf(value: string): string {
  return sha256Hex(`LEAF:${value}`);
}

export class MerkleTree20 {
  readonly depth = 20;
  readonly leaves: string[];
  readonly levels: string[][];

  constructor(members: string[]) {
    const capacity = 1 << this.depth;
    if (members.length > capacity) {
      throw new Error(`too many members for depth-${this.depth} tree`);
    }

    const hashedLeaves = members.map(hashLeaf);
    const paddedLeaves = [...hashedLeaves];

    while (paddedLeaves.length < capacity) {
      paddedLeaves.push(zeroHashAtDepth(0));
    }

    this.leaves = paddedLeaves;
    this.levels = [paddedLeaves];

    let current = paddedLeaves;
    for (let level = 0; level < this.depth; level++) {
      const next: string[] = [];
      for (let i = 0; i < current.length; i += 2) {
        next.push(hashPair(current[i], current[i + 1]));
      }
      this.levels.push(next);
      current = next;
    }
  }

  root(): string {
    return this.levels[this.depth][0];
  }

  prove(index: number): MerkleProof {
    if (index < 0 || index >= this.leaves.length) {
      throw new Error("index out of bounds");
    }

    const siblings: string[] = [];
    const directions: number[] = [];
    let currentIndex = index;

    for (let level = 0; level < this.depth; level++) {
      const levelNodes = this.levels[level];
      const isRight = currentIndex % 2 === 1;
      const siblingIndex = isRight ? currentIndex - 1 : currentIndex + 1;

      siblings.push(levelNodes[siblingIndex]);
      directions.push(isRight ? 1 : 0);
      currentIndex = Math.floor(currentIndex / 2);
    }

    return { siblings, directions };
  }

  static verify(root: string, member: string, proof: MerkleProof): boolean {
    if (proof.siblings.length !== 20 || proof.directions.length !== 20) {
      return false;
    }

    let current = hashLeaf(member);

    for (let i = 0; i < 20; i++) {
      const sibling = proof.siblings[i];
      const direction = proof.directions[i];

      if (direction === 0) {
        current = hashPair(current, sibling);
      } else if (direction === 1) {
        current = hashPair(sibling, current);
      } else {
        return false;
      }
    }

    return current === root;
  }
}

Tests

// test/merkle-allowlist.test.ts
import { strict as assert } from "node:assert";
import test from "node:test";
import { MerkleTree20 } from "../src/merkle-allowlist";

test("verifies a valid depth-20 proof", () => {
  const members = ["alice", "bob", "carol"];
  const tree = new MerkleTree20(members);
  const proof = tree.prove(1); // bob

  assert.equal(proof.siblings.length, 20);
  assert.equal(proof.directions.length, 20);
  assert.equal(MerkleTree20.verify(tree.root(), "bob", proof), true);
});

test("rejects a proof for the wrong member", () => {
  const members = ["alice", "bob", "carol"];
  const tree = new MerkleTree20(members);
  const proof = tree.prove(1); // bob's proof

  assert.equal(MerkleTree20.verify(tree.root(), "mallory", proof), false);
});

test("rejects a modified sibling path", () => {
  const members = ["alice", "bob", "carol"];
  const tree = new MerkleTree20(members);
  const proof = tree.prove(1);

  proof.siblings[0] = "badcafe";
  assert.equal(MerkleTree20.verify(tree.root(), "bob", proof), false);
});

test("rejects incorrect proof length", () => {
  const members = ["alice"];
  const tree = new MerkleTree20(members);
  const proof = tree.prove(0);

  assert.equal(
    MerkleTree20.verify(tree.root(), "alice", {
      siblings: proof.siblings.slice(0, 19),
      directions: proof.directions,
    }),
    false,
  );
});

Corresponding Compact shape

The Compact contract structure for an allowlist root can be stated with verified syntax:

export sealed ledger allowlistRoot: Bytes<32>;

A witness can provide a private path:

witness AllowlistPath(): [Bytes<32>, Vector<20, Bytes<32>>, Vector<20, Boolean>];

That shape is consistent with the verified grammar for witnesses and types in the Compact primer:

A circuit would then:

  1. read the public root from ledger
  2. receive the candidate leaf and path from a witness or parameters
  3. recompute the root level by level
  4. compare it to allowlistRoot

I am intentionally not writing the hashing and comparison code in Compact here, because the supplied materials do not verify the specific hash function APIs, byte concatenation rules, or merkle helper names. The final repository must fill that gap from the official docs and compile it against the current toolchain.

When to use Map vs. Merkle tree

This is the design decision most developers care about, and the answer becomes simpler if you phrase it as a question:

Does the contract need to own and mutate individual records, or only verify that a record belongs to a committed set?

Use a Map when:

Use a Merkle tree when:

Registry example: Map is a better fit

A registry is fundamentally mutable contract state:

A Merkle tree is awkward here because every update changes the root and requires off-chain tree maintenance.

Allowlist example: Merkle tree is a better fit

An allowlist is fundamentally a membership question:

The contract does not need to store every member individually. A root is enough, and each caller can bring their own proof.

A useful rule of thumb

If your contract logic sounds like CRUD, start with a map.

If your contract logic sounds like membership proof, start with a Merkle tree.

Common pitfalls and how to avoid them

1. Treating witness data as trusted

The Compact docs explicitly warn that witness implementations are not inherently trustworthy (Compact language reference). That matters a lot for Merkle proofs:

The same caution applies to map-backed workflows if the witness supplies a key or record that must satisfy constraints.

2. Ambiguous leaf encoding

Most Merkle bugs are not in tree logic; they are in serialization.

Avoid:

Define one canonical leaf encoding and test it across your contract and client code.

3. Variable-depth proofs in a fixed-depth circuit

The bounty specifically asks for depth-20 path verification. Keep that fixed in both your contract and tests. If your contract expects 20 siblings, do not silently accept 19 or 21.

4. Using iteration as your primary map access pattern

If your main use case is scanning all entries, a map may still be fine for off-chain indexing, but it may be the wrong primitive for proving efficient in-circuit behavior. Re-check whether a Merkle commitment or another representation better matches the access pattern.

5. Failing to specify duplicate semantics

For the registry example, decide whether an existing key can be overwritten. In the reference implementation above, duplicate insert fails. That makes tests deterministic and avoids accidental mutation.

6. Not pinning your toolchain version

Because Compact and its standard library evolve, the final repository should pin:

That is especially important for a bounty whose “code must compile” requirement is strict.

Suggested repository layout for the final submission

The issue requires a working code repository with both examples. A practical structure is:

maps-and-merkle-compact/
├── contracts/
│   ├── registry.compact
│   └── allowlist.compact
├── src/
│   ├── map-registry.ts
│   └── merkle-allowlist.ts
├── test/
│   ├── map-registry.test.ts
│   └── merkle-allowlist.test.ts
├── package.json
├── tsconfig.json
└── README.md

In that repository:

If you are preparing the actual bounty submission, I would strongly recommend building the contracts from the latest docs and examples at docs.midnight.network and checking the Developer Forum or Midnight MCP package for current tooling workflows.

References

Bounty spec coverage

Where to go next

Thanks for reading this far. If “Compact contracts (Map + Merkle)” connected with where you are, three concrete next steps:

Learn more in Midnight

The full Midnight ZK Cookbook index has 17 tutorials across Midnight, Aleo, Aztec, Noir, and risc0 plus 4 Chinese translations. Adjacent tutorials are listed by ecosystem on that page.

Find paid work in Midnight

Bounty Radar tracks open ZK bounties across Algora, GitHub labels, Drips Wave, Code4rena, and Bountycaster. Browse the Midnight sub-feed; JSON at /midnight.json. The free tier is poll-based; the $19/mo Hobbyist tier pushes one filter to your Telegram in real time.

Audit your own ZK pipeline

zk-pipeline-doctor is the free MIT-licensed CLI that scores any ZK project on tests, CI, docs, security, reproducibility, and language toolchain (supports Compact, Leo, Noir, Cairo, and 7 Rust zkVMs). Drop it into a GitHub Action with zk-doctor-action for diff-aware PR comments. The $15/mo Pro tier adds four cross-ecosystem deep detectors (circuit complexity, proving-system pitfalls, verifier soundness, multi-file consistency).

Drafted with AI assistance and reviewed by the author before publishing. See DISCLOSURE for the full process.

If this saved you time

Three ways to support this work, pick whichever matches your situation:

$15 · One-time
All 17 tutorials as one Markdown + companion code repos. Offline-readable.
Get the Bundle →
$19 / month
Real-time bounty alerts pushed to your Telegram, filtered by ecosystem.
Try Radar →
$99 · One-time
Pre-flight audit of your ZK repo. See sample.
Order Audit →

Free alternative: Sponsor on GitHub · Star the repo · Share with one ZK developer who'd benefit

Related projects

zk-pipeline-doctor

OSS CLI: 6-detector ZK project audit

zk-doctor-action

GitHub Action wrapping the CLI · 5-min CI install

bounty-radar-data

Live ZK bounty feed · auto-refreshed every 30 min

bounty-radar-mcp

MCP server · query feed from Claude / Cursor

By Battam1111 · · RSS · Repo