zk

Series ZK - Introduction

Principle

ZK is solving a problem of proving, not calculation.

• Transform normal problems into a polynomial problems.
  • zk-SNARK: Convert the problem of proving that a CI statement holds into a problem of proving that a polynomial equation holds.
  • zk-STARK: Converts the problem of proving that a CI statement holds into a problem of proving that a polynomial is less than a certain degree.
• Transfor normal problems into a set problems.
  • Bulletproofs: range proofs, settings, etc.

Statement

• A standard ZK-proof for the statement:
  $$st:\{(a, b, c, ...; x, y, z, ...) : f(a, b, c, ...; x, y, z, ...)\}$$
  means that the prover shows knowledge of x, y, z, . . . such that f(a, b, c, . . . , x, y, z, . . .) is true, where a, b, c, . . . are public variables. We use st[a, b, c, . . .] to denote an instance of st where the variables a, b, c, . . . have some fixed values.
• Example
  

Circle

• R1CS
• Rank-1 Constraint System
  

Easy for algebraic operations, but hard for logical operations.

Sulotuion

zk-SNARK and zk-STARK permeate almost everything zero-knowledge in blockchain.

• Differences between zk-SNARK and zk-STARK:
  • Trusted setup: SNARK
  • Size(gas cost): SNARK < STARK
  • Quantum resistant: STARK
• Details of zk-SNARK
• Details of zk-STARK

Bulletproofs is used in some cases:

• $\sum$-Bullets

Engineering

• Circom: solidity
• Bellman: Rust
• zkMove: Move

Application

Note that what ZK could do currently can all be done engineeringly better by hardware based TEE, e.g., SGX. But ZK seems to be still believed as the future by most Web3ers. We are not sure whether it's promoted by technology trend or just by risk ventures, but anyway, the technology part is still beautiful.

Privacy

• private payment system
• Privacy-Cross-Chain-Demo

Rollup

Note that the Rollup implemented based on zk can be considered as an instance of VC(verifiable computation), which is general capacity expansion. Another instance of VC is TEE(Trusted Execution Environment), one implementation of which is Intel SGX. Intel SGX is based on hardware and has a high performance in engineering, but it depends on the centralized certificate of Intel company. Actually the certificate can be decentralized by a MPC method.

Projects

• scroll: Rollup, GPU
• StarkNet(StarkWare): Rollup
• Aleo: Privacy
• zkEVM(zksync): Rollup
• Zether: Smart contract based privacy trading

Reference

• Why And How ZkSnark Works