Step1. Build trace （fib2-example）
標紅部分為Public info
Step2. Prover for Trace
協議參數選取：
1.AIR 實例化
2.驗證AIR和Trace的一致性（Debug模式）
2.1 校驗基礎參數
2.2 校驗assertion有效(boundary cs)
2.3 校驗Trace滿足transition cs（Debug module）
Transcript
3.Commit for trace
域參數選取：
3.1 Interpolate -> LDE -> evaluate over LDE-domain
3.2 Commitment
Tracescript
4.Evaluate CS
4.1 獲取線性組合係數
係數個數和約束的個數一致
在本例中（fib2-example），transition cs 2 個；boundary cs 3個
4.2 為t-cs和b-cs構建evaluator
4.2.1 t-cs
4.2.2 b-cs
4.3 Evaluate t/s-cs over ce_domain
4.3.1 定義evaluator table
5 Commitment to Evaluate CS
5.1 建立constraints composition polynomial
5.2 commitment to composition poly
Example:
Compose_poly = a * x^3 + b * x^2 + c * x + d = (a * x^2 + c) * x^ + (b * x^2 + d)
(a * x^2 + c), (b *x^2 +d) 分別對應兩個column
6.建立DEEP composition多項式
The general formal: f(x) = q(x)* t(x)
Need check at random z
1. f(z) = q(z) * t(z)
2. f(x),q(x),t(x) indeed equal respectively f(z), q(z), t(z)
3. calculate Deep_composition = (q(x) - q(z)) / (x - z)
4. Check LDT for q_q(x)
6.1 select z which out of domain(ood)
draw an out-of-domain point z. Depending on the type of E, the point is drawn either from the base field or from an extension field defined by E.
The purpose of sampling from the extension field here (instead of the base field) is to increase security.
6.2 evaluate trace and constraint polynomials at the OOD point z
6.2.1 trace_poly at z & z * g
6.2.2 composition poly at z
6.3 建立Deep compositon polynomial
6.3.1 產生隨機數
6.3.2 cal quotient poly
6.4 evaluate Deep over LDE
7.計算Deep 的FRI Layer num
8.確定query位置
從lde_domain中選取多個query的位置。
9.構建proof對象
9.1 生成FRI proof
9.2 query trace poly at above positions
和上述類似
9.3 query constraint poly at above positions
和上述類似
9.4 構建STARK PROOF
Step3. Verify for proof
從 transcript中讀取pub-info，用來獲取相關的數據，以執行驗證過程。
1. Ood consistency check
驗證章節5.2描述的數學關係的一致性。
2. 實例化FRI-verifier對象
3.計算Deep poly on query positions
計算方式和章節6.4相同
4.執行FRI VERIFY過程
關於我們
Sin7Y成立於2021年，由頂尖的區塊鏈開發者和密碼學工程師組成。我們既是項目孵化器也是區塊鏈技術研究團隊，探索EVM、Layer2、跨鏈、隱私計算、自主支付解決方案等最重要和最前沿的技術。
微信公眾號：Sin7Y
GitHub：Sin7Y
Twitter：@Sin7Y_Labs
Medium：Sin7Y
Mirror：Sin7Y
HackMD：Sin7Y
HackerNoon：Sin7Y
Email：contact@sin7y.org
