zkStudyClub - LatticeFold: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems (Binyi Chen)

Folding is a recent technique for building efficient recursive SNARKs. Several elegant folding protocols have been proposed, such as Nova, Supernova, Hypernova, Protostar, and others. However, all of them rely on an additively homomorphic commitment scheme based on discrete log, and are therefore not post-quantum secure. In this work we present LatticeFold, the first lattice-based folding protocol based on the Module SIS problem. This folding protocol naturally leads to an efficient recursive lattice-based SNARK and an efficient PCD scheme. LatticeFold supports folding low-degree relations, such as R1CS, as well as high-degree relations, such as CCS. The key challenge is to construct a secure folding protocol that works with the Ajtai commitment scheme. The difficulty, is ensuring that extracted witnesses are low norm through many rounds of folding. We present a novel technique using the sumcheck protocol to ensure that extracted witnesses are always low norm no matter how many rounds of folding are used. Our evaluation of the final proof system suggests that it is as performant as Hypernova, while providing post-quantum security.

Paper Link: https://eprint.iacr.org/2024/257

1. LatticeFold& its Applications to
Succinct Proof Systems
Dan BonehBinyiChen
Stanford University

2. (zk)SNARKs
(zk)SNARK = A succinct ZK proof showing that ∃" s.t. #(%,") =0
!
S(")→(%%!,'%")
P(%%!, ),*)
Properties:
•Completeness: honest P can compute valid !
•Knowledge soundness: malicious P* knows valid * if it can generate valid !
•Zero knowledge: ! hide the witness *
V ('%!, ), !)→0/1
E.g., SHA-3(") = %
Key requirements for /:Short (i.e. !≪|*|) + Fast to verify (e.g. O(log6) time)
Applications: Blockchain, Verifiable zkML/FHE, Fighting disinformation & more
[Xie+22, NT16, DB22, KHSS22, BBBF18, XCBFCK22……]
Challenges: Proving expensive statements (e.g., ML tasks) efficiently

3. Monolithic SNARKs [Bitansky-Canetti-Chiesa-Tromer12…]
Global computation
over the entire !
Proof "
Challenges for proving expensive computation:
•Expensive global computation
•Large prover memory
•Harder parallelization + less streaming-friendly
NP statement #,% for a relation &!
Extended witness !∈("
Algebraic transform
Full computation trace
Pre-quantum Schemes:
•Groth16, Plonk [GWC19], Marlin[CHMMVW20], Bulletproof[BBBPWM18]
•HyperPlonk[CBBZ22], Spartan[Setty19], etc…
Post-quantum Schemes:
•STARK[BBHR18],Brakedown[GLSTW21],Ligero[AHIV17], Basefold[ZCF23] …
•Lattice Bulletproofs[BLNS20,ACK21], LaBRADOR[BS22] …
E.g., a block of 10K txs is valid w.r.t. ledger state update
FFTs, MSMs, etc…

4. Piecemeal SNARKs [Valiant08, BCTV14, BCCT12]
NP statement #,% for a relation &!
split
SNARK Proof "#$
Ideas:
•Split the statement into multiple small chunks
•Prove chunk statements using SNARK Recursion
Problem: noticeable recursion overhead
•SNARK generation at each recursion step
•Concretely expensive SNARK verifier circuit
Pros:
•Minimal memory overhead
•Streaming/parallelization friendly+ v
+ v+ v
#!#"
SNARK Circuit:
(1) chunk stmt 3 is correct
(2) "%,"& verify correctly
e.g., a block of 10K txs is valid w.r.t. the ledger state
#!∗#"∗
[Bitansky-Canetti-Chiesa-Tromer12]
e.g. Mangrove[NDCTB24], [Sou23]
chunk
stmt 1
chunk
stmt 2
chunk
stmt 3

5. Folding Schemes [KST21,BCLMS20,KS23,BC23]
Committed NP Relation:
!,#∈%
com: A commitment scheme
!′=(),!),#∈%!
!,#∈%∧()=com#)
if and only if
Next: We omit public input . for notational convenience

6. Folding Schemes [KST21,BCLMS20,KS23,BC23]
Folding:
E.g., )%=com%%∧/%%=1
Folding 1'(Folding v'($
%'(
Stmt)%,%%)%,)&
)'(
Completeness: If )%,%%×)&,%&∈&×&, then )'(,%'(∈& for honest execution
Knowledge soundness: If )'( %'(∈& for 1∗’s output %'(, then 1∗ also knows %%,%&
Reduced goal: prove )'(,%'(∈&
Generalization: Reduction of knowledge [Kothapalli and Parno23]
Input relation: &% Output relation: &&
)*+,%*+
Goal: prove )%,%%×)&,%&∈&×&
),-$,%,-$
%$% and v$% can be made non-interactive
×)&,%&
≔&×& ≔&
≔)%,%%×)&,%& ≔()'(,%'()

7. SNARKs from Folding [KST21,BCLMS20,KS23,BC23]
Piecemeal SNARK:
NP statement #,% for a relation &!
("!,$!)∈'"#$("%,$%)∈'"#$
split
………… ("&,$&)∈'"#$
("'(
),$'(
()))("'(
!,$'(
(!))!!" !!"……
SNARK V checks
∈)&'(!!" !!" !!")=("'(
&,$'(
(&))……("'(
,,$'(
(,))
Is !"#
$ correct?
Fix:
•Set x=H(.),H(.)*!,…,H(.!)) as public input
•SNARK P also sends (.!,…,.))
•V checks x=H(.),H(.)*!,…,H(.!)) and computes .$%
) by iteratively calling folding v$% given .!,…,.)
Caveat: proof/verifier complexity linear to 2
Idea: Delegate the verifier work into the folded relation
Prove a chain of computations (can extend to a tree of computations)
Similar strategies used in SNARGs for P and BARGs[Choudhuru-Jain-Jin21, Waters-Wu22]
SNARK P computes:

8. SNARKs from Folding [KST21,BCLMS20,KS23,BC23]
Relation ) :
(1) .+,!=com(6+,!)
(2)local computation is correct
(3)Folding verifier v$%.+,.$%
(+),.$%
(+,!);#$%=1
)'(
(/0%)+ witness %'(
(/0%)
Folding verifier 9$%:
•≈ check .$%
(+,!)=.++<⋅.$%
(+) for some scalar <
•much simpler than a SNARK verifier!
v$%
.$%
(+)
.+""#Compute
.+,!,6+,!∈)v$%
.$%
(+),6$%
(+)∈)
.+,6+∈)
v$%
Prev %−1 steps are correct
The %-th step is correct
Piecemeal SNARK:Prove a chain of computations (can extend to a tree of computations)
): an expanded relation to )&'(
Omit public input hash checks for simplicity
Folding prover >$%:
•6$%
(+,!)=6++<⋅6$%
(+) : linear combination of field elems
•much faster than a SNARK prover!
Why faster than SNARK recursion?
Simpler relation ) Faster folding for relation ) than SNARK proving
A folding scheme could be more eXicient than a SNARK

9. Folding Schemes: State-of-the-Art
Committed NP statement !,#∈%
•Instance ): a short com(%) to witness %
•com is linearly-homomorphic for easy folding
State-of-the-art:
•Pedersen commitments
•Linearly-homomorphic
•Pairing-free
•No trusted setup
Security:
•Based on DLOG assumptions & not post-quantum secure
E?iciency:
•Require cycle curves
•Prover: many group-exponentiations over a large field
•Wasteful as real data units usually small (e.g. 32-bit)
•The folding verifier circuit v'(:
•Elliptic curve scalar multiplications : (
•Non-native field-op simulations : (
Alternative Option:
Recursive SNARKs from hash-based STARKs
Less e5icient: need full SNARK recursion
implement arithmetic in ?/ as a circuit over ?0
e.g., com&+com(=com(&+()

10. Can we construct a folding scheme with
•Post-quantum security
•Ultra-fast prover
•Efficient verifier circuit (e.g., no need for non-native field emulation)

11. LatticeFold: The first lattice-based folding scheme
•Based on the Module Short-Integer-Solution (MSIS) assumption
•Competitive efficiency vs existing folding schemes
•Linear-time prover + succinct verifier circuit
•Relatively small fields (e.g., 32-bit or 64-bit)
•Native simulation of ring operations in circuits
•More friendly for applications like verifiable FHEs/MLs
Technical contribution:
New folding techniques for lattice-based commitments
Contributions

12. Folding for
Relation & :
(1) )/0%=com(%/0%)
(2)local computation is correct
(3)Folding verifier v'()%,)&,)'(;"'(=1
Commitments Opening Relation
Warmup:

13. Folding for Ajtai Commitment Openings
Committed NP statement !,#∈%
•Instance .: a short com(6) to witness 6
•com is linearly-homomorphic for easy folding
A←$ℤ/2×):
;
How about Ajtai binding commitments?[Ajt96,99]
6∈ℤ2"
=.
Binding for “small-norm” % (under SIS assumption)
.!."+=A×
6!6"+
=A6!+
6"
Homomorphic property:(over small-norm messages)
speed ≈ Poseidon hash over fast fields [GKRRS19]
6+∈(−E,E) for F∈[2]
∈ℤ23Compact
Module-SIS
Generalization
ℤ ⇒ &≔ℤ[?]/(?4+1)
ℤ2⇒ &2≔&/C&
[LM’07,PR’07]
How to commit to # w/ large norms?

14. Dealing with Arbitrary Witness
How to commit to an arbitrary witness 1 w/ large norms?
Comm open relation:
&%IJKIL
M≔{!;(#,⃗, ):(!=1⃗,)∧(,<4)∧(#=5×⃗,)}
Gadget matrix
E.g. %%=1,2,2&,…,256% ×
⃗G%⃗G&.
.
.
⃗G5
Our full-fledged protocol fold a similar relation
The infinite norm of 6∈ℤ)
6≔max|6+|+4!)
Comm open relation:
%IJKIL
M≔{!,#∶!=1#∧#<4}
Next, assume that % is always low-norm in the first place!

15. Folding for Ajtai Commitment Openings
Comm open relation: %IJKIL
M
Naïve approach:
)%,%%∈&78$7*
9
)&,%&∈&78$7*
9
)'(≔)%+I⋅)&
%'(≔%%+I⋅%&Folding 1'(
,∈ℤ( is a random scalar
∉%IJKIL
M!
Problems:
•‖"/0‖ can be larger than # (even if I is small)
•$/0 no longer binding after ‖"/0‖ exceeds threshold
Thoughts:
Make "1,"2 smaller
before random LinComb?
The infinite norm of 6∈ℤ)
6≔max|6+|+4!)
Can’t support many folding steps
≔{!,#∶!=1#∧#<4}

16. Our Strategy
Relation: !&'(&)
*≔{$,&∶$=)&∧&<,}
&78$7*
9
&78$7*
9Π
Recall our goal: reduction of knowledge Π
× &78$7*
9
Attempt:
&78$7*
9
&78$7*
9
Decompose 6×
&78$7*:
&78$7*:
&78$7*:
&78$7*:
×
×
×Fold&78$7*
9
Π
(K<M)
How to instantiate
Decompose and Fold?
Sequential composition:
&%&&&;Π5Π6&%&;Π6∘Π5
Nice property of RoK! [Kothapalli and Parno23]

17. Roadmap
•Decomposition Protocol
•Fold Protocol
&78$7*
9
&78$7*
9
Decompose 6×
&78$7*:
&78$7*:
&78$7*:
&78$7*:
×
×
×

18. Norm Control with Decomposition
),%∈&78$7*
9Decompose
&78$7*:
&78$7*:×
Goal:
K&=M
RoK from 3)*+),
-×3)*+),
- to 3)*+),./
is a parallel composition of the above protocol
“Write” the big vector # using “base” ;
6
ℤ-coeffs
in (−-,-)
6!
ℤ-coeLs
in (−.,.)
6"
ℤ-coeLs
in (−.,.)
=+3⋅
!0,!1
!0=670 ,!1=671
V check:
.=.!+T⋅."
70 ,71
Decompose:
1 U
!=677!=67
6 6!6"=+3⋅
A A
)=)"+)#3⋅
Extract:
7∗=70+(⋅71
“remainder” + “quotient”
),%∗∈&78$7*
9

19. Roadmap
•Decomposition Protocol
•Fold Protocol
&78$7*
9
&78$7*
9
Decompose 6×
&78$7*:
&78$7*:
&78$7*:
&78$7*:
×
×
×Fold&78$7*
9

20. Folding: Naïve Approach
Fold&78$7*
9
&78$7*:
&78$7*:
×
×
…
…
Goal:
Folding 1'()'(≔)%+I⋅)&
%'(≔%%+I⋅%&
,∈ℤ( is a
small random scalar
Knowledge extraction:
Naïve idea:
)%,%%∈&78$7*:
)&,%&∈&78$7*:
Solve linear eqs
for %%,%&
#V=#WX
Y−#WXZ⋅>[−>\
]^
Extracted witness:
The norm can be much larger than N!
∈%IJKIL
M!
Completeness✔
#WXZ=#_+@Z⋅#V
#WX
Y=#_+@Y⋅#V
Same for #_
Rewind 1'(∗ to obtain %'(<, %'(
= for )'(<=)%+I<⋅)& and )'(
==)%+I=⋅)&
K≪M
!V,#V∉%IJKIL`!

21. Roadmap
•Decomposition Protocol
•Fold Protocol
•Naïve extraction+ argue smallness of the extracted witness
Using Range proof: witness %∈−K,K"

22. •!′=1#a
•#a=B_,BV,…,Bb has small norms
(Batched) Range proof via Sumcheck
Goal: Given input commitment !a, prove knowledge of #a=B_,BV,…,Bb∈ℤb
•!′=1#a
•#a=B_,BV,…,Bb has norm smaller than ;
•E\icient (folding) verifier circuit
!3=!0 !1 in folding
Our strategy: Combine naïve folding & extraction+ Range proof protocol
(achieved by naïve folding + extraction)
73=70 71 in folding
Our solution: A range-proof protocol from Sumcheck

23. Review of the Sumcheck Protocol [LFKN92]
Goal: Given a “committed” Q-variate poly R(#%,…,#>), convince V that ∑<∈@,%4R⃗#=T
Naïve verifier: query R at every #∈0,1> and check the sum Ω2> complexity : (
Sumcheck protocol [LFKN92]
•Q-round interactive protocol between P and V
•V sends a random challenge I/∈( in each round
•At the end of the protocol, V queries R at a single random point
Sumcheck: Σ⃗<∈@,%4R(⃗#) =T
Sumcheck protocol [LFKN92]
EvalCheck: R⃗I%,…,⃗I>=X′ at a random ⃗I∈ℤ2>
History: Key ingredient for proving 1Z⊆ \1 and inspires the proof of \1=1]1^_`
cd-time verifierA reduction from
Sumcheck to Eval stmt

24. Step 1: Rephrase the range-proof statement as a Sumcheck statement
Step 2: Construct a folding protocol for the Sumcheck statement
Goal: Given input commitment !a, prove knowledge of #a=B_,BV,…,Bb∈ℤb
•#a=B_,BV,…,Bb has norm smaller than ;
Our solution: A range-proof protocol from Sumcheck

25. Step 1: Reducing Range proof to Sumcheck
Range proof: Prove knowledge of a witness %C=a%,a&,…,a"∈ℤ" s.t.Can extend to elements in ring
)=ℤe/(e7+1)
ℎ#≔##+1⋅#−1⋯#+K−1#−K−1over ℤ/≔−/
",/
" and g>2T is a prime
Embed 6′ to the Boolean hypercube of
a multilinear polynomial kl!,…,l89:)
Zero-check to sum-check [CBBZ23, Setty20]
Sumcheck: prove that Σ⃗<∈@,%5678R(⃗#) =0 where R⃗#≔ℎa⃗#⋅dCD(⃗#) for a rand e∈ℤ2E,F"
k!∈ℤk"………k)*!k)
∈−(,(⊆ℤ∈−(,( ∈−(,(∈−(,(
ℎk!=0ℎ(k")=0………ℎk)*!=0ℎk)=0
⃗l00…0000…01………11…1011…11
ℎl=0⟺l∈−T,T
k⃗lk!k"………k)*!k)ℎ(k⃗l)ℎk!=0ℎ(k")=0………ℎk)*!=0ℎk)=0

26. Step 2: Sumcheck Folding
Sumcheck: Σ⃗<∈@,%5678R(⃗#) =0
Range proof: witness %′=a%,a&,…,a"∈−K,K"
Sumcheck protocol [LFKN92]
EvalCheck: R⃗I=X′ at a random ⃗I∈ℤ2E,F"
Prover time: ≈g(K;)
Verifier time: g(Klog;)
Problem: How to check B⃗@=E given the comm of B?
•Send B_,BV,…,Bb to the folding verifier to check it?
Observation: EvalStmt B⃗@=E is easy to fold!
EvalCheck: a⃗I=X
q⃗l≔ℎk⃗l⋅rg;(⃗l) Step 1✔
(and verifier can check q⃗<= ℎs⋅rg;⃗<=s′ itself)
F(G) folding verifier : (

27. Folding Evaluation Statements
Observation: a⃗I=X is easy to fold!
a%⃗I%=?X%
a&⃗I&=?X&
Translate to
SumChk Stmt
Multilinear extension: a⃗I=Σ⃗<∈@,%5678a⃗#⋅dC⃗H(⃗#)
SumCheck
a'(≔a%+j⋅a& for rand j
a'(⃗II=?XI
efficiently
computable
a%⃗II=?XI,%
a&⃗II=?XI,&
⃗II: sumcheck challenge
How does it help to check B⃗@=E given the comm of B?
•Fold the evaluation statement without checking!

28. Folding for Ajtai Commitment Openings
Solution: Expand relation %IJKIL to include the evaluation statement
()=coma)∧(a⃗I=X)
Naïve Fold
+
SumCheck for
RangeProof & EvalStmt
Verifier: 5(3log8)
."=?com6k"∧
k"⃗<"=?s"
)=>?86
Accumulated
statement
.!=?com6k!)?@A?B6
Online statement
.$%=?comCk$%
∧
k$%⃗<D=?sD
)=>?8
C
New accumulated
statement
MatMul +
RangePf +
EvalStmt
The knowledge soundness proof is more subtle than intuition
•A malicious prover can adaptively choose the output witness after seeing the challenges
•⇒ The extracted input witnesses could depend on the sumcheck challenges

29. Subtleties & Optimizations
Sumcheck over Rings: [CCKP19, BCS21]
•Ajtai commitments over ring +<≔ℤ<[/]/(/=+1) for concrete e;iciency
•Small-norm random folding scalar chosen from 6⊆+< for negligible soundness error
•Implication: Run Sumcheck over rings
Supporting Small Modulus:
•We want a small modulus 8 for better efficiency
•Efficient CPU/GPU ops; no big-number arithmetics
•More efficient packing of real-world data
Folding for NP-complete relation
Relation ) :
(1) .+,!=com(6+,!)
(2)local computation is correct
(3)Folding verifier v$%.!,.",.$%;#$%=1
needs to express computationArithmetic over a ring → Great fit for Verifiable ML/FHE

30. ETiciency Estimates
Folding prover:
g(_JKL)-sized Multi-Scalar-Muls
)/≔ℤ/[e]/(eEF+1) ≅?/!!E; g: a 64-bit prime
w&'(: chunk circuit size (e.g. 2"G gates over ?/!)
Norm bound: E≈2!E; Base: T=2
Folding verifier:
native-ops in the circuit over &2
non-native field ops in the circuit
Competitive circuit sizes
Piecemeal SNARK proof: ≈2 folding instance-witness pairs
Solution: Use a PQ-secure STARK to prove the correctness of the folding statement
<100KB and 2ms verifier (STIR[ACFY24])
g(_JKL) multiplications over &2
Compute Ajtai commitments
LatticeFoldExisting schemes
Pedersen commimtents
g(K⋅log|_JKL|) hashes and &2-ops
Sumcheck verifierECC scalar-mul + (Sumcheck V)
speed ≈ fast hash
Can reuse fast FHE impl!
<5KB w/ Hyperplonk+KZG[CBBZ23]
i.e., arithmetic in ?/ as a circuit over ?0
What if it’s still large?
E.g., splitting a stmt of size 2-) to 2%) chunks → 2%)-sized chunk stmts

31. Summary & Open Problems
Takeaway:
•The first lattice-based folding scheme based on Ajtai commitments
•Gives memory-efficient, plausibly PQ-secure SNARKs, with fast provers
•Generic techniques for folding lattice-based commitments w/ norm constraints
Open problems:
•Compact + homomorphic lattice commitments with no norm constraints
•Folding table lookup relations (e.g., from Lasso [Setty-Thaler-Wahby23])
•Efficient implementation
Concurrent work:[Bünz-Mishra-Nguyen-Wang24]
•Purely from hashing; no lattice crypto
•General optimization techniques for piecemeal SNARKs (apply to LatticeFold)
•Larger verifier circuit; only supports bounded-depth folding (attack exists)

32. Thank you!
https://eprint.iacr.org/2024/257.pdf
Expecting updates soon!