前言
本系列的第一篇文章，以 Zk-snark 做對照，分別從概念和算法流程上，做了概括性的介紹，建議在閱讀本篇文章之前，先閱讀下第一篇文章的內容。本篇文章，讓我們由淺入深，一起踏上探索 Zk-stark 算法奧秘的旅途，
回顧
在第一篇的文章中講到，Zk-stark 算法大體可以分為兩個部分：Arithmetization 和 Low Degree Testing，本篇我們先詳細介紹算法的第一階段 Arithmetization。 Arithmetization 的整體步驟如下圖所示：
那什么是 Arithmetization ？具體過程又是什么呢？帶著這些疑問，讓我們仔細的品味文章后面的內容。
首先，什么是 Arithmetization？
Arithmetization 就是把 CI statement 轉化成正式的 Algebraic language 的過程，此步驟有兩個目的：第一，把 CI statement 以簡潔清晰的方式呈現出來；第二，把 CI statement 嵌入到代數域，為后面多項式的轉換做鋪墊，Arithmetization representation 主要由兩部分組成：第一，執行軌跡（圖中橙色部分）；第二，多項式約束（圖中灰色部分）。執行軌跡是一個表，表的每一行代表一個單步的運算；多項式約束的構造是和執行軌跡相輔相成的，即當前僅當執行軌跡是正確的，多項式約束會滿足執行軌跡的每一行計算。最后把執行軌跡和多項式約束結合組成一個確定的多項式，然后對多項式進行 LDT 驗證。至此，驗證 CI statement 的問題轉換成了驗證確定性多項式 LDT 的問題。
Arithmetization
知道了 Arithmetization 的整體流程，接下來，我們討論下具體的過程，為了便于理解，我們用一個簡單的例子，來貫穿整個 Arithmetization 的過程， 每個人都去過超市，一般超市的收據的內容如下：
現在，好萊塢人氣演員 Bob 聲稱：”the total sum we should pay at the supermarket was computed correctly”，那怎么驗證呢？其實很簡單，這時另一個氣人演員 Alice 只要對著收據，每一項累加求和就可以完成驗證，那么，這只是一個很簡單的例子，事實上，Alice 只需要 5 步，就可以完成驗證過程。試想這樣一個場景：畢竟 Bob 很有錢，在超市買了 1000000 樣東西，同樣，他又聲稱：”the total sum we should pay at the supermarket was computed correctly”，這時候，Alice 真的生氣了，這怎么驗證，按照之前的辦法，得大約要算 1000000 步，鬧呢？誰愛干誰干。Bob 心里也心疼 Alice，畢竟那么多年了，心想，有沒有什么牛掰的辦法能讓 Alice 用很少的步驟，就能確信我說的是對的呢？于是，Bob 開動了最強大腦模式。 下面，讓我們用上面簡單的例子，跟隨 Bob 去尋找這個牛掰的辦法。
Bob 心想，你不就是驗證最終的總和對不對么？那我就把總和的計算過程列出來，我保證每次的累加都對，那么我最終的結果一定也是對的。于是 Bob 在收據上新增了一列，用來保存計算總和過程中的中間值（圖中橙棕色部分標注），這就是執行軌跡（圖 1 中的橙色部分），新增的一列值需要滿足，初始化的值為 0（圖 2 中黃色部分）、最終的值和要付的總和相等（圖 2 中黃色部分）、中間的每一個值都要等于上一個值加上上一行物品的單價（圖 2 中紅線部分），這構成了多項式約束（圖 1 灰色部分，圖 2 左下角部分）。 從圖 2 可以看出：
- 多項式約束總共有 3 個，兩個是邊界約束（多項式索引 1&3），一個是循環約束（多項式索引 2）；
- 多項式的大小和執行軌跡的答案小沒有關系，即表格的長度即使擴大到 1000000 ，最終的多項式約束仍是這三個，唯一變化的是變量 x 的取值范圍而已。
在這里，借用 V 神的話來描述一下 Zk-stark：Zk-Stark 不是一個確定性的算法，它是一大類密碼��數學結構，對于不同的應用，具有不同的最優設置。可以理解為，對于不同的問題，具有不同的算術化的方案（在本例中，是加一列值，在其他案例中就不一定適用了），因此要做到具體問題具體分析，但是有一個共同目標就是，無論是什么問題，得到的執行軌跡最好是用一個 LOOP 就可以表示，這樣得到的多項式約束也就最為簡潔，多項式約束的個數和形式直接影響到了 proof 的大小和 Zk-stark 算法的性能，因此，尋找一個最優的設置對于 Zk-stark 算法顯得尤為重要。 回歸到主題，現在 Bob 已經得到了多項式約束和執行軌跡，那么如何把它們轉換成一個確定的多項式呢？請看下圖：（藍色箭頭代表主流程，紅色箭頭代表分支）
Bob 首先把關注點切到執行軌跡，可以看到執行軌跡有 2 列，一列是單項價格，一列是價格總和，我們分別對兩列的元素進行拉格朗日插值，得到兩個函數 f(x), w(x)，0≤ x ≤5，分別對兩個函數進行域擴展，得到了在更多的點上的評估，即 f(x)，w(x) ，0≤ x ≤10000（從多項式插值，到域擴展，這其實就是 Reed-Solomen 的編碼過程，它可以實現，原始數據哪怕有一處差異，得到的碼字會大不相同；主要目的用于防止證明者作惡，加入證明者作惡，會使得驗證者很容易發現），
然后，Bob 把 f(x)，w(x) 和多項式約束等式結合，得到一組確切的多項式約束(圖中紅色圈 2 所示)，以循環約束多項式為例：
1 ≤ x ≤ 5 w(x) – f(x -1) – w(x -1) = 0 (1)
令 Q(x) = w(x) – f(x-1) – w(x-1)，則有 Q(1) = 0、Q(2) = 0、Q(3) = 0、Q(4) = 0、Q(5) = 0，
根據已知事實，度為 d 的多項式 H(x) 在 x=n 處為 0，則存在一個度為 d-1 的多項式 H(x), 滿足 d (H(x)) = d(H(x)) – 1 && H(x) = H`(x) * (x – n)
因此對于 Q(x)，度為 5，存在一個多項式 Ψ(x)，度為 0，即常量，滿足 Q(x) = Ψ(x) * (x – 1)(x – 2)(x – 3)(x – 4)(x – 5)，令目標多項式 T(x) = (x – 1)(x – 2)(x – 3)(x – 4)(x – 5)，度為 5，則有：
Q(x) = Ψ(x) * T(x) (2)
驗證者 Alice 從 0≤x≤10000 隨機選擇一點 a，發送給證明者 Bob，要求 Bob 返回相應的值，以公式 (2) 為例，Bob 需要返回 w(a)、w(a-1)、f(a-1)、Ψ(a)，然后 Alice 判斷等式是否成立，即：
w(a) – f(a – 1) – w(a – 1) = Ψ(a) * T(a) (3)
如果等式成立，則 Alice 大概率相信執行軌跡是正確的，那么原始計算成立，假如驗證者Bob作惡，講表格中的 4.98 改成 5.98 把，那么 Q(1) = w(1) – w(0) – f(0) = 5.98 – 0 – 4.98 = 1，不等于 0，在這種情況下，觀察公式(2)，等式右邊為 Q(x)，度為5，x = 1不是零點；等式右側 Ψ(x) * T(x) ，令G(x) = Ψ(x) * T(x)，度為 5，因為 T(x)在 x = 1 處是零點，所以 G(x) 在 x=1 處也是 0 點，因此，等式兩邊實際上是度相等的不同多項式，其交點最多為 5 個，因此在 0≤ x ≤10000 范圍內，只有 5 個值相等，9995 值是不等的，因此隨機的從 0≤ x ≤10000 中選擇一個值，驗證不通過的概率是 99.95%，如果域擴展的范圍更大，則驗證不通過的概率將會更接近于 1。按照同樣的邏輯，分別處理邊界約束多項式，得到的結果如圖所示（圖中紅色圈 3 所示），
下面，我們講討論如何增加零知識屬性。
對于證明者 Bob 來講，執行軌跡是不希望被驗證者 Alice 看到的，因為它會包含一些重要的資訊，因此，限定驗證者 Alice 只能從 6 ≤ x ≤ 10000 范圍內隨機選擇一個值，進行驗證，當然這種限定，雙方都是同意的。
存在這樣一類問題，當驗證者 Alice 收到證明者 Bob 反饋的值時，如何保證這些值是合法的，確實是通過多項式的形式計算，并且這些多項式是小于某個度的，而不是證明者Bob僅僅為了驗證通過，而生成的隨機值？比如如何確保 w(a)、w(a-1)、f(a-1)、Ψ(a) 是多項式 w(x)、f(x)、Ψ(x) 分別在 x = a && x = a – 1 上的取值呢，且多項式 w(x)、f(x)、Ψ(x) 的度小于某個固定值的呢？這些問題將在下一篇文章中給出答案，在此之前，不如先討論一下，為何多項式的度小于某個固定值就能證明原始執行軌跡式正確的呢？
從以上的例子中，可以看出，當且僅當執行軌跡是正確的時候，Q(x) 才會在 x 取值為 1、2、3、4、5 時，等于 0，那么 Q(x) 才可以被目標多項式 T(x) 整除，即：Ψ(x) = Q(x) / T(x) ，d(Ψ(x)) = d(Q(x)) – 5。
從圖 3 可以看出，需要驗證的多項式的個數時 5 個(紅色圈 4 所示)，如果對每一個多項式都進行 LDT，那么消耗是很巨大的，因此，可以通過將這些多項式進行線性組合(紅色圈 5 所示)，當且僅當每個多項式都滿足小于某個度時，其線性組合后的多項式也是小于某個度的，這個條件時充分的，具體的細節見后續的系列章節。
