關於 zero-knowledge proof github ，我們在網路上蒐集到這些相關的討論、資訊與評價

📜 [專欄新文章] Unirep介紹: 使用ZKP的評價系統

✍️ Ya-Wen Jeng

📥 歡迎投稿： https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium

Unirep是什麼? 怎麼用?

Photo by Raphael Lovaski on Unsplash

UniRep 是一個使用零知識證明(Zero-knowledge Proof)而達到具有隱私保障的評價 (reputation) 系統。使用者有權利享有多個暫時性的身份，但又同時能提出證明，讓其他人可以驗證評價是否符合自己宣稱的數量。此外，使用者也無法拒絕接收對自己不利的評價。

想像一個情境：如果Alice是Airbnb的使用者，Alice常常透過Airbnb租房，且Alice曾經獲得獲得許多Airbnb房東的好評；有一天Alice想透過Booking.com訂房，http://xn--alicebooking-kt4so6lvyab96x7trhi5b54x.com/，所以在Booking.com上沒有任何評價，萬一Booking.com的房東不想把房子租給來路不明的客人，那Alice要如何向Booking.com的房東證明她其實都是用Airbnb租房，且獲得許多好評？

Alice雖然可以透過截圖或公開自己的資訊向Booking.com的房東證明自己擁有這些好評，但這樣Alice的隱私或許會被洩漏，例如Alice不想讓Booking.com的房東知道自己去過哪些地方、住過哪些民宿；或者Alice有可能偽造截圖，或者偽造評價，那Booking.com的房東要如何相信Alice所提供的證明文件是真的來自Airbnb的房東？除此之外有沒有更彈性的方式，Alice可以選擇性地向Booking.com的房東證明，自己至少有10個好評，但不透露自己總共有多少好評？

Photo by Andrea Davis on Unsplash

使用Unirep協定就可以解決這個問題。UniRep 取名自 Universal Reputation，希望透過區塊鏈上智能合約的可互用性 (interoperable，指智能合約容易被多方呼叫且容易透過智能合約與對方互動)，讓不管是Airbnb的房東、Booking.com的房東或是Alice都能很容易地透過Unirep的智能合約與對方互動，且透過零知識證明的方式，讓Alice的評價具有隱私的保障，Alice不用明確地向Booking.com的房東說這些評價是怎麼獲得、是什麼時候獲得，也可以彈性的證明自己至少有多少好評，或者最多有多少差評。

密碼學

Unirep主要用到的密碼學方法有

雜湊函數 hash：若有一個雜湊函數 f(x) = y 則由x可以很輕易的用f算出y，但從y推回x是幾乎不可能的，且要找到兩個不同的x對應到相同的y也是幾乎不可能的(沒有碰撞問題)。

零知識證明 zero-knowledge proof：可以將複雜的運算邏輯轉成容易驗證且具有隱私保障的驗證問題，使用者只要將變數輸入，這個零知識證明的演算法就會產生對應的證明且計算出對應的結果，使用者只要將此證明和運算結果輸入驗證的程序中，其他人就能驗證使用者是不是提出正確的證明，若驗證成功，則驗證者就能相信提出證明者高機率擁有正確的知識，也就是在計算證明時的輸入變數。

ZKP Proof System

ZKP Verification System

Semaphore：semaphore 是設計為可以用零知識證明驗證的身份認證系統。Unirep 中用來產生私鑰 (identity) 和公鑰的 hash 值(identity commitment)，讓使用者不必公開 identity 仍能透過零知識證明驗證其公私鑰的對應性。

雜湊樹 Merkle trees：Unirep 中大量運用雜湊樹的方式確保評價紀錄，而其中用到的雜湊樹又分兩種：Incremental merkle tree 和 Sparse merkle tree

Incremental merkle tree: 從 index 0 開始依序插入雜湊樹中的樹葉。為了使 ZKP 的 circuit 大小固定， Unirep 中使用固定高度的 Incremental merkle tree。

Sparse merkle tree: 在特定的 index i 插入樹葉

Incremental merkle tree and sparse merkle tree

UniRep中用到的名詞定義

Epoch

指一段特定的時間，例如7天

UniRep 的 Epoch 從 1 開始計算，7天過後Epoch數加一，即 Epoch 變為 2

Epoch Key

每個使用者在每個 Epoch 都能產生 n 把 Epoch key，用來收取評價 epoch_key = hash (id, epoch, nonce)

id: 這裡指用 semaphore 產生的 identity

epoch: 表示這是在第幾個 epoch 產生的 epoch key

nonce: 若 Unirep 規定使用者能在一個 epoch 產生 5 把 epoch key，則使用者可以選從 0 到 4 為此 nonce

因為雜湊函數的性質，算出來的 epoch key 很難推回原本的 id, epoch, nonce， 所以看到 epoch key 並不能推回使用者是誰。

以Alice為例，當Alice住完Airbnb，房東會透過 epoch key 給予 Alice 評價，但房東無法知道 Alice 在同個 epoch 的其他 epoch key 是哪一把，也無法知道 Alice 在別的 epoch 獲得的評價，除非 Alice 在這個 epoch 重複使用同一把 epoch key 收取評價。

User 使用者

用 semaphore 產生 identity 並使用此 identity 註冊的使用者

使用者是接收評價、證明評價、或是花費評價的人，用 epoch key 跟其他人互動，因為 epoch key 會隨著 epoch 增加而改變，所以對使用者來說每個 epoch 能產生的 epoch key 都不同，具有保護隱私的效果。

在上面的例子中使用者指的是 Alice, Bob, Airbnb 的房東, Booking.com的房東

Attester 證人

用 Ethereum address 或 smart contract address 註冊的用戶

是會被使用者記錄下來的評價給予者

Unirep 會給這些 address 一個 attester ID，而這個 attester ID 不會隨著 epoch 增加而改變，使用者可以知道這個評價是來自哪一個 attester。

在上面的例子中指的是 Airbnb 跟 Booking.com，因為 attester ID 不變，所以使用者可以證明這些評價是來自於 Airbnb 或是 Booking.com

User State Tree (UST)

是一 Sparse merkle tree

每個使用者都有自己的 User State Tree，其中樹葉表示所收到的評價的hash值，而葉子的 index 表示 attester ID，UST 樹葉的定義為

USTLeaf = hash(posRep, negRep, graffiti)

例如 Airbnb 的 ID 是1，Booking.com 的 ID 是 3，那 Alice 的 User State Tree 中 index 為 1 的地方會有自己在 Airbnb 獲得的總評價的 hash 值，而 index 為三的地方則為空的評價。另一個使用者 Bob 的 User State Tree 亦同，在 index 為 1 的地方會有自己在 Airbnb 獲得的評價，在 index 為 3 的地方會有自己在 Booking.com的評價。

Global State Tree (GST)

是一固定樹高的 Incremental merkle tree

Global State Tree 的葉子到樹根都是公開的資訊，當有使用者註冊或者更新 User State Tree 時會在 Global State Tree 裡新增一個新的樹葉，GST 樹葉的定義為：

GSTLeaf = hash(id, USTRoot)

先送出的樹葉先插入到較前面的 index，之後的樹葉依序插入 GST 中。

以 Alice的例子來說，當 Alice跟 Bob註冊 Unirep時，都會產生一個 GST的樹葉，更新 GST的樹根，若 Alice先註冊，則 Alice的 index會較 Bob前面。注意，這邊的 Airbnb 和 Booking.com 等 attester 並不是用這棵 Global State Tree註冊。

Epoch Tree

是一個 Sparse merkle tree

Epoch Tree 跟 Global State Tree 一樣從葉子到樹根都是公開的資訊，Epoch Tree 中樹葉的 index 為 epoch key，而樹葉的值為該 epoch key 的 sealed hash chain

每個 epoch key 都有一個 hash chain，hash chain 的定義為

hashedReputation = hash(attestIdx, attesterID, posRep, negRep, graffiti)hashChain[epochKey] = hash(hashedReputation, hashChain[epochKey])

此 hash chain 是為了防止使用者漏收了哪一筆評價，如果使用者少收了其中一筆評價，則 hash chain 的結果會完全不同。最後驗證時如果其中一個 epoch key 的 hash chain 改變，會造成 epoch tree 樹根跟原本的 epoch tree 的樹根不同。

而 Sealed hash chain 是在每個 epoch 結束後，Unirep 智能合約會再將這條 hash chain 再 hash 一次

sealedHashChain[epochKey] = hash(1, hashChain[epochKey]) isEpochKeyHashChainSealed[epochKey] = true

需要再把這條 hash chain 封起來的用意是，避免這把 epoch key 過了這個 epoch 之後再繼續接收評價，所以 epoch tree 會用這個 epoch key 最後的 sealed hash chain 去計算樹根。

Nullifier

中文翻譯為註銷符，當我們要防止一件事情重複發生時，就可以使用這個 Nullifier

Unirep 中使用到 Epoch key nullifier：此 nullifier 是用來限制使用者不能在不同的 epoch 使用重複的 epoch key 去收取評價，也不能被其他使用者使用；此外也可以用來檢視使用者是否重複執行 UST 的更新

Nullifier 也用 hash 計算，但多使用一個 domain 變數，避免與 epoch key 產生相同的 nullifier 而洩露自己擁有的 epoch key，也可以用不同的 domain 產生不同用途的 nullifier

epochKeyNullifier = hash(EPOCH_KEY_DOMAIN, id, epoch, nonce)

Epoch Transition

一個 epoch 結束過後，要透過 epoch transition 的步驟，更新 Unirep 及使用者的狀態

其中要做的事包含將智能合約上的 epoch 數加一，還有將所有 epoch key 的 hash chain 封起來

接著使用者就可以執行 User State Transition 更新自己的 UST

User State Transition

到下一個 epoch 後，使用者可以透過自己的 identity，找出自己在前一個 epoch 所有的 epoch key，並根據每把 epoch key 收到的評價更新到自己的 UST，最後計算出最新的評價狀態，產生一個 GST的樹葉，插入 GST 中 (如同註冊時一樣)。

使用者之後如果要花費評價或者產生下一個 epoch 的 epoch key 時，因為必須確認自己的 UST 在當前的 epoch，所以需要經過 User State Transition 確保自己有一個 GST 的樹葉在 GST 中。

Unirep 協定

有了 Unirep 的名詞定義後，接著介紹 Unirep 是如何運作的。

註冊

Unirep 的 user 和 attester 的註冊方式不同：

User signup and attester signup in Unirep

User

User 透過 semaphore 產生 identity 和 identity commitment，identity 就如同私鑰，identity commitment 就如同公鑰

將 identity commitment 和預設的 UST 樹根經由 hash 計算得 GST 的一個樹葉

若使用者要證明自己在某個 epoch 有註冊或者有更新自己的 UST，則證明自己是 GST 的某一個樹葉，利用零知識證明的方法，輸入 identity、UST 樹根，還有 merkle tree 中要計算 hash 值的相鄰節點，則最後可得到一個 GST 的 root，其他人可以驗證這個 GST 的 root 是否符合這顆公開的 GST。

Attester

Attester 則是用自己的錢包，或者用智能合約的地址註冊，呼叫 attester sign up 的 function 後，Unirep 會指定一個 attester ID 給這個地址，往後 attester 用相同錢包或合約地址給予評價時，Unirep 會檢查此地址是否被註冊，若有註冊則可以給予 epoch key 評價。

以 Alice 和 Bob 為例，Alice、Bob、Airbnb的房東、Booking.com的房東會產生 identity 並且透過 Unirep 合約用 user 的註冊方式獲得一個 GST 的樹葉代表自己；
而 Airbnb 和 Booking.com 會透過 attester 的註冊方式，使用特定的錢包地址或是撰寫智能合約呼叫 Unirep 的 attester sign up function。
當然 Alice 或 Bob 如果想用自己的錢包註冊為 attester 也是可以，這時合約就會紀錄 Alice 和 Bob 的錢包地址，並給予一個新的 attester ID。

給予評價

在 Unirep 中評價的接收者是 epoch key，接著介紹 user 和 attester 是如何互動。

How an attester gives reputation to an epoch key

Alice 在 Unirep 註冊過後，就可以產生 epoch key 接收評價

epochKey = hash(identity, epoch, nonce)

但 Airbnb 的房東看到這把 epoch key，要如何知道 Alice 確實是 Unirep 的合法使用者，且 epoch key 的 是合法的，例如 nonce 小於 5，或者 epoch 是當前的 epoch？

如果 Alice 直接提供 epoch 和 nonce，別人沒有 identity 也無法計算此 epoch key，更不用說如果 Alice 提供 identity 會造成 Alice 完全沒有隱私可言，所有人都可以計算出 Alice 收過哪些評價。

因此我們用一個零知識證明，證明此 epoch key 是合法的。細節請參考 epoch key proof，主要是證明使用者有一個合法的 GST 樹葉在 GST 中，並且 epoch 和 nonce 也都符合。

房東得到 Alice 提供的 epoch key 和 epoch key 的證明，並且透過 Unirep 的合約驗證通過之後，就可以給予評價。

獲得空投評價、使用者可以給予評價的限制可以由各個應用自行定義，例如 Airbnb 可以決定空投 30 個正評給使用者， Booking.com 可以決定空投 20 個正評給使用者。

另外，為了確認房東也是合法的使用者，也為了防止房東重複花費 (double spending) 自己的評價點數，Unirep 上的應用也可以用 reputation nullifier 及其 proof 去證明使用者合法使用自己的評價。

例如，此 reputation nullifier 可以用下列計算方式取得：

reputationNullifier = hash(REPUTATION_DOMAIN, id, epoch, nonce)

當 reputation nullifier 及 proof 產生後，就會與房東要給的評價一起發送到 Airbnb 的智能合約上，智能合約會驗證 proof 是否合法，nullifier 是否有被發送過，若檢查都通過的話則 Unirep 會紀錄此評價給 epoch key，並將 hash chain 更新。

接收評價

使用者即使可以證明自己擁有哪一把 epoch key 並且大家都知道這把 epoch key 有多少評價，但這有可能造成使用者故意忽略其他把 epoch key 中對自己不好的評價，因此 Unirep 限制使用者只能在每個 epoch 結束，每把 epoch key 都封起來之後，才能用 User State Transition 更新自己的評價。

User State Transition in Unirep

這裏也是用 User State Transition Proof 去保證使用者是根據正確的方式計算出最新的 UST，且用 epoch tree 限制使用者必須處理每一把 epoch key 的結果。

亦即，需要等到 epoch 結束後，Alice 才能透過 User State Transition 獲得 Airbnb 房東的評價，更新自己的使用者狀態。

證明評價

當使用者通過 User State Transition 之後會有最新的 UST 狀態，此時 Alice 就可以透過 reputation proof 向 Booking.com 她有來自 Airbnb 的評價，在reputation proof 中檢查使用者是否有其宣稱的 UST (例如總共有多少好評、多少差評來自哪一個 attester ID)，並且此 UST 的狀態儲存在當前 epoch 的 GST 中。

在生成 reputation proof 時，即使 Alice 總共有 100 個好評，但 Alice 仍可以產生「至少有10個好評」的證明，Booking.com 的房東若驗證成功，則只能知道 Alice 宣稱的「至少有 10 個好評」而不能知道 Alice 總共有 100 個好評。

常見問題

Alice 能不能給 Airbnb 的房東評價？ Alice 能不能給 Bob 評價？

可以。

Airbnb 的房東和 Bob 也都能產生 epoch key，因此如果 Alice 有兩者的 epoch key 及合法的 proof 則可以給予評價。此時 Alice 可以選擇透過 Airbnb、Booking.com、或甚至自己的 Ethereum account 當作證人給予評價 (也必須選擇一個證人)。

Alice 可以透過 Unirep 給 Airbnb 評價嗎？

如果 Airbnb 也透過 Unirep 註冊為使用者，並且產生 epoch key 的話就可以。但如果 Airbnb 只註冊為證人的話不行。

Alice 可以證明評價來自哪一個 Airbnb 房東嗎？

如果 Airbnb 的房東沒有註冊為證人，則 Alice 不能證明評價來自哪個房東。

若 Airbnb 的房東用自己的 Ethereum account 註冊為證人，則 Alice 只能證明評價來自這個 Ethereum account，但無法知道這個 account 是一個 Airbnb 的房東。

從 Airbnb 獲得的評價可以在 Booking.com 花費嗎？

需看 Booking.com 的智能合約如何定義，但一般來說不行，因為 attester ID不同，但未來可能會開發各個應用程式之間的兌換評價功能。

如果遲遲不執行 User State Transition 會發生什麼事？會不會收不到之前的評價？

若 Alice 在第一個 epoch 註冊，並在第一個 epoch 產生 epoch key 接收評價，但 Alice 到第五個 epoch 才執行 User State Transition，那 Alice 會根據第一個 epoch 的 GST、epoch tree 執行 User State Transition，因此仍然可以在第五個 epoch 收到來自第一個 epoch 的評價；而在第二到第四個 epoch 因為 Alice 無法產生出合法的 epoch key proof，因此無法接收評價。

User State Transition 可以自動執行嗎？

不行。

只有使用者主動給出私鑰，即 semaphore 的 identity，才可以產生合法的 User State Transition proof，若將私鑰交給第三方幫忙執行可能會侵害使用者的隱私。

結論

Unirep 是一個具有隱私保障的評價系統，透過 ZKP 的保護使用者可以在匿名的情況下收取評價、給予評價、並且向他人證明自己的評價。Unirep 可以用於跨應用程式間的評價證明，可以在 A 應用程式中獲得評價，並向 B 應用程式證明在 A 應用程式中獲得多少評價。若想了解更多有關 Unirep ，可以參考 Github、文件或加入 telegram 群組討論。

本文感謝 CC, Nic, Kevin, Doris 協助審稿。

Unirep介紹: 使用ZKP的評價系統 was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.

👏 歡迎轉載分享鼓掌

📜 [專欄新文章] ZKP 與智能合約的開發入門

✍️ Johnson

📥 歡迎投稿： https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium

這篇文章將以程式碼範例，說明 Zero Knowledge Proofs 與智能合約的結合，能夠為以太坊的生態系帶來什麼創新的應用。

本文為 Tornado Cash 研究系列的 Part 2，本系列以 tornado-core 為教材，學習開發 ZKP 的應用，另兩篇為：

Part 1：Merkle Tree in JavaScript

Part 3：Tornado Cash 實例解析

Special thanks to C.C. Liang for review and enlightenment.

近十年來最強大的密碼學科技可能就是零知識證明，或稱 zk-SNARKs (zero knowledge succinct arguments of knowledge)。

zk-SNARKs 可以將某個能得出特定結果 (output) 的計算過程 (computation)，產出一個證明，而儘管計算過程可能非常耗時，這個證明卻可以快速的被驗證。

此外，零知識證明的額外特色是：你可以在不告訴對方輸入值 (input) 的情況下，證明你確實經過了某個計算過程並得到了結果。

上述來自 Vitalik’s An approximate introduction to how zk-SNARKs are possible 文章的首段，該文說是給具有 “medium level” 數學程度的人解釋 zk-SNARKs 的運作原理。（可惜我還是看不懂 QQ）

本文則是從零知識證明 (ZKP) 應用開發的角度，結合電路 (circuit) 與智能合約的程式碼來說明 ZKP 可以為既有的以太坊智能合約帶來什麼創新的突破。

基本上可以謹記兩點 ZKP 帶來的效果：

1. 擴容：鏈下計算的功能。
2. 隱私：隱藏秘密的功能。

WithoutZK.sol

首先，讓我們先來看一段沒有任何 ZKP 的智能合約：

這份合約的主軸在 process()，我們向它輸入一個秘密值 secret，經過一段計算過程後會與 answer 比對，如果驗證成功就會改寫變數 greeting 為 “answer to the ultimate question of life, the universe, and everything”。

Computation

而計算過程是一個簡單的函式：f(x) = x**2 + 6。

我們可以輕易推出秘密就是 42。

這個計算過程有很多可能的輸入值 (input) 與輸出值 (output)：
f(2) = 10
f(3) = 15
f(4) = 22
…

但是能通過驗證的只有當輸出值和我們存放在合約的資料 answer 一樣時，才會驗證成功，並執行 process 的動作。

可以看到有一個 calculate 函式，說明這份合約在鏈上進行的計算，以及 process 需要輸入參數 _secret，而我們知道合約上所有交易都是公開的，所以這個 _secret 可以輕易在 etherscan 上被看到。

從這個簡單的合約中我們看到 ZKP 可以解決的兩個痛點：鏈下計算與隱藏秘密。

Circuits

接下來我們就改寫這份合約，加入 ZKP 的電路語言 circom，使用者就能用他的 secret 在鏈下進行計算後產生一個 proof，這 proof 就不會揭露有關 secret 的資訊，同時證明了當 secret 丟入 f(x) = x**2 + 6 的計算過程後會得出 1770 的結果 (output)，把這個 proof 丟入 process 的參數中，經過 Verifier 的驗證即可執行 process 的內容。

有關電路 circuits 的環境配置，可以參考 ZKP Hello World，這裡我們就先跳過去，直接來看 circom 的程式碼：

template Square() { signal input in; signal output out; out <== in * in;}template Add() { signal input in; signal output out; out <== in + 6;}template Calculator() { signal private input secret; signal output out; component square = Square(); component add = Add(); square.in <== secret; add.in <== square.out; out <== add.out;}component main = Calculator();

這段就是 f(x) = x**2 + 6 在 circom 上的寫法，可能需要時間去感受一下。

ZK.sol

circom 寫好後，可以產生一個 Verifier.sol 的合約，這個合約會有一個函式 verifyProof，於是我們把上方的合約改寫成使用 ZKP 的樣子：

我們可以發現 ZK 合約少了 calculate 函式，顯然 f(x) = x**2 + 6 已經被我們寫到電路上了。

snarkjs

產生證明的程式碼以 javascript 寫成如下：

let { proof, publicSignals } = await groth16.fullProve(input, wasmPath, zkeyPath);

於是提交 proof 給合約，完成驗證，達到所謂鏈下計算的功能。

最後讓我們完整看一段 javascript 的單元測試，使用 snarkjs 來產生證明，對合約的 process 進行測試：

對合約來說， secret = 42 是完全不知情的，因此隱藏了秘密。

publicSignals

之前不太清楚 publicSignals 的用意，因此在這裡特別說明一下。

基本上在產生證明的同時，也會隨帶產生這個 circom 所有的 public 值，也就是 publicSignals，如下：

let { proof, publicSignals } = await groth16.fullProve(input, wasmPath, zkeyPath);

在我們的例子中 publicSignals 只有一個，就是 1770。

而 verifyProof 要輸入的參數除了 proof 之外，也要填入 public 值，簡單來說會是：

const isValid = verifyProof(proof, publicSignals);

問題來了，我們在設計應用邏輯時，當使用者要提交參數進行驗證的時候，publicSignals 會是由「使用者」填入嗎？或者是說，儘管是使用者填入，那它需不需要先經過檢查，才可以填入 verifyProof？

關鍵在於我們的合約上存有一筆資料：answer = 1770

回頭看合約上的 process 在進行 verifyProof 之前，必須要檢查 isAnswer(publicSignals[0])：

想想要是沒有檢查 isAnswer，這份合約會發生什麼事情？

我們的應用邏輯就會變得毫無意義，因為少了要驗證的答案，就只是完成計算 f(42) = 1770，那麼不論是 f(1) = 7 或 f(2) = 10，使用者都可以自己產生證明與結果，自己把 proof 和 publicSignals 填入 verifyProof 的參數中，都會通過驗證。

至此可以看出，ZKP 只有把「計算過程」抽離到鏈下的電路，計算後的結果仍需要與鏈上既有的資料進行比對與確認後，才能算是有效的應用 ZKP。

應用邏輯的開發

本文主要談到的是 zk-SNARKs 上層應用邏輯的開發，關於 ZKP 的底層邏輯如上述使用的 groth16 或其他如 plonk 是本文打算忽略掉的部分。

從上述的例子可以看到，即使我們努力用 circom 實作藏住 secret，但由於計算過程太過簡單，只有 f(x) = x**2+6，輕易就能從 answer 反推出我們的 secret 是 42，因此在應用邏輯的開發上，也必須注意 circom 的設計可能出了問題，導致私密訊息容易外洩，那儘管使用再強的 ZKP 底層邏輯，在應用邏輯上有漏洞，也沒辦法達到隱藏秘密的效果。

此外，在看 circom 的程式碼時，可以關注最後一個 template 的 private 與 public 值分別是什麼。以本文的 Calculator 為例，private 值有 secret，public 值有 out。

另外補充：

如果有個 signal input 但它不是 private input，就會被歸類為 public。

一個 circuit 至少會有一個 public，因為計算過程一定會有一個結果。

最後，在開發的過程中我會用 javascript 先實作計算過程，也可以順便產出 input.json，然後再用 circom 語言把計算過程實現，產生 proof 和 public 後，再去對照所有 public 值和 private 值，確認是不是符合電路計算後所要的結果，也就是比較 javascript 算出來的和 circom 算出來的一不一樣，如果不一樣就能確定程式碼是有 bug 的。

參考範例：https://github.com/chnejohnson/circom-playground

總結

本文的程式碼展現 ZKP 可以做到鏈下計算與隱藏秘密的功能，在真實專案中，可想而知電路的計算過程不會這麼單純。

會出現在真實專案中的計算像是 hash function，複雜一點會加入 Merkle Tree，或是電子簽章 EdDSA，於是就能產生更完整的應用如 Layer 2 擴容方案之一的 ZK Rollup，或是做到匿名交易的 Tornado Cash。

本文原始碼：https://github.com/chnejohnson/mini-zkp

下篇文章就來分享 Tornado Cash 是如何利用 ZKP 達成匿名交易的！

參考資料

概念介紹

Cryptography Playground

zk-SNARKs-Explainer

神奇的零知識證明！既能保守秘密，又讓別人信你！

認識零知識證明 — COSCUP 2019 | Youtube

應用零知識證明 — COSCUP 2020 | Youtube

ZK Rollup

動手實做零知識 — circom — Kimi

ZK-Rollup 开发经验分享 Part I — Fluidex

ZkRollup Tutorial

ZK Rollup & Optimistic Rollup — Kimi Wu | Medium

Circom

circom/TUTORIAL.md at master · iden3/circom · GitHub

ZKP Hello World

其他

深入瞭解 zk-SNARKs

瞭解神秘的 ZK-STARKs

zk-SNARKs和zk-STARKs解釋 | Binance Academy

[ZKP 讀書會] MACI

Semaphore

Zero-knowledge Virtual Machines, the Polaris License, and Vendor Lock-in | by Koh Wei Jie

Introduction & Evolution of ZK Ecosystem — YouTube

The Limitations of Privacy — Barry Whitehat — YouTube

Introduction to Zero Knowledge Proofs — Elena Nadolinski

ZKP 與智能合約的開發入門 was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.

👏 歡迎轉載分享鼓掌

📜 [專欄新文章] [ZKP 讀書會] Trust Token Browser API
✍️ Yuren Ju
📥 歡迎投稿： https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium

Trust Token API 是一個正在標準化的瀏覽器 API，主要的目的是在保護隱私的前提下提供跨站授權 (Cross-domain authorization) 的功能，以前如果需要跨站追蹤或授權通常都使用有隱私疑慮的 Cookies 機制，而 Trust Token 則是希望在保護隱私的前提下完成相同的功能。

會在 ZKP (Zero-knowledge proof) 讀書會研究 Trust Token 主要是這個 API 採用了零知識證明來保護隱私，這也是這次讀書會中少見跟區塊鏈無關的零知識證明應用。

問題

大家應該都有點了一個產品的網頁後，很快的就在 Facebook 或是 Google 上面看到相關的廣告。但是產品網頁並不是在 Facebook 上面，他怎麼會知道我看了這個產品的頁面？

通常這都是透過 Cookie 來做跨網站追蹤來記錄你在網路上的瀏覽行為。以 Facebook 為例。

當使用者登入 Facebook 之後，Facebook 會透過 Cookie 放一段識別碼在瀏覽器裡面，當使用者造訪了有安裝 Facebook SDK 來提供「讚」功能的網頁時，瀏覽器在載入 SDK 時會再度夾帶這個識別碼，此時 Facebook 就會知道你造訪了特定的網頁並且記錄下來了。如此一來再搭配其他不同管道的追蹤方式，Facebook 就可以建構出特定使用者在網路上瀏覽的軌跡，從你的瀏覽紀錄推敲喜好，餵給你 Facebook 最想給你看的廣告了。

不過跨站追蹤也不是只能用在廣告這樣的應用上，像是 CDN (Content Delivery Network) 也是一個應用場景。CDN 服務 Cloudflare 提供服務的同時會利用 Captcha 先來確定進入網站的是不是真人或是機器人。而他希望使用者如果是真人時下次造訪同時也是採用 Cloudflare 服務的網站不要再跳出 Captcha 驗證訊息。

雖然 Cloudflare 也需要跨站驗證的功能來完成他們的服務，但是相較於 Google 或 Facebook 來說他們是比較沒那麼想知道使用者的隱私。有沒有什麼辦法可以保護使用者隱私的狀況下還能完成跨站驗證呢？

這就是今天要講的新 API: Trust Token。

Trust Token API - The Chromium Projects

Trust Token / Privacy Pass 簡介

Trust Token 其實是由 Privacy Pass 延伸而來。Privacy Pass 就是由 Cloudflare 所開發的實驗性瀏覽器延伸套件實作一個驗證機制，可以在不透漏過多使用者隱私的前提下實作跨站驗證。而 Trust Token 則是標準化的 Privacy Pass，所以兩個運作機制類似，但是實作方式稍有不同。

先看一下 Privacy Pass 是如何使用。因為這是實驗性的瀏覽器延伸套件所以看起來有點陽春，不過大致上還是可以了解整個概念。

以 hCaptcha 跟 Cloudflare 的應用為例，使用者第一次進到由 Cloudflare 提供服務的網站時，網站會跳出一些人類才可以解答的問題比如說「挑出以下是汽車的圖片」。

當使用者答對問題後，Cloudflare 會回傳若干組 blind token，這些 blind token 還會需要經過 unblind 後才會變成真正可以使用的 token，這個過程為 issue token。如上圖所示假設使用者這次驗證拿到了 30 個 token，在每次造訪由 Cloudflare 服務的網站時就會用掉一個 token，這個步驟稱為 redeem token。

但這個機制最重要的地方在於 Cloudflare 並無法把 issue token 跟 redeem token 這兩個階段的使用者連結在一起，也就是說如果 Alice, Bob 跟 Chris 都曾經通過 Captcha 測試並且獲得了 Token，但是在後續瀏覽不同網站時把 token 兌換掉時，Clouldflare 並無法區分哪個 token 是來自 Bob，哪個 token 是來自 Alice，但是只要持有這種 token 就代表持有者已經通過了 Captcha 的挑戰證明為真人。

但這樣的機制要怎麼完成呢？以下我們會透過多個步驟的例子來解釋如何達成這個目的。不過在那之前我們要先講一下 Privacy Pass 所用到的零知識證明。

零知識證明 (Zero-knowledge proof)

零知識證明是一種方法在不揭露某個祕密的狀態下，證明他自己知道那個秘密。

Rahil Arora 在 stackexchange 上寫的比喻我覺得是相對好理解的，下面簡單的翻譯一下：

假設 Alice 有超能力可以幾秒內算出樹木上面有幾片樹葉，如何在不告訴 Bob 超能力是怎麼運作並且也不告訴 Bob 有多少片葉子的狀況下證明 Alice 有超能力？我們可以設計一個流程來證明這件事情。

Alice 先把眼睛閉起來，請 Bob 選擇拿掉樹上的一片葉子或不拿掉。當 Alice 睜開眼睛的時候，告訴 Bob 他有沒有拿掉葉子。如果一次正確的話確實有可能是 Alice 幸運猜到，但是如果這個過程連續很多次時 Alice 真的擁有數葉子的超能力的機率就愈來愈高。

而零知識證明的原理大致上就是這樣，你可以用一個流程來證明你知道某個秘密，即使你不真的揭露這個秘密到底是什麼，以上面的例子來說，這個秘密就是超能力運作的方式。

以上就是零知識證明的概念，不過要完成零知識證明有很多各式各樣的方式，今天我們要介紹的是 Trust Token 所使用的零知識證明：DLEQ。

DLEQ (Discrete Logarithm Equivalence Proof)

說明一下以下如果小寫的變數如 c, s 都是純量 (Scalar)，如果是大寫如 G, H則是橢圓曲線上面的點 (Point)，如果是 vG 則一樣是點，計算方式則是 G 連續相加 v 次，這跟一般的乘法不同，有興趣可以程式前沿的《橢圓曲線加密演算法》一文解釋得比較詳細。

DLEQ 有一個前提，在系統中的所有人都知道公開的 G 跟 H 兩個點，此時以下等式會成立：

假設 Peggy 擁有一個秘密 s 要向 Victor 證明他知道 s 為何，並且在這個過程中不揭露 s 真正的數值，此時 Victor 可以產生一個隨機數 c 傳送給 Peggy，而 Peggy 則會再產生一個隨機數 v 並且產生 r，並且附上 vG, vH, sG, sH：

r = v - cs

所以 Victor 會得到 r, sG, sH, vG, vH 再加上他已經知道的 G, H。這個時候如果 Victor 計算出以下兩個等式就代表 Peggy 知道 s 的真正數值：

vG = rG + c(sG)vH = rH + c(sH)

我們舉第二個等式作為例子化簡：

vH = rH + c(sH) // 把 r 展開成 v - csvH = (v - cs)H + c(sH) // (v - cs)H 展開成 vH - csHvH = vH - c(sH) + c(sH) // 正負 c(sH) 消掉vH = vH

這樣只有 Peggy 知道 s 的狀況下才能給出 r，所以這樣就可以證明 Peggy 確實知道 s。

從簡易到實際的情境

Privacy Pass 網站上透過了循序漸進的七種情境從最簡單的假設到最後面實際使用的情境來講解整個機制是怎麼運作的。本文也用相同的方式來解釋各種情境，不過前面的例子就會相對比較天真一點，就請大家一步步的往下看。

基本上整個過程是透過一種叫做 Blind Signature 的方式搭配上零知識證明完成的，以下參與的角色分為 Client 與 Server，並且都會有兩個階段 issue 與 redeem token。

Scenario 1

如果我們要設計一個這樣可以兌換 token 來確認身分的系統，其中有一個方法是透過橢圓曲線 (elliptic curve) 完成。Client 挑選一個在橢圓曲線上的點 T 並且傳送給 Server，Server 收到後透過一個只有 Server 知道的純量 (scalar) s 對 T 運算後得到 sT 並且回傳給 Client，這個產生 sT 的過程稱為 Sign Point，不過實際上運作的原理就是橢圓曲線上的連續加法運算。

SignPoint(T, s) => sT

等到 Client 需要兌換時只要把 T 跟 sT 給 Server，Server 可以收到 T 的時候再 Sign Point 一次看看是不是 sT 就知道是否曾經 issue 過這個 token。

Issue

以下的範例，左邊都是 Client, 右邊都是 Server。 -> 代表 Client 發送給 Server，反之亦然。

// Client 發送 T 給 Server, 然後得到 sT

T -> <- sT

Redeem

// Client 要 redeem token 時，傳出 T 與 sT

T, sT ->

問題：Linkability

因為 Server 在 issue 的時候已經知道了 T，所以基本上 Server 可以透過這項資訊可以把 issue 階段跟 redeem 階段的人連結起來進而知道 Client 的行為。

Scenario 2

要解決上面的問題，其中一個方法是透過 Blind Signature 達成。Client 不送出 T，而是先透過 BlindPoint 的方式產生 bT 跟 b，接下來再送給 Server bT。Server 收到 bT 之後，同樣的透過 Sign Point 的方式產生結果，不一樣的地方是情境 1 是用 T，而這邊則用 bT 來作 Sign Point，所以得出來的結果是 s(bT)。

Client:BlindPoint(T) => (bT, b)

Server:SignPoint(bT, s) => sbT

而 Blind Signature 跟 Sign Point 具備了交換律的特性，所以得到 s(bT) 後可以透過原本 Client 已知的 b 進行 Unblind：

UnblindPoint(sbT, b) => sT

這樣一來在 Redeem 的時候就可以送出 T, sT 給 Server 了，而且透過 SignPoint(T, s) 得出結果 sT’ 如果符合 Client 傳來的 sT 就代表確實 Server 曾經簽過這個被 blind 的點，同時因為 T 從來都沒有送到 Server 過，所以 Server 也無法將 issue 與 redeem 階段的 Client 連結在一起。

Issue

bT -> <- s(bT)

Redeem

T, sT ->

問題：Malleability

以上的流程其實也有另外一個大問題，因為有交換律的關係，當 Client 透過一個任意值 a 放入 BlindPoint 時產生的 a(sT) 就會等於 s(aT)：

BlindPoint(sT) => a(sT), a// a(sT) === s(aT)

此時如果將 aT 跟 s(aT) 送給 Server Redeem，此時因為

SignPoint(aT, s) => s(aT)

所以就可以兌換了，這樣造成 Client 可以無限地用任意數值兌換 token。

Scenario 3

這次我們讓 Client 先選擇一個純數 t，並且透過一種單向的 hash 方式來產生一個在橢圓曲線上的點 T，並且在 redeem 階段時原本是送出 T, sT 改成送出 t, sT。

因為 redeem 要送出的是 t，上個情境時透過任意數 a 來產生 s(aT) 的方法就沒辦法用了，因為 t 跟 sT 兩個參數之間並不是單純的再透過一次 BlindPoint() 就可以得到，所以就沒辦法無限兌換了。

Issue

T = Hash(t) bT -> <- sbT

Redeem

t, sT ->

問題：Redemption hijacking

在這個例子裏面，Client 其實是沒有必要傳送 sT 的，因為 Server 僅需要 t 就可以計算出 sT，額外傳送 sT 可能會導致潛在的 Redemption hijacking 問題，如果在不安全的通道上傳輸 t, sT 就有可能這個 redemption 被劫持作為其他的用途。

不過在網站上沒講出實際上要怎麼利用這個問題，但是少傳一個可以計算出來的資料總是好的。Client 只要證明他知道 sT 就好，而這可以透過 HMAC (Hash-based Message Authentication Code) 達成。

Scenario 4

步驟跟前面都一樣，唯一不一樣的地方是 redeem 的時候原本是傳 t, sT，現在則改傳 t, M, HMAC(sT, M)，如果再介紹 HMAC 篇幅會太大，這邊就不解釋了，但可以是作是一個標準的 salt 方式讓 Hash 出來的結果不容易受到暴力破解。

這樣的特性在這個情境用很適合，因為 Server 透過 t 就可以計算出 sT，透過公開傳遞的 M 可以輕易地驗證 client 端是否持有 sT。

Issue

T = Hash(t) bT -> <- sbT

Redeem

t, M, HMAC(sT, M) ->

問題：Tagging

這邊的問題在於 Server 可以在 issue 階段的時候用不一樣的 s1, s2, s3 等來發出不一樣的 sT’，這樣 Server 在 Redeem 階段就可以得知 client 是哪一個 s。所以 Server 需要證明自己每次都用同樣的 s 同時又不透漏 s 這個純亮。

要解決這個問題就需要用到前面我們講解的零知識證明 DLEQ 了。

Scenario 5

前面的 DLEQ 講解有提到，如果有 Peggy 有一個 s 秘密純量，我們可以透過 DLEQ 來證明 Peggy 知道 s，但是又不透漏 s 真正的數值，而在 Privacy Pass 的機制裡面，Server 需要證明自己每次都用 s，但是卻又不用揭露真正的數值。

在 Issue 階段 Client 做的事情還是一樣傳 bT 給 Server 端，但 Server 端的回應就不一樣了，這次 Server 會回傳 sbT 與一個 DLEQ 證明，證明自己正在用同一個 s。

首先根據 DLEQ 的假設，Server 會需要先公開一組 G, H 給所有的 Client。而在 Privacy Pass 的實作中則是公開了 G 給所有 Client，而 H 則改用 bT 代替。

回傳的時候 Server 要證明自己仍然使用同一個 s 發出 token，所以附上了一個 DLEQ 的證明 r = v - cs，Client 只要算出以下算式相等就可證明 Server 仍然用同一個 s (記住了 H 已經改用 bT 代替，此時 client 也有 sbT 也就是 sH)：

vH = rH + c(sH) // H 換成 bTvbT = rbT + c(sbT) // 把 r 展開成 v - csvbT = (v - cs)bT + c(sbT) // (v - cs)bT 展開成 vbT - csbTvbT = vbT - c(sbT) + c(sbT) // 正負 c(sbT) 消掉vbT = vbT

這樣就可以證明 Server 依然用同一個 s。

Issue

T = Hash(t) bT -> <- sbT, DLEQ(bT:sbT == G:sG)

Redeem

t, M, HMAC(sT, M) ->

問題：only one redemption per issuance

到這邊基本上 Privacy Pass 的原理已經解釋得差不多了，不過這邊有個問題是一次只發一個 token 太少，應該要一次可以發多個 token。這邊我要跳過源文中提到的 Scenario 6 解釋最後的結果。

Scenario 7

由於一次僅產生一個 redeem token 太沒效率了，如果同時發很多次，每次都產生一個 proof 也不是非常有效率，而 DLEQ 有一個延伸的用法 “batch” 可以一次產生多個 token, 並且只有使用一個 Proof 就可以驗證所有 token 是否合法，這樣就可以大大的降低頻寬需求。

不過這邊我們就不贅述 Batch DLEQ 的原理了，文末我會提及一些比較有用的連結跟確切的源碼片段讓有興趣的人可以更快速的追蹤到源碼片段。

Issue

T1 = Hash(t1) T2 = Hash(t2)T3 = Hash(t3)b1T1 ->b2T2 ->b3T3 -> c1,c2,c3 = H(G,sG,b1T1,b2T2,b3T3,s(b1T1),s(b2T2),s(b3T3)) <- sb1T1 <- sb2T2 <- sb3T3 <- DLEQ(c1b1T1+c2b2T2+c3b3T3:s(c1b1T1+c2b2T2+c3b3T3) == G: sG)

Redeem

t1, M, HMAC(sT1, M) ->

結論

Privacy Token / Trust Token API 透過零知識證明的方式來建立了一個不需要透漏太多隱私也可以達成跟 cookie 相同效果的驗證方式，期待可以改變目前許多廣告巨頭透過 cookie 過分的追蹤使用者隱私的作法。

不過我在 Trust Token API Explainer 裡面看到這個協議裡面的延伸作法還可以夾帶 Metadata 進去，而協議制定的過程中其實廣告龍頭 Google 也參與其中，希望這份協議還是可以保持中立，盡可能地讓最後版本可以有效的在保護隱私的情況下完成 Cross-domain authorization 的功能。

參考資料

IETF Privacy Pass docs

Privacy Pass: The Protocol

Privacy Pass: Architectural Framework

Privacy Pass: HTTP API

Cloudflare

Supporting the latest version of the Privacy Pass Protocol (cloudflare.com)

Chinese: Cloudflare支持最新的Privacy Pass扩展_推动协议标准化

Other

Privacy Pass official website

Getting started with Trust Tokens (web.dev)

WICG Trust Token API Explainer

Non-interactive zero-knowledge (NIZK) proofs for the equality (EQ) of discrete logarithms (DL) (asecuritysite.com) 這個網站非常實用，列了很多零知識證明的源碼參考，但可惜的是 DLEQ 這個演算法講解有錯，讓我在理解演算法的時候撞牆很久。所以使用的時候請多加小心，源碼應該是可以參考的，解釋的話需要斟酌一下。

關鍵源碼

這邊我貼幾段覺得很有用的源碼。

privacy pass 提供的伺服器端產生 Proof 的源碼

privacy pass 提供的瀏覽器端產生 BlindPoint 的源碼

github dedis/kyber 產生 Proof 的源碼

[ZKP 讀書會] Trust Token Browser API was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.

👏 歡迎轉載分享鼓掌