О защищённости блокчейнов — часть 2

В первой статье этой серии мы рассматривали определение консенсуса Накамото и механизм голосования, в рамках которого доказательства работы или доли владения позволяют «выбрать лидера» для добавления блока в общую цепочку. Далее мы перешли к алгоритмам византийских генералов и способам, благодаря которым анализ безопасности таких алгоритмов можно применить к блокчейнам, использующим соглашение Накамото. Сегодня мы совершим формальный анализ блокчейнов и протоколов византийского соглашения, а также идеализированное моделирование блокчейн-системы.

Моделирование блокчейнов представляет собой среду, которая отражает состояние всех необходимых участников, противников и хеш-функций. Такую среду можно назвать классом, который содержит все состояния, необходимые для моделирования блокчейна, начиная с самых основ, а также функции, которые изменяют эти состояния для ускорения роста блокчейна. Такое моделирование подразумевает создание среды, а затем многократный вызов функции «увеличения временного шага», которая создает блок и/или распространяет его по сети майнеров. Это идеализированное моделирование похоже на моделирование дискретных событий, например, на марковские цепи и воспроизводящие вероятностные графические модели, что позволяет использовать математические инструменты анализа конвергентности этих моделей в идеализированных блокчейнах.

Из работы о протоколе Avalanche от Team Rocket (при участии Эмина Гюна Сайрера и соавторов) стало ясно, что все методы, использующиеся для формального анализа блокчейнов, одинаковы. Если вы внимательно изучите работы об основном протоколе Биткойна, Algorand или dfinity_network, то обнаружите, что в итоге все авторы создают нечто вроде среды. Конечно, академическая литература может вызывать споры. Авторы каждой работы утверждают, что их метод анализа идеализированных блокчейнов лучше всех остальных, однако не стоит забывать, что анализ безопасности блокчейнов зависит от конкретной модели. Вместо того чтобы фокусироваться на сходстве этих способов, мы можем создать новый протокол, способный взять лучшее ото всех вышеупомянутых протоколов. Предлагаю читателям задуматься над следующим вопросом: возможно ли совместить среды (как в случае с бустингом в машинном обучении) и их моделирования для создания «лучшего» комплекта возможных аксиом? Этот вопрос возник в связи с использованием Team Rocket метастабильности для изменения вида консенсусного механизма в зависимости от состояния среды, что я считаю первым шагом к «бустингу» безопасности и производительности блокчейнов.

Для того чтобы совершить прорыв в понимании сред, прежде всего необходимо понять, какие существуют требования к безопасности и как создавать противников в византийских протоколах. Далее последует обобщенное рассуждение с целью объединить гарантии безопасности и противников всех вышеупомянутых протоколов. Устраивайтесь поудобнее!

Большая часть академической литературы о безопасности блокчейнов фокусируется на доказательстве свойств или аксиом, которыми должен обладать безопасный протокол. В литературе о консенсусе Накамото упоминаются два необходимых (но, возможно, не обязательных) свойства для обеспечения безопасности блокчейнов:

1. Постоянство. Как только транзакция принимается в блокчейн большим количеством майнеров, вероятность её перемещения в возможный форк уменьшается по экспоненте.
2. Жизнеспособность. Любая транзакция, созданная надёжным узлом будет однажды принята всеми надёжными майнерами.

Team Rocket смогли создать гибрид алгоритмов византийского соглашения (таких как Algorand) и алгоритмов консенсуса Накамото, заменив аксиому постоянства, которая нужна для обеспечения безопасности остальных протоколов. Преимущества такого алгоритма, как Avalanche, следующие:

• Такие алгоритмы намного проще внедрять. Проще приводить аргументы в их пользу, чем в пользу византийского соглашения или гибрида византийского соглашения и консенсуса Накамото;
• Такой алгоритм на порядок лучше Algorand с точки зрения времени ожидания транзакции (времени, которое требуется сети для подтверждения транзакции) и пропускной способности — количества транзакций в секунду;
• С вероятностной точки зрения в нём есть простой в описании фазовый переход в параметрах протокола. Этот переход относится к точкам, в которых вероятности, распадающиеся по экспоненте (как и те, что обладают постоянством и жизнеспособностью), начинают неэкспонентальный распад.

Avalanche добивается этого путём замещения свойства постоянства более слабой аксиомой под названием безопасность, которая утверждает:

Аксиома 1. Безопасность. Два правильных узла никогда не примут конфликтные транзакции.

Появление фазового перехода, качественно отличающегося от протокола Snow White или Биткойна, предполагает, что выбор аксиом может привести к совсем другому и, возможно, неуниверсальному поведению [0]. Кроме того, очевидно, что постоянство — более сильная аксиома, но непонятно, почему одну аксиому стоит предпочесть другой. У меня нет ответа на этот вопрос, и я подозреваю, что большинство академиков и практиков в этой сфере задаются тем же вопросом. Это связано с тем, что аксиомы, согласно которым необходима распределённая система, зачастую не связаны с результатами, действительно гарантирующими безопасность. Безопасность распределённых и финансовых систем гарантируется благодаря многим факторам. Приведу несколько примеров идеальных целей:

1. Честное поведение большинства участников приводит к равновесию Нэша, близкому к 𝝴.
2. Исследователи теории аукционов зачастую стремятся доказать, что аукцион зависит от стимула доминантной стратегии (DSIC — dominant strategy-incentive compliant). Это означает, что вы не можете увеличить свою полезность, ведя себя нечестным и/или неожиданным образом [1].

На практике в распределённой системе эти свойства очень сложно доказать [2], приходится действовать по следующей схеме обеспечения доказуемой безопасности:

1. Определить алгоритмы протокола.
2. Создать модель противника, который стремится нарушить протокол.
3. Создать моделирование, которое включает игру между честными участниками и противниками.
4. Показать, что желаемые аксиомы (например, постоянство, жизнеспособность, безопасность, соглашение и т. д.) сохраняются с высокой вероятностью в большинстве примеров моделирования.
5. Доказать, что выбранные аксиомы приводят к приблизительному равновесию Нэша и/или не являются равновесием Нэша (и это нормально!) [3].

В последнем пункте мы говорим уже не о формальной безопасности протокола (например, о доказательствах того, что протокол соответствует определённым аксиомам), а о более качественном соглашении, которое утверждает, что эти аксиомы «достаточно хороши». [4] В оставшейся части статьи я проигнорирую пятый пункт и сфокусируюсь на разъяснении пунктов со 2-го по 4-й. Мы вернёмся к пятому пункту в следующих публикациях, а сейчас попытаемся найти ответ на следующие вопросы:

1. Как создаются противники? Какими свойствами они должны обладать?
2. Как создать игру в этой обстановке?
3. Как «смоделировать» пример протокола? Например, как бы выглядел Биткойн, если бы первичный блок был другим? Нужно ли усреднять все первичные блоки?

В первой публикации этой серии мы нашли сходство между византийским соглашением и консенсусом Накамото. Тем не менее, для того чтобы понять процесс создания противников, нам нужно разобраться с их отличиями. Главные отличия заключаются в следующем:

• Византийское соглашение может позволить нечестное поведение только 1/3 всех узлов, в то время как соглашение Накамото может выдержать нечестное поведение до половины всех узлов.
• Так как византийское соглашение подразумевает явный выбор лидера с фиксированным количеством участников, становится понятно, как создавать модели противников. В частности, мы можем предположить, что некоторый процент голосующих контролируется или искажается одним противником. [5]
• В соглашении Накамото с цензуростойкими условиями и неизвестным количеством участников сложнее определить противника, ведь тогда придётся понять, как адаптироваться к нему с течением времени.

Перед тем как мы начнём обсуждать решение этой проблемы с помощью анализа Биткойна и других распределённых реестров, предлагаю немного углубиться в понятие противника, ведь это фундаментальный фактор для понимания моделей блокчейнов.

В теоретической информатике и криптографии противники моделируются как объекты, которые должны выполнять хотя бы следующие функции:

• Копировать известные механизмы для взлома безопасности/в своих целях.
• Влиять на действия, которые могут предпринимать честные участники сети.
• Иметь независимые генераторы случайных чисел.

Защищаемый объект (тот, на которого нападает противник) — это соперник. Например, рассмотрим противника, который хочет заполучить собственность в стандартной криптографии с публичным ключом. Открытый текст в системе шифрования — это допустимое нешифрованное входное значение, а шифртекст — это зашифрованное выходное значение. Неформально, система с публичным ключом размером λ считается устойчивой к простой атаке на основе подобранного шифртекста (CCA — chosen-ciphertext attack) [6], если невозможно выбрать «небольшую» группу открытых текстов, запросить связанные группы шифртекстов и использовать их для «инвертирования» случайного шифртекста со «значительной степенью вероятности» [7]. Это значит, что если я перехвачу ряд зашифрованных текстов и связанный с ними публичный ключ, то не получу никакой нетривиальной информации о секретном ключе или изначальном тексте из статистических свойств части этих зашифрованных текстов. Строго говоря, цель противник заключается в том, чтобы взять два открытых текста, P⁰ и P¹, и шифртекст C, для которого C = Encrypt(P⁰) или C = Encrypt(P¹), а затем угадать со степенью вероятности значительно больше 50%, является ли C зашифрованной версией P⁰ или P¹.

Затем нам нужно создать игру с участием противника и его соперника. В описании CCA-атаки выше был упомянут «запрос связанного набора шифртекстов». Мы сформулируем это определение более точно с помощью простой трёхшаговой игры (на основе работы Крега Джентри о гомоморфном шифровании):

• Шаг запроса. Противник создает список открытых текстов фиксированного размера n =O(Poly(λ)) и запрашивает у соперника шифртекст для каждого из этих открытых текстов;
• Шаг вызова. Противник отправляет сопернику два открытых текста, P⁰ и P¹. Соперник случайным образом выбирает P⁰ или P¹, зашифровывает его в виде шифртекста C и отправляет обратно противнику;
• Шаг угадывания. Противник пытается угадать, какой из текстов, P⁰ or P¹, зашифровал соперник, и сообщает ему свой выбор. Противник выигрывает, если правильно угадывает открытый текст.

Противник может использовать информацию, собранную в шаге запроса для создания двух открытых текстов в шаге вызова, и получить преимущество на последнем шаге. Идея заключается в том, что если противник выигрывает более чем в 50% случаев, то может использовать алгебраическое число примеров для получения нетривиальной информации об экспоненциально большом пространстве (число шифртекстов в показательной зависимости с λ). Проблема с противниками и играми интересна тем, что мы четко видим компромиссы и то, где находятся случайные элементы системы. Например, в случае с устойчивой к CCA-атакам игре элемент случайности присутствует в шаге вызова, а также неявным образом противник использует механизм случайности для выбора двух открытых текстов. Тем не менее, пример с устойчивой к CCA-атакам игрой намного проще, чем византийская система или цензуростойкая модель Накамото, ведь у нас есть чётко определённые противники и соперники, их личность установлена и не изменяется. Как же использовать схему с противниками в этом случае?

В блокчейн-системах число участников и противников меняется. Как утверждает знаменитая задача византийских генералов, зачастую честный участник сети не может узнать, является ли другой участник противником и действует ли он во вред системе (например, увеличивает время задержки крупномасштабной сети или создает проблемы с аппаратным обеспечением). Мы создаём одного обобщённого противника, один вызов для среды, которая управляет состоянием всех пользователей, включая противников. В коде этой среды прописано то, как мы можем смоделировать нашу распределённую систему, а также случайная переменная, которая отвечает за все возможные реализация распределённой системы. Если быть немного конкретнее — среда представляет собой некую систему, которая имеет доступ к следующему:

• К состоянию всех участников (локальной копии блокчейна, времени задержки сети);
• Доступ к вероятностному оракулу, который представляет универсальную хеш-функцию для создания блокчейна;
• Содержит все случайные элементы, необходимые для системы (например, все монеты, которые определяют долю/доказательство работы каждого участника, любая случайность, которая нужна системе). Сюда также входит любая статическая и общая случайность, необходимая всем участникам, например, выбор первичного блока;
• Содержит состояние, необходимое противнику. В этом случае противник использует функцию, которая может контролировать любого участника и изменять его состояние — изменять его блокчейн, отправлять транзакции с двойным расходованием и так далее. Однако противник может влиять только на определённый процент (𝛾) участников сети. Среда позволяет противнику «брать под контроль» некоторую часть сети до того, как та начинает развиваться.

Учитывая всё вышесказанное, среда исполняет определённый цикл:

• Позволяет противнику изменять состояние и/или действия до 𝛾n участников. Участники, на состояние и/или деятельность которых влияет противник, называются нечестными участниками;
• Выбирает подгруппу участников (честных или нечестных) потенциально недетерменированным способом и заставляет их совершать допустимое действие — создавать блок, транзакцию, выполнять некоторое количество запросов универсальной хеш-функции и/или публиковать/отправлять блок;
• Обновлять состояние всех участников под влиянием этого действия. Например, если на предыдущем шаге был смайнен новый блок, то среда отправит его остальной части сети, чтобы участники добавили его в свои копии блокчейна [8].

Сомневаться, что такой цикл может представлять сложные зависимости, скрытые в блокчейн-протоколе, — естественно. Могу возникнуть следующие вопросы:

1. Что будет, если одновременно будут созданы два блока, которые спровоцируют появление форка?
2. Что если наш протокол создаст направленный ациклический граф (как, например, Avalanche), а относительное распределение двух блоков неверно с топологической точки зрения?

Тем не менее, такой цикл представляет собой дискретно-событийное моделирование, создающее эволюцию среды, по мере того как появляются новые блоки и новые участники. Этот цикл более-менее похож на цикл выборки из направленной графической модели с использованием методов Монте-Карло с цепями Маркова (MCMC) [9]. В случае с графической моделью, происходит следующее:

1. Создаём изначальное состояние.
2. Делаем выборку из распределения в текущем состоянии, а затем решаем, переходить в следующее состояние или повторить этот шаг.
3. Проходим через графическую модель до тех пор, пока не произойдёт сбой и/или пока мы не посчитаем, что уже достаточно близки к стационарному распределению модели.

Графическая модель может содержать очень сложные зависимости между, казалось бы, несвязанными состояниями, но мы всё же можем делать из неё выборку с помощью локального алгоритма в единичном цикле (MCMC). Эти зависимости встроены в наш механизм и позволяют противнику изменять состояние, обеспечивают методологию для выборки участников, а также работу механизма распространения блоков. Возможно, понадобится много итераций цикла, прежде чем произойдёт изменение, придётся ждать, пока зависимость будет удовлетворена. Единственная разница между графическими моделями и блокчейн-средами и моделированием заключается в том, что зависимости непосредственно вписаны в код распределения, из которого мы делаем выборку в протоколе. Таким образом, доказательство схожести результатов с результатами предыдущей секции похоже на доказательство свойств направленных графических моделей, хотя здесь и есть сложность в изучении внутренних зависимостей. Как только мы выписываем цикл для определённого протокола, то можем с лёгкостью анализировать алгоритм как рандомизированный [10]. Вместо того чтобы углубляться в анализ циклов и механизмов цикла определённого протокола, предлагаю рассмотреть несколько примеров таких циклов. В следующих статьях этой серии мы проанализируем циклы для разных протоколов со средами и моделированием.

В первом примере мы определим среду задачи византийских генералов:

• Изначальные условия: изначальное состояние ДА/НЕТ всех генералов, выбор первого лидера;
• Состояние: сетевой граф генералов, все отправленные сообщения;
• Оракул: нет;
• Противник: детерминированный список нечестных генералов;
• Цикл: отправка сообщений голосования всем соседним участникам сетевого графа до достижения консенсуса.

Пример с византийскими генералами — это относительно простая среда, так как в ней используется чистый детерминированный механизм консенсуса. Сложность среды возрастает, по мере того как мы добавляем в неё случайность, свободное поведение и примитивы синхронизации. Сначала взглянем на Avalanche, так как его среда намного проще среды Algorand или протокола Биткойна. Основной алгоритм Snowflake, на котором построен Avalanche, имеет следующий цикл среды:

Snowflake — это очень простой механизм выборки из урны Пойа, где красные и синие шары (например, R и B в цикле выше) распределяются среди определённого количества участников. Цикл делает следующее:

1. Делает выборку одного честного пользователя, чей цвет (например, голосование ДА/НЕТ), будет изменён.
2. Передает информацию о выбранном пользователе и группе честных пользователей противнику, который теперь может обновить цвета византийских пользователей.
3. Получает выборку «голосов» от k пользователей (которые могут быть честными или нечестными) и подсчитывает число цветов.
4. Изменяет цвета/голоса на основе набора параметров протокола.

Анализ этой среды, которую Сайрер называет «глобальным планированием», на удивление прост, так как он приводит к стандартному результату процессов теории очередей. Мы рассмотрим Snowflake и Avalanche более подробно в следующей статье. Основной протокол Биткойна использует более сложный цикл среды:

Это намного более сложная среда, так как здесь мы имеем дело с большим количеством состояний и вычисление доказательства выполненной работы проводится в каждой итерации. На высоком уровне этот цикл делает следующее:

1. Для каждого пользователя мы выбираем самую длинную цепочку, которую получили.
2. Определяем, какой блок использовать для проверки доказательства выполненной работы.
3. Проверяем доказательство выполненной работы.
4. Если блок майнится, то распределяем его по всей оставшейся сети.

В этом цикле противник прячется в функции «доказательства работы», так как цель протокола — показать, что противник, имеющий t% мощностей хеширования (где t < 0.5), не может подделать транзакцию. В этом протоколе функции R, I и V имеют некий контроль на тем, как мы выбираем пользователей, которые могут майнить блоки, и косвенным образом устанавливаем противника. Мы рассмотрим этот процесс подробнее в четвёртой статье из этой серии. Algorand немного более сложен для использования в такой форме, поэтому мы займёмся его использованием в единичном цикле в пятой статье.

Как вы уже поняли, формально создание вероятностного моделирования распределённых систем с противниками может быть сложным, иметь свои тонкости и противоречащие меняющиеся составляющие. Выбор необходимых аксиом непосредственно влияет на среду, а если сделать его правильно, то можно значительно упростить весь анализ. Исследователи зачастую сталкиваются с проблемой курицы и яйца, когда пытаются понять, что нужно делать сначала, выбирать аксиомы или создавать среду. Упомянутые выше среды и модели показывают, что существуют разные мнения о том, из чего состоит «хорошая» модель. Возможно, однажды мы сможем совместить все эти варианты в протоколе, который будет обеспечивать безопасность, гибкость и производительность, используя все преимущества Algorand, Bitcoin Backbone, DFINITY и Avalanche.

Спасибо Эйбу Стенвею и Утхсаву Читре за помощь в написании статьи.

[0] Само название документа об Avalanche — Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies — намекает на отличия этого протокола от Биткойна. В этом протоколе состояние — это бинарный вектор (например, да или нет) определённого блока, а квазистабильное состояние — это состояние, когда нарушение даже одного голоса приведёт к тому, что алгоритм будет направлен в сторону изменённого голоса. В Avalache квазистабильные состояния служат границей между использованием византийского соглашения или консенсуса Накамото. В статистической физике эти точки равновероятности выделяют в особый вид поверхностей (committer surfaces). Они очень важны для нахождения эффективных путей к локальным минимумам. Более подробно об этом можно прочитать в статье Э. Вандена-Айндена здесь.

[1] Самый простой пример — аукцион Викри, где все участники подчиняются квазилинейной/многопеременной логистической функции выгоды u(x) = max(v-x, 0), где v — это личная оценка товара участником аукциона. В этом случае личная оценка обладает свойством DSIC, так как выигрывает вторая ставка цены.

[2] Равновесия Нэша имеют собственный класс сложности под названием PPAD. Более подробно об этом можно прочитать в знаменитой работе Пападимитриу.

[3] Может показаться, что неоднозначные равновесия Нэша оказывают отрицательный эффект на протокол, но в действительности это напоминает нейтральные сети или неотрицательное матричное разложение, когда существование множества минимумов позволяет более простому алгоритму быстрее находить «достаточно хорошее» решение. Более подробно о неоднозначных равновесиях Нэша и Биткойне можно прочитать в этой работе от авторов Ouroboros.

[4] Во многом это похоже на выбор аксиом теории множеств (используем ли мы ZF или ZFC?), поэтому чёткого разрешения проблемы зачастую нет.

[5] Распределённые реестры, которые используют византийское соглашение, например, Algorand, дополняют стандартное византийское соглашение свойством свободы от ограничений, случайным образом выбирая определённое количество голосующих, которые совместно решают достоверность транзакции. В этом случае нужно доказать, что и методология византийского соглашения, и механизм совместного выбора удовлетворяют необходимым требованиям безопасности.

[6] Технически это атака CCA1, в которой противнику нужно запросить все пары до атаки, во время которой используется статистическое преимущество пар. В мире CCA2 противник адаптируется и может попытаться увеличить свои преимущества в зависимости от того, как хорошо работаю те пары, которые он запросил. Этот вопрос хорошо объясняется во второй главе работы Крега Джентри о гомоморфном шифровании.

[7] Понятие «со значительной степенью» вероятности относится к полиномиальному увеличению размера ключа — в этом случае преимуществом должно быть Ω(1/Poly(λ)).

[8] Обратите внимание, что в синхронизированном мире — без задержки сети — среда сообщает о действиях участников остальной части сети моментально (например, все пользователи выполняют некое действие). В асинхронном мире каждая итерация циклов является «витком», в котором не выбираются участники и/или действия. В какие-то моменты времени «ничего не происходит», в то время как пакеты проходят по сети майнеров.

[9] Рассмотрим этот вопрос немного подробнее. Обычно мы пытаемся создать моделирование с дискретным временем, но нам не нужно привязываться к частоте событий. Теоретически в одном витке синхронизированной среды может быть создано множество блоков, которые моментально распространятся по сети. Если предположить, что существует минимальный временной масштаб (например, самая быстрая из возможных частот система), то можно установить соответствующий временной шаг. Можно провести аналогию с выбором временного шага в моделировании молекулярной динамики, где используется самый быстрый режим колебаний в системе (например, период колебаний водорода) для определения временного шага (обычно в фемтосекундах). Тем не менее, всё это можно рассматривать как выборку направленной графической модели, хоть и с продолжительными временными состояниями. Здесь можно вспомнить Гамильтониан Монте-Карло с иерархическим потенциалом.

[10] Не стоит беспокоиться о правильности среды в качестве моделирования на уровне недерменированных машин Тьюринга с доступом к случайным оракулам. В этой работе даётся теоретическое обоснование подобной системы. Ознакомьтесь с введением в протокол Биткойна, чтобы узнать об этом подробнее.

[11] В работе об Algorand алгоритм представлен не в виде одного цикла. У него есть последовательность сопрограмм, которые доказывают свойства. В пятой статье я превращу эти подпрограммы в один цикл и расскажу о том, чем этот цикл похож на другие алгоритмы, рассматриваемые в этой серии.

Источник

Первая часть: О защищенности блокчейнов — часть 1