tree_nullifier_reference.py

#!/usr/bin/env python3
"""
The Only Vote
Reference #1 - Eligible-Voter Tree + Nullifier

WHAT THIS IS
    A small, runnable, original demonstration of the core voting mechanism:
    one human -> one secret -> membership in the eligible set (proven without
    revealing which member) -> one election-scoped nullifier -> repeat votes
    rejected, including across locations (the "two homes" FL/PA case).

WHAT IT PROVES
    Privacy + one-vote + no geo-duplication are a SINGLE mechanism, and the
    math does the deduplication on its own.

WHAT THIS IS NOT (honest scope)
    - Not a zero-knowledge system. Real privacy needs a ZK proof framework
      (e.g. Noir / circom) so the membership check reveals nothing. Here we
      verify the Merkle path in the clear to show the LOGIC transparently.
    - Not production crypto. We use SHA-256 from the standard library as a
      stand-in; a real build uses a ZK-friendly hash (Pedersen / Poseidon).
    - The nullifier registry here is in-memory. A real build anchors it to a
      public, permanent record (see ARCHITECTURE.md, Layer 5).

PROVENANCE
    Original work for this project. Built from public concepts (Merkle
    membership, nullifiers) credited as prior art in CREDITS.md. Depends on
    no one's code. No third-party dependencies.

RUN
    python3 tree_nullifier_reference.py
"""

import hashlib
import secrets


# ----------------------------------------------------------------------
# Primitives
# ----------------------------------------------------------------------

def H(*parts: bytes) -> bytes:
    """Domain-separated, length-prefixed hash.
    Stand-in for a ZK-friendly hash in production."""
    d = hashlib.sha256()
    for p in parts:
        d.update(len(p).to_bytes(4, "big"))
        d.update(p)
    return d.digest()


def new_secret() -> bytes:
    """A voter's ONE secret = their one credential. In the real system this is
    derived at enrollment and unlocked locally by biometric (No Vault); it is
    never stored centrally."""
    return secrets.token_bytes(32)


def commitment(secret: bytes) -> bytes:
    """The public leaf placed in the eligible-voter tree. Hides the secret."""
    return H(b"commitment", secret)


def nullifier(secret: bytes, election_id: bytes) -> bytes:
    """Unique per (person, election), unlinkable to identity. Voting twice in
    the same election -> same nullifier -> caught, no matter where it's cast."""
    return H(b"nullifier", secret, election_id)


# ----------------------------------------------------------------------
# Merkle tree of eligible voters
# ----------------------------------------------------------------------

class MerkleTree:
    """A binary Merkle tree. The root is a single fingerprint of the whole
    eligible-voter set; a 'proof' shows one leaf is in it without revealing
    the others."""

    def __init__(self, leaves):
        if not leaves:
            raise ValueError("need at least one eligible voter")
        self.leaves = list(leaves)
        self._levels = self._build(self.leaves)

    @staticmethod
    def _build(leaves):
        empty = H(b"empty")
        level = list(leaves)
        size = 1
        while size < len(level):
            size <<= 1
        level += [empty] * (size - len(level))          # pad to power of two
        levels = [level]
        while len(level) > 1:
            level = [H(b"node", level[i], level[i + 1])
                     for i in range(0, len(level), 2)]
            levels.append(level)
        return levels

    @property
    def root(self) -> bytes:
        return self._levels[-1][0]

    def proof(self, index: int):
        """Sibling path from a leaf up to the root: list of (sibling, sib_is_right)."""
        path = []
        for level in self._levels[:-1]:
            sib = index ^ 1
            path.append((level[sib], sib > index))
            index >>= 1
        return path

    @staticmethod
    def verify(leaf: bytes, path, root: bytes) -> bool:
        node = leaf
        for sibling, sib_is_right in path:
            node = (H(b"node", node, sibling) if sib_is_right
                    else H(b"node", sibling, node))
        return node == root


# ----------------------------------------------------------------------
# An election
# ----------------------------------------------------------------------

class Election:
    """Holds the eligible-voter tree and the registry of spent nullifiers.
    NOTE: in the real system the voter computes their own proof + nullifier and
    submits only those; the raw secret never reaches the election. We compute
    them inline here only to make the demo self-contained."""

    def __init__(self, election_id: bytes, eligible_secrets):
        self.election_id = election_id
        self._index_of = {}
        leaves = []
        for i, s in enumerate(eligible_secrets):
            leaves.append(commitment(s))
            self._index_of[s] = i
        self.tree = MerkleTree(leaves)
        self.used_nullifiers = set()
        self.tally = {}

    def cast_vote(self, voter_secret: bytes, choice: str, where: str = "") -> str:
        loc = f" (from {where})" if where else ""

        # 1) ELIGIBILITY - prove the voter's commitment is in the tree.
        idx = self._index_of.get(voter_secret)
        if idx is None:
            return "REJECTED - not on the eligible roll" + loc
        leaf = commitment(voter_secret)
        if not MerkleTree.verify(leaf, self.tree.proof(idx), self.tree.root):
            return "REJECTED - membership proof failed" + loc

        # 2) ONE-VOTE - the election-scoped nullifier.
        n = nullifier(voter_secret, self.election_id)
        if n in self.used_nullifiers:
            return "REJECTED - already voted this election" + loc + "  [nullifier already seen]"

        # 3) ACCEPT.
        self.used_nullifiers.add(n)
        self.tally[choice] = self.tally.get(choice, 0) + 1
        return "ACCEPTED - vote recorded" + loc


# ----------------------------------------------------------------------
# Demonstration
# ----------------------------------------------------------------------

def _line():
    print("=" * 68)


if __name__ == "__main__":
    _line()
    print("The Only Vote  -  eligible-voter tree + nullifier")
    _line()

    # Each eligible voter holds ONE secret (their one credential).
    alice = new_secret()
    bob = new_secret()
    carol = new_secret()
    mallory = new_secret()          # never enrolled -> ineligible

    election = Election(b"2026-general-president", [alice, bob, carol])
    print(f"\nEligible voters enrolled : 3")
    print(f"Eligible-set root        : {election.tree.root.hex()[:24]}...\n")

    print("1) A normal vote")
    print("    ", election.cast_vote(alice, "Candidate A", where="FL"))

    print("\n2) The SAME person votes again, same election, from a second home")
    print("   (the 'two homes' case: one secret -> one nullifier -> caught)")
    print("    ", election.cast_vote(alice, "Candidate B", where="PA"))

    print("\n3) A different eligible voter")
    print("    ", election.cast_vote(bob, "Candidate B", where="TX"))

    print("\n4) Someone not on the eligible roll")
    print("    ", election.cast_vote(mallory, "Candidate A", where="FL"))

    print(f"\nFinal tally              : {election.tally}")
    print(f"Distinct voters counted  : {len(election.used_nullifiers)}")

    # ------------------------------------------------------------------
    # The false-match dial - why entropy matters (the "No Vault" entropy wall).
    # If the nullifier space is too small, two DIFFERENT people can land on the
    # same value: a real, distinct voter wrongly rejected as a "duplicate."
    # We shrink the nullifier to N bits and measure the false-match rate.
    # ------------------------------------------------------------------
    print()
    _line()
    print("The false-match dial - why entropy matters")
    print("(too small a space wrongly rejects real, DISTINCT voters)")
    _line()

    TRIALS = 20000
    for bits in (12, 16, 24, 32, 48):
        seen, collisions = set(), 0
        for _ in range(TRIALS):
            value = int.from_bytes(nullifier(new_secret(), b"dial"), "big") % (1 << bits)
            if value in seen:
                collisions += 1
            else:
                seen.add(value)
        print(f"  space = 2^{bits:<2d}  ->  false-match rate over {TRIALS} voters: {collisions / TRIALS:7.3%}")

    print("\n  Takeaway: with enough bits the rate vanishes. This is exactly why")
    print("  the design keeps the biometric to a 1:1 local check and lets the")
    print("  residency layer carry uniqueness - sidestepping the entropy wall")
    print("  instead of fighting it. (See foundations.md and ARCHITECTURE.md.)")
    print()