GLV falso: você não precisa de um endomorfismo eficiente para implementar multiplicação escalar semelhante ao GLV em circuitos SNARK – zk-s(nt)arks

O uso das propriedades SNARK (sucinta) fornece uma ótima maneira de reduzir o custo do gás para computação no Ethereum (por exemplo, ~232k de gás para Groth16, ~285k de gás para PLONK e ~185k de gás para FFLONK). Isso é muito competitivo (e às vezes melhor) com o verificador de contrato inteligente atualmente ideal para gás. Além disso, é possível agrupar muitas verificações ECDSA numa única prova, amortizando assim o custo do gás. No entanto, a verificação de assinaturas P-256 em um circuito SNARK pode ser muito cara, ou seja, um longo tempo de prova. Isso ocorre porque o campo onde se encontram os pontos da curva P-256 é diferente do campo onde o cálculo do SNARK é normalmente expresso. Para poder verificar a prova onchain através da procompilação, o campo SNARK precisa ser o campo escalar BN254. Diferentes equipes tentaram implementar a verificação ECDSA no P-256 em um circuito BN254 SNARK de forma eficiente. Entre estes: zkwebauthn/webauthn-halo2, https://github.com/zkwebauthn/webauthn-circom e PSE/circom-ecdsa-p256.

Se o P-256 tivesse um endomorfismo eficiente poderíamos ter otimizado bastante o tempo de prova!

Nesta nota mostramos uma maneira de implementar um circuito de multiplicações escalares do tipo GLV sem ter um endomorfismo eficiente.

Outras aplicações

Fundo

Multiplicação escalar padrão

Deixar E ser uma curva elíptica definida sobre o campo principal \mathbb{F}_p e deixe R ser um divisor principal da ordem da curva \#E(\mathbb{F}_p) (ou seja, o número de pontos).
Deixar s \in \mathbb{F}_r e P(x,y) em E(\mathbb{F}_p)estamos interessados ​​em provar a multiplicação escalar s\cponto P sobre o R-subgrupo de torção de Edenotado E(r) (ou seja, o subconjunto de pontos de ordem R).

O algoritmo mais simples é o padrão da esquerda para a direita dobrar e adicionar:

INPUT: s = (s_{t−1},..., s_1, s_0), P ∈ E(Fp).
OUTPUT: sP.
1. Q ← ∞.
2. For i from t−1 downto 0 do
    2.1 Q ← 2Q.
    2.2 If s_i = 1 then Q ← Q + P.
3. Return(Q).

A ramificação if/else não é possível em circuitos SNARK, então ela é substituída por pesquisas constantes na tabela de janelas dentro do circuito. Isto pode ser conseguido usando polinômios que desaparecem nas constantes que não estão sendo selecionadas, ou seja, uma pesquisa de tabela de 1 bit Q ← s_i * Q + (1 - s_i) * (Q+P). Portanto, este algoritmo de dobrar e adicionar requer t duplicações, t adições e t Pesquisa de tabela de 1 bit.
Isto pode ser estendido para janela double-and-add, ou seja, varrendo mais de um bit por iteração usando tabelas de janelas maiores, mas a profundidade multiplicativa da avaliação aumenta exponencialmente. Usamos coordenadas afins para duplicar/adicionar pontos porque os inversos custam tanto quanto as multiplicações, ou seja, em vez de verificar isso 1/x é sim nós fornecemos sim desligue o circuito e verifique no circuito se x\cponto y = 1. No entanto, desde que começamos com Q ← ∞ é inviável evitar a ramificação condicional, uma vez que as fórmulas afins são incompletas. Em vez disso, varremos os bits da direita para a esquerda e assumimos que o primeiro bit s_0 é 1 (então começamos em Q ← P), dobramos o ponto de entrada P em vez do acumulador Q neste algoritmo e finalmente subtrair condicionalmente (usando a pesquisa de 1 bit) P se s_0 era 0.

INPUT: s = (s_{t−1},..., s_1, s_0), P ∈ E(Fp).
OUTPUT: sP.
1. Q ← P.
2. For i from 1 to t−1 do
    2.1 If s_i = 1 then Q ← Q + P.
    2.2 P ← 2P.
3. if s_0 = 0 then Q ← Q - P
4. Return(Q).

Multiplicação escalar GLV

Porém é bem sabido que se a curva estiver equipada com um endomorfismo eficiente então existe um algoritmo mais rápido conhecido como (GLV).

Exemplo 1: suponha que E tem Multiplicação Complexa (CM) com discriminante -D=-3ou seja E é da forma y^2=x^3+bcom b\in\mathbb{F}_p. Este é o caso BN254, BLS12-381 e secp256k1 curvas elípticas usadas no Ethereum. Existe um endomorfismo eficiente \phi: E \rightarrow E definido por (x,y)\mapasto (\omega x,y) (e \mathcal{O} \mapsto \mathcal{O}) que atua sobre P \in E(r) como \phi(P)=\lambda \cdot P. Ambos \ómega e \lambda são raízes cúbicas da unidade em \mathbb{F}_p e \mathbb{F}_r respectivamente, ou seja \omega^2+\omega+1 \equiv 0 \pmod p e \lambda^2+\lambda+1 \equiv 0 \pmod r.

Exemplo 2: suponha que E tem Multiplicação Complexa (CM) com discriminante -D=-8o que significa que o anel de endomorfismo é \mathbf{Z}(\sqrt{−2}). Este é o caso do Bandersnatch curvas elípticas especificadas no teste Ethereum Verkle. Existe um endomorfismo eficiente \phi: E \rightarrow E cujo núcleo é gerado por um ponto de 2 torções. O mapa pode ser encontrado observando curvas 2 isógenas e aplicando as fórmulas de Vélu. Para Bandersnatch é definido por (x,y)\mapsto (u^2\cdot \frac{x^2+wx+t}{x+w},u^3\cdot y\cdot \frac{x^2+2wx+v}{(x+w)^2}) para algumas constantes você, v, w, t (e \mathcal{O} \mapsto \mathcal{O}) que atua sobre P \in E(r) como \phi(P)=\lambda \cdot P onde \lambda^2+2 \equiv 0 \pmod r.

O algoritmo GLV começa decompondo é como s = s_0 + \lambda s_1 e então substituindo a multiplicação escalar s \cdot P por s_0 \cdot P + s_1 \cdot \phi(P). Porque s_0 e s_1 são garantidos para serem \leq \sqrt{r} (veja a Seção 4 de (GLV) e a Seção 4 de (FourQ) para um truque de otimização), podemos reduzir pela metade o tamanho do loop for no algoritmo double-and-add. Podemos então escanear simultaneamente os bits de s_0 e s_1 e aplique o truque de Strauss-Shamir. Isso resulta em uma aceleração significativa, mas apenas quando um endomorfismo está disponível. Por exemplo, dobrar e adicionar da esquerda para a direita se tornaria:

INPUT: s and P ∈ E(Fp).
OUTPUT: sP.
1. Find s1 and s2 s.t. s = s1 + 𝜆 * s2 mod r 
    1.1 let s1 = (s1_{t−1},..., s1_1, s1_0) 
    1.2 and s2 = = (s2_{t−1},..., s2_1, s2_0)
2. P1 ← P, P2 ← 𝜙(P) and Q ← ∞.
3. For i from t−1 downto 0 do
    3.1 Q ← 2Q.
    3.2 If s1_i = 0 and s2_i = 0 then Q ← Q.
    3.3 If s1_i = 1 and s2_i = 0 then Q ← Q + P1.
    3.4 If s1_i = 0 and s2_i = 1 then Q ← Q + P2.
    3.5 If s1_i = 1 and s2_i = 1 then Q ← Q + P1 + P2.
4. Return(Q).

Usar o endomorfismo eficiente no circuito também é possível (ver (Halo, Seção 6.2 e Apêndice C) ou (implementação gnark) para curvas de Weierstrass curtas e implementações (arkworks) e (gnark) para Edwards torcidos). Mas deve-se ter cuidado com algumas verificações extras da decomposição s = s_0 + \lambda s_1 \mod r (não o módulo SNARK). Os inteiros s_0, s_1 podem ser negativos, caso em que serão reduzidos no módulo do circuito do campo SNARK e não R.

O truque do falso GLV

Lembre-se que estamos provando que s\cponto P = Q e não computá-lo. Podemos “sugerir” o resultado P e verifique no circuito se s\cdot P – Q = \mathcal{O}. Agora, se pudermos encontrar você,v \leq \sqrt{r} tal que v\cdot s = você \pmod r então podemos verificar se

(v\cdot s)\cdot P – v\cdot Q = \mathcal{O}

o que equivale a

você\cdot P – v\cdot Q = \mathcal{O}

A coisa agora é que você e v são “pequenos” e podemos, de forma semelhante ao algoritmo GLV, reduzir pela metade o tamanho do loop duplo e adicionar e aplicar o truque de Strauss-Shamir.

Solução: executar o algoritmo meio-GCD (ou seja, executar o GCD pela metade) é suficiente para encontrar você e v. Podemos aplicar exatamente o mesmo truque para encontrar a base da rede do artigo GLV (Seção 4). Para completar, relembraremos o algoritmo a seguir.
Aplicamos o algoritmo euclidiano estendido para encontrar o máximo divisor comum de R e é (Este mdc é 1, pois R é primo.) O algoritmo produz uma sequência de equações

w_i \cdot r + v_i \cdot s = u_i

para eu = 0, 1, 2, \pontos onde w_0 = 1, v_0 = 0, u_0 = r, w_1 = 0, v_1 ​​= 1, u_1 = se você_i \geq 0 para todos eu. Paramos no índice eu para o qual você_m \geq \sqrt{r} e pegue você = você_{m+1} e v = -v_{m+1}.
Observação: Por construção você é garantido que é um número inteiro positivo, mas v pode ser negativo, caso em que seria reduzido no módulo do circuito o módulo SNARK e não R. Para contornar isso voltamos na dica você, v e um \texttt{b}=1 se v é negativo e \texttt{b}=0 de outra forma. No circuito nós negamos P em vez disso, quando \texttt{b}=1.

Implementação

Uma implementação genérica na biblioteca gnark está disponível em gnark.io (ramo feat/fake-GLV). Para Short Weierstrass (por exemplo, P256), veja o scalarMulFakeGLV método no pacote emulado e para Edwards distorcidos (por exemplo, Bandersnatch/Jubjub) veja o scalarMulFakeGLV método no pacote nativo.

Referência

O melhor algoritmo para implementar multiplicação escalar em um circuito não nativo (ou seja, campo de circuito ≠ campo de curva) quando um endomorfismo eficiente é não disponível é uma adaptação de (Joye07) (implementado no gnark aqui).
Em seguida, comparamos esta multiplicação escalar com nosso GLV falso em um circuito PLONKish vanilla (ou seja, sem portas personalizadas) (scs) sobre a curva BN254 (compatível com Ethereum). Também fornecemos benchmarks em R1CS.

Observe aqui que a antiga verificação ECDSA usa o truque de Strauss-Shamir para computação (s)P+

Comparação

p256wallet.org é uma carteira de contrato inteligente ERC-4337 que utiliza zk-SNARKs para verificação de assinatura WebAuthn e P-256. Ele usa PSE/circom-ecdsa-p256 para gerar a prova webAuthn e abaixo de PSE/circom-ecdsa-p256 para gerar a prova ECDSA na curva P-256. Os relatórios README do github 1,972,905 R1CS. Compilar nosso circuito em R1CS resulta em 195,266 R1CS. Isto é mais do que um 10x redução, que não se deve apenas ao algoritmo GLV falso, mas também à aritmética de campo não nativa otimizada no gnark.

Outras curvas

Resultados semelhantes são observados para outras curvas em Weirstrass curto, por exemplo, curva P-384 e STARK:

e também em Edwards distorcido, por exemplo, Jubjub vs. Bandersnatch:

EDIT: Obrigado a Ben Smith por relatar que uma ideia semelhante foi proposta em (SAC05:ABGL+) para verificação ECDSA. Notamos que, no nosso contexto, o truque se aplica a uma única multiplicação escalar e que o meio GCD é livre através da dica.

Reconhecimento

Gostaria de agradecer a Arnau Cube, Aard Vark, Holden Mui, Olivier Bégassat, Thomas Piellard e Ben Smith pelas discussões frutíferas.