Building Sybil-Resistant Anonymous Systems on Midnight: Mastering Historic Merkle Trees and Domain-Separated Nullifiers in Compact

Introduction

Traditional EVM patterns make every transaction public, permanently stamping the caller's address on the global ledger. If you want to verify eligibility, you must reveal the address, linking their entire transactional history, wallet balance, and identity forever. Midnight Network flips this paradigm. On Midnight, smart contracts written in Compact execute inside local Zero-Knowledge (ZK) circuits on the user's device before touching the network. However, moving to a privacy-first ZK architecture introduces a fundamental computer science dilemma: if a user's identity is completely private, how do you prevent them from voting twice, claiming an airdrop multiple times, or double-spending a confidential voucher?

This comprehensive guide builds a production-grade, Sybil-resistant anonymous action engine on Midnight, exploring:

• The Anonymous Membership Accumulator: why HistoricMerkleTree solves asynchronous race conditions where standard Merkle trees fail
• The Nullifier Pattern: how deterministic, domain-separated cryptographic nullifiers prevent double-actions without doxxing the user
• The Compact Witness Taint System: why the compiler requires disclose() and why disclosing the nullifier does not compromise voter privacy
• End-to-End TypeScript SDK Integration: wiring the Compact contract to @midnight-ntwrk/midnight-js-contracts and running the local Docker Proof Server

Architecture Overview

The Anonymous Membership Accumulator

The core challenge is preventing Sybil attacks while maintaining anonymity. Standard Merkle trees fail under certain conditions due to race conditions when generating Zero-Knowledge proofs on user devices.

The Nullifier Pattern

A deterministic, domain-separated cryptographic nullifier prevents double-actions without revealing the user's identity. The nullifier is computed as:

nullifier = persistentHash<Vector<2, Bytes<32>>>([sk, poll_id])

Key properties:

• Deterministic: the same secret key and poll ID always produce the exact same nullifier
• Unlinkable: because persistentHash uses SHA-256 compression, it is computationally infeasible to invert the nullifier to discover the secret key
• Domain-separated: adding poll_id ensures voters in different polls get distinct nullifiers

The Compact Witness Taint System

In Compact, any variable derived from a witness function is tagged with a witness taint in the compiler's type system. Writing a tainted variable to the ledger throws a compile-time error requiring explicit disclose().

Toolchain & Versions

All code in this guide is tested and pinned against these active versions:

The Nullifier Pattern

Before writing Compact code, understanding the cryptographic flow is essential. Two invariants must be satisfied:

1. Zero-Knowledge Membership: the verifier must be convinced the caller is in the authorized roster without learning which member they are
2. Unlinkable Single-Use Enforceability: the blockchain must guarantee the caller cannot execute the action more than once

Sequence of operations:

1. Fetch Merkle path for commitment
2. Derive Nullifier = persistentHash([sk, poll_id])
3. Submit private inputs (sk, path) to generate ZK Proof
4. Return ZK Proof & public transcript
5. Submit Tx: Proof + disclose(Nullifier) + vote choice

On the ledger side:

• Check that the voter's tree commitment exists (voter_tree.checkRoot(root) == true)
• Ensure the nullifier hasn't been spent (spent_nullifiers.member(nullifier) == false)

The Three Cryptographic Pillars

1. Identity Commitment

A voter possesses a 32-byte secret key sk kept in local private storage. During registration, their public commitment is derived via a one-way collision-resistant hash:

Commitment = persistentHash<Bytes<32>>(sk)

This commitment is inserted as a leaf into the on-chain Merkle tree.

2. Historic Merkle Membership Proof

To vote, the user constructs a Merkle membership proof showing their commitment exists in the tree. The key insight is using HistoricMerkleTree instead of a regular MerkleTree.

Why HistoricMerkleTree? Generating a ZK proof on a user's machine typically takes 2-5 seconds. If another user registers their commitment during that window, the root of a standard Merkle tree advances. When the first user submits their transaction, it would revert with a stale root error!

HistoricMerkleTree keeps a bounded ring-buffer of recent valid roots on the ledger. The method voter_tree.checkRoot(computed_root) verifies against any valid recent root, eliminating concurrent front-running bugs.

3. Domain-Separated Nullifier

If the voter disclosed their identity commitment on-chain, anyone could match it against the registration list and deanonymize them. Instead, the circuit derives a Nullifier that is deterministic and domain-separated:

Nullifier = persistentHash<Vector<2, Bytes<32>>>([sk, poll_id])

Properties:

• Deterministic: same sk and poll_id always produce the exact same nullifier
• Unlinkable: because persistentHash is a one-way cryptographic function (SHA-256 compression), it is computationally infeasible to invert the nullifier to discover sk
• Domain-Separated: scoping the nullifier with poll_id guarantees that voting in "Poll #1" generates a completely different nullifier than voting in "Poll #2"

The Smart Contract

Here is the complete, production-ready Compact contract implementing this pattern. Save this file as anonymous_voting.compact:

pragma language_version >= 0.23;
import CompactStandardLibrary;

// ===========================================================================
// 1. PUBLIC LEDGER STATE
// Stored persistently on the Midnight blockchain and visible to everyone.
// =========================================================================

// Bounded Merkle tree of depth 16 storing voter commitments.
// Uses HistoricMerkleTree to accept recent valid roots and avoid race conditions.
export ledger voter_tree: HistoricMerkleTree<16, Bytes<32>>;
// Set-like mapping tracking consumed nullifiers to prevent double-voting.
export ledger spent_nullifiers: Map<Bytes<32>, Boolean>;
// Public vote tallies
export ledger votes_yes: Counter;
export ledger votes_no: Counter;

// ===========================================================================
// 2. PRIVATE WITNESS DECLARATIONS
// Witnesses run strictly on the client machine. They supply private data to
// the local ZK circuit and are NEVER transmitted over the network.
// =========================================================================

// Retrieves the voter's raw private key from secure local storage
witness get_voter_secret(): Bytes<32>;

// Retrieves the Merkle inclusion proof for this voter's commitment
witness get_merkle_path(): MerkleTreePath<16, Bytes<32>>;

// ===========================================================================
// 3. EXPORTED CIRCUITS
// Callable entrypoints that generate Zero-Knowledge proofs.
// =========================================================================

/** * @notice Registers a new voter by appending their public commitment to the Merkle tree. *
 * @param voter_commitment The persistentHash(secret_key) of the voter. */
export circuit register_voter(voter_commitment: Bytes<32>): [] {
    // Append commitment leaf into the Historic Merkle tree
    voter_tree.insert(voter_commitment);
}

/** * @notice Casts an anonymous vote using a ZK membership proof and nullifier guard. *
 * @param poll_id The 32-byte identifier of the specific poll or proposal. *
 * @param choice True for 'Yes', False for 'No'. */
export circuit cast_vote(poll_id: Bytes<32>, choice: Boolean): [] {
    // Step 1: Read private data locally from the user's device
    const secret = get_voter_secret();
    const path = get_merkle_path();

    // Step 2: Cryptographically derive the voter's identity commitment
    const expected_leaf = persistentHash<Bytes<32>>(secret);

    // Step 3: ZK Invariant: Ensure the supplied Merkle path belongs to this secret
    assert(path.leaf == expected_leaf, "Merkle path leaf does not match derived secret commitment");

    // Step