Ни один аукцион блокчейна не может удовлетворить UIC, MIC и Global SCP одновременно
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. Сравнение понятий с сговором сговора
Ссылки
3 предварительные: лемма Myerson's Lemma
Концептуально, пользовательяДолжен заплатить минимальную цену, которая подтверждает ее ставку.
4 разминка: невозможность UIC + MIC + Global SCP для детерминированных механизмов
В качестве разминки мы сначала показываем конечную невозможность для UIC + MIC + Global SCP длядетерминированныймеханизмы. Напомним, что TFM считается тривиальным, если вероятность подтверждения каждого равна нулю для любого вектора ставок, предполагая, что майнер следует правилу включения. В этом случае утилита каждого всегда равна честному исполнению. Мы покажем, что ни один нетривиальный механизм не может удовлетворить все три свойства одновременно. Позже в разделе 5 мы расширяем невозможность рандомизированных механизмов. Из-за принципа откровения, который мы доказываем в разделе 8, если мы сможем доказать невозможность правдивых механизмов, невозможность немедленно распространяется и на не правдивые механизмы. Поэтому в этом разделе мы будем принимать правдивые механизмы.
Лемма 4.1.Для любого глобального механизма SCP подтвержденные предложения должны соответствовать самым высоким предложениям.
ДоказательствоПолем Предположим, что в некотором сценарии Алиса требует своего истинного значения B, а Боб дает его истинную ценность B ′ <B; Тем не менее, ставка Боба подтверждается, а Алиса - нет. Теперь мы можем попросить Алису и Боб поменять свои заявки. Шахтер создает тот же блок, что и раньше, в котором позиция, первоначально соответствующая Бобу, теперь имеет ставку Алисы B ′. Поскольку механизм является слабо симметричным (определение 1), заявка Алисы подтверждается. Таким образом, социальное обеспечение увеличивается на B - B 'по сравнению с честным случаем, и это нарушает глобальный SCP.
Лемма 4.2.Для любого глобального механизма SCP количество сгоревших монет зависит только от количества подтвержденных ставок.
ДоказательствоПолем Предположим, в двух разных сценариях, когда все действуют честно, сделаны блокиБеременныйиБеременный′ Соответственно подтвержденные предложениябеременный ⊆ Беременныйибеременный′ ⊆ Беременный′ Соответственно гдебеременныйибеременный′ Имеет одинаковую длину, а сгорание в двух сценарияхQ.иQ ′соответственно, гдеQ. < Q ′Полем Теперь предположим, что мы на самом деле во втором сценарии. Глобальная коалиция может принять следующую стратегию: создать блок, идентичныйБеременныйв котором подтвержденные предложения соответствуют пользователям с самыми высокими истинными значениями, а остальные могут быть поддельными ставками. Обратите внимание, что социальное обеспечение является суммой истинных значений всех подтвержденных ставок (где поддельные предложения имеют истинное значение 0) за вычетом общих сгорев монет. Следовательно, вышеуказанная стратегия достигает строго более высокого социального обеспечения, чем честный случай.
Теорема 4.3.Ни один нетривиальный детерминированный TFM не может одновременно удовлетворять UIC, MIC и Global SCP, когда размер блока конечен.
5 Невозможность UIC + MIC + Global SCP для рандомизированных механизмов
В этом разделе мы расширяем конечную невозможность UIC + MIC + Global SCP даже рандомизированных механизмов. Напомним, что TFM состоит из пяти правил, как определено в разделе 2.1, и рандомизированный TFM может использовать случайность в любом из пяти правил. С момента подтверждения, платежа и правил доходов майнера выполняются блокчейн, стратегические игроки могут только смешивать случайность и отклоняться от правила торгов и правила включения. Опять же, из -за принципа откровения, доказанного в разделе 8, достаточно учитывать правдивые механизмы.
5.1 Доказательница дорожной карты
5.2 Формальные доказательства
В остальной части этого раздела мы представляем официальные доказательства.
ДоказательствоПолем Сначала мы докажем, что ожидаемое полезность майнера одинакова в обоих сценариях. Предположим, что это неправда, и без потери общности предположим, что ожидаемая полезность шахтера выше в сценарии. 1. Тогда шахтер может игнорировать заявкибеременный, вводить поддельные ставкибеременный′, Притворяйся, что вектор ставок (аВбеременный′) И запустите честный механизм. Поскольку вероятность подтверждениябеременный«Равна 0, майнеру не нужно платить каких -либо затрат на поддельные ставки. Следовательно, шахтер получает более высокую ожидаемую полезность, принимая вышеуказанную стратегию, которая нарушает MIC.
Доказательство общего социального обеспечения аналогично. Предположим, что без потери общности, что ожидаемое общее социальное обеспечение в сценарии 1 выше. Затем глобальная коалиция может вводить поддельные ставкибеременный′ И притворяется, что вектор ставок (аВбеременный′), Что позволяет ему увеличить ожидаемое социальное обеспечение. Это нарушает глобальный SCP.
Эквивалентность в общей пользовательской утилите следует непосредственно из вышеперечисленного, поскольку общая утилита пользователя заключается в разнице между социальным благосостоянием и утилитой шахтеров.
Лемма 5.5.Предположим, что механизм удовлетворяет UIC, MIC и Global SCP, а размер блока - K. Пусть будет любого положительного реального числа. Рассмотрим сценарий только с одной заявкой. Затем единственная утилита пользователя - это нулевая, предполагая, что он дает свое истинное значение.
Теорема 5.6.Никакая нетривиальная, возможно, рандомизированная TFM может одновременно удовлетворять UIC, MIC и Global SCP, когда размер блока конечен.
ДоказательствоПолем Мы покажем, что при любой достаточно большой A, вероятность подтверждения при одной ставке A не нулевой. Если мы сможем показать это, то мы можем показать противоречие с UIC. В частности, рассмотрите B> A и оба достаточно большие. По лемме 5.5, если есть только один пользователь с истинным значением B, его утилита равна нулю, когда он правдиво предлагает. Тем не менее, пользователь может недооценивать а. Поскольку вероятность подтверждения ненулевой, а платеж больше всего А, пользователь пользуется положительной утилитой, которая нарушает UIC.
Авторы:
(1) Хао Чунг ∗, Университет Карнеги -Меллона (haochung@andrew.cmu.edu);
(2) Тим Гроугарден †, Колумбийский университет и A16Z (Crypto tim.roughgarden@gmail.com);
(3) Элейн Ши ∗, Университет Карнеги -Меллона (runting@cs.cmu.edu).
Эта статья есть
Оригинал