一級標題
一級標題
一、零知識證明的歷史
現代零知識證明體系最早來源於Goldwasser、Micali 和Rackoff合作發表的論文：The Knowledge Complexity of Interactive Proof Systems（即GMR85），該論文提出於1985年，發表於1989年。這篇論文主要闡釋的是在一個交互系統中，經過K輪交互，需要多少知識被交換，從而證明一個證言（statement）是正確的。如果可以讓交換的知識為零，則被稱之為零知識證明。這裡面會假設證明者（prover）具有無限資源，而驗證者（verifer）只具有有限資源。而交互式系統的問題在於證明不完全是數學上可證的，而是概率意義上正確的，雖然概率很小(1/2^n)。
所以交互式系統並不完美，只有近似完備性，以此為基礎誕生的非交互式系統（NP）系統則具有完備性，成為零知識證明系統的完美所選。
早年的零知識證明系統在效率以及可用性方面都有所欠缺，所以一直都停留在理論層面，直到最近10年才開始蓬勃發展，伴隨著密碼學在crypto成為顯學，零知識證明走向台前，成為至關重要的一個方向。特別是發展出一個通用的、非交互的、證明大小有限的零知識證明協議，是其中最關鍵的探索方向之一。
基本上零知識證明就是要在證明的速度、驗證的速度和證明體積的大小之間做取捨，理想的協議是證明快、驗證快、證明體積小。
零知識證明最重要的突破是Groth在2010年的論文Short Pairing-based Non-interactive Zero-Knowledge Arguments，也是ZKP裡面最重要的一組zk-SNARK的理論先驅。
零知識證明在應用上最重要的進展就是2015年Z-cash使用的零知識證明系統，實現了對交易及金額隱私的保護，後來發展到zk-SNARK和智能合約相結合，zk-SNARK進入了更為廣泛的應用場景。
在此期間，一些重要的學術成果包括：
2013 年的Pinocchio (PGHR13)：Pinocchio: Nearly Practical Verifiable Computation，將證明和驗證時間壓縮到適用範圍，也是Zcash使用的基礎協議。
2016 年的Groth16：On the Size of Pairing-based Non-interactive Arguments，精簡了證明的大小，並提升了驗證效率，是目前應用最多的ZK基礎算法。
2017 年的Bulletproofs (BBBPWM17)Bulletproofs: Short Proofs for Confidential Transactions and More，提出了Bulletproof算法，非常短的非交互式零知識證明，不需要可信的設置，6個月以後應用於Monero，是非常快的理論到應用的結合。
一級標題
一級標題
二、零知識證明的應用簡述
零知識證明最廣泛的兩個應用就是隱私保護和擴容。早期隨著隱私交易和幾個有名的項目Zcash和Monero等推出，隱私交易一度成為非常重要的門類，但由於隱私交易的必要性並沒有業界希望的那樣突出，因此這一類代表性項目開始慢慢進入二三線的陣營（不是退出歷史舞台）。而應用層面，擴容的必要性提升到無以復加，隨著以太坊2.0（已經改名叫consensus layer）在2020年轉變為以rollup為中心的路線，ZK系列正式又回歸業界的視線，成為焦點。
圖片描述
圖片描述
Source: Demystifying the Role of zk-SNARKs in Zcash
System setup階段生成證明秘鑰（加密證明多項式）和驗證秘鑰，借助KeyGen function
CPA階段ECIES加密方法（Elliptic Curve Integrated Encryption Scheme）用來生成公鑰和私鑰
MintingCoins階段，生成新幣的數量。公共地址和幣的commitment
Pouring階段，生成zk-SNARK證明，證明被加到了pour交易賬本中
Verification階段，驗證者驗證Mint和Pour的交易量是否正確
Receiving階段，receiver接收幣。如果想使用收到的幣，則繼續調用Pouring，形成zk-SNARK驗證，重複上述4-6的步驟，完成交易。
Zcash使用零知識還是有局限性的，就是其基於UTXO, 所以部分交易信息只是被shield了，而不是真正的掩蓋。因為其基於比特幣的設計的單獨網絡，所以難以擴展（和其他應用結合）。真正使用shielding（即隱私交易）的使用率只有不到10%，說明隱私交易並沒有很成功的擴展。 （from 2202）
Tornado使用的單一大混幣池更加通用，而且基於以太坊這樣“久經考驗”的網絡。 Torndao本質上就是一個用了zk-SNARK的混幣池，可信設置基於Groth 16的論文。 Tornado Cash可以提供的特性包括：
只有被存進去的coin可以被提取
沒有幣可以被提取兩次
證明過程和幣的廢止通知（Nullifier）是綁定的，相同證明但不同Nullifier的哈希不會允許提幣
安全性有126-bit的安全，不會因為composition而降級
Vitalik提到過，和擴容相比，隱私相對比較容易實現，如果一些擴容的protocol都可以成立的話，隱私基本上不會成為問題。
圖片描述
圖片描述
Source: Polygon
ZK rollup的優缺點：
圖片描述
圖片描述
Source: 以太坊research
圖片描述
Source: Starkware
目前市場上最有競爭力的ZKrollup項目有：Starkware的StarkNet，Matterlabs的zkSync和Aztec的Aztec connect，Polygon的Hermez和Miden，Loopring，Scroll等
基本上技術路線就在於SNARK(及其改進版本)和STARK的選擇，以及對EVM的支持（包括兼容還是等同）。
Aztec開發了通用化的SNARK協議-Plonk協議，運行中的Aztec3可能會支持EVM，但是隱私優先於EVM兼容
Starnet 用的是zk-STARK，一種不需要可信設置的zkp，但是目前不支持EVM，有自己的編譯器和開發語言
zkSync也是用的plonk，支持EVM。 zkSync 2.0是EVM兼容的，有自己的zkEVM
Scroll， 一種EVM兼容的ZK rollup, 團隊也是以太坊基金會zkEVM項目的重要貢獻者
一級標題
一級標題
三、ZK SNARK實現的基本原理
Goldwasser、Micali和Rackoff 提出了零知識證明有三個性質：
完整性（Completeness）：每一個擁有合理見證的聲明（statement），都是可以被驗證者驗證的
可靠性（Soundness）：每一個只擁有不合理見證的聲明，都不應該被驗證者驗證
零知識（Zero-knowledgeness）：驗證過程是零知識的
所以為了了解ZKP, 我們從zk-SNARK開始，因為很多目前的區塊鏈應用都是從SNARK開始。首先，我們先了解一下zk-SNARK。
zk-SNARK的意思是：零知識證明（zh-SNARK）是zero-knowledge Succint Non-interactive ARguments of Knowledge。
Zero Knowledge：證明過程零知識，不會暴露多餘信息
Succinct：驗證體積小
Non-interactive：非交互過程
ARguments：計算具備可靠性，即有限計算能力的證明者不能偽造證明，無限計算能力的證明者可以偽造證明
of Knowledge：證明者無法在不知道有效信息的情況下構建出一個參數和證明
圖片描述
圖片描述
Source： https://learnblockchain.cn/article/3220
步驟是：
1. 將問題轉換為電路
2. 將電路拍平成R1CS的形式.
3. R1CS轉換成QAP（Quadratic Arithmetic Programs）形式
4. 建立trusted setup, 生成隨機參數，包括PK (proving key)，VK(verifying key)
5. zk-SNARK的證明生成和驗證
下一篇我們將開始研究zk-SNARK的原理、應用，通過幾個案例來透視ZK-SNARK的發展，並探索它與zk-STARK的關係等。
Reference：
https://ethresear.ch/t/on-chain-scaling-to-potentially-500-tx-sec-through-mass-tx-validation/3477
https://blog.polygon.technology/zkverse-why-zero-knowledge-rollups-need-a-new-consensus-mechanism/
https://blog.decentriq.com/zk-snarks-primer-part-one/
