Теорема о невозможности, стоящая за правдивыми механизмами блокчейна
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. Сравнение понятий с сговором сговора
Ссылки
6 осуществимость и невозможность UIC + MIC + OCA-защита
Мы можем обобщить доказательство в разделе 5 и исключить UIC, MIC и OCA-защищенные (а не глобальные SCP) для правдивых механизмов. Напомним, что для правдивого механизма разница между OCA-защищенным и глобальным SCP заключается в том, что Global SCP настаивает на том, что оптимальной стратегией глобальной коалиции является правдивая стратегия, тогда как OCA-защищенность позволяет быть какой-то другой стратегией, в которой каждый пользователь действует независимо и дает результат некоторой функции σ (·).
Интересно, что если мы допустим, чтобы правило торгов не было не рассказывать правде, то есть, учитывая не правдивые механизмы, у нас может быть механизм, который удовлетворяет UIC, MIC и OCA-защите. Мы представляем осуществимость для не правдивых механизмов в разделе 6.1, и мы доказываем невозможность UIC + MIC + OCA-защищенных для правдивых механизмов в разделе 6.2. Обратите внимание, что из-за осуществимости в разделе 6.1 мы должны требовать, чтобы правило торгов было правдой, чтобы достичь невозможности в разделе 6.2.
6.1 Непотянутый механизм с UIC + MIC + OCA-защищенным
Обоснование проекта заключается в том, чтобы сигнализировать о механизме, когда каждый принимает глобально оптимальную стратегию σ (в отличие от правила торгов, используемого для установления МСК). Когда механизм обнаруживает, что каждый ведет себя в соответствии с σ, он принимает другое поведение для оптимизации социального обеспечения. Мы используем диапазон [0, 1), чтобы кодировать фактическую ставку, и используем диапазон [1, ∞) для передачи сигналов. Хотя результирующий механизм несколько надуман и не обязательно значимый с практической точки зрения, он разъясняет, какие понятия о сговоре, наиболее точно отражают предполагаемые цели моделирования и иллюстрируют некоторые технические проблемы, связанные с доказательством в разделе 6.2. Рассмотрим следующее TFM:
• глобально оптимальная стратегияσ (v): Учитывая истинное значение v, вывод BID V + 1.
• Правило торгов: Учитывая истинное значение v, вывод BID 1/(V + 2).
• Правило включения: Пусть S - набор всех ожидающих предложений, которые находятся в [0, 1). Если | s | > k, затем случайным образом выбирайте k предложения из S, чтобы включить. Если 1 ≤ | s | ≤ k, затем включите все предложения в S. if | s | = 0, выберите «Поверхность до k», чтобы включить.
• Правила подтверждения, оплаты и доходов майнера: Все включенные предложения подтверждены. Каждая подтвержденная ставка ничего не платит, и шахтер ничего не получает.
Очевидно, этот механизм нетривилен.
Требование 6.1.Вышеуказанный механизм удовлетворяет UIC, MIC и OCA-защите.
ДоказательствоПолем Для UIC обратите внимание, что если пользователь следует правилу торга, его ставка всегда находится в [0, 1). Если в [0, 1) до того, как пользователь предъявит свою заявку, не будет предложения, то ставки 1/(v + 2) всегда гарантирует, что ставка пользователя будет включена и подтверждена, где V обозначает истинное значение. Если в [0, 1) до того, как пользователь подает заявку, уже есть некоторые предложения, то ставки 1/(v + 2) являются доминирующей стратегией, поскольку она гарантирует, что ставка пользователя добавляется в S, набор всех заявок в [0, 1), что лучшее, что может сделать пользователь. Далее, MIC удерживает, так как доход шахтеров всегда нулевой. Наконец, если все пользователи следуют глобально оптимальной стратегии σ, предложение каждого составляет как минимум 1. Правило честного включения будет включать в себя пополнение до k предложения, что максимизирует социальное обеспечение. Таким образом, OCA-защита держит.
Замечание 1.Мы можем попытаться применить принцип откровения и испечь правило торгов в механизм, чтобы результирующий механизм был правдивым. Например, всякий раз, когда увидев ставку B, шахтер и механизм рассматривают его как 1/(B + 2). Модифицированный механизм, однако, больше не удовлетворяет Ocaproofness, когда число пользователей больше, чем размер блока, поскольку майнер должен выбрать k пользователей с самыми высокими значениями истинными вместо случайного выбора, как указано правилом включения. Это не совпадение: в следующем разделе мы показываем, что невозможно иметь нетривиальный правдивый механизм, удовлетворяющий UIC, MIC и защиту от OCA.
Авторы:
(1) Хао Чунг ∗, Университет Карнеги -Меллона (haochung@andrew.cmu.edu);
(2) Тим Гроугарден †, Колумбийский университет и A16Z (Crypto tim.roughgarden@gmail.com);
(3) Элейн Ши ∗, Университет Карнеги -Меллона (runting@cs.cmu.edu).
Эта статья есть
Оригинал