原文：Sãos e salvos — Um mergulho profundo na segurança da STARK
Tradução e revisão: "Starknet Chinese Community"
Fatos rápidos em destaque
O STARK não interativo é derivado do Interactive Oracle Proof (IOP), compilado em uma prova não interativa no modelo oracle aleatório.
Este artigo explica as atualizações mais recentes da documentação do ethSTARK e fornece uma análise abrangente e detalhada da segurança do protocolo ethSTARK no modelo Oracle aleatório.
Explicação detalhada da segurança STARK
O sistema de prova STARK, ou argumento de conhecimento transparente e escalável, é uma ferramenta poderosa para a integridade computacional: permite a verificação sem confiança da exatidão dos cálculos realizados em dados públicos. Neste artigo, iremos nos aprofundar na segurança fornecida pelas provas STARK, defini-las e explorar técnicas para provar a segurança dos esquemas.
(Leia a seção 6 da documentação do ethSTARK (versão 1.2) para obter detalhes, bem como o importante e abrangente trabalho independente sobre este tópico de Block et al.).
O que estamos tentando alcançar com a análise de segurança? Queremos evitar "ataques bem-sucedidos" ao sistema STARK causados por uma declaração falsa e pela prova STARK aceita pelo validador STARK em resposta a essa declaração (falsa). Como as deturpações são perigosas e podem assumir todos os tamanhos e formas, queremos estar seguros contra todas elas. Qualquer afirmação falsa, mesmo tão trivial como 1+1=3, quando combinada com uma prova STARK aceita por um validador STARK, será considerada um ataque bem-sucedido ao sistema. (Aqueles com experiência em criptografia podem estar interessados em saber que o STARK também pode satisfazer conceitos de segurança mais fortes, como confiabilidade do conhecimento, mas por uma questão de simplicidade, este artigo se concentrará em casos simples sobre confiabilidade).
Como definimos formalmente a segurança de um sistema STARK? Determinamos isso analisando o “erro de confiabilidade”. O "erro de confiabilidade" mede aproximadamente o "custo" esperado que custaria a um invasor lançar um ataque bem-sucedido (ou seja, encontrar uma prova STARK para uma declaração falsa, mas a prova é aceita pelo validador STARK). Matematicamente falando, o erro de confiabilidade é uma função (t) cuja entrada é o parâmetro de tempo t, representando o tempo computacional que o atacante está disposto a gastar para lançar um ataque, e a saída é a probabilidade de o ataque do atacante ter sucesso (encontrada para declarações falsas provas convincentes). Quanto maior o “custo” que o invasor está disposto a gastar, maior será sua probabilidade de sucesso.
Até agora, definimos a segurança do STARK como uma função (t), que é diferente da forma como todos discutem segurança no Twitter criptografado todos os dias. No Twitter, você poderá ouvir algo assim: “Esta solução tem 96 bits de segurança”. Como isso se traduz em nossa definição de segurança? Não há uma resposta única para isso, pois as pessoas entendem “x bits de segurança” de maneira um pouco diferente:
Interpretado estritamente, isso significa que para qualquer t entre 1 e 2⁹⁶, o erro de confiabilidade é (t) 2⁹⁶. Um invasor com tempo de execução de 2⁹⁶ ou menos tem uma probabilidade de sucesso muito pequena, inferior a 2⁹⁶, que é menos de 1 em um bilhão vezes 1 em um bilhão.
Uma interpretação mais flexível e talvez mais comum é que a segurança de 96 bits significa que, para qualquer t, existe uma situação em que t/(t) 2⁹⁶. Isto significa que a probabilidade de sucesso é (inversamente) linear com o tempo de execução. Se o invasor tiver um tempo de execução de 2⁸⁶, sua probabilidade de sucesso será de no máximo 2¹⁰.
Neste artigo, discutiremos a segunda opção.
Do IOP ao STARK com segurança de 96 bits
Então, como provamos que uma solução possui 96 bits de segurança? Para responder a esta pergunta, precisamos compreender a estrutura de alto nível sobre a qual a STARK está construída. STARK consiste em três partes principais: IOP (Interactive Oracle Proof), árvore Merkle e hash Fiat-Shamir; nosso foco principal é o IOP. Uma vez especificadas essas partes componentes, podemos compilá-las para gerar um STARK. Examinaremos esses componentes detalhadamente, incluindo o que são e como se encaixam.
O primeiro componente que revisaremos é o IOP: o IOP é semelhante a uma prova interativa padrão, onde o provador e o validador interagem por múltiplas rodadas (estamos limitados a protocolos de moedas públicas, onde o validador envia apenas desafios aleatórios ao provador). Em um IOP, o verificador não lê completamente a mensagem do provador, mas em vez disso faz uma amostragem de uma pequena porção dos bits da mensagem de cada provador. É por isso que o STARK compilado posteriormente alcança simplicidade.
Dado o IOP, como faço para construir um STARK a partir dele? As mensagens do provador podem ser muito longas (na verdade, são mais longas que o próprio cálculo). Para compactar essas informações, usamos árvores Merkle. Uma árvore Merkle é uma árvore hash binária na qual cada nó folha representa uma consulta ou resposta no IOP. As raízes são a promessa de toda a mensagem. Quando um validador deseja ler um local específico em uma mensagem, o provador fornece o valor desse local e o caminho de verificação. O validador pode então usar esse caminho para verificar se o valor está correto. O validador IOP lê apenas uma pequena quantidade de informações de localização das informações do provador. Portanto, protocolos concisos (protocolos com baixo volume de comunicação) podem ser implementados utilizando árvores Merkle.
Rodadas de compressão
Podemos escolher o STARK interativo, mas para simplificar o processo de geração do STARK, geralmente escolhemos o STARK não interativo, para que o validador não precise esperar por informações externas ao construir o STARK. Na verdade, é assim que todos os sistemas STARK atuais são implantados e como o protocolo ethSTARK é construído. STARKs não interativos também são um caso especial de SNARKs transparentes (transparente significa que nenhuma configuração confiável é necessária para instanciá-los; "Protocolo Arthur Merlin" ou "IOP de moeda pública"). Para fazer isso, a etapa final é aplicar o algoritmo Fiat-Shamir para compactar múltiplas rodadas de interações em uma única mensagem, que chamamos de prova STARK. A transformação Fiat-Shamir é um método de converter um protocolo interativo em um protocolo não interativo. O provador simula um protocolo interativo enquanto conversa com a função hash. Para derivar o desafio aleatório para a rodada i, o provador faz hash para o registro parcial da rodada i e interpreta a saída como o próximo desafio.
Isto garante que o provador não possa alterar a sua resposta após o desafio ser gerado. No entanto, o provador de trapaça tem alguns novos caminhos estratégicos que não estão disponíveis em IOPs interativos. O provador pode regenerar o desafio do validador modificando as informações do último provador, para que obtenha um novo registro e, portanto, um novo desafio. Acontece que o conceito de confiabilidade padrão do IOP é insuficiente para comprovar a segurança da conversão Fiat-Shamir.
Por exemplo, tenha um IOP de 96 rodadas e adicione o seguinte hack ao validador: se o primeiro bit da aleatoriedade do validador for 0 em cada uma das 96 rodadas, então o validador irá aceitá-lo (sem ver nenhuma prova). Podemos ver que adicionar este hack ao validador apenas adiciona um termo de 2⁹⁶ ao erro de confiabilidade do IOP. No entanto, após a transformação Fiat-Shamir, um invasor pode facilmente modificar as informações do provador para garantir que cada valor de hash comece com 0, invadindo assim o sistema em um tempo muito curto. Fique tranquilo, este cenário terrível é apenas um exemplo teórico e não se aplica aos STARKs implantados. Então, vamos ver por que nosso STARK é seguro, afinal. Resumindo, mostraremos que o atacante executa no máximo t passos, e a probabilidade de o ataque ter sucesso é no máximo (t) t 2⁹⁶.
IOP e confiabilidade rodada a rodada
A segurança do STARK depende do seu IOP subjacente. Mas o que significa um IOP ter 96 bits de segurança? Por definição padrão, o erro de confiabilidade do IOP é 2⁹⁶: isso significa que a probabilidade de qualquer invasor (independentemente do tempo de execução) conseguir enganar o validador é de no máximo 2-96. Contudo, como discutimos, a confiabilidade do IOP é apenas um dos três componentes, o que não é suficiente para obter 96 bits de segurança de um STARK compilado a partir de todas as três etapas. Em contraste, a segurança do STARK compilado é comprovada assumindo que o STARK tem um erro de confiabilidade rodada a rodada de 96 bits (uma definição semelhante chamada confiabilidade de recuperação de estado às vezes é usada).
Intuitivamente, “solidez rodada por rodada” significa que cada rodada tem 96 bits de segurança, não apenas o protocolo inteiro. Para ser mais específico, a confiabilidade rodada a rodada refere-se à existência de um predicado que pode obter parte do registro do protocolo e nos dizer se esse registro é “enganoso”: “registro vazio” não é “enganoso”, e quando E o registro completo é "enganoso" somente se aceito pelo validador. Finalmente, para qualquer registro parcial que não esteja “falsificando” o validador, a probabilidade de o registro se tornar “falsificado” na próxima rodada é de no máximo 2⁹⁶. Se houver um predicado com essas propriedades, dizemos que o protocolo possui 96 bits de confiabilidade rodada a rodada (esse predicado não requer computação eficiente).
Em muitos casos, as pessoas analisam apenas a fiabilidade da PIO e não a sua fiabilidade entre rondas. É certo que é difícil pensar em um exemplo (exceto para exemplos fabricados) de um IOP que tenha confiabilidade padrão, mas não confiabilidade rodada a rodada. No entanto, ao derivar limites de segurança específicos, podem surgir diferenças entre os dois e cada bit conta. Portanto, para obter limites rígidos e específicos, é necessária uma análise rigorosa da confiabilidade rodada a rodada do PIO. Isso é exatamente o que estamos fazendo com o protocolo FRI e o IOP ethSTARK no qual o IOP STARK se baseia. A análise em si está longe de ser trivial e foge ao escopo deste artigo. Usando a nova análise, podemos definir parâmetros precisos para a nossa prova.
A confiabilidade rodada a rodada realmente nos dá a garantia de que precisamos. O provador pode regenerar o desafio várias vezes, mas sabemos que em qualquer rodada a probabilidade de gerar um registro fraudulento é 2⁹⁶. Portanto, se o provador tiver t vezes (medido no número de chamadas de hash), então ele pode tentar em na maioria das vezes para obter um registro enganoso, o que limita sua probabilidade de sucesso a (t) t 2⁹⁶.
Adicione todos os itens de erro
Finalmente, para que tudo isto seja verdade, precisamos de garantir que o provador não pode alterar a árvore Merkle. Podemos mostrar que, desde que o provador não encontre colisões na função hash, ele não poderá trapacear na árvore Merkle. A probabilidade de um invasor encontrar uma colisão usando chamadas t (função hash aleatória) é no máximo t2/2, que é o comprimento de saída da função hash (causada pelo "Paradoxo do Aniversário"). É por isso que precisamos definir o função hash O comprimento é o dobro da segurança necessária. Portanto, se tivermos uma função hash com comprimento de saída de 192 e um IOP com confiabilidade rodada a rodada de 96 bits, obteremos um STARK compilado que é confiável Erro sexual (t )=t2-⁹⁶ + t2 2¹⁹⁶. Como t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵, este esquema tem 95 bits de sexo de segurança.
Resumir
Em conjunto, o STARK fornece um método poderoso para verificar sem confiança a exatidão dos cálculos realizados em dados públicos. A segurança do STARK é geralmente medida pelo “erro de confiabilidade”, que representa a probabilidade de um invasor fornecer com sucesso uma declaração falsa e convencer o validador com uma prova. Para atingir o nível de segurança exigido, como 96 bits, o IOP subjacente deve atender à confiabilidade rodada a rodada para garantir que altos níveis de segurança sejam mantidos em cada rodada. Analisamos a confiabilidade rodada a rodada dos IOPs nos quais nosso STARK se baseia para derivar limites de segurança específicos.
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.
Uma análise aprofundada da segurança completa do STARK
原文：Sãos e salvos — Um mergulho profundo na segurança da STARK
Tradução e revisão: "Starknet Chinese Community"
Fatos rápidos em destaque
Explicação detalhada da segurança STARK
O sistema de prova STARK, ou argumento de conhecimento transparente e escalável, é uma ferramenta poderosa para a integridade computacional: permite a verificação sem confiança da exatidão dos cálculos realizados em dados públicos. Neste artigo, iremos nos aprofundar na segurança fornecida pelas provas STARK, defini-las e explorar técnicas para provar a segurança dos esquemas.
(Leia a seção 6 da documentação do ethSTARK (versão 1.2) para obter detalhes, bem como o importante e abrangente trabalho independente sobre este tópico de Block et al.).
O que estamos tentando alcançar com a análise de segurança? Queremos evitar "ataques bem-sucedidos" ao sistema STARK causados por uma declaração falsa e pela prova STARK aceita pelo validador STARK em resposta a essa declaração (falsa). Como as deturpações são perigosas e podem assumir todos os tamanhos e formas, queremos estar seguros contra todas elas. Qualquer afirmação falsa, mesmo tão trivial como 1+1=3, quando combinada com uma prova STARK aceita por um validador STARK, será considerada um ataque bem-sucedido ao sistema. (Aqueles com experiência em criptografia podem estar interessados em saber que o STARK também pode satisfazer conceitos de segurança mais fortes, como confiabilidade do conhecimento, mas por uma questão de simplicidade, este artigo se concentrará em casos simples sobre confiabilidade).
Como definimos formalmente a segurança de um sistema STARK? Determinamos isso analisando o “erro de confiabilidade”. O "erro de confiabilidade" mede aproximadamente o "custo" esperado que custaria a um invasor lançar um ataque bem-sucedido (ou seja, encontrar uma prova STARK para uma declaração falsa, mas a prova é aceita pelo validador STARK). Matematicamente falando, o erro de confiabilidade é uma função (t) cuja entrada é o parâmetro de tempo t, representando o tempo computacional que o atacante está disposto a gastar para lançar um ataque, e a saída é a probabilidade de o ataque do atacante ter sucesso (encontrada para declarações falsas provas convincentes). Quanto maior o “custo” que o invasor está disposto a gastar, maior será sua probabilidade de sucesso.
Até agora, definimos a segurança do STARK como uma função (t), que é diferente da forma como todos discutem segurança no Twitter criptografado todos os dias. No Twitter, você poderá ouvir algo assim: “Esta solução tem 96 bits de segurança”. Como isso se traduz em nossa definição de segurança? Não há uma resposta única para isso, pois as pessoas entendem “x bits de segurança” de maneira um pouco diferente:
Neste artigo, discutiremos a segunda opção.
Do IOP ao STARK com segurança de 96 bits
Então, como provamos que uma solução possui 96 bits de segurança? Para responder a esta pergunta, precisamos compreender a estrutura de alto nível sobre a qual a STARK está construída. STARK consiste em três partes principais: IOP (Interactive Oracle Proof), árvore Merkle e hash Fiat-Shamir; nosso foco principal é o IOP. Uma vez especificadas essas partes componentes, podemos compilá-las para gerar um STARK. Examinaremos esses componentes detalhadamente, incluindo o que são e como se encaixam.
O primeiro componente que revisaremos é o IOP: o IOP é semelhante a uma prova interativa padrão, onde o provador e o validador interagem por múltiplas rodadas (estamos limitados a protocolos de moedas públicas, onde o validador envia apenas desafios aleatórios ao provador). Em um IOP, o verificador não lê completamente a mensagem do provador, mas em vez disso faz uma amostragem de uma pequena porção dos bits da mensagem de cada provador. É por isso que o STARK compilado posteriormente alcança simplicidade.
Dado o IOP, como faço para construir um STARK a partir dele? As mensagens do provador podem ser muito longas (na verdade, são mais longas que o próprio cálculo). Para compactar essas informações, usamos árvores Merkle. Uma árvore Merkle é uma árvore hash binária na qual cada nó folha representa uma consulta ou resposta no IOP. As raízes são a promessa de toda a mensagem. Quando um validador deseja ler um local específico em uma mensagem, o provador fornece o valor desse local e o caminho de verificação. O validador pode então usar esse caminho para verificar se o valor está correto. O validador IOP lê apenas uma pequena quantidade de informações de localização das informações do provador. Portanto, protocolos concisos (protocolos com baixo volume de comunicação) podem ser implementados utilizando árvores Merkle.
Rodadas de compressão
Podemos escolher o STARK interativo, mas para simplificar o processo de geração do STARK, geralmente escolhemos o STARK não interativo, para que o validador não precise esperar por informações externas ao construir o STARK. Na verdade, é assim que todos os sistemas STARK atuais são implantados e como o protocolo ethSTARK é construído. STARKs não interativos também são um caso especial de SNARKs transparentes (transparente significa que nenhuma configuração confiável é necessária para instanciá-los; "Protocolo Arthur Merlin" ou "IOP de moeda pública"). Para fazer isso, a etapa final é aplicar o algoritmo Fiat-Shamir para compactar múltiplas rodadas de interações em uma única mensagem, que chamamos de prova STARK. A transformação Fiat-Shamir é um método de converter um protocolo interativo em um protocolo não interativo. O provador simula um protocolo interativo enquanto conversa com a função hash. Para derivar o desafio aleatório para a rodada i, o provador faz hash para o registro parcial da rodada i e interpreta a saída como o próximo desafio.
Isto garante que o provador não possa alterar a sua resposta após o desafio ser gerado. No entanto, o provador de trapaça tem alguns novos caminhos estratégicos que não estão disponíveis em IOPs interativos. O provador pode regenerar o desafio do validador modificando as informações do último provador, para que obtenha um novo registro e, portanto, um novo desafio. Acontece que o conceito de confiabilidade padrão do IOP é insuficiente para comprovar a segurança da conversão Fiat-Shamir.
Por exemplo, tenha um IOP de 96 rodadas e adicione o seguinte hack ao validador: se o primeiro bit da aleatoriedade do validador for 0 em cada uma das 96 rodadas, então o validador irá aceitá-lo (sem ver nenhuma prova). Podemos ver que adicionar este hack ao validador apenas adiciona um termo de 2⁹⁶ ao erro de confiabilidade do IOP. No entanto, após a transformação Fiat-Shamir, um invasor pode facilmente modificar as informações do provador para garantir que cada valor de hash comece com 0, invadindo assim o sistema em um tempo muito curto. Fique tranquilo, este cenário terrível é apenas um exemplo teórico e não se aplica aos STARKs implantados. Então, vamos ver por que nosso STARK é seguro, afinal. Resumindo, mostraremos que o atacante executa no máximo t passos, e a probabilidade de o ataque ter sucesso é no máximo (t) t 2⁹⁶.
IOP e confiabilidade rodada a rodada
A segurança do STARK depende do seu IOP subjacente. Mas o que significa um IOP ter 96 bits de segurança? Por definição padrão, o erro de confiabilidade do IOP é 2⁹⁶: isso significa que a probabilidade de qualquer invasor (independentemente do tempo de execução) conseguir enganar o validador é de no máximo 2-96. Contudo, como discutimos, a confiabilidade do IOP é apenas um dos três componentes, o que não é suficiente para obter 96 bits de segurança de um STARK compilado a partir de todas as três etapas. Em contraste, a segurança do STARK compilado é comprovada assumindo que o STARK tem um erro de confiabilidade rodada a rodada de 96 bits (uma definição semelhante chamada confiabilidade de recuperação de estado às vezes é usada).
Intuitivamente, “solidez rodada por rodada” significa que cada rodada tem 96 bits de segurança, não apenas o protocolo inteiro. Para ser mais específico, a confiabilidade rodada a rodada refere-se à existência de um predicado que pode obter parte do registro do protocolo e nos dizer se esse registro é “enganoso”: “registro vazio” não é “enganoso”, e quando E o registro completo é "enganoso" somente se aceito pelo validador. Finalmente, para qualquer registro parcial que não esteja “falsificando” o validador, a probabilidade de o registro se tornar “falsificado” na próxima rodada é de no máximo 2⁹⁶. Se houver um predicado com essas propriedades, dizemos que o protocolo possui 96 bits de confiabilidade rodada a rodada (esse predicado não requer computação eficiente).
Em muitos casos, as pessoas analisam apenas a fiabilidade da PIO e não a sua fiabilidade entre rondas. É certo que é difícil pensar em um exemplo (exceto para exemplos fabricados) de um IOP que tenha confiabilidade padrão, mas não confiabilidade rodada a rodada. No entanto, ao derivar limites de segurança específicos, podem surgir diferenças entre os dois e cada bit conta. Portanto, para obter limites rígidos e específicos, é necessária uma análise rigorosa da confiabilidade rodada a rodada do PIO. Isso é exatamente o que estamos fazendo com o protocolo FRI e o IOP ethSTARK no qual o IOP STARK se baseia. A análise em si está longe de ser trivial e foge ao escopo deste artigo. Usando a nova análise, podemos definir parâmetros precisos para a nossa prova.
A confiabilidade rodada a rodada realmente nos dá a garantia de que precisamos. O provador pode regenerar o desafio várias vezes, mas sabemos que em qualquer rodada a probabilidade de gerar um registro fraudulento é 2⁹⁶. Portanto, se o provador tiver t vezes (medido no número de chamadas de hash), então ele pode tentar em na maioria das vezes para obter um registro enganoso, o que limita sua probabilidade de sucesso a (t) t 2⁹⁶.
Adicione todos os itens de erro
Finalmente, para que tudo isto seja verdade, precisamos de garantir que o provador não pode alterar a árvore Merkle. Podemos mostrar que, desde que o provador não encontre colisões na função hash, ele não poderá trapacear na árvore Merkle. A probabilidade de um invasor encontrar uma colisão usando chamadas t (função hash aleatória) é no máximo t2/2, que é o comprimento de saída da função hash (causada pelo "Paradoxo do Aniversário"). É por isso que precisamos definir o função hash O comprimento é o dobro da segurança necessária. Portanto, se tivermos uma função hash com comprimento de saída de 192 e um IOP com confiabilidade rodada a rodada de 96 bits, obteremos um STARK compilado que é confiável Erro sexual (t )=t2-⁹⁶ + t2 2¹⁹⁶. Como t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵, este esquema tem 95 bits de sexo de segurança.
Resumir
Em conjunto, o STARK fornece um método poderoso para verificar sem confiança a exatidão dos cálculos realizados em dados públicos. A segurança do STARK é geralmente medida pelo “erro de confiabilidade”, que representa a probabilidade de um invasor fornecer com sucesso uma declaração falsa e convencer o validador com uma prova. Para atingir o nível de segurança exigido, como 96 bits, o IOP subjacente deve atender à confiabilidade rodada a rodada para garantir que altos níveis de segurança sejam mantidos em cada rodada. Analisamos a confiabilidade rodada a rodada dos IOPs nos quais nosso STARK se baseia para derivar limites de segurança específicos.