bulletproofs
1.1 Release
Les Bulletproofs sont de courts arguments de connaissance sans connaissance qui ne nécessitent pas de configuration fiable. Les systèmes d’argumentation sont des systèmes de preuve dotés d’une solidité informatique.
Les pare-balles conviennent pour prouver des déclarations sur des valeurs engagées, telles que des preuves de portée, des suffles vérifiables, des circuits arithmétiques, etc. Ils reposent sur l'hypothèse logarithmique discrète et sont rendus non interactifs à l'aide de l'heuristique de Fiat-Shamir.
L'algorithme de base de Bulletproofs est l'algorithme de produit interne présenté par Groth [2]. L'algorithme fournit un argument de connaissance de deux engagements de Pedersen de vecteurs de liaison qui satisfont une relation de produit interne donnée. Les pare-balles s'appuient sur les techniques de Bootle et al. [3] pour introduire une preuve de produit interne efficace en matière de communication qui réduit la complexité globale de la communication de l'argument à seulement 
où 
est la dimension des deux vecteurs d’engagements.
Les Bulletproofs présentent un protocole pour réaliser des épreuves à courte portée et agrégées. Ils codent une preuve de la plage d'un nombre engagé dans un produit interne, à l'aide de polynômes. Les preuves de plage sont des preuves qu'une valeur secrète se situe dans un certain intervalle. Les preuves de plage ne divulguent aucune information sur la valeur secrète, autre que le fait qu'elles se situent dans l'intervalle.
L’algorithme de preuve peut être esquissé en 5 étapes :
Laisser 
être une valeur dans 
et 
un vecteur de bit tel que 
. Les composants de sont les chiffres binaires de . On construit un vecteur complémentaire 
et exiger que 
tient.
- où 
et 
sont les engagements aveuglés de Pedersen à et 
.
- Le vérificateur envoie des défis 
et 
réparer et .
- où 
et 
sont des engagements sur les coefficients 
, d'un polynôme 
construit à partir des valeurs existantes dans le protocole.
, 
- Le vérificateur défie le prouveur avec de la valeur 
.
- Le prouveur envoie plusieurs engagements que le vérificateur vérifiera ensuite.
Voir Prover.hs pour les détails de mise en œuvre.
L'interaction décrite est rendue non interactive à l'aide de la transformation Fiat-Shamir dans laquelle tous les défis aléatoires lancés par V sont remplacés par un hachage de la transcription jusqu'à ce point.
La taille de l'épreuve est encore réduite en tirant parti du format compact 
preuve de produit intérieur.
L'argument du produit interne dans le protocole permet de prouver la connaissance des vecteurs 
et 
, dont le produit interne est et l'engagement 
est un engagement de ces deux vecteurs. On peut donc remplacer l'envoi ( 
) avec un transfert de ( 
) et une exécution d'un argument de produit interne.
Alors, au lieu de partager et , qui a un coût de communication de 
éléments, l'argument du produit interne transmet uniquement 
éléments. Au total, le prouveur envoie uniquement 
éléments de groupe et 5 éléments dans 
Nous pouvons construire une seule preuve de plage de valeurs multiples, tout en n'entraînant qu'un coût d'espace supplémentaire de 
pour 
valeurs supplémentaires , par opposition à un facteur multiplicatif de lors de la création preuves de gamme indépendantes.
La preuve de plage globale utilise l’argument du produit interne. Il utilise ( 
) regrouper les éléments et 5 éléments dans .
Voir l'exemple de preuve multi-gamme
Preuve à plage unique
importer Data.Curve.Weierstrass.SECP256K1 (Fr)importer Bulletproofs.RangeProof qualifié en tant que RPimport Bulletproofs.Utils (commit)testSingleRangeProof :: Integer -> (Fr, Fr) -> IO BooltestSingleRangeProof upperBound (v, vBlinding) = laisser vCommit = commit v vBlinding -- Prouveur proofE <- runExceptT (RP.generateProof upperBound (v, vBlinding)) -- Cas du vérificateur proofE de Left err -> panic (show err) Right [email protected]{..} -> pure (RP.verifyProof upperBound vCommit proof )
Preuve multi-gamme
import Data.Curve.Weierstrass.SECP256K1 (Fr)importer Bulletproofs.MultiRangeProof qualifié en tant que MRPimport Bulletproofs.Utils (commit)testMultiRangeProof :: Integer -> [(Fr, Fr)] -> IO BooltestMultiRangeProof upperBound vsAndvBlindings = do let vCommits = fmap ( validation non curry) vsAndvBlindings -- Démonstrateur proofE <- runExceptT (MRP.generateProof upperBound vsAndvBlindings) -- Cas du vérificateur proofE de Left err -> panic (show err) Right [email protected]{..} -> pure (MRP.verifyProof upperBound vCommits proof)
Notez que la limite supérieure 
doit être tel que 
, où est également une puissance de 2. Cette implémentation utilise la courbe elliptique secp256k1, une courbe de Koblitz, qui a une sécurité de 128 bits. Voir Exemples de preuves de plage pour plus de détails.
Un circuit arithmétique sur un champ et des variables 
est un graphe acyclique orienté dont les sommets sont appelés portes.
Le circuit arithmétique peut être décrit alternativement comme une liste de portes de multiplication avec une collection d'équations de cohérence linéaire reliant les entrées et les sorties des portes. Tout circuit décrit comme un graphe acyclique peut être efficacement converti dans cette description alternative.
Bulletproofs présente un protocole pour générer un argument de connaissance nulle pour les circuits arithmétiques en utilisant l'argument du produit interne, ce qui permet d'obtenir une preuve de taille 
éléments et inclure des valeurs engagées comme entrées dans le circuit arithmétique.
Dans le protocole, le Prover prouve que le produit hadamard de et et un ensemble de contraintes linéaires est valable. Les valeurs d'entrée utilisés pour générer la preuve sont ensuite validés et partagés avec le Vérificateur.
import Data.Curve.Weierstrass.SECP256K1 (Fr)import Data.Field.Galois (rnd)import Bulletproofs.ArithmeticCircuitimport Bulletproofs.Utils (hadamard, commit)-- Exemple :-- 2 contraintes linéaires (q = 2) :-- aL [0] + aL[1] + aL[2] + aL[3] = v[0]-- aR[0] + aR[1] + aR[2] + aR[3] = v[1]---- 4 contraintes de multiplication (implicites) (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 valeurs d'entrée (m = 2)arithCircuitExample :: ArithCircuit FrarithCircuitExample = ArithCircuit
{ poids = 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]]
}
, engagementWeights = [[1, 0]
,[0, 1]]
, cs = [0, 0]
}testArithCircuitProof :: ([Fr], [Fr]) -> ArithCircuit Fr -> IO BooltestArithCircuitProof (aL, aR) arithCircuit = do let m = 2 -- Contraintes de multiplication let aO = aL `hadamard` aR -- Contraintes linéaires
v0 = somme aL
v1 = somme aR
commitBlinders <- replicateM m rnd let engagements = zipWith commit [v0, v1] commitBlinders let arithWitness = ArithWitness
{ affectation = affectation aL aR aO
, engagements = engagements
, commitBlinders = commitBlinders
}
preuve <- generateProof arithCircuit arithWitness pure (vérifyProof engagements preuve arithCircuit)Voir l'exemple de circuit aritmétique pour plus de détails.
Références :
Bunz B., Bootle J., Boneh D., Poelstra A., Wuille P., Maxwell G. "Bulletproofs : courtes preuves pour les transactions confidentielles et plus". Stanford, UCL, Blockstream, 2017
Groth J. "Algèbre linéaire avec arguments sous-linéaires à connaissance nulle". Collège universitaire de Londres, 2009
Bootle J., Cerully A., Chaidos P., Groth J, Petit C. "Arguments efficaces de connaissance nulle pour les circuits arithmétiques dans le cadre de journaux discrets". University College de Londres et Université d'Oxford, 2016.
Notations :
: Produit Hadamard
:Produit intérieur
: Vecteur
Il s'agit d'un code expérimental destiné uniquement aux projets de recherche. Veuillez ne pas utiliser ce code en production tant qu'il n'a pas mûri de manière significative.
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.
