Cowrie Research

maci-1-0-processmessages-under-constrained-message-state-binding-coordinator-censorship-near-miss-2021-12-01

15 min read

MACI 1.0 ProcessMessages Under-Constrained Message/State Binding / Coordinator Censorship Near Miss (2021-12-01)

  • Name: MACI 1.0 ProcessMessages under-constrained message/state binding / coordinator censorship near miss
  • Date: 2021-12-01
  • Protocol: MACI 1.0
  • Chain: Ethereum ecosystem
  • Category: under-constrained circuit / message-state binding failure / coordinator censorship / vote invalidation near miss
  • Loss: no public theft was documented, but the bug let the MACI coordinator exclude otherwise valid votes from the proved tally by deliberately mismatching messages to the wrong state leaves during batch processing, directly undermining MACI’s advertised uncensorability and correct execution guarantees
  • Summary: MACI was designed so users posted encrypted votes onchain, a coordinator decrypted and processed them offchain, and a SNARK proved that the published tally reflected the newest valid message for each state leaf. The weak point sat in the old ProcessMessages circuit. It processed msgs[i] against coordinator-supplied currentStateLeaves[i], but the circuit did not force each message to be applied to the leaf identified by msgs[i].stateIndex before other invalidity branches ran. As issue #320, the later audit disclosures, and the v1.1.1 release notes describe, the coordinator could reorder or substitute currentStateLeaves[], feed a target message the zero leaf or another user’s leaf, cause the message to fail an earlier validity check, and thereby avoid the later stateIndex consistency check from ever constraining the batch. The proof could still verify, but it would be proving a censored batch transition rather than the intended apply each command to its actual indexed voter state statement.
  • Trigger / entry point:
    • The vulnerable surface was MACI 1.0’s offchain message-processing proof, specifically the ProcessMessages circuit.
    • The coordinator controlled the ordering and contents of the currentStateLeaves[] witness array supplied to that circuit.
    • The circuit then paired msgs[i] with currentStateLeaves[i] during processing rather than proving that each message was applied to the leaf located at that message’s stateIndex in the real state tree.
    • Because the proof output was later used as authority for the batch transition and tally, any hole in that binding directly affected vote inclusion.
  • Root cause:
    • The circuit under-constrained the relationship between msgs[i] and the state leaf each message was supposed to update.
    • stateIndex was intended to bind a message to one exact voter state leaf, but that binding was not enforced early and unconditionally.
    • Earlier validity checks could already mark the message invalid when the coordinator fed it the wrong leaf, including the zero leaf or another participant’s leaf.
    • Once the message had already been pushed down the invalid path, the later currentStateLeaf[i].index === msgs[i].stateIndex logic no longer restored the intended constraint.
    • The verified statement therefore drifted from these are the correctly indexed valid/invalid votes to these are some coordinator-chosen leaves and a batch outcome consistent with them.
  • Failure path:
    1. Users submit encrypted MACI messages onchain, each message carrying a stateIndex that identifies which voter state leaf it is allowed to update.
    2. The coordinator decrypts a batch of messages and prepares the witness for ProcessMessages.
    3. Instead of supplying the real leaves corresponding to each message’s stateIndex, the coordinator chooses a manipulated currentStateLeaves[] ordering.
    4. For a target message they want to censor, the coordinator pairs msgs[k] with an unrelated leaf or the zero leaf.
    5. The circuit sees a public-key mismatch or another early invalidity condition and marks msgs[k] invalid on that basis.
    6. Because the message has already entered the invalid branch, the later stateIndex check no longer forces the circuit to reject the coordinator’s mismatched leaf assignment.
    7. The coordinator produces a valid proof for a batch transition in which the censored message is treated as invalid and therefore excluded from the final tally state.
    8. Onchain verification then accepts a tally proof that appears censorship-resistant but in fact reflects coordinator-selected invalidation.
  • What the attacker needed to be true:
    • They needed to be the coordinator or otherwise control the witness generation path for the batch proof.
    • The circuit had to accept coordinator-supplied currentStateLeaves[] without independently proving each leaf’s membership and index binding against the authoritative state tree.
    • Earlier invalidity branches had to run before an unconditional stateIndex-to-leaf binding constraint.
    • The final system had to trust a successful ProcessMessages proof as evidence that valid messages were processed against the correct leaves.
    • Vote integrity had to matter economically or politically enough for censorship to be meaningful.
  • Technical anatomy worth remembering:
    • This was not a bad decryption or malicious coordinator simply refused to publish a proof story. The sharper problem was that the proof system itself failed to force the coordinator’s claimed batch semantics.
    • The coordinator’s leverage came from witness ordering. currentStateLeaves[] was not merely a transport detail; it was the security object that decided which public key a message was tested against.
    • The issue is a good example of zk soundness failing without a public-input range bug or a broken verifier key. The circuit still verified a relation; it was just the wrong relation for censorship resistance.
    • Issue #320 is especially useful because it sketches the missing safe shape in concrete circuit terms: for each batch position i, prove leavesToOperateOn[i] is a member of currentStateRoot or the prior updatedRoots[i-1] using pathElements[i], then apply commands[i] to that exact leaf and commit the next root. That is a stricter statement than the coordinator supplied some leaf array consistent with an invalid/valid outcome and it preserves the exact indexed state object across intermediate-root transitions.
    • The exploit target was vote inclusion, not token withdrawal. That matters because it broadens the proofs/verifiers corpus beyond direct asset drains into proof-backed governance or tally integrity can still fail if the proof statement is underbound.
  • Representative artifacts:
    • Public disclosure / fix-tracking issue: privacy-ethereum/maci#320
    • Vulnerable circuit called out in public materials: ProcessMessages.circom
    • Public redesign direction from the issue: replace coordinator-chosen currentStateLeaves[] pairing with leavesToOperateOn[] plus Merkle proofs against the current and intermediate roots
    • Public secondary summary: 0xPARC zk-bug-tracker entry MACI 1.0: Under-constrained Circuit
  • Response / mitigation:
    • The public fix direction was to redesign message processing so each command carried a Merkle-proven relationship to the real state tree rather than trusting coordinator-supplied leaf ordering.
    • Issue #320 describes the intended safer structure: for each batch element, prove that leavesToOperateOn[i] is a member of currentStateRoot or the prior updatedRoots[i-1], then apply commands[i] to that exact leaf and commit the resulting updated root for the next step.
    • PSE’s later MACI v1.1.1 release note is a useful primary-source confirmation that this was treated as one of the headline circuit flaws, explicitly naming Incomplete validation when processing messages as one of the two high-risk zk issues fixed in the release. The security-audit page later repeats that the 2022 HashCloak findings were remediated in v1.1.1.
    • The durable mitigation lesson is that zk tally systems cannot treat witness-side object pairing as an implementation detail. Message -> voter state leaf has to be one enforced proof object before the system branches on message validity.

Pattern tags

Three canonical-outcome promotions this incident collapsed

  1. A decrypted MACI message and some state-leaf-shaped witness object existed for this batch slot at all

    • The coordinator had a real msgs[i], a real stateIndex, and some currentStateLeaves[i] object it could feed into ProcessMessages.
    • That is only the existence question: some message and some leaf-shaped witness object are present for this position.

  2. That witness pairing still counted as canonical message -> exact indexed voter state truth for this slot

    • This was the dangerous promotion. The circuit let coordinator-supplied currentStateLeaves[] pairing stand in for the leaf actually located at msgs[i].stateIndex before invalidity branching finished doing real work.
    • Issue #320 is the useful primary-source correction because it sketches the healthier shape explicitly: prove leavesToOperateOn[i] is a member of currentStateRoot or updatedRoots[i-1] with pathElements[i], then apply commands[i] to that exact leaf.

  3. That accepted per-message classification still deserved canonical tally and publication authority

    • Once the proof system accepted the coordinator-shaped pairing, the resulting invalid classification still flowed into the batch transition the contract and downstream users had to honor as the poll’s real result.
    • The v1.1.1 release note makes the consequence explicit by listing Incomplete validation when processing messages as one of the headline high-risk circuit flaws that had to be fixed to restore MACI’s advertised uncensorability and correct execution properties.

Why the exploit worked

  • The coordinator controlled the witness-side currentStateLeaves[] array, and the circuit let that array decide which public key or state object each decrypted message would actually be tested against.
  • stateIndex looked like the authoritative binding between msgs[i] and one exact voter state leaf, but that binding was not enforced early and unconditionally enough to survive the circuit’s invalid-message branches.
  • That ordering mattered: once a target message had already been made to fail an earlier check by pairing it with the zero leaf or another user’s leaf, the later stateIndex consistency logic no longer restored the intended identity constraint.
  • The exploit therefore did not need to break encryption, forge a verifier key, or bypass onchain proof verification. It only needed the proof statement itself to tolerate witness-side object substitution before invalidity became final.
  • The sharper reusable lesson is that batch zk systems fail when which indexed object is this command acting on? remains a coordinator-supplied transport detail instead of a Merkle-proven and equality-constrained statement object.

Detection and audit pivots

  • For every batch-processing circuit, ask the per-item identity question explicitly: what exact constraint forces message[i], command[i], or note[i] to operate on the unique indexed object the public semantics name, rather than on a witness-supplied sibling object that merely makes the branch outcome convenient?
  • Trace invalidity branches in order, not just eventual checks in isolation. If an earlier branch can already mark a command invalid before the leaf index, owner, or membership path binding becomes mandatory, the later check may be semantically dead.
  • Build negative tests that keep the public batch and roots fixed while intentionally permuting the witness-side per-item leaves or accounts. Proof generation should fail, not merely produce a different invalid classification.
  • Treat coordinator-controlled witness ordering as a first-class security surface. Arrays like currentStateLeaves[], commands[], or pathElements[] are not just serialization details when their relative pairing decides which state object receives authority.
  • In tally and governance systems, audit correct execution and uncensorability claims as proof-statement questions, not only as liveness or operator-behavior questions. A coordinator can stay inside the formal proof system and still violate the social guarantee if the circuit proves the wrong indexed relation.

Failure-prevention checklist

  • Make the per-item target object explicit in the proved statement. If a command is supposed to act on stateLeavesInTree[msg.stateIndex], the circuit should prove that exact leaf-to-index relationship before any validity branch can discard or mutate the command.
  • Couple membership proof and state transition tightly. The healthier #320 redesign shape is prove this leaf belongs to current or prior intermediate root -> apply this command to that exact leaf -> commit the next root, not accept a coordinator-supplied leaf array and classify outcomes afterward.
  • Treat witness ordering as authority. Any array whose ordering decides which key, balance, vote state, or note a command touches should be constrained as carefully as a public input.
  • Force invalidity reasons to be local to the right object. A command should become invalid because its own signature, nonce, voice-credit limit, or state transition is wrong, not because the coordinator can first pair it with the wrong state leaf.
  • Test permutation resistance directly. Hold messages, roots, and expected outcomes fixed while shuffling witness-side leaves or paths; proofs should fail rather than silently recategorize valid commands as invalid.
  • Make intermediate roots first-class proof objects. If a batch updates state incrementally, each step should prove membership against the previous committed root rather than against a free-floating witness snapshot.
  • Re-audit coordinator-controlled helpers after every circuit optimization or batching refactor. Performance-driven witness reshaping is a common place for this array is only a transport detail mistakes to re-enter.
  • For voting and tally systems, review censorship resistance as a proof invariant, not only as an operator-trust assumption. If a coordinator can stay within a valid proof while excluding real votes, the statement is still too weak.
  • Keep release notes and migration docs explicit when a fix changes the proved statement. Integrators need to understand that this was not just a bugfix in implementation, but a tightening of what the proof is allowed to claim.

Audit prompts

  • What exact constraint ties each command to the one indexed state object the public semantics name, and does that constraint survive every invalidity branch?
  • Can a prover permute witness-side leaves, accounts, or paths while keeping the same public roots and still obtain a valid proof with different inclusion outcomes?
  • Does the circuit prove this leaf is a member of the current or prior committed root before applying the command, or does it trust a witness-side object first and justify the result later?
  • Which arrays or intermediate objects are coordinator-controlled, and what stops them from becoming hidden authority over vote inclusion or exclusion?
  • If a command becomes invalid, what proves it failed for reasons intrinsic to that command rather than because it was compared against the wrong state object?
  • Are there property tests for same messages, different witness permutation and same roots, wrong leaf pairing, not only happy-path tally correctness tests?
  • Do public security claims like uncensorability and correct execution map cleanly onto concrete circuit constraints, or do they still depend on an honest coordinator choosing the right witness pairing offchain?
  • During upgrades, which review step re-establishes that batching helpers, intermediate roots, and per-command path data still describe one exact state-transition object end to end?

Lessons that should already be standard

  • A zk proof can preserve coordinator censorship if the circuit proves the wrong indexed relation. Verifier accepted is not the same as every valid vote was processed against its real state leaf.
  • Witness arrays are often hidden control planes. When their ordering decides which state object a command touches, they deserve the same paranoia teams usually reserve for public inputs.
  • Late equality checks are not enough if earlier invalidity branches can already discard the object whose identity was supposed to be checked.
  • Governance and tally systems have proof-security bugs too. The absence of a direct asset drain does not make a statement-binding failure less important.
  • The healthy question is not only can the coordinator fabricate a message? but can the coordinator make a real message look invalid by choosing the wrong object for the proof to examine?
  • Batch-processing circuits should prove one exact per-step state object across intermediate roots. Anything weaker invites transport-layer substitution to become protocol truth.
  • Social guarantees like uncensorability only become real when they are encoded as machine-checkable object bindings inside the proof statement itself.

Why this incident matters

  • It preserves a high-value non-theft exploit shape for the corpus: a coordinator could keep the proof system intact while still using an under-constrained circuit to censor selected votes.
  • It is especially valuable because the violated property was not vague fairness rhetoric; MACI’s own release materials enumerate uncensorability and correct execution as first-class security properties, and this bug struck both through the proving layer itself.
  • It shows that zk systems can fail at the semantic-binding layer even when there is no field-modulus aliasing, malformed proof element, or verifier-key collapse.
  • It is also a useful comparison point for later proof-statement incidents like Aztec 2.0: in both cases the verifier could be cryptographically correct about a statement that was too weak for the application’s actual security promise.
  • The broader lesson is that proof verified does not imply the protocol's social claim held; here the missing claim was that each message had been evaluated against its actual indexed voter state.

Internal linkages

  • Closest recurring pattern: witness-public-input-binding-failure. The MACI bug is witness-side rather than classic public-input/root decoupling, but it belongs to the same broader family where a proof authenticates a weaker relation than operators think it does.
  • Direct statement-binding companion: proof-state-object-unification-and-indexed-binding-discipline — the sharper proof-design question here is how each message should have been bound to its exact indexed voter-state leaf before any invalidity branch or intermediate-root transition could weaken that identity.
  • Direct canonical-result companion: proof-backed-outcome-integrity-failure — the broader preserved lesson one layer out is that MACI never committed one exact command-result object that uniquely determined which proof-backed tally result had to be published.
  • Positive-design companion: canonical-outcome-commitment-and-finalization-discipline — use this when the sharper healthy-side question is what exact committed command-result object should have forced one unambiguous published tally and one unambiguous set of justified exclusions.
  • Positive-design companion: proof-effect-truth-security-object — the next healthy-side question one layer out is how one proved message-processing batch should stay identical to one economically and politically real tally effect set.
  • Adjacent proof-consumer contrast: proof-to-effects-binding-failure — that family is downstream settlement drift after a sound proof, whereas MACI’s problem was that the proof statement itself already allowed coordinator-chosen censorship.
  • Useful comparison: aztec-2-escapehatch-old-data-root-decoupling-unsound-proof-withdrawal-2026-06-17 — both incidents preserve the verifier accepted a weaker statement than the application promise required lesson, despite very different economic surfaces.

Control surface

Graph View

Backlinks