WEB3DEV

Cover image for Nos bastidores do protocolo zkSNARK Groth16 (parte 3)
Diogo Jorge
Diogo Jorge

Posted on

Nos bastidores do protocolo zkSNARK Groth16 (parte 3)

Neste artigo abordarei como converter R1CS criado na parte 2 em QAP.

Nos bastidores do protocolo zkSNARK Groth16 (parte 2)

Lembrete: Tudo nesta série é suportado pelo código funcional publicado em GitHub. O código não está pronto para produção, mas serve mais como uma demonstração tangível de que a matemática subjacente é funcional.

Como resultado do R1CS, obtemos três matrizes: L, R, e O, bem como um vetor testemunha w. Esses elementos são incorporados à equação Lw×Rw=Ow. Esta forma de equação permanecerá consistente ao longo dos artigos subsequentes. Embora a sua forma evolua, o conceito fundamental é que o lado esquerdo, quando multiplicado pelo lado direito, produz o resultado. A avaliação de todo o nosso programa será encapsulada por esta representação.

Anteriormente, destaquei como o tamanho de um programa influencia diretamente a equação que precisamos avaliar. Correspondentemente, as dimensões das matrizes e do vetor testemunha também se expandem. Mas considere trabalhar com matrizes de dimensões 1000x1000 – lidar com estruturas tão extensas representa desafios. Alguns leitores podem sugerir rapidamente que as GPUs, sendo adequadas para multiplicação de matrizes, lidariam facilmente com isso. Porém, no primeiro artigo, enfatizei a importância do zkSNARK de manter um tempo de verificador constante ou próximo dele - representado como O(1).

Avaliando Lw×Rw=Ow por verificadores não é inerentemente O(1), pois depende do tamanho do programa. Além disso, a introdução da criptografia no mix desacelera ainda mais a execução. Portanto, precisamos de uma representação mais concisa do que R1CS, e é aqui que entra o QAP. Mas antes de nos aprofundarmos no QAP, há alguns conceitos matemáticos que preciso mencionar:

Image description

Polinômio de grau n

  • Polinômios: Não há muito o que aprofundar aqui. Você provavelmente estudou isso na escola.
  • Homomorfismo: Vamos simplificar este conceito. Na Álgebra Abstrata, estudamos números, categorizamos e depois organizamos em grupos com base em regras específicas – isto é conhecido como Teoria dos Grupos. Na Teoria dos Grupos, também exploramos as relações entre esses grupos. Em sua essência, um homomorfismo é um mapeamento entre dois grupos que preserva suas estruturas inerentes. Pense nisso como uma ponte que nos permite relacionar as operações de um grupo com outro. Curiosamente, o espaço vetorial onde reside R1CS e o espaço dos polinômios podem ser considerados como dois desses grupos, e existe um homomorfismo entre eles. Para quem quer se aprofundar, é importante notar que tanto os vetores quanto os polinômios pertencem tecnicamente à categoria de “Anéis”. Fornecerei um link no final deste artigo para os curiosos saberem mais.

QAP

Portanto, nosso novo objetivo é passar do campo vetorial para o campo polinomial:

Image description

l(x),r(x) e o(x) são polinômios

Existe uma relação de preservação de estrutura entre R1CS e QAP, facilitada por um homomorfismo. Mas isso significa que a avaliação do verificador não dependerá do tamanho do programa? O lema de Schwartz-Zippel fornece informações sobre isso. Segundo ele, ao avaliar dois polinômios (considerando que L(x)×R(x) produz um novo polinômio, digamos k(x)), usando um valor aleatório τ (tau), se os resultados forem iguais, então com uma probabilidade muito alta, os dois polinômios são idênticos. Isto implica que toda a avaliação pode ser condensada num único ponto.

Coeficientes é o que precisamos dos polinômios. Considere cada coluna nas matrizes L, R, e O como representando um conjunto de coordenadas y para um polinômio específico.

Image description

Selecionaremos 5 coordenadas x, por exemplo, variando de 1 a 5. Isso nos dá o seguinte conjunto de pontos: (1, 1), (2, 0), (3, 5), (4, 0), e(5, 13). Ao empregar o método de Interpolação de Lagrange, podemos determinar um polinômio correspondente aos coeficientes de cada coluna da matriz. Vamos nos aprofundar na parte de codificação:

mtxs = [L, R, O]
poly_m = []

for m in mtxs:
   poly_list = []
   for i in range(0, m.shape[1]):
       points_x = FP(np.zeros(m.shape[0], dtype=int))
       points_y = FP(np.zeros(m.shape[0], dtype=int))
       for j in range(0, m.shape[0]):
           points_x[j] = FP(j+1)
           points_y[j] = m[j][i]

       poly = galois.lagrange_poly(points_x, points_y)
       coef = poly.coefficients()[::-1]
       if len(coef) < m.shape[0]:
           coef = np.append(coef, np.zeros(m.shape[0] - len(coef), dtype=int))
       poly_list.append(coef)


   poly_m.append(FP(poly_list))

Lp = poly_m[0]
Rp = poly_m[1]
Op = poly_m[2]

print(f'''Lp
{Lp}
''')

print(f'''Rp
{Rp}
''')

print(f'''Op
{Op}
''')
Enter fullscreen mode Exit fullscreen mode

Os resultados da interpolação serão armazenados em formato de matriz. Além disso, como estamos trabalhando dentro de um Campo Finito caracterizado pelo número primo p=21888242871839275222246405745257275088548364400416034343698204186575808495617, os resultados tendem a parecer bastante complexos e difíceis de ler. Para fins ilustrativos, vamos usar p=71 como nosso parâmetro de campo. Com isso, nossos resultados serão muito mais compreensíveis. Entretanto, antes de visualizar esses resultados, certifique-se de que o R1CS seja executado novamente com esse parâmetro de campo atualizado.

Lp
[[ 0  0  0  0  0]
[ 0  0  0  0  0]
[ 5 35  0 29  3]
[61  6  2 14 59]
[10 16 30 68 18]
[67 14 39 31 62]
[ 0  0  0  0  0]
[ 0  0  0  0  0]]

Rp
[[ 0  0  0  0  0]
[ 0  0  0  0  0]
[68 11 24 50 61]
[61  6  2 14 59]
[51 17 20 31 23]
[ 0  0  0  0  0]
[ 0  0  0  0  0]
[ 0  0  0  0  0]]

Op
[[ 0  0  0  0  0]
[ 1 63 34 41  3]
[ 0  0  0  0  0]
[10 62 56 55 30]
[ 4 43 37 59  0]
[61  6  2 14 59]
[ 9 24 67 27 15]
[67 14 39 31 62]]
Enter fullscreen mode Exit fullscreen mode

Ainda não terminamos. A próxima etapa envolve a integração do nosso vetor testemunha w na equação. Multiplicando (ponto produto) w com essas matrizes, o vetor resultante produzirá os coeficientes para nossos polinômios.

U = galois.Poly((w @ Lp)[::-1])
V = galois.Poly((w @ Rp)[::-1])
W = galois.Poly((w @ Op)[::-1])

print("U = ", U)
print("V = ", V)
print("W = ", W)

U =  11856131555579607412050136445347690672963697383558685269503193934395229601792x^4 + 20064222632519335620392538599819168831169334033714698148390020504361157787655x^3 + 20976232752179305421319472172538221959858849217065366246044112345468483141610x^2 + 12768141675239577212977070018066743801653212566909353367157285775502554955812x + 21888242871839275222246405745257275088548364400416034343698204186575808495601
V =  10944121435919637611123202872628637544274182200208017171849102093287904247809x^4 + 3648040478639879203707734290876212514758060733402672390616367364429301415930x^3 + 10944121435919637611123202872628637544274182200208017171849102093287904247836x^2 + 18240202393199396018538671454381062573790303667013361953081836822146507079635x + 26
W =  12768141675239577212977070018066743801653212566909353367157285775502554955771x^4 + 7296080957279758407415468581752425029516121466805344781232734728858602831936x^3 + 9120101196599698009269335727190531286895151833506680976540918411073253539611x^2 + 14592161914559516814830937163504850059032242933610689562465469457717205664076x + 21888242871839275222246405745257275088548364400416034343698204186575808495461
Enter fullscreen mode Exit fullscreen mode

É fascinante como conseguimos reduzir as três matrizes R1CS a três polinômios, cada um de grau 4. Neste ponto, você pode presumir que terminamos. No entanto, há uma reviravolta. Se aplicarmos o lema de Schwartz-Zippel e escolhermos um valor aleatório τ (tau) para avaliar a nossa equação, descobriremos que a equação não é satisfeita.

número = FP(20)

tau = FP(20)

assert U(tau)*V(tau) == W(tau) # vai falhar
Enter fullscreen mode Exit fullscreen mode

O desequilíbrio surge porque, após a multiplicação de U e V, a nossa equação fica distorcida. O lado esquerdo agora tem um polinômio de grau 8. Isso significa que precisamos ajustar o lado direito determinando polinômios adicionais. Nosso primeiro passo é identificar T(x), comumente referido como o polinômio alvo. Este polinômio deve retornar um valor 0 para as coordenadas x 1, 2, 3, 4 e 5. Para derivar tal polinômio, podemos empregar a seguinte equação:

Image description

Polinômio alvo.

Vamos codificar isso:

tau = FP(20)

print(f"τ = {tau}")

T = galois.Poly([1, p-1], field=FP)
for i in range(2, L.shape[0] + 1):
   T *= galois.Poly([1, p-i], field=FP)

print("\nT = ", T)
for i in range(1, L.shape[0] + 2):
   print(f"T({i}) = ", T(i))
   if i == L.shape[0]:
       print("-"*10)

T_tau = T(tau)
print(f"\nT(τ) = {T_tau}")

τ = 20

T =  x^5 + 21888242871839275222246405745257275088548364400416034343698204186575808495602x^4 + 85x^3 + 21888242871839275222246405745257275088548364400416034343698204186575808495392x^2 + 274x + 21888242871839275222246405745257275088548364400416034343698204186575808495497
T(1) =  0
T(2) =  0
T(3) =  0
T(4) =  0
T(5) =  0
----------
T(6) =  120 # Apenas confirmando que nós construímos o polinômio certo. 

T(τ) = 1395360
Enter fullscreen mode Exit fullscreen mode

Primeiro polinômio,T(x),foi deduzido com base em parâmetros conhecidos, agora precisamos encontrar o polinômio restante -H(x). Nossa equação agora fica assim:

Image description

Algumas transformações da matemática escolar e teremos uma fórmula para calcular H(x).

Image description

H(x)

H = (U * V - W) // T
rem = (U * V - W) % T

print("H = ", H)
print("rem = ", rem)

assert rem == 0

H = 5928065777789803706025068222673845336481848691779342634751596967197614800896x^3 + 1489616528777950674847324835441120110192 8747994727578928350166738086314115075x^2 + 1672018552709944635032711549984930735930777836142891512365835042030096482298x + 1824 0202393199396018538671454381062573790303667013361953081836822146507079683
rem = 0
Enter fullscreen mode Exit fullscreen mode

Após a divisão, o resto deve ser 0. Caso contrário, isso indica um erro computacional em algum lugar ao longo do caminho.

Verificação final para ver se a nova equação é válida com polinômios descobertos:

u = U(tau)
v = V(tau)
_w = W(tau) # desculpe, w foi levado 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
Enter fullscreen mode Exit fullscreen mode

Com sucesso, resumimos R1CS em cinco polinômios, que representam a forma pura de QAP. Esses polinômios servirão de base para o próximo capítulo.

Referências:

  1. https://www.rareskills.io/zk-bootcamp
  2. https://www.rareskills.io/post/rank-1-constraint-system
  3. https://www.rareskills.io/post/rings-and-fields
  4. https://risencrypto.github.io/R1CSQAP/
  5. https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
  6. 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)