In September 2022, I contributed a repair to circom-pairing, a cryptography library that helps developers prove calculations involving very large numbers. Such zero-knowledge proofs allow someone to demonstrate that a calculation obeys agreed rules without disclosing all its inputs. The repair concerned division, one of the earliest operations most of us learn.
Dividing seventeen by five gives three, with two left over. Multiply the answer by five and add the remainder, and you recover seventeen. Yet that equation alone does not determine the answer:
17 = 5 × 3 + 2
17 = 5 × 2 + 7The remainder must also be nonnegative and smaller than five. In a proof system, developers write rules like these as mathematical conditions, collectively called a circuit. Every condition needed to establish the intended answer has to be expressed there.
Very large numbers add another requirement. The library represents them in smaller pieces, much as we write decimal numbers using digits. Each decimal digit has an allowed value between zero and nine. Putting twelve in a single digit position breaks the assumptions behind ordinary digit-by-digit comparison. The library uses binary pieces instead, with a fixed number of bits allotted to each. Enforcing those allowed values is called a range check.
The two division routines, BigMod and BigMod2, already compared the remainder with the divisor. The omission was in the representation: they did not enforce the size of each piece of the remainder. Their comparison relied on those pieces being within their allowed values.
This is a boundary between cryptography and the program it is meant to verify. A proof system such as Groth’s construction (2016) establishes the mathematical relation supplied to it. If that relation leaves out a requirement, a valid proof can establish less than the developer intended.
Ecnerwala had already addressed the same omission in circom-ecdsa. Following that earlier repair, I added the missing bit limits to the remainder pieces in both circom-pairing routines. Yi Sun merged the change on September 22, 2022.