Como o Algoritmo Ganancioso Molda as Recompensas dos Mineradores nas Redes Blockchain

Tabela de Links

Abstrato e 1. Introdução

1.1 Nossa Abordagem

1.2 Nossos Resultados e Roteiro

1.3 Trabalhos Relacionados

1. Modelo e Aquecimento e 2.1 Modelo de Blockchain

   2.2 O Minerador

   2.3 Modelo de Jogo

   2.4 Aquecimento: A Função de Alocação Gananciosa

2. O Caso Determinístico e 3.1 Limite Superior Determinístico

   3.2 A Classe de Função de Alocação Tendenciosa à Imediatez

3. O Caso Aleatorizado

4. Discussão e Referências

• A. Provas Ausentes para as Seções 2, 3
• B. Provas Ausentes para a Seção 4
• C. Glossário

\

2.3 Modelo de Jogo

Examinamos um jogo entre um adversário e um minerador. Esta perspetiva visa quantificar quanto rendimento o minerador pode perder devido ao conhecimento incompleto de transações futuras ao alocar as transações atualmente conhecidas para o próximo bloco. Neste sentido, os utilizadores ativos no sistema podem ser considerados como uma "natureza" omnisciente adversária, que cria um cronograma de transações de pior caso. Uma função de alocação não tem conhecimento de transações futuras que serão enviadas pelo adversário, e assim o planeamento ótimo baseado na informação parcial revelada por transações anteriores pode não ser o melhor curso de ação. No entanto, surpreendentemente, mostramos mais tarde que de facto é. Dado a taxa de desconto de um minerador, existe uma tensão conceptual entre incluir transações com a maior taxa e aquelas com o menor TTL. Assim, a qualidade de uma função de alocação x é quantificada comparando-a com a melhor função possível x′, quando confrontada com um ψ adversário de pior caso. A quantidade resultante é chamada de razão competitiva de x. Para permanecer compatível com a literatura sobre agendamento de pacotes, definimos a razão competitiva como o melhor desempenho offline possível dividido pelo desempenho online de uma função de alocação, em vez do contrário, e assim temos Rx ≥ 1. Um limite superior é então alcançado encontrando uma função de alocação que garanta bom desempenho, e um limite inferior é alcançado mostrando que nenhuma função de alocação pode garantir melhor desempenho.

\ \

\ \ \

2.4 Aquecimento: A Função de Alocação Gananciosa

A função de alocação Gananciosa, definida na Definição 2.6, é talvez um algoritmo clássico para o problema de agendamento de pacotes, e foi explorada pela literatura anterior para o caso não descontado. Além disso, evidências empíricas sugerem que a maioria dos mineradores alocam gananciosamente transações para blocos. Trabalhos anteriores mostram que no Bitcoin e Ethereum, transações que pagam taxas mais altas geralmente têm um tempo de espera menor no mempool, o que significa que são incluídas relativamente rápido em blocos [MACG20; PORH22; TFWM21; LLNZZZ22]. De facto, os algoritmos de seleção de transações padrão para o Bitcoin Core (a implementação de referência para clientes Bitcoin) e geth (o cliente de execução mais popular do Ethereum), priorizam transações com base nas suas taxas, embora o comportamento padrão de ambos possa ser substituído. É, portanto, de interesse ver o desempenho desta abordagem.

\ Definição 2.6 (A função de alocação Gananciosa). Dado algum conjunto de transações S, a função de alocação Gananciosa escolhe a transação com maior pagamento presente no conjunto S, desconsiderando o TTL:

\

\ No caso de existirem múltiplas transações com a mesma taxa, aquelas com o TTL mais baixo são preferidas.

\ No Exemplo 2.7, ilustramos como o desempenho do Ganancioso pode depender da taxa de desconto.

\ Exemplo 2.7. Examinamos o desempenho do Ganancioso dado o seguinte adversário ψ.

\

\ O cronograma de transações definido por ψ é representado na Fig. 1. No turno 1, o adversário transmite duas transações: (1, 2) que expira no final do turno e tem uma taxa de 2, e (2, 4) que paga uma taxa igual a 4 e expira no final do próximo turno. Como o Ganancioso prioriza transações com taxas mais altas, ele alocará (2, 4), deixando a outra transação expirar. No próximo turno, o adversário transmite uma única transação com um TTL de 2 e uma taxa de 6, que é a única disponível para o Ganancioso nesse turno, e assim será alocada. No passo 3, o adversário não emite nenhuma transação, e no passo 4, uma transação (1, 8) é transmitida e então alocada pelo Ganancioso.

\

\

\ No Lema 2.8, limitamos a razão competitiva do Ganancioso, como uma função da taxa de desconto.

\

\

\

\

:::info Autores:

(1) Yotam Gafni, Instituto Weizmann (yotam.gafni@gmail.com);

(2) Aviv Yaish, Universidade Hebraica, Jerusalém (aviv.yaish@mail.huji.ac.il).

:::

:::info Este artigo está disponível no arxiv sob licença CC BY 4.0 DEED.

:::

\