買幣
支付方式為
市場
NFT
New
下載
English
USD
要聞
複製連結
建立圖片
更多

HashKey Capital深度解讀ZK(一):歷史原理與行業

HashKey Hub
2022-08-10 02:48
原文來源:HashKey Capital
當前區塊鏈行業裏零知識證明項目(ZKP)增速驚人,特別是ZKP在擴容和隱私保護兩個層面應用的崛起,令我們接觸到了各種花樣繁多的零知識證明項目。由於ZKP極富數學性的特質,對於加密愛好者來說,想要深度瞭解ZK的難度大幅提升。因此我們也希望從頭梳理ZKP理論和應用層面的一些變化,與讀者一起探索對於crypto行業的影響和價值——通過幾篇報告的形式共同學習,也作爲 HashKey Capital 研究團隊的思考總結。本篇是該系列的第一篇,主要介紹ZKP的發展歷史、應用和一些基本原理。

一、零知識證明的歷史

現代零知識證明體系最早來源於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,是非常快的理論到應用的結合。
2018 年的zk-STARKs (BBHR18)Scalable, transparent, and post-quantum secure computational integrity,提出了不需要可信設置的ZK-STARK算法協議,這也是目前ZK發展另一個讓人矚目的方向,也以此爲基礎誕生了StarkWare這個最重量級的ZK項目。
其他的發展包括PLONK、Halo2等也是極爲重要的進展,也對zk-SNARK做出了某些層面上的改進。

二、零知識證明的應用簡述

零知識證明最廣泛的兩個應用就是隱私保護和擴容。早期隨着隱私交易和幾個有名的項目Zcash和Monero等推出,隱私交易一度成爲非常重要的門類,但由於隱私交易的必要性並沒有業界希望的那樣突出,因此這一類代表性項目開始慢慢進入二三線的陣營(不是退出歷史舞臺)。而應用層面,擴容的必要性提升到無以復加,隨着以太坊2.0(已經改名叫consensus layer)在2020年轉變爲以rollup爲中心的路線,ZK系列正式又迴歸業界的視線,成爲焦點。
隱私交易:隱私交易有很多已經實現的項目,包括使用SNARK的Zcash,Tornado,使用bulletproof的Monero, 以及Dash。Dash嚴格意義上用的不是ZKP,而是一種簡單粗暴的混幣系統,只可以隱藏地址而不能隱藏金額,在此略過不表。
Zcash應用的zk-SNARKs交易步驟如下:
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都可以成立的話,隱私基本上不會成爲問題。
擴容:ZK的擴容可以在一層網絡上做,如Mina,也可以在二層網絡上做,即zk-roll up. ZK roll up的思路可能最早來自於Vitalik於2018的post,On-chain scaling to potentially ~500 tx/sec through mass tx validation。
ZK-rollup有兩類角色,一類是Sequencer, 還有一個是Aggregator。Sequencer負責打包交易,Aggregator負責將大量的交易合併並創造一個rollup, 並形成一個SNARK證明(也可以是基於其他算法的零知識證明),這個證明會和Layer1以前的狀態進行比較,進而更新以太坊的Merkle樹,計算新的狀態樹。
Source: Polygon
ZK rollup的優缺點:
優點:費用低,不像OP會被經濟攻擊,不需要延遲交易,可以保護隱私,快速達成最終性
缺點:形成ZK證明需要大計算量,安全問題(SNARK需要一個可信設置),不抗量子攻擊(SNARK, STARK可以),交易順序可能被改變
Source: 以太坊research
根據數據可用性以及證明的方法,Starkware對L2有一張經典的分類圖(Volition的數據可用層可以在鏈上和鏈下選擇):
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項目的重要貢獻者
簡要討論下EVM兼容性問題:
ZK系統和EVM的兼容一直令人頭疼,一般項目會在兩者間取捨。強調ZK的可能會在自己的系統裏做一個虛擬機,並有自己的ZK語言以及編譯器,但會加重開發者的學習難度,而且因爲基本上不開源,會變成一個黑箱子。一般業界目前是兩種選擇,一是和Solidity的操作碼完全兼容,另一種是設計一種新的虛擬機同時ZK友好併兼容Solidity。業界一開始也沒有想到可以這麼快的融合,但是近一兩年技術的快速迭代,讓EVM的兼容提升到一個新高度,開發者可以做到一定程度的無縫遷移(即以太坊主鏈到ZKrollup),是振奮人心的進展,這將影響ZK的開發生態和競爭格局。我們會在之後的報告中仔細討論這個問題。

三、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:證明者無法在不知道有效信息的情況下構建出一個參數和證明
對於證明者來說,在不知道證據(Witness,比如一個哈希函數的輸入或者一個確定 Merkle-tree 節點的路徑)的情況下,構造出一組參數和證明是不可能的。”
Groth16的zk-SNARK的證明原理和如下:
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的關係等。
點擊展開全文