理解零知識證明演算法之Zk-stark——Arithmetization

買賣虛擬貨幣
前言本系列的第一篇文章(技術指南 | 理解零知識證明演算法之Zk-stark),以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所示),當且僅當每個多項式都滿足小於某個度時,其線性組合後的多項式也是小於某個度的,這個條件時充分的,具體的細節見後續的系列章節。

歡迎批評指正,謝謝!!

附錄

1. 官方介紹文件:https://medium.com/starkware/arithmetization-i-15c046390862
2. 官方介紹文件:https://medium.com/starkware/arithmetization-ii-403c3b3f4355

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;