В этом исследовании используются модели Маркова, чтобы разорвать справедливость блокчейна
2 июля 2025 г.Авторы:
(1) Krishnendu Chatterjee, IST Австрия, Австрия (Krishnendu.chatterjee@ist.ac.at);
(2) Амирали Эбрагимзаде, Технологический университет Шарифа, Иран (ebrahimzadeh.amirali@gmail.com);
(3) Мехрдад Карраби, Ист Австрия, Австрия (Mehrdad.karrabi@ist.ac.at);
(4) Krzysztof Pietrzak, IST Австрия, Австрия (Krzysztof.pietrzak@ist.ac.at);
(5) Мишель Йео, Национальный университет Сингапура, Сингапур (mxyeo@nus.edu.sg);
(6) ðorđe žikelić, Сингапурский университет управления, Сингапур (dzikelic@smu.edu.sg).
Таблица ссылок
Аннотация и 1. Введение
1.1 Связанная работа
Предварительные
2.1 Системная модель
2.2 Цель эгоистичной добычи
2.3 Процессы принятия решений Маркова
Эгоистичная горнодобывающая атака
3.1 Обзор
3.2 Формальная модель
3.3 Формальный анализ
3.4 Ключевые функции и ограничения
Экспериментальная оценка
Заключение, подтверждение и ссылки
A. NAS Mining Цели
B. Системы эффективных доказательств
C. Доказательство теоремы 3.1
АБСТРАКТНЫЙ
Мы изучаем эгоистичные атаки добычи в блокчанах с самой длинной цепью, такие как биткойны, но там, где доказательство работы заменяется эффективными системами доказательств-например, доказательства ставки или доказательств пространства-и рассмотрим проблему вычисления оптимальной эгоистичной горнодобывающей атаки, которая максимизирует ожидаемый относительный доход противника, тем самым минимизирующий качество цепи. С этой целью мы предлагаем новую эгоистичную горнодобывающую атаку, которая стремится максимизировать эту цель и формально моделировать атаку как процесс принятия решений Маркова (MDP). Затем мы представляем формальную процедуру анализа, в которой вычисляется 𝜖-уплотняя нижняя граница с оптимальным ожидаемым относительным доходом в MDP, и стратегию, которая достигает этой 𝜖-уплотненной нижней границы, где 𝜖> 0 может быть какой-либо определенной точностью. Наш анализ полностью автоматизирован и предоставляет официальные гарантии на правильность. Мы оцениваем нашу эгоистичную атаку добычи полезных ископаемых и наблюдаем, что она достигает превосходного ожидаемого относительного дохода по сравнению с двумя рассматриваемыми базовыми показателями.
В одновременной работе [Sarenche FC’24] проводит автоматический анализ эгоистичной добычи впредсказуемыйБлокчейны с самой длинной цепью на основе эффективных систем доказательства. Предсказуемые означает, что случайность для проблем фиксируется для многих блоков (как используется, например, в Uwoboros), в то время как мы рассматриваемнепредсказуем(Биткойн-подобные) цепи, где вызов получен из предыдущего блока.
1 Введение
БиткойнПолем Протоколы блокчейна были предложены в качестве решения для достижения консенсуса в некоторых штатах (например, финансовых транзакциях) в распределенной и беспрепятственной (то есть каждый может участвовать в обеспечении цепочки). Участники протоколов блокчейна добавляют данные в блоки, которые затем добавляются в блокчейн с некоторой вероятностью, которая зависит от базового протокола консенсуса. Самый ранний и наиболее распространенный протокол консенсуса является доказательством работы (POW), которое также составляет основу протокола блокчейна биткойн [21].
Доказательство работыПолем Стороны, которые поддерживают блокчейн Pow, такие как биткойн, называются шахтерами. Общая идея заключается в том, что для того, чтобы добавить блок в цепь, шахтеры получают вычислительно жесткую, но легко проверяемую головоломку из кончика цепи. Чтобы добавить блок в цепь, этот блок должен содержать решение этой головоломки. Этот механизм гарантирует, что нападение на цепь, в частности, переписывая прошлые блоки в атаке с двойными расходами, вычислительно очень дорого. В биткойнах головоломка представляет собой Hashcash Style POW [2], причем параметры являются уровнем сложности 𝐷 и глобальной хэш -функцией (например, SHA256). Недавно сгенерированный блок может быть добавлен в цепь только в том случае, если хэш нового блока, предыдущий блок, открытый ключ шахтера и некоторые нере, дают значение, которое меньше текущей сложности 𝐷. Чтобы добывать блок в биткойнах, шахтеры будут постоянно генерировать разные нежи и хитры, пока они не найдут нера, который проходит пороговое значение. Счастливый шахтер, который сначала находит блок, транслирует его по всей сети, где другие майнеры могут легко проверить обоснованность Nonce. Протокол биткойнов указывает, что шахтеры всегда должны работать над тем, чтобы расширить самую длинную цепь, о которой они знают, поэтому такие цепочки называются «самая длинная цепочка». Альтернативный подход - это цепи, основанные на византийской устойчивости к разломам, таким как алгоранд [6], где случайно вращающиеся комитеты одобряют добавленные блоки.
Эффективные системы доказательствПолем В качестве альтернативы POW были предложены несколько других консенсусных протоколов, основанных на эффективных системах доказательств [8, 9, 23]. Как правило, мы говорим, что «доказательство X» является эффективным, если вычисление доказательства для случайной задачи очень дешево, если у них есть ресурс X. Например, наиболее популярные и наиболее изученные эффективные доказательства являются доказательствами коляска (почтового), например, используемых в Touboros [9] или Post-Merge Ethereum. Здесь монеты, записанные в блокчейне, являются ресурсом. Другим предложением фактического физического ресурса являются доказательства пространства (Pospace) [10], где ресурс находится на дисковом пространстве. Первым предложением для цепи на основе Pospace было пространство [23]. Первой развернутой сетью была сеть CHIA [8], она использует Pospace в сочетании с проверяемыми функциями задержки (VDF) для решения некоторых проблем безопасности и, таким образом, называется доказательством цепочки пространства и времени (POST). См. Приложение B для получения более подробной информации о блокчейнах на основе эффективных систем доказательства, которые мы рассматриваем в нашей работе.
Эгоистичная добычаПолем Существуют различные свойства безопасности, которые мы хотим от блокчейнов с самой длинной цепью, наиболее важными являются настойчивость и жизнь [16]. Неофициально, настойчивость означает, что записи, добавленные в цепь, останутся там навсегда, в то время как жизнь означает, что цепочка остается доступной. Менее очевидным требованием является справедливость, в том смысле, что сторона, которая вносит 𝑝 долю ресурса (хэширующая сила в военнопленном, пространство в посте, стадильные монеты в почтовой стороне), должна вносить 𝑝 долю блоков и, таким образом, получить 𝑝 фракцию вознаграждений.
Вначале в [11] было замечено, что биткойн не справедливый в этом смысле из -заэгоистичная добычаатаки. В эгоистичной добыче, нападавшие мины блокируются, но иногда выборочно удерживают их (поэтому честные шахтеры не могут добывать поверх них), чтобы позже освободить их, обгоняя честную цепь и, таким образом, отиротев честные блоки. При этом злоумышленники могут уменьшитьКачество цепиБлокчейна [11], эта мера количественно определяет долю блоков, предоставленных состязательным шахтером
Хотя анализ эгоистичной майнинга и ее влияние на качество цепи хорошо изучено в биткойнах и других блокчейнах на основе мощности [11, 19, 27, 31], тщательный анализ оптимальных эгоистичных майнинговых атак в блокчейнах, основанных на эффективных системах доказательств, является затруднением из-за того, что вычислительные затраты на получение доказательств в этих системах. Это приводит к нескольким вопросам, которые в настройке почтового поставки обычно называют проблемой «ничто-нерадостного» (NAS). [1]
Дилемма предсказуемости безопасности против предсказуемостиПолем Предположим, что можно наивно заменить POW в биткойнах на систему эффективной доказательства, такую как Postake. Поскольку вычислительные доказательства теперь дешевы, шахтер состязательного состязания может попытаться расширить блоки на разных глубинах (не только на кончике самой длинной цепи), выращивая частные деревья на каждой глубине. Если им удастся создать дерево глубины 𝑑, которое начинается меньше, чем 𝑑 блоки глубоко в общедоступной цепочке, освобождение самого длинного пути в этом дереве заставит честных шахтеров переключиться на этот путь. Такие атаки «выращивание деревьев» могут быть предотвращены путем отвлечения от биткойн-подобных протоколов, и вместо использования блока на глубине 𝑖 для получения задачи для блока на глубине 𝑖 + 1, человек использует некоторую фиксированную случайность для определенного количества последовательных блоков. К сожалению, это создает новую проблему безопасности, поскольку противник теперь может предсказать, когда в будущем они смогут создавать блоки [3, 5]. Мы отмечаем, что этот подход используется в цепочке Touroboros на основе почты [9], где один создает только свежий вызов каждые пять дней. Экстремальностью в другом направлении является цепочка Spacemint на основе Pospace [23] или раннее предложение цепочки Chia на основе пост [7], которая, как и биткойн, получает задачу из предыдущего блока (развернутая конструкция Chia [8] использует свежий вызов каждые 10 минут, или 32 блока).
(1) (модель), хотя и были также некоторые недавние работы, анализирующиеэгоистичная добычаАтаки в блокчейнах на основе эффективных систем доказательств [8, 12, 14, 19, 28, 29], эти анализы до сих пор были сосредоточены только на предсказуемых протоколах.
(2) (методология) Кроме того, они либо рассматривают различные состязательные цели [8, 12, 14, 29], либо используют обучение глубокому подкреплению для получения эгоистичных стратегий добычи [19, 28]. Однако обучение глубоким подкреплением только эмпирически максимизирует цель и не предоставляетФормальные гарантиио качестве (нижняя или верхняя граница) изученных стратегий.
Наш подходПолем В этой работе мы представляем первый анализ эгоистичной майнинга в непредсказуемых блокчейнах самой длинной цепь на основе эффективных систем доказательств. Напомним, что в таких цепях задача для каждого блока определяется предыдущим блоком. На каждом временном шаге противник должен решать, добывать ли новые блоки или публиковать один из их личных вилок, который длиннее публичной цепочки. Наш анализ связан с обнаружением оптимальной последовательности майнинга, а вилка выявляет действия, которые должен следовать противнику, чтобы максимизировать ожидаемый относительный доход (то есть соотношение ожидаемых состязательных блоков в основной цепочке при выполнении данной стратегии по сравнению с общим количеством блоков в цепочке). Обратите внимание, что это сложная проблема. Поскольку на каждом шаге противник может выбрать между добычей новыми блоками и публикациейлюбойИз своих частных цепей стратегическое пространство противника является экспоненциальным по количеству частных вилок, что делает ручной формальный анализ неразрешимым.
Чтобы преодолеть эту проблему, мы моделируем нашу эгоистичную атаку добычи какКонечный процесс принятия решений марков(MDP) [26]. Затем мы представляем формальную процедуру анализа, которая, учитывая точный параметр 𝜖> 0, вычисляет
• 𝜖-плотная нижняя граница на оптимальном ожидаемом относительном доходечто может достичь эгоистичная стратегия добычи в MDP, и
• аЭгоистичная горнодобывающая стратЕги достигает этой утяжной нижней границы.
В основе нашей формальной процедуры анализа лежит сокращение от проблемы вычисления оптимальной эгоистичной стратегии добычи в соответствии с ожидаемой относительной целью дохода по вычислению оптимальной стратегии в MDP подЦель среднего платьяДля соответствующим образом спроектированной функции вознаграждения. В то время как мы откладываем подробности о MDP и целях среднего платежника в разделе 2, мы отмечаем, что решение MDP-состояния Meanpayoff конечных состояний является классической и хорошо изученной проблемой в сообществе формальных методов, для которой существуют эффективные (полиномиальные) алгоритмы [15, 26], и существуют хорошо развитые инструменты, которые реализуют их вместе с дальнейшими оптимизациями [18, 20]. Эти алгоритмыПолностью автоматизированныйи предоставитьФормальные гарантииО правильной результатах их результатов и формального анализа нашей эгоистичной атаки добычи естественным образом наследуют эти желательные особенности.
ВкладПолем Наш вклад может быть обобщен следующим образом:
(1) Мы изучаем эгоистичную добычу в непредсказуемых протоколах блокчейнов эффективных доказательств, где цель противника - максимизировать ожидаемый относительный доход и, таким образом, минимизировать качество цепи.
(2) Мы предлагаемроман эгоистичной майнинговой атакиЭто оптимизирует ожидаемый относительный доход в непредсказуемых протоколах блокчейна на основе эффективных систем доказательств. Мыформальномодельатака как MDP.
(3) Мы представляемФормальная процедура анализаДля нашей эгоистичной добычи атаки. Учитывая точный параметр 𝜖> 0, наша формальная процедура анализа вычисляет 𝜖-тугойнижняя граница оптимального ожидаемого относительного дохода в MDP вместе сэгоистичныйдобычастратегия, которая достигает этого. Процедура естьПолностью автоматизированныйи обеспечиваетФормальные гарантиина его правильности.
(4) Наш формальный анализгибкийк изменениям значений параметров модели системы. Например, это позволяет нам настраивать параметры модели системной модели и изучать их влияние на оптимальный ожидаемый относительный доход, которого эгоистичная добыча может достичь вПолностью автоматизированная модаи без необходимости разработки новых анализов для различных значений параметров. Это резко контрастирует с формальным анализом, чья правильность доказана вручную, см. Раздел 3.4 для более подробного обсуждения.
(5) Мы реализуем модель MDP и процедуру формального анализа иэкспериментально оценитьКачество ожидаемого относительного дохода, достигнутого расчетной эгоистичной стратегией добычи. Мы сравниваем нашу эгоистичную атаку добычи с двумя базовыми показателями: (1) честная стратегия добычи и (2) прямое расширение стратегии эгоистичной добычи POW [11] к настройке блокчейнов на основе эффективных систем доказательств. Наши эксперименты показывают, что наша стратегия эгоистичной добычи достигает более высокого ожидаемого относительного дохода по сравнению с двумя базовыми показателями.
АЗамечание по моделиПолем В то время как эгоистичные шахтерские атаки, проанализированные в этой статье, применяются к Postake, Pospace и Post Base Byster Chack Blockchains, они захватывают пост лучше, чем Postake и Pospace, как мы вскоре рассказам. Из -за использования VDFS POST «сильно непредсказуем» в том смысле, что майнер не может предсказать, когда он сможет расширить любой блок, в то время как почтовое и поставное место «слабо непредсказуемы» в том смысле, что шахтер может предсказать, когда они найдут блоки на своих собственных (но не других) блоках. Более того, в посте злой шахтер должен запустить VDF поверх каждого блока, который они пытаются расширить, в то время как в Postake или Pospace это поставляется в основном бесплатно. Класс эгоистичных майнинговых атак, проанализированных в этой статье, не использует «слабую непредсказуемость» (необходимое предположение для поста, но не почтовое или позиционное), и, чтобы иметь возможность дать автоматические границы, мы также предполагаем границу на количестве блоков, которые нужно расширить, что является реалистичным предположением для Post (каждый блок требует VDF), но меньше для Pospace или Postake.
1.1 Связанная работа
Оптимальные стратегии эгоистичной добычиПолем Были некоторые работы, которые выходят за рамки предложения и анализа конкретных эгоистичных стратегий майнинга, чтобы фактически претендоватьоптимальностьиз этих стратегий. Работа [27] смоделировала протокол биткойнов в качестве MDP и предложила метод, используя бинарный поиск для решения его приблизительно, чтобы найти оптимальную эгоистичную стратегию добычи. [31] улучшили метод поиска в [27], что приводит к методу, который находит оптимальную стратегию, но с порядок меньше вычислений. [19] и [28] используют глубокое подкрепление, чтобы автоматизировать обнаружение стратегий атаки в биткойнах и накамото-постаке соответственно, но без гарантий на оптимальность. Наконец, [13] предложили моделировать стратегии добычи полезных ископаемых в почтовом порядке в качестве MDP и использование решателя MDP для поиска оптимальных эгоистичных стратегий майнинга. Тем не менее, из -за бесконечного размера их MDP, обнаружение даже приблизительно оптимального раствора недостаточно.
Эта статья есть
[1] We will slightly abuse terminology in our work and continue to use the terms “mining” and “miners” from PoW-based chains also when discussing chains based on efficient proof systems even though when using PoStake this is sometimes referred to as “proposing” and “proposers” (but it is not coherent, some works like [13, 14] use mining) while in PoSpace it was suggested to use the term “farming” and “farmers”.
Оригинал