Resumo Técnico: Split Tallies: Um Cálculo de Certificado Discreto para Auditoria de Conjuntos Ordenados Dinâmicos em Memória Constante

Declaração do Problema

O artigo aborda a verificação de conjuntos ordenados dinâmicos mantidos por uma parte adversária (o "mantenedor") e consultados por um consumidor. Em muitos cenários de computação moderna, as estruturas de dados residem em ambientes não confiáveis (por exemplo, serviços remotos, aceleradores de hardware opacos ou bibliotecas adquiridas). O consumidor emite operações (inserções, deleções, testes de pertinência, consultas de predecessor/sucessor e consultas de extremos) e recebe respostas imediatamente, agindo sobre elas sem demora.

O desafio central é fornecer um certificado de correção para todo o histórico de operações sem exigir que o consumidor (o "auditor") armazene a própria estrutura de dados ou reexecute as operações. O auditor deve ser passivo, armazenando apenas uma quantidade constante de estado (especificamente, cinco palavras de máquina e uma flag), enquanto o mantenedor anexa um curto "notch" (registro) a uma sequência pública e de anexação exclusiva chamada tally (contagem) para cada operação. O objetivo é detectar, com alta probabilidade, se o mantenedor forneceu alguma resposta incorreta, mesmo que o mantenedor possua poder computacional ilimitado e adapte sua estratégia com base no histórico visível.

Metodologia

A solução proposta, denominada Split Tallies, inspira-se nos históricos bastões de contagem de madeira, onde uma dívida era registrada por entalhes no bastão, que era então dividido longitudinalmente. O credor guardava o "stock" (estoque) e o devedor o "foil" (folha); no acerto de contas, as metades eram encaixadas para verificar a autenticidade. Neste contexto digital:

• O Tally (Contagem): Um fluxo público de entalhes anexados pelo mantenedor.
• O Stock (Estoque): O estado privado do auditor (cinco palavras e uma flag).
• O Foil (Folha): A contabilidade interna da estrutura do mantenedor.
• A Auditoria: O processo de "encaixar" o stock contra o foil (divulgado ao final de uma sessão).

O Cálculo de Gaps (Lacunas)

O núcleo técnico do artigo é um cálculo discreto de lacunas (gaps). Em vez de auditar o conjunto $S$ diretamente, o sistema audita a família de intervalos vazios máximos (lacunas) que particionam o universo ordenado.

• Representação: Um conjunto $S$ sobre um universo $\{1, \dots, U\}$ é representado unicamente por uma cadeia intertravada de lacunas $\langle a, b \rangle$ conectando sentinelas $0$e$U+1$.
• Forma Normal: O artigo prova que esta família de lacunas corresponde ao caminho único de unidade de $0$a$U+1$ em um grafo acíclico de intervalos.
• Rewrites (Reescritas): As operações são modeladas como reescritas locais deste caminho:
  • Inserção: Divide uma lacuna $\langle a, b \rangle$ em duas $\langle a, x \rangle, \langle x, b \rangle$.
  • Deleção: Mescla duas lacunas adjacentes $\langle a, x \rangle, \langle x, b \rangle$ em uma única $\langle a, b \rangle$.
  • Consultas: São respondidas exibindo uma lacuna específica (por exemplo, a lacuna que contém $x$ para pertinência, ou a lacuna que começa em $x$ para predecessor).

A Disciplina de Indentura

Para auditar essas reescritas sem armazenar o estado, o auditor emprega um mecanismo de fingerprinting baseado em teste de identidade polinomial sobre um corpo finito $\mathbb{F}_p$:

1. Códigos e Timestamps: Cada nascimento de lacuna recebe um código único (timestamp) via um contador público $\kappa$.
2. Citações: Cada operação deve citar os códigos das lacunas que ela consome (reescreve).
3. Acumuladores: O auditor mantém dois acumuladores, $A$ (para nascimentos) e $R$ (para consumos). Para uma lacuna com código $c$ e extremidades $a, b$, o valor $\nu(a, b, c)$ é mapeado no corpo.
   • No nascimento: $A \leftarrow A \cdot (z - \nu(a, b, c))$
   • No consumo: $R \leftarrow R \cdot (z - \nu(a, b, c))$
   • Aqui, $z$ é um elemento secreto do corpo escolhido pelo auditor antes da sessão.
4. Verificação: Na auditoria, o mantenedor divulga o conjunto atual de lacunas com seus códigos. O auditor verifica se as lacunas divulgadas se encaixam (formam uma cadeia válida) e verifica se $A = R$.

Mecanismos Chave

• Regra Temporal: Um código citado deve ser estritamente menor que o valor do contador no início do evento. Isso evita que o mantenedor "pegue emprestado" códigos futuros para forjar um livro contábil equilibrado.
• Forçamento (Forcing): Devido à unicidade do caminho de lacunas, a resposta correta para qualquer consulta é uma função forçada da lacuna citada. Se o mantenedor citar uma lacuna que não existe ou que não está ativa, a resposta será inconsistente com as propriedades da lacuna, ou o livro contábil ficará desequilibrado.

Principais Contribuições e Resultados

1. O Teorema de Auditoria (Correção e Completude)

O artigo estabelece que o esquema é perfeitamente completo (mantenedores honestos são sempre aceitos) e $\epsilon$-correto (sound).

• Erro de Correção (Soundness Error): Se um mantenedor fornecer uma única resposta incorreta entre $T$ operações, a probabilidade de aceitação é de no máximo $(4T + 1)/p$.
• Parâmetros: Com um primo de 61 bits (ex: $2^{61}-1$), a probabilidade de erro é inferior a $2^{-38}$ para sessões de até um milhão de operações.
• Premissas: Não são exigidas suposições de dureza computacional; a segurança é informacional contra um adversário ilimitado.

2. Resultados de Impossibilidade e Necessidade

O artigo prova que as escolhas de design específicas são indispensáveis:

• Piso Determinístico: Qualquer auditor determinístico com correção ao final da sessão deve armazenar pelo menos $2n - \log_2(2n+1)$ bits de estado para um conjunto de tamanho $n$. Isso prova que a aleatoriedade é um requisito, não uma conveniência.
• Aleatoriedade Secreta: Se as moedas aleatórias do auditor forem visíveis para o mantenedor, o erro de correção torna-se 1 (o mantenedor pode sempre forjar um registro). A secreção do ponto de avaliação $z$ é necessária.
• Necessidade da Regra Temporal: Sem a regra que impede a citação de códigos futuros, existe uma falsificação explícita de três operações que alcança o equilíbrio exato e é aceita com probabilidade 1.

3. Implementação do Mantenedor

O artigo fornece uma implementação concreta usando uma árvore (2, 4)-folheada:

• Complexidade: As operações rodam em tempo $O(\log n)$ no pior caso.
• Sobrecarga: A estrutura requer apenas uma palavra extra por elemento (para armazenar o código da lacuna).
• Rebalanceamento Auditado: O artigo introduz um envelope de atestação provando que o número de eventos estruturais (divisões, fusões, compartilhamentos) sobre $m$ atualizações é de no máximo $2m$. Este limite é certificado pelo auditor contando as atestações de uma palavra anexadas pelo mantenedor, transformando análise amortizada em uma afirmação publicamente verificável.

4. Checkpoints e Épocas

O protocolo suporta checkpoints arbitrários. Auditorias podem ser realizadas a qualquer momento, e épocas aceitas podem ser encadeadas com limites de erro aditivos. Isso permite que a latência de detecção seja ajustada (ex: auditar após cada operação para alta segurança, ou com menos frequência para eficiência).

Significância e Escopo

O artigo afirma fornecer uma conta fechada de auditoria de memória constante para conjuntos ordenados dinâmicos. Sua significância reside em:

• Mudança de Paradigma: Mover de "testar em isolamento" para "certificação que viaja com a execução".
• Garantias Informacionais: Alcançar verificação sem suposições criptográficas (como árvores de Merkle ou assinaturas digitais), baseando-se em propriedades algébricas de polinômios e na estrutura combinatória de conjuntos ordenados.
• Limites Inferiores Estritos: Demonstrar que a solução de memória constante proposta é próxima do ideal ao provar que qualquer solução determinística requer espaço linear e que a aleatoriedade deve ser oculta.
• Constantes Explícitas: Todos os parâmetros (tamanhos de primos, contagens de palavras, limites de erro) são explícitos e calibrados para uso prático (ex: caber em palavras de 64 bits).

O escopo é estritamente limitado à interface de sete operações (inserir, deletar, pertencer, predecessor, sucessor, mínimo, máximo). O artigo nota explicitamente que o cálculo de lacunas certifica o arranjo (adjacência, enquadramento, extremidade), mas não se estende a propriedades agregadas como o ranking, que não são locais a uma única lacuna. A detecção é retrospectiva; o artigo reconhece que a detecção online (rejeitar uma resposta imediatamente) neste cenário informacional é uma fronteira reconhecida ligada à existência de funções de via única, e assim a solução proposta é ótima dentro de seu modelo retrospectivo definido.