Quadratic Residues and the Failure of Zero Knowledge Positivity Proofs over BN254
Mark Askey, 0REI Immutable Evidence Systems0009-0002-4624-0897Zenodo
- Version 2, latest
- Version 1
- BN254
- zero-knowledge proofs
- Groth16
- arithmetization
- quadratic residues
- soundness
A published zero-knowledge circuit claims to prove that a matrix is positive definite by checking a Cholesky witness inside a prime field, and states that the proof system is complete and sound. This paper shows it is neither when the field is the BN254 scalar field, a standard field for Groth16. A prime field has no order that agrees with its arithmetic, and only half of its nonzero elements have square roots, so the test that works over the real numbers does not carry over. The flaw is in the arithmetization, not in Groth16.
What the paper shows
- What the circuit really accepts. It accepts a symmetric matrix exactly when each ratio of consecutive leading principal minors, reduced mod p, is a nonzero quadratic residue with a positive signed representative. That condition is unrelated to the true signs of the minors.
- Soundness fails. For the three-agent star topology at a coupling of about 0.10997, above the exact threshold of 0.1, an indefinite matrix with smallest eigenvalue about -16640.92 has an accepting witness.
- Completeness fails. Every diagonal entry equals 1/10, and both natural encodings of 1/10 are quadratic non-residues mod p. The circuit rejects every configuration, including zero coupling.
- A repair and the code. The paper suggests a repair based on range-checked integer arithmetic and Sylvester's criterion, and releases code that reproduces every number.
Read the abstract
Nagaraj (arXiv:2608.09087v1) proposes a zero-knowledge circuit over a prime field that attests the positivity certificate α_self·I + γ·A_sym ≻ 0 through a Cholesky witness, and states that the proof system is complete and sound. We show it is neither when instantiated over the BN254 scalar field, a standard field for Groth16. We prove an exact acceptance criterion: the circuit accepts a symmetric S if and only if each ratio of consecutive leading principal minors, reduced mod p, is a nonzero quadratic residue with a positive signed representative. That condition is unrelated to the true signs of the minors. For the paper's three-agent star topology with α_self = 1/10, we give two counterexamples. At γ ≈ 0.10997, above the exact threshold of 0.1, an indefinite encoded S (smallest eigenvalue ≈ −16640.92) has an accepting witness. Conversely, every diagonal entry equals α_self, and both natural encodings of 1/10 are quadratic non-residues mod p. The circuit therefore rejects every configuration, including γ = 0. The flaw lies in the arithmetization, not in Groth16. We suggest a repair based on range-checked integer arithmetic and Sylvester's criterion, and release code that reproduces every number.