📜 [專欄新文章] 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.
👏 歡迎轉載分享鼓掌
nonce 區塊 鏈 在 Taipei Ethereum Meetup Facebook 的最佳解答
📜 [專欄新文章] [ZKP 讀書會] Zkopru
✍️ NIC Lin
📥 歡迎投稿: https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
Photo by Barth Bailey on Unsplash
Zkopru
Zkopru 這個名稱是由 zk-transaction + Optimistic Roll-Up 的字首組成,這個layer 2 的協議包含了使用零知識證明來保護交易的隱私( zk-transaction)、再搭配 Optimistic Rollup 來管理 layer 2 。
接下來會講到 Zk Rollup 和 Optimistic Rollup,如果讀者還不熟悉,可以先閱讀這篇ˊ指介紹。
它和 Zk Rollup 有什麼不同?
Zk Rollup 連同 layer 2 的鏈的 state transition 都是由零知識證明來處理,但缺點是目前零知識證明技術的成本較高,包含在鏈下產生證明和在鏈上驗證證明(鏈下產生證明耗費時間,鏈上驗證證明則耗費 gas)。
註:接下來提到的(零知識證明、circuit)的鏈下成本都是指時間多寡,而鏈上成本則都是指 gas 多寡)
另外目前的 Rollup 協議都是使用 merkle tree 來儲存當前的鏈的狀態(例如使用者的餘額、nonce 或是 UTXO) — 如果使用者要證明他有 $20,則他必須要提供 merkle proof ,而這個 merkle proof 的大小及 hash 次數也會因為選擇的 merkle tree 的高度而有不同。
而這個因素再搭配上 hash 的成本在 EVM 和 circuit 會有不同,導致協議如果使用在 EVM 成本較便宜的 hash function,則 circuit 的 hash 成本會較高;反之亦然。
目前還沒有安全的 hash function 是在 EVM 或 circuit 裡都是便宜的,所以協議設計者必須做出妥協。可想而知,Zk Rollup 便是使用在 circuit 便宜但是在 EVM 貴的 hash function,這導致當使用者要離開 layer 2 回到 layer 1 時(這個步驟在這裡稱作 withdraw),他成本會很高(因為要在 EVM 裡驗證他持有資產的擁有權,這可以是一個 merkle proof 或 zk proof)。
和 Optimistic Rollup 有什麼不同?
而這個成本相對的也反映了採用 Optimistic Rollup 的好處 — 只有在特殊情況下(例如協議裡的 Operator 作惡)才需要付出較高的成本,其他時間大家則享受極低成本的使用費。
但使用 Optimistic 的方式也有附帶的缺點: challenge period 。輕節點使用者需要等待 challenge period 來確保交易不會被推翻、withdraw 過程需要等待 challenge period(以下稱 withdraw period) 過了才能將錢提回到 layer 1。
所以使用哪種 Rollup 就要看協議設計者如何依照他們的使用需求去權衡。
那為什麼不使用 Optimistic Rollup 就好?
因為需要零知識證明來保護交易隱私!
前提
zkopru 使用和 Bitcoin 相同的 UTXO model
transfer 的付款方、收款方和金額都是被保護住、看不到的,但 zkopru 和其他隱私幣一樣,不需要付款方和收款方合作即可由付款方單獨完成 transfer。
但也和隱私幣一樣,收款方必須去監看鏈上每一筆交易並嘗試解密來得知是否有人 transfer 給自己
基本使用流程
Deposit
使用者將 ether 、ERC20 或 ERC721 代幣轉入 zkopru 位於 layer 1 的合約,觸發 event。協議的 Operator 會監看合約並搜集 deposit event,然後將這些 deposit 一起放入下一個(zkopru 的)區塊裡。
Transfer
如同 Bitcoin 的 UTXO,zkopru 裡使用者必須要證明其對某 UTXO 有擁有權才能花費該 UTXO。要被花費的 UTXO 會被放到 transaction 格式裡的 inputs 欄位, outputs 欄位的 UTXO 則是填入收款方的公鑰和收款金額(outputs 的 UTXO 就會是新產生的 UTXO)。
因為要保護交易的隱私,新的 UTXO 的資訊是不會洩露出去的,第三方只會看到該 UTXO 的 hash 值。那收款方要怎麼知道一個 UTXO 是不是他的呢?
sender 會利用自己的私鑰、收款方的公鑰及一個隨機值,透過密鑰交換協議來產生一個臨時的共享密鑰。 付款方用此共享密鑰加密收款方所需的資訊(包含 transfer 的代幣種類和金額),而收款方會監看每一筆交易並試著用自己的私鑰組出一個共享密鑰然後去解密,如果解密完的資料不是亂碼而是合理的,則可確認收到錢。
Withdraw使用者產生 withdraw 類別的交易,等待協議 Operator 收進區塊裡,然後再等待 withdraw period 過去,即可送出 merkle proof 來將錢提領回 layer 1。
註:提領回 layer 1 之後的收款方和金額都是公開透明的,隱私不再受保護。
零知識證明
zkopru 裡一共有三種類型的 merkle tree 來儲存所需的狀態,分別是 UTXO tree、Nullifier tree 以及 Withdrawal tree。
UTXO tree 紀錄所有產生過的 UTXO,包含新的和已經花掉的。
Nullifier tree 紀錄被花掉的 UTXO 的 nullifier 值。一個 UTXO 的 nullifer 由該 UTXO 的相關資訊算出,而且只能得出唯一一個 nullifier。這個 nullifier 能夠證明該 UTXO 已被花掉,但同時又不會洩露是哪個 UTXO 被花掉。聽起來很饒口,但這就是零知識證明的能力。
Withdrawal tree 紀錄 withdraw 類別的交易的資訊,使用者要提領回 layer 1 就需要這棵 merkle tree 的 merkle proof。也是就說,前面說的 Operator 會把 withdraw 交易放到這棵 merkle tree 裡,然後等待 withdrawal period 過後,再由使用者提供 merkle proof 來領走。
這裏以 transfer 為例來說明其中一部分的 circuit 在做什麼事
當使用者要產生一筆 transfer,他首先要證明 inputs 裡的 UTXO 都是合法的,這包含了證明:
他擁有這個 UTXO — 藉由提供簽章來證明
這個 UTXO 是真的存在的 — 藉由證明該 UTXO 的 hash 值存在 UTXO tree 裡
這個 UTXO 沒有被花過 — 藉由證明該 UTXO 的 nullifier 值不存在 Nullifier tree 裡
接者是 outputs,新產生的 UTXO 的 hash 值會被放進 UTXO tree 裡。
最後是比對 inputs 金額加總等於 outputs 金額加總再加上交易手續費。
而這些都在 circuit 裡完成,第三方沒辦法得知實際的 inputs、outputs 或 nullifiers 等等,第三方只能知道新的 UTXO 的 hash 值以及運算過程是正確的 — 也就是這些 tree 都被正確的更新了。
其他特色
Mass migration
原本每個使用者要把資產換到另外一個 layer 2 協議,他必須申請 withdraw 、等待 withdraw period ,然後把資產 deposit 到另外一個 layer 2 協議。
zkopru 支援使用者成批的搬移資產到另外一個 layer 2 協議 — 共享經濟。
Instant withdrawal
如果其他需要等待 withdraw period 的應用來說,withdraw period 是一個 UX 痛點。zkopru 的 instant withdrawal 提供急著 withdraw 的一方和不急著 withdraw 的一方一個管道能互惠。
急的一方提供一點手續費,對自己的 withdraw 交易做簽名並廣播出去。不急的一方在聽到這個簽名後,可以將這個簽名送到 zkopru 合約並附上 withdraw 金額(扣掉自己該收的手續費)。
這筆錢會直接轉給急的一方,然後急的一方的 withdraw 擁有權便會轉移到不急的一方手上,不急的一方再慢慢等到 withdraw period 過了再提領。
估計效能
目前在初版的效能估計中,一筆 transfer 平均耗費 8800 gas;而 TPS 則是 105。zkopru 還在積極更新迭代中,所以這個效能會在提升。
Reference:
https://ethresear.ch/t/zkopru-zk-optimistic-rollup-for-private-transactions/7717
https://docs.zkopru.network
https://www.chainnews.com/zh-hant/articles/443085023250.htm
[ZKP 讀書會] Zkopru was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
nonce 區塊 鏈 在 Taipei Ethereum Meetup Facebook 的最佳貼文
📜 [專欄新文章] ELI5! 區塊鏈到底在幹嘛?
✍️ Juin Chiu
📥 歡迎投稿: https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
用生活化的例子輕鬆學會區塊鏈技術的重要概念
前言
我們熟知的世界正在慢慢地被區塊鏈技術瓦解與重建。不論背景,有愈來愈多人想對區塊鏈技術一探究竟,或許更進一步成為從業者、貢獻者或佈道者。
不幸的是,初學者若想學習區塊鏈技術,第一個問題可能會是高學習門檻,這是因為目前在各種主流平台上所流傳的區塊鏈知識或資源,都不免會大量使用艱澀的術語,長久以來便塑造出區塊鏈高大上的距離感,好似區塊鏈是只專屬於一小群駭客或者專業人士才能理解的技術。然而這是不準確的,事實上,區塊鏈技術中許多概念都能用一般常識理解,頂多只需要國小數學。
本文中,筆者將化繁為簡,試著把區塊鏈技術中的每個元素都使用生活化的例子比擬,讓區塊鏈愛好者與初學者不需用到密碼學/經濟學/資訊科學,也能領會區塊鏈技術的精髓之處。
本文將提及的概念如下:
什麼是帳本?
什麼是交易?
為什麼需要區塊?
有哪些共識機制?
區塊鏈安全嗎?
智能合約如何運作?
以下正文開始:
區塊鏈:一個公平的記錄系統
簡單來說,區塊鏈技術旨在打造一個去中心化的(Decentralized)狀態紀錄系統,更準確一點:區塊鏈技術旨在打造是一個追求真正「公平」的系統。
區塊鏈實現公平的關鍵在於:它完全仰賴自然法則運作,只透過一系列精細的規則就能保證系統的正確,這打破了人類社會一直以來的仰賴的中心化系統,使促成不平等的最大因素不復存在。
區塊鏈技術可以打造出具世界規模的去中心化運算平台,由數千甚至數萬個參與者共同維護狀態並提供計算資源。如果這個運算平台是應用在貨幣與資產的場景中,那麼這個平台可被稱為分散式帳本。
在接下來的段落,筆者將用一個例子展示一個極度精簡、只用紙跟筆的就可以運作的分散式帳本。在這個例子中,一群學生可以使用區塊鏈技術發行屬於他們自己的虛擬幣:「考卷幣」(Exam Paper Coin, EPC)。
考卷幣:使用區塊鏈技術發行的虛擬幣
考卷幣(EPC)是一種使用區塊鏈技術發行的虛擬幣,並存在於分散式帳本中。它的用途是為考卷加分,這將會吸引想考高分或者擔心被當的人學生持有。為什麼 EPC 只能被稱作虛擬幣,而不被稱作密碼貨幣?這是因為 EPC 的發行不會使用任何有關密碼學的技術,因此 EPC 嚴格來說不是密碼貨幣。
在分散式帳本被創建之初,沒有任何人擁有 EPC ,那麼 EPC 是怎麼「鑄造」與分配的?至少可以肯定的是,EPC 不能憑空產生,否則所有參與者就能不斷製造 EPC,使分散式帳本崩潰。事實上,EPC 的價值奠基於參與者的「付出」。
分散式帳本中最重要的角色非記帳者莫屬。每當記帳者成功完成工作,它便可以獲得固定數量的 EPC 作為報酬。於是,分散式帳本中的 EPC 便如此逐步地被鑄造出來。將 EPC 賦予具有貢獻的記帳者除了能夠公平分配 EPC,同時也是一種激勵機制(Incentivizing Mechanism),提供參與者維護帳本的動機。
那麼每個人所具有的 EPC 是怎麼記錄在帳本中的?
帳本: EPC 都要記錄下來
帳本即為依時間順序與特定格式記錄價值的系統。在分散式帳本中,每一批紀錄都會由某一個特定的「記帳者」維護,而記帳者會以特定的規則從所有的參與者中選出,因此分散式帳本是具有多個「記帳者」的系統。
為了確保能公平選出 EPC 的所有記帳者,分散式帳本不會使用任何記帳者的個人資訊,例如姓名、電話,做為帳本上的識別。記帳者可以自由地使用假名(Pseudonym)作為帳本上唯一的識別(Identifier),或者稱為地址(Address)。所以王小庭同學可以使用 Alice 這個假名,而且如果王小庭同學喜歡的話,他也可以同時使用 Bob 這個假名。
EPC 使用如下的格式記錄每個地址幣的數量:
Alice 100 EPCBob 0 EPCCharlie 0 EPCDavid 0 EPCEva 0 EPC
多數區塊鏈稱其識別為地址(Address),其為非對稱密碼學中公鑰(Public Key)的雜湊值(Hash)。地址具有統一的格式,例如以太坊的地址為長度 160 位元的 16 進位數字。
交易:把我的 EPC 轉移給別人
EPC 是可以轉移的,現在 Alice 可以將它持有的 100 EPC 中的 60 EPC 轉移給 Bob,以幫助 Bob 在下一次考試中免於被當。這樣的轉幣紀錄稱為交易(Transaction, Tx),可以如下表示:
Tx1
60 EPC, from [Alice] to [Bob]
而這筆交易會由 Alice 以上述格式記在紙條上,以 Tx1 表示。
簽章:讓參與者的所有動作都不可抵賴
EPC 的每個參與者的每個行為,例如交易,都必須附帶簽章(Signature),證明「這個動作確實是由我本人發起的」,簽署者不可抵賴,任何沒有附帶簽名的動作都是不被承認的。一個附帶簽名的交易紙條會像這樣:
Tx1
60 EPC, from [Alice] to [Bob], ALICE
簽章分為簽署(Sign)及驗證(Verify)兩個動作。驗證即是確認簽章是否確實是由行為發起者所簽署。在這個例子中,僅用一個簡單的驗證:若簽章與識別相符,則驗證成功。例如 Tx1 中,簽名 ALICE 確實與交易發起者 Alice 相符,因此驗證成功。
簽章就是區塊鏈的數位簽章(Digital Signature),其使用私鑰(Private Key)簽署,公鑰(Public Key)驗證,非常難以偽造。
訊息的散佈:怎麼讓所有參與者都收到訊息?
由於 Tx1 是由 Alice 發起的,因此 Alice 將於它自己的帳本記下這筆交易,接著 Alice 必須把這筆交易的內容也轉達所有的參與者,讓所有參與者皆具有所有的交易內容。
EPC 的參與者們不以口語,而是以傳紙條的方式互相交換訊息。紙條要如何有效率地傳播訊息給所有在教室中的參與者呢?可以使用「一傳十、十傳百」的策略。也就是:一次傳 10 張紙條給自己周圍的參與者,參與者收到後再抄寫 10 次後傳給周圍尚未收到該紀錄的其他參與者,逐步將訊息擴散致所有參與者。
這樣的傳播策略正如同流言被散佈的方式,因此也被稱為流言散佈協定(Gossip Protocol)。紙條傳播的網路就是對等網路(Peer-to-peer Network),紙條就是對等網路的封包(Packet)。關於對等網路的介紹,可以參考筆者日前的撰文:
隱私、區塊鏈與洋蔥路由
區塊:記錄一段時間內的交易順序
經過一段時間之後,每個 EPC 參與者手上都會有許多來自別的參與者的紙條,每張紙條都記載著不同的交易。在理想狀況下,如果所有參與者收到紙條的順序都相同,且每個參與者都收到了所有紙條,則所有參與者的帳本上的狀態,也就是餘額,都會相同。然而,若採用上述的訊息散佈策略,會發生兩種情況:每個參與者收到紙條的順序會不同,或者某些紙條可能會被遺漏。這些情況都會讓每個參與者的帳本產生差異,使帳本不可靠。而一個不可靠的帳本,不能作為貨幣發行的工具。
有沒有辦法能使所有 EPC 參與者用相同的交易順序記帳呢?這便是區塊鏈技術的奧秘之處。
為此,我們需要使用一個精心設計的結構:區塊(Block)。每個參與者皆會將一段時間內收到的交易紙條的編號,依照自己的順序寫在另一張紙條上,這張紙條就是區塊紙條,簡稱區塊,產出區塊的參與者則稱為區塊生產者。收到區塊紙條的其他參與者便會知道區塊生產者在這段時間內的交易順序。
為了要讓所有帳本都具有一致的狀態,EPC 的所有參與者必須要選出其中一個區塊作為所有參與者的共識(Consensus)。所有參與者都必須要遵照共識區塊的交易順序來更新自己的帳本,而這個區塊生產者就是記帳者。由於記帳者可以獲得報酬,因此在利益的驅使下,所有參與者都會努力生產區塊以爭取記帳權。
值得注意的是,每個區塊當中都會記錄前一個已達成共識的區塊的編號。例如接下來的範例,Bk15 的前一個已達成共識的區塊為 Bk3:
Bk15
Last Block: Bk3
Height: 15
Transactions:- Tx1- Tx5- Tx4- Tx10- Tx7- Tx13
Nonce: 1
Signature: CHARLIE
由於每個新的共識區塊都會指向前一個共識區塊,如此便會形成一條長鏈般的結構,已形成共識的區塊接成一條鏈,這就是區塊鏈(Blockchain)名稱的由來。
而當 EPC 參與者在收取共識的區塊後,將按照共識依序為每個交易內容進行帳本餘額的轉換。如此,所有的帳本都將具有一致的狀態。
依據特定輸入及轉換函數(Transition Function)執行狀態更新的系統,稱為狀態機複製(State Machine Replication)
摘要:濃縮紙條上的訊息
在介紹達成共識的方法前,筆者要先來介紹一個樸實無華但重要的概念:摘要(Digest),其顧名思義就是一段內容經過消化的產物。假設有一種摘要產生器,這個機器可以放入一張紙條,然後透過 3 個步驟計算出紙條的摘要。
摘要產生器將記載訊息的紙條切成一條一條固定寬度的細長條狀紙帶,如下圖:
2. 將這些紙帶依照順序接成一個長條紙帶。紙帶上有字跡的黑色部分與沒字跡的白色部分會出現不規則相間,測量每個黑色區塊之間相鄰的距離,如下圖:
3. 每段距離的數字相乘後的數字就是這個紙條的摘要(Digest)。
每個 EPC 參與者都會有一台摘要產生器,而它需要上緊發條才能開始工作,且每計算完一張紙條便須重新上一次發條。
摘要的計算雖然簡單,卻具有一些很有用的特性:
首先,摘要會隨著紙條內容的變動而更動。只要更動了任何一點紙條內容,例如區塊的交易順序,或者流水號(Nonce),都會使摘要改變。因此一個附上摘要的紙條,可以讓收到紙條的人在收到後再自行計算一次摘要並比對兩者,以驗證紙條的內容是否被修改過。因此,摘要是可驗證的(Verifiable)。
若想在不更動摘要的情況下同時變動紙條內容,只能不斷嘗試用不同內容產生摘要,直到發生碰撞(Collision) — 意即兩個不同內容的紙條出現相同摘要。
其次,摘要也是單向的:一個紙條很容易產出摘要,但摘要很難還原出原本的紙條內容。這也代表摘要是隨機且難以預測的,因此摘要可以作為一種亂數(Random Number)來源。
正式的區塊鏈使用更難預測且更不易碰撞的的密碼雜湊函數(Cryptograpgic Hash Function)產生訊息摘要。
理解關於區塊鏈技術的基本要件後,接下來就來看看區塊鏈技術的精妙之處:共識機制。
共識機制:如何達成共識?
在區塊鏈技術中,大致上有兩種方式可以產生共識:抽彩(Lottery)或表決(Vote),它們各自有不同特性,每一種分散式帳本都會使用其中之一作為共識機制。
抽彩
在抽彩機制中,唯有摘要小於門檻值的「合法」區塊才會被所有參與者收受。然而,區塊生產者無法預測摘要,且可驗證的摘要使區塊生產者難以作弊。因此若想生產數字小於門檻值的摘要,區塊生產者必須不斷改動區塊內容,例如流水號或者交易順序,直到找到摘要小於門檻值的區塊,就像抽彩一樣。只有合法的區塊才會被區塊生產者散佈給其他 EPC 參與者。
在這樣的規則下,可能會同時出現多個合法區塊。還記得區塊鏈中「鏈」的部分嗎?當收受多個低於門檻的區塊時,該選哪個區塊作為上一個區塊呢?這裡我們可以用一些簡單的規則來做抉擇:選擇合法區塊中高度(Height)最高的區塊,若高度一樣則選擇摘要數字較低的區塊。
區塊紙條的摘要就是正式區塊鏈中的區塊雜湊值。在正式的區塊鏈中,門檻值愈低,困難度(Difficulty)也愈高。區塊的選擇規則也稱為分岔選擇規則(Fork Choice Rule),使用可驗證的亂數作為共識的做法又稱為中本共識(Nakamoto Consensus)。
表決
有別於複雜的抽彩,表決機制相當直觀:所有參與者針對某個預先選出的領袖(Leader)的提案(Proposal),也就是區塊,進行投票。領袖是怎麼選出的?一個直覺的做法是按照假名的順序,按照 Alice / Bob / Charlie 的順序,所有參與者輪流擔任領袖。
所有參與者在收到提案後,可以選擇同意或反對這個區塊的內容,若同意的話,則將自己對提案的同意票記在紙條上,並將這個投票紙條散佈給所有其他參與者。若多數的參與者同意了提案,則所有參與者皆須認定該提案為共識。
然而,表決機制雖然直觀,卻不如抽彩具有可驗證性,參與者若想作弊則相對容易:例如,參與者可以重複投票,或者串通其他參與者一起不投票,以破壞帳本;另一方面,表決比抽彩來得有效率,因其不需要所有參與者都費功去製造可能將不被收受的區塊。
拜占庭錯誤(Byzantine Fault)特指這些不在預期內的行為,表決機制事實上也就是拜占庭容錯(Byzantine-fault-tolerant, BFT)演算法。PBFT 家族的協定是目前拜占庭容錯演算法的主流,然而其至多只能容忍不超過參與者總數一半的拜占庭錯誤。若想了解更多 PBFT 的細節,可以參考筆者日前的撰文:
若想搞懂區塊鏈就不能忽視的經典:PBFT
女巫:如何避免帳本被單一個體掌控?
上文提到:為了保證公平的記帳權,帳本上的識別都是假名,如上文提及,Alice 跟 Bob 實際上都是由同一個參與者王小庭所控制,其他參與者不僅難以得知,而且王小庭喜歡的話,他愛用幾個假名就用幾個假名 — 掌控多個假名的王小庭就成為了「女巫」(Sybil)。
不論是採取何種共識機制,女巫的存在都會破壞分散式帳本的安全性:
在抽彩機制中,如果多數的參與者皆由女巫控制,則女巫有很大的機會可以無視規則,不需抽彩便竄改帳本。
在表決機制中,如果由女巫控制的參與者可以集體進行不在預期內的行為,例如重複投票或者不投票。
因此,抵抗女巫對於分散式帳本的安全至關重要。對此,一個直覺的思路是:讓每個假名的行為都必須付出有限的資源,例如錢跟力。因此有兩種方式可以抵抗女巫:要嘛出錢,要嘛出力。
出力:在抽彩機制中,每個合法區塊的生產都必須附有低於門檻的摘要,而摘要的計算需要參與者出力不斷地重上發條。
出錢:在表決機制中,抵押一定數量 EPC 的參與者才能獲選為領袖被生產提案,且若違反規則,參與者的押金將會被沒收。
出力即是工作證明(Proof of Work, PoW);出錢即是權益證明(Proof of Stake, PoS),抵抗女巫的機制稱為抗女巫機制(Sybil-control Mechanism)。
合約:進行條件式的交易
回顧一下本文開頭所提:區塊鏈技術可以用來打造去中心化的運算平台,它可以用以記錄任何資訊,不止餘額,例如一段合約(Contract)。合約就是指一段會依據不同條件而達成不同執行結果的語句。例如:
CheckAndPay
給定 A、B 兩個假名,若 A 的餘額大於/等於 30 EPC,則 A 支付 20 EPC 給 B ,否則 A 不支付任何 EPC。
這個合約就可以被記錄在帳本中:
Alice 100 EPCBob 0 EPCCharlie 0 EPCDavid 0 EPCEva 0 EPCCheckAndPay "給定 A、B 兩個假名,若 A 的餘額大於/等於 30 EPC,則 A 支付 20 EPC 給 B ,否則 A 不支付任何 EPC。"
之後 Alice 就可以發起像這樣的交易:
Tx 99
CheckAndPay, {[Alice], [Bob]}, ALICE
如此,若 Alice 的 EPC 餘額不足 30 EPC 則不會支付 Bob。
觸發合約的 Tx 99 ,它的執行過程比較煩瑣:執行 Tx 99 的參與者首先會從帳本中尋找 CheckAndPay 的合約內容,並從 Tx 99 中取出合約需要的輸入:A 與 B,接著參與者再解讀合約的語句,依照條件進行帳本的狀態轉換。其中,為了使參與者能解讀合約,合約需用所有參與者皆能看懂的語言書寫。
合約又稱智能合約(Smart Contract)。正式的區塊鏈使用虛擬機(Virtual Machine)來解讀與執行合約。事實上,智能合約能做的事情非常多,這使具有智能合約功能的分散式帳本得以成為去中心化的運算平台,例如以太坊(Ethereum)。
總結: 分散式帳本究竟是一個怎樣的系統?
如果以上環節皆運作順利,那麼便能成功只用紙筆便發行了專由學生使用的貨幣。最後再次強調一次:這是一個為了便於使初學者掌握核心觀念而極度簡化的例子。正式運行的區塊鏈,例如以太坊,其實際運作遠遠複雜得多。
還有一些比較進階的概念,雖然礙於篇幅未在此文章提及,但部分主題筆者曾撰文介紹:
可擴展性(Scalability):第二層方案(Layer 2)與分片(Sharding)
隱私(Privacy)與匿名(Anonymity)
共識機制的安全性(Safety)與活躍性(Liveness)
最後,如果日後朋友/家人問起「什麼是區塊鏈」時,我想你會知道如何解釋了:)
ELI5! 區塊鏈到底在幹嘛? was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌