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

HashFlare

ComputerUniverse Введи промокод FW7FRUX при покупке и получи скидку 5 евро

В первых двух частях этой серии мы изучили взаимодействие вероятностной природы распределённых блочных структур данных (DBDS — distributed block data structures) и способов изменения традиционного анализа систем с задачей византийских генералов (BFT — Byzantine Fault Tolerant) для DBDS. Цель этой серии публикаций — продемонстрировать, что существует небольшое количество базовых элементов безопасности, которые присущи большинству (если не всем) распределённым консенсусным алгоритмам и DBDS.

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

  • Жизнеспособность: реестр продолжает расти и принимать новые транзакции или изменения состояний.
  • Постоянство/безопасность: честные транзакции в итоге попадают в реестр и не могут быть удалены (без колоссальных усилий) после того, как прошло достаточное количество времени.

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

  • [Часть 3] Avalanche как реализация консенсусного протокола Stellar
  • [Часть 4] Сокращение асинхронных моделей Биткойна, Ekiden от Oasis Labs и Zexe до уровня «идеального функционала»

Но какое отношение к безопасности блокчейнов имеет универсальная концепция анализа? Универсальная концепция для оценки безопасности хороша, но она не рассказывает нам о самой безопасности. Я хочу создать обобщённое понятие безопасности (например, выяснить, какие элементы безопасности являются общими для всех протоколов), чтобы создать лучшее понимание минимальных необходимых и достаточных условий для создания безопасного блокчейна. Более того, тот факт, что определённые протоколы могут быть дополнены элементами других протоколов, предполагает, что существует некая общая база для создания более специализированного протокола. Таким образом консенсусный протокол Stellar (Stellar Consensus Protocol — SCP), в отличие от других протоколов, о которых говорилось в предыдущих статьях, предлагает обобщённую концепцию в противопоставление конкретной реализации. Сначала я расскажу об этом протоколе подробнее и покажу примеры, доказывающие, что его обобщённая концепция подходит для разных консенсусных механизмов. Затем я рассмотрю Avalanche, опишу, как можно его реализовать в качестве примера SCP, и приведу численное доказательство. Стоит отметить, что Avalanche обладает более высоким уровнем безопасности, чем указано в его изначальной документации. В конце я рассмотрю идеальный функционал будущего и то, как вероятностные эквивалентности между машинами абстрактных состояний (например, эквивалентность между Avalanche и примером SCP) позволяют проводить комплексный анализ консенсуса и превращать слабые гарантии в сильные.

Консенсусный протокол Stellar был создан Дэвидом Мазьером, профессором Стэнфорда и главным научным сотрудником Stellar Development Foundation (организация поддерживает клиентский код сети Stellar). SCP внедрён в stellar-core, и, по моему мнению, это один из лучших существующих клиентских кодов блокчейна в экосистеме. Ранее Мазьер также создал Kademlia — одноранговую распределённую хеш-таблицу (и алгоритм ячеистых сетей) и ограничения компромиссов между безопасностью и жизнеспособностью систем BFT. Учитывая всё вышесказанное, неудивительно, что эта работа фокусируется на протоколе с гарантиями, похожими на BFT, с блокчейновой сложностью коммуникации. В частности, протокол пытается придерживаться и системы BFT с доступом только для определённых лиц, и инклюзивной блокчейн-системы. Это реализуется благодаря использованию не традиционных групп BFT, где каждый участник сообщается друг с другом, а ограниченных групп «доверенных узлов» для подтверждения. Пример проиллюстрирован ниже:

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

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

В традиционном BFT для того чтобы изменить транзакцию, нужно согласие по крайней мере 2/3 участников. На первом рисунке мы видим сеть из пяти узлов, которые сообщаются друг с другом по линиям. Для того чтобы каждый узел мог решить, добавлять транзакцию в локальную копию реестра или нет, ему нужно получить сообщение о подтверждении ото всех остальных узлов (например, по крайней мере от 2/3 узлов). Это значит, что для достижения консенсуса должен существовать сетевой путь от каждой пары узлов, а значит, стоимость обмена данными равна квадрату от количества узлов [0]. Вместо того, чтобы фокусироваться на явной коммуникационной сети, как в случае с протоколами BFT, SCP фокусируется на том, что Мазьер называет срезом кворума [1]. Срез кворума — это набор подгрупп узлов, которые должны прийти к соглашению, прежде чем занести транзакцию в локальный реестр. Важно, что эта подгруппа не должна быть большой (относительно количества узлов). Более того, один узел обычно участвует в нескольких срезах кворума, что показано в функции выбора кворума:

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

для узла N. Например, в нижней части рисунка мы видим, что для узла 1 существуют две подгруппы, с которыми он может прийти к соглашению: {1,3,5} и {1,2,5}. Согласно алгоритму протокола SCP, узел должен прийти к соглашению только с одним элементом из его среза кворума. Это значит, что узлу 1 нужно достичь соглашения с {1,3,5} или {1,2,5}, чтобы внести изменения в свой реестр. Идея заключается в том, что если размер подгрупп для достижения консенсуса сублинейный, то мы можем достичь косенсуса с субквадратной коммуникационной сложностью. Похоже на бесплатный сыр!

Прежде чем переходить к другим допущениям и ограничениям для выполнения SCP, посмотрим на то, как в этом случае работает традиционный протокол BFT (с подгруппой SCP). Допустим, что у нас есть протокол BFT с группой узлов N, где |N| = nДля каждого элемента определим следующий набор подгрупп:

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

Эти наборы — самые маленькие наборы, с которыми n может прийти к соглашению BFT для добавления транзакции в локальную копию реестра. Затем любая функция выбора кворума Q_{BFT} должна следовать следующему ограничению:

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

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

Те, кто изучают теорию распределённых систем, с сомнением отнесутся к идее, что один узел должен согласиться с сублинейным числом людей для достижения консенсуса. Конечно, это не бесплатный сыр. Вместо того чтобы просчитывать количество узлов, необходимых для достижения консенсуса, SPC создает необходимые и достаточные условия с набором срезов кворума. Эти условия топологичны по своей природе и соотносятся со свойствами связанности срезов кворумов. Мы предоставим наглядный пример таких условий. Во-первых, давайте рассмотрим понятие кворума — набор узлов и срезов кворума, которые обладают свойством так называемого «транзитивного замыкания». В каком-то смысле это означает, что U — это самодостаточный набор. Узлам не нужна входящая информация от других узлов, чтобы достичь консенсуса. Пример проиллюстрирован ниже:

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

В левой части рисунка мы видим три узла и набор срезов кворума, в котором каждый срез содержится в наборе из трех узлов. Справа мы видим набор из пяти узлов {1,2,3}, который не самодостаточен. Нам нужно добавить узлы 4 и 5 для создания кворума. Все консенсусные протоколы указывают (некоторые неявно) минимальный размер кворума для достижения консенсуса [например, 2n/3 для BFT или n/2 у Накамото]. Тем не менее, ключевая особенность SCP заключается в том, что каждый узел выбирает собственное «число для достижения консенсуса». Более того, так как каждый узел может находиться в нескольких срезах кворума, существует избыточность — мы полагаемся не на один набор узлов, а на достижение консенсуса с ним. Таким образом, имеется два параметра: средний размер среза кворума и количество срезов, в которых участвует один узел. В случае с протоколами BFT и Накамото, оба эти параметра имеют фиксированное значение, а SCP предлагает минимальные условия для достижения консенсуса, поэтому разработчики протокола могут настраивать эти два параметра.

Топологические условия SCP напоминают элементарную топологию точечных множеств. В частности, самое важное свойство для достижения консенсуса называется свойством пересечения кворумов (QIP — quorum intersection property), которое утверждает, что любые два кворума имеют непустое пересечение (не напоминает свойство конечных пересечений компактного пространства?). Это строгое условие подразумевает, что узел может найти сообщение с любым другим узлом через кворумы.

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

И, наконец, поговорим о самом протоколе: протокол SCP — это модифицированная версия «single decree synod» алгоритмов Паксоса, которая обеспечивает способ предложения, предварительного принятия и окончательной обработки транзакций с помощью локальных соглашений с кворумом. Главное необходимое допущение для обеспечения жизнеспособности и постоянства модифицированного алгоритма Паксоса заключается в следующем: группа кворумов должна обладать свойством пересечения после удаления группы византийских узлов. Документ содержит подробную информацию о четком изменении состояний, происходящем в системе. Единственное, что нам нужно знать, — Avalanche (описанный ниже) также имеет понятие бивалентного состояния, которое происходит, когда доля сети заставляет одну часть сети верить, что утверждение a верно, а другую, что a не верно. Avalanche и Stellar предлагают явные решения для восстановления консенсуса в сети, даже если сеть оказывается в бивалентном состоянии. Теперь приступим к Avalanche!

Avalanche — это продуманное повторное использование алгоритма нахождения тяжелых элементов (например, генерализация таких алгоритмов оценивания множества, как HyperLogLog) для создания вероятностного консенсусного алгоритма [2]. Основная идея консенсуса намного проще, чем SCP, когда дело заходит о достижении согласия о том, верно утверждение A или нет (в примере — nA):

  1. Создается таблица, описывающая уверенность в A или nA.
  2. Отправляется многократный запрос k пользователям с целью узнать их решение об A или nA.
  3. Уверенность в AnA увеличивается после получения ответа на запрос k.
  4. Когда уверенность в A или nA достигает достаточного уровня, происходит окончательный выбор.

Этот метод достижения консенсуса основывается на «метастабильности». Как только приходит достаточное количество ответов на запросы, система «насильно» принимает решение о правдивости, как и в случае с минимумом функции потенциальной энергии в метастабильной критической точке (например, шар номер 2) [3]:

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

Хотя Avalanche и цитирует документ SCP, в нём не упоминается, что метастабильность — это та же бивалентность Stellar.

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

  • Мы придали случайный характер срезам кворумов (например, нашим запросы k другим участникам).
  • Каждый запрос к k участникам соответствует новым срезам кворумов.
  • Когда поступает достаточно ответов от подгрупп k, охватывается все пространство для создания кворума (с высокой вероятностью).
  • В какой-то момент нам нужна достаточно высокая плотность кворумов для удовлетворения свойства их пересечения с высокой вероятностью.

Приведем список технический сложностей, которые необходимо преодолеть, чтобы сделать вышеупомянутую аналогию более точной:

  1. Нужно доказать, что методика семплирования Avalanche создает кворум с высокой вероятность при наличии определенного количества примеров.
  2. Нужно доказать, что методика семплирования Avalache создает функцию подбора кворумов, которая удовлетворяет свойство их пересечения с высокой вероятностью.
  3. Нужно убедиться, что жизнестойкость и постоянство SCP сохраняются при наличии динамической функции подбора кворумов.

Для первых двух пунктов я предлагаю схему доказательства с техническими деталями, доказывающими, что кворумы создаются и имеют свойство пересечения. Основной источник случайности в консенсусном механизме Avalanche — это момент первого попадания: сколько семплов k нужно сделать, чтобы достичь необходимой уверенности в том, что утверждение A можно принять/отклонить? Мы создадим модель с помощью пуассоновского упрощения, которое часто используется для тестирования распределения [4]. Перед вами порождающая модель создания функции подбора кворумов Avalanche Q_{ava}, где λ — это ожидаемое число необходимых примеров [5]:

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

Пуассоновское упрощение позволяет более легким способом вычислять ожидания кворумов. Например, возьмем элементарное вычисление, для того чтобы показать, что для U⊂[n] можно использовать следующее:О защищённости блокчейнов — часть 3

где последний шаг:О защищённости блокчейнов — часть 3

и (n)_k — это убывающий символ Похгаммера. Как показывает даже это простое вычисление, существует компромисс в вероятности кворумов между размеров кворума и ожидаемым количеством примеров (обозначенных λ). Конкретная зависимость неизвестна, но функциональная форма напоминает критическую перколяцию — кворумы соотносятся с кластерами в группе перколяции [6]. Возникает ощущение, что элементы достаточно плотного среза кворума образуют граф случайных пересечений, для которого имеются следующие суб- и суперкритические результаты перколяции для определенного числа примеров [7]:

О защищённости блокчейнов — часть 3Субкритические О защищённости блокчейнов — часть 3Суперкритические

Нам нужно сделать кое-что ещё — адаптировать пуассоновский процесс и использовать предельную теорему мартингалов, чтобы убедиться, что Y \wedge 2^n не порождает проблем. Результат показывает, что кворумы появляются с высокой вероятностью и существует четкий фазовый переход, если вышеупомянутые условия удовлетворены.

Вторая проблема со свойством пересечения кворумов заключается в следующем: маловероятно, что мы не сможем создать аналитические границы вероятности достаточного свойства пересечения. Тем не менее, как и в ответе на знаменитый вопрос «Как k крысам найти m отравленных бутылок?» из интервью, мы можем использовать теорему Франкла-Фюреди о непрофсоюзных группах для обеспечения явных более низких связей с минимальным количеством кворумов, которые бы имели достаточное свойство пересечения. Как только мы разберёмся с проблемой распределения кворумов, где Y находится в конце Poisson(λ), мы сможем объединить два результата, чтобы получить связи вероятности свойства пересечения кворумов в субкритическом и суперкритическом режимах.

Таким образом, для того чтобы доказать, что Avalanche — это отдельный пример SCP, нам нужно всего лишь показать, что результаты SCP имеют функции случайного выбора кворумов! Рассмотрим один метод, который, как я думаю, сработает, — идеальная функциональность. В моём понимании, идеальная функциональность, во всяком случае в мире блокчейнов, — это функциональность, которая показывает, что существует вероятностная универсальность между разными протоколами. Это чем-то похоже на законы Вигнера и Трейси-Уидома в теории случайных матриц — пока протоколы удовлетворяют некоторым простым условиям (похожим на условия для моментов по вероятности), разница между статистикой этих протоколов приближается (по крайней мере слабо) к нулю. Это позволяет создавать отношения эквивалентности между статистически похожими протоколами, а затем переносить доказательства с более простых протоколов к более сложным. Например, Пасс, Симен и Шелат используют такой метод для переноса доказательств безопасности в Биткойне из синхронных условий в асинхронные. Более подробно расскажу об этом в следующий раз!

Несмотря на то что к SCP относятся не с большим энтузиазмом — этот протокол по большей части упоминается в статьях об Avalanche, где он представляется как конкурент/альтернатива, — я надеюсь, что у меня получилось привести доказательства того, что он является практичным консенсусным алгоритмом. Гибкость SCP позволяет разработчикам протокола сочетать протоколы византийского соглашения и Накамото с помощью топологических ограничений (вместо ограничений процента честных участников). Она также позволяет улучшать безопасность алгоритмов (например, определить более четкие границы в Avalanche, как в случае с фазовым переходом последнего раздела) из абстрактного описания. Мы также увидели, что при формулировке Avalanche как примера SCP мы можем создать более четкие концентрационные границы для возможности достижения консенсуса.

Надеюсь, что подогрел ваш аппетит к пониманию последнего кусочка пазла классификации консенсуса — идеального функционала и его связи с универсальными классами.

Благодарю Утсава Читру, Артура Брейтмана, И Суня, Рея Чиана и Заки Маниана за комментарии и предложения.

[0] В оригинальном документе задачи византийских генералов авторы предлагают более явное необходимое и достаточное условие графа сети:О защищённости блокчейнов — часть 3

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

Обратите внимание на условие об избежании пересечений в определении регулярности — это условие создает ограничения на проводимость графа (через теорию Чигера). В частности, можно доказать, что все разрезы регулярного графа $$G = (V,E)$$ имеют размер $$\Omega(|V|²)$$, что доказывает через теорему о максимальном потоке и минимальном разрезе, что минимальный поток имеет квадратичные затраты.

[1] Интересно, что срезы кворумов являются простыми краями гиперграфов группы узлов. Функция подбора кворумов возвращает определенному узлу группу краев гиперграфов.

[2] По какой-то причине люди в сфере блокчейна немного знают о рандомизированных алгоритмах и рассматривают Avalanche как часть «обширных деталей и доказательств низкого уровня, которые трудно понять людям вне научных кругов». Тем не менее, если посмотреть на заметки о таких алгоритмах нахождения тяжелых элементов, как этот (из курса базового высшего образования от Тима Рафгардена и Грегори Валианта), то можно увидеть те же основные алгоритмы, что рассматриваются в Avalanche более тщательно. Кроме того, были найдены более эффективные границы момента первого попадания, чем в оригинальном документе Sirer/Team Rocket, и эти границы стали ещё популярнее с момента их освещения в прессе!

[3] В своих лекциях об Avalanche Эмин Гюн Сирер всегда говорит, что в протоколе используется «основанный на физике» подход. Это можно видеть и на изображениях выше. Если создать цепь Маркова (например, с помощью алгоритма Метрополиса) для семплирования метастабильного потенциала выше, то получится похожий результат момента первого попадания, как и в лемме 3/теореме 4 документа Avalanche.

[4] Примером может послужить вот этот документ STOC 2011 от Валиантов

[5] Конечно, здесь допускается, что большая часть пользователей Avalanche честные и не пытаются совершить атаку Eclipse, которая бы исказила распределение семплирования. Для синхронизации случайности можно использовать VRF/VDF, но это, скорее всего, разрушит заявленные преимущества сложности коммуникации Avalanche

[6] Для того чтобы привести численные доказательства фазового перехода, предлагаю следующий срез этой функции:

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

Значения теплых оттенков — это $$|U|/n$$, где вероятность максимизирована (например, $$argmax_{|U|} Pr[U\text{ is a quorum}]$$) for $$n = 128$$). Мне не удалось полностью устранить численные артефакты в убывающем расчёте Похгаммера (например, используя коэффициенты функций $$\Gamma$$, $$(n)_k = \frac{\Gamma(n)}{\Gamma(n-k-1)}$$), но я использовал расчёт с более высокой степенью точности scipy для вот этой оценки [если вы рассмотрите этот пример, то увидите тонкости, благодаря которым удаётся получить более высокую степень точности; обратите внимание, что определение для scipy — это восходящий символ Похгаммера, $$\mathsf{poch}(n, k) = \frac{\Gamma(n+k)}{\Gamma(n)}$$]. Обратите внимание, что верхняя часть оси y соотносится с $$\log_{10} \lambda = -2$$

[7] Эти результаты получены из теорем 5 и 6 вот этого документа; они используют стандартную перколяцию краев на графах Эрдёша — Реньи с разветвляющимся процессом Гальтона — Уолтона для создания основных деревьев

Источник

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

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

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