作者：Fox Tech CEO 康水躍，Fox Tech 首席科學家孟鉉濟
隨著比特幣、區塊鏈、智能合約等概念的鋪開，越來越多的人關注到Web3領域的蓬勃發展。而在技術方面，也有許多開發者關注到支撐區塊鏈底層的密碼學協議。在這之中，零知識證明協議以其獨特的特性大放異彩，無論是在實現隱私保護，還是在實現Layer2性能擴容的zkrollup項目當中，都發揮著關鍵的作用。
零知識證明是一類算法的統稱，到目前為止，研究者發明了包括Plonk、Groth16、zkStark、Virgo、Orion、Foaks等等在內的許多種協議。不同的協議適用於不同的計算場景，複雜度和效率也各有不同，例如Foaks就以線性的證明時間和較小的證明長度為優勢。
上述的每一種協議，協議目標是相同的，就是證明者（Prover）希望在不向驗證者（Verifier）透露任何關於自己的秘密的信息的情況下讓驗證者相信自己擁有秘密。 sum-check protocol是很多協議的組件，最早在[LFKN92]當中被提出。很多計算問題可以被轉化成sum-check protocol能處理的問題，從而生成證明。包括Foaks在內的不少協議的底層協議都基於sum-check protocol，在其上進行調整來實現。
在Fox Tech所採用的Foaks證明系統當中，該協議同樣發揮著重要的作用。具體來講，為了實現對於某一操作碼opcode正確性的證明，需要先將其轉化為算術電路，之後轉換為矩陣，最終生成多項式，對多項式應用證明系統當中的算法，在最後壓縮證明的部分當中，同樣將證明者（Prover）和驗證者（Verifier）之間的交互過程轉換為計算某個和式，也就是sum-check protocol的過程。
圖1: Sum-check Protocol所在環節
Sum-check Protocol
1.協議目標
協議的目標非常簡單且容易理解。
假設我們有一個定義在有限域F上的v元多項式，記作g。協議的目標是計算和式：
H :=b10,1b20,1...bv0,1g(b1, ... ,bv)
和在zkRollup當中考慮的“外包計算”的場景類似，在應用當中，上述式子的計算量會非常大，我們希望將這個式子的計算交給證明者（Prover），之後證明者向驗證者（Verifier）證明自己的計算結果是正確的。
2. 協議假設
首先，需要明確在這個協議當中驗證者的能力。我們假設驗證者擁有可以計算函數g的預言（Oracle）。也就是說，對於驗證者而言，確定某個輸入r1, ... ,rv之後，計算g(r1, ... ,rv)是容易的。但是計算完整的結果H是困難的。
事實上，在現實應用當中，預言（Oracle）不會存在，但是可以通過某種手段實現，例如我們可以讓證明者幫助驗證者計算這個值，並用更多的技巧附加正確性的證明。
第二點，關於協議的目標，事實上sum-check協議可以對於任意的集合B計算bBmg(b)，但是不失一般性的，我們假設B={0,1}。
3. 協議過程
協議一共包含v輪。在每一輪當中會處理g中的一個變量。
第1輪：
證明者發送多項式g1(X1)，並聲明g1(X1)=（x2,...,xv）0,1v-1g(X1,x2, ... ,xv)。
如果證明者是誠實的，應當成立H=g1(0)+g1(1)。驗證者驗證，若通過則選擇隨機數r1發送給證明者。注意到，根據協議的假設，證明者可以完成上述驗證。
我們用degi(p)來表示多元多項式p當中，第i個變量的次數。 g1(X1)的次數為deg1(g)，所以我們知道g1可以用deg1(g)+1個域元素表出。
第j(j>1)輪：
證明者發送多項式gj(Xj)，並聲明gj(Xj)=（xj+1,...,xv）0,1v-jg(r1, ... ,rj-1,Xj,xj+1, . .. ,xv)。
如果證明者是誠實的，應當成立gj-1(rj-1)=gj(0)+gj(1)。驗證者驗證，若通過則選擇隨機數rj發送給證明者。
第v輪：
證明者發送多項式gv(Xv)，並聲明gv(Xv)=g(r1, ... ,rv-1,Xv)。
如果證明者是誠實的，應當成立gv(rv)=g(r1, ... ,rv-1,rv)。驗證者驗證，若通過則可以相信H=g1(0)+g1(1)。
圖2: The Foaks Sum-check protocol
Completeness: 若證明者擁有有效的Witness，則驗證者會以不低於（1-negl(n)）的概率接受證明；
Soundness： 若證明者沒有有效的Witness，則驗證者會以低於negl（n）的概率拒絕證明
Succinctness: Proof的Size必須遠小於Witness的Size；
Zero-knowledge：驗證者無法通過證明的交互過程獲取任何關於witness的信息
#其中negl（n）為任意可忽略的函數
4. 協議複雜度
通過第3部分的論證，我們可以看到，協議一共由v輪組成，每一輪當中證明者需要給驗證者發送一個degi(g)次的多項式，也就是deg1(g)+1個域元素，所以總體的通信複雜度是O(i=1vdegi(g))。關於計算複雜度方面，在每一輪驗證都通過的情況下，證明者最多需要進行2v次對g取值的運算；驗證者做的運算是對每一輪的gj進行取值以及在最後一輪對g取值。
下表具體展示了複雜度的結果，其中T代表訪問一次預言（Oracle）也就是對g進行一次求值所需要的開銷。
圖3:Sum-check協議的複雜度
Sum-check Protocol的應用
在許多的零知識證明算法當中，sum-check protocol都在發揮著重要的作用。許多問題的證明，都依賴於將原始的問題轉化為sum-check的形式，再完成後續的步驟。
例如，可以利用sum-check protocol來計算一個無向圖中的三角形數量。
首先，我們使用鄰接矩陣A表示無向圖G，設E為其邊集合，則Ai,j=1(i,j)E，也就是說若點i,j之間存在一條邊則Ai,j =1否則為0。對於點i,j,k，三點構成三角形的條件是Ai,j=1,Ai,k=1,Aj,k=1。
接下來記矩陣A為一映射表，表示的映射為f:{0,1}log n{0,1}log n{0,1}，其中logn為i，j的二進制長度。所以對於點i,j,k，三點構成三角形的條件進一步可以表示為f(i,j)f(i,k)f(j,k)=1。
所以，G中全部三角形的數量h可以表示為h=16i,j,k{0,1}log nf(i,j)f(i,k)f(j,k)。再定義三元多項式g(I,J,K)=f(i,j)f(i,k)f(j,k)。則有6h=i,j,k{0,1}log ng(i,j,k)。於是使用sum-check protocol計算H=i,j,k{0,1}log ng(i,j,k)即可。
此外，在許多證明系統當中，都採用了sum-check protocol作為底層邏輯進行構造。下圖展示了根據在sum-check基礎上進行不同改造得到的不同證明系統。
圖4: Sum-check protocol在四類證明系統當中的應用
圖5: Sum-check protocol在簡潔證明方面的具體應用
結語
本文梳理了sum-check協議的具體流程，以及討論了協議的複雜度，同時展示了其在許多證明系統當中的應用。
在web3領域不斷拓展的當下，密碼學作為區塊鏈技術的底層構件，其作用顯得越來越重要。隨著zkrollup、隱私保護等等依賴零知識證明的應用和項目逐漸誕生，sum-check協議，作為諸多證明系統的重要組件，也正在被學界和產業界同時給予越來越多的關注。
參考文獻
[LFKN92] Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. J. ACM, 39:859–868, October 1992.
https://people.cs.georgetown.edu/jthaler/sumcheck.pdf
介紹sum-check的中文博客https://blog.csdn.net/mutourend/article/details/111610754
APP 
