Há algum tempo eu estava traduzindo um livro sobre tecnologia à prova de conhecimento zero. O conteúdo básico foi traduzido no final do mês passado. A tradução demorou muito mais do que eu esperava. No momento, estamos discutindo alguns erros administrativos do livro com o autor e preparando a versão final.
De qualquer forma, finalmente tenho tempo para ver algo novo. Vamos começar com o algoritmo Nova ~
Informações relacionadas ao algoritmo Nova
Três informações podem ajudar a entender o algoritmo Nova:
Artigo Nova:
Novos ataques potenciais e correções correspondentes:
Resumo da compreensão dos possíveis ataques do Nova:
Este artigo é uma compreensão e um resumo das informações acima. **Algumas das imagens neste artigo vêm das informações acima e não serão rotuladas uma por uma neste artigo. **
Comece com IVC
O algoritmo Nova é um novo algoritmo à prova de conhecimento zero para IVC (Incrementally Verifiable Computation). IVC, ou seja, a mesma função calcula iterativamente a saída anterior como a próxima entrada. O processo de cálculo iterativo da função F é o seguinte:
z0 é a entrada inicial e o resultado gerado pelo cálculo da função F é usado como entrada da próxima função F.
Relaxe R1CS e compromisso com o Slack R1CS
Como todos sabemos, R1CS é uma representação de restrições de circuito em tecnologia à prova de conhecimento zero. R1CS relaxado pode ser visto como uma forma estendida de R1CS. Com base no R1CS, um escalar u e um vetor de erro E são adicionados. Uma instância de R1CS relaxado é representada por (E, u, x).
O compromisso relaxado R1CS compromete os vetores E e W com base no R1CS relaxado. Uma instância de um compromisso de folga R1CS é representada por (\bar{E}, u, \bar{W}, x), onde x e u são variáveis públicas.
Extensão de R1CS para R1CS relaxado para esquema de dobramento. Observe que da perspectiva do R1CS relaxado, o R1CS é um caso especial dele. Em outras palavras, o R1CS também é um R1CS folga "especial".
Esquema de dobramento
Intuitivamente falando, um esquema de dobramento para uma relação R é "colapsar" duas instâncias em conformidade com a relação R em uma nova instância da relação composta R. Slack R1CS/Relax Commitment R1CS pode realizar dobras semelhantes. O processo de dobramento é semelhante para ambos. O esquema de dobramento do Slack Commitment R1CS é o seguinte:
Todo o esquema de dobramento consiste em 4 etapas. Na primeira etapa, o provador P envia um compromisso \bar{T} do item cruzado T ao verificador. Na segunda etapa, o verificador envia um desafio aleatório r ao provador. O terceiro passo é o desdobramento do compromisso que tanto o provador quanto o verificador precisam cumprir. Na quarta etapa, o provador atua sozinho e dobra os vetores E e W das duas instâncias.
Função aumentada F' (Função Argumentada)
Esquema de recolhimento, a instância R1CS recolhida é relaxada. Então, quais são os cálculos comprovados por esses exemplos relaxados do R1CS? Obviamente, esses cálculos incluem cálculos dobráveis. Esses cálculos não são apenas a função F nos cálculos IVC, eles também são chamados de funções aumentadas F'. O cálculo da função aumentada F' consiste principalmente em duas partes:
Função 1/F na VCI
2/ Cálculo dobrável da instância R1CS
Aparência ideal
Com o entendimento acima, você pode imaginar o processo de dobramento:
Entre eles, circuito é o circuito correspondente à função aumentada F'. acc{1,2,3,4,5,6} é uma instância R1CS de compromisso de folga. O circuito possui dois cálculos: 1/Relaxe o dobramento da instância de compromisso R1CS, como acc1+acc2->acc3. 2/Calcule a função F, alterando o estado de estado1 para estado2, e depois de estado2 para estado3, etc.
Observe que o circuito correspondente à função aumentada F' é ele próprio uma instância R1CS, que pode ser expressa como uma instância R1CS relaxada. Isso é acc4 e acc6 na imagem. "resumir" é converter uma instância R1CS folgada em uma instância R1CS comprometida com folga.
Olhando atentamente para a entrada do segundo circuito, acc3 é a instância R1CS de compromisso relaxado após a dobra, e acc4 é a instância R1CS de compromisso relaxado que prova que acc3 é o resultado de dobramento correto. Essas duas instâncias entrarão na próxima dobragem e gerarão acc5. Você pode imaginar que se acc3 e acc4 são instâncias R1CS de compromisso de folga satisfatória, isso significa que acc3 é dobrado a partir de duas instâncias R1CS de compromisso de folga satisfatória. Em outras palavras, acc1 e acc2 são compromissos de folga satisfatórios.Instância R1CS. Esse tipo de confiabilidade pode ser deduzido “adiante” passo a passo, provando assim que o cálculo da função F em cada circuito está correto. Em geral, através da satisfatibilidade de duas instâncias R1CS de compromisso de folga correspondentes a um determinado circuito, todos os cálculos IVC anteriores podem ser comprovados como corretos.
Aparência real
Amigos familiarizados com provas de conhecimento zero sabem que curvas elípticas são frequentemente usadas em esquemas de comprometimento polinomial. O comprometimento polinomial correspondente no domínio escalar é representado pelo domínio base da curva elíptica. Os circuitos R1CS são geralmente representados pelo domínio escalar. Observe com atenção, o "resumo" na imagem acima envolve conversão de domínio. Ou seja, se você deseja dobrar a instância R1CS de compromisso de folga correspondente a um circuito, você deve “dobrá-la” em outro circuito. Neste momento, um ciclo de curva elíptica precisa ser introduzido. Entre duas ou mais curvas elípticas, o domínio escalar de uma curva é igual ao domínio base da outra curva. Coincidentemente, o domínio escalar desta curva é o mesmo que o domínio base da curva anterior. Usando esse loop de curva elíptica, a "aparência ideal" pode ser alcançada:
Todo o processo de dobramento é dividido em dois circuitos de dobramento. A parte superior pode ser chamada de dobra do Circuito 1 e a parte inferior pode ser chamada de dobra do Circuito 2. Uma representação formal da relação entre os dois circuitos está na página 8 do artigo "Potenciais Ataques à Nova e Correções Correspondentes". U representa a instância dobrada e u representa a instância relaxada correspondente a uma instância R1CS. Observe que o Circuito 1 recolhe a instância R1CS de compromisso de folga correspondente ao Circuito 2, enquanto o Circuito 2 recolhe a instância R1CS de compromisso de folga correspondente ao Circuito 1. O principal objetivo do Circuito 2 é colapsar a instância R1CS de compromisso de folga correspondente ao Circuito1, e o cálculo da função em seu circuito não tem sentido. Em vez disso, a função F é implementada no Circuito 1. Combinado com a "aparência ideal", podemos adivinhar aproximadamente a satisfatibilidade de U{i+2}^2, u{i+2}^1, u{i+2}^2, U{i+2}^1 é uma parte importante da prova.
Porque o “circuito” é cortado em duas partes, e o respectivo circuito é dobrado no outro circuito. Existem vários problemas de ligação entre instâncias: a ligação entre as instâncias u e U e a ligação das instâncias u que passam entre dois circuitos. Para resolver esses problemas de ligação, x_0/x_1 variáveis públicas são introduzidas no circuito, onde x_1 especifica a instância U da saída do circuito ligada à instância u e a saída da função F atual (para simplificar a estrutura do circuito, não refletida na figura). Você pensa que, se o resultado H_1 da instância U for introduzido no circuito, se a instância u for satisfatória, x_0/x_1 é real e confiável, ou seja, está "ligado" a U. x_0 estabelece a relação de ligação entre a entrada u e U, e x_1 estabelece a relação de ligação entre a saída u e U.
Por exemplo, quando u{i+1}^1 é usado como entrada da segunda metade do circuito, ele passa pelo Circuito 2 e sua saída u{i+1}^2.x0 = u{i+1 }^1.x1, então, quando inserido na parte superior do circuito, se u{i+1}^2 puder ser satisfeito, então seu x_0 deve ser igual ao resultado de H1 de U_{i +1}^2. Isso é verificado no Circuito 1. Desta forma, é garantido que a instância correta seja passada entre os dois circuitos.
Comprovante de IVC
Para provar que o IVC é calculado corretamente em uma determinada iteração, as seguintes informações precisam ser provadas logicamente:
Além de provar que quatro instâncias podem ser satisfeitas, também é necessário provar a relação de ligação entre dois x1, conforme mostra a figura a seguir:
Se esta informação está correta, requer implementação de circuito de prova adicional. Ou seja, a prova do cálculo do IVC é uma prova do circuito. É concebível que, se for um cálculo com muitas iterações, essas iterações originalmente precisem ser realizadas no circuito, uma por uma, mas agora apenas quatro instâncias do circuito precisam ser verificadas quanto à satisfatibilidade e às relações de ligação. A melhoria de desempenho é enorme.
Correção de Ataque e Algoritmo
Vendo a imagem acima, tenho uma intuição: sinto que as instâncias dos circuitos superior e inferior estão “separadas” e não têm ligação. Na verdade, é assim que o ataque está estruturado.
U_i^1 e U{i+1}^2 forjados, embora sejam forjados, são instâncias satisfatórias. Forje u{i+1}^1, modifique x_0 e x_1 para corresponder à instância U forjada. Obviamente, a instância u{i+1}^1 não está satisfeita. Embora não esteja satisfeito, o circuito do Circuito 2 ainda pode ser satisfeito, mas a instância de saída U{i+1}^1 não está satisfeita. Se u{i+1}^2 for construído com sucesso, o Circuito 1 pode construir u{i+2}^1 e U_{i+2}^2 satisfatórios e satisfazer a relação de ligação de x1. Desta forma, metade da prova final de falsificação é construída primeiro. Através da simetria, a instância de saída da metade inferior pode ser construída. Ao “unir” os resultados das duas construções, a prova do cálculo do IVC pode ser forjada.
A lógica de verificação revisada é a seguinte:
O Capítulo 6 do artigo "Ataques Potenciais ao Nova e Correções Correspondentes" fornece uma análise de segurança detalhada. Amigos interessados podem verificar o artigo original por conta própria.
A ideia básica do Nova é dobrar instâncias de circuito por meio de um esquema de dobramento. A lógica é bastante complicada e requer uma reflexão cuidadosa sobre o processo de dobramento do circuito e as relações de ligação no circuito.
Uma palavra para descrevê-lo: Absoluto ~
Ver original
Esta página pode conter conteúdo de terceiros, que é fornecido apenas para fins informativos (não para representações/garantias) e não deve ser considerada como um endosso de suas opiniões pela Gate nem como aconselhamento financeiro ou profissional. Consulte a Isenção de responsabilidade para obter detalhes.
Progresso revolucionário na tecnologia de prova de conhecimento zero: uma exploração aprofundada do algoritmo Nova
Há algum tempo eu estava traduzindo um livro sobre tecnologia à prova de conhecimento zero. O conteúdo básico foi traduzido no final do mês passado. A tradução demorou muito mais do que eu esperava. No momento, estamos discutindo alguns erros administrativos do livro com o autor e preparando a versão final.
De qualquer forma, finalmente tenho tempo para ver algo novo. Vamos começar com o algoritmo Nova ~
Informações relacionadas ao algoritmo Nova
Três informações podem ajudar a entender o algoritmo Nova:
Este artigo é uma compreensão e um resumo das informações acima. **Algumas das imagens neste artigo vêm das informações acima e não serão rotuladas uma por uma neste artigo. **
Comece com IVC
O algoritmo Nova é um novo algoritmo à prova de conhecimento zero para IVC (Incrementally Verifiable Computation). IVC, ou seja, a mesma função calcula iterativamente a saída anterior como a próxima entrada. O processo de cálculo iterativo da função F é o seguinte:
z0 é a entrada inicial e o resultado gerado pelo cálculo da função F é usado como entrada da próxima função F.
Relaxe R1CS e compromisso com o Slack R1CS
Como todos sabemos, R1CS é uma representação de restrições de circuito em tecnologia à prova de conhecimento zero. R1CS relaxado pode ser visto como uma forma estendida de R1CS. Com base no R1CS, um escalar u e um vetor de erro E são adicionados. Uma instância de R1CS relaxado é representada por (E, u, x).
O compromisso relaxado R1CS compromete os vetores E e W com base no R1CS relaxado. Uma instância de um compromisso de folga R1CS é representada por (\bar{E}, u, \bar{W}, x), onde x e u são variáveis públicas.
Extensão de R1CS para R1CS relaxado para esquema de dobramento. Observe que da perspectiva do R1CS relaxado, o R1CS é um caso especial dele. Em outras palavras, o R1CS também é um R1CS folga "especial".
Esquema de dobramento
Intuitivamente falando, um esquema de dobramento para uma relação R é "colapsar" duas instâncias em conformidade com a relação R em uma nova instância da relação composta R. Slack R1CS/Relax Commitment R1CS pode realizar dobras semelhantes. O processo de dobramento é semelhante para ambos. O esquema de dobramento do Slack Commitment R1CS é o seguinte:
Todo o esquema de dobramento consiste em 4 etapas. Na primeira etapa, o provador P envia um compromisso \bar{T} do item cruzado T ao verificador. Na segunda etapa, o verificador envia um desafio aleatório r ao provador. O terceiro passo é o desdobramento do compromisso que tanto o provador quanto o verificador precisam cumprir. Na quarta etapa, o provador atua sozinho e dobra os vetores E e W das duas instâncias.
Função aumentada F' (Função Argumentada)
Esquema de recolhimento, a instância R1CS recolhida é relaxada. Então, quais são os cálculos comprovados por esses exemplos relaxados do R1CS? Obviamente, esses cálculos incluem cálculos dobráveis. Esses cálculos não são apenas a função F nos cálculos IVC, eles também são chamados de funções aumentadas F'. O cálculo da função aumentada F' consiste principalmente em duas partes:
Função 1/F na VCI
2/ Cálculo dobrável da instância R1CS
Aparência ideal
Com o entendimento acima, você pode imaginar o processo de dobramento:
Entre eles, circuito é o circuito correspondente à função aumentada F'. acc{1,2,3,4,5,6} é uma instância R1CS de compromisso de folga. O circuito possui dois cálculos: 1/Relaxe o dobramento da instância de compromisso R1CS, como acc1+acc2->acc3. 2/Calcule a função F, alterando o estado de estado1 para estado2, e depois de estado2 para estado3, etc.
Observe que o circuito correspondente à função aumentada F' é ele próprio uma instância R1CS, que pode ser expressa como uma instância R1CS relaxada. Isso é acc4 e acc6 na imagem. "resumir" é converter uma instância R1CS folgada em uma instância R1CS comprometida com folga.
Olhando atentamente para a entrada do segundo circuito, acc3 é a instância R1CS de compromisso relaxado após a dobra, e acc4 é a instância R1CS de compromisso relaxado que prova que acc3 é o resultado de dobramento correto. Essas duas instâncias entrarão na próxima dobragem e gerarão acc5. Você pode imaginar que se acc3 e acc4 são instâncias R1CS de compromisso de folga satisfatória, isso significa que acc3 é dobrado a partir de duas instâncias R1CS de compromisso de folga satisfatória. Em outras palavras, acc1 e acc2 são compromissos de folga satisfatórios.Instância R1CS. Esse tipo de confiabilidade pode ser deduzido “adiante” passo a passo, provando assim que o cálculo da função F em cada circuito está correto. Em geral, através da satisfatibilidade de duas instâncias R1CS de compromisso de folga correspondentes a um determinado circuito, todos os cálculos IVC anteriores podem ser comprovados como corretos.
Aparência real
Amigos familiarizados com provas de conhecimento zero sabem que curvas elípticas são frequentemente usadas em esquemas de comprometimento polinomial. O comprometimento polinomial correspondente no domínio escalar é representado pelo domínio base da curva elíptica. Os circuitos R1CS são geralmente representados pelo domínio escalar. Observe com atenção, o "resumo" na imagem acima envolve conversão de domínio. Ou seja, se você deseja dobrar a instância R1CS de compromisso de folga correspondente a um circuito, você deve “dobrá-la” em outro circuito. Neste momento, um ciclo de curva elíptica precisa ser introduzido. Entre duas ou mais curvas elípticas, o domínio escalar de uma curva é igual ao domínio base da outra curva. Coincidentemente, o domínio escalar desta curva é o mesmo que o domínio base da curva anterior. Usando esse loop de curva elíptica, a "aparência ideal" pode ser alcançada:
Todo o processo de dobramento é dividido em dois circuitos de dobramento. A parte superior pode ser chamada de dobra do Circuito 1 e a parte inferior pode ser chamada de dobra do Circuito 2. Uma representação formal da relação entre os dois circuitos está na página 8 do artigo "Potenciais Ataques à Nova e Correções Correspondentes". U representa a instância dobrada e u representa a instância relaxada correspondente a uma instância R1CS. Observe que o Circuito 1 recolhe a instância R1CS de compromisso de folga correspondente ao Circuito 2, enquanto o Circuito 2 recolhe a instância R1CS de compromisso de folga correspondente ao Circuito 1. O principal objetivo do Circuito 2 é colapsar a instância R1CS de compromisso de folga correspondente ao Circuito1, e o cálculo da função em seu circuito não tem sentido. Em vez disso, a função F é implementada no Circuito 1. Combinado com a "aparência ideal", podemos adivinhar aproximadamente a satisfatibilidade de U{i+2}^2, u{i+2}^1, u{i+2}^2, U{i+2}^1 é uma parte importante da prova.
Porque o “circuito” é cortado em duas partes, e o respectivo circuito é dobrado no outro circuito. Existem vários problemas de ligação entre instâncias: a ligação entre as instâncias u e U e a ligação das instâncias u que passam entre dois circuitos. Para resolver esses problemas de ligação, x_0/x_1 variáveis públicas são introduzidas no circuito, onde x_1 especifica a instância U da saída do circuito ligada à instância u e a saída da função F atual (para simplificar a estrutura do circuito, não refletida na figura). Você pensa que, se o resultado H_1 da instância U for introduzido no circuito, se a instância u for satisfatória, x_0/x_1 é real e confiável, ou seja, está "ligado" a U. x_0 estabelece a relação de ligação entre a entrada u e U, e x_1 estabelece a relação de ligação entre a saída u e U.
Por exemplo, quando u{i+1}^1 é usado como entrada da segunda metade do circuito, ele passa pelo Circuito 2 e sua saída u{i+1}^2.x0 = u{i+1 }^1.x1, então, quando inserido na parte superior do circuito, se u{i+1}^2 puder ser satisfeito, então seu x_0 deve ser igual ao resultado de H1 de U_{i +1}^2. Isso é verificado no Circuito 1. Desta forma, é garantido que a instância correta seja passada entre os dois circuitos.
Comprovante de IVC
Para provar que o IVC é calculado corretamente em uma determinada iteração, as seguintes informações precisam ser provadas logicamente:
Além de provar que quatro instâncias podem ser satisfeitas, também é necessário provar a relação de ligação entre dois x1, conforme mostra a figura a seguir:
Se esta informação está correta, requer implementação de circuito de prova adicional. Ou seja, a prova do cálculo do IVC é uma prova do circuito. É concebível que, se for um cálculo com muitas iterações, essas iterações originalmente precisem ser realizadas no circuito, uma por uma, mas agora apenas quatro instâncias do circuito precisam ser verificadas quanto à satisfatibilidade e às relações de ligação. A melhoria de desempenho é enorme.
Correção de Ataque e Algoritmo
Vendo a imagem acima, tenho uma intuição: sinto que as instâncias dos circuitos superior e inferior estão “separadas” e não têm ligação. Na verdade, é assim que o ataque está estruturado.
U_i^1 e U{i+1}^2 forjados, embora sejam forjados, são instâncias satisfatórias. Forje u{i+1}^1, modifique x_0 e x_1 para corresponder à instância U forjada. Obviamente, a instância u{i+1}^1 não está satisfeita. Embora não esteja satisfeito, o circuito do Circuito 2 ainda pode ser satisfeito, mas a instância de saída U{i+1}^1 não está satisfeita. Se u{i+1}^2 for construído com sucesso, o Circuito 1 pode construir u{i+2}^1 e U_{i+2}^2 satisfatórios e satisfazer a relação de ligação de x1. Desta forma, metade da prova final de falsificação é construída primeiro. Através da simetria, a instância de saída da metade inferior pode ser construída. Ao “unir” os resultados das duas construções, a prova do cálculo do IVC pode ser forjada.
A lógica de verificação revisada é a seguinte:
O Capítulo 6 do artigo "Ataques Potenciais ao Nova e Correções Correspondentes" fornece uma análise de segurança detalhada. Amigos interessados podem verificar o artigo original por conta própria.
A ideia básica do Nova é dobrar instâncias de circuito por meio de um esquema de dobramento. A lógica é bastante complicada e requer uma reflexão cuidadosa sobre o processo de dobramento do circuito e as relações de ligação no circuito.
Uma palavra para descrevê-lo: Absoluto ~