💻 computer science

A Complexity-Theoretic Approach to Proofs of Space

Este artigo apresenta uma estrutura elementar para a construção de Provas de Espaço (PoS) seguras sem depender do modelo de oráculo aleatório, demonstrando que tais protocolos podem ser construídos a partir de uma combinação de suposições criptográficas padrão (como funções de hash resistentes à colisão ou SNARGs) e suposições específicas de complexidade de derandomização.

Autores originais: Marshall Ball, Jiaxin Guan

Publicado 2026-08-11

📖 7 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Marshall Ball, Jiaxin Guan

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

O Grande Assalto ao Armazenamento Digital

Imagine um mundo onde você pode provar que possui uma biblioteca de livros massiva sem nunca mostrar uma única página. Este é o coração das Provas de Espaço (Proofs of Space), um conceito no campo da criptografia e da ciência da computação. É como um senhorio digital que quer garantir que um inquilino realmente tem um armazém cheio de móveis, e não apenas um desenho inteligente de móveis. O senhorio (o Verificador) precisa ter certeza de que o inquilino (o Provador) está usando uma enorme quantidade de memória persistente para armazenar dados, em vez de manter apenas uma pequena nota que diz "eu tenho os móveis" e então conjurar magicamente os móveis apenas quando solicitado.

Por anos, a única maneira de construir esses armazéns digitais dependia de uma ferramenta mágica e imaginária chamada "Oráculo Aleatório". Pense nisso como uma caixa preta mágica que cospe respostas perfeitamente aleatórias e imprevisíveis toda vez que você faz uma pergunta. Embora útil para a teoria, é como construir uma casa sobre um alicerce de pura magia; não sabemos se ela aguentaria no mundo real. A grande questão para os cientistas tem sido: Podemos construir uma Prova de Espaço segura usando apenas leis físicas reais de computação, sem depender de caixas mágicas? Este artigo mergulha justamente nessa questão, usando as ferramentas da teoria da complexidade — o estudo de quão difíceis são os problemas para resolver — para ver se podemos construir essas provas do zero.

A Grande Ideia do Artigo: A String "Profunda"

Os autores, Marshall Ball e Jiaxin Guan, apresentam uma nova estrutura elementar para construir Provas de Espaço sem magia. Sua principal descoberta é que você pode criar essas provas se tiver dois ingredientes específicos: uma suposição criptográfica (como funções de hash resistentes a colisões) e uma suposição de "derandomização" (uma crença sobre o quão difíceis certos problemas de computador são para máquinas poderosas e não determinísticas).

Para entender o truque deles, imagine que você precisa provar que possui uma pilha gigante e bagunçada de areia (os dados). O método antigo exigia uma caixa mágica para garantir que a areia não pudesse ser comprimida. Os autores percebem que, no mundo real, não precisamos que a areia seja impossível de comprimir; só precisamos que seja difícil de comprimir rapidamente.

Eles introduzem o conceito de Profundidade Computacional. Pense em uma string de dados como uma história.

A Configuração: O Provador pega uma semente minúscula (um resumo curto da história) e gasta muito tempo (Fase 1) expandindo-a em um romance massivo e detalhado (os dados).
A Armadilha: O Verificador então pede páginas específicas desse romance.
O Flagrante: Se o Provador não escreveu o romance inteiro e apenas guardou o resumo curto, ele precisaria reescrever as páginas do zero. Mas o Verificador dá a ele apenas um tempo ínfimo (Fase 2) para fazer isso.

Os autores mostram que, se assumirmos que certos problemas difíceis existem (especificamente, que alguns problemas são difíceis demais para circuitos "não determinísticos" resolverem rapidamente), você pode criar uma função que transforma uma semente curta em uma string longa. Esta string é "profunda": ela pode ser gerada a partir de uma semente curta se você tiver bastante tempo, mas não pode ser reconstruída a partir de uma semente curta se você estiver com pressa. É como um quebra-cabeça que leva um ano para resolver, mas apenas um minuto para verificar; se você tentar resolvê-lo em um minuto, simplesmente não consegue.

Como a Prova Funciona: A "Árvore de Merkle" e o "Feitiço Mágico"

O artigo descreve um protocolo de duas etapas para testar essa "profundidade".

Fase 1: A Configuração (A Longa Espera)
O Verificador envia uma semente aleatória para o Provador. O Provador passa muito tempo (digamos, horas) usando sua função "profunda" especial para transformar essa semente em um arquivo de dados massivo. Eles então constroem uma Árvore de Merkle sobre esses dados. Imagine a Árvore de Merkle como uma impressão digital digital de todo o arquivo. É como uma árvore genealógica onde cada folha é um pedaço de dado, e cada ramo é um hash (uma impressão digital única) dos dois ramos abaixo dele. No topo de tudo está um único hash "Raiz" que representa o arquivo inteiro. O Provador armazena esse arquivo massivo e a Raiz.

Fase 2: A Verificação (O Questionário Rápido)
O Verificador subitamente pede páginas específicas do arquivo (índices aleatórios). O Provador deve fornecer rapidamente essas páginas e o "caminho" através da Árvore de Merkle que prova que essas páginas pertencem ao arquivo original.

É aqui que a engenhosidade dos autores brilha. Para impedir que o Provador tente contornar o protocolo (apenas guardando a semente curta e tentando adivinhar as páginas), eles adicionam um Argumento Sucinto (uma prova curta e não interativa).

Opção A (A Suposição Mais Forte): Eles usam um "SNARG" (uma prova muito curta e não interativa) para provar que o hash da Raiz enviado realmente veio do arquivo gerado pela semente. Isso requer uma suposição forte sobre a existência de certas ferramentas criptográficas, mas mantém o overhead de armazenamento baixo.
Opção B (A Suposição Mais Fraca): Eles usam um argumento do tipo "Kilian", baseado em funções de hash resistentes a colisões. Esta é uma suposição mais padrão e "segura", mas força o Prover honesto a armazenar um pouco mais de dados (uma string "PCP") para provar que a árvore de Merkle foi construída corretamente.

O Que Eles Descartam e O Que Eles Provam

O artigo argumenta explicitamente contra a ideia de que as Provas de Espaço devem depender do modelo de Oráculo Aleatório. Eles mostram que a "caixa mágica" não é necessária. Em vez disso, provam que, se aceitarmos a "suposição de derandomização" (que alguns problemas são difíceis para circuitos não determinísticos), as Provas de Espaço são possíveis.

Eles também abordam um tipo específico de tentativa de burlar o protocolo: e se o Provador armazenar um pouco de dado e tentar "comprimir" o arquivo grande em tempo real? Os autores provam que, se o Provador conseguir convencer o Verificador a aceitar, ele deve ter armazenado uma quantidade significativa de dados. Especificamente, eles mostram que um Provador tentando contornar o protocolo não consegue armazenar significativamente menos do que o provador honesto (por exemplo, se o provador honesto armazena $N$ bits, um Provador tentando contornar o protocolo não consegue se safar armazenando muito menos que $N$ bits, dependendo da construção específica utilizada).

A Conclusão

Este artigo não afirma ter construído um produto comercial pronto para o seu smartphone hoje. Em vez disso, fornece um projeto teórico. Ele demonstra que a tarefa "impossível" de provar que você possui um armazém de dados sem usar magia é, na verdade, possível, desde que aceitemos certas crenças padrão sobre a dificuldade dos problemas de computação.

Eles mostram que:

Funciona: Você pode construir essas provas usando "profundidade computacional" em vez de magia.
É eficiente: O usuário honesto não precisa fazer nada de muito louco, embora precise armazenar os dados.
É seguro: Se alguém tentar contornar o protocolo armazenando menos dados, a matemática diz que essa pessoa quase certamente será pega, assumindo que os problemas difíceis subjacentes permaneçam difíceis.

Em suma, Ball e Guan tiraram a "Prova de Espaço" do reino das caixas pretas mágicas e a plantaram firmemente no solo da teoria da complexidade, mostrando-nos que, com as suposições certas, podemos construir armazéns digitais tão seguros quanto as leis da computação permitem.

Resumo Técnico: Uma Abordagem de Teoria da Complexidade para Provas de Espaço

Enunciado do Problema
As Provas de Espaço (PoS - Proofs of Space), introduzidas por Dziembowski et al. [DFKP15], são protocolos de duas fases que permitem que um Provador convença um Verificador eficiente de que este alocou uma quantidade significativa de memória persistente. O protocolo consiste em uma fase de inicialização (de longa duração), onde o Provador armazena dados, e uma fase de execução (de curta duração), onde o Verificador desafia o Provador para provar que os dados ainda estão armazenados.

Uma limitação crítica dos protocolos de PoS existentes é que suas provas de segurança dependem fortemente do Modelo de Oráculo Aleatório (ROM) ou de suposições criptográficas ad hoc. Especificamente, eles dependem da simultânea incomprimibilidade e extratibilidade de consultas ao oráculo aleatório. Até o momento, não se conhece construções que sejam seguras no modelo puro (plain model, sem oráculos aleatórios) baseadas apenas em suposições criptográficas padrão. Há uma carência de suposições limpas e falsificáveis sobre funções de hash criptográficas que sejam suficientes para a segurança provável dessas construções.

Metodologia e Estrutura
Este artigo apresenta uma estrutura elementar para construir PoS no modelo puro, combinando suposições de derandomização com suposições criptográficas. A ideia central é que um PoS requer uma string $\sigma$ que é paradoxalmente tanto comprimível a partir de uma descrição curta (dado um tempo suficiente $T$ ) quanto incomprimível de qualquer descrição ligeiramente mais curta (dentro de um tempo $t$ ).

Os autores formalizam isso usando a noção de complexidade teórica de profundidade computacional (introduzida por Antunes et al. [AFVmV06]). Eles buscam uma função $f$ com alta profundidade computacional:

Comprimibilidade em longo prazo: $f(x)$ pode ser computada a partir de uma semente curta $x$ em tempo $T$ .
Incomprimibilidade em curto prazo: $f(x)$ não pode ser reconstruída a partir de qualquer descrição mais curta que $|f(x)|$ dentro de um tempo $t$ , mesmo dado $x$ .

A construção procede em três etapas principais:

Construindo Funções de Alta Profundidade:
Os autores utilizam Geradores de Números Pseudoaleatórios (PRGs) de extensão de semente contra distinguidores não determinísticos. Sob a suposição de que $E = \text{DTIME}[2^{O(n)}]$ requer circuitos não determinísticos de tamanho exponencial (uma suposição padrão usada para mostrar que $\text{AM} = \text{NP}$ ), eles constroem PRGs que são difíceis para circuitos não determinísticos.
- Para alcançar uma probabilidade esmagadora de incomprimibilidade (em vez de apenas um erro perceptível), eles empregam PRGs multiplicativos contra distinguidores não determinísticos. Estes preservam a probabilidade de eventos negligenciáveis, garantindo que a saída do PRG permaneça incomprimível com probabilidade esmagadora.
- Para lidar com a incomprimibilidade aproximada (resiliência a erros de distância de Hamming), eles compõem o PRG com códigos de correção de erros (ECC) decodificáveis por lista. Isso garante que, mesmo que um adversário recupere uma string próxima a $f(x)$ , a string original permaneça incomprimível.
O Lema de Extração:
Uma contribuição técnica central é o Lema de Extração (Lema 11). Ele estabelece que, se um provador consegue manter um estado pequeno $S$ e responder com sucesso aos desafios de verificação com probabilidade não negligenciável, então a string subjacente $y = f(x)$ é aproximadamente compressível.
- O lema utiliza um Gerador de Conjunto de Atingimento (HSG) para selecionar deterministicamente um conjunto de índices de desafio "úteis" que cubram uma grande fração da string armazenada.
- Isso permite que um extrator recupere a maior parte dos bits de $y$ a partir do pequeno estado do provador dentro do tempo $t$ , contradizendo a suposta incomprimibilidade de $f$ .
Instanciação do Protocolo:
A estrutura é instanciada em dois protocolos específicos de PoS, que diferem em suas suposições criptográficas e sobrecarga de armazenamento:
- Construção 1 (baseada em SNARG): Utiliza um Argumento Não Interativo Semi-Universal (SNARG) para $P$ . O Provador armazena a raiz de Merkle de $f(x)$ e uma prova sucinta de que a raiz corresponde a $f(x)$ . Isso depende da existência de SNARGs para $P$ (uma suposição forte), mas oferece armazenamento quase ideal para o provador honesto ( $N$ bits).
- Construção 2 (baseada em Kilian): Utiliza o sistema de argumento interativo de Kilian baseado em PCPs e Funções de Hash Resistentes a Colisões (CRHF). O Provador deve armazenar a string PCP da computação $f(x)$ , o que leva a requisitos de armazenamento honesto mais altos ( $N + \tilde{O}(T)$ ), mas depende de suposições criptográficas mais fracas (CRHF + derandomização).

Principais Resultados
O artigo estabelece os seguintes teoremas (informalmente):

Teorema 1: Assumindo que $E$ é difícil para circuitos não determinísticos de tamanho exponencial, existem funções explícitas que são incomprimíveis em tempo- $t$ para tamanho $N - O(\rho N \log(1/\rho))$ .
Teorema 2 (instanciação SNARG): Assumindo que $E$ é difícil para circuitos não determinísticos de tamanho exponencial, funções de via única e um SNARG semi-universal para $P$ , existe um PoS onde o provador honesto armazena $N$ bits, e o esquema é seguro contra qualquer provador usando $(1-o(1))N$ bits.
Teorema 3 (instanciação CRHF): Assumindo que $E$ é difícil para circuitos não determinísticos de tamanho exponencial e funções de hash resistentes a colisões, existe um PoS onde o provador honesto armazena $N$ bits, e o esquema é seguro contra qualquer provador usando $N^{1/c}$ bits (para algum constante $c$ ).

Significância e Alegações
Os autores enfatizam que seu trabalho fornece um resultado de viabilidade genérica e pedagogicamente limpo para PoS no modelo puro.

Quebrando a Barreira do ROM: Eles demonstram que o PoS pode ser construído sem oráculos aleatórios, baseando-se, em vez disso, em suposições de derandomização padrão (dificuldade de $E$ contra circuitos não determinísticos) combinadas com primitivas criptográficas padrão.
Compromissos (Trade-offs): O artigo destaca o compromisso entre suposições criptográficas e eficiência de armazenamento. A abordagem baseada em SNARG minimiza o armazenamento do provador honesto, mas requer suposições mais fortes. A abordagem baseada em Kilian utiliza suposições mais fracas (CRHF), mas exige que o provador honesto armazene um PCP da computação, aumentando significativamente o armazenamento.
Limitações: Os autores declaram explicitamente que seu foco é na viabilidade teórica, não em modelos de ameaça sofisticados ou protocolos práticos. Eles observam que, embora sua estrutura gere PoS, não é imediatamente claro como adaptar essas ideias para construir Funções de Memória Difíceis (MHFs), um objeto relacionado frequentemente derivado de PoS baseados em ROM. Além disso, eles reconhecem que lidar com a composição (um único provador interagindo com muitos verificadores) requer mais trabalho para garantir que os custos de armazenamento não sejam amortizados.

Em resumo, este trabalho faz a ponte entre a teoria da complexidade e os protocolos criptográficos, mostrando que a "dificuldade" necessária para as Provas de Espaço pode ser derivada de suposições fundamentais de derandomização, em vez de modelos de oráculo aleatório heurísticos.