{"version":3,"sources":["../src/core/always-hash-tree.ts"],"names":["PoseidonM31"],"mappings":";;;;;;;;;;;AAuCO,IAAM,yBAAA,GAA4B;AAMlC,IAAM,qBAAA,GAAwB;AAkC9B,IAAM,uBAAN,MAA2B;AAAA,EACxB,SAAmB,EAAC;AAAA,EACpB,KAAA,uBAAY,GAAA,EAAoB;AAAA;AAAA,EAEhC,QAAA,GAA4B,IAAA;AAAA,EAC5B,UAAA,GAA4B,IAAA;AAAA,EAE3B,KAAA;AAAA,EACA,MAAA;AAAA,EAET,WAAA,CACE,KAAA,GAAgB,yBAAA,EAChB,MAAA,EACA;AACA,IAAA,IAAI,CAAC,OAAO,SAAA,CAAU,KAAK,KAAK,KAAA,GAAQ,CAAA,IAAK,QAAQ,qBAAA,EAAuB;AAC1E,MAAA,MAAM,IAAI,KAAA;AAAA,QACR,CAAA,sDAAA,EAAyD,qBAAqB,CAAA,OAAA,EAAU,KAAK,CAAA;AAAA,OAC/F;AAAA,IACF;AACA,IAAA,IAAA,CAAK,KAAA,GAAQ,KAAA;AACb,IAAA,IAAA,CAAK,MAAA,GAAS,MAAA,IAAU,IAAIA,6BAAA,EAAY;AAAA,EAC1C;AAAA;AAAA,EAGA,IAAI,QAAA,GAAmB;AAGrB,IAAA,OAAO,KAAK,IAAA,CAAK,KAAA;AAAA,EACnB;AAAA;AAAA,EAGA,IAAI,IAAA,GAAe;AACjB,IAAA,OAAO,KAAK,MAAA,CAAO,MAAA;AAAA,EACrB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,OAAO,IAAA,EAAsB;AAC3B,IAAA,IAAI,SAAS,EAAA,EAAI;AACf,MAAA,MAAM,IAAI,MAAM,+EAA+E,CAAA;AAAA,IACjG;AACA,IAAA,IAAI,IAAA,CAAK,MAAA,CAAO,MAAA,IAAU,IAAA,CAAK,QAAA,EAAU;AACvC,MAAA,MAAM,IAAI,KAAA;AAAA,QACR,CAAA,wCAAA,EAA2C,IAAA,CAAK,QAAQ,CAAA,iBAAA,EAAoB,KAAK,KAAK,CAAA,CAAA;AAAA,OACxF;AAAA,IACF;AACA,IAAA,MAAM,KAAA,GAAQ,KAAK,MAAA,CAAO,MAAA;AAC1B,IAAA,IAAA,CAAK,MAAA,CAAO,KAAK,IAAI,CAAA;AACrB,IAAA,IAAA,CAAK,UAAA,GAAa,IAAA;AAClB,IAAA,IAAA,CAAK,MAAM,KAAA,EAAM;AACjB,IAAA,OAAO,KAAA;AAAA,EACT;AAAA;AAAA,EAGA,QAAQ,IAAA,EAAsB;AAC5B,IAAA,OAAO,IAAA,CAAK,MAAA,CAAO,OAAA,CAAQ,IAAI,CAAA;AAAA,EACjC;AAAA;AAAA,EAGA,IAAI,IAAA,EAAuB;AACzB,IAAA,OAAO,IAAA,CAAK,MAAA,CAAO,QAAA,CAAS,IAAI,CAAA;AAAA,EAClC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,MAAM,OAAA,GAA2B;AAC/B,IAAA,IAAI,IAAA,CAAK,UAAA,KAAe,IAAA,EAAM,OAAO,IAAA,CAAK,UAAA;AAC1C,IAAA,MAAM,OAAO,MAAM,IAAA,CAAK,WAAA,CAAY,IAAA,CAAK,OAAO,CAAC,CAAA;AACjD,IAAA,IAAA,CAAK,UAAA,GAAa,IAAA;AAClB,IAAA,OAAO,IAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,MAAM,SAAS,KAAA,EAA+C;AAC5D,IAAA,IAAI,CAAC,MAAA,CAAO,SAAA,CAAU,KAAK,CAAA,IAAK,QAAQ,CAAA,IAAK,KAAA,IAAS,IAAA,CAAK,MAAA,CAAO,MAAA,EAAQ;AACxE,MAAA,MAAM,IAAI,KAAA;AAAA,QACR,CAAA,iCAAA,EAAoC,KAAK,CAAA,sBAAA,EAAyB,IAAA,CAAK,OAAO,MAAM,CAAA,CAAA;AAAA,OACtF;AAAA,IACF;AAEA,IAAA,MAAM,eAAyB,EAAC;AAChC,IAAA,MAAM,cAAwB,EAAC;AAC/B,IAAA,IAAI,YAAA,GAAe,KAAA;AAEnB,IAAA,KAAA,IAAS,KAAA,GAAQ,CAAA,EAAG,KAAA,GAAQ,IAAA,CAAK,OAAO,KAAA,EAAA,EAAS;AAC/C,MAAA,MAAM,eAAe,YAAA,GAAe,CAAA;AACpC,MAAA,MAAM,MAAA,GAAS,eAAe,CAAA,KAAM,CAAA;AACpC,MAAA,MAAM,OAAA,GAAU,MAAM,IAAA,CAAK,WAAA,CAAY,OAAO,YAAY,CAAA;AAC1D,MAAA,YAAA,CAAa,KAAK,OAAO,CAAA;AACzB,MAAA,WAAA,CAAY,IAAA,CAAK,MAAA,GAAS,EAAA,GAAK,EAAE,CAAA;AACjC,MAAA,YAAA,GAAe,YAAA,KAAiB,CAAA;AAAA,IAClC;AAEA,IAAA,OAAO;AAAA,MACL,YAAA;AAAA,MACA,WAAA;AAAA,MACA,SAAA,EAAW,KAAA;AAAA,MACX,IAAA,EAAM,MAAM,IAAA,CAAK,OAAA,EAAQ;AAAA,MACzB,OAAO,IAAA,CAAK;AAAA,KACd;AAAA,EACF;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAWA,MAAM,mBAAmB,KAAA,EAAgC;AACvD,IAAA,IAAI,CAAC,OAAO,SAAA,CAAU,KAAK,KAAK,KAAA,GAAQ,CAAA,IAAK,KAAA,GAAQ,IAAA,CAAK,KAAA,EAAO;AAC/D,MAAA,MAAM,IAAI,KAAA;AAAA,QACR,CAAA,gCAAA,EAAmC,KAAK,CAAA,kBAAA,EAAqB,IAAA,CAAK,KAAK,CAAA,CAAA;AAAA,OACzE;AAAA,IACF;AACA,IAAA,MAAM,KAAK,cAAA,EAAe;AAC1B,IAAA,OAAO,IAAA,CAAK,SAAU,KAAK,CAAA;AAAA,EAC7B;AAAA;AAAA;AAAA;AAAA,EAMA,MAAc,cAAA,GAAgC;AAC5C,IAAA,IAAI,IAAA,CAAK,aAAa,IAAA,EAAM;AAC5B,IAAA,MAAM,GAAA,GAAgB,IAAI,KAAA,CAAM,IAAA,CAAK,QAAQ,CAAC,CAAA;AAC9C,IAAA,GAAA,CAAI,CAAC,CAAA,GAAI,EAAA;AACT,IAAA,KAAA,IAAS,CAAA,GAAI,CAAA,EAAG,CAAA,IAAK,IAAA,CAAK,OAAO,CAAA,EAAA,EAAK;AACpC,MAAA,MAAM,IAAA,GAAO,GAAA,CAAI,CAAA,GAAI,CAAC,CAAA;AACtB,MAAA,GAAA,CAAI,CAAC,CAAA,GAAI,MAAM,KAAK,MAAA,CAAO,KAAA,CAAM,MAAM,IAAI,CAAA;AAAA,IAC7C;AACA,IAAA,IAAA,CAAK,QAAA,GAAW,GAAA;AAAA,EAClB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQQ,cAAA,CAAe,OAAe,KAAA,EAAwB;AAI5D,IAAA,MAAM,YAAA,GAAe,SAAS,CAAA,IAAK,KAAA,CAAA;AACnC,IAAA,OAAO,YAAA,IAAgB,KAAK,MAAA,CAAO,MAAA;AAAA,EACrC;AAAA,EAEA,MAAc,WAAA,CAAY,KAAA,EAAe,KAAA,EAAgC;AACvE,IAAA,MAAM,GAAA,GAAM,CAAA,EAAG,KAAK,CAAA,CAAA,EAAI,KAAK,CAAA,CAAA;AAC7B,IAAA,MAAM,MAAA,GAAS,IAAA,CAAK,KAAA,CAAM,GAAA,CAAI,GAAG,CAAA;AACjC,IAAA,IAAI,MAAA,KAAW,QAAW,OAAO,MAAA;AAEjC,IAAA,IAAI,IAAA;AACJ,IAAA,IAAI,IAAA,CAAK,cAAA,CAAe,KAAA,EAAO,KAAK,CAAA,EAAG;AAErC,MAAA,MAAM,KAAK,cAAA,EAAe;AAC1B,MAAA,IAAA,GAAO,IAAA,CAAK,SAAU,KAAK,CAAA;AAAA,IAC7B,CAAA,MAAA,IAAW,UAAU,CAAA,EAAG;AACtB,MAAA,IAAA,GAAO,IAAA,CAAK,OAAO,KAAK,CAAA;AAAA,IAC1B,CAAA,MAAO;AACL,MAAA,MAAM,OAAO,MAAM,IAAA,CAAK,YAAY,KAAA,GAAQ,CAAA,EAAG,QAAQ,CAAC,CAAA;AACxD,MAAA,MAAM,KAAA,GAAQ,MAAM,IAAA,CAAK,WAAA,CAAY,QAAQ,CAAA,EAAG,KAAA,GAAQ,IAAI,CAAC,CAAA;AAC7D,MAAA,IAAA,GAAO,MAAM,IAAA,CAAK,MAAA,CAAO,KAAA,CAAM,MAAM,KAAK,CAAA;AAAA,IAC5C;AACA,IAAA,IAAA,CAAK,KAAA,CAAM,GAAA,CAAI,GAAA,EAAK,IAAI,CAAA;AACxB,IAAA,OAAO,IAAA;AAAA,EACT;AACF;AAGA,eAAsB,yBAAA,CACpB,MAAA,EACA,KAAA,GAAgB,yBAAA,EAChB,MAAA,EAC+B;AAC/B,EAAA,MAAM,IAAA,GAAO,IAAI,oBAAA,CAAqB,KAAA,EAAO,MAAM,CAAA;AACnD,EAAA,KAAA,MAAW,IAAA,IAAQ,MAAA,EAAQ,IAAA,CAAK,MAAA,CAAO,IAAI,CAAA;AAE3C,EAAA,MAAM,KAAK,OAAA,EAAQ;AACnB,EAAA,OAAO,IAAA;AACT","file":"index.cjs","sourcesContent":["/**\n * AlwaysHashMerkleTree — fixed-depth Merkle tree under always-hash\n * semantics. Every internal node is `hashFn.hash2(left, right)`\n * regardless of whether either child is empty; empty subtrees are\n * represented by precomputed zero-subtree roots `ZSR(k)`.\n *\n * Use this for STARK-side ASP / state trees that the in-trace\n * Poseidon31 AIR consumes. The AIR has no propagation primitive\n * (every level hashes), so a tree built under always-hash semantics\n * is the only model where every member's depth-D proof verifies\n * against a single shared root. The LeanIMT-based [`MerkleTree`] is\n * still the right choice for SNARK-side trees whose verifying\n * circuit explicitly mirrors LeanIMT propagation.\n *\n * Cross-class relationship to [`padLeanIMTProofToDepth`]:\n *\n * - The padding helper is a *transitional* compatibility shim: it\n * takes a LeanIMT proof and produces a self-consistent\n * fixed-depth proof, but in sparse trees different leaves'\n * proofs land on different roots. Useful for verifying single-\n * membership end-to-end against a leaf-specific root, not for\n * publishing a shared `pub_asp_root`.\n * - This class is the *operational* fix: insert leaves once, get\n * a single root, get fixed-depth proofs that all verify against\n * it. This is what the asp-whitelist's STARK-side tree should\n * use, and what the SDK + zkdemo prover wiring should consume.\n *\n * @see padLeanIMTProofToDepth — compatibility shim for LeanIMT proofs.\n * @see verifyMerklePath — sync always-hash verifier in the\n * Poseidon31 module that mirrors the in-trace AIR.\n */\n\nimport type { IHashFunction } from './hash/interface.js'\nimport { PoseidonM31 } from './hash/poseidon-m31.js'\n\n/**\n * Default depth for ASP-side STARK trees, matching the in-trace AIR's\n * `ASP_TREE_DEPTH = 20`.\n */\nexport const DEFAULT_ALWAYS_HASH_DEPTH = 20\n\n/**\n * Maximum supported depth. The tree's leaf capacity is `2^depth`, so\n * deeper trees are mostly a memory/proof-size concern.\n */\nexport const MAX_ALWAYS_HASH_DEPTH = 32\n\n/**\n * Proof shape returned by [`AlwaysHashMerkleTree.getProof`].\n *\n * `pathIndices` are `bigint[]` so the result can be fed straight into\n * the Poseidon31 [`verifyMerklePath`] without conversion. Length of\n * both `pathElements` and `pathIndices` is exactly the tree's `depth`.\n */\nexport interface AlwaysHashMerkleProof {\n /** Sibling at each level. Length equals the tree's `depth`. */\n pathElements: bigint[]\n /** Side bit at each level (0n = current is left, 1n = right). */\n pathIndices: bigint[]\n /** Index of the leaf being proven (0-based). */\n leafIndex: number\n /** Tree root the proof verifies against. */\n root: bigint\n /** Fixed depth — pinned alongside the proof so verifiers don't guess. */\n depth: number\n}\n\n/**\n * Fixed-depth Merkle tree where every internal node hashes its two\n * children regardless of fill. Empty subtrees are represented by\n * precomputed zero-subtree roots, and every member's proof verifies\n * against the same root.\n *\n * Capacity is `2^depth`. Inserting beyond capacity throws.\n *\n * Hash function defaults to Poseidon-M31 (matches the STARK AIR). Any\n * `IHashFunction` works in principle, but cross-leaf agreement only\n * matters for AIR-aligned trees today.\n */\nexport class AlwaysHashMerkleTree {\n private leaves: bigint[] = []\n private nodes = new Map()\n /** ZSR cache: `zsr[k]` is the root of an entirely-empty subtree of depth `k`. */\n private zsrCache: bigint[] | null = null\n private cachedRoot: bigint | null = null\n\n readonly depth: number\n readonly hashFn: IHashFunction\n\n constructor(\n depth: number = DEFAULT_ALWAYS_HASH_DEPTH,\n hashFn?: IHashFunction\n ) {\n if (!Number.isInteger(depth) || depth < 1 || depth > MAX_ALWAYS_HASH_DEPTH) {\n throw new Error(\n `AlwaysHashMerkleTree: depth must be an integer in [1, ${MAX_ALWAYS_HASH_DEPTH}], got ${depth}`\n )\n }\n this.depth = depth\n this.hashFn = hashFn ?? new PoseidonM31()\n }\n\n /** Maximum number of leaves the tree can hold (`2^depth`). */\n get capacity(): number {\n // `depth ≤ 32` guarantees `2^depth ≤ 2^32`, well within JS's safe\n // integer range.\n return 2 ** this.depth\n }\n\n /** Number of leaves currently inserted. */\n get size(): number {\n return this.leaves.length\n }\n\n /**\n * Append a leaf and return its index. Rejects `0n` because the\n * tree uses `0n` as the empty-leaf sentinel that drives ZSR(0).\n * Rejects when at capacity.\n */\n insert(leaf: bigint): number {\n if (leaf === 0n) {\n throw new Error('AlwaysHashMerkleTree: leaf cannot be zero (collides with empty-leaf sentinel)')\n }\n if (this.leaves.length >= this.capacity) {\n throw new Error(\n `AlwaysHashMerkleTree: tree at capacity (${this.capacity} leaves at depth ${this.depth})`\n )\n }\n const index = this.leaves.length\n this.leaves.push(leaf)\n this.cachedRoot = null\n this.nodes.clear()\n return index\n }\n\n /** Index of `leaf` in insertion order, or `-1` if absent. */\n indexOf(leaf: bigint): number {\n return this.leaves.indexOf(leaf)\n }\n\n /** Whether `leaf` was inserted. */\n has(leaf: bigint): boolean {\n return this.leaves.includes(leaf)\n }\n\n /**\n * Compute (or return cached) root. Always exactly one value per\n * tree state — the headline cross-leaf-agreement property holds by\n * construction.\n */\n async getRoot(): Promise {\n if (this.cachedRoot !== null) return this.cachedRoot\n const root = await this.getNodeHash(this.depth, 0)\n this.cachedRoot = root\n return root\n }\n\n /**\n * Build a depth-D proof for the leaf at `index`. The returned\n * `pathElements` / `pathIndices` are length `this.depth`, and\n * `verifyMerklePath(leaf, pathElements, pathIndices) === root`\n * holds for every leaf in the tree.\n */\n async getProof(index: number): Promise {\n if (!Number.isInteger(index) || index < 0 || index >= this.leaves.length) {\n throw new Error(\n `AlwaysHashMerkleTree: leaf index ${index} out of bounds (size: ${this.leaves.length})`\n )\n }\n\n const pathElements: bigint[] = []\n const pathIndices: bigint[] = []\n let currentIndex = index\n\n for (let level = 0; level < this.depth; level++) {\n const siblingIndex = currentIndex ^ 1\n const isLeft = currentIndex % 2 === 0\n const sibling = await this.getNodeHash(level, siblingIndex)\n pathElements.push(sibling)\n pathIndices.push(isLeft ? 0n : 1n)\n currentIndex = currentIndex >>> 1\n }\n\n return {\n pathElements,\n pathIndices,\n leafIndex: index,\n root: await this.getRoot(),\n depth: this.depth,\n }\n }\n\n /**\n * Zero-subtree root at `level` — the value an entirely-empty\n * subtree of depth `level` would hash to. Exposed because the\n * asp-whitelist's HTTP layer benefits from sharing these constants\n * with the on-chain side without re-hashing them per request.\n *\n * ZSR(0) = 0n\n * ZSR(k) = hashFn(ZSR(k-1), ZSR(k-1))\n */\n async getZeroSubtreeRoot(level: number): Promise {\n if (!Number.isInteger(level) || level < 0 || level > this.depth) {\n throw new Error(\n `AlwaysHashMerkleTree: ZSR level ${level} out of range [0, ${this.depth}]`\n )\n }\n await this.ensureZsrCache()\n return this.zsrCache![level]!\n }\n\n // -------------------------------------------------------------------------\n // Internals\n // -------------------------------------------------------------------------\n\n private async ensureZsrCache(): Promise {\n if (this.zsrCache !== null) return\n const zsr: bigint[] = new Array(this.depth + 1) as bigint[]\n zsr[0] = 0n\n for (let k = 1; k <= this.depth; k++) {\n const prev = zsr[k - 1]!\n zsr[k] = await this.hashFn.hash2(prev, prev)\n }\n this.zsrCache = zsr\n }\n\n /**\n * Returns true when the subtree rooted at `(level, index)` is\n * entirely empty — i.e. holds no real leaves. Lets `getNodeHash`\n * short-circuit to ZSR(level) without redundantly recomputing\n * empty-subtree hashes.\n */\n private isSubtreeEmpty(level: number, index: number): boolean {\n // The subtree at (level, index) covers leaf positions\n // [index << level, (index + 1) << level). It's empty iff every\n // position in that range is past the inserted leaves.\n const subtreeStart = index * (1 << level)\n return subtreeStart >= this.leaves.length\n }\n\n private async getNodeHash(level: number, index: number): Promise {\n const key = `${level}:${index}`\n const cached = this.nodes.get(key)\n if (cached !== undefined) return cached\n\n let hash: bigint\n if (this.isSubtreeEmpty(level, index)) {\n // Whole subtree empty → reuse precomputed ZSR.\n await this.ensureZsrCache()\n hash = this.zsrCache![level]!\n } else if (level === 0) {\n hash = this.leaves[index]!\n } else {\n const left = await this.getNodeHash(level - 1, index * 2)\n const right = await this.getNodeHash(level - 1, index * 2 + 1)\n hash = await this.hashFn.hash2(left, right)\n }\n this.nodes.set(key, hash)\n return hash\n }\n}\n\n/** Build an [`AlwaysHashMerkleTree`] from an array of leaves. */\nexport async function buildAlwaysHashMerkleTree(\n leaves: bigint[],\n depth: number = DEFAULT_ALWAYS_HASH_DEPTH,\n hashFn?: IHashFunction\n): Promise {\n const tree = new AlwaysHashMerkleTree(depth, hashFn)\n for (const leaf of leaves) tree.insert(leaf)\n // Eagerly seed the root cache so the first getProof call is cheap.\n await tree.getRoot()\n return tree\n}\n"]}