下面，我們看一下FRI協議的具體內容，如圖1所示：
FRI協議分為兩個階段：Commit階段和Query階段。從前面簡單的場景可以看出，一次簡單的迴圈，需要
1. 驗證者傳送隨機數x0
2. 後證明者生成新函式f1，
3. 進行一致性校驗。
FRI協議把每一迴圈前2步歸類到Commit階段，把第3步歸類到了Query階段。即在Commit階段，生成所有的函式f0~fr，r為迴圈的次數，然後在Query階段，統一校驗。
下面，先分別介紹Commit和Query協議裡各引數和各個步驟的意義，然後總結一下相關的流程。
Commit：
· Common input
· R RS編碼比率
· i 迴圈次數索引，取值{0~r}
· r 迴圈次數 取值k0-R/η
· η空間對映引數 x-->x^(2^η)
· L0群的階 2^k0
· RS[F,Li,ρ] 編碼引數[ 有限域，作用域，編碼比率 ]
· q0(x) = x^(2^η)（實際實現的定義，和圖中不一致），L(i+1) = q0(Li)，表示群Li到群L(i+1)的2^η --> 1對映
· Prover input
· fi 第i次迴圈的函式輸入
· Li 第i次迴圈的群，階位2^(n-i)
· RSi fi對應的編碼引數
· LOOP i <= r
· 定義f(i+1) 按照第2步的計算方式
· 儲存f(i+1)的值，在群L(i+1)
· 進入下一步迴圈
· 定義fr 第2步的輸出
· 插值出P(x)
· d是多項式P(x)的度
· 儲存d+1個多項式P(x)的係數 a0~ad
· Commit 階段終止
· Sy 群L(i+1)的每一個元素對應於群Li的元素的集合
· f(i+1)(y) 計算f(i+1)在群L(i+1)上的所有取值
· xi 驗證者傳送的隨機數
· 1
· 2
· 3 i==r
· 4 i < r
Query
· verifier input
· R /η /Li /RSi /xi /fi /P(x) 見Commit
· l query次數
·重構fr
· 獲取a0~ad，重構P`(x)
· 計算P`(x)在群Lr上的所有取值，並賦值給fr，注fr滿足RSr
· repeat l times
· f(i+1)(s(i+1)) = Pi(xi)
· 在Si上，插值出Pi(x)
· Si 滿足s(i+1) = q0(x)的x的集合
· i = {0~r-1}
· i = {0~r-1}
· round consistency check i = {0~r-1}
· 都成功，則驗證透過
下面，以η = 1（即，q0(x) = x^2）為例，FRI協議的兩個階段的過程如圖2所示：
由以上流程可以看出：
· 針對每一輪的一致性的校驗，確保了原始多項式f0的確滿足d < ρ*2^n
· 上述協議重複l次，可以大大降低作惡者成功的概率
總結
以上就是FRI協議的具體過程，可以看出，驗證複雜度滿足對數關係r = Log2(ρ*2^n)。演算法保證了，當且僅當原始多項式f0是小於ρ*2^n時，所有的round consistency 校驗才會透過。真正的實現可能略有差別，具體的可以參考DEEP-FRI論文，相對於FRI，DEEP-FRI在保持證明和驗證的最優複雜度的同時，提高了系統的可靠性。
結合本系列的前三篇的文章，總結ZK-STARK的演算法如下：
演算法分為兩部分：算術化和LDT
算術化把問題轉換位多項式相等以及多項式的LDT問題
LDT階段使用FRI協議，保證線性級的證明覆雜度和對數級的驗證複雜度
零知識屬性保證驗證者不能訪問軌跡多項式裡的點，軌跡多項式裡儲存著隱私值
同時為了保證零知識屬性，需要對軌跡多項式附加數行隨機值，由驗證者和證明者協商確定
整個過程，不需要第三方的CRS
整個過程，不依賴任何數學難題
附錄
官方FRI的簡單介紹 https://medium.com/starkware/low-degree-testing-f7614f5172db
FRI paper https://eccc.weizmann.ac.il/report/2017/134/
DEEP-FRI paper chrome-extension://cdonnmffkdaoajfknoeeecmchibpmkmg/assets/pdf/web/viewer.html?file=https%3A%2F%2Farxiv.org%2Fpdf%2F1903.12243.pdf
Reed-Solomen WIKI https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction
