TL;DR
- **Qual é o processo de construção do SNARK? **
Problemas a serem provados-Circuitos aritméticos-R1CS-Polinômios
- **Por que converter para polinômio no final? **
Devido às características dos polinômios, o tempo de verificação é efetivamente reduzido e a simplicidade é alcançada.
- **Como alcançar conhecimento zero? **
Simplificando, no processo de derivação do polinômio, mais dois números aleatórios são selecionados, de modo que o polinômio derivado possa evitar que o verificador obtenha os coeficientes do polinômio original, ou seja, a entrada secreta do provador, de modo que para realizar ZK.
- **Como conseguir a não interação? **
Antes do início da prova, é introduzido um terceiro, ou seja, uma configuração confiável, que atribui ao verificador original a tarefa de escolher números aleatórios para a configuração confiável, realizando assim a não interação entre o verificador e o provador.
A tecnologia ZK atraiu muita atenção no campo Web3 nos últimos dois anos. A partir do Rollup, mais e mais projetos em diferentes faixas estão tentando usar a tecnologia ZK. Entre eles, SNARK e STARK são os dois termos mais ouvidos. Para entender melhor a aplicação da tecnologia ZK no estágio posterior, **este artigo simplificará a lógica de prova do SNARK de uma perspectiva não técnica e, em seguida, usará * * Scroll’s zk Rollup ** é usado como exemplo para ilustrar a operação do sistema de prova zk. **
O objetivo do artigo é explicar a lógica básica, que é fácil de ler. Ele tentará evitar o uso de terminologia e não entrará em detalhes como transformações matemáticas. Por favor, perdoe-me por quaisquer omissões.
Em janeiro de 2012, Alessandro Chiesa, professor da Universidade da Califórnia, em Berkeley, foi co-autor de um artigo sobre SNARK e propôs o termo zk-SNARK.
zk-SNARK, nome completo Zero-Knowledge-Succinct Non-Interactive Argument of Knowledge, é um sistema de prova que usa a tecnologia ZK. **Deve-se notar que SNARK é o nome de uma classe de esquemas, e existem muitos métodos de combinação diferentes que podem implementar SNARK. **
- Zero-Knowledge (Zero-Knowledge): O conteúdo que apenas o provador conhece ficará oculto, e ninguém mais poderá vê-lo, exceto o provador.
- Short (Sucinct): A prova gerada é pequena e o tempo de verificação é rápido.
- Non-Interactive (Non-Interactive): Há pouca ou nenhuma interação entre o provador e o verificador.
- Argumento: A verificação do verificador só é válida para o certificador com poder computacional limitado, pois o certificador com super poder computacional pode falsificar a prova, ou seja, o sistema tem confiabilidade computacional.
- Conhecimento: O provador só pode calcular a prova se souber alguma informação que o verificador não saiba.
O que o zk-SNARK precisa resolver é o “problema de verificação de cálculo”, ou seja, se o verificador pode verificar com eficiência os resultados do cálculo sem conhecer a privacidade do provador.
A seguir, usaremos o processo de construção simplificado do zk-SNARK para ilustrar como o sistema combina conhecimento zero para obter uma verificação eficiente. **
Construção Zk-SNARK
Transforme o problema a ser provado em um polinômio
Simplificando, a ideia do SNARK é converter a prova de que a afirmação é verdadeira ou não na prova de que a igualdade polinomial é verdadeira ou não.
Todo o processo de conversão: problemas a serem verificados ➡ circuito aritmético ➡ R1CS ➡ polinômio ➡ conversão entre polinômios
Pergunta a ser verificada ➡Circuito aritmético
Para provar se uma questão é verdadeira através do cálculo, a questão a ser provada deve primeiro ser transformada em um problema de cálculo, e qualquer cálculo pode ser descrito como um circuito aritmético.
Os circuitos aritméticos são geralmente compostos por constantes, “portas de adição” e “portas de multiplicação”.Através da superposição de portas, podemos construir polinômios complexos.
O polinômio construído pelo circuito aritmético na figura acima é: (Inp1+Inp2)*(-1) = Saída
O problema na realidade é extremamente complicado de se transformar em um circuito aritmético, podemos entendê-lo simplesmente como: introduza algum conteúdo, o conteúdo é transformado pelo circuito e por fim produza um resultado. Agora mesmo:
Com base no conceito de circuitos aritméticos, construímos um circuito aritmético para geração de provas, a saber:
O circuito contém dois conjuntos de entradas, a entrada pública x e a entrada secreta w. A entrada pública x significa que o conteúdo é um valor fixo do problema a ser provado, que é conhecido tanto pelo verificador quanto pelo provador, e a entrada secreta w significa que o conteúdo é conhecido apenas pelo provador.
O circuito aritmético que construímos é C( x, w ) = 0, ou seja, entrada x e w através do circuito, e o resultado final da saída é 0. Quando o provador e o verificador sabem que a saída do circuito é 0 e a entrada pública é x, o provador precisa provar que conhece a entrada secreta w.
Circuito aritmético ➡R1CS
Finalmente precisamos de um polinômio, mas o circuito aritmético não pode ser convertido diretamente em um polinômio, e R1CS é necessário como um intermediário entre os dois, então o circuito aritmético é convertido em R1CS primeiro.
R1CS, nome completo Rank-1 Constraints (sistema de restrição de primeira ordem), é uma linguagem para descrever circuitos, que é essencialmente uma equação matriz-vetor. Especificamente, R1CS é uma sequência de três vetores (a,b,c) e a solução para R1CS é um vetor s, onde s deve satisfazer a equação:
Entre eles, representa a operação de produto interno.
A conversão matemática específica aqui pode ser encontrada em Vatalik: Quadratic Arithmetic Programs: from Zero to Hero
Precisamos apenas saber que o papel de **R1CS é limitar a descrição de cada porta no circuito aritmético, de modo que os vetores entre cada porta satisfaçam a relação acima. **
R1CS➡Polinômio
Depois de obter o meio de R1CS, podemos convertê-lo em um equivalente polinomial.
Conversões equivalentes entre matrizes e polinômios podem ser realizadas conforme mostrado na figura a seguir:
polinomial
converter para matriz
De acordo com a natureza da transformação equivalente acima, para uma matriz que satisfaça R1CS, podemos usar o método de interpolação de Lagrange para restaurar cada coeficiente do polinômio. Com base nessa relação, podemos derivar a matriz R1CS como uma relação polinomial, a saber:
Nota: A, B, C representam um polinômio respectivamente
Um polinômio corresponde a uma restrição da matriz R1CS correspondente ao problema que queremos provar. Através da conversão acima, podemos saber que se os polinômios satisfazem a relação acima, significa que nossa matriz R1CS está correta, indicando assim que o provador está no circuito aritmético. A entrada secreta para também está correta.
Até este ponto, nosso problema é simplificado para: o verificador seleciona aleatoriamente um número x, e pede ao certificador para provar que A(x) * B(x)=C(x) é verdadeiro. significa que a entrada secreta do certificador está correta.
Conversão entre polinômios
Em circuitos aritméticos complexos, existem dezenas de milhares de portas e precisamos verificar se cada porta satisfaz a restrição R1CS. Em outras palavras, precisamos verificar a igualdade de A(x) * B(x)=C(x) várias vezes, mas a eficiência da verificação separada uma a uma é muito baixa. Como podemos verificar a exatidão de todas restrições de portão ao mesmo tempo?sexo?
Para facilitar o entendimento, introduzimos a P(x), seja P(x) = A(x) * B(x) – C(x)
Sabemos que qualquer polinômio pode ser decomposto em polinômios lineares, desde que tenha uma solução. Assim, dividimos P(x) em F(x) e H(x), a saber:
Então F(x) é público, o que significa que existe um H(x) = P(x)/F(x), então o polinômio que queremos verificar finalmente se transforma em:
A(x) * B(x) – C(x): Contém os coeficientes do polinômio, conhecidos apenas pelo provador, ou seja, a entrada secreta.
F(x): Um polinômio público conhecido tanto pelo verificador quanto pelo provador, ou seja, entrada pública.
H(x): O provador sabe por cálculo, mas o verificador é incognoscível.
**O problema final a ser provado é: a equação polinomial A(x) * B(x) – C(x) = F(x) * H(x), vale para todo x. **
Agora só é necessário verificar o polinômio uma vez para verificar se todas as restrições satisfazem as relações matriciais.
**Aqui completamos a transformação do problema a ser provado em um polinômio que só precisa ser verificado uma vez, percebendo a simplicidade do sistema. **
Mas a simplicidade dessa implementação é encurtar o tempo de verificação do verificador, então e quanto ao tamanho da prova?
**Simplificando, no protocolo de prova, é utilizada a estrutura de árvore Merkle, que efetivamente reduz o tamanho da prova. **
Após a conclusão de todo o processo de conversão, dois problemas surgirão naturalmente:
- Por que converter para polinômio?
Porque os polinômios permitem a simplicidade da prova. O problema da prova de conhecimento zero é verificar se os cálculos satisfazem várias restrições e os polinômios podem verificar várias restrições em um ponto. Em outras palavras, o verificador tem que verificar n vezes para confirmar o problema, mas agora só precisa verificar uma vez para confirmar a correção da prova com alta probabilidade.
- Por que dois polinômios A(x) * B(x) – C(x )= F(x) * H(x) podem ser estabelecidos pela verificação de um ponto no polinômio?
Isso é determinado pelas características dos polinômios, ou seja, o resultado do cálculo de um polinômio em qualquer ponto pode ser considerado como a representação de sua identidade única. Para dois polinômios, eles só se interceptarão em um número finito de pontos.
Para os dois polinômios acima de grau d: A(x) * B(x) – C(x) e F(x) * H(x), se não forem iguais, serão apenas no máximo d pontos Interseção, ou seja, as soluções em d pontos são as mesmas.
Depois de concluir a conversão polinomial, entraremos no estágio de prova polinomial.
Prove que o polinômio vale
Para fins de ilustração, usamos o polinômio P(x) = F(x) * H(x).
Agora, o problema que o provador quer provar é: em todo x, P(x) = F(x) * H(x).
O processo de verificação do polinômio acima pelo provador e pelo verificador é o seguinte:
- O verificador escolhe um ponto de desafio aleatório x, assumindo x = s;
- Após o provador receber s, calcule P(s) e H(s), e dê esses dois valores ao verificador;
- O verificador primeiro calcula F(s), depois calcula F(s) * H(s) e julga se F(s) * H(s) = P(s) é verdadeiro e, se for verdadeiro, a verificação é aprovada.
Mas se pensarmos bem, veremos que existem alguns problemas no processo acima:
- O provador pode conhecer a informação de toda a equação. Se ele receber um ponto aleatório s, ele pode calcular F(s) e então construir um par falso de P(x) e H(x), de modo que P(s ) = F(s) * H(s) para enganar o verificador.
- O provador não usa os s dados pelo verificador para calcular F(s) e H(s), mas calcula com outros valores para enganar o verificador.
- O valor recebido pelo verificador é calculado pela entrada pública e a entrada privada do provador.Se o verificador tiver um grande poder de computação, ele pode quebrar a entrada privada do provador.
Para resolver os problemas acima, fazemos as seguintes otimizações:
- Depois que o verificador seleciona um ponto aleatório s, ele executa a criptografia homomórfica em s. Criptografia homomórfica significa a solução calculada após a criptografia = a solução criptografada após o cálculo; nesta forma de criptografia, o provador pode calcular a solução, mas não pode construir falso P(x) e H(x).
- Quando o verificador escolhe o ponto de desafio s, outro parâmetro aleatório λ é selecionado para gerar uma relação linear adicional entre s e λ. O verificador envia s e λ após a criptografia homomórfica para o provador. O provador envia a prova de volta, e o verificador precisa verificar a relação entre o parâmetro aleatório λ e s além de verificar se a prova é verdadeira.
- **Visando o problema de que o verificador pode decifrar a entrada secreta, podemos introduzir o ZK. ** Observando toda a prova, podemos constatar que durante o processo de verificação, o provador envia apenas o valor do polinômio calculado para o verificador, e o verificador pode deduzir o coeficiente do polinômio através do valor, que é a entrada secreta do provador. Para evitar que o verificador retroceda, podemos selecionar mais dois números aleatórios e adicionar um conjunto de valores ao derivar os polinômios A, B e C de R1CS, de modo que o polinômio restaurado seja uma ordem a mais que o polinômio original , de modo que a verificação O leitor não pode obter as informações do polinômio original do polinômio criptografado para realizar ZK.
Após a otimização, descobrimos que o sistema de prova ainda requer interação entre o verificador e o provador. Como podemos obter a não interação?
Implemente não interativo
**Para alcançar a não interação, o SNARK introduz configurações confiáveis (configuração). **
Ou seja, antes do início da prova, o direito do verificador de escolher os pontos de desafio aleatórios é entregue a um terceiro confiável. Após o terceiro escolher o parâmetro aleatório λ, ele coloca o λ criptografado no circuito R1CS. forma, CRS (Common Reference String, string de referência pública) é gerado. O verificador pode obter seu próprio Sv do CRS, e o provador pode obter seu próprio Sp do CRS.
Deve-se notar que λ precisa ser destruído após a geração de Sv e Sp. Se λ for vazado, ele pode ser usado para falsificar transações por meio de verificação falsa.
Fluxo de trabalho zk-SNARK
Depois de entender o processo de construção do SNARK, com base no circuito aritmético que construímos que pode gerar provas, o processo de prova do zk-SNARK é o seguinte:
- Configuração:(circuito C, λ)= (Sv, Sp)
Através do circuito C e do parâmetro aleatório λ, são gerados os parâmetros aleatórios Sv e Sp usados pelo provador e verificador subseqüentes.
O provador calcula a prova Π por meio do parâmetro aleatório Sp, a entrada pública x e a entrada secreta w.
- Verifique(Sv,x,Π) == (∃ w st C(x,w))
O verificador verifica se C(x,w)=0 existe através do parâmetro aleatório Sv, entrada pública x e prova Π. Ao mesmo tempo, verifique se a prova é calculada pelo circuito C ou não.
Neste ponto, concluímos a explicação de todo o zk-SNARK. Vamos dar uma olhada no caso de aplicação real.
Caso: Use o zk Rollup do Scroll como exemplo
O papel do sistema de prova é permitir que o provador convença o verificador a acreditar em uma coisa;
Para o sistema de prova zk, é fazer o verificador acreditar que a Prova de Conhecimento Zero (prova de conhecimento zero) calculada pelo algoritmo zk é verdadeira.
Tomamos o zk Rollup de Scroll como um exemplo para ilustrar a operação do sistema de prova zk.
Rollup refere-se ao cálculo off-chain e à verificação on-chain. Para zk Rollup, depois que a transação é executada fora da cadeia, o provador precisa gerar um certificado zk para a nova raiz de estado gerada após a transação ser executada e, em seguida, passar o certificado para o contrato L1 Rollup para verificação na cadeia.
Deve-se notar que existem dois tipos de blocos no zk Rollup:
- Bloco L1 Rollup: o bloco submetido ao Ethereum
- Bloco L2: um bloco composto por transações enviadas por usuários em L2
A seguir está o fluxo de trabalho do Rollup zk do Scroll:
- O usuário inicia uma transação em L2, o Sequencer recupera a transação, executa a transação off-chain e gera um bloco L2 e um novo estado raiz; ao mesmo tempo, envia os dados da transação e o novo estado raiz para o contrato Rollup no Ethereum (o envio de dados de transação é para disponibilidade de dados);
- Quando o bloco L2 for gerado, o Coordenador receberá a trilha de execução do bloco do Sequencer, e então atribuirá aleatoriamente a trilha a qualquer Roller;
- O Roller converte a pista de execução recebida em circuitos, gera um certificado de validade para cada circuito e depois envia o certificado de volta ao Coordenador;
- A cada geração de k blocos L2, o Coordenador enviará uma tarefa de agregação para outro Roller para agregar as provas de k blocos em uma única prova agregada;
- O coordenador envia uma única prova de agregação ao contrato Rollup, e o contrato Rollup verifica a prova de agregação em combinação com a raiz do estado e os dados da transação enviados anteriormente. Se a verificação for aprovada, o bloco correspondente é considerado finalizado no Scroll.
Como pode ser visto no processo acima, o Roller é o provador no sistema e o contrato Rollup é o verificador. Roller gera uma prova zk para transações executadas fora da cadeia; o contrato Rollup verifica a prova e, se a verificação for aprovada, o contrato Rollup adotará diretamente a raiz de estado enviada como sua nova raiz de estado.
