Resumo Técnico: Uma Análise de Custo de Append de Tempo Constante para Registros On-Chain

Declaração do Problema

Árvores de proveniência (PTs) são grafos acíclicos direcionados (DAGs) de apenas adição (append-only) usados como o substrato de dados para infraestruturas de proveniência com controle por operador. Embora trabalhos anteriores tenham afirmado que a operação de append subjacente para PTs é $O(1)$ em custo de gás — independente do tamanho do registro e da profundidade da árvore — essa afirmação carecia de isolamento formal como uma primitiva autônoma, limites constantes explícitos ou benchmarking empírico contra o padrão da indústria: a Árvore de Merkle Incremental (IMT).

A IMT, dominante em protocolos de prova de conhecimento zero (ex: Tornado Cash, Semaphore) e compromissos de estado de rollups, oferece provas de inclusão sucintas de $O(\log N)$, mas incorre em um custo de append que cresce logaritmicamente com a profundidade da árvore ($\Theta(\log N)$). Para aplicações onde provas de pertinência sucintas não são a consulta primária (como registros de proveniência), o trade-off de custo da IMT é menos favorável, embora o ponto de intersecção onde uma alternativa se torna mais barata não tenha sido rigorosamente estabelecido.

Metodologia

O artigo isola o Grafo Acíclico Direcionado de Hash de Pai (PHDAG) como uma primitiva distinta e o compara com a Árvore de Merkle Incremental (IMT) através de três lentes:

1. Análise de Complexidade Formal: Os autores formalizam a operação de append do PHDAG, provando que ela executa um número limitado de operações EVM independente do tamanho do registro ($n$) ou da profundidade. Eles contrastam isso com o loop de atualização de fronteira da IMT, que escala linearmente com a profundidade ($d$).
2. Modelagem Estocástica de Custo: Reconhecendo que os custos de append da IMT variam com base na representação binária do índice da folha (peso de Hamming), os autores modelam o custo de inserção por variável aleatória. Eles derivam expressões de forma fechada para a média e variância dos custos da IMT sob uma distribuição uniforme de índices de folha, distinguindo entre "níveis de escrita" (atualizando a fronteira) e "níveis de leitura" (travessia sem escrita).
3. Validação Empírica: Contratos independentes para ambas as primitivas foram implantados na rede de teste Base Sepolia. Experimentos cobriram profundidades de árvore de 1 a 25.
   • IMT: Testada via uma "varredura de profundidade proporcional" realizando $\max(d, 2)$ appends por profundidade para capturar a variância.
   • PHDAG: Testada via uma execução de 200 appends caracterizando a distribuição de custo e variância.
   • Métricas: O consumo de gás foi medido a partir de recibos de transação, excluindo custos iniciais de inicialização de armazenamento frio para focar no desempenho de estado estável.

Principais Contribuições

1. Complexidade Formal do PHDAG

O artigo estabelece que o append do PHDAG é estritamente $O(1)$ em custo de gás.

• Mecanismo: Cada append escreve em três slots de armazenamento anteriormente intocados (SSTOREs frios) chaveados por um identificador único, além de uma escrita quente (warm write) a um contador.
• Invariância: O custo é invariante ao tamanho global do registro $n$ e a qualquer noção de profundidade de árvore. A lista de acesso para uma transação é resetada no início de cada transação; como o PHDAG escreve em novos slots a cada vez, o custo depende apenas do número fixo de operações, não do estado do contrato.
• Reconstrução: O artigo prova que o registro completo pode ser reconstruído a partir de logs de eventos públicos em tempo $O(|V|)$ sem dependência off-chain, pois o fluxo de eventos carrega o histórico canônico.

2. Modelo Estocástico para IMT

Os autores derivam que o custo por inserção da IMT é uma variável aleatória $g$ dependente do índice da folha $i$:

• Média: $E[g] = c_0 + \frac{d}{2}(c_L + c_R)$, onde $c_L$ e $c_R$ são os custos marginais dos níveis de escrita e leitura, respectivamente.
• Variância: $Var[g] = (c_L - c_R)^2 \frac{d}{4}$.
• Implicação: Embora a variância relativa (coeficiente de variação) diminua conforme a profundidade aumenta, o desvio padrão absoluto cresce como $\Theta(\sqrt{d})$, introduzindo imprevisibilidade operacional para registros de alta profundidade.

3. Crossover Empírico e Validação

• Desempenho do PHDA G: Medido em um valor constante de 76.276 de gás por append (desvio padrão $\approx 6$ de gás), confirmando a invariância de profundidade.
• Desempenho da IMT: Os custos cresceram linearmente com a profundidade.
• Ponto de Crossover: A profundidade na qual o PHDAG se torna mais barato que a IMT foi identificada em $d \approx 6$ a $7,2$.
  • Em $d=6$, o custo medido da IMT ($\approx 78.000$ de gás) excedeu o custo do PHDAG.
  • O crossover médio de vida útil (distribuição de índice uniforme) é calculado em $d^* \approx 7,2$.

Resultados

Os dados empíricos validam os modelos teóricos:

• O PHDAG exibe variância negligenciável e custo constante em todas as profundidades testadas.
• A IMT exibe crescimento de custo linear e aumento da variância absoluta com a profundidade.
• Contexto de Produção: Cada registro de produção pesquisado (Tornado Cash, Semaphore, zkSync, Scroll, Linea) opera em profundidades $d \ge 20$. Consequentemente, todos esses sistemas operam atualmente no regime onde o PHDAG é estritamente mais barato e oferece custos previsíveis, desde que a aplicação não exija provas de inclusão sucintas.

Significância e Alegações

O artigo alega que a primitiva PHDAG é a escolha superior para registros de proveniência de apenas adição onde:

1. Provas de pertinência sucintas não são exigidas: Consultas de proveniência tipicamente envolvem travessia de cadeia de pais ou verificações de existência por ID único, que são suportadas por reconstrução baseada em logs de $O(|V|)$ em vez de provas de Merkle de $O(\log N)$.
2. A previsibilidade de custo é crítica: Para operadores gerenciando serviços de append de alto volume, a variância próxima de zero do PHDAG elimina a necessidade de orçar caudas de gás de pior caso, uma vantagem operacional significativa sobre a IMT em profundidades de produção.
3. A robustez é primordial: O design log-canônico do PHDAG garante que o histórico do registro seja indestrutível e reconstruível a partir de logs de eventos públicos, independentemente de qualquer serviço de indexação off-chain ou do estado atual do armazenamento do contrato.

Os autores concluem que o PHDAG é um forte candidato à padronização como uma interface uniforme para a infraestrutura de proveniência do Ethereum, ofereindo uma alternativa de custo constante e invariante de profundidade à IMT, que é dependente de profundidade, para aplicações não-ZK.