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

4
ПОДЕЛИТЬСЯ

Недавно я понял, что застрял в кроличьей норе за учебной работой с блокчейнами. Меня заинтересовала эта тема, ведь я всегда был обеспокоен гарантиями безопасности и производительности блокчейн-протоколов.

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

Так как блокчейны сочетают в себе вероятность, теорию игр, криптографию и распределённые системы, естественно, что вероятностник задает вопросы о фазовых переходах, устойчивом равновесии Нэша и случайном блуждании на графах майнеров. Например, кто-то может спросить: «Подчиняется ли закон длины цепочки Биткойна процессу Голтона-Уотсона? Насколько она далека от критического уровня?» Ответы на подобные вопросы, скорее всего, раскроют некоторые секреты о безопасности, скорости обработки транзакций и качестве сервиса блокчейнов и помогут нам создать более сложные распределённые структуры блоков данных.

В этой серии публикации я сфокусируюсь на следующих вопросах:

  1. Каковы отношения между анализом безопасности блокчейна и традиционным анализом распределённых систем?
  2. Как параметры безопасности блокчейнов контролируют скорость обработки транзакций, качество сервиса и другие практические показатели распределённых алгоритмов?
  3. Как определяется централизация, учитывая все различные векторы атаки на блокчейн?
  4. Можем ли мы связать сходство атак grinding в системах с доказательством доли владения с традиционным вероятностным объектом (например, время перемешивания в цепи Маркова)?

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

Предупреждение: мы сильно далеки от уровня таких работ, как Probability on Trees and Networks Расселла Лайонса и Юваля Переса. Я просто хочу поделиться с вами своими размышлениями о некоторых вопросах.?

Дерево Гальтона-Ватсона практически у критического случая: цвет представляет расстояние от корня (автор изображения: Игорь Корчемски)

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

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

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

Самая очевидная уязвимость Биткойна связана со знаменитой атакой 51%. Допустим, существует майнер, который контролирует более 50% всех майнинговых сил, а значит, получает награду за подтверждение более 50% блоков (например, пакеты проверяемых транзакций), принимаемых сетью. Если у какой-либо организации оказалась бы подобная власть, то она могла бы создать транзакцию перевода биткойнов с любого адреса на свой с большим шансом её подтверждения, ведь эта организация контролирует большую часть механизма подтверждения.

В протоколе Биткойна существует система, в которой майнеры соревнуются за подтверждение транзакций. Если майнер первым успешно подтверждает транзакцию, он сообщает об этом всем участникам в сети. Процент майнинговых сил у одного объекта соотносится с вероятностью того, что он подтвердит транзакцию: чем больше у вас майнинговых сил, тем больше транзакций вы подтверждаете. Кроме того, если у вас есть больше 50% майнинговых сил, то вы также можете мешать другим людям подтверждать транзакции.

В банковской сфере это бы выглядело, как будто у Citi больше 50% депозитов потребителей США, а значит, банк может сказать: «Эй, нам нужен миллиард долларов, давайте подтвердим транзакцию от Morgan Stanley в пользу Citi , ведь они скорее всего не смогут нас остановить!». Когда Morgan Stanley попытается заблокировать эту транзакцию, Citi сделает так, что все его майнинговые силы примут её. В современной финансовой системе это не может произойти, потому что центральные банки управляют крупными межбанковскими переводами и являются доверенным сторонним посредником, который не допустит подобные транзакции. Тем не менее, если у кого-то есть большая часть майнинговых сил Биткойна — этот объект статистически равносилен центральному банку, который до известной степени имеет право на последнее слово в подтверждении транзакции.

В абстрактном примере, где Биткойн — это доминирующий платежный метод, все майнеры рациональны и крайне эгоистичны, существует майнер с 51% сил — такая атака просто неизбежна. Тем не менее, в сети Биткойна в прошлом были ситуации, когда майнинговые пулы набирали более 50% майнинговой мощности сети, а атака с двойной тратой так и не была совершена. Это значит, что безопасность блокчейна более сложная, и только благодаря сосредоточению майнинговых сил у одного объекта её не взломать.

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

Обратите внимание, что майнеры, в отличие от обычного голосования, не обязаны идентифицировать себя. Для того чтобы сеть узнала нового майнера, ему нужно только принять участие в одной транзакции или замайнить блок. Более того, количество майнеров может сильно меняться и точное количество участников выборов не раскрывается. С этой точки зрения блокчейны относятся к базам данных только с возможностью присоединения, которые обеспечивают безопасность благодаря многократным случайным выборам без идентификации.

Таким образом, атака 51% может быть совершена при наличии более 50% голосов в большинстве выборов. В таком случае вы можете совершить двойную трату, создав транзакцию с кем-нибудь ещё, исключая прошедшую в прошлом транзакцию из блока или добавляя транзакцию, которая отменяет изначальную транзакцию. Я всегда думаю о том, что аналогия с голосованием также позволяет понять, что всем майнерам и участникам сети не нужно иметь одну и ту же копию цепочки и/или соглашаться с каждой транзакцией. Это большой шаг от традиционных распределённых баз данных, где предпринимаются попытки найти решение таких проблем, как задача византийских генералов Лесли Лэмпорта, где идут попытки найти грань между однозначным консенсусом и невозможностью достичь консенсуса.

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

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

Использование новой системы стимулов в Биткойне привело к взрыву в академическом анализе проблем теории игр, связанных с голосованием. Однако, другие вопросы безопасности у традиционных распределённых баз данных все ещё создают проблемы. Одной из крупнейших проблем поддержания одинакового состояния распределённых баз данных являются задержка сети и асинхронность — узлам нужно время для получения транзакций, которые могут поступать в разном порядке. В мире баз данных мы обычно пытаемся создать системы, которые не зависят от порядка поступления транзакций. Тем не менее, в мире блокчейна именно правильный порядок блоков является основным фактором безопасности и стабильности. Большинство блокчейнов и одноранговых протоколов обеспечивают сообщение через протоколы gossip — вы сообщаете вашим соседям о новом блоке, те говорят своим соседям, и так далее.

Что же произойдет, если два человека создадут один и тот же блок транзакций в одно и то же время? В Биткойне будет образован форк и одна цепочка образует дерево с двумя последними блоками. Так как блоки проходят через сеть, майнеры выбирают блок, который получают первый. В теории, блокчейн мог бы постоянно образовывать форки и выглядеть как случайное дерево Гальтона-Ватсона на картинке выше. Тем не менее, это было бы ужасно — блокчейны, которые выглядят как деревья, в конце концов стали бы тратить больше вычислительных сил на постоянное повторное подтверждение транзакций в ветках, которые завершаются.

Анализ Сатоши Накамото показывает, что вероятность того, что обе ветви будут иметь одну высоту, уменьшается по экспоненте с количеством блоков, намайненных сетью [1]. Для того чтобы преодолеть форк, необходимо подождать, пока одна из ветвей значительно вырастет и станет самой длинной цепочкой для всех майнеров. Этот временной штраф связан с тем, сколько уверенности нужно пользователю, чтобы поверить, что его транзакция была принята сетью. Например, в оригинальном уайтпейпере Биткойна Сатоши предполагает, что для того чтобы убедиться, что транзакция принята сетью, нужно подождать, пока после блока с транзакцией будет создано ещё шесть блоков. В среднем, один блок Биткойна появляется каждые 10 минут, нам бы пришлось ждать целый час, чтобы убедиться, что транзакция подтверждена! Такой компромисс на уровне безопасности (в этом случае для её обеспечения выбран параметр из шести блоков) и времени предполагает, что задержка сети может повлиять не только на безопасность. Вот ещё несколько примеров проблем:

  1. Качество сервиса. Даже если время ожидания, пока транзакция не будет принята сетью большей частью сети, мало, изменения скорости обработки транзакций могут быть критичны. В IPFS, которую также называют «Dropbox на блокчейне», блок соотносится с набором файлов. Если существует большой разброс пропускной способности между блоками, то процесс загрузки папки с большим количеством файлов может затянуться [2]. Такая ситуация может стать неприемлемой для пользователей, которые привыкли к таким централизованным системам, как Dropbox, которым присущи небольшие отклонения в скоростях и малое время ожидания.
  2. Стоимость транзакций. Распределённые биржи стремятся устранить централизованных маркет-мейкеров, используя майнинговую награду для мотивации майнеров (которые играют роль маркет-мейкеров), чтобы сохранять единство книг заявок. Например, майнеры получают награды за обеспечение ликвидности, чтобы выровнять книгу заявок [3]. Тем не менее, маркет-мейкерам может быть очень выгодно оставлять книгу заявок несинхронизованной (например, как в этой статье), поэтому нужно разработать систему стимулов, благодаря которой маркет-мейкеры не захотят одновременно собирать награду за майнинг и создавать большую разницу между курсами из-за асинхронности.
  3. Эффекты «богатые все богаче». Многие блокчейны используют алгоритмы gossip с распределёнными хеш-таблицами, например, Kademlia. В этих алгоритмах узлы следят за своими «ближайшими соседями» на основании того, кто отправляет им наибольшее количество блоков при запросе. Майнер с высокой долей и/или мощностью может воспользоваться такими алгоритмами, чтобы всегда оказываться «ближайшим» соседом к большинству остальных майнеров. Таким образом он может убедиться, что его блоки попадают в сеть раньше блоков других майнеров, и постепенно получить устойчивое преимущество перед майнерами с теми же мощностями. Мы рассмотрим эту проблему в одной из следующих статей об атаках на маршрутизацию.

Задержка сигнала в сети и асинхронность — это расходы на связь в настоящей децентрализованной системе. Приведём более наглядный пример и посмотрим на то, как сильно может отличаться время поиска одного файла в Dropbox и IPFS. Допустим, что мы находимся в идеальном мире, где Dropbox — это один сервер и существует один маршрут от вашего компьютера до Dropbox. В этом случае разница время поиска зависит только от свойств этого одного пути. Однако, в IPFS есть узлы N и K, на которых хранятся копии вашего файла. В этой ситуации у нас есть два дополнительных источника колебаний:

  1. Выбор пути/маршрутизация. Так как протоколы gossip пытаются создать экспандеры, то скорее всего уникального пути нет (особенно если K~ N/2) [4].
  2. Время работы узла. Если узел выключается, а мы пытаемся загрузить с него файл, то нам придётся повторять свой запрос, что увеличивает время поиска.

Более того, обратите внимание, что эти дополнительные источники масштабируются с N и K, а колебания с одним путем не зависят от N или K. Из этого идеализированного примера мы видим, что у блокчейн-систем снижено качество сервиса, а значит, любая защищённая и производительная система должна иметь некую централизацию. Можем ли мы связать это наблюдение с теорией традиционных баз данных и найти способ анализировать этот компромисс?

Интересно, что Шостак, Пис и Лэмпорт рассматривают компромисс между централизацией и качеством сервиса в своей оригинальной статье «Задача византийских генералов». В последнем разделе они анализируют d-регулярный граф связей [5]. На высоком уровне это свойство связано с тем, что у узлов v и w нет пар, а все пути от v к k проходят либо через w, либо через любого соседа w. Они показывают, что можно оставаться устойчивым к византийским врагам, но придётся заплатить штраф, пропорциональный диаметру графу связи. Значит, если кто-то сможет создать случайную версию этого свойства [6], то мы сможем использовать её для анализа безопасности блокчейна.

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

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

Спасибо Утхсаву Читра, Джайанту Гарлапати и И Суну за комментарии и предложения.

[0] Например, если мы знаем, что в детерминированной византийской схеме существует m нечестных майнеров, то алгоритм Лэмпорта предлагает алгоритм Ω(m) для честного голосования, допуская, что мы можем определить личность всех голосующих.

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

[2] Обратите внимание, что этим свойством обладают не только блокчейны — такие распределённые файловые системы, как NFS и Amazon S3 также имеют проблемы с большим количеством файлов. Тем не менее, эти системы контролируют топологии сети и могут решать большую часть проблем случайной маршрутизации сетей блокчейн.

[3] Интересно, что рынок ценных бумаг США в какой-то мере использует это через Регулирование системы национального рынка.

[4] Не доказано, что графы, которые создаются такими алгоритмами, как Kademlia, являются экспандерами. Они часто имеют свойства, которые определяют постоянный диаметр графа Ω(log N).

[5] Это отличается от стандартного определения регулярности в теории графов, где граф является d-регулярным, если каждая вершина имеет d ребер!

[6] Первая попытка случайной версии. Допустим, у нас есть два узла v и k, а ε > 0. Для каждого узла w∊ ∂v, и любая пара путей ?, ? с длиной максимум εN, которая начинается с w и заканчивается на k, Pr[|? ∩?|>2] = O(f(N, ε)) для быстро убывающей функции f.

[7] См. Бен-Ор, Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols и Микали, Byzantine Agreement, Made Trivial

Источник

4 КОММЕНТАРИИ

  1. Кто-нибудь может пояснить этот абзац: «Самая очевидная уязвимость Биткойна связана со знаменитой атакой 51%. Допустим, существует майнер, который контролирует более 50% всех майнинговых сил, а значит, получает награду за подтверждение более 50% блоков (например, пакеты проверяемых транзакций), принимаемых сетью. Если у какой-либо организации оказалась бы подобная власть, то она могла бы создать транзакцию перевода биткойнов с любого адреса на свой с большим шансом её подтверждения, ведь эта организация контролирует большую часть механизма подтверждения.»
    ???

  2. Самый защищённый блокчейн на данный момент BitShares с децентрализованной биржей. Биткоин взламывали, эфириум — взламывали несколько раз, а BitShares ещё никому не удалось за 6 лет работы

    • У тебя в голове все перепуталось)
      Что значит взламывали?) Находились баги — да. В любой системы они будут.
      Взламывали не эфириум, а конкретный смарт-контракт theDAO.
      BitShares хорош, но скорее всего не сможет конкурировать с другими платформами без его основателя Дена Камера

      • Возможно он имел в виду что взламывали биржи, где торгуется Биткоин и Эфир, а биржу Битшерс не взломаешь.

ОСТАВЬТЕ ОТВЕТ

Please enter your comment!
Please enter your name here