PoSME: Proof of Sequential Memory Execution via Latency-Bound Pointer Chasing with Causal Hash Binding

Título: PoSME: Prova de Execução Sequencial de Memória via Perseguição de Ponteiros Limitada por Latência com Ligação Causal de Hash

1. O Problema

O artigo identifica uma lacuna crítica nas primitivas criptográficas existentes para provar que uma parte realizou um cálculo sequencial sustentado sob restrições de recursos concretas. As soluções atuais falham em atender a todos os requisitos simultaneamente:

• VDFs (Funções de Atraso Verificáveis): Garantem tempo sequencial, mas são insensíveis à memória; ASICs podem acelerá-las arbitrariamente usando ALUs mais rápidas.
• PoSW (Provas de Trabalho Sequencial): Provam travessia de grafos, mas operam sobre memória estática e imutável, permitindo que adversários recalculem blocos sem armazená-los.
• Funções Duras de Memória (MHFs) como Argon2id: Aumentam o custo por avaliação, mas são primitivas de "único disparo" sem um sistema de prova em cadeia, e oferecem apenas uma vantagem de 8–16× para ASICs baseada em largura de banda.

O objetivo é criar uma primitiva que force o armazenamento de um grande estado mutável, seja resistente a ASICs (limitada pela latência de acesso aleatório à memória, não pela largura de banda) e permita verificação eficiente.

2. Metodologia e Construção

O PoSME (Proof of Sequential Memory Execution) é construído sobre três princípios fundamentais:

1. Perseguição de Ponteiros Dependente de Dados:

   • O endereço de cada leitura subsequente depende estritamente do valor lido na etapa anterior. Isso cria uma cadeia sequencial rígida que não pode ser paralelizada.
   • O acesso ocorre em uma Arena Mutável (um hiperespaço booleano de dimensão $d_{hc}$), onde o estado evolui a cada passo.

2. Estado Mutável da Arena:

   • Diferente de grafos estáticos, a arena é modificada in-place. Para recriar um bloco que foi descartado (cache miss), o adversário deve reexecutar toda a cadeia de escrita que levou àquele estado, o que é computacionalmente proibitivo se o armazenamento for reduzido.

3. Ligação Causal Simbiótica (Symbiotic Causal Binding):

   • Cada bloco escrito contém dois campos interdependentes: o valor dos dados e um hash causal (histórico de escrita).
   • O novo valor dos dados incorpora o hash causal antigo, e o novo hash causal incorpora o cursor atual. Isso cria uma dependência bidirecional: é impossível forjar um bloco sem forjar toda a sua linhagem causal.

Algoritmo de Execução:

• Inicialização: A arena é inicializada deterministicamente a partir de uma semente, formando um DAG (Grafo Acíclico Direcionado) com links de "pulo" (skip-links).
• Passo (Step): O provador realiza $d$ leituras sequenciais. O endereço de cada leitura é derivado do hash do cursor atual. Após as leituras, um novo bloco é escrito em um endereço derivado do cursor final, atualizando o valor e o hash causal de forma simbiótica.
• Verificação: O sistema suporta dois modos:
  • Clássico: Usa Merkle Trees e Fiat-Shamir, com tamanho de prova escalável.
  • IVC (Computation Verificável Incremental): Utiliza a aritmetização sobre campos binários (Binius) para "dobrar" a prova de cada passo no anterior, resultando em um tamanho de prova constante ($O(1)$) independentemente do número de passos $K$.

3. Contribuições Principais

• Nova Construção: O primeiro primitivo a combinar estado mutável, endereçamento de perseguição de ponteiros dependente de dados e ligação causal simbiótica.
• Segurança Espaço-Tempo Formal:
  • Prova de um limite inferior formal de $S \cdot T = \Omega(K^2)$ (Produto Espaço-Tempo) para grafos causais dinâmicos.
  • Introdução do conceito de "Temporal Staleness" (Rancor Temporal): Demonstra que, devido à aleatoriedade das escritas, os dados armazenados em cache tornam-se obsoletos rapidamente, aumentando exponencialmente o custo de recomputação para adversários que tentam reduzir o armazenamento.
  • Extensão da segurança para adversários adaptativos sem perda de fator.
• Validação ROM (Random Oracle Model): Validação matemática e empírica da uniformidade dos endereços gerados pelo BLAKE3 em escala de produção ($N=2^{24}$, 5,4 bilhões de leituras), com estatística $\chi^2/df \approx 1.0004$.
• Resistência a ASICs: Demonstração de que o gargalo é a latência de acesso aleatório à DRAM (40–50 ns), e não a capacidade de cálculo ou largura de banda.

4. Resultados Empíricos

Os autores realizaram benchmarks em 17 plataformas de CPU e 4 arquiteturas de GPU (incluindo NVIDIA H100, A100, T4).

• Desempenho de Hardware:
  • GPUs vs. CPUs: As GPUs são 14 a 19 vezes mais lentas que CPUs de consumo (como laptops) ao executar o PoSME. Isso ocorre porque as GPUs são otimizadas para paralelismo massivo e largura de banda, enquanto o PoSME é limitado por latência sequencial.
  • Custo de Hash: O cálculo do hash representa menos de 3,5% do custo total por passo; o restante é tempo de espera pela memória (DRAM).
  • Vantagem de ASIC: A vantagem teórica de um ASIC personalizado com memória HBM3 sobre a DDR5 é de apenas ~1,3× (devido à física da latência de DRAM), tornando o desenvolvimento de hardware dedicado economicamente irracional para a maioria dos cenários de ataque.
• Gargalo de Capacidade: Em GPUs, a capacidade de VRAM limita o número de instâncias paralelas que podem ser executadas, impedindo que a alta largura de banda seja explorada para amortizar o custo sequencial.

5. Significado e Impacto

O PoSME preenche uma lacuna fundamental na criptografia de provas de trabalho e atraso verificável:

1. Resistência a ASICs Estrutural: Ao depender da latência de DRAM (que melhorou apenas 1,3× em duas décadas) em vez de largura de banda ou poder de cálculo (que melhoraram 20×), o PoSME oferece uma resistência a ASICs mais durável e justa.
2. Aplicações Práticas:
   • Resistência a Sybil: Impede a criação de múltiplas identidades falsas sem um custo de armazenamento real.
   • Atestado de Autoria: Prova que um documento foi processado sequencialmente ao longo do tempo.
   • Atraso Verificável: Pode ser combinado com VDFs tradicionais para criar primitivas de tempo verificável que também exigem armazenamento massivo.
3. Eficiência de Verificação: A integração com o Binius permite verificação em tempo constante ($O(1)$), tornando o protocolo viável para clientes leves e blockchains.

Em resumo, o PoSME estabelece um novo padrão para primitivas de trabalho sequencial, onde a segurança é garantida pela física da memória (latência) e pela complexidade de recomputação de estados mutáveis, e não apenas pela dificuldade computacional de hashing.