Fast Proof of Bootstrapping

[d-i-rubin]

Zama Grant Program: Application

• Library targeted: TFHE-rs, verifiable-fhe-paper

• Overview: We will demonstrate a practical Proof-of-Bootstrapping capability. Extending the recent work by the Zama team “Towards verifiable FHE in practice,”¹ we will bring the proof generation time of a SNARK attesting to the correct bootstrapping of a TFHE ciphertext from 20 minutes down to seconds by making use of several recent advances in ZK techniques. This work will demonstrate the potential viability for verifiable private smart contracts.

• Description: Verifiable FHE is a major challenge at the frontier of ZK technology. Recently, a Zama team has brought the proof generation time of a proof of correct bootstrapping, the single most expensive TFHE operation, down from approximately 24 hours using general-purpose ZK Virtual Machine software to about 20 minutes. This is a significant achievement, but not yet practical for building a protocol to verify an entire smart contract operating on FHE ciphertexts.

We intend to follow the Zama team’s effort closely in proving the bootstrap in Zama’s TFHE library². They decompose the Programmable Bootstrap into 4 steps: Modulus Switch, Blind Rotation, Sample Extraction, and Key Switching. We will follow their decision to choose a modulus q for the polynomial ideal ring in which a Number Theoretic Transform (NTT) is available for fast multiplication of objects in this ring.

Where we will depart from the Zama team is in our choice of Interactive Oracle Proof (IOP) and the use of folding as a substitute for recursion. The Zama team wrote a custom circuit for the bootstrap using the plonky2 library, which implements the Plonk IOP and FRI commitment scheme. As a substitute for Plonk, we will use a newer IOP called a Customizable Constraint System (CCS)³⁴. This system generalizes all Plonkish, AIR, and R1CS schemes, has a more efficient proof gadget than Plonk (Sumcheck), and is well-suited to custom gates and folding schemes.

We believe our main speedup will come from the use of folding. The largest part of the bootstrap circuit is the Blind Rotation, which consists of a subcircuit of size S, performed serially N times. The Zama team employed a method of Incrementally Verifiable Computation, proving at each step the k-th subcircuit, and the Verifier’s circuit for the result at the previous step. Folding avoids recursion by combining the proofs of these subcircuits into a single proof. Note that the large speedup gained by folding is not necessarily removing the need for proving the Verifier circuit N times. If the size of the Verifier circuit V is much smaller than the size of S, then removing N instances of V while still performing N instances of S does not significantly decrease the size of the computation. However, with a folding scheme, the N instances of S can be proved in parallel before being folded together. With the same parameters as in Zama’s effort, the size of S was a degree 2^17 Plonk polynomial, V a degree 2^12 Plonk polynomial, and N approximately 700. We believe we can achieve a constant multiplier speedup through the use of custom gates to reduce the size of S, another constant multiplier from the linear-time Multi-Linear Extension and Sumcheck gadgets over the quasi-linear gadgets involved in Plonk, small speedup from the elimination of most of the N instances of proving V, and the largest multiplier from achieving maximal parallelism across the N instances of S.

We intend to implement a folding scheme as described in the recent paper “Accumulation without homomorphism”⁵. This approach gives the benefits of working with the fast FRI commitment scheme. Experiments will reveal the optimal/achievable level of accumulation/parallelism vs. recursion. In the longer term we would also like to experiment with the recently described LatticeFold⁶ commitment scheme, an additively homomorphic succinct commitment scheme based on lattice cryptography.

Our main tasks are to 1) write custom CCS circuits for the subcircuits of the bootstrap operation, optimized to reduce the size of the multilinear polynomials, 2) construct a folding circuit to accumulate these circuits efficiently, 3) implement the linear combination check described in⁵ to achieve folding with the FRI scheme, and 4) demonstrate the proof generation on a hardware system capable of taking advantage of the parallelism of our approach. At the end of this project, we will make available a library entirely analogous to the Zama teams’ verifiable-fhe-paper library⁷ that can perform the bootstrap operation on a TFHE ciphertext, and then generate a SNARK attesting to the correctness of the bootstrap. The goal is to achieve a proof generation time in a few seconds, with no additional overhead in proof size or verifier time compared with the Zama team’s result.

• Reward: US $350,000. This grant will support a technical team of 3 people working for 6 months. The team will consist of Principal Investigator Daniel Rubin, and Cryptography Engineers Brian Hwang and Hridam Basu.

• Related links and reference: This work will be carried out by L-Infinity Labs, an early-stage startup founded by Daniel Rubin and Scott Miller. L-Infinity Labs won an NSF Small Business Innovation Research grant in 2023 to conduct research in FHE.

References:

Footnotes

1. L.T. Thibeault, M. Walter, Towards verifiable FHE in practice: proving correct execution of TFHE's bootstrapping using plonky2 ↩

2. GitHub - zama-ai/tfhe-rs: TFHE-rs: A Pure Rust implementation of the TFHE Scheme for Boolean and Integer Arithmetics Over Encrypted Data ↩

3. S. Setty, J. Thaler, R. Wahby, Customizable constraint systems for succinct arguments ↩

4. https://github.com/thor314/ccs-hack ↩

5. B. Bunz, P. Mishra, W. Nguyen, W. Wang, Accumulation without homomorphism ↩ ↩²

6. D. Boneh, B. Chen, LatticeFold: a lattice-based folding scheme and its applications to succinct proof systems ↩

7. https://github.com/zama-ai/verifiable-fhe-paper/tree/main ↩

[zama-bot]

Hello d-i-rubin,

Thank you for your Grant application! Our team will review and add comments in your issue! In the meantime:

1. Join the FHE.org discord server for any questions (pick the Zama library channel you will use).
2. Ask questions privately: bounty@zama.ai.

[zaccherinij]

Hi,

Thank you very much for your interest in what we do at Zama, and your proposition for a grant. For now, we will not follow up with your proposition. But we invite you to keep an eye on this repository as we will launch new bounties soon, if you're interested in playing with Zama libs.

Cheers,
JZ