Почему идеальный механизм платы за блокчейн может быть невозможным
4 августа 2025 г.Авторы:
(1) Хао Чунг ∗, Университет Карнеги -Меллона (haochung@andrew.cmu.edu);
(2) Тим Гроугарден †, Колумбийский университет и A16Z (Crypto tim.roughgarden@gmail.com);
(3) Элейн Ши ∗, Университет Карнеги -Меллона (runting@cs.cmu.edu).
Таблица ссылок
Аннотация и 1. Введение
1.1 Наши вклад
1.2 TFM Поощрительные представления о совместимости: шпаргалка
Определения
2.1 Механизм платы за транзакцию
2.2 Представления о совместимости стимулирования
Предварительная: лемма Майерсона
Разминка: невозможность UIC + MIC + Global SCP для детерминированных механизмов
Невозможность UIC + MIC + Global SCP для рандомизированных механизмов и 5.1 Доройся
5.2 Формальные доказательства
Осуществимость и невозможность UIC + MIC + OCA-защита
6.1 Непотянутый механизм с UIC + MIC + OCA-защищенным
6.2 Невозможность UIC + MIC + OCA-защита для правдивых механизмов
Как обойти невозможность и 7.1, позволяя глобально оптимальной стратегии координировать
7.2 Разрешение глобально оптимальной стратегии вывести несколько ставок
7.3 Обсуждения в отношении режима и 7.4 и открытые вопросы, касающиеся использования криптографии
Принцип статического откровения для механизмов платы за транзакцию
8.1 Принцип статического откровения: правила торга, которые выводят отдельную ставку
8.2 Принцип статического откровения: разрешение правил торгов, которые выводят несколько заявок
A. Сравнение понятий с сговором сговора
Ссылки
Абстрактный
Пользователи предлагают механизму комиссии за транзакцию (TFM), чтобы включить свои транзакции и подтвержденные с помощью протокола блокчейна. Roughgarden (EC'21) инициировал формальную обработку TFMS и предложил три требования: совместимость с стимулированием пользователя (UIC), совместимость с стимулированием шахтеров (MIC) и форма сговора сговора, называемая OCA-защищенностью. Механизм Ethereum EIP1559 удовлетворяет всем трем свойствам одновременно, когда между транзакциями нет споров, но теряет свойство UIC, когда есть слишком много приемлемых транзакций, чтобы соответствовать одному блоку. Чунг и Ши (Soda’23) считали альтернативным понятием сговора сговора, называемого C-Side-Contract-Pressness (C-SCP), и показали, что, когда между транзакциями существует споры, ни один TFM не может удовлетворить UIC, MIC и C-SCP для каких-либо C ≥ 1. OCA-подбодные утверждают, что пользователи и шахтер не должны быть способны «воровать». С другой стороны, условие C-SCP требует, чтобы коалиция шахтера и подмножества пользователей не смогли получить прибыль через стратегические отклонения (будь то за счет протокола или пользователей за пределами коалиции).
Нашим основным результатом является первое доказательство того, что, когда существует споры между транзакциями, нет (возможно, рандомизированным) TFM, в котором пользователи должны быть предъявлены, правдиво удовлетворяет UIC, MIC и OCA-защищение. Этот результат разрешает основной открытый вопрос в Roughgarden (EC'21). Мы также предлагаем несколько расслаблений базовой модели, которые позволяют обходить нашу невозможную результат.
1 Введение
Недвижимость на блокчейне мало, и пользователи блокчейна представляют собой аукцион, называемый механизмом платы за транзакцию (TFM), чтобы включить свои транзакции и подтвержденные на блокчейн. Оригинальный протокол биткойнов принял простой аукцион первой ценности, где выигрывают лучшие K, и каждый из них оплачивает свою ставку. Тем не менее, такие аукционы первой ценности, как известно, стимулируют неверные торги. Следовательно, линия последующих работ [LSZ19, YAO, BEOS19, BCD+, Rou20, Rou21, FMPS21, CS23, SCW23, WSC24, GY22, ZCZ22, BGR23, TY23, KKLP23, XFP23, CMW23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23. «Мечта TFM» для блокчейнов. Большинство работ [Rou20, Rou21, CS23, SCW23, WSC24, GY22, GY22, ZCZ22, BGR23, TY23] согласны с примерно одним и тем же набором Desiderata, то есть Dream TFM должны обеспечить стимулирующую совместимость не только для отдельного пользователя, но и для шахтера блока. Кроме того, Dream TFM должна обеспечить устойчивость против сговора с майнером-пользователем.
Roughgarden [Rou21] был первым, кто официально определил вышеупомянутые требования для TFM, который он назвал какПользовательская совместимость[1], (близорукий)Совместимость с стимулированием шахтера, иOCA-защита, где OCA означает «соглашение о не цепи» и относится к стратегиям сговора между майнером и набором пользователей, которые разрешают переводы за цепочку. Roughgarden [Rou21] также показал, что простой механизм «размещенного ценового аукциона со всеми сгораниями», который соответствует поведению Ethereum EIP-1559 TFM [BCD+], когда нет заторов, удовлетворяет все три свойства. Тем не менее, опубликованный аукцион цен со всеми счетными сборами не удовлетворяет все три объекта, когда есть перегрузка. На практике заторы возникают, когда существуют серьезные события, такие как NFT Mint или колебания цен - например, в Ethereum примерно 2,3% блоков испытывают заторы. [2] Когда возникает перегрузка, приблизительно говоря, механизм Ethereum EIP-1559 возвращается на аукцион первой цены, нарушая совместимость с стимулом пользователя. Поэтому интересный вопрос заключается в том, можем ли мы создать Dream TFM, удовлетворяющую все три свойства для конечных размеров блоков.
Чунг и Ши [CS23] считали альтернативным понятием сговора сговора, называемого SideContract-защищенным. К сожалению, они доказали, что ни один (даже рандомизированный) TFM не может одновременно удовлетворять совместимость с пользователем и боковой защиты. Поскольку боковой защитник является более требовательным свойством, чем OCA-защищенность, вопрос, поднятый Roughgarden [Rou21], о том, есть ли мечта, удовлетворяющая все три имущества под его представлением о сговоре, остается открытой.
Два понятия сговора с сговором сговора с майнером.Многочисленные естественные представления о сговоре сговора могут и были изучены в контексте дизайна TFM. Здесь мы неоднократно уточняем ключевые различия между понятиями, предложенными Rogegarden [Rou21] и Chung и Shi [CS23]. Эти понятия определяются формально в определениях 4–6 (см. Раздел 2) и сравниваются далее с помощью примеров в Приложении A.
• OCA-защитник:Появление Roughgarden, отныне и называемое OCA-защитой, утверждает, что существует «справочная стратегия» для майнера и всех пользователей, которые гарантируют максимизировать их совместный профицит. В этой справочной стратегии ожидается, что шахтер будет следовать правилу включения, предназначенное TFM. Для пользователей определение требует только того, чтобы пользователи следили за какой -то фиксированной тратегией σ (то есть отображение от частной оценки пользователя до пользовательской заявки), которая является индивидуально рациональным (то есть, σ (V) ≤ V для всех V ≥ 0). В частности, в справочной стратегии ожидается, что пользователи будут предлагать предложение независимо (с предложением пользователя независимо от оценки и предложений других пользователей), и ожидается, что они будут отправлять одну заявку (без дополнительных поддельных ставок). Одним из примеров такой стратегии торгов является стратегия по проверке правды (с σ (v) = V). Поскольку Roughgarden [Rou21] хотел обсудить свойства OCA-защиты не UIC TFM, таких как аукционы первой ценности, определение также позволяет определять справочную стратегию с помощью стратегии не правдивых торгов (например, σ (v) = V/2). Как следствие, чтобы доказать, что TFM является как UIC, так и OCA-защищенным, достаточно доказать, что он является UIC в соответствии с одной стратегией торгов и защитой от OCA в рамках, возможно, другой стратегии торгов (как в примере в разделе 6.1).
• в-SCP:Понятие Чунга и Ши [CS23], отныне называемое C-SCP (где SCP означает, что защита от SideContract) требует, чтобы честная стратегия (то есть все пользователи следуют правилу честной торгов, и шахтер честно реализовал правило включения), является стратегией, максимизирующей прибыль, для любой коалиции, состоящей из шахтера нынешнего блока и в большинстве случаев. Для правдивых механизмов правило честного торга является правдивым, в то время как для не туристических механизмов правило торгов может быть более общим (см. Раздел 2.1 для формального определения). Понятие Чанга и Ши согласуется со стандартными понятиями, используемыми в линейке работы на пересечении теории игры и криптографии [HT04, KN08, ADGH06, OPRV09, AL11, ACH11, GKM+13, GKTZ15, GTZ15, KAT08, DR07, GLR10, CGL+18, WAS22, CCWS21, PS2, PS2, PS2, PS21, CCWS21, PS2, PS2, PS2, CGWS21, PS2, PS2, CGWS2, PS2, CGWS21, PS2, PS2, CGWS2, PS2, PS2, PS2, PS21, CAT08. FW20, EFW22].
ДискуссияПолем Два понятия сговора сговора решают различные проблемы. OCA-защищенность отражает интуитивно понятное требование, чтобы пользователи и шахтерыне должно быть в состоянии украсть из протоколаЧерез стратегические отклонения - по этой причине, это рассматриваетТолько глобальная коалициясостоящий из шахтера и всех пользователей. В отличие от этого, понятие C-SCP отражает интуитивную идею о том, что лучшим ответом коалиции майнера является действовать честно, и что никакие стратегические отклонения не могут позволить коалицииукрасть у других пользователей или украсть из протоколаПолем Для дальнейшего обсуждения см. Конец этого раздела и Приложение A.
Эта статья есть
∗ Поддержан NSF Awards 2212746, 2044679, 1704788, стипендием Packard, щедрый подарок от покойного Nikolai Mushegian, подарок от Google и грант ACE Center от Algorand Foundation.
† Исследование автора в Колумбийском университете частично поддерживается NSF Awards CCF-2006737 и CNS-2212745, а также исследовательские награды из лаборатории цифровых финансов Family Family и Центра цифровых финансов и технологий.
[1] Совместимость с стимулированием пользователя (UIC) обычно называется доминантной стратегической стимулируемой, совместимой (DSIC) в литературе по проектированию механизма. В целом, мы позволяем UIC TFMS использовать не туристические (но доминирующие) стратегии торгов (см. Определение 2).
[2] С 1 января 2024 года по 5 февраля 2024 года на Ethereum были произведены блоки 256595, а среди них было полным 5840 блоков (что означает более 99,9% газового предела (30 м)).
Оригинал