Как жадный алгоритм формирует вознаграждения майнеров в сетях блокчейн

Таблица ссылок

Резюме и 1. Введение

1.1 Наш подход

1.2 Наши результаты и дорожная карта

1.3 Связанные работы

1. Модель и разминка и 2.1 Модель блокчейна

   2.2 Майнер

   2.3 Игровая модель

   2.4 Разминка: Функция жадного распределения

2. Детерминированный случай и 3.1 Детерминированная верхняя граница

   3.2 Класс функций распределения с предпочтением срочности

3. Рандомизированный случай

4. Обсуждение и ссылки

• A. Отсутствующие доказательства для разделов 2, 3
• B. Отсутствующие доказательства для раздела 4
• C. Глоссарий

\

2.3 Игровая модель

Мы рассматриваем игру между противником и майнером. Эта перспектива направлена на количественную оценку того, сколько дохода майнер может потерять из-за неполного знания о будущих транзакциях при распределении текущих известных транзакций в предстоящий блок. В этом отношении активных пользователей системы можно рассматривать как всезнающую противоборствующую "природу", создающую наихудший сценарий расписания транзакций. Функция распределения не имеет знаний о будущих транзакциях, которые будут отправлены противником, поэтому оптимальное планирование на основе частичной информации, раскрываемой предыдущими транзакциями, может не быть лучшим курсом действий. Однако, что несколько удивительно, мы позже покажем, что на самом деле это так. Учитывая ставку дисконтирования майнера, существует концептуальное напряжение между включением транзакций с наибольшей комиссией и транзакций с наименьшим TTL. Таким образом, качество функции распределения x определяется путем сравнения ее с наилучшей возможной функцией x′ при столкновении с наихудшим противоборствующим ψ. Полученная величина называется конкурентным соотношением x. Чтобы оставаться совместимым с литературой по планированию пакетов, мы определяем конкурентное соотношение как наилучшую возможную автономную производительность, деленную на онлайн-производительность функции распределения, а не наоборот, и поэтому у нас Rx ≥ 1. Верхняя граница достигается путем нахождения функции распределения, гарантирующей хорошую производительность, а нижняя граница достигается путем доказательства того, что никакая функция распределения не может гарантировать лучшую производительность.

\ \

\ \ \

2.4 Разминка: Функция жадного распределения

Жадная функция распределения, определенная в Определении 2.6, возможно, является классическим алгоритмом для проблемы планирования пакетов и была исследована в предыдущей литературе для недисконтированного случая. Более того, эмпирические данные свидетельствуют о том, что большинство майнеров жадно распределяют транзакции по блокам. Предыдущие работы показывают, что в Биктоин и блокчейн Ethereum транзакции с более высокими комиссиями обычно имеют меньшее время ожидания в мемпуле, что означает, что они относительно быстро включаются в блоки [MACG20; PORH22; TFWM21; LLNZZZ22]. Действительно, алгоритмы выбора транзакций по умолчанию для Bitcoin Core (эталонная реализация для клиентов Bitcoin) и geth (самый популярный клиент исполнения Ethereum) приоритизируют транзакции на основе их комиссий, хотя поведение по умолчанию обоих может быть переопределено. Таким образом, интересно увидеть производительность этого подхода.

\ Определение 2.6 (Функция жадного распределения). Учитывая некоторый набор транзакций S, функция жадного распределения выбирает транзакцию с наивысшей оплатой, присутствующую в наборе S, игнорируя TTL:

\

\ В случае, если есть несколько транзакций с одинаковой комиссией, предпочтение отдается тем, у которых наименьший TTL.

\ В Примере 2.7 мы иллюстрируем, как производительность Жадного алгоритма может зависеть от ставки дисконтирования.

\ Пример 2.7. Мы исследуем производительность Жадного алгоритма при следующем противнике ψ.

\

\ Расписание транзакций, определенное ψ, изображено на Рис. 1. На ходу 1 противник транслирует две транзакции: (1, 2), которая истекает в конце хода и имеет комиссию 2, и (2, 4), которая платит комиссию, равную 4, и истекает в конце следующего хода. Поскольку Жадный алгоритм отдает приоритет транзакциям с более высокими комиссиями, он распределит (2, 4), позволяя другой транзакции истечь. На следующем ходу противник транслирует одну транзакцию с TTL 2 и комиссией 6, которая является единственной доступной для Жадного алгоритма на этом ходу, и, таким образом, будет распределена. На шаге 3 противник не выпускает никаких транзакций, а на шаге 4 транзакция (1, 8) транслируется и затем распределяется Жадным алгоритмом.

\

\

\ В Лемме 2.8 мы ограничиваем конкурентное соотношение Жадного алгоритма как функцию ставки дисконтирования.

\

\

\

\

:::info Авторы:

(1) Йотам Гафни, Институт Вейцмана (yotam.gafni@gmail.com);

(2) Авив Яиш, Еврейский университет, Иерусалим (aviv.yaish@mail.huji.ac.il).

:::

:::info Эта статья доступна на arxiv под лицензией CC BY 4.0 DEED.

:::

\