Merkle commitments for the 11chooses.siv.org voter files

11chooses-voterfile-commitments.ts

/* Commmitments

novRowsTree: { // Active Voters as of Nov 20th, 2025
  root: 'fdcd59ab3145ab7fc9dd112680cf0a24052de68c',
  depth: 16,
  length: 62228,
},
authTokensTree: { // Auth Tokens ("Voter Codes") generated for this vote
  root: 'd4cedbcdb40851044b5cfe3928d7389fa8a4ae2a',
  depth: 16,
  length: 62228,
},
recipientsWithoutWithheldsTree: { // Mailmerge data for postal letters
  root: '3e1cd6f4aff043d0e1b0ffe613bce6f5b907c892',
  depth: 15,
  length: 27092,
},
recipientsWithWithheldsTree: { // Mailmerge data for postal letters including withheld voters
  root: '56efb09d31d0ab7daeee3d37c28d7bdbf41f3ae6',
  depth: 13,
  length: 8016,
} */

import { buildMerkleTree } from './merkle-tree'
import { readFileSync } from 'fs'
import { novRows } from '../nov-dataset'
import authTokens from '../auth-tokens.json'
import { join } from 'path'

const recipientsWithWithhelds = readFileSync(
  join(__dirname, '../recipients-with-withhelds.csv'),
  'utf8'
).split('\n')
const recipientsWithoutWithhelds = readFileSync(
  join(__dirname, '../recipients-without-withhelds.csv'),
  'utf8'
).split('\n')

const novRowsTree = buildMerkleTree(novRows)
const authTokensTree = buildMerkleTree(Object.entries(authTokens))
const recipientsWithWithheldsTree = buildMerkleTree(recipientsWithWithhelds)
const recipientsWithoutWithheldsTree = buildMerkleTree(
  recipientsWithoutWithhelds
)
console.log({
  novRowsTree,
  authTokensTree,
  recipientsWithWithheldsTree,
  recipientsWithoutWithheldsTree,
})

merkle-tree.test.ts

import { describe, expect, test } from 'bun:test'

import { buildMerkleTree, verifyInclusionProof } from './merkle-tree'

const example = ['foo', 'bar', 'baz']
const tree = buildMerkleTree(example)

describe('merkle tree', () => {
  test('should produce a root hash, to be shared publicly', () => {
    expect(typeof tree.root).toBe('string')

    // And an integer depth
    const expectedDepth = Math.ceil(Math.log2(example.length))
    expect(tree.depth).toBe(expectedDepth)
    expect(Math.floor(tree.depth)).toBe(tree.depth)
  })

  test('hashes should be long enough to prevent forged proofs', () => {
    const minimumSecurityLevel = 80 // 2^n attempts, 2^80 ~= $1 trillion dollars to break

    // hashes are hexadecimal, base 16 = 2^4
    // but since these are commitments', we worry about collisions, so each character provides 2 bits of collision resistance
    const hexNeeded = minimumSecurityLevel / 2

    expect(tree.root.length).toBeGreaterThanOrEqual(hexNeeded)
  })

  test('should provide inclusion proofs when requested', () => {
    const inclusionProof = tree.getInclusionProof(2)
    // console.log({ inclusionProof })
    expect(inclusionProof).not.toBe(null)
    expect(inclusionProof.item).toBe('baz')
    expect(inclusionProof.index).toBe(2)
    expect(Array.isArray(inclusionProof.path)).toBe(true)
  })

  test('should accept valid inclusion proofs', () => {
    // Test proof for each item in the tree
    for (let i = 0; i < example.length; i++) {
      const proof = tree.getInclusionProof(i)
      const isValid = verifyInclusionProof(tree.root, proof)
      expect(isValid).toBe(true)
    }
  })

  test('should reject invalid inclusion proofs', () => {
    const validProof = tree.getInclusionProof(0)

    // Test with wrong root
    const wrongRoot = '0'.repeat(40)
    expect(verifyInclusionProof(wrongRoot, validProof)).toBe(false)

    // Test with wrong item
    const wrongItemProof = {
      ...validProof,
      item: 'wrong-item',
    }
    expect(verifyInclusionProof(tree.root, wrongItemProof)).toBe(false)

    // Test with wrong index
    const wrongIndexProof = {
      ...validProof,
      index: validProof.index === 0 ? 1 : 0,
    }
    expect(verifyInclusionProof(tree.root, wrongIndexProof)).toBe(false)

    // Test with tampered path (empty path)
    const emptyPathProof = {
      ...validProof,
      path: [],
    }
    expect(verifyInclusionProof(tree.root, emptyPathProof)).toBe(false)

    // Test with tampered path (wrong hash)
    const tamperedPathProof = {
      ...validProof,
      path: ['0'.repeat(40)],
    }
    expect(verifyInclusionProof(tree.root, tamperedPathProof)).toBe(false)

    // Test with wrong length (duplicate-entry attack prevention)
    const wrongLengthProof = {
      ...validProof,
      treeLength: validProof.treeLength + 1,
    }
    expect(verifyInclusionProof(tree.root, wrongLengthProof)).toBe(false)

    // Test with index out of bounds for committed length
    const outOfBoundsProof = { ...validProof, index: validProof.treeLength }
    expect(verifyInclusionProof(tree.root, outOfBoundsProof)).toBe(false)
  })

  test('should prevent duplicate-entry attacks by committing to array length', () => {
    // Create a tree with duplicate items
    const itemsWithDuplicates = ['foo', 'bar', 'foo']
    const treeWithDupes = buildMerkleTree(itemsWithDuplicates)

    // Get a proof for the first 'foo' (index 0)
    const proofForFirstFoo = treeWithDupes.getInclusionProof(0)

    // Try to use this proof with a wrong length (simulating using it in a smaller tree)
    const tamperedProof = {
      ...proofForFirstFoo,
      treeLength: 2, // Claiming the tree only has 2 items
    }
    expect(verifyInclusionProof(treeWithDupes.root, tamperedProof)).toBe(false)

    // Try to use it with a wrong length (larger tree)
    const tamperedProof2 = {
      ...proofForFirstFoo,
      treeLength: 4,
    }
    expect(verifyInclusionProof(treeWithDupes.root, tamperedProof2)).toBe(false)
  })

  test('should enforce order - proofs are position-specific', () => {
    // Create tree with ['a', 'b', 'c']
    const tree1 = buildMerkleTree(['a', 'b', 'c'])
    const proofForA = tree1.getInclusionProof(0) // 'a' at index 0

    // Create tree with ['b', 'a', 'c'] - same items, different order
    const tree2 = buildMerkleTree(['b', 'a', 'c'])

    // Root hashes should be different
    expect(tree1.root).not.toBe(tree2.root)

    // Proof from tree1 should NOT validate against tree2's root
    expect(verifyInclusionProof(tree2.root, proofForA)).toBe(false)

    // Proof from tree1 should validate against tree1's root
    expect(verifyInclusionProof(tree1.root, proofForA)).toBe(true)

    // Get proof for 'a' from tree2 (at index 1)
    const proofForAInTree2 = tree2.getInclusionProof(1)

    // This proof should validate against tree2's root
    expect(verifyInclusionProof(tree2.root, proofForAInTree2)).toBe(true)

    // But NOT against tree1's root
    expect(verifyInclusionProof(tree1.root, proofForAInTree2)).toBe(false)
  })
})

merkle-tree.ts

import crypto from 'crypto'

type InclusionProof<I> = {
  item: I
  index: number
  path: string[]
  root: string
  treeLength: number
}
type Tree<I> = {
  root: string
  depth: number
  length: number
  getInclusionProof: (index: number) => InclusionProof<I>
}

const sha256Hash = <I>(item: I) =>
  crypto.hash('SHA-256', JSON.stringify(item)).slice(0, 40)

/** Traverse up the merkle tree from a leaf index, calling a callback at each level.
 *  The callback receives: (isLeft, level, currentIndex) */
function traverseUpTree(
  startIndex: number,
  depth: number,
  callback: (isLeft: boolean, level: number, currentIndex: number) => void
): void {
  let currentIndex = startIndex
  for (let level = 0; level < depth; level++) {
    const isLeft = currentIndex % 2 === 0
    callback(isLeft, level, currentIndex)
    currentIndex = Math.floor(currentIndex / 2)
  }
}

/** Given an array of items, build a binary tree, hashing each step up,
 *  for a single root hash and fast inclusion proofs */
export function buildMerkleTree<I>(items: I[]): Tree<I> {
  if (items.length === 0) throw new Error('Bad input: Empty array')

  // Hash each of the inputs into leaf nodes
  let currentLevel = items.map(sha256Hash)
  const levels: string[][] = [currentLevel] // Store all levels for proof generation

  // Build tree level by level until we reach the root
  while (currentLevel.length > 1) {
    const nextLevel: string[] = []
    // Pair up nodes and hash them together
    for (let i = 0; i < currentLevel.length; i += 2) {
      const left = currentLevel[i]
      const right =
        i + 1 < currentLevel.length ? currentLevel[i + 1] : currentLevel[i] // Duplicate last node if odd
      const combined = sha256Hash(left + right)
      nextLevel.push(combined)
    }
    levels.push(nextLevel)
    currentLevel = nextLevel
  }

  const merkleRoot = currentLevel[0]
  const depth = levels.length - 1

  // Commit to the array length in the root hash to prevent duplicate-entry attacks
  const root = sha256Hash(merkleRoot + items.length.toString())

  const getInclusionProof = (index: number): InclusionProof<I> => {
    if (index < 0 || index >= items.length)
      throw new Error(`No index ${index} for array of length ${items.length}`)

    const path: string[] = []

    // Traverse up the tree, collecting sibling hashes at each level
    traverseUpTree(index, depth, (isLeft, level, currentIndex) => {
      const currentLevelHashes = levels[level]
      const siblingIndex = isLeft ? currentIndex + 1 : currentIndex - 1

      // If sibling exists at this level, add it to path
      // Otherwise, duplicate the current node (for odd-length levels)
      path.push(
        currentLevelHashes[
          siblingIndex < currentLevelHashes.length ? siblingIndex : currentIndex
        ]
      )
    })

    return { item: items[index], index, path, root, treeLength: items.length }
  }

  return { root, getInclusionProof, depth, length: items.length }
}

/** Verify that an inclusion proof is valid for a given root hash and tree length */
export function verifyInclusionProof<I>(
  root: string,
  proof: InclusionProof<I>
): boolean {
  // Verify index is within bounds of committed length
  if (proof.index < 0 || proof.index >= proof.treeLength) return false

  // Hash the item to get the leaf hash
  let currentHash = sha256Hash(proof.item)

  // Reconstruct the merkle root using the proof path
  let pathIndex = 0
  traverseUpTree(proof.index, proof.path.length, (isLeft) => {
    const siblingHash = proof.path[pathIndex++]
    // Combine hashes: left hash first, then right hash
    currentHash = sha256Hash(
      isLeft ? currentHash + siblingHash : siblingHash + currentHash
    )
  })

  // Reconstruct the final root by hashing merkle root + length
  const reconstructedRoot = sha256Hash(
    currentHash + proof.treeLength.toString()
  )

  return reconstructedRoot === root
}

Explanation shared with teammates:

I've made and published cryptographic "commitments" for our:

• 62k active-voters file
• 62k auth tokens generated
• and 35k rows of data for the letter mailmerges

https://gist.github.com/dsernst/514bbd834676d771470a773e1abbf592

It's very cool how it works ("merkle hash trees") but no need to worry about it if you aren't interested.

The high-level point is that this allows us to prove-if-challenged, in an unforgeable way, the specific Voter Roll files we've used. But this also enables the ability to prove individual lines, in a privacy-protecting way, without needing to reveal the whole file. If those challenged lines are chosen using random sampling, proving just a few dozen of them is enough to show overwhelming odds the whole thing is legitimate.

No further action needed now. Just a heads up, in case it becomes useful later.

Timestamped repo file commit-to-datafiles.ts — which includes the merkle roots — to bitcoin blockchain, using opentimestamps.org