Bulletproofs
Bulletproofs is one of the zero knowledege proving system.
任意の楕円曲線に対してOK. (not in the case of snarks)
Decaf: Eliminating cofactors through point compression
proof size is descrete log of the circuit complexity.
1/3 proof size comparing to the previous work.
range proofに対して使われているが、任意の算術回路に対しても使える。
Specifications
No need trusted setup
Proving is scalable
Verifying is not scalable
Assumption is based on EC-DLP
constraint system is the r1cs
Alice can prove that the commitment $ C is a dot product $ t=v_1 \cdot v_2 of a scalar value $ t without revealing any values$ t, v_1, v_2.
コミットメントの２つの性質
Hiding - コミットメントはコミットされた値を明らかにしない
Binfing - コミットメントにコミットを明らかにするときそのコミットを違う値にすることはできない
Pedersen commitment
$ C = rH + aG
C: commitment
a: the commited value
r: the randomness which provides hiding
G: publically agreed generator of the elliptic curve
H: another curve point, for which nobady knows the discrete logarithm q (H = qG)
addictively homomorphism
$ C(r_1, a_1) + C(r_2, a_2) = C(r_1+r_2, a_1+a_2)
Vector Pedersen Commitment
$ C = rH + \vec{v}_nG
ベクトルの要素がどれだけ大きくてもコミットメントはcurve上の１つの点。
It can be extended this further to create commitments to 2 or even multiple vectors.
$ C = rH + \vec{v}_nG + \vec{w}_nH
このコミットメントもBulletProofsも完全拘束ではない。（現実的な計算能力ではコミット値の書き換えはできない）
一方でrに乱択を使っているのでコミットメントは完全秘匿。
A zero knowledge argument of knowledege of a set of vectors
argument of knowldge: 現実的な計算量的にsoundnessを破ることが厳しい。
proof of knowledge: 完全soundness
証明者はN次元のランダムベクトルのコミットメント$ C_0を検証者に提示
検証者は証明者にランダムスカラー値eを提示
証明者は、ランダムスカラー値eとランダムベクトル、隠したいベクトルを用いて、検証者に以下のN次元ベクトル$ \vec{z}とスカラー値sを提示。
$ \vec{z} = \Sigma^m_{i=0}{e^i\vec{x}_i}
$ s = \Sigma^m_{i=0}e^ir_i
https://gyazo.com/7e846432705177f57ccb11d32c212a3a
検証者は以下を検証
$ \Sigma^m_{i=0}e^iC_i =? sH + \vec{z}G
https://gyazo.com/349e1b08a2d8161e890afc88c0d02139
https://gyazo.com/5ebd3fcdbc4ce268fa5ca00463b8da2e
eの累乗を使う理由は、ランダムスカラーeの１つでm+1個のランダム値を得るため。
xベクトルを係数にした多項式$ P(e) = x_0 + x_1e + x_2e^2 + .... + x_me^mを考えると、$ e^0~e^mでm次元のベクトルを固定することができることが分かる。
Completeness
$ sH + \vec{z}G = \Sigma^m_{i=0}e^i(r_iH+\vec{x_i}G) = \Sigma^m_{i=0}e^iC_i
インデックスiのvector pedersen commitmentの形と確かに一致している。
Zero knowledge
証明者と検証者間のやり取りがオープンで、検証者の実行環境が定義通りのSimulatorである場合、vector commitmentの開けられる証明者からの証明に対して検証者はSingle bit (0 or 1, 証明が正しいかどうか）しか情報を得られない。
Schnorr's identity protocol
シュノア署名とほぼ同じだがinteractiveにすることでゼロ知識証明に適用。
証明者が鍵ペア(x, P=xG)を持っていると想定。
R=kGとなるようなkを証明者が知っている楕円曲線上のランダムな点Rを検証者に送信。
検証者はランダムスカラーeを証明者に送る。
証明者はs = k + ex を検証者に送る。
検証者は$ sG =? R + ePが成り立つか検証。
つまり、transcriptは$ (R, e, s)
（redjubjubのre-randomizationと同じ。alpha(=k)をSNARK内でゼロ知識証明していた。）
上記のプロトコルにおいてtranscriptを$ (C_0, e, (\vec{z}, s))にすると、検証式は
$ C_0 = (sH + \vec{z}G)-(\Sigma^m_{i=1}e^iC_i)
これは上述の検証式と確かに一致し、Simulatorとhonest Proversからのtranscriptは区別つかない。
Soundness
An inner product proof
inner productのzをゼロ知識証明
https://gyazo.com/784c14a0332d184e9a9f1ff0e9feb2ff
Schnorr's identity protocolもproof of knowlege of a set of vectorsもSigma protocolの一例。
一般的に、
P -> V: commitment
V -> P: challenge
P -> V: response (proof)
Schnorr's identity protocolでは、証明者があらかじめhidingするためのコミットメントを送っておいて、検証者が検証できるようにランダム値を送り、検証者がkを知り得ないことを利用してxを隠す。
The commitment step for the inner product proof
まず、証明者は検証者に内積を計算したいベクトルのpedersen commitmentを2つ送る。（内積なのでinput2つ）。ここの部分は一番最初の例だと、$ C_0を送っていた部分で、schnorr's identity protocolだと秘密鍵xではなく公開鍵Pを送っていた部分。
それぞれのベクトルを$ \vec{d_x}, \vec{d_y}とすると、
$ A_d = r_dH + \vec{d_x}G
$ B_d = s_dH + \vec{d_y}G
schnorr responseの例と考えると、ex + kであったので、内積の場合だと、$ e\vec{x}+\vec{d_x}, e\vec{y}+\vec{d_y}がproofになる。
しかし、これで十分ではなく「内積であること」も証明しなければならない。
内積は$ (e\vec{x} + \vec{d_x}) \cdot (e\vec{y} + \vec{d_y})で$ eの二次式になる。最初のコミットメントの時点ではまだchallengeの$ eは受け取っていないのでこの3つの係数をコミットメントとして提示しておく。
$ e^2の係数 xyは$ C_zとしてすでにコミットメントしてあるので（schnorrにおける公開鍵Pに相当）残りの２つのコミットメントを加える。
$ C_1 = t_1H + (\vec{x}\cdot\vec{d_y}+\vec{y}\cdot\vec{d_x})G
$ C_0 = t_0H + (\vec{d_x}\cdot\vec{d_y})G
まとめると証明者は2つのランダムスカラー$ r_d, s_d, t_1, t_0と2つのランダムベクトル$ \vec{d_x},\vec{d_y}を使って4つのpedersen commitment$ A_d, B_d, C_1, C_0を検証者に送信。
The response step
challenge stepは普通に検証者が証明者にランダムスカラーを送信。
response stepで検証者はまず受け取った証明から以下の5つのパラメタを計算。
https://gyazo.com/9c3ed1c9afcab8406c9c2ea2ea4a529b
内積ベクトルのコミットメントが一致するか検証
https://gyazo.com/a51c6b0c5436b37863afc03c9d5ab635
(ep+R =? sG)
$ t_zはinner productが正しいかの検証に利用
https://gyazo.com/486fe58c2edc156a5c7d76f5ac959e59
$ \vec{f_x}\cdot\vec{f_y}で計算する内積が正しいかチェックしている。右辺のe多項式の係数は証明一部のコミットメントを利用。
A more compact inner product proof
$ A = a_1G_1 + ... + a_{10}G_{10}というコミットメントを考えた時に、10個のスカラー値を効率的に明らかにすることを考える。
aの10次元のベクトルを2次元の5つのベクトルで表現し、Gも同様に考える。
https://gyazo.com/d16e75f242b04af6b5e1742c16d09eeb
上のような行列を考え、主対角線が実際のコミットメントになっている。このマトリクスにおける全ての対角線（2*5 - 1個）を証明者は検証者に送信する。
例えば、以下の式でk=-4を代入すると左下の$ a_1G_5だけが得られる。
https://gyazo.com/9e5fad9008df84215b74c901507c5245
続いて、verifierからchallengeのランダム値$ xを受け取った後のステップとして、次の2次元ベクトル$ a', G'を用いて新しいコミットメント$ A'を生成する。
https://gyazo.com/940f4ece4c9604ad34a94abe198ab1d0
https://gyazo.com/d2ab511c2be486fadf9b49de03e65f83
Bulletproofs
An even more compact inner pruduct proof
ベースの考え方としては、証明者サイドで$ a, b, xから１つのスカラー値$ a'が生成されるような関数$ f(a, b, x)と検証サイドで必要なxとaに
まず2つのスカラーa,bのコミットメントを考える。$ C = aG_1 + bG_2
$ a' = ax + bx^{-1}, G' = x^{-1}G_1 + xG_2を証明サイドが計算し、検証側が、
$ C' = a'G' = aG_1+bG_2+x^2aG_2+x^{-2}bG_1 = C + x^2L + x^{-2}R
の検証を考える。これだとa, bの代わりに$ a', L, Rを使ってコミットメントを検証する必要があり不可能。
次にスカラーa,b の代わりにベクトルを考える。１次元ベクトルを半分にカットし、二次元ベクトルへfold、検証者が送信するxを用いて、G'を以下のように計算できる。
https://gyazo.com/f453599baaf7f438eaba1c750dc4be7e
https://gyazo.com/663f4d0828e9482b006917e10e8c8438
a'G'も以下のように計算することができ、結局、元のコミットメントとL,Rを用いて表せる。
https://gyazo.com/8dcc271cf92069131d5c2855dad26e6c
https://gyazo.com/1ad23b4d1a6b96232bd186edf293723f
よって、
証明者がLとRを計算し証明者に送信。
検証者が乱数としてxを送信。
両者がG'を計算し、最終的なC'=a'G'を生成
上記に２つのベクトルC=aG + bHも同様に適用可能。
https://gyazo.com/2092a427ecda6b4e329324030ec9175b
inner product
証明者が$ C = zG + \vec{a}\vec{G} + \vec{b}\vec{H}のコミットメントを提示し、検証者が$ z = \vec{a} \cdot \vec{b}であることを検証。
上述と同様にコミットメントを生成すると以下のようになるが、a'とb'のベクトル内積はzではなくなってしまっている。
https://gyazo.com/236b402852bde1af227b610fd41d5db3
In the case of n=4
https://gyazo.com/e4751991dc6ab46dd3d8628525c00f7d
https://www.youtube.com/watch?v=gZjDKgR4dw8&index=2&t=656s&list=WL
Implementations
secp256k1
secp256k1, ristretto, ed25519
Merlin: flexible, composable transcripts for zero-knowledge proofs
Merlin is a small Rust library that performs the Fiat-Shamir transformation in software
The ristretto255 Group draft-hdevalence-cfrg-ristretto-00
Building, and building on, Bulletproofs
ZkVM
TxVM