ZK Research: Bignum Arithmetic for Zero-Knowledge Proofs

Daniel Lubarov and Jordi Baylina

October 27, 2022

As part of our ongoing efforts to inform the Ethereum community about the efforts of Polygon’s zero-knowledge (ZK) teams, we will be posting a series of technical papers by our engineers and researchers. We hope that everyone who’s interested in the inner workings of Polygon’s ZK projects, Ethereum itself, and cryptographic engineering in general will be able to learn something from them. Today’s authors are Polygon Zero lead Daniel Lubarov and Polygon Hermez lead Jordi Baylina.

In ZK applications, we often need to prove the result of some arithmetic calculation. An example is zkEVMs, such as Polygon zkEVM, which must support the EVM’s 256-bit arithmetic instructions. Since most ZK constructions are based on prime field arithmetic, simulating 256-bit arithmetic is a nontrivial task, a bit like solving a base-13 math problem using a base-10 calculator.

Instead of reaching for grade-school arithmetic algorithms, we take inspiration from another grade-school technique, namely the casting out nines test. Instead of computing x * y deterministically, we ask the prover to provide the result z, then check that x * y = z holds under several small moduli. The resulting algorithm is much more efficient than any deterministic method.

Read more below about this nifty ZK trick:

Download ZK Whitepaper

Polygon is so bullish on the future of ZK, the core development team made it a centerpiece of its strategic vision in the Zero Knowledge Thesis published in August 2021. As part of that mission, the team has committed $1 billion, a significant portion of the treasury, to ZK-related efforts.

Polygon is always on the lookout for new ZK talent. You can browse all the open vacancies here, and also follow our LinkedIn page. Tune in to the Polygon Blog for more in this series and to get the latest on zero-knowledge proofs and let's bring the world to Ethereum!