動手實做零知識 - circom

零知識證明在過去一年越來越廣為人知，去年(2019)也有越來越多的專案是基於零知識證明。前年底提出的 zk rollup，目前由 Matter Labs 在開發，Matter Labs更在上個月（2019/12）發表了 ZK Sync，解決了因為產生證明（proof）而延伸的延遲問題。此外 Iden3 跟 ConsenSys 也有 zk rollup 的專案。在以太坊研究論壇有基於 zk rollup 所衍生的匿名 zk rollup。Semaphore是一個基於零知識證明的一個訊號系統，發送者可以不揭露身份的狀況下廣播任何訊息(an arbitrary string)。Semaphorejs 延續 Semaphore 的核心概念，並將整個概念更加完整化，從前端網頁到後端服務。這兩年才發表的 zk-STARKs，也在去年年初跟 0x 合作，推出基於 zk-STARKs 的去中心化交易所。

在技術上，去年下半年有新的論文，使用 DARK compiler 可以讓 SNARKs 達到公開性（Transparent）。還有 MARLIN, SONIC, PLONK 等可通用且可更新的可信設定（trusted setup）。STARKs 的 FRI 驗證方式也默默地跟 SNARKs 做結合。（東西越來越多，根本看不完 QQ）

這篇文章沒有要談高深的技術，只會介紹實做所需的知識。這篇會使用到 Iden3 所開發語言 circom 來幫助寫算數迴路 。藉由 circom，可以更輕鬆地實做零知識證明的程式。但在開始之前，先介紹一些基本觀念。

算數迴路

在實做零知識程式跟一般撰寫程式不同，需要先把問題轉成迴路，才去執行（實際上是把問題轉成多項式再轉成迴路）。舉例來說，一個多項式 $x^3 + x +5$，會轉成像這樣的迴路

sym_1 = x * x       // sym_1 = x^2
sym_2 = sym_1 * x   // sym_2 = x^3
y = sym_2 + x       // y = x^3 + x
~out = y + 5

而 circom 就是一個將我們寫的邏輯（程式）轉成迴路的工具，不需要自己處理迴路。若你證明的內容需要雜湊或是簽章，circomlib 已經有實做一些基本使用的函數。

產生/驗證證明

使用SNARKs產生證明前需要先產生可信設定（trusted setup），可信設定的產生會需要迴路邏輯及亂數。設置完成後會產生證明鑰匙（proving key）跟驗證鑰匙（verification key），故名思義，一個是產生證明時需要的，另一個則是驗證所需要的（這兩把鑰匙跟橢圓曲線的公私鑰是不一樣的）。
* 建立可信設定是一門學問，有興趣可以參考 ZCash 可信設定的儀式。

建立完兩把鑰匙後，就可以來產生證明啦！

資訊有兩種- 公開跟私有的。舉例來說，A 轉帳給 B，礦工要確認 A 的餘額是足夠的，但是 A 不想透露自己有多少錢，那 A 帳戶的錢就是私有資訊，也稱做證據（witness）。而公開資訊可以是 A、B 的地址或是實際轉帳的金額，依照自己系統的設計。

接著，證明者就拿著證明鑰匙、公開資訊跟證據（witness）產生證明（proof）。

最終，就是驗證啦！

驗證者，拿著公開資訊、證明跟驗證鑰匙，就可以確認證明是否為真。

Circom 101

首先，介紹 circom 的語法。根據官方說法，circom結合了是 js 跟 c 的語法。有 for, while, if, 陣列,  >> 等。 

下面是一個用 circom 寫的範例。假設 x, y 是秘密（也就是witness），在不能公開的狀況下，證明 (x * y) + z == out（z, out 為公開資訊）。若 out = 30, z = 10，可以得到 (x * y) = 20，但無法知道 x, y 各為多少。

template add() {     signal private input x;     signal private input y;     signal input z;     signal output out;     out <== (x * y) + z; } component main = add();

signal：代表此變數要轉換成迴路，有以下屬性：  

  private：私有的資訊（witness），若沒指定，則皆為公開資訊。

  input：輸入

  output：輸出

template：代表函數的宣告，像是 Solidity 的 function，或是 golang 的 func。
component：官方沒有正式解釋這個關鍵字。使用情境是在於承接函數、對函數內的 signal 變數作操作，可以想作是一個物件，而 signal 變數則為 class 的公開成員變數。

在 circom 比較特別的是，關於 signal 的操作有另一組的操作符號

<==, ==>：給予 signal 變數值，並且建立一個迴路的約束。

<--, -->：給予 signal 變數值。

===：建立一個迴路的約束。

所以，<==： <-- + ===

這些是在寫 cricom 程式前需要先知道的關鍵字。

Circom 指令

第一步，編譯剛寫好的 circom 檔案，編譯完後會產出迴路 circuit.json。

circom sample1.circom

第二步，建立可信設定，建立完後會產生 proving_key.json 跟 verification_key.json。（指定groth 這個方法）

snarkjs setup --protocol groth

第三步，產生證據（witness）。這步驟需要有輸入值，建立 input.json 將輸入值以 json 格式寫入。完成後會產生 witness.json。

// input.json {"x":3, "y":5, "z": 100}

產生證據

snarkjs calculatewitness

最後，產生證明。成功後，會產生 proof.json、public.json。public.json 中會放公開資訊。

// public.json {   "115", // --> out   "100" // --> z:100 }

產生證明

snarkjs proof

成功後，會產生 proof.json。要驗證的話直接呼叫verify。

snarkjs verify

 以上就是 circom 的基本指令。下面來介紹一個進階一點的範例，來瞭解實際上如何使用 circom 來寫零知識的程式。

範例

這裡的範例，我們來練習寫 zk rollup！

zk rollup 是 layer 2 解決方案，和以往的 layer 2 不同，zk rollup 直接將資料放在鏈上，透過 zk-SNARKs 做驗證，所以沒有繁複的挑戰程序。zk rollup 將使用者的地址紀錄在合約中，使用 merkle tree 的索引值（3 bytes）來替代原本位址（以太坊的地址為20 bytes）。藉由資料量的減少，來增加交易速度。更多細節可以參考之前的文章。

為了讓範例容易理解，這邊簡化很多細節。（這個範例是參考 ZKRollup Tutorial）
首先，有一顆紀錄帳號的 merkle tree，帳號內容包含了（公鑰, 餘額）。每筆的交易內容為（發送者索引值, 接收者索引值, 金額）。而驗證流程如下

1. 驗證 發送者 是否存在（藉由驗證 merkle root）
2. 驗證 發送者 的簽章
3. 改變 發送者 的 餘額，並確認 merkle root
4. 增加 接收者 的 餘額，並更新 merkle root

0. 變數宣告

// account tree signal input account_root; signal private input account_pubkey[2]; signal private input account_balance; // new account root after sender's balance is updated signal private input new_sender_account_root; // tx signal private input tx_sender_pubkey[2] signal private input tx_sender_balance signal private input tx_amount signal private input tx_sender_sig_r[2] signal private input tx_sender_sig_s signal private input tx_sender_path_element[levels] signal private input tx_sender_path_idx[levels] signal private input tx_receiver_pubkey[2] signal private input tx_receiver_balance signal private input tx_receiver_path_element[levels] signal private input tx_receiver_path_idx[levels] // output new merkle root signal output new_root;

這裡幾乎所有的變數都是私有的，從公鑰、餘額到簽章等等，只有帳號的 merkle root 跟帳號更新後的 merkle root 為公開資訊。而 path_element 是形成 merkle root 的中繼值，而 path_idx 是這個帳號在樹中每一層的位置（只有分左右，左為0、右為1，最終路徑會像二進位字串 001011）。

1. 驗證 發送者 是否存在

//__1. verify sender account existence component senderLeaf = HashedLeaf(); senderLeaf.pubkey[0] <== tx_sender_pubkey[0]; senderLeaf.pubkey[1] <== tx_sender_pubkey[1]; senderLeaf.balance <== account_balance; component senderExistence = GetMerkleRoot(levels); senderExistence.leaf <== senderLeaf.out; for (var i=0; i<levels; i++) { senderExistence.path_index[i] <== tx_sender_path_idx[i]; senderExistence.path_elements[i] <== tx_sender_path_element[i]; } senderExistence.out === account_root;

從第一行 component senderLeaf = HashedLeaf(); 可以看到 component 的用法，senderLeaf 承接了函數 HashedLeaf() ，使用了 <== 給予公鑰及餘額的值，並建立迴路約束。而雜湊過的結果為 senderLeaft.out。
這段代碼的意思為，先將公鑰及餘額做雜湊，作為 merkle tree 的樹葉。接著跟 merkle tree 的中繼值做計算，得到一個 merkle root（senderExistence.out）。最終確認計算的 merkle root 是否跟代入的（account_root）一樣。
這裡跳過計算 merkle root 跟雜湊的細節，先當作一個函數呼叫。對實做細節有興趣的可以直接看 HashedLeaf 實做及 GetMerkleRoot 實做。

2. 驗證 發送者 的簽章

//__2. verify signature component msgHasher = MessageHash(5); msgHasher.ins[0] <== tx_sender_pubkey[0]; msgHasher.ins[1] <== tx_sender_pubkey[1]; msgHasher.ins[2] <== tx_receiver_pubkey[0]; msgHasher.ins[3] <== tx_receiver_pubkey[1]; msgHasher.ins[4] <== tx_amount component sigVerifier = EdDSAMiMCSpongeVerifier(); sigVerifier.enabled <== 1; sigVerifier.Ax <== tx_sender_pubkey[0]; sigVerifier.Ay <== tx_sender_pubkey[1]; sigVerifier.R8x <== tx_sender_sig_r[0]; sigVerifier.R8y <== tx_sender_sig_r[1]; sigVerifier.S <== tx_sender_sig_s; sigVerifier.M <== msgHasher.out;

這步是在驗證，交易是否為發送者的送出的。實做是先將訊息做雜湊，雜湊完再驗證簽章。跟上一段很類似，都是呼叫函數，所以不多做解釋。
（SNARKs 中使用的簽章方式不是一般的ECDSA，用的是EdDSA，因為迴路複雜度較低。）

3. 改變 發送者 的 餘額，並確認 merkle root

//__3. Check the root of new tree is equivalent component newAccLeaf = HashedLeaf(); newAccLeaf.pubkey[0] <== tx_sender_pubkey[0]; newAccLeaf.pubkey[1] <== tx_sender_pubkey[1]; newAccLeaf.balance <== account_balance - tx_amount; component newTreeExistence = GetMerkleRoot(levels); newTreeExistence.leaf <== newAccLeaf.out; for (var i=0; i<levels; i++) { newTreeExistence.path_index[i] <== tx_sender_path_idx[i]; newTreeExistence.path_elements[i] <== tx_sender_path_element[i]; } newTreeExistence.out === new_sender_account_root;

前兩步驗證完發送者資訊後，這步就是將餘額做更新，重新計算 merkle root。最後一行 newTreeExistence.out === new_sender_account_root; 會驗證更新完的 merkle root 是否正確，new_sender_account_root 為發送者所代入的新的 merkle root。

4. 增加 接收者 的 餘額，並更新 merkle root

//__5. update the root of account tree component newReceiverLeaf = HashedLeaf(); newReceiverLeaf.pubkey[0] <== tx_receiver_pubkey[0]; newReceiverLeaf.pubkey[1] <== tx_receiver_pubkey[1]; newReceiverLeaf.balance <== tx_receiver_balance + tx_amount; component newReceiverTreeExistence = GetMerkleRoot(levels); newReceiverTreeExistence.leaf <== newReceiverLeaf.out; for (var i=0; i<levels; i++) { newReceiverTreeExistence.path_index[i] <== tx_receiver_path_idx[i]; newReceiverTreeExistence.path_elements[i] <== tx_receiver_path_element[i]; } new_root <== newReceiverTreeExistence.out;

最後，更新接受者的餘額資訊，重新計算 merkle root 並輸出。

zk rollup 是集中多筆如上的交易，產生單一的證明（proof），藉此減少交易資料。這邊的範例為了好解釋，只有單筆的交易。可以參考完整的代碼。這裡也有其他 circom 的使用範例。

總結

撰寫 circom 程式，常用的雜湊、簽章或是 merkle tree，在 GitHub 上都有人實做了，所以使用上比較像是呼叫不同的函數，來完成自己想要的邏輯/驗證，像組積木一樣。從撰寫的方面來看並不困難（雖然沒有文件，常常要直接看code），比較難的地方在於，部分運算是牽涉到密碼學，對工程背景的人來說比較吃力。另外，雜湊函數的選擇也相當重要，要怎麼減少迴路的複雜度，但又能確保足夠的安全性，也是一門學問。


有任何建議或是錯誤，歡迎指正。

Thanks for C.C. Liang's review.