Snarks for the world

Introduction

zk-SNARKs are a cryptographic technique allowing a prover to efficiently convince verifiers that the prover knows something — but without revealing the information itself. zk-SNARKs allow for secure, private interaction with unknown and untrusted parties in a blockchain setting due to their (knowledge) soundness property: a valid proof cannot be created without knowledge of the correct statement, even if they are kept private.

The Filecoin Network currently generates 6-7 million zk-SNARK proofs per day, with each proof including more than 100 million arithmetic constraints. In order to accomplish this, we improved and heavily optimized existing SNARK-generation tooling so it would scale to meet our unprecedented requirements.

Filecoin is the largest deployed zk-SNARK network to date.

Build the future of zk-SNARKs with us.

Achievements

Facts you didn’t know about zk-SNARKs

Live statistics from Filecoin Mainnet today:

Statistics

Zcash's supported amount of constraints

Zcash
2,097,152

Filecoin's supported amount of constraints

Filecoin
134,217,728

Maximum Constraints

To support the amount of constraints needed for Filecoin, we ran a new Powers of Tau Ceremony, increasing the supported number by a factor of 64, over the Ceremony Zcash had run. This allows us to generate proofs of over 100 million constraints, limited only by the size of the parameters which must be distributed.

To support the Phase 2 (circuit-specific) trusted setup for our large circuits, we implemented techniques to dramatically decrease RAM usage, allow for parallelism, and reduce I/O overhead — in order to allow many parties using practical hardware to participate during the 7 weeks the ceremony took place.

The generation of zk-SNARKs quickly became a bottleneck, so the expensive parts (FFT and MultiExponentiation) were implemented on the GPU using OpenCL and CUDA. Because the core operations supporting proof generation are highly parallelizable, we take advantage of modern general-purpose GPU computing to off-load them from the CPU.

This allows a much higher throughput, while also creating economic efficiency. By moving the parallelizable work to relatively inexpensive parallel processors, we keep main memory and CPU free for the highly-sequential and memory-intensive workloads used to create the data miners must prove.

Low level operations in ms:

Low level field arithmetic is the basis of most of the operations performed when generating and verifying zk-SNARKs. The blst library implements the critical parts in assembly and C to get last bits of performance out of the CPU. To ensure these optimizations do not compromise security, this code (even the assembly language!) is undergoing formal verification by Galois.

Runtime in ms vs number of zk-SNARKs to be verified:

To improve the verification speed of multiple zk-SNARKs, Batch Verification was implemented. This is a technique that was described in the Zcash Specification Appendix B2, but hadn’t been used yet. This allows to reduce the number of Miller loops (the most expensive operation during verification) that need to be executed to decrease considerably when looking at multiple verifications at once.

SnarkPack and Batched

SnarkPack

Proofs Time (ms) Size (kB)
8 9 11.22
16 11 14.196
32 11 17.172
64 13 20.148
128 15 23.124
256 17 26.1
512 18 29.076
1024 21 32.052
2048 23 35.028
4096 28 38.004
8192 33 40.98
16384 58 43.956
32768 96 46.932
65536 242 49.908
131072 402 52.884

Batched

Proofs Time (ms) Size (kB)
8 3 1.536
16 3 3.072
32 5 6.144
64 7 12.288
128 12 24.576
256 21 49.152
512 38 98.304
1024 64 196.608
2048 117 393.216
4096 222 786.432
8192 435 1,572.864
16384 829 3,145.728
32768 1474 6,291.456
65536 2914 12,582.912
131072 6161 25,165.824

Even though Batch Verification helped, we needed faster verification, so we implemented SnarkPack. This allows us to aggregate many zk-SNARKs into a single combined proof. Not only does this optimization reduce verification time by a factor of more than 10x at scale — it also reduces chain bandwidth by reducing the average bytes-per-proof which must be submitted to the chain.

In order to accomplish this, we built on the research on the Inner Product Argument— and collaborated with the authors to extend it to support our needs without requiring a new trusted setup. We accomplished this by adapting the techniques to securely apply using two existing Powers of Tau trusted setups. This is a great example of how we have historically had to pick our way through obstacles to the practical realization of groundbreaking scale.

Below is the hardware we use to generate the future

Learn More

Explore:

Join our Community:

Acknowledgements

Thank you, folks! This is a collaborative effort. These are the people in no particular order that helped us achieve this: