Working with Maps and Merkle Trees in Compact (Midnight Network)

Bounty: midnightntwrk/contributor-hub #289

Midnight is a privacy-first blockchain built on Cardano's infrastructure. Its smart-contract language, Compact, compiles to ZK circuits so that contract state can remain shielded while still being verifiable. One of the most powerful—and initially confusing—features of the SDK is its first-class support for Maps and Merkle Trees. In this tutorial you'll learn:

• How Maps work in Compact and why they're different from a plain Solidity mapping
• How MerkleTree structures are maintained on the TypeScript side
• How to create, update, and read Map entries from a TypeScript client
• A real-world membership allowlist built with a Merkle tree

---

Table of Contents

1. Why Maps in a ZK Contract Are Different
2. Compact Map Basics
3. TypeScript SDK: Ledger State & Maps
4. Working with MerkleTrees
5. Real-World Example: Membership Allowlist
6. Reading State Back from the Contract
7. Common Pitfalls
8. Summary

---

1. Why Maps in a ZK Contract Are Different

In a conventional EVM smart contract, a mapping is a simple key→value store that lives on-chain in plaintext. Anyone can inspect every entry.

Midnight's shielded ledger flips this model. Contract state is encrypted; only the current owner of the state (whoever holds the relevant secret key) can decrypt it. The network verifies that state transitions are valid via zero-knowledge proofs—without ever seeing the raw values.

This means:

Concern	EVM Mapping	Midnight Map
On-chain visibility	Public	Encrypted
Verification method	Re-execution	ZK proof
Client responsibility	Simple RPC call	Maintain local Merkle witness
Key lookup	O(1) in storage	O(log n) via Merkle path

The trade-off is that the client bears more responsibility for maintaining cryptographic state. Understanding this is key to writing correct Midnight dApps.

---

2. Compact Map Basics

Compact's standard library ships Map<K, V> as a built-in type. Here's a minimal contract that stores a UInt64 balance per Bytes<32> address:

pragma language_version >= 0.14;

import CompactStandardLibrary;

// A shielded map from 32-byte address → UInt64 balance
export ledger balances: Map<Bytes<32>, UInt64>;

// Initialise a new entry (called once per address)
export circuit deposit(
    addr: Bytes<32>,
    amount: UInt64
): [] {
    // insert_or_update: creates the entry if absent, updates if present
    balances.insert_or_update(addr, amount);
}

// Transfer between two addresses
export circuit transfer(
    from: Bytes<32>,
    to:   Bytes<32>,
    amount: UInt64
): [] {
    const fromBal = balances.lookup(from);
    assert fromBal >= amount : "Insufficient balance";

    balances.insert_or_update(from, fromBal - amount);

    const toBal = balances.lookup_with_default(to, 0 as UInt64);
    balances.insert_or_update(to, toBal + amount);
}

Key API surface for Map<K,V> in Compact:

Method	Description
insert_or_update(k, v)	Create or overwrite an entry
lookup(k)	Fetch value; circuit aborts if key missing
lookup_with_default(k, d)	Fetch value; return d if key missing
remove(k)	Delete an entry
member(k)	Boolean existence check

Important: lookup will cause the ZK proof to fail if the key doesn't exist. Prefer lookup_with_default for optional lookups, or guard with member.

---

3. TypeScript SDK: Ledger State & Maps

When a Midnight contract compiles, the SDK generates typed TypeScript bindings. For the balances map above you'll get a BalancesLedger type and a helper that deserialises the on-chain state into a local Map-like object.

3.1 Project Setup

# Scaffold a new Midnight project
npx @midnight-ntwrk/midnight-js-cli init my-map-demo
cd my-map-demo
npm install

The important packages are:

{
  "@midnight-ntwrk/compact-runtime": "^0.14.0",
  "@midnight-ntwrk/midnight-js-contracts": "^0.14.0",
  "@midnight-ntwrk/midnight-js-types": "^0.14.0"
}

3.2 Deploying the Contract

import {
  createMidnightClient,
  deployContract,
  MidnightProviders,
} from '@midnight-ntwrk/midnight-js-contracts';
import { balancesContractInstance } from './generated/balances'; // auto-generated

async function deploy(providers: MidnightProviders) {
  const client = createMidnightClient(providers);

  const { deployTxData, contractAddress } = await deployContract(
    client,
    balancesContractInstance,
    {}, // initial ledger state — empty Map by default
  );

  console.log('Contract deployed at:', contractAddress);
  return contractAddress;
}

3.3 Calling deposit

import { ContractAddress } from '@midnight-ntwrk/midnight-js-types';
import { encodePadded } from '@midnight-ntwrk/midnight-js-utils';

async function callDeposit(
  providers: MidnightProviders,
  contractAddress: ContractAddress,
  rawAddress: Uint8Array, // 32-byte address
  amount: bigint,
) {
  const client = createMidnightClient(providers);
  const contract = await client.getContract(
    balancesContractInstance,
    contractAddress,
  );

  // The SDK builds the ZK proof automatically
  const tx = await contract.callTx.deposit(rawAddress, amount);
  await tx.submit();

  console.log('Deposit submitted, tx hash:', tx.hash);
}

3.4 Calling transfer

async function callTransfer(
  providers: MidnightProviders,
  contractAddress: ContractAddress,
  from: Uint8Array,
  to: Uint8Array,
  amount: bigint,
) {
  const client = createMidnightClient(providers);
  const contract = await client.getContract(
    balancesContractInstance,
    contractAddress,
  );

  const tx = await contract.callTx.transfer(from, to, amount);
  await tx.submit();
}

Behind the scenes, callTx.transfer does a lot of work:

1. Fetches the latest shielded ledger state
2. Decrypts it using the caller's secret key
3. Builds a ZK proof that the transition is valid
4. Submits the proof + encrypted new state to the network

---

4. Working with MerkleTrees

Compact's Map is implemented as a Sparse Merkle Tree (SMT) under the hood. Every entry you insert changes the root hash of the tree. The TypeScript SDK exposes this tree directly so you can:

• Compute Merkle paths (witnesses) for membership proofs
• Verify on the client side before submitting
• Build your own custom off-chain indexes

4.1 The MerkleTree Type

The SDK exports MerkleTree<K, V> from @midnight-ntwrk/compact-runtime:

import { MerkleTree, MerkleTreeKey, MerkleTreeValue } from '@midnight-ntwrk/compact-runtime';

// Construct an empty tree with the same parameters as the contract's Map
const tree = MerkleTree.empty<Uint8Array, bigint>();

// Insert a key-value pair
const updatedTree = tree.insert(myKey, myValue);

// Get the root (a 32-byte Uint8Array)
const root: Uint8Array = updatedTree.root();

// Generate a Merkle path for a key
const path = updatedTree.witness(myKey);
console.log('Path length:', path.siblings.length);

// Verify the path against the root
const isValid = MerkleTree.verifyPath(root, myKey, myValue, path);
console.log('Valid:', isValid); // true

4.2 Syncing the Local Tree with On-Chain State

The contract's shielded state changes every time a transaction is confirmed. The SDK provides a subscription mechanism to keep your local tree in sync:

import { subscribeToContractState } from '@midnight-ntwrk/midnight-js-contracts';

async function watchBalances(
  providers: MidnightProviders,
  contractAddress: ContractAddress,
) {
  const subscription = subscribeToContractState(
    providers,
    balancesContractInstance,
    contractAddress,
  );

  for await (const state of subscription) {
    // `state.balances` is a MerkleTree<Bytes32, bigint>
    const root = state.balances.root();
    console.log('New root:', Buffer.from(root).toString('hex'));

    // You can now query the tree locally
    const myBalance = state.balances.get(myAddress);
    console.log('My balance:', myBalance);
  }
}

---

5. Real-World Example: Membership Allowlist

Let's build something concrete: a private membership allowlist where:

• Members are stored as a Merkle tree of public keys
• Membership proofs can be verified without revealing who the other members are
• The contract can gate access to a function based on Merkle membership

5.1 Compact Contract

pragma language_version >= 0.14;

import CompactStandardLibrary;

// Shielded set of 32-byte member public keys
export ledger members: Map<Bytes<32>, Boolean>;

// Admin address (deployer-set, stored in public state)
export ledger adminKey: Bytes<32>;

// Add a member — only callable by admin
export circuit addMember(
    adminSig: Bytes<64>,    // signature over the new member's key
    newMember: Bytes<32>
): [] {
    // Verify admin signature (simplified — real implementation uses secp256k1)
    assert verify_signature(adminKey, adminSig, newMember) : "Not admin";
    members.insert_or_update(newMember, true);
}

// Remove a member
export circuit removeMember(
    adminSig: Bytes<64>,
    target: Bytes<32>
): [] {
    assert verify_signature(adminKey, adminSig, target) : "Not admin";
    members.remove(target);
}

// Gate-checked action — only members can call this
export circuit memberOnlyAction(
    callerKey: Bytes<32>
): [] {
    const isMember = members.lookup_with_default(callerKey, false);
    assert isMember : "Not a member";

    // ... do the privileged action
}

5.2 TypeScript Client: Admin Adds Members

import { createMidnightClient } from '@midnight-ntwrk/midnight-js-contracts';
import { signBytes } from '@midnight-ntwrk/midnight-js-crypto'; // hypothetical helper

interface MembershipContract {
  callTx: {
    addMember(adminSig: Uint8Array, newMember: Uint8Array): Promise<Transaction>;
    removeMember(adminSig: Uint8Array, target: Uint8Array): Promise<Transaction>;
    memberOnlyAction(callerKey: Uint8Array): Promise<Transaction>;
  };
}

async function addMember(
  providers: MidnightProviders,
  contractAddress: ContractAddress,
  adminSecretKey: Uint8Array,
  newMemberKey: Uint8Array,
) {
  const client = createMidnightClient(providers);
  const contract = await client.getContract<MembershipContract>(
    membershipContractInstance,
    contractAddress,
  );

  // Sign the new member's key with the admin secret key
  const sig = signBytes(adminSecretKey, newMemberKey);

  const tx = await contract.callTx.addMember(sig, newMemberKey);
  await tx.submit();
  console.log('Member added:', Buffer.from(newMemberKey).toString('hex'));
}

5.3 TypeScript Client: Querying Membership

One of the key privacy properties is that you can check your own membership without revealing others:

async function checkMembership(
  providers: MidnightProviders,
  contractAddress: ContractAddress,
  candidateKey: Uint8Array,
): Promise<boolean> {
  const client = createMidnightClient(providers);
  const contract = await client.getContract(
    membershipContractInstance,
    contractAddress,
  );

  // Fetch latest ledger state (decrypted client-side)
  const state = await contract.fetchState();

  // Check local Merkle tree — no network round-trip needed
  const isMember = state.members.get(candidateKey) ?? false;
  return isMember;
}

5.4 Generating a Merkle Proof for Off-Chain Verification

Sometimes you need to prove membership to a third party (e.g., a web2 backend) without them having access to the full contract state:

async function generateMembershipProof(
  providers: MidnightProviders,
  contractAddress: ContractAddress,
  memberKey: Uint8Array,
) {
  const client = createMidnightClient(providers);
  const contract = await client.getContract(
    membershipContractInstance,
    contractAddress,
  );

  const state = await contract.fetchState();
  const tree = state.members; // MerkleTree<Bytes32, Boolean>

  // Generate a Merkle path
  const path = tree.witness(memberKey);
  const root = tree.root();

  return {
    root: Buffer.from(root).toString('hex'),
    key: Buffer.from(memberKey).toString('hex'),
    value: true,
    path: path.siblings.map(s => Buffer.from(s).toString('hex')),
  };
}

// Third-party verification (no access to contract state needed)
function verifyMembershipProof(proof: ReturnType<typeof generateMembershipProof>) {
  const root = Buffer.from(proof.root, 'hex');
  const key = Buffer.from(proof.key, 'hex');
  const siblings = proof.path.map(s => Buffer.from(s, 'hex'));

  return MerkleTree.verifyPath(root, key, true, { siblings });
}

---

6. Reading State Back from the Contract

Full state reads are useful for building UIs, dashboards, or off-chain indexes. The SDK's fetchState() method returns the entire decrypted ledger:

async function buildMemberList(
  providers: MidnightProviders,
  contractAddress: ContractAddress,
): Promise<string[]> {
  const client = createMidnightClient(providers);
  const contract = await client.getContract(
    membershipContractInstance,
    contractAddress,
  );

  const state = await contract.fetchState();

  // Iterate the Merkle tree — yields [key, value] pairs
  const memberKeys: string[] = [];
  for (const [key, value] of state.members.entries()) {
    if (value === true) {
      memberKeys.push(Buffer.from(key).toString('hex'));
    }
  }

  return memberKeys;
}

Privacy note: Only the state owner (holder of the secret key) can decrypt and iterate. A third party sees only the encrypted blob and root hash.

---

7. Common Pitfalls

7.1 Forgetting lookup_with_default

// ❌ This will abort the proof if key is missing
const val = myMap.lookup(key);

// ✅ Safe version with a sensible default
const val = myMap.lookup_with_default(key, 0 as UInt64);

7.2 Stale Local State

If you call contract.callTx.someCircuit() with a stale local tree, the SDK will throw a proof-generation error. Always use subscribeToContractState or call fetchState() before building transactions.

7.3 Key Size Mismatches

Compact's Bytes<32> is exactly 32 bytes. If you pass a shorter buffer from TypeScript, the SDK will pad or reject it depending on the version. Always use the typed helpers:

import { toBytes32 } from '@midnight-ntwrk/midnight-js-utils';

const key = toBytes32(myPublicKey); // ensures correct length

7.4 Large Maps and Proof Size

Every lookup in a Compact circuit adds Merkle path length to the proof. A map with 1M entries has a path depth of ~20. Keep circuits lean: do the minimum number of lookups per circuit call.

---

8. Summary

Midnight's Map<K,V> gives you a privacy-preserving key-value store backed by a Sparse Merkle Tree. The key takeaways:

• Compact exposes insert_or_update, lookup, lookup_with_default, remove, and member on maps
• TypeScript interacts via auto-generated contract bindings; the SDK handles ZK proof generation
• MerkleTree in the SDK lets you compute paths, verify membership, and iterate entries locally
• The membership allowlist pattern is a canonical use case: store member keys privately, gate circuits with assert member(key), generate proofs for off-chain verifiers

Maps and Merkle trees unlock private state that is still publicly verifiable—the core value proposition of Midnight. Once you're comfortable with the basics, explore combining maps with Midnight's witness pattern for even richer ZK identity proofs (see the companion article on DIDs).

---

Happy building on Midnight! Drop questions in the Midnight Discord or the contributor hub.