Norm Blowup in Lattice Folding — LatticeFold Lab (ZK Hack S3M4)

This repo contains a tiny Rust lab inspired by Binyi Chen’s LatticeFold whiteboard session (ZK Hack S3M4). The goal: see norm blowup with your own eyes, and understand why lattice-based folding schemes must use decomposition + range proofs to keep proofs sound.

This is not an implementation of LatticeFold itself. It’s a minimal experiment designed to build intuition for SNARK engineers and cryptographers learning folding schemes.

📌 Contents

• src/element.rs – small integer lattice vectors, norms, signed base-B decomposition
• src/folding.rs – folding recurrence, per-step statistics, multi-base decomposition
• plots/ – Python scripts to parse experiment output and generate figures
• blog/ – link to the full write-up

🧠 Background

In lattice-based succinct proofs, folding combines two witnesses:

$$ s_{k+1} = \alpha s_k + \beta t $$

This recurrence is linear, therefore the norm of $s_k$ typically grows geometrically.

But lattice-based SNARKs require that witnesses stay small (SIS-style short vectors).

So how do real systems avoid blowup?

Digit decomposition.

A huge coefficient $c$ is decomposed as:

$$ c = \sum_i d_i B^i, \hspace{4mm} d_i \in [−⌊B/2⌋,⌊B/2⌋] $$

The raw coefficient blows up, but its digits stay bounded, so range proofs can enforce shortness at each recursion step.

This repo demonstrates this phenomenon cleanly.

🚀 Running the experiment

Compile and run:

cargo run --release > plots/data.txt

This prints per-step statistics:

• L∞ norm of coefficients
• L₂ norm
• number of coordinates exceeding the bound
• L∞ norm of digits after decomposition for bases 4, 8, 16

Example output:

# step, avg_l2, avg_linf, avg_exceed, avg_decomp_linf_b4, avg_decomp_linf_b8, avg_decomp_linf_b16
 0, 6.54, 1.0, 0.00, 1.00, 1.00, 1.00
 1, 23.32, 5.0, 42.17, 2.00, 3.00, 5.00
 2, 63.79, 13.0, 56.83, 2.00, 4.00, 7.00
 ...
10, 20981.79, 4093.0, 56.83, 2.00, 4.00, 8.00

📈 Plotting

Activate the Python environment:

cd plots
python3 -m venv .venv
source .venv/bin/activate
pip install matplotlib

Generate the figures:

python plot.py

You will get two images:

1. Norm blowup (raw coefficients)

Shows that naïve folding makes coefficients explode exponentially.

2. Multi-base digit bounds

Shows that decomposition digits remain small and flat across folding steps, with different flat lines for bases 4, 8, 16.

📝 Blog Post

Full write-up (theory + Rust code + plots):

👉 https://www.reymom.xyz/blog/cryptography/2025-12-01-norm-blowup

📚 References

• LatticeFold: A Lattice-Based Folding Scheme and Its Applications to Succinct Proof Systems https://eprint.iacr.org/2024/257

• LatticeFold+: Faster, Simpler, Shorter Lattice-Based Folding (zkSummit 13 talk)

• SWIFFT, SIS, ZK Range Proofs (see blog post for full list)

✔️ License

MIT — do whatever you want.