Game-Theoretic Analysis of Transaction Selection in DAG-Based Distributed Ledgers

Resumo Técnico: Análise Teórica dos Jogos na Seleção de Transações em Livros-Contábeis Distribuídos Baseados em DAG

Enunciado do Problema
Em tecnologias de livro-Contábil distribuído (DLTs) baseadas em DAG, múltiplos validadores propõem blocos concorrentemente para melhorar o rendimento. No entanto, esse paralelismo introduz o desafio de colisões de transações, onde múltiplos validadores selecionam a mesma transação, levando a ineficiências, já que inclusões redundantes não aumentam a utilidade do sistema. Os sistemas atuais frequentemente dependem de heurísticas ingênuas para seleção de transações, como seleção uniforme ou proporcional, sem analisar rigorosamente se essas estratégias constituem equilíbrios de Nash (EN) sob mecanismos específicos de alocação de taxas. Além disso, a interação entre modelos de distribuição de taxas e incentivos de validadores em um ambiente descentralizado e não cooperativo permanece pouco examinada. Este artigo aborda essa lacuna derivando os equilíbrios de Nash mistos simétricos para estratégias de seleção de transações sob dois mecanismos distintos de alocação de taxas e avaliando seu desempenho em comparação com benchmarks ingênuos.

Metodologia
Os autores modelam o processo de seleção de transações como um jogo de tiro único (modelo miope) envolvendo $N$ validadores e um pool finito de $m$ transações com taxas variáveis. Cada validador seleciona um subconjunto de $b$ transações para incluir em seu bloco. O estudo foca em dois mecanismos de alocação de taxas:

1. Alocação Aleatória de Taxas (RFA): Se múltiplos validadores incluírem uma transação, a taxa é atribuída aleatoriamente a exatamente um deles. Este mecanismo é típico de sistemas de Prova de Trabalho (PoW) com ordenação total (por exemplo, GHOSTDAG).
2. Compartilhamento Colaborativo de Taxas (CFS): Se pelo menos um validador incluir uma transação, a taxa é distribuída igualmente entre todos os $N$ validadores. Este mecanismo é mais típico de protocolos semelhantes à Tolerância a Falhas Bizantinas (BFT).

Os autores empregam uma estrutura teórica dos jogos para derivar equilíbrios de Nash simétricos. Eles primeiro estabelecem um resultado teórico geral (Teorema IV.1) caracterizando o EN usando uma função estritamente decrescente $f(p)$ representando a participação esperada de recompensas. Reconhecendo que inverter diretamente $f(p)$ para RFA é computacionalmente intensivo, o artigo propõe uma abordagem eficiente baseada em otimização usando as condições de Karush-Kuhn-Tucker (KKT). Isso transforma a derivação do equilíbrio em um problema de otimização côncava solucionável via descida de gradiente projetada.

O desempenho dos equilíbrios derivados é avaliado numericamente contra dois benchmarks ingênuos:

• Seleção Aleatória de Transações (RTS): Seleção uniforme.
• Seleção Proporcional de Transações (PTS): Probabilidade de seleção proporcional às taxas das transações.

As métricas incluem Rendimento Efetivo de Transações (número esperado de transações únicas incluídas) e Rendimento Efetivo de Taxas (recompensas totais esperadas coletadas). As simulações utilizam uma distribuição de taxas tipo Zipf para modelar estruturas de taxas assimétricas.

Principais Contribuições

1. Derivação de Equilíbrios de Nash Simétricos: O artigo fornece a primeira derivação explícita de equilíbrios de Nash mistos simétricos para ambos os modelos RFA e CFS em um jogo de seleção de transações de tiro único.
2. Método de Cálculo Eficiente: Os autores introduzem uma estrutura de otimização côncava usando condições KKT para calcular esses equilíbrios de forma eficiente, superando a intratabilidade computacional dos métodos de inversão direta, particularmente para o modelo RFA.
3. Análise Comparativa de Desempenho: Através de simulações numéricas, o estudo demonstra que o EN do mecanismo de Compartilhamento Colaborativo de Taxas (CFS) alcança consistentemente maior rendimento de taxas e recompensas em comparação com o EN da Alocação Aleatória de Taxas (RFA), especialmente sob distribuições de taxas assimétricas.
4. Benchmarking de Estratégias Ingênuas: A análise revela que, embora o EN-CFS seja ótimo para receita de taxas, a heurística de Seleção Proporcional de Transações (PTS) frequentemente supera o EN-RFA em termos de recompensas. Em cenários onde o CFS não é viável (por exemplo, sistemas PoW sem permissão), a PTS serve como uma alternativa robusta que pode aproximar o desempenho do equilíbrio RFA.

Resultados
Avaliações numéricas sob parâmetros variados (número de transações, taxa máxima e assimetria de taxas) produzem as seguintes percepções:

• Rendimento de Taxas: O equilíbrio CFS maximiza consistentemente o rendimento de taxas em todos os cenários testados. A estratégia PTS também performa bem, superando significativamente o equilíbrio RFA. Por outro lado, o equilíbrio RFA frequentemente produz menor rendimento de taxas do que mesmo a estratégia uniforme (RTS).
• Rendimento de Transações: Existe um trade-off entre maximização de taxas e diversidade de transações. A estratégia uniforme (RTS) alcança o maior rendimento efetivo de transações ao minimizar colisões através de uma distribuição de probabilidade uniforme. No entanto, isso ocorre à custa de um rendimento de taxas mais baixo. O equilíbrio CFS, embora maximize taxas, resulta no menor rendimento efetivo de transações, porque os validadores concentram-se em transações de alta taxa, levando a taxas de colisão mais altas para esses itens específicos.
• Impacto da Assimetria: À medida que as distribuições de taxas se tornam mais assimétricas (parâmetro Zipf mais alto), a lacuna de desempenho se amplia. CFS e PTS mantêm rendimento de taxas superior, enquanto RFA luta, destacando sua ineficiência no manuseio de estruturas de taxas diversas.

Significado e Alegações
O artigo alega que suas descobertas fornecem percepções acionáveis para o design de mecanismos de seleção de transações e incentivos em DLTs baseadas em DAG. Ao caracterizar os equilíbrios de Nash, os autores demonstram que estratégias intuitivas (como seleção uniforme) nem sempre são ótimas e que a escolha do mecanismo de alocação de taxas altera fundamentalmente o comportamento dos validadores e o desempenho do sistema.

Especificamente, o trabalho sugere que:

• CFS é superior para receita: Se o objetivo principal é maximizar a receita de taxas, o CFS com sua estratégia de equilíbrio correspondente é o mecanismo mais eficaz.
• RFA possui ineficiências inerentes: O mecanismo RFA, comum em sistemas PoW, leva a equilíbrios que podem ser superados por heurísticas simples como seleção proporcional, indicando um desalinhamento entre incentivos individuais e bem-estar coletivo em tais designs.
• Heurísticas Práticas: Para protocolos onde o CFS não é viável (por exemplo, devido à falta de um conjunto conhecido de validadores em ambientes sem permissão), a seleção proporcional oferece uma heurística valiosa que aproxima o desempenho de equilíbrio do RFA sem exigir cálculo complexo de equilíbrio.

Os autores mantêm um escopo modesto, reconhecendo que o estudo é limitado a um modelo de tiro único com taxas estáticas e latências homogêneas. Eles observam que estender essa análise para jogos sequenciais de múltiplas rodadas com taxas dinâmicas e condições de rede heterogêneas permanece um passo necessário para aplicabilidade no mundo real. O artigo não propõe novas implementações de protocolos, mas fornece uma base teórica e numérica para avaliar estruturas de incentivos existentes e futuras.