Como projetar um esquema de recursão de prova melhor?
Quase todos os problemas encontrados nas trilhas zkRollup e zkEVM são essencialmente problemas algorítmicos. A principal razão pela qual a aceleração de hardware ZK-Proof é frequentemente mencionada é que os algoritmos atuais são geralmente lentos.
Para não cair na situação constrangedora de “o algoritmo não basta, o hardware serve para compensar”, devemos resolver o problema a partir da essência do algoritmo. Projetando uma recursão requintada à prova de entrega esquema é a chave para resolver este problema.
Com o desenvolvimento contínuo de contratos inteligentes, mais e mais aplicações Web3 estão surgindo gradualmente, e o volume de transações da Camada 1 tradicional, como Ethereum, está aumentando rapidamente, e o congestionamento pode ocorrer a qualquer momento. Como obter maior eficiência e ao mesmo tempo garantir a segurança proporcionada pela Camada 1 tornou-se um problema urgente a ser resolvido.
Para Ethereum, zkRollup usa o algoritmo de prova de conhecimento zero como componente subjacente para mover os cálculos caros que originalmente precisavam ser realizados na camada 1 fora da cadeia e fornecer prova de execução correta para a cadeia. A trilha inclui projetos como StarkWare, zkSync, rolagem, e Tecnologia Fox.
Na verdade, no projeto do zkRollup, existem requisitos muito elevados de eficiência: espera-se que o valor da prova submetido seja pequeno o suficiente, possa reduzir a quantidade de cálculo da Camada 1. Para obter um comprimento de prova suficientemente pequeno, cada O projeto zkRollup está melhorando o algoritmo e o design da arquitetura. Por exemplo, a Fox desenvolveu seu algoritmo de prova FOAKS em combinação com o mais recente algoritmo de prova de conhecimento zero para obter o tempo e a duração da prova ideais.
Além disso, na etapa de verificação das provas, o meio mais trivial é gerar provas linearmente e verificá-las sequencialmente. Para melhorar a eficiência, a primeira coisa que todos pensam é agrupar várias provas em uma prova, comumente chamada de Agregação de Provas.
Falando intuitivamente, a verificação das provas geradas pelo zkEVM é um processo linear, e o Verificador precisa verificar cada valor de prova gerado por vez. No entanto, a eficiência deste método de verificação é relativamente baixa e a sobrecarga de comunicação é relativamente grande. Para o cenário zkRollup, uma sobrecarga maior do lado do verificador significa mais cálculos da Camada 1, o que também levará a taxas de gás mais altas.
Vejamos primeiro um exemplo: Alice quer provar ao mundo que foi ao Fox Park de 1 a 7 deste mês. Por isso, ela poderá tirar uma foto no parque com o jornal do dia todos os dias, de 1 a 7, e essas sete fotos servirão de prova.
Colocar sete fotos diretamente em um envelope no exemplo acima é agregação de provas em um sentido intuitivo, que corresponde a conectar diferentes provas e verificá-las linearmente em sequência, ou seja, verificar primeiro a primeira prova e depois verificar a segunda prova.
Duas provas e provas subsequentes. O problema é que esta abordagem não alterará o tamanho da prova nem o tempo da prova, o que é o mesmo que provar e verificar um por um. Se você deseja obter compactação de espaço logarítmico, você precisa usar a Recursão de Prova mencionada abaixo.
Esquema de recursão de prova usado por Halo2 e STARK
Para explicar melhor o que é uma prova recursiva, voltemos ao exemplo acima.
As sete fotos de Alice são sete provas. Agora considere mesclá-las, para que Alice possa tirar uma foto na 1ª, tirar essa foto na 2ª e o jornal na 2ª, e tirar a foto na 2ª e o jornal na 3ª foto. Por analogia, Alice tirou a última foto do dia 7 com a foto do dia 6 e o jornal do dia 7, e outros amigos podem verificar que estão do dia 1 ao 7 quando virem a última foto do dia 7.
Alice foi toda para o parque. Pode-se ver que as sete fotos de prova anteriores foram compactadas em uma. E uma habilidade fundamental nesse processo são “fotos contendo fotos”, o que equivale a aninhar recursivamente fotos anteriores em fotos subsequentes. É diferente de juntar muitas fotos e tirar uma foto só.
O truque de prova recursiva do zkRollup pode compactar bastante o tamanho da prova. Especificamente, cada transação gerará uma prova. Definimos o circuito de cálculo da transação original como C0, P0 como a prova de correção de C0 e V0 como o processo de cálculo para verificação de P0.
O provador também converte V0 no circuito correspondente, denotado como C0′. Atualmente, para o processo de cálculo da prova C1 de outra transação, os circuitos de C0′ e C1 podem ser mesclados. Desta forma, uma vez verificada a prova de correção P1 do circuito mesclado, equivale a verificar os dois circuitos acima ao mesmo tempo. A exatidão da transação, ou seja, a compactação, é alcançada.
Olhando novamente para o processo acima, pode-se descobrir que o princípio da compressão é converter o processo de verificação e prova em um circuito e então gerar “prova para a prova”, portanto, nesta perspectiva, é uma operação que pode recorrer continuamente para baixo, também conhecida como prova recursiva.
O esquema de Recursão de Prova adotado por Halo2 e STARK pode gerar provas em paralelo e combinar múltiplas provas, de modo que a exatidão de múltiplas execuções de transações possa ser verificada enquanto verifica um valor de prova, o que pode comprimir a sobrecarga de cálculo, melhorando assim muito a eficiência do sistema.
No entanto, tal otimização ainda permanece no nível acima do algoritmo específico de prova de conhecimento zero. Para melhorar ainda mais a eficiência, precisamos de otimização e inovação de nível inferior. O algoritmo FOAKS desenvolvido por Fox faz isso aplicando ideias recursivas dentro de uma prova até este ponto.
Esquema de recursão de prova usado por FOAKS
Fox Tech é um projeto zkRollup baseado em zkEVM. Em seu sistema de prova também é utilizada a técnica de prova recursiva, mas a conotação é diferente do método recursivo mencionado acima. A principal diferença é que Fox utiliza a ideia de Recursão dentro de uma prova. Para expressar a ideia central da prova recursiva usada por Fox para reduzir continuamente o problema a ser provado até que o problema reduzido seja suficientemente simples, precisamos dar outro exemplo.
No exemplo acima, Alice prova que foi ao Fox Park em um determinado dia tirando uma foto, então Bob apresenta uma sugestão diferente. Ele pensa que o problema de provar que Alice esteve no parque pode ser reduzido a provar que o telemóvel de Alice esteve no parque. E comprovar essa questão pode se resumir a comprovar que a localização do celular de Alice está dentro do escopo do parque.
Portanto, para comprovar que Alice esteve no parque, ela só precisa enviar a localização com seu celular enquanto estiver no parque. Desta forma, o tamanho da prova é alterado de uma foto (dados de dimensões muito altas) para dados tridimensionais (latitude, longitude e tempo), economizando custos efetivamente.
Este exemplo não é totalmente apropriado porque algumas pessoas podem questionar que o telemóvel de Alice tenha estado no Fox Park não significa que Alice tenha estado lá, mas em situações reais, este processo de redução é estritamente matemático.
Especificamente, o uso da prova recursiva de Fox é a recursão no nível do circuito. Ao realizar a prova de conhecimento zero, escreveremos o problema a ser provado em um circuito e então calcularemos algumas equações que precisam ser satisfeitas por meio do circuito. E em vez de mostrar que estas equações são satisfeitas, escrevemos estas equações como circuitos novamente, e assim por diante, até que finalmente as equações para provar a satisfação se tornam suficientemente simples para que possamos facilmente prová-la diretamente.
A partir desse processo, podemos ver que isso está mais próximo do significado de “recursão”. Vale ressaltar que nem todos os algoritmos podem utilizar esta técnica recursiva, assumindo que cada recursão mudará a prova de complexidade O(n) em uma prova de O(f(n)) e o cálculo do próprio processo recursivo.
A complexidade é O(g(n)), então a complexidade computacional total se torna O1(n)=O(f(n))+O(g(n)) após uma recursão e O2(n) após duas recursões) =O(f(f(n)))+O(g(n))+O(g(f(n))), depois de três vezes é O3(n)=O(f(f(f(n) ) )))+O(g(n))+O(g(f(n)))+O(g(f(f(n)))),…, e assim por diante.
Portanto, tal técnica recursiva pode funcionar efetivamente apenas quando as duas funções de f e g correspondentes às características do algoritmo satisfazem Ok(n)
Conclusão
A complexidade da prova sempre foi uma das chaves mais importantes na aplicação de provas de conhecimento zero. A natureza da complexidade da prova se tornará cada vez mais importante à medida que as coisas a serem provadas se tornarem cada vez mais complexas, especialmente em aplicações ZK gigantes como o zkEVM.
Neste cenário, a complexidade da prova terá um impacto decisivo no desempenho do produto e na experiência do utilizador. Entre as muitas maneiras de reduzir a complexidade da prova final, a otimização do algoritmo central é a mais importante.
A Fox projetou um esquema de prova de entrega requintado baseado no algoritmo mais avançado e usa essa tecnologia para criar o zkEVM mais adequado. Espera-se que o algoritmo ZK-FOAKS se torne o líder de desempenho na indústria zkRollup.
AVISO LEGAL: As informações neste site são fornecidas como comentários gerais do mercado e não constituem aconselhamento de investimento. Nós encorajamos você a fazer sua própria pesquisa antes de investir.
Junte-se a nós para acompanhar as novidades: https://linktr.ee/coincu
Harold
coincu Novidades
Autor
Recursos Educacionais
Como projetar um esquema de recursão de prova melhor?
Quase todos os problemas encontrados nas trilhas zkRollup e zkEVM são essencialmente problemas algorítmicos. A principal razão pela qual a aceleração de hardware ZK-Proof é frequentemente mencionada é que os algoritmos atuais são geralmente lentos.
Para não cair na situação constrangedora de “o algoritmo não basta, o hardware serve para compensar”, devemos resolver o problema a partir da essência do algoritmo. Projetando uma recursão requintada à prova de entrega esquema é a chave para resolver este problema.
Com o desenvolvimento contínuo de contratos inteligentes, mais e mais aplicações Web3 estão surgindo gradualmente, e o volume de transações da Camada 1 tradicional, como Ethereum, está aumentando rapidamente, e o congestionamento pode ocorrer a qualquer momento. Como obter maior eficiência e ao mesmo tempo garantir a segurança proporcionada pela Camada 1 tornou-se um problema urgente a ser resolvido.
Para Ethereum, zkRollup usa o algoritmo de prova de conhecimento zero como componente subjacente para mover os cálculos caros que originalmente precisavam ser realizados na camada 1 fora da cadeia e fornecer prova de execução correta para a cadeia. A trilha inclui projetos como StarkWare, zkSync, rolagem, e Tecnologia Fox.
Na verdade, no projeto do zkRollup, existem requisitos muito elevados de eficiência: espera-se que o valor da prova submetido seja pequeno o suficiente, possa reduzir a quantidade de cálculo da Camada 1. Para obter um comprimento de prova suficientemente pequeno, cada O projeto zkRollup está melhorando o algoritmo e o design da arquitetura. Por exemplo, a Fox desenvolveu seu algoritmo de prova FOAKS em combinação com o mais recente algoritmo de prova de conhecimento zero para obter o tempo e a duração da prova ideais.
Além disso, na etapa de verificação das provas, o meio mais trivial é gerar provas linearmente e verificá-las sequencialmente. Para melhorar a eficiência, a primeira coisa que todos pensam é agrupar várias provas em uma prova, comumente chamada de Agregação de Provas.
Falando intuitivamente, a verificação das provas geradas pelo zkEVM é um processo linear, e o Verificador precisa verificar cada valor de prova gerado por vez. No entanto, a eficiência deste método de verificação é relativamente baixa e a sobrecarga de comunicação é relativamente grande. Para o cenário zkRollup, uma sobrecarga maior do lado do verificador significa mais cálculos da Camada 1, o que também levará a taxas de gás mais altas.
Vejamos primeiro um exemplo: Alice quer provar ao mundo que foi ao Fox Park de 1 a 7 deste mês. Por isso, ela poderá tirar uma foto no parque com o jornal do dia todos os dias, de 1 a 7, e essas sete fotos servirão de prova.
Colocar sete fotos diretamente em um envelope no exemplo acima é agregação de provas em um sentido intuitivo, que corresponde a conectar diferentes provas e verificá-las linearmente em sequência, ou seja, verificar primeiro a primeira prova e depois verificar a segunda prova.
Duas provas e provas subsequentes. O problema é que esta abordagem não alterará o tamanho da prova nem o tempo da prova, o que é o mesmo que provar e verificar um por um. Se você deseja obter compactação de espaço logarítmico, você precisa usar a Recursão de Prova mencionada abaixo.
Esquema de recursão de prova usado por Halo2 e STARK
Para explicar melhor o que é uma prova recursiva, voltemos ao exemplo acima.
As sete fotos de Alice são sete provas. Agora considere mesclá-las, para que Alice possa tirar uma foto na 1ª, tirar essa foto na 2ª e o jornal na 2ª, e tirar a foto na 2ª e o jornal na 3ª foto. Por analogia, Alice tirou a última foto do dia 7 com a foto do dia 6 e o jornal do dia 7, e outros amigos podem verificar que estão do dia 1 ao 7 quando virem a última foto do dia 7.
Alice foi toda para o parque. Pode-se ver que as sete fotos de prova anteriores foram compactadas em uma. E uma habilidade fundamental nesse processo são “fotos contendo fotos”, o que equivale a aninhar recursivamente fotos anteriores em fotos subsequentes. É diferente de juntar muitas fotos e tirar uma foto só.
O truque de prova recursiva do zkRollup pode compactar bastante o tamanho da prova. Especificamente, cada transação gerará uma prova. Definimos o circuito de cálculo da transação original como C0, P0 como a prova de correção de C0 e V0 como o processo de cálculo para verificação de P0.
O provador também converte V0 no circuito correspondente, denotado como C0′. Atualmente, para o processo de cálculo da prova C1 de outra transação, os circuitos de C0′ e C1 podem ser mesclados. Desta forma, uma vez verificada a prova de correção P1 do circuito mesclado, equivale a verificar os dois circuitos acima ao mesmo tempo. A exatidão da transação, ou seja, a compactação, é alcançada.
Olhando novamente para o processo acima, pode-se descobrir que o princípio da compressão é converter o processo de verificação e prova em um circuito e então gerar “prova para a prova”, portanto, nesta perspectiva, é uma operação que pode recorrer continuamente para baixo, também conhecida como prova recursiva.
O esquema de Recursão de Prova adotado por Halo2 e STARK pode gerar provas em paralelo e combinar múltiplas provas, de modo que a exatidão de múltiplas execuções de transações possa ser verificada enquanto verifica um valor de prova, o que pode comprimir a sobrecarga de cálculo, melhorando assim muito a eficiência do sistema.
No entanto, tal otimização ainda permanece no nível acima do algoritmo específico de prova de conhecimento zero. Para melhorar ainda mais a eficiência, precisamos de otimização e inovação de nível inferior. O algoritmo FOAKS desenvolvido por Fox faz isso aplicando ideias recursivas dentro de uma prova até este ponto.
Esquema de recursão de prova usado por FOAKS
Fox Tech é um projeto zkRollup baseado em zkEVM. Em seu sistema de prova também é utilizada a técnica de prova recursiva, mas a conotação é diferente do método recursivo mencionado acima. A principal diferença é que Fox utiliza a ideia de Recursão dentro de uma prova. Para expressar a ideia central da prova recursiva usada por Fox para reduzir continuamente o problema a ser provado até que o problema reduzido seja suficientemente simples, precisamos dar outro exemplo.
No exemplo acima, Alice prova que foi ao Fox Park em um determinado dia tirando uma foto, então Bob apresenta uma sugestão diferente. Ele pensa que o problema de provar que Alice esteve no parque pode ser reduzido a provar que o telemóvel de Alice esteve no parque. E comprovar essa questão pode se resumir a comprovar que a localização do celular de Alice está dentro do escopo do parque.
Portanto, para comprovar que Alice esteve no parque, ela só precisa enviar a localização com seu celular enquanto estiver no parque. Desta forma, o tamanho da prova é alterado de uma foto (dados de dimensões muito altas) para dados tridimensionais (latitude, longitude e tempo), economizando custos efetivamente.
Este exemplo não é totalmente apropriado porque algumas pessoas podem questionar que o telemóvel de Alice tenha estado no Fox Park não significa que Alice tenha estado lá, mas em situações reais, este processo de redução é estritamente matemático.
Especificamente, o uso da prova recursiva de Fox é a recursão no nível do circuito. Ao realizar a prova de conhecimento zero, escreveremos o problema a ser provado em um circuito e então calcularemos algumas equações que precisam ser satisfeitas por meio do circuito. E em vez de mostrar que estas equações são satisfeitas, escrevemos estas equações como circuitos novamente, e assim por diante, até que finalmente as equações para provar a satisfação se tornam suficientemente simples para que possamos facilmente prová-la diretamente.
A partir desse processo, podemos ver que isso está mais próximo do significado de “recursão”. Vale ressaltar que nem todos os algoritmos podem utilizar esta técnica recursiva, assumindo que cada recursão mudará a prova de complexidade O(n) em uma prova de O(f(n)) e o cálculo do próprio processo recursivo.
A complexidade é O(g(n)), então a complexidade computacional total se torna O1(n)=O(f(n))+O(g(n)) após uma recursão e O2(n) após duas recursões) =O(f(f(n)))+O(g(n))+O(g(f(n))), depois de três vezes é O3(n)=O(f(f(f(n) ) )))+O(g(n))+O(g(f(n)))+O(g(f(f(n)))),…, e assim por diante.
Portanto, tal técnica recursiva pode funcionar efetivamente apenas quando as duas funções de f e g correspondentes às características do algoritmo satisfazem Ok(n)
Conclusão
A complexidade da prova sempre foi uma das chaves mais importantes na aplicação de provas de conhecimento zero. A natureza da complexidade da prova se tornará cada vez mais importante à medida que as coisas a serem provadas se tornarem cada vez mais complexas, especialmente em aplicações ZK gigantes como o zkEVM.
Neste cenário, a complexidade da prova terá um impacto decisivo no desempenho do produto e na experiência do utilizador. Entre as muitas maneiras de reduzir a complexidade da prova final, a otimização do algoritmo central é a mais importante.
A Fox projetou um esquema de prova de entrega requintado baseado no algoritmo mais avançado e usa essa tecnologia para criar o zkEVM mais adequado. Espera-se que o algoritmo ZK-FOAKS se torne o líder de desempenho na indústria zkRollup.
AVISO LEGAL: As informações neste site são fornecidas como comentários gerais do mercado e não constituem aconselhamento de investimento. Nós encorajamos você a fazer sua própria pesquisa antes de investir.
Junte-se a nós para acompanhar as novidades: https://linktr.ee/coincu
Harold
coincu Novidades
Outras postagens
Artigos relacionados
Novidades
FSOCIETY ameaça vazamento massivo de dados da Bitfinex: 400,000 usuários em risco
Novidades
Os agricultores do LayerZero Sybil Airdrop agora estão sendo drasticamente bloqueados por fraude
Novidades
Lançamento do Disappointment Clouds Friend Tech v2, apesar dos novos recursos interessantes
Novidades
Novos tokens MakerDAO são lançados para promover a governança do protocolo
Novidades
Investimento da Pantera Capital TON direcionado para aprimorar as capacidades de pagamento P2P
Novidades
Presidente da SEC acusado de engano em relação à legitimidade da Ethereum!
Novidades
Roger Ver é preso na Espanha, acusado de fraude fiscal de US$ 48 milhões
Novidades
Erro de endereço resulta em perda de US$ 68 milhões no WBTC, vítima cai em esquema de phishing
Principais projetos
Os 10 melhores bots de criptografia de telegrama em 2024
Recursos Educacionais
Mineração de Bitcoin: Quanto tempo leva para extrair 1 Bitcoin?
Recursos Educacionais
Previsões eleitorais nos EUA: os efeitos e a importância do novo presidente dos EUA
Recursos Educacionais
Potenciais candidatos às eleições dos EUA em 2024: quem vencerá?
Novidades
