當前區塊鏈行業裡零知識證明項目（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）用來生成公鑰和私鑰
- Minting Coins 階段，生成新幣的數量。公共地址和幣的 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
目前市場上最有競爭力的 ZK rollup 項目有：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 的兼容提升到一個新高度，開髮者可以做到一定程度的無縫遷移（即以太坊主鏈到 ZK rollup），是振奮人心的進展，這將影響 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
步驟是：
- 將問題轉換爲電路
- 將電路拍平成 R1CS 的形式.
- R1CS 轉換成 QAP（Quadratic Arithmetic Programs）形式
- 建立 trusted setup, 生成隨機參數，包括 PK (proving key)，VK(verifying key)
- zk-SNARK 的證明生成和驗證
下一篇我們將開始研究 zk-SNARK 的原理、應用，通過幾個案例來透視 ZK-SNARK 的髮展，併探索它與 zk-STARK 的關繫等。
聲明：
- 本文轉載自[HashKey Capital]，著作權歸屬原作者[HashKey Capital]，如對轉載有異議，請聯繫Gate Learn團隊，團隊會根據相關流程盡速處理。
- 免責聲明：本文所錶達的觀點和意見僅代錶作者個人觀點，不構成任何投資建議。
- 文章其他語言版本由Gate Learn團隊翻譯， 在未提及Gate.io的情況下不得覆製、傳播或抄襲經翻譯文章。
แชร์
บทความที่เกี่ยวข้อง
什麼是穩定幣 USDT？
當前區塊鏈行業裡零知識證明項目（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）用來生成公鑰和私鑰
- Minting Coins 階段，生成新幣的數量。公共地址和幣的 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
目前市場上最有競爭力的 ZK rollup 項目有：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 的兼容提升到一個新高度，開髮者可以做到一定程度的無縫遷移（即以太坊主鏈到 ZK rollup），是振奮人心的進展，這將影響 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
步驟是：
- 將問題轉換爲電路
- 將電路拍平成 R1CS 的形式.
- R1CS 轉換成 QAP（Quadratic Arithmetic Programs）形式
- 建立 trusted setup, 生成隨機參數，包括 PK (proving key)，VK(verifying key)
- zk-SNARK 的證明生成和驗證
下一篇我們將開始研究 zk-SNARK 的原理、應用，通過幾個案例來透視 ZK-SNARK 的髮展，併探索它與 zk-STARK 的關繫等。
聲明：
- 本文轉載自[HashKey Capital]，著作權歸屬原作者[HashKey Capital]，如對轉載有異議，請聯繫Gate Learn團隊，團隊會根據相關流程盡速處理。
- 免責聲明：本文所錶達的觀點和意見僅代錶作者個人觀點，不構成任何投資建議。
- 文章其他語言版本由Gate Learn團隊翻譯， 在未提及Gate.io的情況下不得覆製、傳播或抄襲經翻譯文章。
บทความที่เกี่ยวข้อง
什麼是穩定幣 USDT？