Cowrie Research

zk-kit-incremental-binary-quin-tree-zero-leaf-snark-scalar-range-check-omission-near-miss-2022-03-09

13 min read

ZK-Kit Incremental Binary/Quin Tree Zero-Leaf SNARK_SCALAR_FIELD Range-Check Omission Near Miss (2022-03-09)

  • Name: ZK-Kit incremental binary/quin tree zero-leaf SNARK_SCALAR_FIELD range-check omission near miss
  • Date: 2022-03-09
  • Protocol: ZK-Kit incremental-merkle-tree.sol
  • Chain: Ethereum ecosystem
  • Category: public-input domain mismatch / Merkle zero-value initialization mismatch / verifier-level denial of service / library-level near miss
  • Loss: no theft was reported, but callers could initialize proof-backed trees with zero values outside the proving field, creating trees whose later verification or removal flows could revert once those zeroes appeared as proof siblings
  • Summary: In March 2022, PSE’s security team disclosed that ZK-Kit’s Solidity incremental Merkle tree libraries let callers initialize IncrementalBinaryTree and IncrementalQuinTree with any uint256 zero value even though downstream proof logic expected field-safe values below SNARK_SCALAR_FIELD. The vulnerable boundary was clean and familiar: Solidity accepted an unrestricted integer at tree-creation time, but later verifier-style logic required sibling nodes to satisfy < SNARK_SCALAR_FIELD. If an oversized zero value propagated into a Merkle path, functions such as verify() during remove() could revert, leaving the tree created but unable to participate soundly in the proof-backed flows that depended on it. The fix was one line in the right place: reject out-of-field zero values at initialization for both tree variants.
  • Trigger / entry point:
    • The issue centered on the init() functions in ZK-Kit’s Solidity tree libraries, especially IncrementalBinaryTree.init() and the matching IncrementalQuinTree.init() path patched in the same fix.
    • Those initializers accepted a caller-supplied uint256 zero leaf value with no check that it fit inside the SNARK scalar field.
    • Downstream verification logic later required Merkle proof siblings to satisfy proofSiblings[i] < SNARK_SCALAR_FIELD.
    • That meant the same tree value was treated as an unrestricted Solidity integer on entry and as a field element once proof verification paths ran.
  • Root cause:
    • The library exposed a proof-facing tree parameter as a raw uint256 API input without enforcing the proving system’s numeric domain at the caller boundary.
    • Zero values are not cosmetic defaults in incremental Merkle trees; they become actual path elements and therefore part of later proof verification semantics.
    • The verification side already knew that sibling nodes must be field-safe.
    • The initialization side failed to preserve that same invariant when the tree was first created.
    • As a result, the protocol could author Merkle trees whose stored default path values were valid Solidity state but invalid zk-facing inputs.
  • Failure path:
    1. A caller initializes an incremental binary or quin tree with zero >= SNARK_SCALAR_FIELD.
    2. The library accepts the value and stores it as the default zero node used to derive higher empty-tree nodes.
    3. The tree now exists onchain and may look healthy to application code that only checks depth or root bookkeeping.
    4. Later, a proof-backed flow such as verification during removal encounters one of those zero-derived path elements as a proofSibling.
    5. The verification logic enforces proofSiblings[i] < SNARK_SCALAR_FIELD and reverts because the tree was initialized with an out-of-field value.
    6. The result is a proof-backed tree that can be created but can fail once the proving / verification boundary actually uses its stored zero values.
  • What the attacker or failure needed to be true:
    • The application had to use ZK-Kit’s tree libraries in a context where tree nodes later crossed into zk verification semantics.
    • The caller had to be able to choose the tree’s initial zero value.
    • The initializer had to omit the scalar-field check.
    • Later verification or removal logic had to enforce field-domain safety on siblings or equivalent proof-path values.
    • Integrators had to assume that a successfully initialized tree was also safe for later zk-backed operations.
  • Technical anatomy worth remembering:
    • This was not a bad verifier or a broken hash function. The dangerous gap sat between tree initialization and later proof consumption.
    • The zero leaf matters because empty-tree defaults are not inert metadata; they are real Merkle-path material that reappears in proofs whenever empty branches are traversed.
    • In practical terms, one bad zero at initialization poisons the whole precomputed empty-branch ladder above it. The impossible value is not confined to one leaf slot; it is hashed upward into the library’s default-path state and can later surface as a sibling anywhere an empty branch is proven.
    • The issue is the Merkle-tree analogue of Semaphore’s groupId bug: the same value family crossed from a broad uint256 contract surface into a finite-field proof surface without a single canonical domain check.
    • The patch is useful evidence of the true invariant location. Rather than loosening verification, the fix moved the field check outward to init() so impossible trees could not be created in the first place.
    • The same fix was applied to both the binary and quin-tree libraries in the same patch series, which is a helpful reminder that proof-facing numeric invariants tend to be library-wide rather than function-local.
  • Representative contracts and artifacts:
    • Reported component: packages/incremental-merkle-tree.sol/contracts/IncrementalBinaryTree.sol
    • Same-fix sibling component: packages/incremental-merkle-tree.sol/contracts/IncrementalQuinTree.sol
    • Reported failure site: IncrementalBinaryTree.verify() when called from IncrementalBinaryTree.remove() with a proofSibling derived from the oversized zero value
    • Reported issue: GitHub issue zk-kit/zk-kit#23
    • Fix artifact: GitHub pull request zk-kit/zk-kit#24
    • Patched binary-tree guard: require(zero < SNARK_SCALAR_FIELD, "IncrementalBinaryTree: leaf must be < SNARK_SCALAR_FIELD")
    • Same-patch quin-tree guard: require(zero < SNARK_SCALAR_FIELD, "IncrementalBinaryTree: leaf must be < SNARK_SCALAR_FIELD")
    • Release bump shipped with the fix: @zk-kit/incremental-merkle-tree.sol 0.3.0 -> 0.3.1
  • Response / mitigation:
    • ZK-Kit merged a focused two-commit patch series on 2022-03-09 that added zero < SNARK_SCALAR_FIELD checks in both IncrementalBinaryTree.init() and IncrementalQuinTree.init(), then bumped @zk-kit/incremental-merkle-tree.sol to 0.3.1.
    • The mitigation strategy was the right one for this bug class: reject impossible proof-facing state at creation time rather than relying on deeper verifier paths to fail later.
    • The durable lesson is broader than validate this one constructor argument: empty-tree defaults, precomputed zero ladders, and helper-library initialization parameters are part of the proof surface and need the same field-domain discipline as explicit nullifiers or public inputs.

Pattern tags

  • public-input-domain-mismatch
  • proof-facing-field-domain-canonicalization-discipline
  • The decisive break was not verify() forgot one range check; it was init()` publishing empty-tree state that the later proof system would never accept as valid sibling material.
  • Tree successfully created and tree can later participate in proof-backed insert / remove / verify flows were treated as different truths even though applications would naturally read them as the same object-level guarantee.
  • Empty defaults were treated like harmless configuration even though one out-of-field zero value actually poisoned the entire precomputed zero ladder above it.

Three proof-object publication promotions this incident collapsed

  1. A tree-shaped object existed as application state at all

    • IncrementalBinaryTree.init() and IncrementalQuinTree.init() accepted a caller-supplied zero, stored it, and built the empty-node ladder above it.
    • At this point the protocol had only proved a tree object now exists with this default zero semantics.

  2. That created tree was promoted into canonical proof-usable tree truth

    • This was the decisive failure. The same zero family that init() accepted as an unrestricted Solidity uint256 was later expected to reappear as field-safe sibling material under < SNARK_SCALAR_FIELD.
    • Once an oversized zero seeded the empty-branch ladder, the library had already collapsed tree was published into tree is verifier-legal proof infrastructure even though later proof paths would reject the very default material the initializer had authored.

  3. That accepted created-tree truth still deserved live proof-backed workflow authority

    • Applications and integrators were still allowed to treat the created tree as real anonymous-action or proof-backed lifecycle infrastructure even though remove() / verify() could later revert when those zero-derived siblings surfaced.
    • The practical failure was not merely bad sibling later reverts; it was the library published a user-visible proof-backed object before the proving boundary had actually accepted its core default-path semantics.

Why the exploit worked

  • ZK-Kit split one proof-facing object across two incompatible numeric domains. init() accepted zero as an unrestricted Solidity uint256, while later proof-consumption paths treated the same family of values as finite-field elements that must satisfy < SNARK_SCALAR_FIELD.
  • The bug mattered because the supplied zero was not inert metadata. It seeded the empty-tree ladder, so an oversized initialization value could be hashed upward into many later sibling positions rather than staying confined to one leaf slot.
  • The verifier-side guard therefore did not fully protect the higher-level application invariant. By the time verify() reverted on an oversized sibling, the library had already authored a tree that looked valid to callers but was unusable for the proof-backed lifecycle it was supposed to support.
  • The patch location is the important clue about the real security boundary: the fix did not loosen verify() or add a special case in remove(); it moved the field-domain check outward to init() so impossible trees could never become live state.
  • The sharper reusable lesson is created onchain != usable in the proof system unless proof-facing defaults, cached empty values, and initialization parameters are canonicalized before the object exists.

Detection and audit pivots

  • Trace every constructor or init() parameter that can later appear as Merkle siblings, public inputs, witness material, cached empty nodes, or nullifier/domain values. If the first field-domain check only appears deep inside proof verification, the protocol may already be authoring dead-on-arrival proof state.
  • Treat empty-tree defaults and precomputed zero ladders as part of the proof surface, not as convenience constants. Any value reused automatically across many future proof paths deserves the same field-bound checks as explicit user-submitted proof inputs.
  • Build lifecycle tests, not just local verifier tests: create tree with oversized zero -> insert/use/remove/verify later. The important property is not merely verify rejects bad siblings; it is a successfully initialized proof-backed tree remains proof-usable under its advertised lifecycle.
  • Centralize proof-facing range checks at the earliest shared creation primitive. ZK-Kit’s one-line guard in both IncrementalBinaryTree.init() and IncrementalQuinTree.init() is the healthy pattern because downstream callers and extensions should not have to remember the field bound themselves.
  • Be suspicious whenever an API says uint256 but the surrounding proving system really means field element. Merkle-tree helpers, poll identifiers, nullifiers, scopes, zero values, and other setup constants often become proof objects long after the call site that first accepted them.

Why this incident matters

  • It is a strong library-level exemplar for the proofs/verifiers corpus because it shows how zk bugs often begin before any proof is generated: state can be authored with values the proving system will never soundly accept.
  • It broadens the public-input domain mismatch pattern beyond nullifiers and external nullifiers into Merkle-tree initialization, which is a common hidden dependency in anonymous-action systems.
  • It also preserves an integration lesson that shows up repeatedly in proof-heavy stacks: when a library says uint256, the real security object may still be field element, and the API should enforce that early.

Failure-prevention checklist

  • Enforce field-domain bounds at object creation, not only at later proof verification. If zero will ever become a Merkle sibling or cached empty node, reject out-of-field values before the tree exists.
  • Treat empty-tree defaults as proof material, not configuration trivia. Reviewers should ask whether every precomputed zero node, cached branch value, or helper-derived default can legally appear inside the proving system.
  • Make initialized tree imply later proof-usable tree. A successful init() should already guarantee that subsequent insert(), verify(), and remove() paths will not discover impossible state the initializer was allowed to publish.
  • Reuse one shared field-guard helper across binary-tree, quin-tree, and wrapper-level creation surfaces so proof-domain checks do not drift between sibling libraries.
  • Add lifecycle tests that start from edge-case creation values and continue through ordinary proof-backed flows. Reject bad sibling in verify() is weaker than bad zero can never seed live tree state at all.
  • Audit every proof-facing uint256 for hidden semantic narrowing. If an API parameter eventually becomes a Merkle path element, nullifier, scope, or public input, document and enforce that narrower semantic type up front.
  • Keep library release notes and version bumps explicit when the fix changes object-creation validity. Integrators need to know that upgrading from 0.3.0 to 0.3.1 is not cosmetic; it closes a tree-initialization invariant hole.
  • During review, trace which automatically reused values can poison many later proof paths at once. One oversized zero mattered because it seeded the whole empty-branch ladder, not because it sat in one isolated slot.

Audit prompts

  • Which caller-supplied initialization values can later reappear as Merkle siblings, cached empty nodes, public inputs, or witness-side path elements?
  • Does tree creation already prove those values are field-safe, or does the first real domain check appear only when proof verification or removal runs later?
  • Can the library publish a tree that looks healthy to application code but is dead on arrival for its intended proof-backed lifecycle?
  • Are binary-tree, quin-tree, factory, and wrapper code paths all enforcing the same field-domain invariant, or did one sibling surface quietly widen back to raw uint256 semantics?
  • If one default value is out of field, how far does that contamination spread through precomputed branch state, cached zeros, emitted roots, or downstream integration assumptions?
  • Do tests exercise create with bad zero -> attempt later verify/remove, not just verify rejects bad proofSibling in isolation?
  • When integrators wrap this library, what single helper or type discipline prevents them from reintroducing the same out-of-field initialization bug at a higher layer?
  • If the proof system changed fields or tree hashing assumptions tomorrow, where would reviewers re-establish that stored zero values and later verifier expectations still describe the same object?

Lessons that should already be standard

  • Empty defaults are not harmless metadata in proof-backed Merkle systems. They are future proof-path material and should be reviewed like any other public input or nullifier.
  • Verifier rejects impossible values later is not enough once the protocol can already publish impossible proof-backed state now.
  • Library initialization is part of the zk security boundary. A bad init() can be as real a proof bug as a bad verifier because it decides which objects are allowed to exist at all.
  • One caller-facing uint256 often hides a stricter semantic type. If reviewers cannot name that narrower type explicitly, the API is probably too loose.
  • The healthiest fix is usually outward, not deeper: push the field check to object creation rather than teaching later consumers to survive poisoned state.
  • Precomputed ladders and cached defaults magnify small admission mistakes. One out-of-field seed can turn into many future proof failures because helper state is reused automatically.
  • A proof-backed object should have one truth from birth: if it can be created, it should already satisfy the numeric domain the later proof system expects.

Internal linkages

Control surface

Graph View

Backlinks