前言
前言
前言
一級標題
算法效率的重要性不言而喻，高效的算法可以明顯的降低系統運行時間，從而降低客戶端延遲，顯著的提高用戶體驗和效率，這也是FOAKS 致力於實現線性證明時間的一個重要原因。
一級標題
另一方面，從密碼學的角度來講，零知識證明系統的設計往往依賴證明者和驗證者的多輪交互。例如在許多介紹零知識證明的科普文章當中都會使用的“零知識洞穴”的故事當中，證明的實現就依賴於阿里巴巴（證明者）和記者（驗證者）多輪的信息傳遞交互才能實現。但是事實上，在許多應用場景當中，依賴交互會使得系統不再可用，或者極高的增加延遲。就像在zkRollup 系統當中，我們期望證明者（也就是FOX 當中的folder）能夠在本地，不依賴於和驗證者交互的情況下就計算出正確的證明值。
一級標題
零知識證明算法隨著應用的鋪開而變得異常火爆，近些年也誕生了包括FOAKS、Orion、zk-stark 等在內的各種算法。這些算法，以及密碼學界早期的sigma 協議等的核心證明邏輯都是證明者（Prover）先將某個值發送給驗證者（Verifier），驗證者通過本地隨機數產生一個挑戰（Challenge），將這個隨機產生的挑戰值發給證明者，證明者需要真的有知識才能以大概率做出通過驗證者的響應。例如在零知識洞穴當中，記者拋一個硬幣，告訴阿里巴巴從左側出來還是從右側出來，這裡的“左和右”就是對阿里巴巴的挑戰，他如果真的知道咒語，就一定可以從要求的方向走出來，否則就有一半的概率失敗。
一級標題
這裡我們注意到，Challenge 的生成是一個很關鍵的步驟，它有兩個要求，隨機和不可被證明者預測。第一點，隨機性保證了它的概率屬性。第二點，如果證明者可以預測挑戰值那就意味著協議的安全性被破壞了，證明者沒有知識也可以通過驗證，可以繼續類比，阿里巴巴如果能預測記者要求他從哪邊出來，他即使沒有咒語也可以提前進入那一邊，結果表現出來一樣可以通過協議。
一級標題
一級標題
哈希函數（Hash Function）
哈希函數的名字對我們來說或許並不陌生，無論是在比特幣的共識協議POW 當中擔任挖礦的數學難題，還是壓縮數據量，構造消息驗證碼等等，都有哈希函數的身影。而在上述不同的協議當中，其實是運用了哈希函數的各種不同性質。
具體來講，安全的哈希函數的性質包括以下幾點：
抗碰撞性：給定一個輸入x 1 ，希望找到另一個輸入x 2 ，x 1 x 2 ，h（x 1 ）= h（x 2 ），是困難的。
一級標題
注意，如果哈希函數滿足抗碰撞性，那麼必然滿足單向性，也就是說給定一個輸出y，要找出x 滿足h（x）= y 是困難的。在密碼學當中，還不能構造出理論上絕對滿足單向性的函數，但是哈希函數在實際應用當中可以基本視作單向函數。
圖片描述
圖片描述
一級標題
圖片描述
非交互式FOAKS
圖片描述
在本節，我們具體展示Fiat-Shamir 啟發式在FOAKS 協議當中的應用，主要是用來產生Brakedown 部分的挑戰，從而實現非交互式的FOAKS。
圖片描述
圖片描述
結語
結語
function PC. Commit(ϕ)：
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.
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 γ0 ∈ Fk by computing: γ0 =H(C1 , R, r0 , r1 )
Proximity:
Consistency:
Prover sends c1 , y1 , cγ 0 , yγ 0 to the verifier.
Prover computes a vector Î as challenge, in which Î = H(C1 , R, r0 , r1 , c1 , y1 , cγ 0 , yγ 0 )
for idx ∈ Î 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: ∀idx ∈ Î, Cγ 0 [idx] == <γ0 , C1 [:, idx]> and Ec(yγ 0 ) == Cγ 0
Consistency: ∀idx ∈ Î, C1 [idx] == <γ0 , C1 [:, idx]> and Ec(y1 ) == C1
y==
∀idx ∈ Î, 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.
結語
參考文獻
參考文獻
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/zhuowangy 2 k/p/12246575.html
IOS
Android