Powering Filecoin

zk-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 statment, 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

13K
Winning PoSt per day
72k
Window PoSt per day
7.1m
PoREP per day
2.8k
Active miners
8.2
EiB

Statistics

The baseline

Powers of Tau /
Trusted Setup

Zcash's supported amount of constraintsA smaller square with an arrow illustrating the amount of constraints Zcash supports

Zcash

2,097,152

Filecoin's supported amount of constraintsA square with an arrow illustrating the amount of constraints Filecoin supports

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.

Use the parallelism

GPU based prover

GPU based prover's line chartGPU based prover's line chartGPU based prover's line chartGPU based prover's line chartGPU based prover's line chart

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-loading 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.

Assembly to the rescue

blst

blst's horizontal bar chartblst's horizontal bar chart
  • Colored square associated with the paired dataset

    paired

  • blstrs

    Colored square associated with the blstrs dataset

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.

Stronger together

Groth16 Batch Verification

Groth16 Batch Verification's line chartGroth16 Batch Verification's line chart
  • Colored shape associated with the Single dataset

    Single

  • Colored shape associated with the Batched dataset

    Batched

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.

Pack ’em tighter

SnarkPack

SnarkPack's line chartSnarkPack's line chart
  • SnarkPack
  • Batched
  • Time
  • Size of Proof
SnarkPack
ProofsTime (ms)Size (kB)
8911.22
161114.196
321117.172
641320.148
1281523.124
2561726.1
5121829.076
10242132.052
20482335.028
40962838.004
81923340.98
163845843.956
327689646.932
6553624249.908
13107240252.884
Batched
ProofsTime (ms)Size (kB)
831.536
1633.072
3256.144
64712.288
1281224.576
2562149.152
5123898.304
102464196.608
2048117393.216
4096222786.432
81924351,572.864
163848293,145.728
3276814746,291.456
65536291412,582.912
131072616125,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.

Our hardware

Below is the hardware we use to generate the future
CPU
AMD Ryzen Threadripper 3970X
RAM
256 GB
GPU
GeForce RTX 3090

Learn More

More on zk-SNARKs and blockchain

Be part of the world of cryptocurrencies technology

Acknowledgements

Thank you, folks!

This is a collaborative effort.
These are the people in no particular order that helped us achieve this.
  • R. Gennaro, C. Gentry, B. Parno and M. Raykova for their work on QAPsDownload file icon
  • P. Baretto, B. Lynn and M. Scott for their work on BLSDownload file icon
  • B. Bünz, M. Maller, P. Mishra, N. Tyagi and P. Vesely for their work on Inner Pairing ProductsDownload file icon