A humble dive into Fully Post-Quantum zkEVM

Introduction

For the past few years, Zero-Knowledge Proofs have been developed over the SNARK (Succinct Non-Interactive Arguments of Knowledge) and STARK (Scalable Transparent Argument of Knowledge) patterns, in order to harness the power of secure, verifiable computation for L1 Ethereum (opens in a new tab). Each of them have their own advantages and disadvantages, for instance, SNARKs have significantly fast verification times, whereas, STARKs have fast, platform-independent proof generation times. However, zkSNARKs are based on the idea of billinear (opens in a new tab) pairings, which in itself requires something called a Trusted Setup Ceremony (opens in a new tab), which in itself again is a time-taking process.

Looking at this 2 more variants were created, namely STARKs and Bulletproofs. These variants did not require a trusted setup ceremony, but their proof sizes were significantly bigger when compared to SNARKs.

Here's a detail describing everything about them:

For several months, various companies have come across various methods to speeden up the process, one such notable implementation was Bonsai (opens in a new tab) by RISC Zero, which converts zkSTARKs to zkSNARKs thereby deriving the best of both worlds, in context of Prover and Verifier times.

Fully Post-Quantum

Inspite of so much optimization of speed and performance, both zero-knowledge proofs (SNARKs and Bulletproofs) and well as very common digital signature algorithms have been extensively rumored to get cracked by a Quantum Computer (opens in a new tab).

However, while (almost) nobody saw this coming, we made some notable observations:

1. Elliptic Curve Cryptography (with Billinear Pairings): Mainly SNARKs, if not Zero-Knowledge Proofs then, core digital signature algorithms used by L1 Ethereum, as well as most of the L2 ecosystem as well.
2. Such algorithms like ECDSA (Elliptic Curve Digital Signature Algorithm) heavily rely on NIST standardized curves like Edwards25519, Curve25519, BN254, etc. for perform point operations, for safely evaluating these signatures
3. 256-bit Elliptic Curve Encryption is one such technique used in Bitcoin. And, this is the impact when ECC algoritms are tried to be cracked by Quantum Computers.

4. Similarly current cryptographic protocols based on the Computational Diffie-Hellman Assumption (opens in a new tab), as well as Polynomial Commitment Schemes (opens in a new tab), such as Pedersen Commitments exploit the mathematical properties of Discrete Logarithm. Such technology is also being used in Ethereum's upcoming The Verge upgrade.
5. The entire mathematical feature of Discrete Logs that make it secure, finding all possible factors of a given number, such that, the number modulo a prime p (finite field) always gives the same result is occassionally a difficult job by the computer.
6. However, a very note-worthy quantum algorithm called Shor's Algorithm (opens in a new tab), is often used for computing factors of a number. Which in-turn means it's quite a doable job for Quantum Computers to crack Discete Log Problems if the finding factors of a number gets boiled down to an NP problem (a problem that can be cracked by a Non-deterministic machine in Polynomial Time).

Turns out that's exactly what has happened, here's a graphic decribing so:

We see that Classical Algorithms take exponential time, where d stands for the number of digits of the number whose factors are supposed to be computed. Turns out Shor's Factoring Algorithm solved it in Poly. time with $O(k * d^3)$ time complexity, where $k$ is an arbitrary constant.

For further reading you can consider going through this (opens in a new tab) paper. Here's how factor calculation happen behind the scenes.

Our Goal

TrueZK brings forth applied use-cases to Fully Post-Quantum Zero Knowledge Proofs and Digital Signature algorithms. For building the world's one of a kind scalable Post-Quantum zkEVM Prover we plan to use the Goldreich Kahan (GK96) protocol for constructing zero-knowledge proofs. You can find further details in this (opens in a new tab) paper.

Here's the portion in the paper we're mainly interested in:

Additionally, we have smaller usecase, specifically designed for app-centric privacy, which were primarily built of zkSNARKs along with Rate Limiting Nullifiers, which are engineered to prevent sybil-attacks. We call it, TrueID.

We realise that TrueID won't be so truely secure and post-quantum in the upcoming years, hence we plan on extending futher research over CRYSTALS (opens in a new tab) (Cryptographic Suite for Algebraic Lattices). One such algorithm we wish to heavy study and draw applications from are Dilithium (opens in a new tab) and KYBER (opens in a new tab).

Both Dilithium and Kyber are Fully Post-Quantum cryptographic algorithms based on Lattice Cryptography. Currently both of them have been standardized by NIST under PQC.

For further exploration, you can read more about how ZCash intends to migrate to Post-Quantum under these 2 Github Issues by Daira Hopwood:

1. https://github.com/zcash/zcash/issues/805 (opens in a new tab)
2. Fully Post Quantum Privacy for ZCash (opens in a new tab)

Conclusion

Our zkEVM Prover will essentially be fully Ethereum as well as EVM compatible, with both approaches, namely in an L2 network as well as in a Validium (off-chain) approach.

Additionally, we want to slowly be in line with the Development Roadmap of Ethereum Foundation, hence, any and every further upgrade by Ethereum will be acknowledged by us, thereby every development change we bring forth shall be totally at par and fully compatible, as we firmly believe developing in the open-source ethos, in favor of the community.