Olá a todos, estou trabalhando há alguns meses em um esquema chamado Boojum para reduzir o custo de uma verificação de snark. Uma demonstração PoC pode ser encontrada neste repositório
Visão geral
Este artigo introduziu a agregação recursiva de snark usando ciclo de curvas elípticas, e criou o conceito de Proof Carrying Data (PCD) e tem sido visto como uma solução potencial para verificar instantaneamente (30ms) o estado da cadeia através de uma única verificação SNARK. No entanto, isto levanta o problema da disponibilidade de dados, pois pode potencialmente criar situações em que o Estado se torne inacessível.
Propomos aqui uma solução independente de predicado para combinar múltiplas provas ppzksnarks (forjadas para vários circuitos) em uma única que pode ser verificada em tempo constante (mais um pequeno custo linear extra por prova). Esta é uma variação do sistema à prova de PCD e vem com dois circuitos descritos no diagrama abaixo:
Ambos os circuitos representam o seguinte predicado: “Eu executei um algoritmo verificador ZK-SNARK em 2 trigêmeos (provas, vk e entradas primárias) e sua saída foi 1 em ambos”. Isso funcionará apenas para quaisquer circuitos com uma entrada primária de comprimento 1, mas não há perda de generalidade: dada uma função hash criptográfica amigável ao snark, sempre podemos converter um circuito de entrada multiprimária em uma entrada primária única, passando as entradas primárias como auxiliares e adicionando a seguinte restrição:
Primary = Hash(Auxilliary)
Esta heurística também é aplicada aos nossos circuitos, graças a isso possibilitamos que a prova de uma instância do circuito boojum seja usada como entrada de outra instância. Portanto, podemos agregar recursivamente a prova com os mesmos dois circuitos.
Os dois circuitos diferem no sentido de que não estão definidos no mesmo CE. Qualquer prova gerada em uma das teses pode ser verificada recursivamente dentro de uma prova da outra. Esta é uma condição necessária para a construção de SNARKs recursivos práticos. Estamos usando o ciclo de curva elíptica MNT4-MNT6 apresentado no mesmo artigo.
Uma das principais diferenças com o PCD é que o Boojum aceita uma chave de verificação como parâmetro público. O gerador não faz suposições sobre a prova que vai verificar. A preocupação aqui não é sobre qual circuito está sendo provado, mas sim convencer que um verificador foi executado com sucesso para um determinado trio (prova, chave de verificação, entrada primária).
Além disso, a agregação recursiva PCD funciona de forma sequencial: as atribuições são adicionadas uma após a outra na prova, enquanto aqui descrevemos um protocolo que agrega provas de forma hierárquica.
Os nós folha (ou seja: o lote de provas a serem agregadas) são inseridos como:
- Uma chave de verificação
- Uma prova
- Uma entrada primária da tarefa comprovada
Verificação na cadeia
Cada nó pai (ou seja: prova agregada) utiliza o hash das provas anteriores como entradas primárias. Portanto, durante a verificação da prova raiz, precisamos primeiro reconstruir sua entrada fazendo hash recursivamente dos nós intermediários.
In yellow, the elements that are sent in the payload to the verifier.
In grey, the elements that are already known to the verifier
In blue, the elements that are recomputed during verification by the verifier
Estimativa de custo de gás
Embora nenhum benchmark adequado tenha sido executado ainda. Podemos estimar que atualmente cada prova agregada pesa em média 355 bytes (373B para MNT6 e 337B para MNT4). E cada chave de verificação (somente no MNT4) pesa 717B. Isso soma (355 + 337 + 717 = 1409B) para cada prova. Isso representa um custo extra de 88.641 Gás por prova extra, assumindo que podemos negligenciar os zero bytes.
Esta estimativa também não leva em consideração o custo de re-hashing da árvore merkle. Atualmente usamos “subset sum hash”, que está disponível como um gadget no libsnark. É importante notar que esta função hash foi criptoanalisada (veja este artigo). Por este motivo, não pode continuar a ser uma escolha definitiva e a sua substituição terá obviamente impacto no custo de verificação de uma prova extra.
Outras opções estão sendo consideradas como um substituto potencial:
- Pedersen Hash (poderíamos reutilizar a implementação do zcash)
- MiMc
- David-Meyers
(Retirado deste tópico)
Na pior das hipóteses, a sobrecarga de hash de cada snark agregado ainda é significativamente menor em comparação com o custo atual de uma verificação e em comparação com a carga útil de gás de aproximadamente 90 mil que teríamos que pagar por prova extra.
Melhorando o tamanho da carga útil
Neste protocolo de agregação, não nos importamos muito com as provas intermediárias. A única coisa que importa é que essas provas existem e foram verificadas com sucesso o mesmo se aplica às provas folhas (ou seja: as provas que são submetidas ao processo de agregação).
No final, o que um usuário final deseja provar é apenas que possui uma atribuição válida para uma determinada entrada pública e um determinado circuito. Portanto, em vez de publicar as provas on-chain, poderíamos simplesmente publicar um hash delas. A prova teria que ser comunicada fora da cadeia ao pool agregador.
A versão melhorada do circuito é descrita na figura abaixo:
A carga útil adicional por prova extra é reduzida para (32 * 4 =) 128B (8kGas) e, portanto, dada uma função hash barata e amigável ao snark, o custo de uma verificação se torna realmente interessante.
Agregação fora da cadeia
A estrutura em árvore da prova agregada torna possível distribuir o cálculo da prova por um conjunto de trabalhadores. Dado que cada etapa de agregação leva cerca de 20 segundos, seriam necessárias mais de 5,5 horas para agregar 1.024 provas. Porém, num caso ideal, com 512 trabalhadores, o processo termina em apenas 3min12. Se pudéssemos executar um provador em uma GPU, poderíamos ter um rendimento muito melhor sem exigir um conjunto muito grande de trabalhadores.
O protocolo deve ser razoavelmente eficiente (ou seja: replicar o mínimo possível a agregação), resiliente a atores mal-intencionados (ninguém pode impedir ou retardar o processo de agregação de forma eficiente).
Além disso, este protocolo deve incluir um mecanismo de recompensa, a fim de incentivar o trabalhador a aderir ao pool. Esta não é uma tarefa trivial porque a condição BFT exige que as tarefas sejam replicadas e isso pode criar situações em que os trabalhadores não são realmente recompensados pelas suas tarefas.
Protocolo de agregação baseado em Prova de Participação
Uma ideia de design possível é usar uma eleição de líder PoS (para que possamos evitar o ataque sybil):
- As pessoas podem enviar uma prova ao pool fornecendo token/eths
- Os trabalhadores podem aderir ao pool se fornecerem uma participação
- Um líder é eleito aleatoriamente no grupo a uma taxa regular
- O líder despacha o trabalho pelo pool e gerencia as falhas
- Cada trabalhador adiciona um endereço em seu comprovante de agregação para ser recompensado
- Cada trabalhador mantém registro de seus empregos anteriores (em caso de falha do líder)
- Cada trabalho produzido por um trabalhador é verificado pelo verificador.
- Cada par de tarefas atribuídas ao trabalhador pelo líder é verificado.
- Quando todos os trabalhos são concluídos, o líder envia a prova agregada para verificação on-chain.
- Se o líder não responder após um tempo limite determinado, o próximo eleito assume a liderança e cada trabalhador envia seus trabalhos anteriores.
O líder deve agendar as tarefas da forma mais aleatória possível, a fim de tornar impossível para um trabalhador desonesto realizá-las o tempo todo. Nesse caso, as falhas dos trabalhadores e dos líderes são bem tratadas. Mas precisamos de outro mecanismo para garantir que os ataques sejam menos prováveis de acontecer.
- Cada mensagem trocada deverá ser autenticada (ex.: assinada). Quando uma prova falsa é produzida, qualquer membro pode denunciá-la e ganhar a pilha do trabalhador faltoso.
Não temos evidências até agora de que tal protocolo seja realmente seguro
Fontesethresear
