Exness外匯：技術幹貨 | 理解零知識證明算法之Bulletproofs：Range Proof I

發表於 2023-02-11 03:44 作者： 區塊鏈情報速遞pro

Exness外匯

前言

Bulletproofs，又一個有意思的零知識證明算法，相信讀者已經很熟悉它了。和zk-snark相比，它不需要可信設置；和zk-stark算法相比，它具有較小的proof size。根據論文，它有兩個方面的應用：1. 用於range proof；2. 用於一般算術電路的零知識證明。下面，讓我們先看一下Bulletproofs是如何高效的實現第一點。

Range proof

1. 預備知識

a_L：表示向量{a₁,a₂……a_n}

2ⁿ：表示向量{2⁰,2¹…2^n-1}

<a, b>：表示向量內積 ∑ a_i*b_i，結果是一個值

a o b：向量對應位相乘，{a₁*b₁……a_n*b_n}，結果是一個向量

2. 證明

Alice想要證明 v ⸦ [0, 2ⁿ-1]

=>則，需要證明一個relation得成立，如下所示：

{（g、h ⸦ G，V，n；v，r ⸦ Z_p）：V = g^rh^v ^ v ⸦ [0, 2ⁿ-1] }

public-x           witness-w relation-R

即，對於公开信息x，Alice有隱私信息w，使得關系R成立。

令 a_L爲金額v的在範圍[0, 2ⁿ-1]內的二進制形式，則a_L = {a₁,a₂……a_n}⸦{0,1}ⁿ，且滿足<a_L, 2ⁿ> = v。因此，證明者需要證明以下幾個等式相等：

V = g^rh^v     (1)

<a_L, 2ⁿ> = v    (2)

a_L o a_R = 0ⁿ   (3)

a_R = a_L - 1ⁿ    (4)

等式(1)確保了承諾V和金額v的綁定關系，等式(2)確保了v的範圍，等式(3)(4)確保了a_L 元素只屬於{0,1}。等式(2)/(3)/(4)總共包含了2n+1個約束，其中公式(2)1個，公式(3)(4)各n個。接下來，爲了效率，我們需要把2n+1個約束轉換成1個約束。

3. 2n+1個約束轉換成1個約束

 

=>預備：從Z_p中任意選擇一個數y，則b = 0ⁿ是等式<b, yⁿ> = 0成立的充分條件；因爲當b != 0ⁿ，等式成立的概率僅有n/p，p是有限域，遠大於n。（理解：如果b != 0ⁿ ，把等式看作求n階一次多項式的零點即可）因此，如果有<b, yⁿ> = 0，那么驗證者愿意相信b != 0ⁿ 。

利用這個理論，我們把等式(2)/(3)/(4)做以下轉換：

1. 驗證者隨機選取一個數y發送給證明者；

2. 證明者要證明：

<a_L, 2ⁿ> = v (5)

<a_L , a_R o yⁿ> = 0        (6)

<a_L - 1ⁿ- a_R, yⁿ> = 0    (7)

同理，等式(5)確保了v的範圍，等式(6)(7)確保了a_L 元素只屬於{0,1}。此時2n+1個約束轉換成3個約束，接下來，還需要做進一步的處理：

Exness外匯 1. 驗證者隨機選取一個數z發送給證明者：

2. 證明者利用z對公式(5)(6)(7)進行线性組合，得到如下公式：

z² * <a_L, 2ⁿ> + z * <a_L - 1ⁿ- a_R, yⁿ> + <a_L , a_R o yⁿ> = z² * v    (8)

至此，我們已經把2n+1個約束轉換成1個約束。下面我們對公式(8)做進一步的優化，把三個點積優化成1個點積

4. 三個點積優化成1個點積

 

=> z² * <a_L, 2ⁿ> + z *  <a_L - 1ⁿ- a_R, yⁿ> + <a_L , a_R o yⁿ> = z² * v

=> <a_L, z² * 2ⁿ> + <a_L, z * yⁿ> - <z * 1ⁿ, yⁿ> - <z * a_R, yⁿ> + <a_L , a_R o yⁿ> = z² * v

=> <a_L , a_R o yⁿ + z * yⁿ + z² * 2ⁿ> - <z * 1ⁿ , yⁿ> + <z * 1ⁿ, yⁿ o a_R> = z² * v

=> <a_L , a_R o yⁿ + z * 1ⁿ o yⁿ + z² * 2ⁿ> - <z * 1ⁿ, yⁿ + yⁿ o a_R> = z² * v

=> <a_L , (a_R + z * 1ⁿ) o yⁿ + z² * 2ⁿ> -  <z * 1ⁿ, yⁿ + yⁿ o a_R> = z² * v

=> <a_L , (a_R + z * 1ⁿ) o yⁿ + z² * 2ⁿ> -  <z * 1ⁿ, (a_R + z * 1ⁿ) o yⁿ + z² * 2ⁿ -z * 1ⁿ * yⁿ + yⁿ - z²*2ⁿ>  =  z² * v

=>  <a_L - z * 1ⁿ, (a_R + z * 1ⁿ) o yⁿ + z² * 2ⁿ> - <z * 1ⁿ , -z * 1ⁿ * yⁿ + yⁿ - z²*2ⁿ> =  z² * v

=>  <a_L - z * 1ⁿ, (a_R + z * 1ⁿ) o yⁿ + z² * 2ⁿ> = z² * v + <z * 1ⁿ , -z * 1ⁿ * yⁿ + yⁿ - z²*2ⁿ>

=>  <a_L - z * 1ⁿ, (a_R + z * 1ⁿ) o yⁿ + z² * 2ⁿ> = z² * v + <z * 1ⁿ , (-z * 1ⁿ + 1ⁿ) * yⁿ > - <z * 1ⁿ ,  z²*2ⁿ>

=>  <a_L - z * 1ⁿ, (a_R + z * 1ⁿ) o yⁿ + z² * 2ⁿ> = z² * v + (z – z²) * <1ⁿ, yⁿ> - z³ * <1ⁿ, 2ⁿ>    (9)

 

=>  令

L =  a_L - z * 1ⁿ

R =  (a_R + z * 1ⁿ) o yⁿ + z² * 2ⁿ

δ =  (z – z²) * <1ⁿ, yⁿ> - z³ * <1ⁿ, 2ⁿ>

5. 驗證：

1. 證明者把L/R/V發送給驗證者；

2. 驗證者事先算好 δ

3. 驗證者根據L算出來a_L，根據<a_L, 2ⁿ> = v算出v

4. 驗證者根據L,R,v,δ驗證等式<L, R> = z² * v +δ

因爲y，z都是驗證者提供，因此如果驗證者如果能驗證公式(9)成立，則相信等式(5)(6)(7)成立，則相信等式(2)(3)(4)成立，則相信v滿足關系v ⸦ [0, 2ⁿ-1]。

但是，可以看到上述過程，泄露了v的信息，因此需要一個零知識證明協議。

6.  一個零知識證明協議

由於L,R包含了v的相關信息，因此，我們需要添加兩個盲因子s_L、s_R來隱藏a_L，a_R。如公式(10)(11)所示：

l(X) = (a_L - z * 1ⁿ) + s_L * X )   (10)

r(X) = (a_R + z * 1ⁿ + s_R * X) o yⁿ + z² * 2ⁿ    (11)

此時，定義公式(12)

t(X) = <l(X), r(X)> = t₀ + t₁*X + t₂ * X²    (12)

可以看出系數t₀是l(x)和r(x)常數項的乘積，即滿足：

t₀ = <L, R> = z²*v + δ

因此，問題由證明：

<L, R> = z²*v + δ

轉化成了，在任意一點x，驗證者驗證多項式值l(x), r(x), t(x)滿足關系：

<l(x), r(x)> = t(x)

多項式值l(x), r(x), t(x)由證明者提供，爲了保證l(x)，r(x) well-formed，即：

l(x) = (a_L - z * 1ⁿ) + s_L * x )

r(x) = (a_R + z * 1ⁿ + s_R * x) o yⁿ + z² * 2ⁿ

需要校驗：

P = A * S^x * g^(-z) *(h`)^{z*yn+z^2*2^n}

= h^αg^aLh^aR * (h^ρg^sLh^sR)^x * g^(-z) * (h`)^{z*y^n+z^2*2^n}

= h^αg^aLh^aR *  h^ρxg^sL*xh^sR*x * g^(-z) * (h`)^{z*y^n+z^2*2^n}

= h^α+ρx * g^{aL+ sL * x – z * 1^n} * h^{aR + sR * x} * (h`)^{z*y^n+z^2*2^n}

= h^α+ρx * g^{aL+ sL * x – z * 1^n} * (h`)<sup>y^n o (aR + sR * x)</sup> * (h`)^{z*y^n+z^2*2^n}

Exness外匯 = hα+ρx * gaL+ sL * x – z * 1^n * (h`)y^n o (aR + sR * x) + z*y^n+z^2*2^n

= h^α+ρx * g^{aL+ sL * x – z * 1^n} * (h`)^{y^n o (aR + sR * x + z * 1^n) + z^2*2^n}

=? h^μg^l(h`)^r

=> 當且僅當l/r well-formed，等式成立

爲了保證t(x) well-fromed，即：

t = t₀ +t₁x + t₂x²

需要校驗：

=> g^th^τx =? V^{z^2} * g^δ*T₁^x *T₂^{x^2}

=> g^th^τx =? (h^rg^v)^{z^2} *g^δ *(g^t1)^x*(h^τ1)^x*(g^t2)^{x^2}*(h^τ2)^{x^2}

=> g^th^τx =? h^{z^2*r + τ1*x + τ2*x^2} * g^{z^2*v + δ + t1*x + t2*x^2}

=> g^th^τx =? h^{z^2*r + τ1*x + τ2*x^2} * g^{t0 + t1*x + t2*x^2}

=> t = ? t₀ + t₁*x + t₂*x² && τ_x = ? z²*r + τ₁*x + τ₂*x²

=> 當且僅當t和τ_x welle-formed，等式成立

具體的協議流程圖如下圖所示：

總結

從上述流程可以看出，一次range proof，證明者需要發送總共{ l / r / t / τ_x / μ / T₁ / T₂/ A / S}個元素給驗證者，總共2n+3個Z_p元素，4個G元素。下一篇文章將細講，Bulletproofs如何將交互復雜度降低到對數級O(log(n))

附錄

1. Bulletproofs 論文：chrome-extension://cdonnmffkdaoajfknoeeecmchibpmkmg/assets/pdf/web/viewer.html?file=https%3A%2F%2Feprint.iacr.org%2F2017%2F1066.pdf

標題：Exness外匯：技術幹貨 | 理解零知識證明算法之Bulletproofs：Range Proof I

地址：https://www.coinsdeep.com/article/10109.html

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播信息之目的，不構成任何投資建議，如有侵權行為，請第一時間聯絡我們修改或刪除，多謝。