Neste artigo, forneceremos uma breve visão geral de dois protocolos ZK-SNARK, Groth16 e Plonk. Destacaremos suas características-chave e, em seguida, os compararemos em termos de usabilidade, desempenho e segurança.
Contexto sobre ZK-SNARK
O protocolo de Prova de Conhecimento Zero (ZKP) consiste em duas partes: o proponente (P) que deseja convencer outra parte, e o verificador (V), de que uma afirmação x é verdadeira, usando uma testemunha secreta w, sem revelar w ao verificador ou a qualquer outra pessoa.
Como exemplo, suponha que eu queira assegurar a alguém que minha conta bancária contém fundos suficientes, mas não estou disposto a divulgar o saldo exato. Nesse cenário, a afirmação pública "o saldo da minha conta excede 10 milhões de dólares" serve como a declaração pública, enquanto meu saldo real funciona como a testemunha privada ou entrada secreta.
Os requisitos básicos a seguir são necessários para cada protocolo ZKP:
Completude: P honesto sempre convencerá V honesto.
Validade: P desonesto não convencerá V honesto.
Zero-conhecimento: V desonesto não aprende nada além da verdade da afirmação.
Para integração na blockchain, o protocolo ZKP deve atender às demandas de ter um tamanho de prova curto e manter uma complexidade de tempo razoável para ambos, proponente e verificador. Além disso, dados os desafios de escalabilidade e desempenho na tecnologia blockchain, minimizar a interação entre o proponente e o verificador, especialmente evitando múltiplas rodadas, é altamente preferível. Idealmente, estamos interessados em um protocolo onde o proponente gera uma prova e a transmite para o verificador em uma única rodada. Para abordar essas questões, resultou em uma nova categoria de protocolo ZKP, chamada Argumento Não Interativo e Sucinto de Conhecimento (ZK-SNARK).
Eliminar múltiplas rodadas de comunicação não apenas melhora o desempenho do protocolo, mas também elimina a necessidade de ambas as partes estarem disponíveis simultaneamente. Para alcançar essa redução de rodadas, duas abordagens são comumente usadas: o Modelo do Oráculo Aleatório e a Cadeia de Referência Comum (CRS). Vamos nos concentrar na abordagem da Cadeia de Referência Comum (CRS), que foi empregada pelos protocolos Groth16 e Plonk. Em teoria, uma terceira parte confiável e honesta é responsável por gerar um valor aleatório "r" e usá-lo para criar parâmetros CRS, incluindo a chave de prova "pk" e a chave de verificação "vk". É importante observar que qualquer pessoa com acesso à aleatoriedade "r" pode potencialmente gerar uma prova fraudulenta. Para aprimorar a segurança do protocolo ZK-SNARK, muitas vezes se utiliza a Computação Multi-Partidária, onde todas as partes calculam colaborativamente uma função sem a necessidade de uma autoridade terceira confiável.
De acordo com este artigo, contanto que haja pelo menos uma parte honesta, os parâmetros finais são seguros.
Nota: todos os parâmetros seguros gerados pela cerimônia MPC devem ser removidos por um processo seguro.
Vamos definir as propriedades de SNARK como fizemos para o protocolo ZK:
Sucinto: o tamanho da prova é muito pequeno em comparação com o tamanho da afirmação ou da testemunha.
Não interativo: não há necessidade de várias interações entre P e V.
Argumento de conhecimento: P desonesto não pode convencer V honesto a menos que ele conheça alguma testemunha secreta.
Zero-conhecimento: não revelar mais do que já é de conhecimento público.
Para resumir, ZK-SNARK consiste em três fases: Realização de uma configuração confiável por meio de um protocolo MPC para gerar chaves de prova e verificação, geração de prova pelo proponente usando a chave de prova, entrada pública e entrada secreta (testemunha), e verificação da prova pelo verificador.
CRS(aleatoriedade r, afirmação x) → (pk, vk)
Proponente(pk, afirmação x, testemunha w) → prova pi
Verificador(vk, pi, afirmação x) → aceitar ou rejeitar prova pi
Groth16
Em 2016, Groth introduziu um protocolo ZK-SNARK, construído com base em um conjunto de equações polinomiais e criptografia de emparelhamento assimétrica. SNARKs baseados em emparelhamento seguem um paradigma simples em que o proponente calcula um número de elementos do grupo usando operações de grupo genéricas e o verificador verifica a prova usando um número de equações de produto de emparelhamento.
No esquema Groth16, qualquer programa F(x,w) = y com entrada pública x e testemunha privada w é convertido em um circuito aritmético C.
Para provar a correção do circuito C, devemos verificar a correção de cada portão. Para fazer isso, groth16 usa Linguagens Aritméticas Quadráticas (QAP) para codificar o circuito. A intuição por trás da codificação do circuito C em QAP é que definimos o polinômio P(z)=Ui(z).Vi(z)-Wi(z) que codifica todas as equações de portão de multiplicação, onde os polinômios Ui, Vi e Wi representam a esquerda, direita e saída do i-ésimo portão sobre (a1,…, am) que representam os valores do fio do circuito.
Agora definimos um polinômio alvo T(z)=(z-r1)(z-r2)…(z-rn) onde r1, …, rn são variáveis aleatórias, e n denota o número de portões de multiplicação em nosso circuito. A ideia básica é que o polinômio P(z) foi definido de tal forma que é divisível por T(z). Isso significa que há um polinômio H(z) tal que P(z)=H(z)T(z). Portanto, se houver uma parte confiável que avalie esses polinômios (U(z), V(z), W(z)) em um ponto aleatório como s, colocando-os em CRS, então o proponente pode fazer uma prova e o verificador é capaz de verificá-la.
Plonk
O protocolo PlonK aborda as questões de configuração confiável única e não-palatável introduzindo SRS universal e atualizável. Em outras palavras, vários programas podem compartilhar CRS, desde que o tamanho de seus circuitos não ultrapasse o limite do CRS.
Da mesma forma que Groth16, em Plonk, cada programa é convertido em um circuito aritmético de portas multiplicativas e aditivas. No entanto, a maneira como Plonk prova a correção e consistência do circuito é diferente. Para provar a correção do circuito de Plonk, precisamos provar a validade de cada restrição de porta, bem como a relação de porta. Além da verificação da equação polinomial, é adotado um método matemático de argumento de permutação para verificar a relação de restrição entre as portas, ou seja, a restrição de cópia.
Comparação de Eficiência
PlonK fornece duas variantes, uma com grau combinado de polinômios de 9(n+a), e outra com 11(n+a). A primeira tem um tamanho de prova maior, mas uma redução de cerca de 10% na computação do proponente em comparação com a segunda. Aqui, n representa portões de multiplicação, e 'a' representa portões de adição no circuito.
A comparação de desempenho e segurança entre Groth16 e duas variantes de Plonk é mostrada abaixo.
Análise da Complexidade da Prova
Em circuitos comuns, a proporção entre portas aditivas e portas multiplicativas é 2:1. Sob essa suposição de circuito, isso significa que PlonK é 2,25 vezes pior que Groth16 no tempo de prova. Com a capacidade de geração de prova ser executada offline e fora da cadeia, não há necessidade de se preocupar com a complexidade de tempo de geração de prova. No entanto, o tamanho da prova deve ser levado em consideração, afetando o tamanho da transação e, consequentemente, a taxa de transferência da rede blockchain. Lembre-se de que cada elemento de grupo é um par de pontos x e y em F.
Tamanho da prova Groth16: 2G1.(2 F) + 1 G2 (conta 4 elementos F) = 6F
Tamanho da prova Plonk: 9*G1+ 7F* = 16*F*
Assumindo que cada elemento tem 256 bits. De acordo com o post de Vitalik, o tamanho da prova Groth16 seria de cerca de 200 bytes em um nível estimado de 128 bits de segurança, enquanto o Plonk requer cerca de 500–1000 bytes para o mesmo nível de segurança.
Análise da Complexidade da Verificação
O algoritmo de verificação de Groth16 é linear no tamanho de entrada pública, enquanto Plonk requer um número fixo de computações exponenciais e de emparelhamento.
Nota: precisa de uma implementação de benchmark para estimar o custo de gás.
Conclusão
Teoricamente, tanto Groth16 quanto Plonk dependem da suposição de problemas matemáticos e não são resistentes a quantum. No entanto, Plonk requer suposições de segurança mais fracas do que Groth16. Em relação ao tamanho da prova, Plonk tem um tamanho de prova de cerca de 2x-5x o de Groth16, no entanto, Plonk tem uma grande vantagem de SRS universal e atualizável sobre Groth16. Consequentemente, a probabilidade de que a configuração tenha sido comprometida por colisão é reduzida, e não há necessidade de reexecutar a cerimônia MPC para quaisquer alterações no programa.
Este artigo foi escrito por Mehri Rezaei e traduzido por Adriano P. de Araujo. O original em inglês pode ser encontrado aqui.
Top comments (0)