(ZKP) 解析 Groth16 如何做到 Trustless

之前用 circom 實作 Groth16 都把 verifier.sol 部署到鏈上就完事了，最近想了一下第三方怎麼驗證 verifier.sol 跟電路的 binding，才發現原來 .zkey 也要公開，第三方才能驗證完整信任鏈。

好我知道這樣跳得有點快，讓我重新陳述一下問題是什麼，以及為什麼這樣解。

首先來點背景知識：

• ZKP 是指零知識證明，其概念為「在保密細節的情況下證明某陳述為真」
• Groth16 是一種 ZKP 的 proving system
• circom 是用來撰寫 Groth16 的 DSL，寫出來的程式稱為「電路」
• 高層次來說，circom 電路的輸入是 public input, private input 及 randomness，輸出是 proof 及 verifier.sol
• 透過 public input 以及 verifier.sol 可以對 proof 進行驗證

問題是，如果我寫了電路 A 跟電路 B，然後開源電路 A、部署 verifier B，並宣稱這兩個是一套的，接著我可以產生一堆 proof B 丟上鏈給 verifier B 驗證，然後再宣稱 proof B 通過電路 A 的驗證，別人要怎麼拆穿我？

前面已經回答了，解法就是公開 .zkey，這是 circom 運作流程中的一個產物。雖然 .zkey 動輒數 GB，但沒辦法，這是 Groth16 目前的限制。

在解釋為什麼公開 .zkey 可以解決問題之前，先來回顧整個 circom 流程是怎麼運作的，依照官方文檔一共分為幾個階段：

1. 撰寫電路
2. 編譯電路
3. 計算 Witness
4. 進行證明

以下是各步驟的指令、input 及 output

1. 撰寫電路

我們以最簡單的 *a b = c** 為例，其中 a, b 是 private input、c 是 public input。

先在空的根目錄加入一個 multiplier2.circom 檔案，並透過以下代碼建立一個名為 Multiplier2 的 template：

// multiplier2.circom

pragma circom 2.0.0;
  template Multiplier2() {
  signal input a;
  signal input b;
  signal output c;
  c <== a*b;
}

component main = Multiplier2();

2. 編譯電路

以下指令對 multiplier2.circom 進行編譯：

• --r1cs: 產生 R1CS (Rank-1 Constraint System) 描述電路邏輯，證明的時候會用到
• --wasm: 產生 multiplier2_js 目錄，裡面有 WebAssembly 腳本以及計算 witness 所需要的檔案

circom multiplier2.circom --r1cs --wasm
# Input: multiplier2.circom
# Output: multiplier2_js/*, multiplier2.r1cs

3. 計算Witness

首先進到 multiplier2_js

cd multiplier2_js

新增 input.json，自行定義 a, b (根據我們的電路，這兩個都是 private input)

{"a": "3", "b": "11"}

然後跑以下指令在根目錄產生 witness

node generate_witness.js multiplier2.wasm input.json ../witness.wtns
# Input: multiplier2_js/*, input.json
# Output: witness.wtns

4. 進行證明

這階段是最繁瑣的，也是最關鍵的部份。在進行 “proving” 之前，要進行 Phase 1 與 Phase 2 Trusted Setup。

Phase 1 Trusted Setup 稱為 Power of Tau，是通用的，可以直接到 PSE 的 Perpetual Powers of Tau 下載「相對應」的 .ptau 檔。根據官方說明：

”A phase-2-ready .ptau file is available for each power of 2 up to 28. When choosing a file, the best choice is generally the smallest file with a number of points > the number of constraints in the circuit.

這裡提到的 constraints 在編譯的時候可以看到，比如目前用的這個示範電路的 non-linear constraint 是 1 (linear constraint 經過 optimization 以後會變成 0，可以直接忽略)，.ptau 檔就要使用 Degree 2 (Number of Points = 4 > 1)

我們將下載下來的檔案放在根目錄，並命名為 ppot_0080_02.ptau。

Phase 2 Trusted Setup 是 Circuit-Specific，也就是每個電路都要各自進行一遍。下面這個指令會開始 phase 2：

snarkjs powersoftau prepare phase2 ppot_0080_02.ptau ppot_final.ptau -v
# Input: ppot_0080_02.ptau
# Output: ppot_final.ptau

然後以下指令根據電路的 R1CS 和前個指令的 output 初始化 .zkey 檔，此時的 .zkey 檔包含了 proving key 與 verification key。

注意：前面有提到 .zkey 檔案動輒多達數 GB，就是因為 .zkey 裡面的 proving key 是由 .r1cs 與 .ptau 結合而來。

snarkjs groth16 setup multiplier2.r1cs ppot_final.ptau multiplier2_0000.zkey
# Input: multiplier2.r1cs, pot12_final.ptau
# Output: multiplier2_0000.zkey

接下來進行一輪以上的 phase 2 contributions，把隨機性 (entropy) 注入 zkey 裡面。

注意：嚴格來說不是真正的隨機，而是建立在「至少一名參與者誠實拋棄 entropy， 使之成為 toxic waste」假設之上的隨機。

snarkjs zkey contribute multiplier2_0000.zkey multiplier2_0001.zkey --name="1st Contributor Name" -v
# Input: multiplier2_0000.zkey, (contribution)
# Output: multiplier2_0001.zkey

至此完成了 Trusted Setup，接下來才是真正的 proving 指令，這會使用到 .zkey 裡面的 proving key 以及第三步算出來的 witness：

snarkjs groth16 prove multiplier2_0001.zkey witness.wtns proof.json public.json
# Input: multiplier2_0001.zkey witness.wtns
# Output: proof.json public.json

proof.json 是 proof 本身，public.json 裡面則是 public input，驗證的時候會需要這兩個檔案加上 verification key。

前面有說，verification key 被包在 .zkey 檔，所以接下來根據我們要在鏈上或鏈下驗證 proof，有不同導出 verification key 的方式。

對於本地驗證，可以用 snarkjs zkey export verificationkey 導出 verification key 後，直接透過指令完成驗證：

snarkjs zkey export verificationkey multiplier2_0001.zkey verification_key.json
# Input: multiplier2_0001.zkey
# Output: verification_key.json

snarkjs groth16 verify verification_key.json public.json proof.json
# Input: verification_key.json, public.json, proof.json
# Output: boolean

對於鏈上驗證，要透過 snarkjs zkey export solidityverifier 從 .zkey 檔導出 verifier 合約，這份合約裡面會有 verification key：

snarkjs zkey export solidityverifier multiplier2_0001.zkey verifier.sol
# Input: multiplier2_0001.zkey
# Output: verifier.sol

將合約部署到區塊鏈以後，用以下指令將 public input 以及 proof 轉換成適當格式餵給合約：

snarkjs generatecall
# Input: public.json, proof.json
# Output Example: ["0x248a6b2d1d8c1d9b30fd44cb9bce77cfa790ebce28227f91fc753805df79a55e", "0x2ff71d911369492ac1adce524ea785fdb68503fb7b92ce3ebc6ce9104af7a058"],[["0x0cc63fddd190864cc6310f02dc6fea3510dc06dc3226b355feb0a97b579bfcb5", "0x04c8f09429642de4bfbb9ec59fa92b79db6be8831cb589d488b2c7d5c359f489"],["0x113409848ef7cfbe73d26eac18e50bcdad7df651ec7ba32eab39f1d03bea4ee5", "0x110a4b5a88802d49dd934bfae53d92538df11cb4d6d83fd09f09df7b89052b6b"]],["0x009cb74c655df4374125364f5068bd7c27882b2030f2aff94746939df36511f6", "0x0166d8c5fc9e9d299340f992b80da771dcbf872e8f8591993ea284c870b39e01"],["0x0000000000000000000000000000000000000000000000000000000000000021"]

總地來說可以整理成這張圖：

現在可以回答一開始的問題了：為什麼公開 .zkey 別人才能驗證你部署在鏈上的 verifier.sol 跟你所開源的電路之間的 binding？

因為 verifier.sol 是 verification key 的格式轉換，而 verification key 是 R1CS 經過 Trusted Setup 以後得到的，本質上就是電路與隨機 entropy 的疊加。

如果要用最原始的方法驗證 binding，可以讓第三方按照上述的流程 (編譯電路、計算 Witness、進行證明) 跑一遍，並比對最後的 verifier.sol 是否一樣。

問題是，根據 toxic waste 的假設，第三方無從得知你在 phase 2 trusted setup 所使用的 entropy；取得代之，circom 用 .zkey 紀錄了 R1CS 與 verification key 之間的關聯性。第三方可以用 snarkjs zkey verify 指令驗證 .r1cs 以及 .ptau 結合後的數學性質是否與 .zkey 中的數據吻合，然後再從 .zkey 導出 verifier.sol 與鏈上的合約進行比對。

snarkjs zkey verify multiplier2.r1cs ppot_final.ptau multiplier2_0001.zkey
snarkjs zkey export solidityverifier multiplier2_0001.zkey verifier.sol

snarkjs zkey verify 驗證通過會顯示 Zkey OK!

總地來說，公開 entropy 可以讓第三方直接驗證 R1CS 與 verification key 之間的關聯性，但基於安全考量，circom 實作中應拋棄 entropy，並公佈 .zkey 讓第三方可以間接驗證，這樣就完成整條 Groth16 的信任鏈了。