ZK8 - 简书

Zero knowledge Summit 8 on Sept 15, 2022

Demstifying zk programming

by Aleo

Record model: supoort zero-knowledge applications.

Decentralized private computations.

Account model: no concurrency, no privacy.

Pairing-friendly: BLS12-377

efficient Pedersen hashes: Edwards-BLS12

Univeal setup: Marlin.

Leo code -> Aleo instructions -> AVM bytecode

Github.com/AleoHQ

unfolding ZK hardware

ZKPs come in many shapes and form:

QuickSilver, Mystique, Wolverine, AntMan..
Ligero, Ligero++, BooLigero, Limbo...
Marlin, Nova, Groth16, Plonk

Production-ready ZK systems:

zkSync, Risco, Plonky2, Halo2, Aleo, SnarkVM, et al.

$MSM(x, G) = \sum_{j=0}^{n-1}x_jG_j$
Hardware-based products:

ZKPaaS: Proof as a service, running GPU/FPGA clusters
Cloud: ZK Attestation service
ZKP miner: Aleo

Generalizing AIR to multivariate domains

Polygon zero

Airpods: AIR -> Polynomials -> Multivariate

Namada: asset-agnostic interchain privacy

provide privacy to users in an interchain world.

Namada is a sovereign pos blockchain, using Tendermint BFT consensus.

MASP: multi-asset shielded pool.

Zcash, Namada, Penumbra, Aleo

Private bridges.

Hyperplonk: Plonk without FFTs and with high degree gates

Espresso:

New polynomial IOP
Plonk-based but using multi-linear polynomials defined over Boolean hypercube
support for all the nice PLONK features
- Custom gates (Turboplonk)
- Plookup (Ultraplonk)
- Halo2 arithmetization (access multiple rows)
No FFTs: Better parallelization/memory constraints
Support for high-degree custom gates

Multiset checks in STARK-based VMs

Polygon Miden

Multiset: A is mulltiset-equal to B(A=B) if B is a permutation of A.

Reduce multiset equality check to a grand product check.

Multiset checks can be used in STARK-based VMs to connect the main portion of the execution trace to specialized groups of columns in the trace that enable optimized handling of specific functionality, such as range checking or hashing.

Succinct verification of consensus with zkSNARKs

Succinct Labs

L1 bridgess built with multisigs or off-chain oracles are not secure.

A maximally secure and trust-minimized bridge.

Bridge security should be based on the same mechanism validators used to agree the state: verification of consensus.

ETH Consensus verification Smart Contrat.

Verifying consensus in a smart contract allows you to run a light client.

Verifying consensus -> access to valid block headers.
Block headers contain state roots which enable trustless verification of blockchain state.

Implementing consensus verification as a smart contract is generally very expensive & difficult.

Keeping track of current set of active validators and their stakes.
Verification of BLS12-381 validator signatures which don't have precompiles on the EVM.

Introducing the sync committee: easy-to-verify consensus for light-clents on Ethereum

The sync committee is a group of 512 validators chosen randomly every 27 hours.
Validators sign every block header. If enough validators sign off on the header, the block header is valid.
The sync committee provides weaker security guarantees that full consensus itself.
Even verifying the consensus on-chain is too gas-expensive.
- Store 512 validator BLS pubkeys on-chain every 24 hours.
- For every desired header, have to compute up to 512 curve additions and 1 paring.
- No precompiles for the BLS12-381 curve on EVM.

zero knowledge proofs for a succinct on-chain light client

def validate_new_block():
   other_stuff()
   verify_validators()
   verify_bls_signatures()

def validate_new_block()
  other_stuff()
  verify_groth16_proof()

Proof of consensus: use zkSNARKs to generate a validity proof of the state of a chain according to its consensus protocol.

Aggregated BLS signature verification proof (every update)
Sync committee SSZ proof (every 27 hours update sync committee validators)
Light client contract

www.succinct.xyz

Zooming out: pros and cons of proof-based bridges

Pros:

Higher security guarantess
Censorship resistant
More decentralized

Cons:

Higher gas costs
Higher latency
Have to implement new SANRKs for different consensus algorithms.

zkEVM: compatibility and equivalence

by zkSync

Zk: the only tech for infinite scalability

compatibility => full equivalence

sourcecode -> bytecode-> 100% API -> Gas calc -> block root

performance: better -> worse

Type 4: compiled into RISC

Solidity -> Yul -> LLVM -> zkVM (RISC)

Main pros:

Lowest cost per tx
Experimentatiion for better UX and DevEx.

Main cons:

Opcode-level tools (debuggers + tracers) require reimplementation.

Type 1-3: solidity -> EVM (CISC)

How to build a private DEX

by Penumbra

penumbra is :

private pos L1
Cross-chain shielded pool
private dex

Shielded swaps are live on penumbra testnet 29

penumbra.zone

Tiered Merkle Topiary in Rust

by Penumbra

On a shielded blockchain, every client need to sysnc their state fragment, ZK-friendly hash fucntions are slow in software, so sync times suffer. The Tiered Commitment tree allows fast-forwarding clinet sync by up to 4 million times compared to an unoptimized Merkle tree.

Poseidon hash is SNARK-friendly, but slow in software

State sync effort should scale with only your own activity.

Tiered commitment tree.

Caulk: lookup arguments in sublinear time

membership proofs

lookup tables

range proofs

Github.com/caulk-crypto/caulk

how to build a zk-VM

by neptune/triton VM

Steps:

VM
STARK engine

Step 1: virtual machine

Program ROM: Address | Instruction (or Arguments)
Processor Layout: CLK | IP | CI | ARG | MEMP | MEM_0 | MEM_1
Instruction set: increase, toggle_memp, jmp_if_zero, halt

step 2: stark engine

Algebraic execution tables
Arithmetic intermediate representation
STARK

Hasse's theorem about elliptic curves

by Aztec - Ariel Gabizon

Hasse's thm: $|p + 1 -N|\leq 2\sqrt{p}$

A new ZK nullifier signature for ECDSA

by Aayush Gupta - 0xPARC

Anonymous Aridrops using zk proofs

Stealthdrop.xyz

Motivation:

zk airdrop
message borad
anon voting
sybil resistant anon application

Desired property:

unique
deterministic
verifiable without secret key
Noninteractive

we want a deterministic function of a user's secret key, that can be verified with ouly their public key and keeps them anonymous.

Github.com/zk-nullier-sig

Vampire: a new succinct zkSNARK

by Michal

counting vampires: from univariance sumcheck to updatable ZK-SNARK

Vampire proof size: $4\mathbb{G}_1 + 2\mathbb{F}$ ， 2048 bytes.

Https://ia.cr/2022/406

Poseidon VM: A zkApp with EVM compatibility

by Poseidonlabs

Poseidon VM, a blockchain VM designed to support application by ZK with applications on privacy, scaling and verifiability with cheap transaction cost.

Poseidon VM includes primitives such as privacy preserving assets (zkAsset), configurable asset disclosure (CAD), zero-knowledge signal (semaphore).

The primitives is designed in a modular and composable manner so that aApp developers can program powerful applications such as privacy preserving decentralized exchanges, makerplaces for private NFTs, private DAO payroll system and many more using pure Solidity or any EMV compitable languages.

ZK application landscape:

privacy: zcash, manta, Aleo, ZKOPRU, Aztec, Espresso

Scaling: zkSync, scorll, polygon hermez

Attestation/oracle: SISMO, zkAttestor, Hyper Oracle