bulletproofs
1.1 Release
Bulletproofs sind kurze wissensfreie Argumente des Wissens, die keine vertrauenswürdige Einrichtung erfordern. Argumentsysteme sind Beweissysteme mit rechnerischer Solidität.
Bulletproofs eignen sich zum Beweis von Aussagen über festgelegte Werte, wie z. B. Bereichsbeweise, überprüfbare Suffles, arithmetische Schaltkreise usw. Sie basieren auf der diskreten logarithmischen Annahme und werden mithilfe der Fiat-Shamir-Heuristik nicht interaktiv gemacht.
Der Kernalgorithmus von Bulletproofs ist der von Groth [2] vorgestellte Inner-Product-Algorithmus. Der Algorithmus liefert ein Argument für die Kenntnis zweier Bindungsvektor-Pedersen-Verpflichtungen, die eine gegebene innere Produktrelation erfüllen. Bulletproofs bauen auf den Techniken von Bootle et al. auf. [3] um einen kommunikationseffizienten Beweis für das innere Produkt einzuführen, der die Gesamtkommunikationskomplexität des Arguments auf nur reduziert 
Wo 
ist die Dimension der beiden Verpflichtungsvektoren.
Bulletproofs stellen ein Protokoll zur Durchführung von Kurz- und aggregierbaren Reichweitennachweisen dar. Sie kodieren mithilfe von Polynomen einen Beweis für den Bereich einer festgelegten Zahl in einem inneren Produkt. Bereichsbeweise sind Beweise dafür, dass ein geheimer Wert in einem bestimmten Intervall liegt. Bereichsbeweise lassen keine Informationen über den geheimen Wert preis, außer der Tatsache, dass sie im Intervall liegen.
Der Beweisalgorithmus kann in 5 Schritten skizziert werden:
Lassen 
ein Wert sein 
Und 
ein Vektor von Bit so 
. Die Bestandteile von sind die Binärziffern von . Wir konstruieren einen Komplementärvektor 
und verlangen das 
hält.
- Wo 
Und 
sind blinde Pedersen-Verpflichtungen Und 
.
- Verifier sendet Herausforderungen 
Und 
reparieren Und .
- Wo 
Und 
sind Verpflichtungen gegenüber den Koeffizienten 
, eines Polynoms 
wird aus den vorhandenen Werten im Protokoll erstellt.
, 
- Der Verifizierer fordert den Prüfer mit Wert heraus 
.
– Der Prüfer sendet mehrere Zusagen, die der Prüfer dann prüft.
Einzelheiten zur Implementierung finden Sie unter Prover.hs.
Die beschriebene Interaktion wird mithilfe der Fiat-Shamir-Transformation nicht interaktiv gemacht, wobei alle von V durchgeführten zufälligen Herausforderungen bis zu diesem Zeitpunkt durch einen Hash des Transkripts ersetzt werden.
Die Größe des Beweises wird durch die Nutzung der Kompaktheit weiter reduziert 
innerer Produktnachweis.
Das Argument des inneren Produkts im Protokoll ermöglicht den Nachweis der Kenntnis von Vektoren 
Und 
, dessen inneres Produkt ist und das Engagement 
ist eine Verpflichtung dieser beiden Vektoren. Wir können daher das Versenden ( 
) mit einer Übertragung von ( 
) und eine Ausführung eines inneren Produktarguments.
Dann statt zu teilen Und , was einen Kommunikationsaufwand von hat 
Elemente überträgt das Inner-Product-Argument nur 
Elemente. Insgesamt sendet der Prüfer nur 
Gruppenelemente und 5 Elemente in 
Wir können einen einzigen Beweis für den Bereich mehrerer Werte erstellen und verursachen dabei nur zusätzliche Platzkosten von 
für 
zusätzliche Werte , im Gegensatz zu einem multiplikativen Faktor von beim Erstellen unabhängige Bereichsnachweise.
Der aggregierte Bereichsbeweis nutzt das Argument des inneren Produkts. Es verwendet ( 
) Gruppenelemente und 5 Elemente in .
Siehe Beispiel für einen Mehrbereichsnachweis
Einzelbereichsnachweis
import Data.Curve.Weierstrass.SECP256K1 (Fr)import Qualified Bulletproofs.RangeProof as RPimport Bulletproofs.Utils (commit)testSingleRangeProof :: Integer -> (Fr, Fr) -> IO BooltestSingleRangeProof UpperBound (v, vBlinding) = do let vCommit = commit v vBlinding – Beweiser ProofE <- runExceptT (RP.generateProof UpperBound (v, vBlinding)) – Verifier Case ProofE von Left err -> Panic (Show Err) Right [email protected]{..} -> Pure (RP.verifyProof UpperBound vCommit Proof )
Mehrbereichssicher
import Data.Curve.Weierstrass.SECP256K1 (Fr)import Qualified Bulletproofs.MultiRangeProof as MRPimport Bulletproofs.Utils (commit)testMultiRangeProof :: Integer -> [(Fr, Fr)] -> IO BooltestMultiRangeProof UpperBound vsAndvBlindings = do let vCommits = fmap ( uncurry commit) vsAndvBlindings -- Prüfer ProofE <- runExceptT (MRP.generateProof UpperBound vsAndvBlindings) – Verifier Case ProofE von Left err -> Panic (show err) Right [email protected]{..} -> Pure (MRP.verifyProof UpperBound vCommits Proof)
Beachten Sie die Obergrenze 
muss so sein 
, Wo ist auch eine Potenz von 2. Diese Implementierung verwendet die elliptische Kurve secp256k1, eine Koblitz-Kurve, die 128-Bit-Sicherheit bietet. Weitere Einzelheiten finden Sie unter Beispiele für Bereichsbeweise.
Eine arithmetische Schaltung über ein Feld und Variablen 
ist ein gerichteter azyklischer Graph, dessen Eckpunkte Tore genannt werden.
Eine arithmetische Schaltung kann alternativ als eine Liste von Multiplikationsgattern mit einer Sammlung linearer Konsistenzgleichungen beschrieben werden, die die Ein- und Ausgänge der Tore in Beziehung setzen. Jede als azyklischer Graph beschriebene Schaltung kann effizient in diese alternative Beschreibung umgewandelt werden.
Bulletproofs stellen ein Protokoll zur Generierung von Zero-Knowledge-Argumenten für arithmetische Schaltkreise unter Verwendung des inneren Produktarguments dar, das einen Größenbeweis ermöglicht 
Elemente und schließen festgeschriebene Werte als Eingaben für die Rechenschaltung ein.
Im Protokoll beweist der Prüfer, dass das Hadamard-Produkt von Und und es gelten eine Reihe linearer Einschränkungen. Die Eingabewerte Die zur Erstellung des Nachweises verwendeten Daten werden dann festgeschrieben und an den Verifizierer weitergegeben.
import Data.Curve.Weierstrass.SECP256K1 (Fr)import Data.Field.Galois (rnd)import Bulletproofs.ArithmeticCircuitimport Bulletproofs.Utils (hadamard, commit)-- Beispiel:-- 2 lineare Einschränkungen (q = 2):-- aL [0] + aL[1] + aL[2] + aL[3] = v[0]-- aR[0] + aR[1] + aR[2] + aR[3] = v[1]---- 4 Multiplikationsbeschränkungen (implizit) (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 Eingabewerte (m = 2)arithCircuitExample :: ArithCircuit FrarithCircuitExample = ArithCircuit
{weights = GateWeights
{ wL = [[1, 1, 1, 1]
,[0, 0, 0, 0]]
, wR = [[0, 0, 0, 0]
,[1, 1, 1, 1]]
, woO = [[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 – Multiplikationsbeschränkungen let aO = aL `hadamard` aR – Lineare Beschränkungen
v0 = Summe aL
v1 = Summe aR
commitBlinders <- ReplicateM m rnd let commits = zipWith commit [v0, v1] commitBlinders let arithWitness = ArithWitness
{ Zuweisung = Zuweisung aL aR aO
, Verpflichtungen = Verpflichtungen
, commitBlinders = commitBlinders
}
Beweis <- genericProof arithCircuit arithWitness pure (verifyProof Commitments Proof arithCircuit)Weitere Einzelheiten finden Sie im Beispiel für eine arithmetische Schaltung.
Referenzen :
Bunz B., Bootle J., Boneh D., Poelstra A., Wuille P., Maxwell G. „Bulletproofs: Kurze Beweise für vertrauliche Transaktionen und mehr“. Stanford, UCL, Blockstream, 2017
Groth J. „Lineare Algebra mit sublinearen Zero-Knowledge-Argumenten“. University College London, 2009
Bootle J., Cerully A., Chaidos P., Groth J, Petit C. „Effiziente Zero-Knowledge-Argumente für arithmetische Schaltkreise in der diskreten Protokolleinstellung“. University College London und University of Oxford, 2016.
Notation :
: Hadamard-Produkt
:Inneres Produkt
: Vektor
Hierbei handelt es sich um experimentellen Code, der ausschließlich für Forschungsprojekte gedacht ist. Bitte verwenden Sie diesen Code nicht in der Produktion, bis er erheblich ausgereift ist.
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.
