Обзор алгоритмов блокчейн консенсуса: Ouroboros PoS, Proof of Elapsed Time, Practical Byzantine Fault Tolerance

В новом обзоре алгоритмов консенсуса вашему вниманию я подобрал еще несколько наиболее интересных для меня алгоритмов.

Как видно из названия, алгоритм Ouroboros PoS (далее Ouroboros) базируется на использовании алгоритма PoS. В частности он выглядит похожим на подмножество алгоритмов Delegated PoS (DPoS), но с некоторыми нюансами.
Также как и в классическом PoS алгоритме, в формировании блоков могут принимать участие все Владельцы узлов имеющие положительный баланс токенов.

Давайте рассмотрим каким именно образом выбираются узлы, осуществляющие формирование и подписание блоков. Основными временными сущностями в Ouroboros являются Эпохи и Слоты, каждая Эпоха делится на Слоты (например, 20 секунд). У каждого Слота есть свой Слот Лидер — выбранный владелец узла, который должен сформировать и подписать один блок, формируемый в рамках одного, определенного Слота. В том случае, если по какой-либо причине, Слот Лидер не смог подписать блок в своем Слоте, он теряет свое право формирования блока в текущем Слоте.

Выбор Слот Лидеров осуществляется следующим образом:
- Перед каждой Эпохой производится выбор Слот Лидеров для Эпохи и соответственно формируется количество Слотов в ней.
- Шанс стать Слот Лидером есть у каждого владельца токенов, но чем больше токенов есть у владельца, тем выше его шансы на то, чтобы стать Слот Лидером.
- Выбором занимается специальная группа владельцев — Выборщиков, имеющая существенное количество токенов, например 2% от всех токенов.
- Каждый из выборщиков производит случайный выбор потенциальных Слот Лидеров, после чего, используя алгоритм Follow-the-Satoshi, из сформированного списка выбираются реальные Слот Лидеры для следующей Эпохи.

Ссылки
- Ouroboros A Provably Secure Proof of Stake Protocol / Video presentation
- Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol / pdf
- Ouroboros Proof of Stake Algorythm
- Алгоритм Ouroboros Proof-of-stake (PoS)
- Peer Review of Cardano's Ouroboros / Daniel Larimer / тоже самое на русском языке

Алгоритм консенсуса Proof-of-Elapsed-Time, предложенный компанией Intel, на данный момент используется в качестве алгоритма консенсуса в проекте Hyperledger Sawtooth.

По-сути, алгоритм PoET похож на алгоритм PoW, но без использования существенного количества электроэнергии, необходимой для функционирования алгоритма PoW. Оборудование, используемое для генерации блока, создает блок и дальше переключается на другие, не связанные с генерацией блоков задачи до того момента, пока не придет его время для того, чтобы сгенерировать следующий блок. Встроенный механизм гарантирует, что каждый из узлов сети уверен, что время выбрано случайным образом: оно изначально не меньше определенного для всех узлов блокчейн сети, а также то, что выигравший узел ожидал необходимое время. За обеспечение работы этого механизма отвечают специальные инструкции процессоров компании Intel (Intel Software Guard Extensions (SGX).

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

Ссылки
- PoET 1.0 Specification
- Trusted execution environment
- DEFINITION of 'Proof of Elapsed Time (Cryptocurrency)'
- On Security Analysis of Proof-of-Elapsed-Time (PoET)

Алгоритм pBFT был предложен в уже далеком 1999г. как механизм обеспечивающий целостность работы распределенной сети. Во время своей работы pBFT достаточно интенсивно использует сеть для обмена сообщениями между узлами сети для обеспечения целостной работы сети. pBFT лучше всего подходит для работы в доверенных сетях, например таких как внутрикорпоративные или межорганизационные блокчейны. Именно поэтому данный алгоритм используется в проекте Hyperledger, который и предназначен для работы в подобной среде.

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

Достоинства
- Позволяет отказаться от существенных расходов на "бессмысленные" вычисления, как в случае с PoW.
- Обладает достаточно высокой производительностью при относительно небольшом количестве узлов блокчейн сети.

Недостатки
- Имеет высокие накладные расходы на взаимодействия между узлами сети.
- Из-за предыдущего пункта имеет существенное ограничение в размере сети, т.к. достаточно большая сеть будет "заблокирована" высокими сетевыми издержками между узлами.
- Обладает существенной уязвимостью при построении небольших сетей (<20 узлов), а также сетей с одним контролирующим (управляющим) лицом, например в рамках одной организации.

Ссылки
- Byzantine fault tolerance
- Practical Byzantine Fault Tolerance (.pdf)
- pBFT— Understanding the Consensus Algorithm
- Sybil attack

С момента предыдущего обзора, в котором я рассмотрел 9 наиболее популярных алгоритмов консенсуса прошло чуть больше года, а ведь я собирался выпустить новый обзор практически сразу. Явно, сейчас на рынке представлено существенно больше 12 алгоритмов консенсуса, но они либо являются производными от рассмотренных мною алгоритмов, либо по тем или иным причинам не представляют, по крайней мере пока, для меня интереса.
Если вы хотите, чтобы я в сжатом виде рассмотрел какие-то другие алгоритмы консенсуса — не стесняйтесь, оставляйте свою заявку, используя форму ниже и я постараюсь в ближайшем будущем рассмотреть их.