📜 [專欄新文章] 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.
👏 歡迎轉載分享鼓掌
零知識證明 在 [新聞] 零知識證明的抗量子協議以加強區塊鏈安全 - 批踢踢實業坊 的推薦與評價
新聞來源連結：
https://bit.ly/3A6sUDG
新聞本文：
Researchers at Technology Innovation Institute (TII) in the United Arab
Emirates have improved the feasibility of a new class of algorithms to
protect blockchain applications against quantum computing cryptographic
attacks. This builds on the considerable research already underway across the
cryptographic community in developing better protocols for improving
zero-knowledge proofs.
阿拉伯聯合大公國技術創新研究所 (TII) 的研究人員提高了一類新算法的可行性，以保
護區塊鏈應用程序免受量子計算密碼攻擊。這建立在整個加密社區已經進行的大量研究的
基礎上，該研究旨在開發更好的協議以改進零知識證明。
The specialised area of cryptography has been gaining significant interest
since zero-knowledge proofs are widely used in techniques like blockchain,
smart contracts, and identity verification.
由於零知識證明廣泛用於區塊鏈、智能合約和身份驗證等技術，密碼學的專業領域引起了
人們的極大興趣。
The most popular approaches have involved using matrix computations. However,
there is some concern that future research may find new and improved ways to
compromise these protocols. So, researchers are always looking for promising
alternatives to provide multiple types of protection against future
cryptographic attacks.
最流行的方法涉及使用矩陣計算。然而，有人擔心未來的研究可能會找到新的和改進的方
法來破壞這些協議。因此，研究人員一直在尋找有前途的替代方案，以提供多種類型的保
護以防止未來的密碼攻擊。
Need for alternative approaches
需要替代方法
The various types of quantum-resistant problems and algorithms built on them
are considered safe at the present time, because no one has demonstrated a
credible quantum computer attack against them. Emanuele Bellini, Lead
Cryptographer at TII, said: “We are in the early stages of understanding
what is quantum-resistant and what is not. The safest approach is to build
the quantum-resistant scheme based on many different problems so that if one
is broken, you are still hopeful that the others are not.”
目前，各種類型的抗量子問題和建立在它們之上的算法被認為是安全的，因為沒有人證明
過可信的量子計算機攻擊它們。 TII 的首席密碼學家 Emanuele Bellini 說：“我們正
處於了解什麼是量子抗性、什麼不是的早期階段。最安全的方法是基於許多不同的問題構
建抗量子方案，這樣即使一個被破壞，你仍然希望其他的沒有。”
Most of the work on quantum-resistant protocols for zero-knowledge proofs has
been based on lattices. Lattices are very flexible and are one of the most
malleable cryptographic mathematical structures that can be applied across
the board. The TII team has focused on alternatives to lattices based on the
Rank Syndrome Decoding problems, which, although promising, still need more
research to make them a credible solution.
用於零知識證明的抗量子協議的大部分工作都基於格。晶格非常靈活，是可以全面應用的
最具延展性的加密數學結構之一。 TII 團隊專注於基於 Rank Syndrome Decoding 問題
的格子替代方案，雖然前景廣闊，但仍需要更多研究才能使它們成為可靠的解決方案。
Cryptography is a bit of a cat-and-mouse game, where researchers are
constantly finding enhanced solutions to break protocols and more effective
ways to implement them. It is not even necessary to completely break an
approach to reduce its attractiveness. Bellini said, “If someone discovers
an attack to the lattice problem that just slightly improves the previous
attack, it means that the lattice parameters would have to become larger, and
then other approaches would become relatively more efficient.”
密碼學有點像貓捉老鼠的遊戲，研究人員不斷尋找增強的解決方案來破壞協議以及更有效
的實施方法。甚至沒有必要完全打破一種方法來降低其吸引力。貝里尼說，“如果有人發
現對格子問題的攻擊只是稍微改進了之前的攻擊，這意味著格子參數必須變大，然後其他
方法會變得相對更有效。”
The importance of zero-knowledge proofs
零知識證明的重要性
“Zero-knowledge” has recently become the most popular keyword in
cryptographic papers presented at conferences. The popularity of these
protocols grew in response to the enthusiasm around blockchain since this is
the most common use case. In these applications, the goal is to be able to
prove a statement is true without the rest of the blockchain understanding
information about the exchange. The simplest implementations of
zero-knowledge protocols are often used for identity verification.
“零知識”最近成為會議上發表的密碼論文中最受歡迎的關鍵詞。由於區塊鍊是最常見的
用例，因此這些協議的受歡迎程度隨著對區塊鏈的熱情而增長。在這些應用程序中，目標
是能夠證明一個陳述是真實的，而無需區塊鏈的其餘部分理解有關交換的信息。零知識協
議的最簡單實現通常用於身份驗證。
A zero-knowledge-proof protocol organised the interaction between two parties
in which one is the prover and the other the verifier. The two parties
exchange information, and after the exchange, the prover can confirm the
truthfulness of the statement, such as whether someone has enough money in a
blockchain wallet for a transaction without knowing the total in the wallet.
This is also done in a way that hides information from third-party observers.
零知識證明協議組織了兩方之間的交互，其中一方是證明者，另一方是驗證者。雙方交換
信息，交換後，證明者可以確認陳述的真實性，例如某人在區塊鏈錢包中是否有足夠的錢
進行交易，而無需知道錢包中的總數。這也是以向第三方觀察者隱藏信息的方式完成的。
Initially, the zero-knowledge-proof community focused on using classical
cryptographic algorithms based on discrete logs or factorisation problems.
The community has recently started exploring quantum-resistant zero-knowledge
proofs.
最初，零知識證明社區專注於使用基於離散日誌或分解問題的經典密碼算法。社區最近開
始探索抗量子零知識證明。
Classical algorithms were inefficient, and the quantum-resistant
implementations are even less so because they require larger keys. They also
require larger parameters such as the size of the proof, the number of bits
that need to be communicated between prover and verifier, and the amount of
work each party must perform to build the proof. These quantum-resistant
protocols might take minutes or hours to run compared to a few seconds for
the protocols built on classical algorithms.
經典算法效率低下，而抗量子實現的效率更低，因為它們需要更大的密鑰。它們還需要更
大的參數，例如證明的大小、證明者和驗證者之間需要通信的比特數以及各方為構建證明
而必須執行的工作量。與基於經典算法的協議相比，這些抗量子協議可能需要幾分鐘或幾
小時才能運行。
Rank Syndrome Decoding problem
Rank Syndrome 解碼問題
TII’s researchers studied the Rank Syndrome Decoding problem, an evolution
of another technique called the Syndrome Decoding problem. Other popular
quantum techniques have included the shortest vector problem, the NTRU
problem, the isogenies problem, and the multivariate quadratic problem.
TII 的研究人員研究了 Rank Syndrome Decoding 問題，這是另一種稱為 Syndrome
Decoding 問題的技術的演變。其他流行的量子技術包括最短向量問題、NTRU 問題、同構
問題和多元二次問題。
These different classes of problems organise numbers into a particular
structure that is best suited for verifying a zero-knowledge proof built on
top of the problem. The shortest vector and NTRU are similar and use lattices
to encode the numbers to compute the problem’s answer. Multivariate problems
use a system of polynomials to organise the calculation. The Syndrome
Decoding Problem uses a linear code. The Rank Syndrome Decoding problem is
similar to the Syndrome Decoding problem but organises the linear codes more
efficiently.
這些不同類別的問題將數字組織成一個特定的結構，最適合驗證建立在問題之上的零知識
證明。最短向量和 NTRU 相似，使用格子對數字進行編碼以計算問題的答案。多元問題使
用多項式系統來組織計算。Syndrome Decoding問題使用線性代碼。
Rank Syndrome Decoding 問題類似於 Syndrome Decoding 問題，但可以更有效地組織線
性代碼。
Emanuele Bellini, Lead Cryptographer at the TII, said: “The Rank Syndrome
Decoding problem is not something we invented. However, it is a newer problem
than Syndrome Decoding and the lattice problems, so it is less studied.”
TII 的首席密碼學家 Emanuele Bellini 說：“Rank Syndrome Decoding 問題不是我們
發明的。然而，它是一個Syndrome Decoding和格問題更新的問題，因此研究較少。”
More efficient and adaptable
更高效、適應性更強
TII’s researchers improved the efficiency of RSD and implemented it in a way
that is more adaptable to different use cases. Their implementation is 60%
smaller, and the parameters are 1% of the size compared to the
state-of-the-art Syndrome Decoding implementation for a given proof. It is
also considerably faster, solving one benchmark proof in 47 ms compared to
5,000 ms for Syndrome Decoding.
TII 的研究人員提高了 RSD 的效率，並以更適合不同用例的方式實施。對於給定的證明
，與最先進的Syndrome Decoding實現相比，它們的實現小了 60%，參數大小只有其大小的
1%。它也快得多，與 Syndrome Decoding 的 5,000 ms 相比，它在 47 ms 內解決了一個
基準證明。
A key building block of this new construction is a commitment scheme that
essentially requires one party to commit to a statement, such as having
executed a certain amount of work, which can be verified later as part of a
transaction.
這種新結構的一個關鍵構建區塊是一個承諾方案，它本質上要求一方承諾一個聲明，例如
執行了一定數量的工作，稍後可以作為交易的一部分進行驗證。
TII researchers also demonstrated how this commitment scheme could be built
into any kind of circuit, which is a fundamental building block for
cryptographic transactions. Prior research had examined how RSD could be
applied to signature schemes based on identification protocols using
zero-knowledge proofs. However, the TII research is the first demonstration
of how RSD could apply to any arbitrary circuit that could be used across
many different applications.
TII 研究人員還演示了如何將這種承諾方案構建到任何類型的電路中，這是加密交易的基
本構建區塊。先前的研究已經研究瞭如何將 RSD 應用於基於使用零知識證明的識別協議
的簽名方案。然而，TII 研究首次展示了 RSD 如何應用於可用於許多不同應用的任意電
路。
An arbitrary circuit in cryptography is analogous to an electrical circuit in
a computer chip in which bits are logically combined using gates that perform
logical operations such as executing AND, OR, and NOT statements. Bellini
said: “if you have enough of these gates, you can build any function.”
密碼學中的任意電路類似於計算機芯片中的電路，其中使用執行邏輯運算（例如執行 AND
、OR 和 NOT 語句）的門對位進行邏輯組合。貝里尼說：“如果你有足夠多的這些門，你
就可以構建任何功能。”
The proof size required for verifying the statement grows at a quasi-linear
rate. This means that larger statements require more computation to prove but
not nearly as much as would be needed if the proof size grew at a quadratic
or exponential rate.
驗證語句所需的證明大小以準線性速率增長。這意味著更大的語句需要更多的計算來證明
，但如果證明大小以二次或指數速度增長，則沒有所需的那麼多。
Reducing the cheating probability
降低作弊概率
A zero-knowledge proof is not the same as a mathematical proof. A
mathematical proof is a deterministic process that allows someone to assert
whether a statement is true or false based on certain assumptions. In
contrast, a zero-knowledge proof is a probabilistic proof in which a
statement is proved with a certain degree of probability. The probability of
making a mistake is called the soundness error or cheating probability since
it represents the risk that someone might be cheating but not caught.
零知識證明與數學證明不同。數學證明是一個確定性的過程，它允許某人根據某些假設斷
言一個陳述是真是假。相比之下，零知識證明是一種概率證明，其中一個陳述以一定的概
率被證明。犯錯的概率被稱為可靠性錯誤或作弊概率，因為它代表了某人可能作弊但未被
抓住的風險。
This error can be made as small as possible by repeating the calculation
multiple times. The current implementation’s cheating probability is 2/3 on
the first pass, which is insufficient to convince a verifier. However, by
repeating the proof 219 times, the cheating probability drops to 1/2128,
which is extremely low. “The fact that it is wrong is less probable than a
meteor will fall on your head this afternoon,” said Bellini.
通過多次重複計算，可以使這個誤差盡可能小。當前實現的第一遍作弊概率為 2/3，不足
以說服驗證者。但是，通過重複證明219次，作弊概率下降到1/2128，非常低。貝里尼說
：“這件事是錯誤的，遠比今天下午流星落在你頭上的可能性要小。”
Future research is looking at how to reduce the soundness error of the
fundamental building blocks even further. But this needs to be approached
cautiously since it may reduce the probability by creating a much longer
proof that takes more time to execute. Bellini expects this to be doable
since there are already examples of reducing the likelihood from 2/3 to 1/2
when using RSD for identification protocols. This would mean the researchers
would only need to repeat the process 128-times rather than 219-times!
未來的研究將著眼於如何進一步降低基本構建區塊的可靠性誤差。但這需要謹慎處理，因
為它可能會通過創建需要更多時間來執行的更長的證明來降低概率。 Bellini 預計這是
可行的，因為在使用 RSD 進行識別協議時，已經有將可能性從 2/3 降低到 1/2 的例子。
這意味著研究人員只需要重複這個過程 128 次而不是 219 次。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 112.78.82.243 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/DigiCurrency/M.1633434604.A.CAF.html
... <看更多>