bulletproofs
1.1 Release
Bulletproof は、信頼できるセットアップを必要としない、知識に関する短いゼロ知識の議論です。議論システムは、計算上の健全性を備えた証明システムです。
Bulletproof は、範囲証明、検証可能なサッフル、算術回路など、コミットされた値に関するステートメントの証明に適しています。Bulletproof は、離散対数の仮定に依存し、Fiat-Shamir ヒューリスティックを使用して非対話型に作成されます。
Bulletproofs のコア アルゴリズムは、Groth [2] によって提示された内積アルゴリズムです。このアルゴリズムは、指定された内積関係を満たす 2 つの結合ベクトル Pedersen コミットメントの知識の引数を提供します。 Bulletproof は Bootle らの技術に基づいて構築されています。 [3] 引数の全体的な通信の複雑さを最小限に抑える、通信効率の高い内積証明を導入します。 
どこ
はコミットメントの 2 つのベクトルの次元です。
Bulletproofs は、短く集約可能な範囲の証明を行うためのプロトコルを提供します。これらは、多項式を使用して、内積で確定された数値の範囲の証明をエンコードします。範囲証明は、秘密の値が特定の範囲内にあることの証明です。範囲証明は、シークレット値が区間内にあるという事実を除き、シークレット値に関する情報を漏らしません。
証明アルゴリズムは 5 つのステップで概略的に説明できます。
させて
の値になる
そして
次のようなビットのベクトル
。のコンポーネントは の 2 進数です 。相補的なベクターを構築します
そしてそれを要求します
が成立する。
- どこ
そして
ペダーセンの盲目的な約束は、 そして
。
- 検証者がチャレンジを送信
そして
直すそして 。
- どこ
そして
係数に対するコミットメントです
多項式の
プロトコル内の既存の値から構築されます。
、 
- 検証者は価値のある証明者に挑戦します
。
- 証明者はいくつかのコミットメントを送信し、検証者がそれをチェックします。
実装の詳細については、Prover.hs を参照してください。
説明されているインタラクションは、V によって行われたすべてのランダムなチャレンジがその時点までのトランスクリプトのハッシュに置き換えられる Fiat-Shamir 変換を使用して非インタラクティブにされます。
コンパクトさを活用することで証明のサイズがさらに縮小されます。 
内積証明。
プロトコルの内積引数により、ベクトルの知識を証明できます。 
そして
、その内積はそしてコミットメント
は、この 2 つのベクトルのコミットメントです。したがって、送信を置き換えることができます ( 
) の転送により ( 
) と内積引数の実行。
次に、共有する代わりに、 そしての通信コストがかかります。 
要素、内積引数はのみを送信します
要素。合計すると、証明者が送信するのは
グループ要素と 5 つの要素
追加のスペースコストがかかるだけで、複数の値の範囲を示す単一の証明を構築できます。 
のために
追加の値の乗算係数とは対照的に、 作成するとき独立した範囲証明。
集計範囲の証明では、内積引数を利用します。それは ( 
) グループ要素と 5 つの要素 。
マルチレンジの証明例を参照してください。
単一範囲の証明
import Data.Curve.Weierstrass.SECP256K1 (Fr)修飾された Bulletproofs.RangeProof を RP としてインポートBulletproofs.Utils をインポート (commit)testSingleRangeProof :: Integer -> (Fr, Fr) -> IO BooltestSingleRangeProof upperBound (v, vBlinding) = do let vCommit = commit v vBlinding -- 証明者 proofE <- runExceptT (RP.generateProof upperBound (v, vBlinding)) -- 検証者のケースproofE 左 err -> パニック (show err) 右[email protected]{..} -> pure (RP.verifyProof upperBound vCommitproof ）
マルチレンジプルーフ
import Data.Curve.Weierstrass.SECP256K1 (Fr)修飾された Bulletproofs.MultiRangeProof を MRP としてインポートimport Bulletproofs.Utils (commit)testMultiRangeProof :: Integer -> [(Fr, Fr)] -> IO BooltestMultiRangeProof upperBound vsAndvBlindings = do let vCommits = fmap (アンカリーコミット) vsAndvBlindings -- 証明者 proofE <- runExceptT (MRP.generateProof upperBound vsAndvBlindings) -- ベリファイア ケースproofE 左 err -> パニック (show err) 右[email protected]{..} -> pure (MRP.verifyProof upperBound vCommits 証明)
上限に注意してください
そうでなければなりません
、 どこまた、2 の累乗です。この実装では、128 ビット セキュリティを持つコブリッツ曲線である楕円曲線 secp256k1 を使用します。詳細については、範囲証明の例を参照してください。
フィールドと変数の算術回路
は、頂点がゲートと呼ばれる有向非巡回グラフです。
算術回路は、ゲートの入力と出力を関連付ける線形一貫性方程式の集合を備えた乗算ゲートのリストとして記述することもできます。非巡回グラフとして記述された回路は、この代替記述に効率的に変換できます。
Bulletproofs は、内積引数を使用して算術回路のゼロ知識引数を生成するプロトコルを提供し、サイズの証明を取得できるようにします。 
要素に含まれ、算術回路への入力としてコミットされた値が含まれます。
議定書の中で、証明者は、次のアダマール積が次のことを証明します。 そしてそして一連の線形制約が成立します。入力値証明の生成に使用されたデータはコミットされ、検証者と共有されます。
import Data.Curve.Weierstrass.SECP256K1 (Fr)import Data.Field.Galois (rnd)import Bulletproofs.ArithmeticCircuitimport Bulletproofs.Utils (hadamard、commit)-- 例:-- 2 つの線形制約 (q = 2):-- aL [0] + aL[1] + aL[2] + aL[3] = v[0]-- aR[0] + aR[1] + aR[2] + aR[3] = v[1]---- 4 つの乗算制約 (暗黙的) (n = 4):-- aL[ 0] * aR[0] = aO[0] -- aL[1] * aR[1] = aO[1] -- aL[2] * aR[2] = aO[2] -- aL[3] * aR[3] = aO[3]---- 2 つの入力値 (m = 2)arithCircuitExample :: ArithCircuit FrarithCircuitExample = ArithCircuit
{ 重み = GateWeights
{ wL = [[1, 1, 1, 1]
,[0, 0, 0, 0]]
、wR = [[0, 0, 0, 0]
、[1、1、1、1]]
、wO = [[0, 0, 0, 0]
,[0, 0, 0, 0]]
}
、commitmentWeights = [[1, 0]
,[0, 1]]
、cs = [0, 0]
}testArithCircuitProof :: ([Fr], [Fr]) -> ArithCircuit Fr -> IO BooltestArithCircuitProof (aL, aR) arithCircuit = do let m = 2 -- 乗算制約 let aO = aL `hadamard` aR -- 線形制約
v0 = 合計 aL
v1 = 合計 aR
commitBlinders <-replicateM m rnd let commitments = zipWith commit [v0, v1] commitBlinders let arithWitness = ArithWitness
{ 割り当て = 割り当て aL aR aO
、コミットメント = コミットメント
、コミットブラインダー = コミットブラインダー
}
proof <-generateProof arithCircuit arithWitness pure (verifyProof コミットメントproof arithCircuit)詳細については、算術回路の例を参照してください。
参考文献：
Bunz B.、Bootle J.、Boneh D.、Poelstra A.、Wuille P.、Maxwell G.「防弾: 機密取引などの簡易証拠」。スタンフォード、UCL、ブロックストリーム、2017
Groth J.「準線形ゼロ知識引数を使用した線形代数」。ユニバーシティ・カレッジ・ロンドン、2009 年
Bootle J.、Cerully A.、Chaidos P.、Groth J、Petit C.「離散対数設定における算術回路の効率的なゼロ知識引数」。ユニバーシティ・カレッジ・ロンドンとオックスフォード大学、2016年。
表記法：
：アダマール積
：内積
: ベクトル
これは研究レベルのプロジェクトのみを対象とした実験的なコードです。このコードが十分に成熟するまでは、実稼働環境でこのコードを使用しないでください。
Copyright 2018-2022 Stephen Diehl Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
