前言
本系列的第二篇文章，以超市收據為例，描述了 Arithmetization 的具體過程。本文將以另外一個例子為基礎，在回顧 Arithmetization 過程的同時，將內容引申到多項式的 LDT 過程。
新的實例
Alice Claim：“我有 1000000 個數，他們都在 [0,9] 范圍內”。為了方便驗證者 Bob 驗證，Alice 首先要對 Claim 進行 Arithmetization 轉換。過程如下圖 1 所示(圖中：黑色箭頭代表主流程，紅色箭頭代表附加說明資訊，黃色圈對應下面詳細說明的索引)。
下面具體說明一下對應流程：
- 首先生成執行軌跡(EXCUTE TRACE)，事實上，它是一張表，總共有 1000000 行（實際上，為了達到零知識的目的，還需要在執行軌跡后面增加一些隨機值，具體數量是由證明者和驗證者統一協調決定的，作為一個擴展，不具體講述）；
- 生成多項式約束(Polynomial Constrains)，多項式約束滿足執行軌跡的每一行(個人理解：步驟 1，2 沒有一定的先后依賴關系，只是習慣上先生成執行軌跡，再生成約束多項式)；
- 對執行軌跡進行插值，得到一個度小于 1000000 的多項式 P(x)、x 取值[1,1000,000]，并計算更多點上的值，x 取值范圍擴大到11000000000；假如，證明者有一個值不在[0,9] 范圍內(圖中紅線 1/2 所示)，假如就是第 1000000個點，它實際的值是 13，大于 9，其插值后的曲線 G(x) 如圖所示，圖中 P(x) 為有效曲線，G(x) 為無效曲線，可以看出，兩條曲線在變量 x 取值 [1,1000000000] 范圍內，最多有 1000000個交點，即有1000000000 – 1000000 個點不同，這很重要，
- 將插值后的多項式 P(x) 和多項式約束進行組合變換，最終得到的形式為：
Q(P(x)) = Ψ(x) * T(x)，其中 T(x) = (x – 1)(x – 2)……(x – 1000000)，x 取值[1,1000000000]
其中，d(Q(P(x))) = 10000000、d(Ψ(x)) = 10000000 – 1000,000、d(T(x)) = 1000000；
- 至此，問題就轉化成了，Alice 宣稱“多項式等式在變量x取值[1,1000000000]范圍內成立”的問題。那么驗證者 Bob 該如何驗證呢？具體過程如下（圖中紅線 3/4 所示）： a. 證明者 Alice 在本地計算多項式P(x)、Ψ(x)在所有點上的取值，對！從1至1000000000，并形成一個默克爾樹； b. 驗證者 Bob 隨機的從[1,1000,000000]內選取一個值 ρ，并發送給證明者Alice，要求其返回對應的資訊（事實上為了達到零知識的目的，只允許從[1000,000,1000,000,000]上隨機選擇一點）； c. 證明者 Alice 返回 P(ρ)、Ψ(ρ)、root、AuthorizedPath(P(ρ)、Ψ(ρ))給驗證者Bob； d. 驗證者Bob首先根據默克爾樹驗證路徑驗證值 P(ρ)、Ψ(ρ)的有效性，然后等式Q(P(ρ)) = Ψ(ρ) * T(ρ)，如果成立，則驗證通過；
完整性分析：如果驗證者 Alice 是誠實的，那么等式 Q(P(x))一定會被目標多項式 T(x)整除，因此必定存在一個 d(Ψ(x)) = d(Q(P(x))) – d(T(x)) 的多項式 Ψ(x)，滿足Q(P(x)) = Ψ(x) * T(x)，因此對于任意的 x，取值在[1,1000,000,000]之間，等式都會成立；
可靠性分析：如果驗證者 Alice 是不誠實的，即類似于步驟 3 里的假設，在x = 1000,000上，P(x)的取值為 13，那么Q(P(1000,000)) != 0，但是等式右邊，T(1000,000) = 0，因此Q(P(x)) != Ψ(x) * T(x)，即等式兩邊是不相等的多項式，其交點最多有 10,000,000 個，因此通過一次隨機選取，其驗證通過的概率僅為10,000,000/1000,000,000 = 1/100 = 0.01，經過k次驗證，其驗證通過的概率僅是 1- 10(^-2k)；
- 上述的驗證過程為交互式的，如果是非交互式的，可以利 Fiat-Shamir heuristic 進行變換，以默克爾樹的根作為隨機源，生成要查詢的隨機點；
LDT
我們忽略了一種攻擊方式，即針對每一個數 x，證明者都隨機生成 p，然后根據 Ψ(x) = Q(p) / T(x)，這些點不在任何一個度小于 1000000 的多項式上，但是可以通過驗證者驗證，如下圖 2 所示：
圖中：紫色的點為隨機生成的點 p，這些點大概率不在一個度小于 1000,000 的多項式上(事實上，可以不考慮前 1000,000 個點，因為驗證者只會從[1000,000，1000,000,000]范圍內取值)，因為即使選擇 1000,000 個點插值出一個度小于 1000,000 的多項式，也不能保證其他的點在這個多項式上，因為其他的點是隨機生成的。因此，需要有一種方式，保證證明者 P(x)的度是小于 1000,000， Ψ(x)的度小于10,000,000 – 1000,000。這就是 LDT 的目標，那 LDT 具體的過程是怎么樣的呢？請繼續往下看。
舉個栗子，如果 Alice 想證明多項式 f(x) 的度是小于 3 的，即有可能是 2 次的或者是1次的，一般流程如下：
- 驗證者 Bob 隨機選取三個值 a,b,c，發送給證明者 Alice；
- 證明者 Alice 返回 f(a),f(b),f(c)；
- 驗證者 Bob 插值出度小于 3 的多項式 g(x)，然后再隨機選取一個點 d，發送給證明者；
- 證明者 Alice 返回f(d)；
- 驗證者 Bob 比對 f(d)和g(d)的值，如果相等，則證明成立。
回歸到一般情況，其過程可以用下圖 3 表示：
可以看出，如果 D 很大，Alice 和 Bob 交互的次數則為 D+k 次，復雜度很高；有沒有一種辦法，使得兩者之間交互的次數小于 D 的情況下，使得驗證者相信多項式的度是小于 D 的，直接返回小于 D 個點肯定是不行的，因為那不能唯一確定一個度小于 D 的多項式，因此需要證明者需要額外發送一些輔助資訊。下面我們以 P(x)為例，詳細闡述這個過程(事實上，應該是證明 P(x) 和 Ψ(x) 的線性組合小于 10,000,000 – 1000,000，本文重點是 LDT，因此只以 P(x) 為例，這并不影響對 LDT 的理解)。
假如 P(x) = x + x^999 + x^1001 + x^999999 = x + x^999 + x * x^1000 + x^999*(x^1000)^999;
此時，我們找到一個二維多項式 G(x, y)，取值范圍分別是[0, 999999999]、[01000, 9999999991000]，滿足： G(x, y) = x + x^999 +x * y + x^999y^999 可以發現，當y = x^1000時，滿足： G(x, y) = G(x, x^1000) = x + x^999 + x * x^1000 + x999(x^1000)^999 = P(x) 如果我們能證明 G(x, y) 相對的 x,y 的最高度都是小于 1000，因為P(x) = G(x, x^1000)上，因此可以相信 P(x) 的度小于 1000000；如圖 4 所示：
驗證者把所有的點都計算好（沒錯，總共 10^18 個點），形成一顆默克爾樹，驗證者隨機選擇一行和一列，如圖中紅線 1/2 所示，對于每一列，它是由關于y的度小于 1000 的多項式生成，對于每一行，它是由關于x的度小于 1000 的多項式生成，驗證者從行/列中隨機選擇 1010 個點，用來驗證對應行/列上的點是否在度小于 1000 的多項式上，需要注意的是，因為 P(x)的點都在上圖的對角線上，因此我們要確保每一行/列對應的對角線上的點也在對應的度小于 1000 的多項式上，即 1010 個里面一定要包含對角線的點，
可靠性分析：如果原始多項式的度實際上是小于 10^6 +10999，即 P(x) = x + x^999 + x^1001 + x^1010999 ，那么對應的 G(x, y) 為 G(x, y) = x + x^999 +x * y + x^999*y^1010 ，即，對于每一個 x，G(x, y) 是關于 y 的一元多項式函數，且度 d < 1010，因此下圖中的每一列所有點都是在度 d < 1010 的多項式上，而不在 d < 1000的多項式式上。所以如果證明者任然宣稱多項式 P(x) 的度 d < 1000,000 ，則會驗證失敗，其他場景是同樣的道理
那有沒有可能惡意證明者仍以 G(x, y) = x + x^999 +x * y + x^999*y^999 的形式去生成證據呢？這樣會驗證通過嗎？
我們知道，我們在驗證時著重強調了對角線上的那一點一定要在多項式上，我們知道，此時對角線對應的多項式形式是：
P(x) = x + x^999 + x1001 + x^999999 ，而實際的 P(x)，我們在這里標記為 P`(x) ，其形式是：
P`(x) = x + x^999 + x^1001 + x^1010999
因此，如果驗證者恰好選擇的點是兩個多項式的交點，則會驗證通過，事實上，兩個多項式最多有 1000,000 左右個交點，但是由于隨機選取的點不是證明者自己選取，是由默克爾樹的根為種子隨機生成，因此證明者沒有機會作惡，去可以選取那些能通過驗證的點，
由于總共由 10^9 個點，因此隨機選取一個點，能驗證成功的概率為 10^6 / 10^9 = 10^(-3)，如果選擇 k 行，則成功的概率僅為 10^(-3k)，
以上可以看出，驗證者和證明者只需要交互 1010 * 2 * k 個點，就可以完成驗證，假如k = 10，則 1010 * 2 * 10 = 20100 << 10^6。
- 雖然上述實現了在交互次數小于 D 的情況下，完整 LDT 驗證，但是證明者的復雜度過于龐大，至少 10^18 的復雜度遠遠大于原始的計算，因此需要一些優化方案，降低復雜度，話不多說，直接引入有限域，畢竟在實際項目中，我們可不希望數值本身過于龐大。直接引用費馬小定理的結論：在有限域p內，如果滿足(p – 1) 能被 k 整除，則映射 x => x^k的像只有(p -1) / k + 1個，下圖 5 以 p = 17，映射 x=> x^2 為例：
圖中，紅色為 x^2 在有限域 p 內的象，總共由(p – 1) /2 + 1 = 9 個，同時我們可以發現，9^2 和 8^2 的像一致，10^2 和 7^2 的像一致，以此類推，16^2 和 1^2 的像一致，記住這個現象，對下一張圖的理解有幫助。
因此，在本例中，我們選擇一個素數 p = 1000,005,001，其滿足：
- 為素數
- p – 1 能被 1000 整除
- p 要大于 10^9
因此，在有限域 p 內，x => x^1000 的像在 p 內有(p -1) / 1000 = 1000005個，因此圖 4 可以變成圖 6 的形式：
可以看出，列坐標變成了 10^6 個元素，對角線變成了平行的線條，總共有 1000 個，還記得上面費馬小定理結論的特殊現象嗎？這就是對角線這種分布的原因，讀者試著去理解(可能讀者會覺得，對角線應該是鋸齒形，不是這種平行的形式，也許你是對的，但是這并不影響驗證流程)。此時證明者的復雜度已經從 10^18 減少到了 10^15 次方，證明和驗證過程和步驟 3 描述的仍然一致。
- 還能不能繼續優化呢？答案是肯定的，回想起前面所述的驗證過程，對于每一行/列，驗證者都要獲取 1000 個點進行插值得出一個度小于 1000 的多項式，仔細觀察圖 6，對于每一行，原始數據里不就是有 1000 個數么？那我們干脆選這些點插值出一個度小于1000 的多項式，然后只需要隨機讓證明者再計算任何一列，并且證明沿著列上的點都在度小于 1000 的多項式上，并且列上的點也在對應的利用原始數據插值出的行多項式上，此時，證明者復雜度從 10^15 減少到了 10^9 次方。
- 總結：個人理解，從步驟 1 到步驟 5，其實是 PCP 到 IOP 的選擇過程。 a. PCP 要求證明者生成全部的證據，然后驗證者多次隨機選取其中的某一部分進行驗證，但是這樣，證明者的復雜度仍然很高； b. IOP 要求證明者不用生成全部的證據，根據多次的交互，每次生成只需生成部分證據，使得證明的復雜度和 D 呈近似線性關系；
- 證明者復雜度已經降低到了與 D 呈擬線性關系，驗證者的復雜度雖然是亞線性，交互次數已經低于 D，但是能不能優化到更低呢？基于證明復雜度的最優設置，我們繼續探索驗證復雜度的優化之路，回顧 P(x) = x + x^999 + x^1001 + x^999999 = x + x*(x^2)^499 + x*(x^2)^500 + x*(x^2)499999，令G(x, y) = x + xy^499 + xy^500 + xy^499999，則當 y = x^2時，有 G(x, y) = G(x, x^2) = x + x*(x^2)^499 + x*(x^2)^500 + x*(x^2)*499999 = P(x)。
最終的圖應如下圖 7 所示：
從圖中可知：
- 證明則復雜度仍為 10^9 次方；
- 每一行上的點都在度 d < 2 的多項式上，因為當 y 取固定值時，G(x, y)就是關于 x 的一次多項式；
- 每一列上的點都在度 d < D/2 的多項式上，證明者需要證明這個多項式是小于 D/2 的，假定這個多項式為 P1(x)，這個時候，并非驗證者選取大于 D/2 個點去驗證，因為驗證復雜度仍然不夠低，而是對這一列再一次用到類似于 P(x) 的處理過程，如圖7中下面的圖所示，以此循環，直到可以直接判斷列上的多項式的度為止，類似于行，
總結
至此，本篇文章就結束了，總結下來，本文主要闡述了以下幾個內容：
- 如何轉換問題形式 — Arithmetization
- 為何需要 LDT — 為了驗證簡潔
- LDT 的大概過程 — 二分法驗證，類似于 FFT
- 降低 LDT 的復雜度 — 有限域 +IOP
