Nos bastidores do protocolo zkSNARK Groth16 (parte 2)

No artigo anterior, cobrimos brevemente os dois primeiros componentes do protocolo SNARK: o código e os circuitos algébricos. Neste artigo, vamos nos concentrar na construção de nosso R1CS (Rank One Constraint System) (Sistema de Restrição Rank One).

Bastidores do protocolo zkSNARK Groth16

Antes de me aprofundar no R1CS, devo apresentar dois assuntos fundamentais da matemática:

1. Vetores e matrizes da álgebra linear.
2. Campos de Galois (GF ou campos finitos) da Álgebra Abstrata.

(A*w)*(B*w)=(C*w)

Usamos matrizes e vetores para codificar nosso circuito algébrico. O vetor contém valores para todas as variáveis ​​que identificamos anteriormente, enquanto a matriz contém as constantes. Simplificando, o vetor serve como meio de armazenar e codificar dados, e a matriz codifica a transformação de dados. Quando uma matriz multiplica um vetor, ocorre a transformação dos dados.

A teoria de Galois de campos finitos é uma área especializada dentro da álgebra abstrata. Para aqueles interessados ​​em se aprofundar na álgebra abstrata, fornecerei referências no final deste artigo. Simplificando, os campos finitos envolvem um conjunto de regras aplicadas a determinados grupos de números. Estas regras abrangem aritmética modular, operações específicas para campos específicos e outras definições relacionadas. Compreender os corpos finitos é crucial porque toda a aritmética subsequente discutida aqui será realizada dentro de um corpo finito, especificamente em GF(p):

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

O valor p é um número primo, então o conjunto sob consideração compreende inteiros variando de 0 a p−1. Esta escolha específica é fundamental por causa da Curva Elíptica conhecida como BN-128, que empregaremos posteriormente para criptografia. Notavelmente, dentro da estrutura da blockchain Ethereum, BN-128 e secp256k1 são as únicas curvas elípticas suportadas.

R1CS

Como fazemos a transição das restrições para a forma matricial e vetorial conforme ilustrado acima?

Primeiro, devemos codificar nossas variáveis ​​em um vetor, w, comumente referido como “vetor testemunha”. Este vetor abrangerá:

• Valores de entrada, nomeadamente x e y,
• Valores calculados, como _v_1, _v_2,…_v_4,
• A saída resultante, out.

A constante 1 teria que ser usada caso a equação original contivesse um termo adicional (ou seja, + 5).

As matrizes servem como codificações para gatilhos ou interruptores, ativando cálculos para variáveis ​​específicas, como v1 para v4 e out. Considere o primeiro cálculo:

Este cálculo é caracterizado por:

• O operando esquerdo, destacado em vermelho,
• O operando direito, destacado em azul, e
• A saída, destacada em verde.

Cada um desses elementos deve ser codificado em três matrizes distintas: L para o operando esquerdo, R para o operando certo, e O para a saída.

v1=x*x — destacado

Observação: A primeira linha de cada matriz serve como guia para indicar qual coluna corresponde a qual parâmetro. Não faz parte da matriz em si.

Você pode interpretar as matrizes da seguinte maneira:

• Para calcular v1, useusar x como parâmetros esquerdo e direito.
• Para derivar v3, pegue x multiplicado por 5 como o parâmetro esquerdo e v1​ como o parâmetro correto.

Como você pode observar, os coeficientes atuam como transformadores do valor de entrada para cada cálculo específico.

Você pode ficar confuso com a presença de valores negativos, especialmente porque mencionamos anteriormente que os cálculos ocorreriam em um campo de Galois GF(p) onde os números estão confinados ao intervalo entre 0 e p−1. Em GF(p), um número negativo, digamos n, é representado como p-n.

Finalmente, se multiplicarmos cada matriz pelo vetor testemunha obteremos o seguinte:

Onde Lw, Rw, e Ow são vetores. A multiplicação elemento a elemento de Lw e Rw deveria gerar Ow. Se esta igualdade for verdadeira, ela confirma a correção do nosso R1CS definido pelas matrizes L, R, O e vetor w.

Vamos nos aprofundar na parte de codificação. Alternativamente, você também pode encontrar este código no GitHub:

import galois
import numpy as np

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617
FP = galois.GF(p)

# input arguments
x = FP(2)
y = FP(3)

v1 = x * x
v2 = y * y
v3 = 5 * x * v1
v4 = 4 * v1 * v2
out = 5*x**3 - 4*x**2*y**2 + 13*x*y**2 + x**2 - 10*y

w = FP([1, out, x, y, v1, v2, v3, v4])

print("w =", w)

R = FP([[0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 1, 0, 0, 0, 0],
        [0, 0, 5, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 4, 0, 0, 0],
        [0, 0, 13, 0, 0, 0, 0, 0]])

L = FP([[0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 1, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0],
        [0, 0, 0, 0, 0, 1, 0, 0],
        [0, 0, 0, 0, 0, 1, 0, 0]])

O = FP([[0, 0, 0, 0, 1, 0, 0, 0],
        [0, 0, 0, 0, 0, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 1],
        [0, 1, 0, 10, FP(p - 1), 0, FP(p - 1), 1]])

Lw = np.dot(L, w)
Rw = np.dot(R, w)
Ow = np.dot(O, w)

print("Lw =", Lw)
print("Rw =", Rw)

LwRw = np.multiply(Lw, Rw)

print("Lw * Rw =", LwRw)

print("Ow =     ", Ow)

assert np.all(LwRw == Ow)

w = [  1 104   2   3   4   9  40 144]
Lw = [2 3 4 9 9]
Rw = [ 2  3 10 16 26]
Lw * Rw = [  4   9  40 144 234]
Ow =      [  4   9  40 144 234]

Em resumo, R1CS fornece um formato para representar nosso programa inicial e avaliar todas as suas etapas intermediárias. Isso é fundamental na construção de um QAP, que discutirei em um artigo subsequente.

Parte 3:

Nos bastidores do protocolo zkSNARK Groth16 (parte 3)

Há uma amplitude considerável de informações, especialmente conceitos matemáticos, que apresentarei neste e nos próximos artigos. Algumas delas podem parecer aleatórias ou aparecer sem explicações abrangentes, especialmente quando se discute a construção de provas de conhecimento zero. Para aqueles que realmente investem na compreensão desses princípios básicos, recomendo o o zk-bootcamp por rareskills.io. Certifique-se de usar o código TARAS23 para obter desconto. Sem este curso, eu teria passado consideravelmente mais tempo lutando com esses fundamentos essenciais.

Referências

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