Este artigo analisa o algoritmo MSM, algoritmo de adição de ponto de curva elíptica, algoritmo de multiplicação de Montgomery, etc. em detalhes, e compara a diferença de desempenho entre GPU e FPGA na adição de ponto de curva BLS12_381.
Escrito por: Star Li
A tecnologia de prova de conhecimento zero é cada vez mais amplamente utilizada, como prova de privacidade, prova de cálculo, prova de consenso e assim por diante. Enquanto procuram mais e melhores cenários de aplicação, muitas pessoas descobriram gradualmente que a prova de conhecimento zero prova que o desempenho é um gargalo. A equipe Trapdoor Tech tem pesquisado profundamente a tecnologia de prova de conhecimento zero desde 2019 e tem explorado soluções eficientes de aceleração de prova de conhecimento zero. GPU ou FPGA são plataformas de aceleração relativamente comuns atualmente no mercado. Este artigo começa com o cálculo do MSM e analisa as vantagens e desvantagens do cálculo de prova de conhecimento zero acelerado por FPGA e GPU.
##TL;DR
ZKP é uma tecnologia com amplas perspectivas para o futuro. Mais e mais aplicativos estão adotando a tecnologia de prova de conhecimento zero. No entanto, existem muitos algoritmos ZKP e vários projetos usam diferentes algoritmos ZKP. Ao mesmo tempo, o desempenho computacional da prova ZKP é relativamente ruim. Este artigo analisa o algoritmo MSM, algoritmo de adição de ponto de curva elíptica, algoritmo de multiplicação de Montgomery, etc. em detalhes, e compara a diferença de desempenho entre GPU e FPGA na adição de ponto de curva BLS12_381. Em geral, em termos de computação de prova ZKP, a GPU de curto prazo tem vantagens óbvias, alto rendimento, desempenho de alto custo, programabilidade e assim por diante. Relativamente falando, o FPGA tem certas vantagens no consumo de energia. A longo prazo, pode haver chips FPGA adequados para cálculos de ZKP ou chips ASIC personalizados para ZKP.
Complexo de algoritmo ZKP
ZKP é um termo geral para a tecnologia Zero Knowledge Proof (Zero Knowledge Proof). Existem principalmente duas classificações: zk-SNARK e zk-STARK. Os algoritmos comuns atuais do zk-SNARK são Groth16, PLONK, PLOOKUP, Marlin e Halo/Halo2. A iteração do algoritmo zk-SNARK ocorre principalmente em duas direções: 1/se uma configuração confiável é necessária 2/o desempenho da estrutura do circuito. A vantagem do algoritmo zk-STARK é que nenhuma configuração confiável é necessária, mas a quantidade de cálculo de verificação é log-linear.
No que diz respeito à aplicação do algoritmo zk-SNARK/zk-STARK, os algoritmos de prova de conhecimento zero usados por diferentes projetos são relativamente dispersos. Na aplicação do algoritmo zk-SNARK, como o algoritmo PLONK/Halo2 é universal (sem necessidade de configuração confiável), pode haver mais e mais aplicações.
PLONK prova a quantidade de computação
Tomando o algoritmo PLONK como exemplo, analise o valor do cálculo da prova PLONK.
O valor de cálculo da parte de prova PLONK consiste em quatro partes:
1/ MSM - Multiplicação Escalar Múltipla. O MSM é frequentemente usado para calcular compromissos polinomiais.
2/ Computação NTT - Conversão polinomial entre valor de ponto e representação de coeficiente.
3/ Cálculo polinomial - adição polinomial, subtração, multiplicação e divisão. Avaliação polinomial (uation) e assim por diante.
4/ Circuit Synthesize - síntese de circuitos. O cálculo desta parte está relacionado com a escala/complexidade do circuito.
De um modo geral, a quantidade de cálculo na parte Circuit Synthesize é mais julgamento e lógica de loop, e o grau de paralelismo é relativamente baixo, o que é mais adequado para o cálculo da CPU. De um modo geral, a aceleração de prova de conhecimento zero geralmente se refere à aceleração de cálculo das três primeiras partes. Dentre eles, o valor de cálculo do MSM é relativamente o maior, seguido pelo NTT.
O que é MSM
MSM (Multiple Scalar Multiplication) refere-se a uma determinada série de pontos e escalares na curva elíptica e calcula os pontos correspondentes aos resultados da adição desses pontos.
Por exemplo, dada uma série de pontos em uma curva elíptica:
Dado um conjunto fixo de pontos de curva elíptica de uma curva especificada:
[G_1, G_2, G_3, ..., G_n]
e coeficientes aleatórios:
e elementos de campo finito amostrados aleatoriamente do campo escalar especificado:
[s_1, s_2, s_3, ..., s_n]
MSM é o cálculo para obter o ponto Q da curva elíptica:
Q = \soma_{i=1}^{n}s_i*G_i
A indústria geralmente adota o algoritmo Pippenger para otimizar o cálculo MSM. Dê uma olhada no diagrama esquemático do processo do algoritmo de Pippenger:
O processo de cálculo do algoritmo Pippenger é dividido em duas etapas:
1/ Divisão escalar em Windows. Se o escalar for de 256 bits e uma janela for de 8 bits, todos os escalares serão divididos em 256/8 = 32 janelas. Cada camada do Window usa um "Balde" para armazenar temporariamente os resultados intermediários. GW_x é o resultado do ponto de acumulação em uma camada. Calcular GW_x também é relativamente simples. Ele percorre cada escalar em uma camada por vez e usa o valor da camada escalar como índice e adiciona o G_x correspondente aos baldes correspondentes. Na verdade, o princípio é relativamente simples: se os coeficientes da soma de dois pontos forem iguais, some primeiro os dois pontos e depois some o escalar novamente, em vez de somar os dois pontos duas vezes antes de somar o escalar.
2/ Os pontos calculados por cada janela são acumulados por dupla soma para obter o resultado final.
O algoritmo de Pippenger também possui muitos algoritmos de otimização de deformação. Em qualquer caso, o cálculo subjacente do algoritmo MSM é a adição de pontos na curva elíptica. Diferentes algoritmos de otimização correspondem a diferentes números de pontos adicionados.
Adição de ponto de curva elíptica (Adição de ponto)
Você pode ver vários algoritmos para adição de pontos em curvas elípticas com o formulário "Weierstrass curto" neste site.
Assumindo que as coordenadas projetivas dos dois pontos são (x1, y1, z1) e (x2, y2, z2) respectivamente, o resultado da adição de pontos (x3, y3, z3) pode ser calculado pela seguinte fórmula de cálculo.
A razão para fornecer o processo de cálculo em detalhes é mostrar que todo o processo de cálculo é principalmente operações inteiras. A largura de bits do inteiro depende dos parâmetros da curva elíptica. Forneça as larguras de bits de algumas curvas elípticas comuns:
BN256 - 256 bits
BLS12_381 - 381 bits
BLS12_377 - 377 bits
Atenção especial é que essas operações inteiras são operações no campo módulo. Adição modular/subtração de módulo é relativamente simples, foco no princípio e implementação da multiplicação modular.
模乘（Modular Multiplication）
Dados dois valores sobre um campo módulo: x e y. O cálculo da multiplicação modular refere-se a x*y mod p. Observe que a largura de bits desses inteiros é a largura de bits da curva elíptica. O algoritmo clássico da multiplicação modular é a multiplicação de Montgomery (MontgomeryMulplication). Antes de realizar a multiplicação de Montgomery, o multiplicando precisa ser convertido para a representação de Montgomery:
A fórmula para calcular a multiplicação de Montgomery é a seguinte:
Existem muitos algoritmos de implementação de multiplicação de Montgomery: CIOS (varredura de operando integrado), FIOS (varredura de operando integrado), FIPS (varredura de produto integrado) e assim por diante. Este artigo não apresenta os detalhes de várias implementações de algoritmo em profundidade, e os leitores interessados podem fazer suas próprias pesquisas.
Para comparar a diferença de desempenho entre FPGA e GPU, escolha o método de implementação de algoritmo mais básico:
Simplificando, o algoritmo de multiplicação modular pode ser dividido em dois cálculos: multiplicação de grandes números e adição de grandes números. Depois de entender a lógica de cálculo do MSM, você pode escolher o desempenho da multiplicação modular (Throughput) para comparar o desempenho do FPGA e GPU.
Observe e pense
Sob tal projeto FPGA, pode-se estimar que todo o VU9P pode fornecer a taxa de transferência em BLS12_381 pontos de curva elíptica. Uma adição de ponto (forma add_mix) requer cerca de 12 multiplicações modulares. O clock do sistema do FPGA é de 450M.
Sob o mesmo algoritmo de multiplicação modular/adição de módulo, usando o mesmo algoritmo de adição de ponto, o ponto mais Troughput da Nvidia 3090 (considerando fatores de transmissão de dados) excede 500M/s. Claro, todo o cálculo envolve uma variedade de algoritmos, alguns algoritmos podem ser adequados para FPGA e alguns algoritmos são adequados para GPU. A razão para usar a mesma comparação de algoritmo é comparar os principais recursos de computação de FPGA e GPU.
Com base nos resultados acima, resuma a comparação entre GPU e FPGA em termos de desempenho à prova de ZKP:
Resumir
Mais e mais aplicativos estão adotando a tecnologia de prova de conhecimento zero. No entanto, existem muitos algoritmos ZKP e vários projetos usam diferentes algoritmos ZKP. De nossa experiência prática em engenharia, FPGA é uma opção, mas GPU é atualmente uma opção econômica. FPGA prefere computação determinística, que tem as vantagens de latência e consumo de energia. A GPU tem alta programabilidade, tem uma estrutura de computação de alto desempenho relativamente madura e tem um ciclo de iteração de desenvolvimento curto e prefere cenários de taxa de transferência.
Ver original
O conteúdo é apenas para referência, não uma solicitação ou oferta. Nenhum aconselhamento fiscal, de investimento ou jurídico é fornecido. Consulte a isenção de responsabilidade para obter mais informações sobre riscos.
Um artigo para entender as vantagens e desvantagens da computação de prova de conhecimento zero acelerada por FPGA e GPU
Escrito por: Star Li
A tecnologia de prova de conhecimento zero é cada vez mais amplamente utilizada, como prova de privacidade, prova de cálculo, prova de consenso e assim por diante. Enquanto procuram mais e melhores cenários de aplicação, muitas pessoas descobriram gradualmente que a prova de conhecimento zero prova que o desempenho é um gargalo. A equipe Trapdoor Tech tem pesquisado profundamente a tecnologia de prova de conhecimento zero desde 2019 e tem explorado soluções eficientes de aceleração de prova de conhecimento zero. GPU ou FPGA são plataformas de aceleração relativamente comuns atualmente no mercado. Este artigo começa com o cálculo do MSM e analisa as vantagens e desvantagens do cálculo de prova de conhecimento zero acelerado por FPGA e GPU.
##TL;DR
ZKP é uma tecnologia com amplas perspectivas para o futuro. Mais e mais aplicativos estão adotando a tecnologia de prova de conhecimento zero. No entanto, existem muitos algoritmos ZKP e vários projetos usam diferentes algoritmos ZKP. Ao mesmo tempo, o desempenho computacional da prova ZKP é relativamente ruim. Este artigo analisa o algoritmo MSM, algoritmo de adição de ponto de curva elíptica, algoritmo de multiplicação de Montgomery, etc. em detalhes, e compara a diferença de desempenho entre GPU e FPGA na adição de ponto de curva BLS12_381. Em geral, em termos de computação de prova ZKP, a GPU de curto prazo tem vantagens óbvias, alto rendimento, desempenho de alto custo, programabilidade e assim por diante. Relativamente falando, o FPGA tem certas vantagens no consumo de energia. A longo prazo, pode haver chips FPGA adequados para cálculos de ZKP ou chips ASIC personalizados para ZKP.
Complexo de algoritmo ZKP
ZKP é um termo geral para a tecnologia Zero Knowledge Proof (Zero Knowledge Proof). Existem principalmente duas classificações: zk-SNARK e zk-STARK. Os algoritmos comuns atuais do zk-SNARK são Groth16, PLONK, PLOOKUP, Marlin e Halo/Halo2. A iteração do algoritmo zk-SNARK ocorre principalmente em duas direções: 1/se uma configuração confiável é necessária 2/o desempenho da estrutura do circuito. A vantagem do algoritmo zk-STARK é que nenhuma configuração confiável é necessária, mas a quantidade de cálculo de verificação é log-linear.
No que diz respeito à aplicação do algoritmo zk-SNARK/zk-STARK, os algoritmos de prova de conhecimento zero usados por diferentes projetos são relativamente dispersos. Na aplicação do algoritmo zk-SNARK, como o algoritmo PLONK/Halo2 é universal (sem necessidade de configuração confiável), pode haver mais e mais aplicações.
PLONK prova a quantidade de computação
Tomando o algoritmo PLONK como exemplo, analise o valor do cálculo da prova PLONK.
O valor de cálculo da parte de prova PLONK consiste em quatro partes:
1/ MSM - Multiplicação Escalar Múltipla. O MSM é frequentemente usado para calcular compromissos polinomiais.
2/ Computação NTT - Conversão polinomial entre valor de ponto e representação de coeficiente.
3/ Cálculo polinomial - adição polinomial, subtração, multiplicação e divisão. Avaliação polinomial (uation) e assim por diante.
4/ Circuit Synthesize - síntese de circuitos. O cálculo desta parte está relacionado com a escala/complexidade do circuito.
De um modo geral, a quantidade de cálculo na parte Circuit Synthesize é mais julgamento e lógica de loop, e o grau de paralelismo é relativamente baixo, o que é mais adequado para o cálculo da CPU. De um modo geral, a aceleração de prova de conhecimento zero geralmente se refere à aceleração de cálculo das três primeiras partes. Dentre eles, o valor de cálculo do MSM é relativamente o maior, seguido pelo NTT.
O que é MSM
MSM (Multiple Scalar Multiplication) refere-se a uma determinada série de pontos e escalares na curva elíptica e calcula os pontos correspondentes aos resultados da adição desses pontos.
Por exemplo, dada uma série de pontos em uma curva elíptica:
Dado um conjunto fixo de pontos de curva elíptica de uma curva especificada:
[G_1, G_2, G_3, ..., G_n]
e coeficientes aleatórios:
e elementos de campo finito amostrados aleatoriamente do campo escalar especificado:
[s_1, s_2, s_3, ..., s_n]
MSM é o cálculo para obter o ponto Q da curva elíptica:
Q = \soma_{i=1}^{n}s_i*G_i
A indústria geralmente adota o algoritmo Pippenger para otimizar o cálculo MSM. Dê uma olhada no diagrama esquemático do processo do algoritmo de Pippenger:
O processo de cálculo do algoritmo Pippenger é dividido em duas etapas:
1/ Divisão escalar em Windows. Se o escalar for de 256 bits e uma janela for de 8 bits, todos os escalares serão divididos em 256/8 = 32 janelas. Cada camada do Window usa um "Balde" para armazenar temporariamente os resultados intermediários. GW_x é o resultado do ponto de acumulação em uma camada. Calcular GW_x também é relativamente simples. Ele percorre cada escalar em uma camada por vez e usa o valor da camada escalar como índice e adiciona o G_x correspondente aos baldes correspondentes. Na verdade, o princípio é relativamente simples: se os coeficientes da soma de dois pontos forem iguais, some primeiro os dois pontos e depois some o escalar novamente, em vez de somar os dois pontos duas vezes antes de somar o escalar.
2/ Os pontos calculados por cada janela são acumulados por dupla soma para obter o resultado final.
O algoritmo de Pippenger também possui muitos algoritmos de otimização de deformação. Em qualquer caso, o cálculo subjacente do algoritmo MSM é a adição de pontos na curva elíptica. Diferentes algoritmos de otimização correspondem a diferentes números de pontos adicionados.
Adição de ponto de curva elíptica (Adição de ponto)
Você pode ver vários algoritmos para adição de pontos em curvas elípticas com o formulário "Weierstrass curto" neste site.
Assumindo que as coordenadas projetivas dos dois pontos são (x1, y1, z1) e (x2, y2, z2) respectivamente, o resultado da adição de pontos (x3, y3, z3) pode ser calculado pela seguinte fórmula de cálculo.
A razão para fornecer o processo de cálculo em detalhes é mostrar que todo o processo de cálculo é principalmente operações inteiras. A largura de bits do inteiro depende dos parâmetros da curva elíptica. Forneça as larguras de bits de algumas curvas elípticas comuns:
模乘（Modular Multiplication）
Dados dois valores sobre um campo módulo: x e y. O cálculo da multiplicação modular refere-se a x*y mod p. Observe que a largura de bits desses inteiros é a largura de bits da curva elíptica. O algoritmo clássico da multiplicação modular é a multiplicação de Montgomery (MontgomeryMulplication). Antes de realizar a multiplicação de Montgomery, o multiplicando precisa ser convertido para a representação de Montgomery:
A fórmula para calcular a multiplicação de Montgomery é a seguinte:
Existem muitos algoritmos de implementação de multiplicação de Montgomery: CIOS (varredura de operando integrado), FIOS (varredura de operando integrado), FIPS (varredura de produto integrado) e assim por diante. Este artigo não apresenta os detalhes de várias implementações de algoritmo em profundidade, e os leitores interessados podem fazer suas próprias pesquisas.
Para comparar a diferença de desempenho entre FPGA e GPU, escolha o método de implementação de algoritmo mais básico:
Simplificando, o algoritmo de multiplicação modular pode ser dividido em dois cálculos: multiplicação de grandes números e adição de grandes números. Depois de entender a lógica de cálculo do MSM, você pode escolher o desempenho da multiplicação modular (Throughput) para comparar o desempenho do FPGA e GPU.
Observe e pense
Sob tal projeto FPGA, pode-se estimar que todo o VU9P pode fornecer a taxa de transferência em BLS12_381 pontos de curva elíptica. Uma adição de ponto (forma add_mix) requer cerca de 12 multiplicações modulares. O clock do sistema do FPGA é de 450M.
Sob o mesmo algoritmo de multiplicação modular/adição de módulo, usando o mesmo algoritmo de adição de ponto, o ponto mais Troughput da Nvidia 3090 (considerando fatores de transmissão de dados) excede 500M/s. Claro, todo o cálculo envolve uma variedade de algoritmos, alguns algoritmos podem ser adequados para FPGA e alguns algoritmos são adequados para GPU. A razão para usar a mesma comparação de algoritmo é comparar os principais recursos de computação de FPGA e GPU.
Com base nos resultados acima, resuma a comparação entre GPU e FPGA em termos de desempenho à prova de ZKP:
Resumir
Mais e mais aplicativos estão adotando a tecnologia de prova de conhecimento zero. No entanto, existem muitos algoritmos ZKP e vários projetos usam diferentes algoritmos ZKP. De nossa experiência prática em engenharia, FPGA é uma opção, mas GPU é atualmente uma opção econômica. FPGA prefere computação determinística, que tem as vantagens de latência e consumo de energia. A GPU tem alta programabilidade, tem uma estrutura de computação de alto desempenho relativamente madura e tem um ciclo de iteração de desenvolvimento curto e prefere cenários de taxa de transferência.