Как обойти теоремы невозможности в проектировании механизма блокчейна
5 августа 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. Сравнение понятий с сговором сговора
Ссылки
7 Как обойти невозможность
В этом разделе мы обсуждаем возможные способы обойти невозможность. Напомним, что в определении OCA-защиты мы требуем, чтобы все пользователи действовали независимо в глобально оптимальной стратегии σ, а σ должно выводить только одну ставку. Если мы удалим любое из двух требований, мы можем иметь механизмы, которые удовлетворяют UIC, MIC и OCA-защищенность, где мы представляем в разделах 7.1 и 7.2. Эти механизмы несколько надуманны и не имеют явно актуальны для реальных протоколов блокчейна; Основная точка этих механизмов состоит в том, чтобы «тестировать» на стресс-тестирование »определений, и эти примеры подчеркивают тонкость моделирования и помогают нам лучше понять компромиссы между различными представлениями о притяжении сговора. В разделе 7.3 мы рассмотрим еще более слабое определение, называемое воспринимающим обращение с режимом включения, которое может быть самым слабым, но все же значимым определением, которое отражает понятие «нет способа украсть из протокола». Наконец, в разделе 7.4 мы обсудим использование криптографии в литературе TFM и указываем будущее направление, используя криптографию и байесовскую совместимость.
7.1 Разрешение глобально оптимальной стратегии координировать
OCA-защита требует, чтобы все пользователи действовали независимо в глобальной оптимальной стратегии σ. Однако, если мы удалим это ограничение, то следующий аукцион будет одновременно удовлетворить UIC, MIC и OCA-защищенные (с вышеупомянутой релаксацией).
Опубликованный ценовой аукцион со случайным выбором и общим сжиганием.Механизм параметризован с некоторой резервной ценой r> 0 и размером блока K. Любая ставка, которая, по крайней мере, R, считается подходящей. Случайно выберите до k предложения, чтобы включить в блок. Все включенные предложения подтверждены, и каждый из них платит r. Весь оплата сожжена, и шахтер ничего не получает. Нетрудно видеть, что приведенный выше механизм удовлетворяет UIC и MIC. Он также удовлетворяет защите от OCA с вышеупомянутой релаксацией, поскольку глобальная коалиция может просто иметь пользователей с лучшими значениями K, которые ставят больше, чем R, в то время как все остальные предлагают 0.
Обратите внимание, что разрешение всем пользователям координировать заявки не тривиализирует определение, поскольку это расслабленное определение OCA-защиты по-прежнему требует, чтобы майнер честно следовал правилу включения TFM. Например, на вышеуказанном аукционе шахтер должен выбирать k предложения в случайном порядке среди всех подходящих предложений.
7.2 Разрешение глобально оптимальной стратегии вывести несколько ставок
Затем мы показываем, что, когда мы позволяем глобально оптимальной стратегии σ вывести несколько ставок, мы можем фактически построить правдивый механизм, который удовлетворяет UIC, MIC и OCA-защите. Подобно разделу 6.1, мы стараемся сигнализировать на механизм, когда все принимают глобально оптимальную стратегию σ. В этом механизме, поскольку σ может выводить несколько ставок, пользователи могут сигнализировать через поддельные заявки. Мы предполагаем, что майнер и механизм могут различать, поступает ли набор предложений от одного и того же пользователя. На практике это может быть реализовано путем проверки того, подписаны ли эти предложения тем же открытым ключом. В частности, рассмотрим следующий механизм, параметризованный резервной ценой r> 1.
• Глобально оптимальная стратегия σ(v): Если истинное значение пользователя v ≥ R, выходы σ (v) (r, r/v), где r/v ∈ (0, 1] является уникальным декодируемым кодированием истинного значения пользователя v. В противном случае, если v <r (v) просто выводит ∅, т. Е. Пользователь отказывает свою заявку.
• Правило включения.
• Правила подтверждения, оплаты и доходов майнера:Все включенные предложения, которые, по крайней мере, R, подтверждены. Каждая подтвержденная ставка оплачивает r, а шахтер ничего не получает.
Претензия 7.1.Приведенный выше механизм удовлетворяет МСП, микрофону и расслабленному понятию OCA-защиты, в которой σ позволяет выводить несколько ставок.
Доказательство UIC - самая сложная часть. Исправить любого пользователяяПолем Обратите внимание, что каждая подтвержденная заявка оплачиваетведущий, поэтому, если пользователь I истинное значение больше всеговедущий, он не может получить положительную полезность независимо от своей ставки. Таким образом, заявка правдиво является доминирующей стратегией. Отныне мы предполагаем, что истинное значение пользователя I строго больше, чемведущийПолем Есть две возможности.
Во -первых, до того, как пользователь я предъявляю свою ставку, вектор ставок содержит ровно n предложений на R, а n предложенных в диапазоне (0, 1] для некоторого n. Затем, по правде говоря, в случае 3 -го случая, когда ставка пользователя I гарантированно будет включена и подтверждена, и, таким образом, максимизирует утилиту.
Во -вторых, до того, как пользователь я подал свою ставку, вектор ставок не содержит точно n предложений на R, а n предложения лежат в диапазоне (0, 1] для некоторых n. Предположим, что нет никаких ставок строго больше, чем r в векторе ставок перед пользователемяпредставляет свою ставку. Затем, если пользователь я буду правдиво, его ставка будет единственной ставкой, больше, чем R, а правило включения внесет в случай 4. Поскольку k ≥ 1, ставка пользователя I гарантированно включена и подтверждена, и, таким образом, максимизирует утилиту. С другой стороны, предположим, что в векторе ставок есть T ≥ 1 предложения, чем R, прежде чем пользователь я подаст свою ставку. Затем включение никогда не может перейти в случай 1 или Case 2. Если пользователь I честен, правило включения должно перейти в Case 4, а ставка пользователя I включена в вероятность min (k, t + 1)/(t + 1). Однако, если стратегические торговцы приводят к случаю 3, это должно быть t = 1. Затем вероятность включения пользователя I упала с 1/2 до 0, если k = 1, или от 1 до максимум 1, если k ≥ 2. С другой к нулевой вероятности включения, которая приводит к нулевой полезности. Наконец, обратите внимание, что инъекция поддельных ставок никогда не помогает в случае 4. Таким образом, во всех случаях полезность лучше, чем торгуя правдивыми.
Напомним, что слабо симметричные механизмы не используют идентичность участников торгов или другую вспомогательную информацию, за исключением разбивания связей среди равных предложений. Поскольку приведенный выше механизм опирается на тот факт, что правило включения может различить, поступает ли набор предложений от одного и того же пользователя, может быть не очевидно, что механизм удовлетворяет слабой симметрии. Следующая претензия доказывает это формально.
Претензия 7.2.Приведенный выше механизм удовлетворяет слабой симметрии.
ДоказательствоПолем Чтобы показать слабую симметрию, мы даем эквивалентное описание следующим образом. Учитывая вектор BID B, алгоритм сортировки проверяет, удовлетворяет ли B условие случая 1. Если так, то алгоритм сортировки помещает множественные R предложенных предложений, соответствующих вектору истинного значения (V1, ..., VN) (определено в случае 1 выше) от высокого до низкого уровня, и сортирует остальное в посчетном порядке. В противном случае, если B не удовлетворяет условию случая 1, алгоритм сортировки сортирует B в порядке убывания и произвольно разбивает галстук.
В исходном механизме единственный случай, который зависит от дополнительной информации (идентификация, в данном случае), - это случай 1. Применение алгоритма сортировки, описанного выше, правило включения может реализовать случай 1 только в зависимости от количества заявок и их относительного положения в спирренном векторе ставок.
7.3 Оценка режима включения
Также естественно рассмотреть дальнейшее расслабление OCA-защиты, отныне называемое «InclusionRule, уважающим». По сравнению с защитой от OCA, воспринимание по отношению к правилам включения только требует, чтобы глобально оптимальная стратегия не включала изменение правила включения, и все остальные ограничения на σ удалялись. Отвещение на правиле включения строго слабее, чем понятия в разделе 7.1 и раздел 7.2. Следовательно, механизмы, упомянутые в разделе 7.1 и в разделе 7.2, одновременно удовлетворяют МСП, MIC и относительно воспитания включения.
Понятие «воспринимание с учетом обработки включения» имеет интуитивную интерпретацию: оно препятствует изменению предполагаемой реализации протокола; Другими словами, все стратегии прибыли могут быть реализованы в качестве стратегий торгов над уровнем протокола. В этом смысле «Ruleerseying» также отражает интуицию «нет способа украсть из протокола». Можно также просмотреть это следующим образом: глобальный SCP захватывает «не воровство из протокола», где протокол является союзом правила включения шахтера, а также честных стратегий торгов пользователей; и воспринимающий в образе включения отражает то же представление, но где протокол является лишь базовым протоколом блокчейна. OCA-защита где-то посередине.
7.4 Обсуждения и открытые вопросы, касающиеся использования криптографии
Другой интересный вопрос заключается в том, можем ли мы преодолеть невозможность, используя криптографию. Shi et al. [SCW23] показали, что если правила TFM применяются с помощью многопартийного вычислительного протокола (впредь названы моделью с помощью MPC), то мы можем спроектировать TFM конечного блока, который одновременно удовлетворяет UIC, MIC и 1-SCP (в смысле экс-пост). С другой стороны, Shi et al. Также показали, что одновременно достижение МСИ, МИК и C-SCP для C ≥ 2 невозможно в модели с помощью MPC, даже для байесовских представлений о равновесии. Отчасти это связано с тем, что даже при соблюдении протокола MPC правило включения стратегический майнер или пользователь все еще может вводить поддельные ставки, а механизм не знает количество заявок заранее (то есть механизм «без разрешений»). Это интересный открытый вопрос, может ли использование криптографии и байесовские представления о равновесии помочь нам преодолеть невозможность в этой статье. В частности, Shi et al. [SCW23] предположил, что модель с помощью MPC также оправдывает расслабленное представление о байесовском равновесии, поскольку игроки не могут видеть предложения других, прежде чем публиковать свои собственные.
Авторы:
(1) Хао Чунг ∗, Университет Карнеги -Меллона (haochung@andrew.cmu.edu);
(2) Тим Гроугарден †, Колумбийский университет и A16Z (Crypto tim.roughgarden@gmail.com);
(3) Элейн Ши ∗, Университет Карнеги -Меллона (runting@cs.cmu.edu).
Эта статья есть
Оригинал