Filecoin — How storage replication is proved using zk-SNARK?

Lotus overall modules

  1. Lotus Blockchain part — Implement blockchain-related logic (consensus algorithms, P2P, block management, virtual machine, etc.). Note that Lotus’s blockchain-related data is stored on IPFS. The part is implemented by Go language implementation.
  2. RUST-FIL-PROOF part — Implements Sector storage and proving. That is FPS (Filecoin Proving Subsystem). The part is implemented by Rust language implementation.
  3. Bellman part — Zero-knowledge proof (zk-SNARK) proof system, mainly based on BLS12_381 elliptic curve and realizes Groth16’s zero-knowledge proof system. Lotus officially recommends Nvidia’s 2080ti graphics card, which also mainly speeds up performance in this part. The part is implemented by Rust language implementation.

Stacked DRG

Before explaining the specific logic, introduce two basic terms: one is Stacked DRG and the other is Sector. Sector is relatively simple, it is a unit of data processing. Anyone who knows the structure of the hard disk knows that the smallest storage unit of the hard disk is called “Sector”. The sector used by Lotus is relatively large, 32G for Lotus test network.

from paper of “Tight Proofs of Space and Replication”
  1. Each node of Stacked DRG and each layer do not use “Zig Zag” liked dependencies. In other words, the dependency relationship between each node and other nodes is fixed.
  2. Stacked DRG addes node dependencies between each layer.

Sector Precommit Phase

Sector processing, which is the legendary precommit phase, is mainly composed of the following steps:

Sector Commit Phase

After Sector precommit, the processed data needs to be “proved”. After all, all processed data cannot be submitted to the blockchain. Lotus uses Bellman’s zero-knowledge proof library and uses Groth16 algorithm for data processing proof. The related logic components are as follows:

Proof on-chain verification

Totally, the data submitted to the chain includes comm_d, comm_r and proof proof data. The miner smart contract on the chain will verify that the submitted proof is correct:

Summary

Filecoin(Lotus) uses the Stacked DRG algorithm to replicate data, and uses the Groth16 zero-knowledge proof algorithm to prove the data is processed correctly. Lotus’s zero-knowledge proof proves that the randomly selected 500 node data in one replica is correctly generated by the Stacked DRG algorithm, and can generate the roots of the specified Merkel trees. Lotus’s circuit logic is relatively large and the circuit scale has reached 100 million. Proof generation is also very long, more than 2 hours with server-end CPU and more than 1 hour with Nvidia 2080ti GPU .

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Trapdoor-Tech

Trapdoor-Tech

Trapdoor-Tech tries to connect the world with zero-knowledge proof technologies. zk-SNARK/STARK solution and proving acceleration are our first small steps :)