Эта статья посвящена поверхностному обзору ключевых подходов к достижению консенсуса в децентрализованной среде. Материал позволит разобраться с задачами, которые решают рассмотренные протоколы, областью их применения, особенностями проектирования и использования, а также позволит оценить перспективы их развития и имплементации в децентрализованных системах учета.
Отметим, что в децентрализованной сети применяется принцип избыточности, который основан на том, что узлы могут делать одну и ту же работу. Для централизованной сети это, естественно, неэффективно, а для децентрализованной это является обязательным условием. Перейдем к базовым требованиям.
Протоколы должны обеспечивать надежную работу пользователей в достаточно суровых условиях и при этом удовлетворить минимальным требованиям. Ниже перечислены основные.
Отсутствие центральной доверенной стороны. Сеть состоит из равноправных узлов. Если злоумышленник или третья сторона попытаются вывести из строя определенное количество узлов, то сеть продолжит нормально работать до тех пор, пока честные участники будут контролировать подавляющее большинство узлов сети.
Честные участники не знают, какие узлы контролируются злоумышленниками. Предполагается, что другие узлы могут в произвольные моменты времени выходить из строя или функционировать произвольным образом, в том числе координироваться злоумышленниками для проведения атаки на сеть. Опять же, честные участники не знают, какие из узлов честные, а какие сбойные, или ненадежные.
Предполагается, что сеть заведомо ненадежная. Некоторые сообщения могут быть доставлены с серьезной задержкой, а другие могут быть потеряны в сети и остаться вовсе недоставленными. Именно в таких условиях децентрализованный консенсус должен продолжать нормально функционировать: все честные узлы должны приходить к одному и тому же состоянию базы данных подтвержденных транзакций.
Протоколы должны быть полностью формальными. Никакого дополнительного участия человека быть не должно и никаких дополнительных данных не требуется. Все честные узлы должны приходить к одному и тому же решению, полностью следуя алгоритму, который выполняется компьютером.
Кроме того, существуют определенные допущения, при которых протокол гарантирует корректную работу. Честные узлы должны составлять большую часть всех участников: более ½ или ⅔ от общего их количества. Однако время принятия решения не ограничено. Ограничение может касаться количества шагов для принятия решения, но не времени.
В первую очередь это применимо к криптовалютам: в Bitcoin применяется алгоритм Nakamoto, в Ethereum применяется упрощенный вариант GHOST, в Bitshares реализован Delegated PoS и т. д.
Нужно отметить, что сообщество, которое поддерживает определенную цифровую валюту не всегда бывает многочисленным и децентрализованным. Существует ряд других цифровых валют, которые являются централизованными. Однако это не значит, что механизм достижения консенсуса не понадобится. Например, Ripple использует BFT-протокол в централизованной среде.
Протоколы достижения консенсуса используются в высоконадежных вычислительных системах. Они могут использоваться для доступа к распределенным базам данных при построении кластеров, а также обязательно используются в критических технических системах: это могут быть системы управления авиационным оборудованием, системы управления ядерными реакторами, а также в космических технологиях.
В 2018 году, 6 февраля, произошел запуск Falcon Heavy. Было интересно наблюдать за ним и читать технические обзоры. Но не менее интересно было читать о том, какие алгоритмы достижения согласия использует команда. Инженеры вынуждены были использовать простую электронику, которая продается в обычных магазинах и не совсем надежно работает в сложных космических условиях. Поэтому они применяют многократную избыточность в своей работе и достижение консенсуса в данном случае необходимо.
Криптовалюты работают в peer-to-peer сетях. При этом сообщения или транзакции передаются между участниками сети в произвольные моменты времени. Предположим, что в сети есть участники, находящиеся в США, и участники, находящиеся в Австралии. Платежи, которые отправлены из США, участники из Америки увидят раньше, чем платежи, отправленные из Австралии. Это происходит из-за наличия серьезной, по компьютерным меркам, задержки при доставке сообщения с одного континента на другой. Аналогичной будет ситуация и для австралийцев, потому что они будут видеть платежи из Австралии раньше, чем платежи из США.
Описанная выше ситуация значит, что разные участники сети увидят в один момент времени увидят разное итоговое состояние базы данных с транзакциями. Поскольку транзакции приходят от пользователей к валидаторам в разное время, нужен протокол, который позволит каждому узлу вне зависимости от его места нахождения получить все транзакции в одном и том же порядке.
В основном для работы учетных систем криптовалют используется два подхода: PoW, который является наиболее распространенным, и PoS, который активно развивается в последнее время.
В PoW выполняется дополнительный объем работы, который сейчас заключается в поиске прообраза хеш-функции. Фактически здесь происходит искусственное замедление сети для обеспечения безопасности. Чтобы осуществить злонамеренное действие, злоумышленнику придется выполнить необходимый объем работы. Это требует колоссальных затрат энергии и делает реализацию атак не очень эффективной. За счет такого подхода обеспечивается надежность в работе сети. Однако необходимость выполнять настолько требовательную к ресурсам задачу ограничивает пропускную способность сети, которая работает по данному протоколу. Но над подходом PoW ученые продолжают трудиться и предлагать альтернативные схемы, а также другие ресурсоемкие задачи, помимо поиска прообраза хеш-функции. Недавно был предложен алгоритм на базе proof-of-space-and-time.
PoS позволяет обеспечить более высокую пропускную способность сети и не требует избыточных затрат электроэнергии, как PoW. Однако PoS требует более серьезного анализа при разработке и реализации криптовалюты.
В учетных системах на базе PoS предполагается, что пользователям, которые владеют большим количеством монет, невыгодно делать атаки. Если в учетных системах на базе PoW системе предприниматель вкладывает деньги в оборудование и оплачивает электроэнергию, а потом совершает успешную атаку на систему, то он будет терять свои инвестиции в майнинг. В PoS применяется другой подход: если предполагается, что злоумышленник инвестировал в конкретные монеты, в ценности которых он заинтересован, то в случае успешной атаки на систему он потеряет свои вложения, поскольку произойдет обесценивание монет. Поэтому наиболее выгодной стратегией принято считать честное следование протоколу.
Safety – способность учетной системы сохранять основные принципы функционирования и интересы честных участников при любых злоумышленных воздействиях.
Finality – свойство, которое указывает на неотменяемость принятого решения или подтвержденных данных.
Liveness – свойство, которое гарантирует, что если все честные участники хотят добавить запись в общую базу данных, то в итоге она будет туда добавлена.
Persistence – способность учетной системы сохранять неизменность конечного состояния своей базы данных даже после того, как все ее валидаторы отказали.
Permissioned – указывает на ограничение, то есть необходимость получить разрешение на участие в некотором процессе.
Permissionless – означает свободный доступ к принятию участия в некотором процессе.
Ouroboros – это протокол на базе PoS, который обеспечивает достижение консенсуса между валидаторами транзакций цифровой валюты Cardano. Причем сам алгоритм является первым доказуемо стойким среди всех PoS-альтернатив.
Сначала рассмотрим более простой вариант, ориентированный на static stake, когда предполагается, что существующее распределение монет не меняется.
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/2a6/d74/618/2a6d746180413c7cef60102d6e8c236d.png)
Есть некоторый genesis block и пользователи формируют новые транзакции, но они не влияют существенным образом на распределение.
Genesis block содержит в себе данные с некоторым случайным значением, с помощью которого происходит выбор валидаторов. Они позволяют выпускать блок в определенный момент времени. Валидатор, получивший такое право, собирает транзакции, получая их от другого валидатора, проверяет корректность и выпускает блок в сеть. Если он видит несколько цепочек, то он выбирает самую длинную из них и присоединяет блок к ней.
В контексте ситуации, связанной со static stake, мы можем использовать такой подход на протяжении определенного периода времени, но потом распределение доли (stake distribution) между различными пользователями может поменяться. Иначе говоря, часть денег переходит от одних пользователей к другим, и нужно скорректировать вероятность получения права выбора блока.
Примечание: static stake подразумевает, что некоторый промежуток времени stake валидатора считается неизменным. Валидатор может в это время участвовать в принятии решения и совершать платежи, но количество монет в его stake, а следовательно, и вес его голоса останутся неизменными до следующего периода времени.
В случае dynamic stake время делится на слоты, а слоты делятся на эпохи. Продолжительность одной эпохи приблизительно приравнивается к продолжительности одного дня. Это соотношение определено из того, что в течение этого промежутка времени распределение монет не может существенно измениться.
По завершении эпохи фиксируется текущее распределение монет у каждого из пользователей. Кроме того, генерируется новое значение случайности, чтобы гарантировать, что в следующей эпохе пользователи, получающие право генерировать блоки, будут действительно выбраны случайным образом в соответствии с количеством имеющихся у них монет.
Подобным образом происходит защита от так называемых grinding-атак, когда конкретный пользователь может перебрать различные варианты блоков, различные варианты случайности, чтобы сформировать ту цепочку, в которой он может максимизировать свою прибыль. К таким атакам потенциально уязвимы криптовалюты, основанные на PoS-протоколах первого поколения, таких как Peercoin и NXT.
Создатели данного алгоритма решили вышеперечисленные проблемы. Валидаторы запускают между собой специальный протокол, который называется MPC (multi-party computation) и дает возможность сгенерировать случайность совместно. Этот протокол также является доказуемо стойким, он основан на уже давно известных подходах.
Протокол Ouroboros обеспечивает стойкость при условии большинства честных валидаторов в системе. Если честные участники, которые работают над выпуском блоков, контролируют больше 50% монет в системе, протокол можно считать защищенным.
Разработан механизм стимулов (мотивации) к честному поведению. С помощью теории игр доказано, что максимальную выгоду валидатор получает, когда следует правилам протокола. Любое участие в совершении атак не только не увеличивает прибыль участника, но в ряде случаев может и уменьшить ее. Поэтому наиболее выгодная стратегия для валидатора – это честно следовать правилам протокола.
Пропускная способность учетной системы будет ограничена только задержками при синхронизации сети. Данный протокол обеспечивает высокую энергоэффективность по сравнению с proof-of-work, поскольку здесь не нужны майнинговые фермы. Сейчас для сбора транзакций и выпуска блоков достаточно обычного персонального компьютера. В перспективе эти вычисления можно будет осуществлять даже на обычном смартфоне.
К ограничениям протокола Ouroboros можно отнести тот факт, что первая версия протокола является синхронной. Это значит, что сообщения между участниками должны доставляться в ограниченный промежуток времени. Если в сети будут появляться более длительные задержки, чем заложены в правилах, это может снизить безопасность. Тем не менее уже запланировано использование следующей версии протокола – Ouroboros Praos. В ней даже при увеличении задержек в сети гарантируется полная безопасность.
Рассмотрим способ достижения консенсуса, который лежит в основе Bitcoin. Часть блоков, которые генерируются честными пользователями все равно отбрасывается – это так называемые orphan blocks. Эти блоки сгенерированы параллельно с основной цепочкой, но большая часть сети решила, что эту цепочку не стоит продолжать, и блоки отбрасываются.
Когда таких блоков мало, в этом нет ничего страшного. Однако если их много, сеть не успевает синхронизироваться и получается, что часть вычислительных мощностей честных пользователей сети теряется впустую. Это значит, что теперь злоумышленнику необходимо бороться не за 51% вычислительной мощности сети, а фактически за меньший процент. Если это значение 20%, то злоумышленник с 20% вычислительной мощности и большой задержкой доставки сообщений сети может реализовать double-spending атаку.
Поэтому в Биткоине установлен промежуток времени между добытыми блоками длительностью 10 минут. Благодаря этому сеть успевает четко синхронизироваться и вероятность появления таких блоков снижается. Если потребуется увеличить пропускную способность сети через увеличение частоты формирования блоков, то понадобится другое решение.
Первым таким решением был PoW-протокол GHOST. Его упрощенная версия используется в платформе Ethereum.
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/61b/2ba/ff2/61b2baff2b3749a33a35ac59ab6d5008.png)
В этом случае злоумышленник может тянуть свою цепочку (обозначенную на рисунке красным цветом) и сделать ее самой длинной, но она не будет выигрышной. Честные пользователи будут следовать той цепочке, которую они строили до этого.
У честных пользователей в этом случае может быть две цепочки. Самая длинная (1B-2D-3F-4C-5B), но она будет короче, чем цепочка злоумышленника. Особенность GHOST в том, что алгоритм ориентируется не на самую длинную цепочку, а на количество блоков в дереве, образуемом текущей цепочкой. Учитывается не только длина самой цепочки, но и блоки на разных ее высотах. Таким образом, получается не линейная цепочка, а дерево. Учитывается количество блоков, которое в нем находится.
Если посмотреть на цепочку 1B-2C-3D-4B, то видны сопровождающие блоки 3E и 3C. По количеству блоков и затраченной работы эта цепочка обладает наибольшей сложностью и именно она будет принята за основную. Честные пользователи продолжат считать ее основной, несмотря на попытки злоумышленника атаковать сеть. В традиционном консенсусе Nakamoto такая атака была бы успешной, но для GHOST она не представляет угрозы.
Тем не менее недостатком GHOST остается тот факт, что часть блоков по-прежнему теряется. В данном случае цепочка 2D-3F-4C-5B все равно будет отброшена. Следовательно, вопрос отбрасывания блоков честных пользователей остается открытым.
C целью увеличения частоты формирования блоков и решения проблемы с отбрасыванием блоков честных пользователей было предложено еще два PoW-протокола: SPECTRE и PHANTOM.
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/e8c/66d/ac6/e8c66dac6444a12fb3bd833d22384336.png)
Они используют уже даже не древовидную структуру, а так называемый направленный ациклический граф (directed acyclic graph, DAG). В этом случае валидатор включает в заголовок своего блока указатели на блоки, на которые еще не ссылаются другие валидаторы, по крайней мере в том состоянии сети, которое он видит на текущий момент времени, и отправляет блок дальше.
Поэтому получается такая структура, в которую включаются вообще все блоки, которые видят валидаторы на текущий момент времени. Здесь майнинговые мощности честных пользователей вообще не теряются. Более того, обеспечивается высокая пропускная способность сети и высокий уровень безопасности. Преимуществом такого подхода является тот факт, что система по-настоящему децентрализована.
Давайте сравним особенности сети Биткоин и сети, которая работает с помощью протоколов SPECTRE и PHANTOM. Если говорить о текущем положении в сети Биткоин, то большое значение стоит придавать майнинговым пулам. В современном Биткоине за сутки выходит 144 блока. Именно такая цифра получается, если количество минут в сутках поделить на 10. Вполне реальной может быть ситуация, когда валидатор купил оборудование, долгое время оплачивал электроэнергию, но сгенерировать блок у него так и не получилось, а за это время оборудование устарело и использовать его больше нет смысла. Чтобы избежать этой ситуации предприимчивые валидаторы объединяются в майнинговые пулы. В большинстве майнинговых пулов есть ведущий (компания/организация), что склоняет современный Биткоин к централизации процесса валидации новых транзакций.
В случае со SPECTRE и PHANTOM майнинговые пулы вообще не нужны. Если мы проведем параллель с современной сетью Биткоина, то каждый пользователь сети, которая использует протоколы SPECTRE и PHANTOM, имеет шанс выпустить один блок в сутки. Таким образом, в майнинговых пулах потребность вообще отпадает и мы приходим к действительно децентрализованной сети.
Итак, протоколы SPECTRE и PHANTOM обеспечивают высокий уровень децентрализации и высокую пропускную способность сети, но требуется хранить большой объем информации.
Следующий тип протоколов, которые применяются – это BFT-протоколы (Byzantine Fault Tolerance).
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/2e8/cc8/390/2e8cc83900502c78dcdd91dbbc164f8b.png)
Название имеет происхождение из шуточного описания проблемы, которое было сделано в 80-х годах XX столетия при разработке протокола для высоконадежных систем. Был приведен пример про византийских генералов, которые организовывают атаку на какой-то город. Задача генералов заключалась в том, чтобы прийти к единому решению. Но нужно было учесть, что среди них есть несколько предателей. Предатели могли вести себя произвольным образом и, более того, они могли влиять на передачу сообщений между честными генералами, для которых важно или одновременно атаковать город, или одновременно отступить. Если какой-то из честных генералов отступит, то противник победит армию по частям. Поэтому им необходимо было прийти к согласованному решению. Постановка задачи таким образом была сделана в работе, откуда и пошло такое название алгоритма достижения консенсуса.
Для BFT-протоколов предполагается взаимодействие равноправных узлов сети. Предполагается, что есть определенное количество злоумышленников, которые могут действовать скоординированно. Они неизвестны честным участникам. В сети возможны сбои и задержки, то есть часть сообщений может пропадать, а часть может приходить с большой задержкой. Однако накладывается ограничение на количество шагов, в течение которого все честные валидаторы должны прийти к общему решению. В примере задачи есть два варианта: атаковать или отступить.
Допускается, что честные узлы составляют более ⅔ участников. BFT-протоколы гарантированно приходят к общему решению, которое в будущем не может быть отменено. Для не BFT-протоколов вероятность отмены решения является экспоненциально убывающей, но не нулевой.
В основе Биткоина и других современных широко распространенных криптовалют лежат не BFT-протоколы. Для Биткоина есть ненулевая вероятность, которая ничтожно мала, что есть альтернативная цепочка, тянущаяся, например, еще с предыдущего месяца, года или даже с Genesis блока. Вероятность отмены текущей цепочки экспоненциально убывающая, но она существует. В случае BFT-протокола принятое решение не может быть отменено.
Первый протокол, который был применен на практике, назывался Practical BFT. Он был предложен в 1999 году. У него достаточно простое функционирование. Клиент обращается к серверу, которого выбирает лидером. Лидер передает эти сообщения другим серверам. После этого сервера сообщают друг другу о том, что пришли определенные сообщения и их необходимо внести в совместную базу данных. Каждый из валидаторов должен подтвердить, что он получил подтверждение от ⅔ других участников.
Когда валидатор получил подтверждение от ⅔ других участников о включении сообщения в свою копию базы данных, то оно вносится в локальную копию данного валидатора.
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/3df/d12/e72/3dfd12e72841067603f9d76466de6847.png)
Протокол является энергоэффективным, обеспечивает высокую пропускную способность и быстрое подтверждение транзакций, но, к сожалению, работает для малого количества валидаторов. Если на базе данного протокола проектировать кластер, файловую систему или облако, то это работает эффективно, но если мы начинаем использовать большое количество узлов, то получаем стремительный рост количества сообщений и очень большой рост нагрузки на сеть. В последнем случае протокол работает неэффективно, особенно, когда сеть работает с задержками, пропускает сообщения и т. д.
Кроме того, в базовом варианте предполагается наличие лидера, что может стать точкой DoS-атаки для остановки работы учетной системы злоумышленником.
HoneyBadger BFT хорошо зарекомендовал себя и был разработан как усовершенствованная версия одного из существующих алгоритмов. Он использует ряд особенностей, в том числе криптографическую защиту всех сообщений, которые передаются по сети. Транзакции дешифруются только после достижения определенного соглашения по ним. HoneyBadger состоит из двух протоколов: RBC (Reliable broadcast) и BA (Byzantine Agreement).
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/87b/3a4/28f/87b3a428fad9f3266abcc85518787f5b.png)
С помощью RBC-протокола сообщения доставляются по сети. Этот протокол завершает свою работу только после того, как получит подтверждение, что как минимум ⅔ честных валидаторов получили необходимый набор сообщений. После этого валидаторы переходят к BA-протоколу и согласованию самих транзакций, которые далее направляются в сеть.
Данный протокол обеспечивает надежную криптографическую защиту. Он хорошо работает в сетях с плохим качеством передачи данных, где есть пропуски передаваемых сообщений и задержки в их доставке, а также в сетях с серьезным злонамеренным вмешательством в работу. Здесь нет лидера. Протокол страдает при попытках значительного масштабирования: при сотнях узлов-валидаторов он еще работает нормально, но при нескольких тысячах уже оказывает слишком большую нагрузку на сеть и время подтверждения транзакций сильно увеличивается. В условиях полностью децентрализованной сети учетной системы, где работают тысячи валидаторов, протокол становится малоэффективным.
Результатом дальнейшего развития стали протоколы Algorand и Hashgraph.
Протокол Algorand был предложен в 2017 году. Он использует тот же BFT-подход, но ориентирован он на то, что среди всех участников случайным образом выбирается некоторый подкомитет, который выполняет подтверждение транзакций. Причем это подтверждение происходит в несколько этапов, на каждом из которых выбирается свой подкомитет.
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/b41/2e4/66e/b412e466e304f0244cdf836ec02ffe4c.png)
Протокол гарантирует с высокой вероятностью, близкой к единице, что подкомитет является честным, если более ⅔ участников сети являются честными, то есть каждый из подкомитетов также будет иметь ⅔ честных участника. Здесь нет лидера, поэтому и нет точки для атаки типа «отказ в обслуживании» (DoS-атаки). Этот протокол обеспечивает высокую пропускную способность учетной системы, быстрое подтверждение транзакций, а также защиту от adaptive corruption.
Предполагается, что злоумышленник может выбрать произвольного валидатора и заявить, что именно он работает в его интересах. Злоумышленник может выбирать те узлы, которые будут работать на него (обязательным для корректной работы является условие, что честных участников остается больше ⅔). И даже в таких условиях протокол обеспечивает стойкость.
Поскольку это BFT-протокол, то в любом случае он обеспечивает свойства safety и persistence. А остальные его свойства будут зависеть от задержек в передаче данных по каналам связи.
Если данный протокол работает в проблемной сети, то существует угроза liveness, связанная с тем, что новые транзакции могут не получать подтверждения. Если в сети появляются слишком большие задержки или злоумышленник получает возможность выбрасывать те сообщения, которые ему нужно выбросить для достижение цели, то это никак не скажется на старых (уже подтвержденных) транзакциях. Их он отменить не сможет. Суть в том, что он сможет отклонять именно принятие новых транзакций.
Протокол Hashgraph является свежим решением с очень хорошими свойствами. Каждый из валидаторов собирает свои транзакции, выбирает произвольным образом другого участника и направляет ему данные о своих транзакциях, а также информацию, которую сообщили ему другие узлы, когда подключались к нему.
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/f51/877/2cf/f518772cfe5c5933570e08bf6a556b20.png)
Итак, функционирование очень простое: валидатор «слушает», принимает все сообщения, которые приходят к нему, а после этого произвольным образом выбирает другого участника и отправляет ему все транзакции вместе со своими.
Hashgraph гарантирует, что за конечное число шагов, то есть раундов работы протокола, все узлы приходят к единому решению. Протокол работает быстро и хорошо масштабируется. Он требует большего объема трафика, чем Algorand, но в то же время является очень эффективным. Hashgraph обеспечивает свойства safety и liveness, то есть добавление новых транзакций и приход к единому решению. Он работает даже в условиях полностью асинхронной сети, когда сообщения могут быть задержаны на очень большой промежуток времени или вообще выброшены.
Кроме того, в сети отсутствует лидер, что позволяет злоумышленнику выводить из строя те узлы, которые ему окажутся интересными, может заставлять их работать сообразно своим намерениям. Однако пока сохраняется ⅔ честных пользователей, протокол обеспечивает высокий уровень безопасности.
Подведем итоги по BFT-протоколам. Они обеспечивают очень высокую пропускную способность и позволяют валидаторам приходить к согласию по поводу состояния транзакций в течение фиксированного количества шагов. Данные свойства позволяют им успешно применяться в криптовалютах. Протокол обеспечивает надежную работу даже в ненадежных сетях при условии, что более ⅔ валидаторов учетной системы являются честными. Такие протоколы, как Algorand и Hashgraph, поддерживают высокую пропускную способность и в них может работать действительно большое количество валидаторов.
В то же время у них есть очень серьезный недостаток: в текущем состоянии развития протоколы разработаны для так называемых permissioned учетных систем. Иначе говоря, они разработаны без учета стимула для валидаторов честно работать в самой сети. Предполагается, что такие стимулы находятся за пределами работы данного протокола. Не рассматриваются награды за формирование блока, различные стратегии поведения пользователей.
Чтобы развернуть такие протоколы для работы в permissionless учетных системах, исследователям понадобится провести серьезную работу. В этом отношении у них остается широкая область для исследований с точки зрения теории игр и с точки зрения разработки системы вознаграждения для валидаторов и т. д.
Distributed Lab подготовила данную статью, опираясь на материал видеолекции Романа Олейникова.
– Возможно ли в ближайшее время внедрение кардинально нового протокола консенсуса и есть ли разработки?
Сейчас, действительно, активно ведутся разработки протоколов консенсуса. Некоторые из них мы сегодня обсуждали: Algorand и Hashgraph из BFT-протоколов, а также протокол на основе PoS-консенсуса Ouroboros. В начале 2018 года был представлен протокол PHANTOM. Это новые протоколы с новыми принципами.
– Чем в Ouroboros обеспечивается, что список узлов, имеющих право формировать блок в определенные временные интервалы, одинаковый для всех узлов?
Вопрос связан с grinding-атаками, которые упоминались выше. Ouroboros обеспечивает свойства persistence и liveness: если транзакция попала в определенный момент времени и получила подтверждение, то она уже не может быть отменена или удалена, так как вероятность замены этого блока стремится к нулю. Иначе говоря, разработчики полагают, что транзакция не может пропасть из совместной базы данных, поскольку она доступна любому желающему.
За счет свойства persistence все узлы сети формируют одинаковый набор транзакций в своей локальной копии базы данных. Потенциальные валидаторы отправляют транзакции со своей случайностью, которая поначалу скрыта, а в момент завершения протокола MPC все могут рассчитать результирующую случайность. У всех пользователей есть согласованная история транзакций, благодаря чему все узлы получают одинаковый список фактических валидаторов. Манипулировать случайностью здесь невозможно, потому что протокол MPC обеспечивает свойства, связанные с тем, что ни один из участников не может получить эту случайность до того момента, пока все не внесли ее в блокчейн. Только после этого случайность вскрывается. Даже если кто-то не хочет вскрывать свою случайность, сам протокол гарантирует, что эти данные будут вскрыты. У всех одинаковое видение истории и случайности. Даже если хотя бы один потенциальный валидатор «пробросил» действительно случайное значение в блокчейн (достаточно одного), результирующая случайность будет непредсказуема.
– В какой книге можно почитать про алгоритмы достижения консенсуса, рассмотренные в этой главе?
К сожалению, пока еще таких книг нет. Есть только отдельные научные работы и статьи. Можно посмотреть статьи по PHANTOM, SPECTRE и Ouroboros. Можно посмотреть сайт, на котором эти статьи можно найти по названию.
– Зачем так много блоков выпускать в PHANTOM и SPECTRE, если нет такого большого количества транзакций? Большинство блоков будут пустыми или содержать мало транзакций.
PHANTOM и SPECTRE ориентируются именно на масштабирование. Для Биткоина уже не раз возникали ситуации, когда транзакции с низкой комиссией могли находиться в сети неподтвержденными даже несколько месяцев. PHANTOM и SPECTRE гарантируют, что все транзакции будут включены в блоки и пропускная способность сети будет увеличена. Эти протоколы могут обеспечить десятки тысяч транзакций в секунду, при этом каждая получит подтверждение. Иначе говоря, они могут обеспечить очень низкую стоимость транзакций в самой сети. Если транзакций нет, то можно, действительно, выпускать пустые блоки.
– Как и кем в BFT выбирается сервер-лидер?
Это зависит от конкретного протокола. Если мы говорим о PBFT, то в этом случае конкретный пользователь выбирает себе сервер-лидер, который будет вести его транзакцию. Если мы говорим про Algorand или Hashgraph, там лидера вообще нет.
– Что будет если в PBFT изначальный запрос придет к скомпрометированному узлу?
В этом случае скомпрометированный (или неработающий) узел его может не обработать. Если пользователь случайным образом выбирает узел, к которому он обращается, и мы имеем две трети честных узлов, то в этом случае с высокой вероятностью через несколько попыток его транзакция получит подтверждение.
– Правильно ли утверждать, что Algorand – это нечто вроде DPoS (Delegated Proof-of-stake)
Нет, это не совсем корректно. Delegated Proof-of-stake подразумевает, что пользователи должны выбрать валидатора и делегировать ему право голоса. Здесь узлы выбираются для подтверждения транзакций действительно случайно. Если посмотреть далеко в будущее и рассматривать варианты построения криптовалюты на Algorand, то дальше действительно необходимо будет разрабатывать варианты делегирования, но для работы самого протокола делегирование не нужно.
– Какие из перечисленных протоколов еще не применяются, но считаются перспективными в будущем?
SPECTRE и PHANTOM – действительно перспективные протоколы. А разработчики SPECTRE работают над тем, чтобы запустить новую цифровую валюту.
Отметим, что в децентрализованной сети применяется принцип избыточности, который основан на том, что узлы могут делать одну и ту же работу. Для централизованной сети это, естественно, неэффективно, а для децентрализованной это является обязательным условием. Перейдем к базовым требованиям.
Требования к протоколам достижения консенсуса
Протоколы должны обеспечивать надежную работу пользователей в достаточно суровых условиях и при этом удовлетворить минимальным требованиям. Ниже перечислены основные.
Отсутствие центральной доверенной стороны. Сеть состоит из равноправных узлов. Если злоумышленник или третья сторона попытаются вывести из строя определенное количество узлов, то сеть продолжит нормально работать до тех пор, пока честные участники будут контролировать подавляющее большинство узлов сети.
Честные участники не знают, какие узлы контролируются злоумышленниками. Предполагается, что другие узлы могут в произвольные моменты времени выходить из строя или функционировать произвольным образом, в том числе координироваться злоумышленниками для проведения атаки на сеть. Опять же, честные участники не знают, какие из узлов честные, а какие сбойные, или ненадежные.
Предполагается, что сеть заведомо ненадежная. Некоторые сообщения могут быть доставлены с серьезной задержкой, а другие могут быть потеряны в сети и остаться вовсе недоставленными. Именно в таких условиях децентрализованный консенсус должен продолжать нормально функционировать: все честные узлы должны приходить к одному и тому же состоянию базы данных подтвержденных транзакций.
Протоколы должны быть полностью формальными. Никакого дополнительного участия человека быть не должно и никаких дополнительных данных не требуется. Все честные узлы должны приходить к одному и тому же решению, полностью следуя алгоритму, который выполняется компьютером.
Кроме того, существуют определенные допущения, при которых протокол гарантирует корректную работу. Честные узлы должны составлять большую часть всех участников: более ½ или ⅔ от общего их количества. Однако время принятия решения не ограничено. Ограничение может касаться количества шагов для принятия решения, но не времени.
Области применения протоколов достижения консенсуса
Цифровые валюты
В первую очередь это применимо к криптовалютам: в Bitcoin применяется алгоритм Nakamoto, в Ethereum применяется упрощенный вариант GHOST, в Bitshares реализован Delegated PoS и т. д.
Нужно отметить, что сообщество, которое поддерживает определенную цифровую валюту не всегда бывает многочисленным и децентрализованным. Существует ряд других цифровых валют, которые являются централизованными. Однако это не значит, что механизм достижения консенсуса не понадобится. Например, Ripple использует BFT-протокол в централизованной среде.
Высоконадежные и критические системы
Протоколы достижения консенсуса используются в высоконадежных вычислительных системах. Они могут использоваться для доступа к распределенным базам данных при построении кластеров, а также обязательно используются в критических технических системах: это могут быть системы управления авиационным оборудованием, системы управления ядерными реакторами, а также в космических технологиях.
В 2018 году, 6 февраля, произошел запуск Falcon Heavy. Было интересно наблюдать за ним и читать технические обзоры. Но не менее интересно было читать о том, какие алгоритмы достижения согласия использует команда. Инженеры вынуждены были использовать простую электронику, которая продается в обычных магазинах и не совсем надежно работает в сложных космических условиях. Поэтому они применяют многократную избыточность в своей работе и достижение консенсуса в данном случае необходимо.
Криптовалюты
Криптовалюты работают в peer-to-peer сетях. При этом сообщения или транзакции передаются между участниками сети в произвольные моменты времени. Предположим, что в сети есть участники, находящиеся в США, и участники, находящиеся в Австралии. Платежи, которые отправлены из США, участники из Америки увидят раньше, чем платежи, отправленные из Австралии. Это происходит из-за наличия серьезной, по компьютерным меркам, задержки при доставке сообщения с одного континента на другой. Аналогичной будет ситуация и для австралийцев, потому что они будут видеть платежи из Австралии раньше, чем платежи из США.
Описанная выше ситуация значит, что разные участники сети увидят в один момент времени увидят разное итоговое состояние базы данных с транзакциями. Поскольку транзакции приходят от пользователей к валидаторам в разное время, нужен протокол, который позволит каждому узлу вне зависимости от его места нахождения получить все транзакции в одном и том же порядке.
В основном для работы учетных систем криптовалют используется два подхода: PoW, который является наиболее распространенным, и PoS, который активно развивается в последнее время.
В PoW выполняется дополнительный объем работы, который сейчас заключается в поиске прообраза хеш-функции. Фактически здесь происходит искусственное замедление сети для обеспечения безопасности. Чтобы осуществить злонамеренное действие, злоумышленнику придется выполнить необходимый объем работы. Это требует колоссальных затрат энергии и делает реализацию атак не очень эффективной. За счет такого подхода обеспечивается надежность в работе сети. Однако необходимость выполнять настолько требовательную к ресурсам задачу ограничивает пропускную способность сети, которая работает по данному протоколу. Но над подходом PoW ученые продолжают трудиться и предлагать альтернативные схемы, а также другие ресурсоемкие задачи, помимо поиска прообраза хеш-функции. Недавно был предложен алгоритм на базе proof-of-space-and-time.
PoS позволяет обеспечить более высокую пропускную способность сети и не требует избыточных затрат электроэнергии, как PoW. Однако PoS требует более серьезного анализа при разработке и реализации криптовалюты.
В учетных системах на базе PoS предполагается, что пользователям, которые владеют большим количеством монет, невыгодно делать атаки. Если в учетных системах на базе PoW системе предприниматель вкладывает деньги в оборудование и оплачивает электроэнергию, а потом совершает успешную атаку на систему, то он будет терять свои инвестиции в майнинг. В PoS применяется другой подход: если предполагается, что злоумышленник инвестировал в конкретные монеты, в ценности которых он заинтересован, то в случае успешной атаки на систему он потеряет свои вложения, поскольку произойдет обесценивание монет. Поэтому наиболее выгодной стратегией принято считать честное следование протоколу.
Краткий глоссарий
Safety – способность учетной системы сохранять основные принципы функционирования и интересы честных участников при любых злоумышленных воздействиях.
Finality – свойство, которое указывает на неотменяемость принятого решения или подтвержденных данных.
Liveness – свойство, которое гарантирует, что если все честные участники хотят добавить запись в общую базу данных, то в итоге она будет туда добавлена.
Persistence – способность учетной системы сохранять неизменность конечного состояния своей базы данных даже после того, как все ее валидаторы отказали.
Permissioned – указывает на ограничение, то есть необходимость получить разрешение на участие в некотором процессе.
Permissionless – означает свободный доступ к принятию участия в некотором процессе.
Протокол достижения консенсуса Ouroboros
Ouroboros – это протокол на базе PoS, который обеспечивает достижение консенсуса между валидаторами транзакций цифровой валюты Cardano. Причем сам алгоритм является первым доказуемо стойким среди всех PoS-альтернатив.
Сначала рассмотрим более простой вариант, ориентированный на static stake, когда предполагается, что существующее распределение монет не меняется.
![image](https://habrastorage.org/getpro/habr/post_images/2a6/d74/618/2a6d746180413c7cef60102d6e8c236d.png)
Есть некоторый genesis block и пользователи формируют новые транзакции, но они не влияют существенным образом на распределение.
Genesis block содержит в себе данные с некоторым случайным значением, с помощью которого происходит выбор валидаторов. Они позволяют выпускать блок в определенный момент времени. Валидатор, получивший такое право, собирает транзакции, получая их от другого валидатора, проверяет корректность и выпускает блок в сеть. Если он видит несколько цепочек, то он выбирает самую длинную из них и присоединяет блок к ней.
В контексте ситуации, связанной со static stake, мы можем использовать такой подход на протяжении определенного периода времени, но потом распределение доли (stake distribution) между различными пользователями может поменяться. Иначе говоря, часть денег переходит от одних пользователей к другим, и нужно скорректировать вероятность получения права выбора блока.
Примечание: static stake подразумевает, что некоторый промежуток времени stake валидатора считается неизменным. Валидатор может в это время участвовать в принятии решения и совершать платежи, но количество монет в его stake, а следовательно, и вес его голоса останутся неизменными до следующего периода времени.
В случае dynamic stake время делится на слоты, а слоты делятся на эпохи. Продолжительность одной эпохи приблизительно приравнивается к продолжительности одного дня. Это соотношение определено из того, что в течение этого промежутка времени распределение монет не может существенно измениться.
По завершении эпохи фиксируется текущее распределение монет у каждого из пользователей. Кроме того, генерируется новое значение случайности, чтобы гарантировать, что в следующей эпохе пользователи, получающие право генерировать блоки, будут действительно выбраны случайным образом в соответствии с количеством имеющихся у них монет.
Подобным образом происходит защита от так называемых grinding-атак, когда конкретный пользователь может перебрать различные варианты блоков, различные варианты случайности, чтобы сформировать ту цепочку, в которой он может максимизировать свою прибыль. К таким атакам потенциально уязвимы криптовалюты, основанные на PoS-протоколах первого поколения, таких как Peercoin и NXT.
Создатели данного алгоритма решили вышеперечисленные проблемы. Валидаторы запускают между собой специальный протокол, который называется MPC (multi-party computation) и дает возможность сгенерировать случайность совместно. Этот протокол также является доказуемо стойким, он основан на уже давно известных подходах.
Протокол Ouroboros обеспечивает стойкость при условии большинства честных валидаторов в системе. Если честные участники, которые работают над выпуском блоков, контролируют больше 50% монет в системе, протокол можно считать защищенным.
Разработан механизм стимулов (мотивации) к честному поведению. С помощью теории игр доказано, что максимальную выгоду валидатор получает, когда следует правилам протокола. Любое участие в совершении атак не только не увеличивает прибыль участника, но в ряде случаев может и уменьшить ее. Поэтому наиболее выгодная стратегия для валидатора – это честно следовать правилам протокола.
Пропускная способность учетной системы будет ограничена только задержками при синхронизации сети. Данный протокол обеспечивает высокую энергоэффективность по сравнению с proof-of-work, поскольку здесь не нужны майнинговые фермы. Сейчас для сбора транзакций и выпуска блоков достаточно обычного персонального компьютера. В перспективе эти вычисления можно будет осуществлять даже на обычном смартфоне.
К ограничениям протокола Ouroboros можно отнести тот факт, что первая версия протокола является синхронной. Это значит, что сообщения между участниками должны доставляться в ограниченный промежуток времени. Если в сети будут появляться более длительные задержки, чем заложены в правилах, это может снизить безопасность. Тем не менее уже запланировано использование следующей версии протокола – Ouroboros Praos. В ней даже при увеличении задержек в сети гарантируется полная безопасность.
Проблемы с PoW в Биткоине
Рассмотрим способ достижения консенсуса, который лежит в основе Bitcoin. Часть блоков, которые генерируются честными пользователями все равно отбрасывается – это так называемые orphan blocks. Эти блоки сгенерированы параллельно с основной цепочкой, но большая часть сети решила, что эту цепочку не стоит продолжать, и блоки отбрасываются.
Когда таких блоков мало, в этом нет ничего страшного. Однако если их много, сеть не успевает синхронизироваться и получается, что часть вычислительных мощностей честных пользователей сети теряется впустую. Это значит, что теперь злоумышленнику необходимо бороться не за 51% вычислительной мощности сети, а фактически за меньший процент. Если это значение 20%, то злоумышленник с 20% вычислительной мощности и большой задержкой доставки сообщений сети может реализовать double-spending атаку.
Поэтому в Биткоине установлен промежуток времени между добытыми блоками длительностью 10 минут. Благодаря этому сеть успевает четко синхронизироваться и вероятность появления таких блоков снижается. Если потребуется увеличить пропускную способность сети через увеличение частоты формирования блоков, то понадобится другое решение.
GHOST
Первым таким решением был PoW-протокол GHOST. Его упрощенная версия используется в платформе Ethereum.
![image](https://habrastorage.org/getpro/habr/post_images/61b/2ba/ff2/61b2baff2b3749a33a35ac59ab6d5008.png)
В этом случае злоумышленник может тянуть свою цепочку (обозначенную на рисунке красным цветом) и сделать ее самой длинной, но она не будет выигрышной. Честные пользователи будут следовать той цепочке, которую они строили до этого.
У честных пользователей в этом случае может быть две цепочки. Самая длинная (1B-2D-3F-4C-5B), но она будет короче, чем цепочка злоумышленника. Особенность GHOST в том, что алгоритм ориентируется не на самую длинную цепочку, а на количество блоков в дереве, образуемом текущей цепочкой. Учитывается не только длина самой цепочки, но и блоки на разных ее высотах. Таким образом, получается не линейная цепочка, а дерево. Учитывается количество блоков, которое в нем находится.
Если посмотреть на цепочку 1B-2C-3D-4B, то видны сопровождающие блоки 3E и 3C. По количеству блоков и затраченной работы эта цепочка обладает наибольшей сложностью и именно она будет принята за основную. Честные пользователи продолжат считать ее основной, несмотря на попытки злоумышленника атаковать сеть. В традиционном консенсусе Nakamoto такая атака была бы успешной, но для GHOST она не представляет угрозы.
Тем не менее недостатком GHOST остается тот факт, что часть блоков по-прежнему теряется. В данном случае цепочка 2D-3F-4C-5B все равно будет отброшена. Следовательно, вопрос отбрасывания блоков честных пользователей остается открытым.
SPECTRE и PHANTOM
C целью увеличения частоты формирования блоков и решения проблемы с отбрасыванием блоков честных пользователей было предложено еще два PoW-протокола: SPECTRE и PHANTOM.
![image](https://habrastorage.org/getpro/habr/post_images/e8c/66d/ac6/e8c66dac6444a12fb3bd833d22384336.png)
Они используют уже даже не древовидную структуру, а так называемый направленный ациклический граф (directed acyclic graph, DAG). В этом случае валидатор включает в заголовок своего блока указатели на блоки, на которые еще не ссылаются другие валидаторы, по крайней мере в том состоянии сети, которое он видит на текущий момент времени, и отправляет блок дальше.
Поэтому получается такая структура, в которую включаются вообще все блоки, которые видят валидаторы на текущий момент времени. Здесь майнинговые мощности честных пользователей вообще не теряются. Более того, обеспечивается высокая пропускная способность сети и высокий уровень безопасности. Преимуществом такого подхода является тот факт, что система по-настоящему децентрализована.
Давайте сравним особенности сети Биткоин и сети, которая работает с помощью протоколов SPECTRE и PHANTOM. Если говорить о текущем положении в сети Биткоин, то большое значение стоит придавать майнинговым пулам. В современном Биткоине за сутки выходит 144 блока. Именно такая цифра получается, если количество минут в сутках поделить на 10. Вполне реальной может быть ситуация, когда валидатор купил оборудование, долгое время оплачивал электроэнергию, но сгенерировать блок у него так и не получилось, а за это время оборудование устарело и использовать его больше нет смысла. Чтобы избежать этой ситуации предприимчивые валидаторы объединяются в майнинговые пулы. В большинстве майнинговых пулов есть ведущий (компания/организация), что склоняет современный Биткоин к централизации процесса валидации новых транзакций.
В случае со SPECTRE и PHANTOM майнинговые пулы вообще не нужны. Если мы проведем параллель с современной сетью Биткоина, то каждый пользователь сети, которая использует протоколы SPECTRE и PHANTOM, имеет шанс выпустить один блок в сутки. Таким образом, в майнинговых пулах потребность вообще отпадает и мы приходим к действительно децентрализованной сети.
Итак, протоколы SPECTRE и PHANTOM обеспечивают высокий уровень децентрализации и высокую пропускную способность сети, но требуется хранить большой объем информации.
BFT-протоколы
Следующий тип протоколов, которые применяются – это BFT-протоколы (Byzantine Fault Tolerance).
![image](https://habrastorage.org/getpro/habr/post_images/2e8/cc8/390/2e8cc83900502c78dcdd91dbbc164f8b.png)
Название имеет происхождение из шуточного описания проблемы, которое было сделано в 80-х годах XX столетия при разработке протокола для высоконадежных систем. Был приведен пример про византийских генералов, которые организовывают атаку на какой-то город. Задача генералов заключалась в том, чтобы прийти к единому решению. Но нужно было учесть, что среди них есть несколько предателей. Предатели могли вести себя произвольным образом и, более того, они могли влиять на передачу сообщений между честными генералами, для которых важно или одновременно атаковать город, или одновременно отступить. Если какой-то из честных генералов отступит, то противник победит армию по частям. Поэтому им необходимо было прийти к согласованному решению. Постановка задачи таким образом была сделана в работе, откуда и пошло такое название алгоритма достижения консенсуса.
Для BFT-протоколов предполагается взаимодействие равноправных узлов сети. Предполагается, что есть определенное количество злоумышленников, которые могут действовать скоординированно. Они неизвестны честным участникам. В сети возможны сбои и задержки, то есть часть сообщений может пропадать, а часть может приходить с большой задержкой. Однако накладывается ограничение на количество шагов, в течение которого все честные валидаторы должны прийти к общему решению. В примере задачи есть два варианта: атаковать или отступить.
Допускается, что честные узлы составляют более ⅔ участников. BFT-протоколы гарантированно приходят к общему решению, которое в будущем не может быть отменено. Для не BFT-протоколов вероятность отмены решения является экспоненциально убывающей, но не нулевой.
В основе Биткоина и других современных широко распространенных криптовалют лежат не BFT-протоколы. Для Биткоина есть ненулевая вероятность, которая ничтожно мала, что есть альтернативная цепочка, тянущаяся, например, еще с предыдущего месяца, года или даже с Genesis блока. Вероятность отмены текущей цепочки экспоненциально убывающая, но она существует. В случае BFT-протокола принятое решение не может быть отменено.
Примеры BFT-протоколов
Practical BFT
Первый протокол, который был применен на практике, назывался Practical BFT. Он был предложен в 1999 году. У него достаточно простое функционирование. Клиент обращается к серверу, которого выбирает лидером. Лидер передает эти сообщения другим серверам. После этого сервера сообщают друг другу о том, что пришли определенные сообщения и их необходимо внести в совместную базу данных. Каждый из валидаторов должен подтвердить, что он получил подтверждение от ⅔ других участников.
Когда валидатор получил подтверждение от ⅔ других участников о включении сообщения в свою копию базы данных, то оно вносится в локальную копию данного валидатора.
![image](https://habrastorage.org/getpro/habr/post_images/3df/d12/e72/3dfd12e72841067603f9d76466de6847.png)
Протокол является энергоэффективным, обеспечивает высокую пропускную способность и быстрое подтверждение транзакций, но, к сожалению, работает для малого количества валидаторов. Если на базе данного протокола проектировать кластер, файловую систему или облако, то это работает эффективно, но если мы начинаем использовать большое количество узлов, то получаем стремительный рост количества сообщений и очень большой рост нагрузки на сеть. В последнем случае протокол работает неэффективно, особенно, когда сеть работает с задержками, пропускает сообщения и т. д.
Кроме того, в базовом варианте предполагается наличие лидера, что может стать точкой DoS-атаки для остановки работы учетной системы злоумышленником.
HoneyBadger BFT
HoneyBadger BFT хорошо зарекомендовал себя и был разработан как усовершенствованная версия одного из существующих алгоритмов. Он использует ряд особенностей, в том числе криптографическую защиту всех сообщений, которые передаются по сети. Транзакции дешифруются только после достижения определенного соглашения по ним. HoneyBadger состоит из двух протоколов: RBC (Reliable broadcast) и BA (Byzantine Agreement).
![image](https://habrastorage.org/getpro/habr/post_images/87b/3a4/28f/87b3a428fad9f3266abcc85518787f5b.png)
С помощью RBC-протокола сообщения доставляются по сети. Этот протокол завершает свою работу только после того, как получит подтверждение, что как минимум ⅔ честных валидаторов получили необходимый набор сообщений. После этого валидаторы переходят к BA-протоколу и согласованию самих транзакций, которые далее направляются в сеть.
Данный протокол обеспечивает надежную криптографическую защиту. Он хорошо работает в сетях с плохим качеством передачи данных, где есть пропуски передаваемых сообщений и задержки в их доставке, а также в сетях с серьезным злонамеренным вмешательством в работу. Здесь нет лидера. Протокол страдает при попытках значительного масштабирования: при сотнях узлов-валидаторов он еще работает нормально, но при нескольких тысячах уже оказывает слишком большую нагрузку на сеть и время подтверждения транзакций сильно увеличивается. В условиях полностью децентрализованной сети учетной системы, где работают тысячи валидаторов, протокол становится малоэффективным.
Результатом дальнейшего развития стали протоколы Algorand и Hashgraph.
Algorand
Протокол Algorand был предложен в 2017 году. Он использует тот же BFT-подход, но ориентирован он на то, что среди всех участников случайным образом выбирается некоторый подкомитет, который выполняет подтверждение транзакций. Причем это подтверждение происходит в несколько этапов, на каждом из которых выбирается свой подкомитет.
![image](https://habrastorage.org/getpro/habr/post_images/b41/2e4/66e/b412e466e304f0244cdf836ec02ffe4c.png)
Протокол гарантирует с высокой вероятностью, близкой к единице, что подкомитет является честным, если более ⅔ участников сети являются честными, то есть каждый из подкомитетов также будет иметь ⅔ честных участника. Здесь нет лидера, поэтому и нет точки для атаки типа «отказ в обслуживании» (DoS-атаки). Этот протокол обеспечивает высокую пропускную способность учетной системы, быстрое подтверждение транзакций, а также защиту от adaptive corruption.
Предполагается, что злоумышленник может выбрать произвольного валидатора и заявить, что именно он работает в его интересах. Злоумышленник может выбирать те узлы, которые будут работать на него (обязательным для корректной работы является условие, что честных участников остается больше ⅔). И даже в таких условиях протокол обеспечивает стойкость.
Поскольку это BFT-протокол, то в любом случае он обеспечивает свойства safety и persistence. А остальные его свойства будут зависеть от задержек в передаче данных по каналам связи.
Если данный протокол работает в проблемной сети, то существует угроза liveness, связанная с тем, что новые транзакции могут не получать подтверждения. Если в сети появляются слишком большие задержки или злоумышленник получает возможность выбрасывать те сообщения, которые ему нужно выбросить для достижение цели, то это никак не скажется на старых (уже подтвержденных) транзакциях. Их он отменить не сможет. Суть в том, что он сможет отклонять именно принятие новых транзакций.
Hashgraph
Протокол Hashgraph является свежим решением с очень хорошими свойствами. Каждый из валидаторов собирает свои транзакции, выбирает произвольным образом другого участника и направляет ему данные о своих транзакциях, а также информацию, которую сообщили ему другие узлы, когда подключались к нему.
![image](https://habrastorage.org/getpro/habr/post_images/f51/877/2cf/f518772cfe5c5933570e08bf6a556b20.png)
Итак, функционирование очень простое: валидатор «слушает», принимает все сообщения, которые приходят к нему, а после этого произвольным образом выбирает другого участника и отправляет ему все транзакции вместе со своими.
Hashgraph гарантирует, что за конечное число шагов, то есть раундов работы протокола, все узлы приходят к единому решению. Протокол работает быстро и хорошо масштабируется. Он требует большего объема трафика, чем Algorand, но в то же время является очень эффективным. Hashgraph обеспечивает свойства safety и liveness, то есть добавление новых транзакций и приход к единому решению. Он работает даже в условиях полностью асинхронной сети, когда сообщения могут быть задержаны на очень большой промежуток времени или вообще выброшены.
Кроме того, в сети отсутствует лидер, что позволяет злоумышленнику выводить из строя те узлы, которые ему окажутся интересными, может заставлять их работать сообразно своим намерениям. Однако пока сохраняется ⅔ честных пользователей, протокол обеспечивает высокий уровень безопасности.
Итоги по BFT
Подведем итоги по BFT-протоколам. Они обеспечивают очень высокую пропускную способность и позволяют валидаторам приходить к согласию по поводу состояния транзакций в течение фиксированного количества шагов. Данные свойства позволяют им успешно применяться в криптовалютах. Протокол обеспечивает надежную работу даже в ненадежных сетях при условии, что более ⅔ валидаторов учетной системы являются честными. Такие протоколы, как Algorand и Hashgraph, поддерживают высокую пропускную способность и в них может работать действительно большое количество валидаторов.
В то же время у них есть очень серьезный недостаток: в текущем состоянии развития протоколы разработаны для так называемых permissioned учетных систем. Иначе говоря, они разработаны без учета стимула для валидаторов честно работать в самой сети. Предполагается, что такие стимулы находятся за пределами работы данного протокола. Не рассматриваются награды за формирование блока, различные стратегии поведения пользователей.
Чтобы развернуть такие протоколы для работы в permissionless учетных системах, исследователям понадобится провести серьезную работу. В этом отношении у них остается широкая область для исследований с точки зрения теории игр и с точки зрения разработки системы вознаграждения для валидаторов и т. д.
Distributed Lab подготовила данную статью, опираясь на материал видеолекции Романа Олейникова.
Часто задаваемые вопросы
– Возможно ли в ближайшее время внедрение кардинально нового протокола консенсуса и есть ли разработки?
Сейчас, действительно, активно ведутся разработки протоколов консенсуса. Некоторые из них мы сегодня обсуждали: Algorand и Hashgraph из BFT-протоколов, а также протокол на основе PoS-консенсуса Ouroboros. В начале 2018 года был представлен протокол PHANTOM. Это новые протоколы с новыми принципами.
– Чем в Ouroboros обеспечивается, что список узлов, имеющих право формировать блок в определенные временные интервалы, одинаковый для всех узлов?
Вопрос связан с grinding-атаками, которые упоминались выше. Ouroboros обеспечивает свойства persistence и liveness: если транзакция попала в определенный момент времени и получила подтверждение, то она уже не может быть отменена или удалена, так как вероятность замены этого блока стремится к нулю. Иначе говоря, разработчики полагают, что транзакция не может пропасть из совместной базы данных, поскольку она доступна любому желающему.
За счет свойства persistence все узлы сети формируют одинаковый набор транзакций в своей локальной копии базы данных. Потенциальные валидаторы отправляют транзакции со своей случайностью, которая поначалу скрыта, а в момент завершения протокола MPC все могут рассчитать результирующую случайность. У всех пользователей есть согласованная история транзакций, благодаря чему все узлы получают одинаковый список фактических валидаторов. Манипулировать случайностью здесь невозможно, потому что протокол MPC обеспечивает свойства, связанные с тем, что ни один из участников не может получить эту случайность до того момента, пока все не внесли ее в блокчейн. Только после этого случайность вскрывается. Даже если кто-то не хочет вскрывать свою случайность, сам протокол гарантирует, что эти данные будут вскрыты. У всех одинаковое видение истории и случайности. Даже если хотя бы один потенциальный валидатор «пробросил» действительно случайное значение в блокчейн (достаточно одного), результирующая случайность будет непредсказуема.
– В какой книге можно почитать про алгоритмы достижения консенсуса, рассмотренные в этой главе?
К сожалению, пока еще таких книг нет. Есть только отдельные научные работы и статьи. Можно посмотреть статьи по PHANTOM, SPECTRE и Ouroboros. Можно посмотреть сайт, на котором эти статьи можно найти по названию.
– Зачем так много блоков выпускать в PHANTOM и SPECTRE, если нет такого большого количества транзакций? Большинство блоков будут пустыми или содержать мало транзакций.
PHANTOM и SPECTRE ориентируются именно на масштабирование. Для Биткоина уже не раз возникали ситуации, когда транзакции с низкой комиссией могли находиться в сети неподтвержденными даже несколько месяцев. PHANTOM и SPECTRE гарантируют, что все транзакции будут включены в блоки и пропускная способность сети будет увеличена. Эти протоколы могут обеспечить десятки тысяч транзакций в секунду, при этом каждая получит подтверждение. Иначе говоря, они могут обеспечить очень низкую стоимость транзакций в самой сети. Если транзакций нет, то можно, действительно, выпускать пустые блоки.
– Как и кем в BFT выбирается сервер-лидер?
Это зависит от конкретного протокола. Если мы говорим о PBFT, то в этом случае конкретный пользователь выбирает себе сервер-лидер, который будет вести его транзакцию. Если мы говорим про Algorand или Hashgraph, там лидера вообще нет.
– Что будет если в PBFT изначальный запрос придет к скомпрометированному узлу?
В этом случае скомпрометированный (или неработающий) узел его может не обработать. Если пользователь случайным образом выбирает узел, к которому он обращается, и мы имеем две трети честных узлов, то в этом случае с высокой вероятностью через несколько попыток его транзакция получит подтверждение.
– Правильно ли утверждать, что Algorand – это нечто вроде DPoS (Delegated Proof-of-stake)
Нет, это не совсем корректно. Delegated Proof-of-stake подразумевает, что пользователи должны выбрать валидатора и делегировать ему право голоса. Здесь узлы выбираются для подтверждения транзакций действительно случайно. Если посмотреть далеко в будущее и рассматривать варианты построения криптовалюты на Algorand, то дальше действительно необходимо будет разрабатывать варианты делегирования, но для работы самого протокола делегирование не нужно.
– Какие из перечисленных протоколов еще не применяются, но считаются перспективными в будущем?
SPECTRE и PHANTOM – действительно перспективные протоколы. А разработчики SPECTRE работают над тем, чтобы запустить новую цифровую валюту.