序言

密碼算法之中的零知識證明技術的應用 web3 全球擁有廣泛應用，包含開展隱私計算、zkRollup 等。在其中 Layer2 新項目 FOX 所使用的 FOAKS 就是一個零知識證明優化算法。在相關的一系列運用之中，針對零知識證明優化算法來講，只有兩個層面特性極其重要，那便是算法的效率及其互動性。

算法效率起著至關重要的作用，高效率的算法能明顯的下降系統軟件使用時間，從而減少手機客戶端延遲時間，明顯的提升用戶體驗和效率，那也是 FOAKS 專注于完成線形證明時長的一個重要原因。

另一方面，從密碼算法的角度來說，零知識證明系統設計通常依靠證明者與驗證者多次互動。比如在很多詳細介紹零知識證明的科普讀物之中都會采用的“零知識洞窟”故事之中，證明的完成就取決于阿里（證明者）和新聞記者（驗證者）多次的信息的傳遞互動才能達到。但是實際上，在很多應用領域之中，依靠互動會使系統軟件不會再可以用，或是非常高的提升延遲時間。就像是在 zkRollup 系統軟件之中，大家期待證明者（其實就是 FOX 之中的 folder）可以在本地，不依賴和驗證者互動的情況下算出正確證明值。

從這點說，如何把交互式的零知識證明協議更新改造屬于非交互式，便是一個很有意義的問題。在這篇文章之中，我們將要詳細介紹 FOX 應用經典 Fiat-Shamir 啟發性（heuristic）來形成 Brakedown 里的考驗以此來實現非交互式協議的一個過程。

零知識證明里的 Challenge

零知識證明優化算法伴隨著運用的鋪平逐漸變得異?；鸨?，近幾年來也出現了包含 FOAKS、Orion、zk-stark 在內的各種各樣優化算法。這種優化算法，及其登陸密碼學術界早期 sigma 協議等關鍵證明邏輯性全是證明者（Prover）先把某一值發給驗證者（Verifier），驗證者根據當地隨機數字產生一個考驗（Challenge），把這個任意造成的考驗值發送給證明者，證明者必須確實有文化才可以以很有可能作出根據驗證者回應。比如在零知識洞窟之中，新聞記者拋一個硬幣，告知阿里從左邊出去還是對于右邊出去，這兒的“左和右”便是對阿里巴巴集團考驗，他如果真了解符咒，就一定能從標準的方向走出去，不然就會有一半的幾率不成功。

這兒我們注意到，Challenge 的形成是一個很重要的流程，生活中有2個規定，任意且不可被證明者預測分析。第一點，偶然性確保了它幾率特性。第二點，假如證明者可以預測考驗值也就意味著協議安全性被破壞，證明者并沒有專業知識還可以通過驗證，還可以繼續對比，阿里如果可以預測分析記者要求我從哪兒出去，他即便沒有符咒還可以提前進入那一邊，結論表達出來一樣能通過協議。

所以我們要一種方法，可以讓證明者自身當地形成這樣一個難以預測的隨機數字，同時也可以被驗證者驗證，那樣就能實現非交互式的協議。

哈希函數（Hash Function）

哈希函數的名稱對于我們來說也許應該十分熟悉，不論是在比特幣的共識協議 POW 之中出任挖礦的世界數學難題，或是縮小信息量，結構信息驗證碼等，都是有哈希函數身影。但在以上不同類型的協議之中，其實就是應用了哈希函數的多種不同特性。

具體而言，安全哈希函數的特性包含以下幾個方面：

膨脹性：確立的哈希函數能將隨意長度消息壓縮變成固定不動長短。

實效性：給出鍵入 x，測算導出 h（x）是很容易的。

抗撞擊性：已知一個鍵入 x1，期待尋找另一個鍵入 x2，x1x2，h（x1）= h（x2），是艱難的。

留意，假如哈希函數達到抗撞擊性，那樣必定達到不可逆性，換句話說給出一個導出 y，要找到 x 達到 h（x）= y 是艱難的。在密碼算法之中，沒法結構出本質上肯定達到不可逆性的函數公式，可是哈希函數在實際應用之中能夠基本上看作單邊函數公式。

這樣一來，不難發現以上這幾種運用分別代表于哈希函數的幾點不一樣的特性，與此同時大家說，哈希函數還有一個很重要的的作用是給予偶然性，盡管密碼算法基礎理論之中標準的完美隨機數生成器現階段也難以結構，可是哈希函數在具體之中同樣也可以當做角色，這就給大家下文推薦的 Fiat-Shamir 啟發性（Heuristic）技巧帶來了基本。

Fiat-Shamir 啟發性（Heuristic）

實際上，Fiat-Shamir 啟發性（Heuristic）就是通過哈希函數來對前邊產生的腳本制作開展哈希運算，從而獲得一個值，用這種值來當做考驗值。

由于將哈希函數 H 看作一個隨機函數，挑戰是勻稱隨機事件被挑選，不同于證明者公開數據和約定的。安全分析覺得 Alice 不可以預測分析 H 輸出，只有把它當作一個 oracle。在這樣的情況下，Alice 在沒有遵照協議的情形下作出合理回應的幾率 ( 尤其是當他不知道必需的真相時 ) 與 H 的函數值域大小反比。

圖 1: 運用 Fiat-Shamir Heuristic 完成非交互式證明

非交互式 FOAKS

在這節，大家詳細展現 Fiat-Shamir 啟發性在 FOAKS 協議之中的運用，主要是用于造成 Brakedown 一部分的考驗，以此來實現非交互式的 FOAKS。

首先我們要見到，在 Brakedown 形成證明的流程之中，必須考驗的流程是“類似性檢測”及其 Merkle Tree 的證明一部分（閱讀者可以參考一下其他回答《一文掌握 FOAKS 之中的代數式服務承諾協議 Brakedown》）。針對第一點本來的過程是證明者在這兒必須驗證者所產生的一個隨機向量，計算步驟如圖所示：

圖 2: 非互動證明 FOAKS 里的 Brakedown Checks

如今我們應用哈希函數，讓證明者自身造成這一隨機向量。

令γ0=H(C1,R, r0,r1)，相對應的，在驗證者驗證測算之中，也要增加這一算出γ0的流程。依據那樣的結構，不難發現，在形成服務承諾以前，證明者根本無法提早預測分析考驗值，因此不可以提早依據考驗值來相對應的“舞弊”，其實就是相對應的形成假服務承諾值，與此同時，依據哈希函數輸出偶然性，這一考驗值也達到偶然性。

針對第二點，令 ? =H(C1,R, r0,r1,c1,y1,cγ0,yγ0)。

使用偽代碼得出改造設計非交互式的 Brakedown 代數式服務承諾之中的證明和驗證函數公式，那也是 FOAKS 系統軟件之中所使用的函數公式。

1. function PC. Commit(?)：
2. Parse was a k × k matrix. The prover locally computes the tensor code encoding C1，C2 ，C1 is a k × n matrix，C2 is a n × n matrix.
3. for i ∈ [n] do
4. Compute the Merkle tree root Roott=Merkle.Commit(C2[:,i])
5. Compute a Merkle tree root R=Merkle.Commit([Root0,......Rootn-1]),and output R as the commitment.
6. function PC. Prover(?, X, R)
7. The prover generates a random vector γ0 ∈ Fk by computing: γ0 =H(C1,R, r0,r1)
8. Proximity:

1. Consistency:

1. Prover sends c1,y1,cγ0,yγ0 to the verifier.
2. Prover computes a vector ? as challenge, in which ? = H(C1,R, r0,r1,c1,y1,cγ0,yγ0)
3. for idx ∈ ? do
4. Prover sends C1 [:,idx] and the Merkle tree proof of Rootidx for C2 [:,idx] under R to verifier
5. function PC. VERIFY_EVAL(ΠX,X,y= ? (X),R)
6. Proximity: ?idx ∈ ?, Cγ0 [idx] == <γ0, C1[:,idx]> and Ec(yγ0) == Cγ0
7. Consistency: ?idx ∈ ?, C1 [idx] == <γ0, C1[:,idx]> and Ec(y1) == C1
8. y==1, y1>
9. ?idx ∈ ?, Ec ( C1[:,idx])is consistent with ROOTidx, and ROOTidx’s Merkle tree proof is valid.
10. Output accept if all conditions above holds. Otherwise output reject.

結束語

很多的零知識證明優化算法在規劃之時都依靠證明者與驗證者彼此之間的互動，但這種交互式證明協議不應該用在追求高效，網絡通信開銷大的使用場景下，例如鏈上數據隱私保護和 zkRollup 等。根據 Fiat-Shamir 啟發性（Heuristic），能夠在沒有毀壞協議安全系數的條件下讓證明者當地生成隨機數“考驗”，并可以被證明者驗證。依據此方法，FOAKS 一樣完成了非交互式的證明，并運用在設備之中。

論文參考文獻

1.Fiat, Amos; Shamir, Adi (1987). "How To Prove Yourself: Practical Solutions to Identification and Signature Problems". Advances in Cryptology — CRYPTO' 86. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 263: 186–194. doi:10.1007/3-540-47721-7_12. ISBN 978-3-540-18047-0.

2.https://www.cnblogs.com/zhuowangy2k/p/12246575.html

來源：liurui