bulletproofs
1.1 Release
Bulletproofs são argumentos curtos de conhecimento zero que não requerem uma configuração confiável. Os sistemas de argumentos são sistemas de prova com solidez computacional.
Bulletproofs são adequados para provar declarações sobre valores comprometidos, como provas de intervalo, suflês verificáveis, circuitos aritméticos, etc. Eles se baseiam na suposição logarítmica discreta e são tornados não interativos usando a heurística Fiat-Shamir.
O algoritmo central do Bulletproofs é o algoritmo de produto interno apresentado por Groth [2]. O algoritmo fornece um argumento de conhecimento de dois compromissos de Pedersen do vetor vinculativo que satisfazem uma dada relação de produto interno. A prova de balas baseia-se nas técnicas de Bootle et al. [3] para introduzir uma prova de produto interno eficiente em comunicação que reduza a complexidade geral da comunicação do argumento para apenas 
onde 
é a dimensão dos dois vetores de compromissos.
Bulletproofs apresentam um protocolo para conduzir provas de alcance curto e agregável. Eles codificam uma prova do intervalo de um número confirmado em um produto interno, usando polinômios. Provas de intervalo são provas de que um valor secreto está em um determinado intervalo. As provas de intervalo não vazam nenhuma informação sobre o valor secreto, exceto o fato de estarem no intervalo.
O algoritmo de prova pode ser esboçado em 5 etapas:
Deixar 
ser um valor em 
e 
um vetor de bit tal que 
. Os componentes de são os dígitos binários de . Construímos um vetor complementar 
e exigir isso 
segura.
- onde 
e 
estão cegos os compromissos de Pedersen com e 
.
- Verificador envia desafios 
e 
consertar e .
- onde 
e 
são compromissos com os coeficientes 
, de um polinômio 
construído a partir dos valores existentes no protocolo.
, 
- O verificador desafia o provador com valor 
.
- O Prover envia vários compromissos que o verificador irá então verificar.
Consulte Prover.hs para obter detalhes de implementação.
A interação descrita torna-se não interativa usando a Transformada Fiat-Shamir, onde todos os desafios aleatórios feitos por V são substituídos por um hash da transcrição até aquele ponto.
O tamanho da prova é ainda mais reduzido aproveitando o formato compacto 
prova interna do produto.
O argumento do produto interno no protocolo permite provar o conhecimento dos vetores 
e 
, cujo produto interno é e o compromisso 
é um compromisso destes dois vetores. Podemos, portanto, substituir o envio ( 
) com uma transferência de ( 
) e uma execução de um argumento de produto interno.
Então, em vez de compartilhar e , que tem um custo de comunicação de 
elementos, o argumento do produto interno transmite apenas 
elementos. No total, o provador envia apenas 
elementos do grupo e 5 elementos em 
Podemos construir uma única prova de intervalo de vários valores, incorrendo apenas em um custo de espaço adicional de 
para 
valores adicionais , em oposição a um fator multiplicativo de ao criar provas de intervalo independentes.
A prova de intervalo agregado faz uso do argumento do produto interno. Ele usa ( 
) agrupar elementos e 5 elementos em .
Veja exemplo de prova de multi faixa
Prova de intervalo único
importar Data.Curve.Weierstrass.SECP256K1 (Fr)importar Bulletproofs.RangeProof qualificados como RPimport Bulletproofs.Utils (commit)testSingleRangeProof :: Integer -> (Fr, Fr) -> IO BooltestSingleRangeProof upperBound (v, vBlinding) = deixe vCommit = commit v vBlinding - Provador provaE <- runExceptT (RP.generateProof upperBound (v, vBlinding)) - Verificador de caso provaE de Esquerda err -> pânico (mostrar erro) Prova [email protected]{..} -> puro (RP.verifyProof UpperBound vCommit prova )
Prova de vários alcances
importar Data.Curve.Weierstrass.SECP256K1 (Fr)importar Bulletproofs.MultiRangeProof qualificados como MRPimport Bulletproofs.Utils (commit)testMultiRangeProof :: Integer -> [(Fr, Fr)] -> IO BooltestMultiRangeProof upperBound vsAndvBlindings = do let vCommits = fmap ( commit sem curry) vsAndvBlindings – Provador provaE <- runExceptT (MRP.generateProof upperBound vsAndvBlindings) - Verificador de caso provaE de Esquerda err -> pânico (mostrar erro) Direita [email protected]{..} -> puro (MRP.verifyProof UpperBound vCommits prova)
Observe que o limite superior 
deve ser tal que 
, onde também é uma potência de 2. Esta implementação usa a curva elíptica secp256k1, uma curva Koblitz, que possui segurança de 128 bits. Consulte exemplos de provas de intervalo para obter mais detalhes.
Um circuito aritmético sobre um campo e variáveis 
é um gráfico acíclico direcionado cujos vértices são chamados de portas.
O circuito aritmético pode ser descrito alternativamente como uma lista de portas de multiplicação com uma coleção de equações de consistência linear relacionando as entradas e saídas das portas. Qualquer circuito descrito como um gráfico acíclico pode ser convertido com eficiência nesta descrição alternativa.
Bulletproofs apresentam um protocolo para gerar argumentos de conhecimento zero para circuitos aritméticos usando o argumento do produto interno, o que permite obter uma prova de tamanho 
elementos e incluem valores confirmados como entradas para o circuito aritmético.
No protocolo, o Provador prova que o produto hadamard de e e um conjunto de restrições lineares é válido. Os valores de entrada usados para gerar a prova são então confirmados e compartilhados com o verificador.
importar Data.Curve.Weierstrass.SECP256K1 (Fr)importar Data.Field.Galois (rnd)importar Bulletproofs.ArithmeticCircuitimport Bulletproofs.Utils (hadamard, commit)-- Exemplo:-- 2 restrições lineares (q = 2):-- aL [0] + aL[1] + aL[2] + aL[3] = v[0]-- aR[0] + aR[1] + aR[2] + aR[3] = v[1]---- 4 restrições de multiplicação (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 = 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]]
}
, compromissoPesos = [[1, 0]
,[0, 1]]
, cs = [0, 0]
}testArithCircuitProof :: ([Fr], [Fr]) -> ArithCircuit Fr -> IO BooltestArithCircuitProof (aL, aR) arithCircuit = do let m = 2 -- Restrições de multiplicação let aO = aL `hadamard` aR -- Restrições lineares
v0 = soma aL
v1 = soma aR
commitBlinders <- replicateM m rnd let commits = zipWith commit [v0, v1] commitBlinders let arithWitness = ArithWitness
{ atribuição = Atribuição aL aR aO
, compromissos = compromissos
, commitBlinders = commitBlinders
}
prova <- generateProof arithCircuit arithWitness puro (verifyProof compromissos prova arithCircuit)Veja exemplo de circuito aritmético para mais detalhes.
Referências :
Bunz B., Bootle J., Boneh D., Poelstra A., Wuille P., Maxwell G. "Bulletproofs: Short Proofs for Confidential Transactions and More". Stanford, UCL, Blockstream, 2017
Groth J. "Álgebra Linear com Argumentos Sublineares de Conhecimento Zero". Faculdade Universitária de Londres, 2009
Bootle J., Cerully A., Chaidos P., Groth J, Petit C. "Argumentos eficientes de conhecimento zero para circuitos aritméticos na configuração de log discreto". University College Londres e Universidade de Oxford, 2016.
Notação :
: Produto Hadamard
:Produto interno
: Vetor
Este é um código experimental destinado apenas a projetos de pesquisa. Por favor, não use este código em produção até que ele esteja significativamente amadurecido.
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.
