Finalmente, chegamos a um ponto em que podemos começar a nossa exploração de provas de conhecimento zero. Nesta discussão, nos aprofundaremos na criptografia e compreenderemos os conceitos de provador, verificador e configuração confiável.
Nos bastidores do protocolo zkSNARK Groth16 (parte 3)
No artigo anterior, construímos um Programa Aritmético Quadrático (QAP) para nosso programa original. Este QAP consiste em cinco polinômios:U, V, W, T, eH:
U = 11856131555579607412050136445347690672963697383558685269503193934395229601792x^4 + 200642226325193356203925385998191688311 69334033714698148390020504361157787655x^3 + 20976232752179305421319472172538221959858849217065366246044112345468483141610x^2 + 12768141675239577212977070018066743801653212566909353367157285775502554955812x + 21888242871839275222246405745257275088548364 4 00416034343698204186575808495601
V = 10944121435919637611123202872628637544274182200208017171849102093287904247809x^4 + 364804047863987920370773429087621251475 8060733402672390616367364429301415930x^3 + 10944121435919637611123202872628637544274182200208017171849102093287904247836x^2 + 1 8240202393199396018538671454381062573790303667013361953081836822146507079635x + 26
W = 1276814167523957721297707001806674380165321256690935336715728577502554955771x^4 + 729608095727975840741546858175242502951 14 592161914559516814830937163504850059032242933610689562465469457717205664076x + 21888242871839275222246405745257275088548364 400 416034343698204186575808495461
T = x ^ 5 + 21888242871839275222246405745257275088548364400416034343698204186575808495602x ^ 4 + 85x ^ 3 + 2188824287183927522224640574 5257275088548364400416034343698204186575808495392x^2 + 274x + 21888242871839275222246405745257275088548364400416034343698204186 575808495497
H = 5928065777789803706025068222673845336481848691779342634751596967197614800896x^3 + 1489616528777950674847324835441120110192 8747994727578928350166738086314115075x^2 + 1672018552709944635032711549984930735930777836142891512365835042030096482298x + 1824 0202393199396018538671454381062573790303667013361953081836822146507079683
Alternativamente, você pode encontrar todos os cálculos aqui. Antes de nos aprofundarmos, é essencial introduzir um conceito matemático fundamental: curvas elípticas.
BN254 (BN128)
BN254 (BN128)
Curvas Elípticas (EC) são um assunto vasto por si só. Embora não vá me aprofundar nelas neste artigo, recomendo fortemente que você explore mais sobre as ECs. Elas servem como um dos pilares fundamentais da moderna criptografia de chave pública. O protocolo Groth16, por exemplo, emprega uma curva elíptica específica conhecida como BN254. Essa curva possui um conjunto de características benéficas e é suportada pela blockchain Ethereum.
Mas por que as curvas elípticas são essenciais? Lembre-se do primeiro artigo, quando discutimos que os zkSNARKs permitem que Alice (a provadora) convença Bob (o verificador) de uma afirmação específica sem revelar qualquer conhecimento subjacente. As curvas elípticas desempenham um papel fundamental na facilitação desse processo. No contexto da nossa discussão, o objetivo é convencer o verificador de que executamos um programa específico com um certo número de argumentos, alcançamos um resultado e todas as evidências necessárias podem ser representadas por cinco polinômios. Além disso, isto deve ser conseguido de tal forma que o verificador permaneça alheio às especificidades.
A esta altura, alguns de vocês já devem estar tendo uma noção do que o provador e o verificador precisam fazer. A pobre Alice (a provadora) tem a difícil tarefa de realizar todos esses cálculos complexos. Ela precisa avaliar polinômios com valor aleatório τ (tau) e então passar os resultados para Bob (o verificador). Enquanto isso, Bob tem um trabalho mais simples: ele só precisa usar esses valores para verificar se a equação é verdadeira:
u = U(tau)
v = V(tau)
_w = W(tau) # desculpe, w foi obtido pelo vetor testemunha
ht = H(tau)*T_tau
assert u * v == _w + ht, f"{u} * {v} != {_w} + {ht}" # esta equação deve ser válida
No entanto, essa abordagem apresenta inúmeras vulnerabilidades de segurança. Considere um cenário em que Alice, depois de realizar repetidamente esses cálculos complexos, fica cansada. Ela pode decidir simplesmente inventar números que ela espera que convençam Bob. Além disso, como Bob pode ter certeza de que Alice está fornecendo provas da afirmação correta? Para abordar essas preocupações, precisamos colocar Bob e Alice dentro de um “framework” ou “ambiente” comum. É aqui que as curvas elípticas entram em jogo.
Aqui estão algumas observações introdutórias sobre curvas elípticas (ECs):
- ECs pertencem à categoria de Grupos de Campos Finitos da Álgebra Abstrata.
- Ao selecionar um ponto em uma curva elíptica e “multiplicá-lo” por um número, você derivará outro ponto nessa mesma curva. No entanto, a engenharia reversa do número original a partir do ponto resultante é um desafio formidável. Este mecanismo lembra um processo de codificação ou criptografia.
- Adicionar dois pontos na curva produzirá um novo ponto.
- Nem todas as curvas elípticas podem ser empregadas para esta finalidade. A curva deve ser “amigável ao emparelhamento”. Embora isso possa parecer abstrato, significa essencialmente que quando você emparelha um ponto de um grupo com um ponto de outro grupo, o resultado pertencerá a um terceiro grupo distinto.
Primeiro, precisamos de um intermediário – a “configuração confiável”. Essa entidade colocará Alice e Bob em um ambiente unificado. A configuração confiável fornece parâmetros essenciais, mas em formato criptografado, garantindo que nem Alice e nem Bob possam decifrar sua verdadeira natureza. Isto é crucial, pois não queremos deixar isso ao acaso ou confiar na suposição de que Alice ou Bob agirão com integridade.
Por enquanto, vamos iniciar o parâmetro τ (tau):
print("Setup phase")
print("-"*10)
print("Toxic waste:")
tau = FP(20)
print(f"τ = {tau}")
T_tau = T(tau)
print(f"\nT(τ) = {T_tau}")
# ...
from py_ecc.optimized_bn128 import multiply, G1, G2, add, pairing, neg, normalize
# G1[τ^0], G1[τ^1], ..., G1[τ^d]
tau_G1 = [multiply(G1, int(tau**i)) for i in range(0, T.degree)]
# G1[τ^0 * T(τ)], G1[τ^1 * T(τ)], ..., G1[τ^d-1 * T(τ)]
target_G1 = [multiply(G1, int(tau**i * T_tau)) for i in range(0, T.degree - 1)]
# G2[τ^0], G2[τ^1], ..., G2[τ^d]
tau_G2 = [multiply(G2, int(tau**i)) for i in range(0, T.degree)]
print("Trusted setup:")
print("-"*10)
print(f"[τ]G1 = {[normalize(point) for point in tau_G1]}")
print(f"[T(τ)]G1 = {[normalize(point) for point in target_G1]}")
print(f"\n[τ]G2 = {[normalize(point) for point in tau_G2]}")
Fase de configuração
----------
Lixo tóxico:
τ = 20
T(τ) = 1395360
Configuração confiável:
----------
[τ]G1 = [(1, 2), (18947110137775984544896515092961257947872750783784269176923414004072777296602, 12292085037693291586083644966434670280746730626861846747147579999202931064992), (16262199471205794413544947826745938654132104752637586692048329713311590397011, 13296900385261935021718889695689394625708483652039722230815936262285054528714), (21603600070689675766438470661345954782419355034652174505468210225883925863279, 15787091953565760722773063158476721787069408761080596737736006929439659337677), (3791913980001525405070663195453841654293855276471519589821575313643995787424, 2219850731288481436925303713906758446890789653022769553096390029843417460412)]
[T(τ)]G1 = [(1641247283492879903468444805169804215277964208279225379119694118848884481979, 18733245328562972535068072505811612803902036184072974454572123739995203670419), (1282524939337382483469274134339301655621870987447481453798307725808867601190, 15539182012162102815636574710752557587640625547182202465638914992086098498248), (19470090098801808262306491352642435880415138366575553697569183294142349316803, 21283889500356371386534994908069309335293143510390960327225612194996849127112), (10272948573416532171977932623710258063324920576107343417279327107779961629108, 18785282366980801465045077992366429274473968090047129812171188476045329716662)]
[τ]G2 = [((10857046999023057135944570762232829481370756359578518086990519993285655852781, 11559732032986387107991004021392285783925812861821192530917403151452391805634), (8495653923123431417604973247489272438418190587263600148770280649306958101930, 4082367875863433681332203403145435568316851327593401208105741076214120093531)), ((6584456886510528562221720296624431746328412524156386210384049614268366928061, 13505823173380835868587575884635704883599421098297400455389802021584825778173), (5101591763860554569577488373372350852473588323930260132008193335489992486594, 17537837094362477976396927178636162167615173290927363003743794104386247847571)), ((15315709620702712460485525966545043944570955016708868204420815750896718746085, 8198197634290639555322052407476232699891641457211856758911101094525731144652), (19804470431547976995467325770475378164766256111835164108366808772087600898145, 4235451872741546336515947567132583436895052948569531554551940659752625222062)), ((19986635427443701428465822624011212382759073037311242937305101102870069910445, 4365363970999997341736126578359184214376070323546413373836819260736276531573), (6768274913977306625187058548104595250269239694287045313007233388318706298825, 1559204428094304399156219358984665346302412186219957044834017722538687643212)), ((743861075034088442646324877524709646812464544329658687977963153953325237344, 5808982581765237968275179275525571115489463112173520579009942912940231914163), (12575326356272000951645854762614021668091710139241570303614619233551006506090, 6009878921857975104286236990966997397219740870771405697347402593872065076583))]
G1,G2 — são pontos na curva elíptica, você pode considerá-los como um “1” em um domínio de curvas elípticas.
A parte do provador será a seguinte:
def evaluate_poly(poly, trusted_points, verbose=False):
coeff = poly.coefficients()[::-1]
assert len(coeff) == len(trusted_points), "Polynomial degree mismatch!"
if verbose:
[print(normalize(point)) for point in trusted_points]
terms = [multiply(point, int(coeff)) for point, coeff in zip(trusted_points, coeff)]
evaluation = terms[0]
for i in range(1, len(terms)):
evaluation = add(evaluation, terms[i])
if verbose:
print("-"*10)
print(normalize(evaluation))
return evaluation
print("\nProof generation:")
print("-"*10)
# G1[u0 * τ^0] + G1[u1 * τ^1] + ... + G1[ud-1 * τ^d-1]
A_G1 = evaluate_poly(U, tau_G1)
# G2[v0 * τ^0] + G2[v1 * τ^1] + ... + G2[vd-1 * τ^d-1]
B_G2 = evaluate_poly(V, tau_G2)
# G1[w0 * τ^0] + G1[w1 * τ^1] + ... + G1[wd-1 * τ^d-1]
B_G1 = evaluate_poly(V, tau_G1)
# G1[w0 * τ^0] + G1[w1 * τ^1] + ... + G1[wd-1 * τ^d-1]
Cw_G1 = evaluate_poly(W, tau_G1)
# G1[h0 * τ^0 * T(τ)] + G1[h1 * τ^1 * T(τ)] + ... + G1[hd-2 * τ^d-2 * T(τ)]
HT_G1 = evaluate_poly(H, target_G1)
C_G1 = add(Cw_G1, HT_G1)
print(f"[A]G1 = {normalize(A_G1)}")
print(f"[B]G2 = {normalize(B_G2)}")
print(f"[C]G1 = {normalize(C_G1)}")
Geração de prova:
[A]G1 = (19092006581455788758709004813424108450475230671546198110182704126760952021248, 18428185916649502171614192229986655674799279684527591370328182794110727996633)
[B]G2 = ((1110332524507442648511549408896049077062269578877062826069065960274388112308, 15815785354885964222010325771656100864105333417560377595802485750386873282739), (20784382045877636010618629654573620888044404319093695781168988411617616204166, 5234804291052944426941184034424257962428641145809086397589880058685491457835))
[C]G1 = (21755526246297599392782387322262927251662305599666002632514868138515690603377, 19883332083442129478217826420060112230198011363938980948134718366700920887106)
Verificador:
print("\nProof verification:")
print("-"*10)
# e(A, B) == e(C, G2[1])
assert pairing(B_G2, A_G1) == pairing(G2, C_G1), "Falha na verificação de emparelhamento!"
print("Verificação de emparelhamento aprovada!")
Agora temos nosso programa de prova inicial. Para enfatizar novamente, esta configuração ainda não é segura. Como Alice apresenta apenas três pontos na curva elíptica, não há nada que confirme que algum cálculo real ocorreu. No artigo subsequente, apresentaremos parâmetros adicionais para transformar isso em uma prova genuína.
Nos bastidores do protocolo zkSNARK Groth16 (parte 5)
Ao longo deste artigo, encobri muitos detalhes sobre criptografia e curvas elípticas. No entanto, se você estiver intrigado com os princípios e raciocínios subjacentes, encorajo você a participar do zk-bootcamp hospedado por rareskills.io.
Referências:
- https://www.rareskills.io/post/elliptic-curve-qap
- https://www.rareskills.io/post/elliptic-curve-addition
- https://www.rareskills.io/post/closed-elliptic-curves
- https://vitalik.ca/general/2017/01/14/exploring_ecp.html
- https://github.com/tarassh/zkSNARK-under-the-hood/blob/main/groth16.ipynb
Este artigo foi escrito por Crypto Fairy e traduzido por Diogo Jorge. O artigo original pode ser encontrado aqui.
Oldest comments (0)