Resumo Técnico: Aquisição Adversarial em Blockchains

Declaração do Problema

O artigo aborda o desafio da aquisição adversarial em protocolos de blockchain, especificamente no contexto de designs emergentes que exploram a assimetria computacional entre a execução e a verificação de tarefas (por exemplo, provas de conhecimento zero, ou SNARKs). Nesses sistemas, um protocolo deve terceirizar tarefas computacionais custosas (como gerar uma prova de validade para um bloco) para um conjunto de $n$ provedores pseudônimos e não confiáveis.

O problema central é projetar um mecanismo que:

1. Incentive pelo menos um provedor a executar a tarefa (garantindo liveness ou disponibilidade).
2. Minimize a perda econômica no pior cenário, onde até $n-h$ provedores são adversários (bizantinos) e podem desviar-se do protocolo para causar uma falha de disponibilidade (nenhuma prova entregue) ou induzir um pagamento excessivo.
3. Opere sem confiança, já que os provedores não possuem reputação e não podem comprometer-se credivelmente com ações futuras.

Os autores modelam isso como um problema de design de mecanismos, onde o designer do protocolo busca minimizar a soma dos pagamentos realizados e a penalidade $C$ incorrida se nenhuma prova for entregue, assumindo que um adversário controla um subconjunto de provedores e age para maximizar a perda do protocolo.

Metodologia

Os autores formalizam o problema utilizando uma estrutura teórica de jogos:

• Configuração: Existem $n$ provedores, dos quais $h$ são honestos. O custo de gerar uma prova é normalizado para 1. Se nenhuma prova for produzida, o protocolo incorre em uma penalidade de disponibilidade $C$.
• Modelo de Adversário: O adversário pode corromper até $a = n-h$ provedores. O adversário observa o mecanismo e escolhe o comportamento do pior caso (recusar-se a entregar provas para ativar a penalidade $C$, ou entregar provas para manipular os pagamentos).
• Objetivo: Minimizar a perda do pior caso $\ell(p, s)$, definida como o custo total esperado (pagamentos + penalidade) sob a estratégia adversarial do pior caso, sujeito à restrição de que o mecanismo seja compatível com incentivos (provedores honestos maximizam sua utilidade seguindo o protocolo).

Para tornar o problema tratável, os autores:

1. Derivam uma função de limite inferior $g(s)$ sobre a perda ótima do protocolo, parametrizada pelo vetor de estratégia $s$ (a probabilidade de cada provedor entregar uma prova). Esse limite assume um adversário "enfraquecido" que escolhe entre duas estratégias extremas: agir totalmente honestamente ou recusar-se totalmente a entregar.
2. Analisam os minimizadores desse limite inferior, caracterizando-os como Equilíbrios de Comitê Uniforme Designado (um líder determinístico + um comitê de randomizadores) ou Equilíbrios de Comitê Simétrico (um comitê de randomizadores sem líder designado).
3. Investigam a implementabilidade: determinar se existe uma regra de pagamento que induza esses equilíbrios enquanto atinge o custo do limite inferior.
4. Estendem a análise para incluir pagamentos negativos (confisco/aposta), onde os provedores depositam colateral que pode ser confiscado se o protocolo detectar um ataque.

Principais Contribuições e Resultados

1. Caracterização dos Equilíbrios Ótimos

O artigo prova que os minimizadores do limite inferior $g(s)$ são exclusivamente de dois tipos:

• Equilíbrios Designados: Um provedor é designado para entregar com probabilidade 1, enquanto um comitê de tamanho $k$ entrega com probabilidade $s \in (0, 1)$.
• Equilíbrios Simétricos: Um comitê de tamanho $k$ entrega com probabilidade $s$, e nenhum provedor individual é designado.

2. Garantias de Aproximação

• Aproximação Aditiva 1: Os autores provam que, para qualquer regra de pagamento e equilíbrio, existe um equilíbrio designado cuja perda é, no máximo, 1 unidade (o custo de uma única prova) maior que a perda ótima (Teorema 3.1).
• Implementabilidade: Todos os equilíbrios designados são implementáveis com uma regra de pagamento simples (Lema 3.4). Em contraste, os equilíbrios simétricos são implementáveis apenas sob condições específicas (por exemplo, quando $C$ é suficientemente grande em relação a $n$ e $h$) e frequentemente exigem estruturas de pagamento complexas ou pagamentos negativos para serem viáveis.

3. Escalonamento Assintótico

• Escalonamento Logarítmico: A perda do pior caso do equilíbrio designado ótimo escala como $O(\frac{\log C}{\tau})$, onde $\tau = h/n$ é a fração de provedores honestos. Isso indica que, mesmo com uma fração fixa de adversários, o custo do protocolo cresce apenas logaritmicamente com a severidade da penalidade de disponibilidade.
• Impacto da Aposta (Staking): A introdução de uma aposta total $B$ (colateral) melhora significativamente o escalonamento. Se $B$ for proporcional a $C$, a perda escala como $O(1/\tau)$, tornando-se efetivamente constante em relação a $C$.

4. Dinâmicas de Transição

O artigo analisa a transição entre a optimalidade designada e simétrica como uma função de $C$ (magnitude da penalidade) e $\tau$ (fração de honestidade).

• Para $C$ pequeno ou $\tau$ alto, o mecanismo designado é ótimo.
• Para $C$ muito grande, o mecanismo simétrico torna-se ótimo na análise do limite inferior.
• No entanto, devido às restrições de implementabilidade, o mecanismo designado frequentemente permanece a escolha prática mesmo em regimes onde o limite inferior simétrico é menor, pois a solução simétrica pode exigir pagamentos negativos que são inviáveis ou complexos de implementar.

Significado e Recomendações Práticas

O artigo argumenta que os resultados teóricos fornecem orientações acionáveis para designers de protocolos de blockchain, particularmente para zk-EVM (Máquina Virtual Ethereum de Conhecimento Zero) e outros mercados de terceirização verificável.

• Recomendação: Os autores recomendam fortemente a adoção do equilíbrio ótimo de comitê uniforme designado. Este design designa um único "líder" (ou trabalhador principal) para produzir a prova deterministicamente, apoiado por um comitê de "reservas" que produzem provas com uma probabilidade calculada $s$.
• Justificativa:
  1. Simplicidade: A regra de pagamento é intuitiva e assemelha-se a mecanismos de consenso existentes (por exemplo, consenso baseado em líder com comitês de atestação).
  2. Quase-Optimalidade: A perda é, no máximo, um custo de prova distante do ótimo teórico, o que é negligenciável dado os custos atuais de geração de provas (frequentemente frações de dólar).
  3. Robustez: Lida efetivamente com o comportamento adversarial do pior caso, escalando logaritmicamente com a penalidade $C$.
  4. Viabilidade: Ao contrário de mecanismos simétricos que podem exigir pagamentos complexos estilo loteria ou pagamentos negativos (confisco) para serem ótimos, mecanismos designados são sempre implementáveis com pagamentos positivos.

O artigo conclui que, embora mecanismos simétricos sejam teoricamente interessantes e ótimos em regimes assintóticos específicos, o mecanismo designado oferece o melhor equilíbrio entre optimalidade teórica, implementabilidade e familiaridade para a comunidade de blockchain. Os autores observam que seu modelo se aplica amplamente a qualquer problema de delegação sem permissão envolvendo falhas de disponibilidade, incluindo inferência de IA verificável e computações baseadas em TEE.