bulletproofs
1.1 Release
Las pruebas de balas son argumentos breves de conocimiento cero que no requieren una configuración confiable. Los sistemas de argumentos son sistemas de prueba con solidez computacional.
Las pruebas de balas son adecuadas para probar declaraciones sobre valores comprometidos, como pruebas de rango, sufles verificables, circuitos aritméticos, etc. Se basan en el supuesto logarítmico discreto y se vuelven no interactivos utilizando la heurística Fiat-Shamir.
El algoritmo central de Bulletproofs es el algoritmo de producto interno presentado por Groth [2]. El algoritmo proporciona un argumento de conocimiento de dos compromisos de Pedersen de vectores vinculantes que satisfacen una relación de producto interna dada. Los Bulletproofs se basan en las técnicas de Bootle et al. [3] para introducir una prueba de producto interno eficiente en la comunicación que reduzca la complejidad general de la comunicación del argumento a solo 
dónde 
es la dimensión de los dos vectores de compromisos.
Bulletproofs presenta un protocolo para realizar pruebas de alcance corto y agregable. Codifican una prueba del rango de un número comprometido en un producto interno, utilizando polinomios. Las pruebas de rango son pruebas de que un valor secreto se encuentra en un intervalo determinado. Las pruebas de rango no filtran ninguna información sobre el valor secreto, aparte del hecho de que se encuentran en el intervalo.
El algoritmo de prueba se puede esbozar en 5 pasos:
Dejar 
ser un valor en 
y 
un vector de bits tal que 
. Los componentes de son los dígitos binarios de . Construimos un vector complementario. 
y exigir que 
sostiene.
- dónde 
y 
están ciegos los compromisos de Pedersen con y 
.
- Verificador envía desafíos 
y 
arreglar y .
- dónde 
y 
son compromisos con los coeficientes 
, de un polinomio 
construido a partir de los valores existentes en el protocolo.
, 
- El verificador desafía al probador con valor 
.
- El probador envía varios compromisos que luego el verificador verificará.
Consulte Prover.hs para obtener detalles de implementación.
La interacción descrita se vuelve no interactiva utilizando la Transformada Fiat-Shamir en la que todos los desafíos aleatorios realizados por V se reemplazan con un hash de la transcripción hasta ese punto.
El tamaño de la prueba se reduce aún más aprovechando el compacto 
Prueba interna del producto.
El argumento del producto interno en el protocolo permite demostrar el conocimiento de los vectores. 
y 
, cuyo producto interno es y el compromiso 
es un compromiso de estos dos vectores. Por lo tanto podemos reemplazar el envío ( 
) con una transferencia de ( 
) y una ejecución de un argumento de producto interno.
Entonces, en lugar de compartir y , que tiene un coste de comunicación de 
elementos, el argumento del producto interno transmite sólo 
elementos. En total, el probador envía sólo 
elementos del grupo y 5 elementos en 
Podemos construir una única prueba de rango de múltiples valores, mientras solo incurrimos en un costo de espacio adicional de 
para 
valores adicionales , a diferencia de un factor multiplicativo de al crear pruebas de rango independientes.
La prueba de rango agregado hace uso del argumento del producto interno. Utiliza ( 
) elementos del grupo y 5 elementos en .
Ver ejemplo de prueba de rango múltiple
Prueba de rango único
importar Data.Curve.Weierstrass.SECP256K1 (Fr) importar Bulletproofs.RangeProof calificado como RPimport Bulletproofs.Utils (commit)testSingleRangeProof :: Integer -> (Fr, Fr) -> IO BooltestSingleRangeProof UpperBound (v, vBlinding) = dejar vCommit = cometer v vBlinding - Prover pruebaE <- runExceptT (RP.generateProof UpperBound (v, vBlinding)) - Caso del verificador pruebaE de error izquierdo -> pánico (mostrar error) Prueba [email protected]{..} -> puro (RP.verifyProof UpperBound vCommit prueba )
Prueba de rango múltiple
importar Data.Curve.Weierstrass.SECP256K1 (Fr)importar Bulletproofs.MultiRangeProof calificado como MRPimportar Bulletproofs.Utils (commit)testMultiRangeProof :: Integer -> [(Fr, Fr)] -> IO BooltestMultiRangeProof lowerBound vsAndvBlindings = do let vCommits = fmap ( compromiso no cursado) vsAndvBlindings -- Probador pruebaE <- runExceptT (MRP.generateProof UpperBound vsAndvBlindings) - Caso del verificador pruebaE de error izquierdo -> pánico (mostrar error) Prueba [email protected]{..} -> puro (MRP.verifyProof prueba de vCommits de límite superior)
Tenga en cuenta que el límite superior 
debe ser tal que 
, dónde también es una potencia de 2. Esta implementación utiliza la curva elíptica secp256k1, una curva de Koblitz, que tiene seguridad de 128 bits. Consulte ejemplos de pruebas de rango para obtener más detalles.
Un circuito aritmético sobre un campo y variables. 
es un gráfico acíclico dirigido cuyos vértices se llaman puertas.
El circuito aritmético se puede describir alternativamente como una lista de puertas de multiplicación con una colección de ecuaciones de consistencia lineal que relacionan las entradas y salidas de las puertas. Cualquier circuito descrito como un gráfico acíclico se puede convertir eficientemente a esta descripción alternativa.
Bulletproofs presenta un protocolo para generar argumentos de conocimiento cero para circuitos aritméticos utilizando el argumento del producto interno, lo que permite obtener una prueba de tamaño. 
elementos e incluyen valores comprometidos como entradas al circuito aritmético.
En el protocolo, el probador demuestra que el producto hadamard de y y se cumple un conjunto de restricciones lineales. Los valores de entrada Los datos utilizados para generar la prueba se confirman y se comparten con el Verificador.
importar Data.Curve.Weierstrass.SECP256K1 (Fr)importar Data.Field.Galois (rnd)importar Bulletproofs.ArithmeticCircuitimport Bulletproofs.Utils (hadamard, commit)-- Ejemplo:-- 2 restricciones lineales (q = 2):-- aL [0] + aL[1] + aL[2] + aL[3] = v[0]-- aR[0] + aR[1] + aR[2] + aR[3] = v[1]---- 4 restricciones de multiplicación (implícitas) (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 valores de entrada (m = 2)arithCircuitExample :: ArithCircuit FrarithCircuitExample = ArithCircuit
{ pesos = Pesos de puerta
{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]]
}
, compromisoPesos = [[1, 0]
,[0, 1]]
, cs = [0, 0]
}testArithCircuitProof :: ([Fr], [Fr]) -> ArithCircuit Fr -> IO BooltestArithCircuitProof (aL, aR) arithCircuit = do let m = 2 -- Restricciones de multiplicación let aO = aL `hadamard` aR -- Restricciones lineales
v0 = suma aL
v1 = suma aR
commitBlinders <- replicateM m rnd let compromisos = zipWith compromiso [v0, v1] commitBlinders let arithWitness = ArithWitness
{ tarea = Tarea aL aR aO
, compromisos = compromisos
, cometerBlinders = comprometerBlinders
}
prueba <- generarPrueba arithCircuit arithWitness puro (verificarProof compromisos prueba arithCircuit)Consulte el ejemplo de circuito aritmético para obtener más detalles.
Referencias :
Bunz B., Bootle J., Boneh D., Poelstra A., Wuille P., Maxwell G. "Balas: pruebas breves para transacciones confidenciales y más". Stanford, UCL, Blockstream, 2017
Groth J. "Álgebra lineal con argumentos sublineales de conocimiento cero". University College de Londres, 2009
Bootle J., Cerully A., Chaidos P., Groth J, Petit C. "Argumentos eficientes de conocimiento cero para circuitos aritméticos en el entorno de registros discretos". University College London y Universidad de Oxford, 2016.
Notación :
: Producto Hadamard
:Producto interno
: Vectorial
Este es un código experimental destinado únicamente a proyectos de investigación. No utilice este código en producción hasta que haya madurado significativamente.
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.
