以超市收据为例，如何进行 stark 验证
其實要做的就是給定程式 A，輸入 x，輸出 y 和時間限制 T，能生成一個證明字串 Π 來證明 “A (x) 在 T 個計算步驟內輸出 y”，y=1 就是有效證明。
首先驗證不可能重新計算一次，驗證只需要抽查一部分執行軌跡，要使得抽查一部分執行軌跡就有效，就得利用纠错碼功能。
還有要保障執行軌跡的資料真實有效，未被改動，這時就得利用多項式承諾，驗證需要用到多項式承諾，快速驗證就得用低度測試，快速冪算法，费马定律等。
有了以上就可以保障能有效的驗證了，還有要實現透明性和非交互式驗證，這時就得利用 Hash 函數。
總結流程#
- 把初始計算的執行軌跡（超市收據）弄下來 (encode (A,x,y,T)), 對執行軌跡進行編碼，形成 T-step 的執行軌跡，通過多項式進行編碼得到𝚽。把執行軌跡進行擴充，例如擴充 10 倍，選擇一個更大的域，本身的執行軌跡的資料只是該域的子群（纠错碼，執行軌跡視為對某個域上的多項式的賦值，並在更大的域上賦值該多項式來擴展執行軌跡）。
- 對程式 A 進行編碼，通過 AIR，多項式中間描述對給定程式進行約束。
- 把上面的多項式合併成一個多項式，然後去做準備做 FRI 多項式承諾，多項式承諾保障了資料不能被修改，或者說改了基本就會被查出來。（多項式承諾的大小，生成承諾的時間的複雜度為：log (n) 對比的是 AIR 合併後的多項式）
- 驗證者發送隨機性𝛔₀，這使得證明者和驗證者都可以將所有多項式約束 “捆綁” 到一個統一的對 A 的多項式約束。
根據證明的資料進行哈希，根據哈希生成一些隨機數證明者根據執行軌跡與對 A 約束合起來的多項式 𝚵 。- 證明者將𝚵發送給驗證者。驗證者通過本地一致性檢查確保𝚽和𝚵適當相關。
- 去做多項式承諾。一個低度測試需要計算 log (𝚵的階數 n) 次多項式拆分，承諾的大小的複雜度也為 log (n)，承諾包括了𝚵 merkle，拆分後的𝚵 merkle，分支路徑（分支路徑的選擇，根據此前證明中生成的資料的哈希隨機選取每個樣本的下標或 r 值），最底層葉子 merkle。
- 根據哈希隨機抽查擴充後執行軌跡（長證明）的 n 個點（低度測試，一個點檢查到錯誤的概率為 90%），證明通過非交互式和多項式承諾結合去驗證每個點是否正確 (低度測試)。得到每個點的多項式多項式承諾，再結合狀態根去生成證明。