Почему правдивые механизмы блокчейна терпят неудачу в конечных размерах блоков
4 августа 2025 г.Таблица ссылок
Аннотация и 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. Сравнение понятий с сговором сговора
Ссылки
1.1 Наши вклад
Как объяснено выше, и понятия как Roughgarden, и Chung и Shi по сговору, отражают соображения совместимости значимых стимулов. Признавая их различия, один из естественных вопросов заключается в следующем: до сих пор сохраняется результат невозможности Чунга и Ши, если мы примем первоначальное представление о OCA-защите от Roughgarden вместо C-SCP? Примечательно, что нет существующей конструкции TFM [LSZ19, YAO, BEOS19, BCD+, Rou20, Rou21, FMPS21, CS23, SCW23, WSC24, GY22, ZCZ22, BGR23, TY23, KKLP23, XFP23, CMW23, LRRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23, LRMP23. Удовлетворяет совместимость с стимулированием пользователя, совместимость с стимулом для майнера и защиту от OCA под конечным размером блока.
Основной невозможность результата.В нашей работе мы даем утвердительный ответ на вышеуказанный вопрос. Мы показываем, что, действительно, аналог с конечной невозможностью Чунга и Ши все еще сохраняется, когда мы заменяем требование C-SCP на защиту от OCA. В частности, мы докажем следующую теорему.
Теорема 1.1ПолемПредположим, что размер блока конечен. Затем, возможно, ни один, возможно, рандомизированный, правдивый TFM одновременно удовлетворить совместимость с поощрением пользователя (UIC), совместимость с стимулированием шахтеров (MIC) и OCA-защищенность. Кроме того, эта невозможности сохраняется, даже когда глобально оптимальная стратегия σ не должна быть индивидуально рациональной.
В правдивом TFM ожидается, что пользователь будет правдой, поэтому, если механизм удовлетворяет UIC, утилита пользователя максимизируется, когда он просто сообщает о своем истинном значении. Тем не менее, OCA-защита позволяет глобальной коалиции принять стратегию не туристической торговли σ даже для правдивых механизмов.
Наша теорема 1.1 интуитивно сильнее, но технически несравненная по сравнению с невозможностью Чунга и Ши, что показывает, что ни один TFM не может одновременно удовлетворять UIC и 1-SCP для конечных размеров блоков. Причина в том, что невозможность Чанга и Ши не полагается на микрофон; Тем не менее, микрофон необходим для нашей теоремы 1.1. В частности, простой аукцион второй ценности без сжигания (см. Замечание 2) удовлетворяет как UIC, так и OCA-защите, но не удовлетворяет микрофону, поскольку майнер может выиграть, внедряя фальшивую (t + 1) -кую ставку, где t-это количество подтвержденных заявок, поскольку (t + 1) -ная ставка устанавливает цену для подтвержденных ставок.
Global SCP.Мы предлагаем более простую версию OCA-защиты, которую мы называем Global SCP, которая также интуитивно отражает требование о том, что стратегические пользователи и шахтеры не могут украсть из протокола, и, возможно, более уместно при сосредоточенности на UIC TFM (как мы делаем в этой статье). В нашей работе Global SCP - это не только техническийступенькак доказательству теоремы 1.1, но также и онезависимый интерескак мы объясняем ниже. В частности, Global SCP почти такой же, как и Ocaproofness, за исключением того, что σ - честная стратегия торгов, обозначенную механизмом (т. Е. Та же стратегия торгов, используемая для создания UIC). Другими словами, механизм удовлетворяет глобальному SCP, когда и только тогда, когда честная стратегия максимизирует избыточное количество для глобальной коалиции. Легко увидеть, что для правдивого механизма C-SCP для любого C подразумевает глобальный SCP, который, в свою очередь, подразумевает защиту от OCA. Чтобы доказать теорему 1.1, мы сначала докажем следующую теорему:
Теорема 1.2.Предположим, что размер блока конечен. Тогда, возможно, ни один, возможно, рандомизированный TFM не может одновременно удовлетворить совместимость с пользователем (UIC), совместимость с стимулированием майнера (MIC) и Global SCP. Кроме того, невозможность относится даже к не туристическим механизмам.
Теперь мы объясняем, почему глобальное представление SCP представляет независимый интерес. Одним из преимуществ Global SCP является то, чтоПринцип откровенияСледует за любым TFM, который удовлетворяет UIC, MIC и Global SCP, которые мы формально доказываем в разделе 8. Другими словами, учитывая любой TFM, который является UIC, MIC и Global SCP, существует эквивалентный правдивый механизм, который имутирует его. По этой причине теорема 1.2 исключает даже не туристические TFM, которые одновременно удовлетворяют UIC, MIC и Global SCP. [3]
Напротив, теорема 1.1 работает только для правдивых механизмов. В частности, в разделе 6.1 мы показываем не потушимый механизм, который одновременно удовлетворяет UIC, MIC и OCA. Механизм надуман, но он демонстрирует тонкость и технические проблемы при моделировании понятия сговора. Это также предполагает, что принцип откровения не поддерживается для механизмов, которые удовлетворяют МСИ, микрофоническим и окапливаемым, отчасти потому, что в таком механизме стратегии торгов, используемые для установления МСБ и защиты от OCA, могут отличаться.
Способы обойти невозможность.В разделе 7 мы показываем, что невозможность теоремы 1.1 можно обойти, позволяя не по правдечке следовать механизмы или позволив пользователям координировать при торгах в глобально оптимальной стратегии σ. В том же разделе мы поднимаем открытый вопрос относительно того, можно ли использовать криптографию (например, модель MPC с помощью Shi et al. [SCW23]) и байесовские представления о совместимости стимулирования, чтобы обойти невозможности.
Авторы:
(1) Хао Чунг ∗, Университет Карнеги -Меллона (haochung@andrew.cmu.edu);
(2) Тим Гроугарден †, Колумбийский университет и A16Z (Crypto tim.roughgarden@gmail.com);
(3) Элейн Ши ∗, Университет Карнеги -Меллона (runting@cs.cmu.edu).
Эта статья есть
[3] Одновременно с и независимо от этой статьи Гафни и Яиш [GY24] доказали, среди прочих результатов версии теоремы 1.2 для особого случая детерминированных механизмов и размера блока 1.
Оригинал