As provas de conhecimento zero (ZKPs) estão se tornando cada vez mais importantes para sistemas descentralizados. A ZK apareceu pela primeira vez aos olhos do público por seu sucesso em projetos como o ZCash, mas hoje a ZK é conhecida como uma solução de escalonamento para Ethereum.
Aproveitando ZK, a Camada 2 (por exemplo, Scroll e Polygon), também conhecida como Rollups, está desenvolvendo zkEVMs (zk Ethereum Virtual Machine). Estes zkEVMs processam um lote de transações e geram uma pequena prova (em kilobytes). Este atestado pode ser usado para verificar para toda a rede se o lote de transações é válido e correto.
No entanto, seus usos não param por aí. ZK permite uma variedade de aplicações interessantes.
Private Layer 1 – Mina, por exemplo, esconde os detalhes das transações e dados em seu blockchain, permitindo que os usuários apenas comprovem a validade de suas transações sem revelar as especificidades da transação em si. neptune.cash e Aleo também são projetos muito interessantes.
Plataforma de nuvem descentralizada - FedML e together.xyz permitem que modelos de aprendizado de máquina (ML) sejam treinados de forma descentralizada, terceirizem cálculos para a rede e verifiquem a correção dos cálculos usando ZKP. A Druglike está construindo uma plataforma de descoberta de medicamentos mais aberta usando tecnologias semelhantes.
Armazenamento descentralizado - Filecoin está revolucionando o armazenamento em nuvem, e ZK está em seu núcleo, permitindo que os provedores de armazenamento provem que armazenaram os dados certos durante um período de tempo.
JOGO - Uma versão mais avançada do Darkforest pode aparecer, o que requer prova em tempo real. ZK também pode expandir o jogo para reduzir a probabilidade de trapaça. Talvez também trabalhe com uma plataforma de nuvem descentralizada para permitir que o jogo pague por sua própria hospedagem!
Identidade - A autenticação descentralizada agora também é possível através do ZK. Em torno desta ideia, estão a ser construídos vários projetos interessantes. Por exemplo, notebook e zkemail (recomendado para saber sobre).
O impacto do ZK e dos sistemas descentralizados é enorme, no entanto, o desenvolvimento da história não é perfeito, e ainda existem muitos obstáculos e desafios hoje. O processo de inclusão da geração de provas consome muitos recursos e requer muitas operações matemáticas complexas. À medida que os desenvolvedores procuram construir protocolos e sistemas mais ambiciosos e complexos usando a tecnologia ZK, tanto para geração de provas quanto para processos de verificação, os desenvolvedores estão exigindo tamanhos de prova menores, desempenho mais rápido e melhores otimizações.
Neste artigo, exploraremos o estado atual da aceleração de hardware e como ela desempenhará um papel fundamental no avanço da adoção do ZK.
Snark vs Stark
Existem duas técnicas populares de conhecimento zero hoje, zk-STARK e zk-SNARK (ignoramos Bulletproofs neste artigo).
| | | |
| --- | --- | --- |
| zk-STARK - Brasil | zk-SNARK - Brasil | |
| Complexidade - Prover | O(N * poli-log(N)) | O(N * log(N)) |
| Complexidade - Verificador | O(poli-log(N)) | O(1) |
| Tamanho da prova | 45KB-200KB | ~ 288 Bytes |
| 抗量子 | Sim (função hash baseada) | Não |
| Configuração fidedigna | Não | Sim |
| Conhecimento Zero | Sim | Sim |
| Interatividade | Interativo ou não interativo | Não interativo |
| Documentação do desenvolvedor | Limitado, mas em expansão Bom |
表1:Snark VS Stark
Como mencionado acima, existem diferenças e compensações entre os dois. O ponto mais importante é que a configuração confiável de um sistema baseado em zk-SNARK depende de pelo menos um participante honesto envolvido no processo de configuração confiável e ter suas chaves destruídas no final do processo. Em termos de verificação on-chain, os zk-SNARKs são muito mais baratos em termos de taxas de gás. Além disso, as provas de zk-SNARKs também são significativamente menores, tornando-as mais baratas para armazenar on-chain.
Atualmente, zk-SNARKs são mais populares do que zk-STARKs. A razão mais provável é que zk-SNARKs têm uma história muito mais longa. Outra razão possível é que o Zcash, um dos primeiros blockchains ZK, usou zk-SNARKs, então a maioria das ferramentas de desenvolvimento e documentação atuais giram em torno do ecossistema zk-SNARK.
Como construir um aplicativo ZK
Os desenvolvedores podem precisar de dois componentes para concluir o desenvolvimento de um aplicativo ZK
Um método de computação de expressão amigável para ZK (DSL ou biblioteca de baixo nível).
Um sistema de certificação que implementa duas funções: Provar e Verificar.
DSLs (linguagem específica do domínio) e bibliotecas de baixo nível
Quando se trata de DSLs, há muitas opções, como Circom, Halo2, Noir e muito mais. O Circom é provavelmente o mais popular no momento.
Quando se trata de bibliotecas de baixo nível, um exemplo popular é Arkworks; Há também bibliotecas em desenvolvimento, como a ICICLE, que é uma biblioteca de aceleração CUDA.
Estas DSLs são projetadas para produzir sistemas confinados. Ao contrário do programa usual, que geralmente é avaliado na forma de x:= y *z, o mesmo programa na forma restrita se parece mais com x-y * z = 0. Ao representar o programa como um sistema de restrições, descobrimos que operações como adição ou multiplicação podem ser representadas por uma única restrição. No entanto, operações mais complexas, como operações de bits, podem exigir centenas de restrições!
Como resultado, torna-se complicado implementar algumas funções de hash como programas amigáveis para ZK. Em provas de conhecimento zero, as funções de hash são frequentemente usadas para garantir a integridade dos dados e/ou para verificar propriedades específicas dos dados, mas devido ao grande número de restrições de operações de bits, algumas funções de hash são difíceis de adaptar ao ambiente de provas de conhecimento zero. Essa complexidade pode afetar a eficiência da geração e verificação de provas e, portanto, se tornar um problema que os desenvolvedores precisam considerar e resolver ao criar aplicativos baseados em ZK
Como resultado, torna-se complicado implementar algumas funções de hash para ser ZK-friendly.
Comprovação
Um sistema de provas pode ser comparado a um software que realiza duas tarefas principais: gerar provas e verificar provas. Os sistemas de prova normalmente aceitam circuitos, evidências e parâmetros públicos/privados como entradas.
Os dois sistemas de prova mais populares são as séries Groth16 e PLONK (Plonk, HyperPlonk, UltraPlonk)
| | | | | | |
| --- | --- | --- | --- | --- | --- |
| | Configuração confiável | Tamanho da prova | Complexidade do provador | Complexidade do verificador | Flexibilidade |
| Groth16 - Brasil | Circuito específico | pequeno | Baixa | Baixa | Baixa |
| Plonk - Brasil | Universal | Grande | Alta | 常数 | Alta |
表2:Groth16 vs Plonk
Como mostrado na Tabela 2, o Groth16 requer um processo de configuração confiável, mas o Groth16 nos fornece tempos de prova e verificação mais rápidos, bem como um tamanho de prova constante.
O Plonk fornece uma configuração genérica que executa uma fase de pré-processamento para o circuito que você está executando toda vez que uma prova é gerada. Apesar de suportar muitos circuitos, o tempo de verificação de Plonk é constante.
Existem também diferenças entre os dois em termos de restrições. O Groth16 cresce linearmente em termos de tamanho de restrição e carece de flexibilidade, enquanto o Plonk é mais flexível.
No geral, entenda que o desempenho está diretamente relacionado ao número de restrições em seu aplicativo ZK. Quanto mais restrições, mais operações o provador deve calcular.
estrangulamento
O sistema de prova consiste em duas operações matemáticas principais: multiplicação multiescalar (MSM) e transformada rápida de Fourier (FFT). Hoje vamos explorar sistemas onde ambos existem, onde o MSM pode ocupar cerca de 60% do tempo de execução, enquanto o FFT pode ocupar cerca de 30%.
O MSM requer muito acesso à memória, que na maioria dos casos consome muita memória na máquina, ao mesmo tempo em que executa muitas operações de multiplicação escalar.
Os algoritmos FFT geralmente exigem a reorganização dos dados de entrada em uma ordem específica para executar transformações. Isso pode exigir muita movimentação de dados e pode ser um gargalo, especialmente para grandes tamanhos de entrada. A utilização do cache também pode ser um problema se os padrões de acesso à memória não se encaixarem na hierarquia de cache.
**Neste caso, a aceleração de hardware é a única maneira de otimizar totalmente o desempenho do ZKP. **
Aceleração de Hardware
Quando se trata de aceleração de hardware, isso nos lembra de como ASICs e GPUs dominaram a mineração de Bitcoin e Ethereum.
Embora as otimizações de software sejam igualmente importantes e valiosas, elas têm suas limitações. A otimização de hardware, por outro lado, pode melhorar o paralelismo projetando FPGAs com várias unidades de processamento, como a redução da sincronização de threads ou vetorização. O acesso à memória também pode ser otimizado de forma mais eficiente, melhorando as hierarquias de memória e os padrões de acesso.
Agora no espaço ZKP, a principal tendência parece ter mudado: GPUs e FPGAs.
No curto prazo, as GPUs têm uma vantagem no preço, especialmente depois que a ETH muda para prova de participação (POS), deixando um grande número de mineradores de GPU ociosos e em espera. Além disso, as GPUs têm a vantagem de ciclos de desenvolvimento curtos e fornecem aos desenvolvedores muito paralelismo "plug-and-play".
No entanto, os FPGAs devem recuperar o atraso, especialmente ao comparar fatores de forma e consumo de energia. Os FPGAs também fornecem latência mais baixa para fluxos de dados de alta velocidade. Quando vários FPGAs são agrupados, eles fornecem um melhor desempenho em comparação com clusters de GPU.
GPU VS FPGA
GPU:
Tempo de desenvolvimento: As GPUs proporcionam um tempo de desenvolvimento rápido. A documentação do desenvolvedor para frameworks como CUDA e OpenCL é bem desenvolvida e popular.
Consumo de energia: as GPUs consomem muita energia. Mesmo quando os desenvolvedores aproveitam o paralelismo no nível de dados e o paralelismo no nível de thread, as GPUs ainda consomem muita energia.
Disponibilidade: GPUs de nível de consumidor são baratas e prontamente disponíveis no momento.
FPGA:
Ciclo de desenvolvimento: FPGAs têm um ciclo de desenvolvimento mais complexo e exigem engenheiros mais especializados. Os FPGAs permitem que os engenheiros alcancem muitas otimizações de "baixo nível" que as GPUs não conseguem.
Latência: FPGAs fornecem menor latência, especialmente ao processar grandes fluxos de dados.
Custo vs. disponibilidade: FPGAs são mais caros do que GPUs e não estão tão prontamente disponíveis quanto GPUs.
ZPRIZE
Hoje em dia, quando se trata do gargalo de otimização de hardware e ZKP, há uma competição que não pode ser evitada - ZPRIZE
ZPrize é uma das iniciativas mais importantes no campo ZK no momento. ZPrize é uma competição que incentiva as equipes a desenvolver aceleração de hardware para os principais gargalos do ZKP (por exemplo, MSM, NTT, Poseidon, etc.) em várias plataformas (por exemplo, FPGAs, GPUs, dispositivos móveis e navegadores) com base na latência, taxa de transferência e eficiência.
O resultado foi muito interessante. Por exemplo, as melhorias da GPU são enormes:
MSM em 2^26 aumentou em 131% de 5,86 segundos para 2,52 segundos. Por outro lado, as soluções FPGA tendem a não ter benchmarks em comparação com os resultados da GPU, que têm benchmarks anteriores para comparar, e a maioria das soluções FPGA são open-source pela primeira vez, com tais algoritmos que devem melhorar no futuro.
Esses resultados indicam a direção em que a maioria dos desenvolvedores se sente confortável no desenvolvimento de suas soluções de aceleração de hardware. Muitas equipes competem pela categoria GPU, mas apenas uma pequena porcentagem compete pela categoria FPGA. Não tenho certeza se é por falta de experiência ao desenvolver para FPGAs, ou se a maioria das empresas/equipes de FPGA optam por desenvolver secretamente para vender suas soluções comercialmente.
ZPrize forneceu algumas pesquisas muito interessantes para a comunidade. À medida que mais rodadas de ZPrize começam, veremos mais e mais soluções e problemas interessantes aparecerem.
Exemplos práticos de aceleração de hardware
Tomando Groth16 como exemplo, se examinarmos a implementação do rapidsnark para Groth16, podemos observar que duas operações principais são realizadas: FFT (Fast Fourier Transform) e MSM (Multiscalar Multiplication); Estas duas operações básicas são comuns em muitos sistemas de prova. O seu tempo de execução está diretamente relacionado com o número de restrições no circuito. Naturalmente, o número de restrições aumenta à medida que circuitos mais complexos são escritos.
Para ter uma noção de como as operações FFT e MSM são computacionalmente intensivas, podemos conferir o benchmark de Ingonyama do circuito Groth16 (processo Vanilla C2 da Filecoin realizado em um setor de 32GB), e os resultados são os seguintes
Como mostrado na figura acima, o MSM (Multiscalar Multiplication) pode ser demorado e um sério gargalo de desempenho para muitos provadores, tornando o MSM um dos operadores criptográficos mais importantes que precisam ser acelerados.
Então, quanto cálculo o MSM ocupa para o provador em outros sistemas de prova ZK? Isso é mostrado na figura abaixo
Em Plonk, o MSM representa mais de 85% das despesas gerais, como mostra o último artigo de Ingonyama, Pipe MSM. **
Então, como a aceleração de hardware deve acelerar o MSM? **
HSH
Antes de falarmos sobre como acelerar o MSM, precisamos entender o que é MSM
Multi-Scalar Multiplication (MSM) é um algoritmo para calcular a soma de múltiplas multiplicações escalares na seguinte forma
onde G é um ponto no grupo da curva elíptica, a é um escalar, e o resultado do MSM também será um ponto da curva elíptica
Podemos decompor o MSM em dois subcomponentes principais:
Multiplicação modular
Adições de pontos de curva elíptica
Tomemos Affine(x,y) como exemplo para executar uma operação P+Q ingênua.
Quando queremos calcular P + Q = R, precisamos calcular um valor k, pela abscissa de k e P,Q
Obtenha as coordenadas de R. O processo de cálculo é como acima, neste processo realizamos 2 vezes multiplicação, 1 operação quadrada, 1 operação inversa, e várias vezes operações de adição e subtração. Vale a pena notar que as operações acima são realizadas em um campo finito, ou seja, sob mod P. Na realidade, P será muito grande. **
O custo da operação acima é encontrar o inverso >> multiplicação** **> **** ao quadrado, e o custo de adição e subtração é insignificante.
Portanto, queremos evitar ao máximo as inversões, porque o custo de uma única inversão é pelo menos cem vezes maior de multiplicação. Podemos fazer isso expandindo o sistema de coordenadas, mas ao custo de aumentar o número de multiplicações no processo, como coordenadas jacobinas: XYZ += XYZ, e multiplicando mais de 10 vezes, dependendo do algoritmo de adição. **
GPU VS FPGA MSM acelerado
Esta seção compara duas implementações MSM líderes, PipeMSM e Sppark, onde o PipeMSM é implementado em FPGAs e o Sppark é implementado em GPUs.
Sppark e PipeMSM usam o algoritmo Pippenger de última geração para implementar o MSM, também conhecido como algoritmo bucket; **
Sppark é implementado usando CUDA; Suas versões são altamente paralelas e alcançaram resultados impressionantes quando executadas nas GPUs mais recentes.
No entanto, o PipeMSM não apenas otimiza o algoritmo, mas também fornece otimizações para os primitivos matemáticos de Multiplicação Modular e Adição EC. O PipeMSM lida com toda a "pilha de MSM", implementando uma série de truques matemáticos e otimizações destinadas a tornar o MSM mais adequado para hardware e projetando um design de hardware projetado para reduzir a latência com foco na paralelização.
Vamos fazer uma rápida recapitulação da implementação do PipeMSM.
Baixa latência
O PipeMSM foi projetado para fornecer baixa latência ao executar vários MSMs em um grande número de entradas. As GPUs não oferecem baixa latência determinística devido ao dimensionamento dinâmico de frequência, e as GPUs ajustam suas velocidades de clock com base nas cargas de trabalho.
Mas graças ao design de hardware otimizado, as implementações FPGA podem fornecer desempenho determinístico e latência para cargas de trabalho específicas.
Implementação de adição de CE
A Adição de Pontos de Curva Elíptica (EC Addition) é implementada como uma fórmula de baixa latência, altamente paralela e completa (completa significa que calcula corretamente a soma de quaisquer dois pontos no grupo da curva elíptica). A adição de pontos de curva elíptica é usada de forma canalizada no módulo de adição EC para reduzir a latência.
Optamos por representar as coordenadas como coordenadas projetivas e, no algoritmo de adição, usamos uma fórmula completa de adição de ponto de curva elíptica. A principal vantagem é que nós não temos que lidar com casos de borda. Fórmulas completas;
Implementamos esta fórmula de adição de forma tubulada e paralela, e nosso circuito de adição de curva elíptica FPGA só precisava de 12 multiplicações, 17 somas de adições, e essa fórmula foi executada. A fórmula original requer 15 modulo multiplicação e 13 adições. O design do FPGA é o seguinte:
Multimod
Utilizamos os algoritmos Barrett Reduction e Karatsuba.
Barrett Reduction é um algoritmo que calcula eficientemente r≡ab mod p (onde p é fixo). Barrett Reduction tenta substituir a divisão (uma operação cara) por divisão aproximada. Uma tolerância a erros pode ser selecionada para descrever o intervalo dentro do qual estamos procurando o resultado correto. Descobrimos que a grande tolerância a erros permite o uso de constantes de redução menores; Isso reduz o tamanho dos valores intermediários usados nas operações de redução de módulos, o que reduz o número de multiplicações necessárias para calcular o resultado final.
Na caixa azul abaixo, podemos ver que, devido à nossa alta tolerância a erros, temos que realizar várias verificações para encontrar um resultado preciso.
Em poucas palavras, o algoritmo de Karatsuba é usado para otimizar a multiplicação que realizamos na Redução de Barrett. O algoritmo de Karatsuba simplifica a multiplicação de dois n-dígitos para a multiplicação de três n/2-dígitos; Essas multiplicações podem simplificar o número de dígitos para ser estreito o suficiente para ser diretamente computado pelo hardware. Os detalhes podem ser lidos no artigo de Ingo: Pipe MSM
Usando os operadores acima, desenvolvemos uma implementação MSM de baixa latência e altamente paralela.
A ideia central é que, em vez de calcular todo o MSM de uma só vez, cada pedaço é passado para o aditivo EC em paralelo. Os resultados do aditivo CE são acumulados no MSM final.
Resultado final****
O diagrama acima mostra a comparação entre Sppark e PipeMSM.
O mais proeminente é a significativa economia de energia oferecida pelos FPGAs, que pode ser extremamente importante para futuras operações de geração à prova em larga escala. Vale a pena notar que nossa implementação foi prototipada e aferida sob @125MHz, e aumentar a velocidade do relógio para @500MHz poderia aumentar o tempo de computação em 4x ou mais.
Outra vantagem de usar nossos FPGAs é que eles podem ser instalados em servidores de chassis pequenos, pois consomem menos energia e geram menos calor.
Estamos nos estágios iniciais da engenharia de FPGA para ZKP e devemos esperar mais melhorias nos algoritmos. Além disso, o FPGA está computando o MSM enquanto a CPU está ociosa, e pode ser possível alcançar tempos mais rápidos usando o FPGA em combinação com os recursos do sistema (CPU / GPU).
Resumo
ZKP tornou-se uma tecnologia chave para sistemas distribuídos.
A aplicação do ZKP vai muito além de apenas estender o nível Ethereum, permitindo a terceirização da computação para terceiros não confiáveis, permitindo o desenvolvimento de sistemas anteriormente impossíveis, como computação em nuvem distribuída, sistemas de identidade e muito mais.
Tradicionalmente, as otimizações ZKP têm se concentrado em melhorias no nível de software, mas à medida que a demanda por um desempenho mais superior aumenta, veremos soluções de aceleração mais avançadas envolvendo hardware e software.
Atualmente, as soluções de aceleração que vemos usam principalmente GPUs, porque o tempo de desenvolvimento usando CUDA é curto, e as GPUs de consumo atuais são muito baratas e abundantes. A GPU também oferece um desempenho incrível. Portanto, é improvável que as GPUs desapareçam desse espaço tão cedo.
À medida que equipes de desenvolvimento mais complexas entram no espaço, é provável que vejamos FPGAs liderando o caminho em termos de eficiência energética e desempenho. Em comparação com GPUs, os FPGAs oferecem mais personalização de baixo nível, bem como mais opções de configuração. Os FPGAs oferecem velocidade de desenvolvimento e flexibilidade mais rápidas do que os ASICs. Com o rápido desenvolvimento do mundo ZKP, os FPGAs podem ser reativados com diferentes programas para acomodar diferentes sistemas e atualizar soluções.
No entanto, para gerar provas quase em tempo real, pode ser necessário combinar configurações GPU/FPGA/ASIC dependendo do sistema para o qual geramos provas.
É provável que a ZPU também evolua para fornecer soluções extremamente eficientes para geradores à prova de grande escala e dispositivos de baixa potência (consulte o artigo anterior para obter detalhes).
Ver original
Esta página pode conter conteúdos de terceiros, que são fornecidos apenas para fins informativos (sem representações/garantias) e não devem ser considerados como uma aprovação dos seus pontos de vista pela Gate, nem como aconselhamento financeiro ou profissional. Consulte a Declaração de exoneração de responsabilidade para obter mais informações.
Uma nova era de ZK impulsionada pela aceleração de hardware
História até agora
As provas de conhecimento zero (ZKPs) estão se tornando cada vez mais importantes para sistemas descentralizados. A ZK apareceu pela primeira vez aos olhos do público por seu sucesso em projetos como o ZCash, mas hoje a ZK é conhecida como uma solução de escalonamento para Ethereum.
Aproveitando ZK, a Camada 2 (por exemplo, Scroll e Polygon), também conhecida como Rollups, está desenvolvendo zkEVMs (zk Ethereum Virtual Machine). Estes zkEVMs processam um lote de transações e geram uma pequena prova (em kilobytes). Este atestado pode ser usado para verificar para toda a rede se o lote de transações é válido e correto.
No entanto, seus usos não param por aí. ZK permite uma variedade de aplicações interessantes.
Private Layer 1 – Mina, por exemplo, esconde os detalhes das transações e dados em seu blockchain, permitindo que os usuários apenas comprovem a validade de suas transações sem revelar as especificidades da transação em si. neptune.cash e Aleo também são projetos muito interessantes.
Plataforma de nuvem descentralizada - FedML e together.xyz permitem que modelos de aprendizado de máquina (ML) sejam treinados de forma descentralizada, terceirizem cálculos para a rede e verifiquem a correção dos cálculos usando ZKP. A Druglike está construindo uma plataforma de descoberta de medicamentos mais aberta usando tecnologias semelhantes.
Armazenamento descentralizado - Filecoin está revolucionando o armazenamento em nuvem, e ZK está em seu núcleo, permitindo que os provedores de armazenamento provem que armazenaram os dados certos durante um período de tempo.
JOGO - Uma versão mais avançada do Darkforest pode aparecer, o que requer prova em tempo real. ZK também pode expandir o jogo para reduzir a probabilidade de trapaça. Talvez também trabalhe com uma plataforma de nuvem descentralizada para permitir que o jogo pague por sua própria hospedagem!
Identidade - A autenticação descentralizada agora também é possível através do ZK. Em torno desta ideia, estão a ser construídos vários projetos interessantes. Por exemplo, notebook e zkemail (recomendado para saber sobre).
O impacto do ZK e dos sistemas descentralizados é enorme, no entanto, o desenvolvimento da história não é perfeito, e ainda existem muitos obstáculos e desafios hoje. O processo de inclusão da geração de provas consome muitos recursos e requer muitas operações matemáticas complexas. À medida que os desenvolvedores procuram construir protocolos e sistemas mais ambiciosos e complexos usando a tecnologia ZK, tanto para geração de provas quanto para processos de verificação, os desenvolvedores estão exigindo tamanhos de prova menores, desempenho mais rápido e melhores otimizações.
Neste artigo, exploraremos o estado atual da aceleração de hardware e como ela desempenhará um papel fundamental no avanço da adoção do ZK.
Snark vs Stark
Existem duas técnicas populares de conhecimento zero hoje, zk-STARK e zk-SNARK (ignoramos Bulletproofs neste artigo).
| | | | | --- | --- | --- | | zk-STARK - Brasil | zk-SNARK - Brasil | | | Complexidade - Prover | O(N * poli-log(N)) | O(N * log(N)) | | Complexidade - Verificador | O(poli-log(N)) | O(1) | | Tamanho da prova | 45KB-200KB | ~ 288 Bytes | | 抗量子 | Sim (função hash baseada) | Não | | Configuração fidedigna | Não | Sim | | Conhecimento Zero | Sim | Sim | | Interatividade | Interativo ou não interativo | Não interativo | | Documentação do desenvolvedor | Limitado, mas em expansão Bom |
表1:Snark VS Stark
Como mencionado acima, existem diferenças e compensações entre os dois. O ponto mais importante é que a configuração confiável de um sistema baseado em zk-SNARK depende de pelo menos um participante honesto envolvido no processo de configuração confiável e ter suas chaves destruídas no final do processo. Em termos de verificação on-chain, os zk-SNARKs são muito mais baratos em termos de taxas de gás. Além disso, as provas de zk-SNARKs também são significativamente menores, tornando-as mais baratas para armazenar on-chain.
Atualmente, zk-SNARKs são mais populares do que zk-STARKs. A razão mais provável é que zk-SNARKs têm uma história muito mais longa. Outra razão possível é que o Zcash, um dos primeiros blockchains ZK, usou zk-SNARKs, então a maioria das ferramentas de desenvolvimento e documentação atuais giram em torno do ecossistema zk-SNARK.
Como construir um aplicativo ZK
Os desenvolvedores podem precisar de dois componentes para concluir o desenvolvimento de um aplicativo ZK
Um método de computação de expressão amigável para ZK (DSL ou biblioteca de baixo nível).
Um sistema de certificação que implementa duas funções: Provar e Verificar.
DSLs (linguagem específica do domínio) e bibliotecas de baixo nível
Quando se trata de DSLs, há muitas opções, como Circom, Halo2, Noir e muito mais. O Circom é provavelmente o mais popular no momento.
Quando se trata de bibliotecas de baixo nível, um exemplo popular é Arkworks; Há também bibliotecas em desenvolvimento, como a ICICLE, que é uma biblioteca de aceleração CUDA.
Estas DSLs são projetadas para produzir sistemas confinados. Ao contrário do programa usual, que geralmente é avaliado na forma de x:= y *z, o mesmo programa na forma restrita se parece mais com x-y * z = 0. Ao representar o programa como um sistema de restrições, descobrimos que operações como adição ou multiplicação podem ser representadas por uma única restrição. No entanto, operações mais complexas, como operações de bits, podem exigir centenas de restrições!
Como resultado, torna-se complicado implementar algumas funções de hash como programas amigáveis para ZK. Em provas de conhecimento zero, as funções de hash são frequentemente usadas para garantir a integridade dos dados e/ou para verificar propriedades específicas dos dados, mas devido ao grande número de restrições de operações de bits, algumas funções de hash são difíceis de adaptar ao ambiente de provas de conhecimento zero. Essa complexidade pode afetar a eficiência da geração e verificação de provas e, portanto, se tornar um problema que os desenvolvedores precisam considerar e resolver ao criar aplicativos baseados em ZK
Como resultado, torna-se complicado implementar algumas funções de hash para ser ZK-friendly.
Comprovação
Um sistema de provas pode ser comparado a um software que realiza duas tarefas principais: gerar provas e verificar provas. Os sistemas de prova normalmente aceitam circuitos, evidências e parâmetros públicos/privados como entradas.
Os dois sistemas de prova mais populares são as séries Groth16 e PLONK (Plonk, HyperPlonk, UltraPlonk)
| | | | | | | | --- | --- | --- | --- | --- | --- | | | Configuração confiável | Tamanho da prova | Complexidade do provador | Complexidade do verificador | Flexibilidade | | Groth16 - Brasil | Circuito específico | pequeno | Baixa | Baixa | Baixa | | Plonk - Brasil | Universal | Grande | Alta | 常数 | Alta |
表2:Groth16 vs Plonk
Como mostrado na Tabela 2, o Groth16 requer um processo de configuração confiável, mas o Groth16 nos fornece tempos de prova e verificação mais rápidos, bem como um tamanho de prova constante.
O Plonk fornece uma configuração genérica que executa uma fase de pré-processamento para o circuito que você está executando toda vez que uma prova é gerada. Apesar de suportar muitos circuitos, o tempo de verificação de Plonk é constante.
Existem também diferenças entre os dois em termos de restrições. O Groth16 cresce linearmente em termos de tamanho de restrição e carece de flexibilidade, enquanto o Plonk é mais flexível.
No geral, entenda que o desempenho está diretamente relacionado ao número de restrições em seu aplicativo ZK. Quanto mais restrições, mais operações o provador deve calcular.
estrangulamento
O sistema de prova consiste em duas operações matemáticas principais: multiplicação multiescalar (MSM) e transformada rápida de Fourier (FFT). Hoje vamos explorar sistemas onde ambos existem, onde o MSM pode ocupar cerca de 60% do tempo de execução, enquanto o FFT pode ocupar cerca de 30%.
O MSM requer muito acesso à memória, que na maioria dos casos consome muita memória na máquina, ao mesmo tempo em que executa muitas operações de multiplicação escalar.
Os algoritmos FFT geralmente exigem a reorganização dos dados de entrada em uma ordem específica para executar transformações. Isso pode exigir muita movimentação de dados e pode ser um gargalo, especialmente para grandes tamanhos de entrada. A utilização do cache também pode ser um problema se os padrões de acesso à memória não se encaixarem na hierarquia de cache.
**Neste caso, a aceleração de hardware é a única maneira de otimizar totalmente o desempenho do ZKP. **
Aceleração de Hardware
Quando se trata de aceleração de hardware, isso nos lembra de como ASICs e GPUs dominaram a mineração de Bitcoin e Ethereum.
Embora as otimizações de software sejam igualmente importantes e valiosas, elas têm suas limitações. A otimização de hardware, por outro lado, pode melhorar o paralelismo projetando FPGAs com várias unidades de processamento, como a redução da sincronização de threads ou vetorização. O acesso à memória também pode ser otimizado de forma mais eficiente, melhorando as hierarquias de memória e os padrões de acesso.
Agora no espaço ZKP, a principal tendência parece ter mudado: GPUs e FPGAs.
No curto prazo, as GPUs têm uma vantagem no preço, especialmente depois que a ETH muda para prova de participação (POS), deixando um grande número de mineradores de GPU ociosos e em espera. Além disso, as GPUs têm a vantagem de ciclos de desenvolvimento curtos e fornecem aos desenvolvedores muito paralelismo "plug-and-play".
No entanto, os FPGAs devem recuperar o atraso, especialmente ao comparar fatores de forma e consumo de energia. Os FPGAs também fornecem latência mais baixa para fluxos de dados de alta velocidade. Quando vários FPGAs são agrupados, eles fornecem um melhor desempenho em comparação com clusters de GPU.
GPU VS FPGA
GPU:
Tempo de desenvolvimento: As GPUs proporcionam um tempo de desenvolvimento rápido. A documentação do desenvolvedor para frameworks como CUDA e OpenCL é bem desenvolvida e popular.
Consumo de energia: as GPUs consomem muita energia. Mesmo quando os desenvolvedores aproveitam o paralelismo no nível de dados e o paralelismo no nível de thread, as GPUs ainda consomem muita energia.
Disponibilidade: GPUs de nível de consumidor são baratas e prontamente disponíveis no momento.
FPGA:
Ciclo de desenvolvimento: FPGAs têm um ciclo de desenvolvimento mais complexo e exigem engenheiros mais especializados. Os FPGAs permitem que os engenheiros alcancem muitas otimizações de "baixo nível" que as GPUs não conseguem.
Latência: FPGAs fornecem menor latência, especialmente ao processar grandes fluxos de dados.
Custo vs. disponibilidade: FPGAs são mais caros do que GPUs e não estão tão prontamente disponíveis quanto GPUs.
ZPRIZE
Hoje em dia, quando se trata do gargalo de otimização de hardware e ZKP, há uma competição que não pode ser evitada - ZPRIZE
ZPrize é uma das iniciativas mais importantes no campo ZK no momento. ZPrize é uma competição que incentiva as equipes a desenvolver aceleração de hardware para os principais gargalos do ZKP (por exemplo, MSM, NTT, Poseidon, etc.) em várias plataformas (por exemplo, FPGAs, GPUs, dispositivos móveis e navegadores) com base na latência, taxa de transferência e eficiência.
O resultado foi muito interessante. Por exemplo, as melhorias da GPU são enormes:
MSM em 2^26 aumentou em 131% de 5,86 segundos para 2,52 segundos. Por outro lado, as soluções FPGA tendem a não ter benchmarks em comparação com os resultados da GPU, que têm benchmarks anteriores para comparar, e a maioria das soluções FPGA são open-source pela primeira vez, com tais algoritmos que devem melhorar no futuro.
Esses resultados indicam a direção em que a maioria dos desenvolvedores se sente confortável no desenvolvimento de suas soluções de aceleração de hardware. Muitas equipes competem pela categoria GPU, mas apenas uma pequena porcentagem compete pela categoria FPGA. Não tenho certeza se é por falta de experiência ao desenvolver para FPGAs, ou se a maioria das empresas/equipes de FPGA optam por desenvolver secretamente para vender suas soluções comercialmente.
ZPrize forneceu algumas pesquisas muito interessantes para a comunidade. À medida que mais rodadas de ZPrize começam, veremos mais e mais soluções e problemas interessantes aparecerem.
Exemplos práticos de aceleração de hardware
Tomando Groth16 como exemplo, se examinarmos a implementação do rapidsnark para Groth16, podemos observar que duas operações principais são realizadas: FFT (Fast Fourier Transform) e MSM (Multiscalar Multiplication); Estas duas operações básicas são comuns em muitos sistemas de prova. O seu tempo de execução está diretamente relacionado com o número de restrições no circuito. Naturalmente, o número de restrições aumenta à medida que circuitos mais complexos são escritos.
Para ter uma noção de como as operações FFT e MSM são computacionalmente intensivas, podemos conferir o benchmark de Ingonyama do circuito Groth16 (processo Vanilla C2 da Filecoin realizado em um setor de 32GB), e os resultados são os seguintes
Como mostrado na figura acima, o MSM (Multiscalar Multiplication) pode ser demorado e um sério gargalo de desempenho para muitos provadores, tornando o MSM um dos operadores criptográficos mais importantes que precisam ser acelerados.
Então, quanto cálculo o MSM ocupa para o provador em outros sistemas de prova ZK? Isso é mostrado na figura abaixo
Em Plonk, o MSM representa mais de 85% das despesas gerais, como mostra o último artigo de Ingonyama, Pipe MSM. **
Então, como a aceleração de hardware deve acelerar o MSM? **
HSH
Antes de falarmos sobre como acelerar o MSM, precisamos entender o que é MSM
Multi-Scalar Multiplication (MSM) é um algoritmo para calcular a soma de múltiplas multiplicações escalares na seguinte forma
onde G é um ponto no grupo da curva elíptica, a é um escalar, e o resultado do MSM também será um ponto da curva elíptica
Podemos decompor o MSM em dois subcomponentes principais:
Multiplicação modular
Adições de pontos de curva elíptica
Tomemos Affine(x,y) como exemplo para executar uma operação P+Q ingênua.
Quando queremos calcular P + Q = R, precisamos calcular um valor k, pela abscissa de k e P,Q
Obtenha as coordenadas de R. O processo de cálculo é como acima, neste processo realizamos 2 vezes multiplicação, 1 operação quadrada, 1 operação inversa, e várias vezes operações de adição e subtração. Vale a pena notar que as operações acima são realizadas em um campo finito, ou seja, sob mod P. Na realidade, P será muito grande. **
O custo da operação acima é encontrar o inverso >> multiplicação** **> **** ao quadrado, e o custo de adição e subtração é insignificante.
Portanto, queremos evitar ao máximo as inversões, porque o custo de uma única inversão é pelo menos cem vezes maior de multiplicação. Podemos fazer isso expandindo o sistema de coordenadas, mas ao custo de aumentar o número de multiplicações no processo, como coordenadas jacobinas: XYZ += XYZ, e multiplicando mais de 10 vezes, dependendo do algoritmo de adição. **
GPU VS FPGA MSM acelerado
Esta seção compara duas implementações MSM líderes, PipeMSM e Sppark, onde o PipeMSM é implementado em FPGAs e o Sppark é implementado em GPUs.
Sppark e PipeMSM usam o algoritmo Pippenger de última geração para implementar o MSM, também conhecido como algoritmo bucket; **
Sppark é implementado usando CUDA; Suas versões são altamente paralelas e alcançaram resultados impressionantes quando executadas nas GPUs mais recentes.
No entanto, o PipeMSM não apenas otimiza o algoritmo, mas também fornece otimizações para os primitivos matemáticos de Multiplicação Modular e Adição EC. O PipeMSM lida com toda a "pilha de MSM", implementando uma série de truques matemáticos e otimizações destinadas a tornar o MSM mais adequado para hardware e projetando um design de hardware projetado para reduzir a latência com foco na paralelização.
Vamos fazer uma rápida recapitulação da implementação do PipeMSM.
Baixa latência
O PipeMSM foi projetado para fornecer baixa latência ao executar vários MSMs em um grande número de entradas. As GPUs não oferecem baixa latência determinística devido ao dimensionamento dinâmico de frequência, e as GPUs ajustam suas velocidades de clock com base nas cargas de trabalho.
Mas graças ao design de hardware otimizado, as implementações FPGA podem fornecer desempenho determinístico e latência para cargas de trabalho específicas.
Implementação de adição de CE
A Adição de Pontos de Curva Elíptica (EC Addition) é implementada como uma fórmula de baixa latência, altamente paralela e completa (completa significa que calcula corretamente a soma de quaisquer dois pontos no grupo da curva elíptica). A adição de pontos de curva elíptica é usada de forma canalizada no módulo de adição EC para reduzir a latência.
Optamos por representar as coordenadas como coordenadas projetivas e, no algoritmo de adição, usamos uma fórmula completa de adição de ponto de curva elíptica. A principal vantagem é que nós não temos que lidar com casos de borda. Fórmulas completas;
Implementamos esta fórmula de adição de forma tubulada e paralela, e nosso circuito de adição de curva elíptica FPGA só precisava de 12 multiplicações, 17 somas de adições, e essa fórmula foi executada. A fórmula original requer 15 modulo multiplicação e 13 adições. O design do FPGA é o seguinte:
Multimod
Utilizamos os algoritmos Barrett Reduction e Karatsuba.
Barrett Reduction é um algoritmo que calcula eficientemente r≡ab mod p (onde p é fixo). Barrett Reduction tenta substituir a divisão (uma operação cara) por divisão aproximada. Uma tolerância a erros pode ser selecionada para descrever o intervalo dentro do qual estamos procurando o resultado correto. Descobrimos que a grande tolerância a erros permite o uso de constantes de redução menores; Isso reduz o tamanho dos valores intermediários usados nas operações de redução de módulos, o que reduz o número de multiplicações necessárias para calcular o resultado final.
Na caixa azul abaixo, podemos ver que, devido à nossa alta tolerância a erros, temos que realizar várias verificações para encontrar um resultado preciso.
Em poucas palavras, o algoritmo de Karatsuba é usado para otimizar a multiplicação que realizamos na Redução de Barrett. O algoritmo de Karatsuba simplifica a multiplicação de dois n-dígitos para a multiplicação de três n/2-dígitos; Essas multiplicações podem simplificar o número de dígitos para ser estreito o suficiente para ser diretamente computado pelo hardware. Os detalhes podem ser lidos no artigo de Ingo: Pipe MSM
Usando os operadores acima, desenvolvemos uma implementação MSM de baixa latência e altamente paralela.
A ideia central é que, em vez de calcular todo o MSM de uma só vez, cada pedaço é passado para o aditivo EC em paralelo. Os resultados do aditivo CE são acumulados no MSM final.
Resultado final****
O diagrama acima mostra a comparação entre Sppark e PipeMSM.
O mais proeminente é a significativa economia de energia oferecida pelos FPGAs, que pode ser extremamente importante para futuras operações de geração à prova em larga escala. Vale a pena notar que nossa implementação foi prototipada e aferida sob @125MHz, e aumentar a velocidade do relógio para @500MHz poderia aumentar o tempo de computação em 4x ou mais.
Outra vantagem de usar nossos FPGAs é que eles podem ser instalados em servidores de chassis pequenos, pois consomem menos energia e geram menos calor.
Estamos nos estágios iniciais da engenharia de FPGA para ZKP e devemos esperar mais melhorias nos algoritmos. Além disso, o FPGA está computando o MSM enquanto a CPU está ociosa, e pode ser possível alcançar tempos mais rápidos usando o FPGA em combinação com os recursos do sistema (CPU / GPU).
Resumo
ZKP tornou-se uma tecnologia chave para sistemas distribuídos.
A aplicação do ZKP vai muito além de apenas estender o nível Ethereum, permitindo a terceirização da computação para terceiros não confiáveis, permitindo o desenvolvimento de sistemas anteriormente impossíveis, como computação em nuvem distribuída, sistemas de identidade e muito mais.
Tradicionalmente, as otimizações ZKP têm se concentrado em melhorias no nível de software, mas à medida que a demanda por um desempenho mais superior aumenta, veremos soluções de aceleração mais avançadas envolvendo hardware e software.
Atualmente, as soluções de aceleração que vemos usam principalmente GPUs, porque o tempo de desenvolvimento usando CUDA é curto, e as GPUs de consumo atuais são muito baratas e abundantes. A GPU também oferece um desempenho incrível. Portanto, é improvável que as GPUs desapareçam desse espaço tão cedo.
À medida que equipes de desenvolvimento mais complexas entram no espaço, é provável que vejamos FPGAs liderando o caminho em termos de eficiência energética e desempenho. Em comparação com GPUs, os FPGAs oferecem mais personalização de baixo nível, bem como mais opções de configuração. Os FPGAs oferecem velocidade de desenvolvimento e flexibilidade mais rápidas do que os ASICs. Com o rápido desenvolvimento do mundo ZKP, os FPGAs podem ser reativados com diferentes programas para acomodar diferentes sistemas e atualizar soluções.
No entanto, para gerar provas quase em tempo real, pode ser necessário combinar configurações GPU/FPGA/ASIC dependendo do sistema para o qual geramos provas.
É provável que a ZPU também evolua para fornecer soluções extremamente eficientes para geradores à prova de grande escala e dispositivos de baixa potência (consulte o artigo anterior para obter detalhes).