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:
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:
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.
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}
''')
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]]
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
É 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
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:
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
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:
Algumas transformações da matemática escolar e teremos uma fórmula para calcular H(x).
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
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
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:
- https://www.rareskills.io/zk-bootcamp
- https://www.rareskills.io/post/rank-1-constraint-system
- https://www.rareskills.io/post/rings-and-fields
- https://risencrypto.github.io/R1CSQAP/
- https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
- 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.
Top comments (0)