撰文:ZKSwap 小白

前言

本系列的第二篇文章,以超市收據爲例,描述了 Arithmetization 的具體過程。本文將以另外一個例子爲基礎,在回顧 Arithmetization 過程的同時,將內容引申到多項式的 LDT 過程。

新的實例

Alice Claim:“我有 1000000 個數,他們都在 [0,9] 範圍內”。爲了方便驗證者 Bob 驗證,Alice 首先要對 Claim 進行 Arithmetization 轉換。過程如下圖 1 所示 (圖中:黑色箭頭代表主流程,紅色箭頭代表附加說明信息,黃色圈對應下面詳細說明的索引)。

ZKSwap 團隊深入解讀零知識證明算法之 Zk-STARK (三):Low Degree Testing

下面具體說明一下對應流程:

1. 首先生成執行軌跡 (EXCUTE TRACE),事實上,它是一張表,總共有 1000000 行(實際上,爲了達到零知識的目的,還需要在執行軌跡後面增加一些隨機值,具體數量是由證明者和驗證者統一協調決定的,作爲一個擴展,不具體講述);

2. 生成多項式約束 (Polynomial Constrains),多項式約束滿足執行軌跡的每一行 (個人理解:步驟 1,2 沒有一定的先後依賴關係,只是習慣上先生成執行軌跡,再生成約束多項式);

3. 對執行軌跡進行插值,得到一個度小於 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 個點不同,這很重要。

4. 將插值後的多項式 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;

5. 至此,問題就轉化成了,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 所示:

ZKSwap 團隊深入解讀零知識證明算法之 Zk-STARK (三):Low Degree Testing

圖中:紫色的點爲隨機生成的點 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 次的。一般流程如下:

1. 驗證者 Bob 隨機選取三個值 a,b,c,發送給證明者 Alice;

2. 證明者 Alice 返回 f(a),f(b),f(c);

3. 驗證者 Bob 插值出度小於 3 的多項式 g(x),然後再隨機選取一個點 d,發送給證明者;

4. 證明者 Alice 返回 f(d);

5. 驗證者 Bob 比對 f(d) 和 g(d) 的值,如果相等,則證明成立。

6. 迴歸到一般情況,其過程可以用下圖 3 表示:

ZKSwap 團隊深入解讀零知識證明算法之 Zk-STARK (三):Low Degree Testing

可以看出,如果 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 所示:

ZKSwap 團隊深入解讀零知識證明算法之 Zk-STARK (三):Low Degree Testing

驗證者把所有的點都計算好(沒錯,總共 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 爲例:

ZKSwap 團隊深入解讀零知識證明算法之 Zk-STARK (三):Low Degree Testing

圖中,紅色爲 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 的形式:

ZKSwap 團隊深入解讀零知識證明算法之 Zk-STARK (三):Low Degree Testing

可以看出,列座標變成了 10^6 個元素,對角線變成了平行的線條,總共有 1000 個。還記得上面費馬小定理結論的特殊現象嗎?這就是對角線這種分佈的原因,讀者試着去理解 (可能讀者會覺得,對角線應該是鋸齒形,不是這種平行的形式,也許你是對的,但是這並不影響驗證流程)。此時證明者的複雜度已經從 10^18 減少到了 10^15 次方,證明和驗證過程和步驟 3 描述的仍然一致。

1. 還能不能繼續優化呢?答案是肯定的。回想起前面所述的驗證過程,對於每一行 / 列,驗證者都要獲取 1000 個點進行插值得出一個度小於 1000 的多項式,仔細觀察圖 6,對於每一行,原始數據裏不就是有 1000 個數麼?那我們乾脆選這些點插值出一個度小於 1000 的多項式,然後只需要隨機讓證明者再計算任何一列,並且證明沿着列上的點都在度小於 1000 的多項式上,並且列上的點也在對應的利用原始數據插值出的行多項式上。此時,證明者複雜度從 10^15 減少到了 10^9 次方。

2. 總結:個人理解,從步驟 1 到步驟 5,其實是 PCP 到 IOP 的選擇過程。 a. PCP 要求證明者生成全部的證據,然後驗證者多次隨機選取其中的某一部分進行驗證,但是這樣,證明者的複雜度仍然很高; b. IOP 要求證明者不用生成全部的證據,根據多次的交互,每次生成只需生成部分證據,使得證明的複雜度和 D 呈近似線性關係;

3. 證明者複雜度已經降低到了與 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 所示:

ZKSwap 團隊深入解讀零知識證明算法之 Zk-STARK (三):Low Degree Testing

從圖中可知:

  • 證明則複雜度仍爲 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

至於 LDT 的詳細過程,將留給本系列的最後一篇,敬請關注。

來源鏈接:zks.org