詳解Bulletproofs零知識證明協議的工作原理

買賣虛擬貨幣
在這篇文章中,我將解釋Bulletproofs零知識證明協議的工作原理,並討論我們正在使用Bulletproofs構建的隱私資產協議和隱私智慧合約語言。背景知識零知識範圍證明是隱私交易系統(例如比特幣機密交易,鏈上的隱私資產和許多其他協議)的關鍵組成部分。範圍證明允許驗證者確保隱私值(如資產金額)是非負的。這防止使用者透過隱私使用負數偽造價值。由於每筆交易都涉及一個或多個範圍證明,因此在證明大小和驗證時間方面,它們的效率是交易效能的關鍵。承諾(Commitment)-對訊息m的承諾Com(m)隱藏了,這意味著它沒有顯示m。它也具有約束力,這意味著如果您對m作出承諾,則無法將其開啟給其他訊息m’。在Bulletproofs的上下文中,承諾是指Pedersen承諾,它具有加性同態的附加屬性,這意味著僅當a + b = c時Com(a)+ Com(b)= Com(c)。零知識證明(Zero-knowledge proof)-一個證明某個陳述是真的,而不透露該陳述的秘密。通常透過對宣告所涉及的秘密作出承諾,並與證據共享承諾。零知識範圍證明(Zero-knowledge range proof)-一個秘密值在一定範圍內(從0到2^n-1)的證明。證據通常與對秘密價值的承諾共享,以便能夠得到驗證。
內積(Inner product)-兩個向量按項相乘的總和。表示法:例如a,2 ^ n(這是n長度向量2 ^ 0、2 ^ 1,...,2 ^ {n-1})和0 ^ n(即 n長度向量0s)。內積表示為c = <a,b>,其中a和b是相同長度的向量,c是標量。

範圍證明(Range Proof)

奧列格·安德列夫(Oleg Andreev)的Bulletproofs範圍證明協議的程式化插圖

我們想證明以下陳述:0≤v <2 ^ n

我們知道,如果這是真的,則v必須是長度為n的二進位制數。例如,如果n = 4和v = 3(我們正在檢查3是否在0到2 ^ 4_1的範圍內),那麼這意味著v必須能夠分解為4的位表示形式。位長(如果實際上在範圍內):

我們希望以內積的形式來表示這一宣告,因為Bulletproof引入了非常高效的內積證明,我們將在下一節中討論這一點。

如果v_bits實際上是位表示形式,則v應該等於v_bits和向量2^n(它是n長度向量2^0,2^1,...,2^{n-1})的內積。v我們可以透過在下圖中新增檢查1來做到這一點。

另外,我們需要確保v_bits實際上僅由位組成(沒有其他討厭的數字,例如5或-1000……那是不好的!)我們可以透過在下圖中新增檢查2來做到這一點。

接下來,我們使用挑戰標量將這兩個語句組合起來,並向它們新增盲因子。這背後的數學並不困難-只是乏味-最終以c=<a,b>的形式給出了一個內部乘積語句。也就是說,我們得到一個語句,如果該語句是真的,那麼我們知道v在0到2^n的範圍內。您可以按照一步一步的數學來說明如何在我們的範圍證明註釋中建立該語句。

內積證明(Inner Product Proof)

在範圍證明部分,我提到我們的目標是以內積的形式建立一個語句,以提高效率。讓我們更詳細地討論什麼是內積,以及如何能夠有效地證明內積!

內積證明是證明c是向量a和向量b的內積,即c=<a,b>。

這可能有助於瞭解內積是什麼:

天真地說,驗證者可以透過傳送a、b和c來向驗證者證明這一點,然後驗證內積證明的偉大之處在於,它使我們可以在O(log(n))時間和空間上進行證明!

內積證明是如何達到這種效率的直覺是,在每一步中,它都將a和b向量的大小減半。因此它需要log(n)個步驟,因為在許多步驟之後,a和b的長度是1(基本情況)。

因此,如果我們從原始的a和b向量及其乘積c開始,則可以將每個向量劃分為hi和lo的一半:

然後我們得到一個隨機挑戰標量x,我們用它來組合a和b的hi和lo兩部分來建立a'和b',這也給了我們一個新的c'=<a',b'>。

在做數學運算以擴充套件c’時,請注意c’的前兩個項與c相同!因此,我們可以簡化要相對於c編寫的c’的表示式,以及可以稱為術語L和R的表示式:

在每一輪中,證明者將L和R傳送給驗證者,並使用a’,b’,c’作為a,b,c重複下一輪。注意在每一步如何將向量a和b的長度減半!

經過log(n)步驟後,我們得出一個基本情況,其中a'和b'均為長度1。然後不再需要進行壓縮,證明者可以簡單地傳送a',b',c 驗證者。

驗證者現在具有基本情況的標量a',b',c',以及每個log(n)步驟的標量L和R。然後驗證者可以從基本情況開始逆轉該過程。他們可以透過檢查c’= a’* b’來輕鬆驗證基本情況。他們可以透過使用該步驟中的c’,L,R來驗證c的計算,從而在每個更高的步驟中檢查計算是否正確完成,直到完成所有檢查為止。

聚合範圍證明(Aggregated Range Proof)

聚合範圍證明對效能很好,因為它們允許m方生成其單個語句的聚合證明(m範圍證明),這樣聚合證明比m單個範圍證明更小,驗證速度更快。建立聚合證明的協議比建立單個範圍證明稍微複雜一些,並且需要涉及各方的多方計算。在我們的實現中,我們使用一個集中的經銷商來協調m個參與方之間的通訊。

約束系統證明(Constraint System Proof)

約束系統是兩種約束的集合:

約束系統非常強大,因為它們可以表示任何可有效驗證的程式。零知識約束系統證明是對某個秘密輸入滿足約束系統中所有約束的證明,而無需透露那些秘密輸入是什麼。

例如我們可以建立一組約束(“gadget”),強制某些輸出是某些輸入的有效置換。我們稱之為shuffle gadget。在一個只有兩個輸入和兩個輸出的簡單shuffle gadget中,我們可以將可能的狀態表示為:

如果我們得到一個隨機標量x,那麼我們可以用一個方程的形式來表示這個需求:(a-x)*(B-x)=(C-x)*(D-x)。由於根置換時多項式的相等性,我們知道如果方程適用於隨機x,那麼{a,B}必須在任意順序上等於{C,D}。

當我們在約束系統中實現此2-shuffle gadget時,它看起來像這樣:

在第6行中,我們得到挑戰標量x。

在第8行和第10行中,我們做了兩個乘法約束:(A-x)*(B-x)=input_mul和(C-x)*(D-x)=output_mul。

在第12行中,我們做了一個線性約束:input_mul-output_mul=0,它約束input_mul=output_mul。

Cloak

隱私資產計劃的目標是使資產價值和資產型別保持隱藏的交易,從而允許進行多資產交易,其中外部觀察者無法推斷正在進行的交易,但可以驗證交易的正確性。Cloak是使用Bulletproofs構建的機密資產計劃。

Cloak專注於一件事:證明某些具有不同資產型別的價值已正確地從投入轉移到產出。Cloak確保每種資產型別的價值保持平衡(以使一種型別不會相互轉化),數量不會溢位組訂單(換句話說禁止負數量)並且數量和資產型別均應保密。Cloak沒有指定如何驗證傳輸或哪種分類帳表示這些傳輸:這些都留在圍繞Cloak構建的協議中進行定義。

Cloak使用“shuffle”、“merge”、“split”和“range proof”等小工具的集合構建一個約束系統,這些小工具組合在一個稱為“cloaked transaction”的小工具下。所有小工具的佈局僅由輸入和輸出的數量決定,而不受資產的實際值影響。這樣所有相同大小的事務都無法區分。例如對於區塊鏈的驗證者或檢視者來說,這就是3輸入3輸出掩蔽事務的樣子:

這就是3輸入3輸出cloaked transaction對於試圖證明輸入為$5,¥3,¥4,輸出為¥3,¥6,$3的事務有效性的驗證者來說的樣子。請注意相同型別($)的資產是如何分組、合併在一起,然後拆分和重新排列為目標金額的:

事實證明Cloak具有驚人的效率:與僅需要範圍證明的單資產交易(例如針對比特幣的隱私交易建議)相比,支援已發行資產所需的其他約束和小工具所佔比重不足20%乘數。並且由於內積證明,對證明大小的影響幾乎為零。這說明了Cloak協議中每個小工具所需的乘數:

ZkVM

ZkVM的目標是製造一種允許隱私性的智慧合約語言。它以以前的智慧合約語言工作為基礎,旨在在安全環境中執行並輸出確定性日誌的表達語言。它使用Cloak來驗證加密的資產流是否正確,並使用Bulletproofs約束系統證明來新增約束,以約束操作值和正確執行智慧合約。

總結

希望本文能幫助您瞭解Bulletproofs零知識證明協議的工作原理,以及我們根據該協議構建的內容。

免責聲明:

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

推荐阅读

;