撰文：康水躍，Fox Tech CEO；孟鉉濟，Fox Tech 首席科學家
前言
密碼學當中的零知識證明技術在web3世界有著廣泛的應用，包括進行隱私計算、zkRollup等等。其中Layer2項目FOX所使用的FOAKS就是一個零知識證明算法。在上述的一系列應用當中，對於零知識證明算法而言，有兩方面屬性極為重要，那就是算法的效率以及交互性。
算法效率的重要性不言而喻，高效的算法可以明顯的降低系統運行時間，從而降低客戶端延遲，顯著的提高用戶體驗和效率，這也是FOAKS致力於實現線性證明時間的一個重要原因。
另一方面，從密碼學的角度來講，零知識證明系統的設計往往依賴證明者和驗證者的多輪交互。例如在許多介紹零知識證明的科普文章當中都會使用的“零知識洞穴”的故事當中，證明的實現就依賴於阿里巴巴（證明者）和記者（驗證者）多輪的信息傳遞交互才能實現。但是事實上，在許多應用場景當中，依賴交互會使得系統不再可用，或者極高的增加延遲。就像在zkRollup系統當中，我們期望證明者（也就是FOX當中的folder）能夠在本地，不依賴於和驗證者交互的情況下就計算出正確的證明值。
從這個角度說，如何將交互式的零知識證明協議改造為非交互式，就是一個很有意義的問題。在這篇文章當中，我們將介紹FOX使用經典的Fiat-Shamir啟發式（heuristic）來生成Brakedown中的挑戰從而實現非交互式協議的過程。
零知識證明中的Challenge
零知識證明算法隨著應用的鋪開而變得異常火爆，近些年也誕生了包括FOAKS、Orion、zk-stark等在內的各種算法。這些算法，以及密碼學界早期的sigma協議等的核心證明邏輯都是證明者（Prover）先將某個值發送給驗證者（Verifier），驗證者通過本地隨機數產生一個挑戰（Challenge），將這個隨機產生的挑戰值發給證明者，證明者需要真的有知識才能以大概率做出通過驗證者的響應。例如在零知識洞穴當中，記者拋一個硬幣，告訴阿里巴巴從左側出來還是從右側出來，這裡的“左和右”就是對阿里巴巴的挑戰，他如果真的知道咒語，就一定可以從要求的方向走出來，否則就有一半的概率失敗。
這裡我們注意到，Challenge的生成是一個很關鍵的步驟，它有兩個要求，隨機和不可被證明者預測。第一點，隨機性保證了它的概率屬性。第二點，如果證明者可以預測挑戰值那就意味著協議的安全性被破壞了，證明者沒有知識也可以通過驗證，可以繼續類比，阿里巴巴如果能預測記者要求他從哪邊出來，他即使沒有咒語也可以提前進入那一邊，結果表現出來一樣可以通過協議。
所以我們需要一種辦法，能夠讓證明者自己本地生成這樣一個不可預測的隨機數，同時還能夠被驗證者驗證，這樣就可以實現非交互式的協議。
哈希函數（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的步驟。根據這樣的構造，可以發現，在生成承諾之前，證明者並不能提前預測挑戰值，於是不能提前根據挑戰值來對應的“作弊”，也就是對應的生成假的承諾值，同時，根據哈希函數輸出的隨機性，這個挑戰值也滿足隨機性。
對於第二點，令I=H(C1,R, r0,r1,c1,y1,c0,y0)。
我們使用偽代碼給出改造後非交互式的Brakedown多項式承諾當中的證明和驗證函數，這也是FOAKS系統當中使用的函數。
-
function PC. Commit()：
-
Parse w as a kk matrix. The prover locally computes the tensor code encoding C1，C2 ，C1 is a kn matrix，C2 is a nn matrix.
-
for i [n] do
-
Compute the Merkle tree root Roott=Merkle.Commit(C2[:,i])
-
Compute a Merkle tree root R=Merkle.Commit([Root0,……Rootn-1]),and output R as the commitment.
-
function PC. Prover(, X, R)
-
The prover generates a random vector 0Fk by computing: 0=H(C1,R, r0,r1)
-
Proximity: c0=i=0k-10[i]C1[:,i],y0=i=0k-10[i]w[i]
-
Consistency: c1=i=0k-1r0[i]C1[:,i],y1=i=0k-1r0[i]w[i]
-
Prover sends c1,y1,c0,y0 to the verifier.
-
Prover computes a vector I as challenge, in which I=H(C1,R, r0,r1,c1,y1,c0,y0)
-
for idxI do
-
Prover sends C1 [:,idx] and the Merkle tree proof of Rootidx for C2 [:,idx] under R to verifier
-
function PC. VERIFY_EVAL(X,X,y=(X),R)
-
Proximity: idxI,C0[idx]==<0,C1[:,idx]>and EC(y0)==C0
-
Consistency: idxI,C1[idx]==
-
y==
-
idxI, EC(C1[:,idx]) is consistent with ROOTidx, and ROOTidx’s Merkle tree proof is valid.
-
Output accept if all conditions above holds. Otherwise output reject.
結語
許多的零知識證明算法在設計之初都依賴證明者和驗證者雙方的交互，但是這種交互式證明協議不適合用在追求高效，網絡通訊開銷大的應用場景下，比如鍊上數據隱私保護和zkRollup等等。通過Fiat-Shamir啟發式（Heuristic），可以在不破壞協議安全性的條件下讓證明者本地生成隨機數“挑戰”，並且可以被證明者驗證。根據這種方法，FOAKS同樣實現了非交互式的證明，並應用在系統當中。
