Catchain: алгоритм консенсуса блокчейна TON

Моя цель - предложение широкого ассортимента товаров и услуг на постоянно высоком качестве обслуживания по самым выгодным ценам.

В предыдущем обзоре наша команда R&D рассказала о структуре Telegram Open Network и особенностях функционирования ключевых узлов (валидаторов) TON Blockchain, а также поделилась опытом Mercuryo, как валидатора сети.


Эта статья посвящена одному из ключевых вопросов, отвечающему за безопасность и корректность работы блокчейна TON — протоколу достижения консенсуса между валидаторами сети, который подробно описан в недавно выпущенном документе Catchain Consensus: An Outline под авторством Николая Дурова.


Первоначальное название протокола на предварительном этапе исследования и разработки было Catch-chain (блокчейн-ловушка), поскольку по сути это отдельный блокчейн, предназначенный для перехвата нежелательных событий, затрудняющих достижение консенсуса в основном блокчейне TON. В дальнейшем его название было сокращено до Catchain.


По сути консенсус TON — это алгоритм из семейства BFT, который включает в себя как сам алгоритм консенсуса, так и протокол обмена сообщениями между узлами валидаторов сети. Известно, что BFT консенсус основан на т.н. “Соглашении Византийских Генералов” и описывает проблему достижения согласия в распределенной системе при условии, что отдельный участник не располагает информацией обо всей сети и не доверяет ни одному из ее участников.



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


1) Когда блоки создаются ДО достижения консенсуса (классические PoW, PoS и т.п. системы) с последующим сложным процессом согласования между участниками сети. При этом возможно одновременное существование нескольких “правильных” блокчейнов, из которых в дальнейшем выбирается одна истинная цепочка.
2) Когда блоки создаются ПОСЛЕ достижения консенсуса. В таких системах невозможно существование одновременно нескольких блокчейнов.


Catchain принадлежит ко второму типу алгоритмов, в которых предварительное согласование происходит до создания нового блока и промежуточные форки (разветвления) практически невозможны. Модель консенсуса Catchain основана на уже известном алгоритме practical Byzantine Fault Tolerance (Hyperledger Fabric, Zilliqa), обладающем повышенной стойкостью против атак Сивиллы в асинхронных сетях, а также имеет сходства с Tendermint (Cosmos) и алгоритмами dBFT (Neo, Algorand). Однако существует ряд принципиальных отличий, которые позволяют отнести его к отдельному классу алгоритмов.


Раунды валидации


Для конкретной задачи создания новых блоков одного из блокчейнов TON (мастерчейна или одного из активных шардчейнов) создается специальная группа, состоящая из нескольких валидаторов. Члены этой группы используются как для создания приватной оверлейной сети внутри ADNL, так и для запуска соответствующего экземпляра протокола Catchain.
Процесс достижения консенсуса состоит из нескольких раундов, которые выполняются внутри одного catchain. В один момент времени может проходить несколько раундов, поскольку одни этапы одного раунда могут пересекаться с другими.


Каждый раунд заканчивается либо коллективным принятием блока-кандидата, предложенного одним из участников процесса, либо принятием особого “нулевого кандидата”, т.е. не принятием ни одного из предложенных кандидатов. Раунд считается завершённым только после того, как потенциальный кандидат соберет подписи более чем 2/3 всех валидаторов и это событие может быть добавлено в специальный CommitSign, после чего процесс автоматически начинает участвовать в следующем раунде (с новым идентификатором).



События одного раунда валидации происходят в следующей последовательности:


  • В начале каждого раунда несколько валидаторов (из заранее составленного списка) предоставляют свои т.н. блок-кандидаты (с задержками в зависимости от приоритета) и фиксируют этот факт посредством Submit events в данный catchain.
  • Как только процесс получает все необходимые файлы, он начинает валидацию этого кандидата и в конечном итоге создается одно из событий: Approve или Reject для данного конкретного кандидата.
  • Далее каждый валидатор голосует либо за кандидата, набравшего более 2/3 голосов, либо, если таких кандидатов еще нет, за действительного кандидата с наивысшим приоритетом. Голосование осуществляется путем создания событий голосования, встроенных в новые сообщения.
  • При каждой медленной попытке (т.е. любой попытке, кроме первой) процесс голосует либо за кандидата, который был предварительно принят (тем же самым процессом), либо за кандидата, который был предложен VoteFor.
  • Если в ходе такой попытки данный кандидат получил более 2/3 голосов «за», то создается следующее событие PreCommit, подтверждающее то, что все другие кандидаты отбрасываются.
  • Далее, если такой блок-кандидат собирает PreCommits более чем у 2/3 всех валидаторов внутри данной попытки, то он будет принят и отмечен событием CommitSign с действительной подписью блока.
  • Все подписи блоков регистрируются в catchain, и в конечном итоге собираются для создания «доказательства блока» (содержащего подписи более 2/3 валидаторов для этого блока). Такое доказательство является внешним выходом протокола консенсуса и распространяется в оверлейной сети полных узлов, которые подписывают новые блоки этого шардчейна или мастерчейна.
  • Как только кандидат в блоки собирает подписи CommitSign более чем у 2/3 всех валидаторов, раунд считается завершённым и процесс автоматически начинает участвовать в следующем раунде, игнорируя все события, связанные другими раундами.

Предотвращение форков


Как уже говорилось выше, в блокчейнах с традиционными механизмами защиты посредством Proof-of-Work и Proof-of-Stake, а также их гибридами, какое-то непродолжительное время могут существовать несколько “правильных” цепочек блоков или форков, из которых потом выбирается одна.


Система TON Blockchain, построенная на основе множества небольших блокчейнов (multi-blockchain), практически не оставляет шансов для возникновения такого рода событий, т.к. использует блокчейн в качестве средства трансляции сообщений внутри определённой группы процессов. Однако, всё же существует небольшая вероятность создания и одновременного подтверждения нескольких идентичных блоков.


Именно для предотвращения таких сценариев как раз и создан протокол Catchain, который методом создания двух (или более) разных версий одного и того же сообщения и рассылки их разным группам пиров, позволяет выявить форки на самой ранней стадии их возникновения.


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



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


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


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


Заключение


Известно, что протокол Catchain был впервые реализован в декабре 2018 г. и протестирован на 300 узлах, распределенных по всему миру. При этом время, за которое был достигнут консенсус при создании блока, составило около 6 секунд. Далее, в январе 2019 г. был выпущен документ, который свидетельствует о том, что протокол Catchain готов на 100%. Следовательно можно сделать вывод о том, что все предварительные тесты прошли успешно. Однако, в статусе также указано, что полная документация готова лишь на 95%, при этом финальный документ был выпущен только через год, в феврале 2020 г. Таким образом можно предположить, что теоретическая часть достаточно детально проработана и представляет из себя полностью завершённую оригинальную модель консенсуса, готовую к реализации в основной сети.


Кстати, коллеги из TON Labs смогли восстановить работу протокола и подготовили его описание ещё до того, как документация была опубликована.

Источник: https://habr.com/ru/company/mercuryo/blog/490392/


Интересные статьи

Интересные статьи

Побег от алгоритма YouTube Я люблю смотреть видео на YouTube, осязаемым образом улучшающие мою жизнь. К сожалению, алгоритм YouTube с этим не согласен. Он любит кормить меня кликбэйт...
Практически любому современному бизнесу важны современные инструменты контекстной рекламы, в особенности — Google AdSense. Еще важнее эта система площадкам, которые размещают у себя рекламу. Каза...
Команда исследователей из компании Google представила новую разработку — алгоритм автоматического кадрирования видео. Исходный материал редактируется машиной, пользователю нужно лишь задать о...
Ваш сайт работает на 1С-Битрикс? Каждому клиенту вы даёте собственную скидку или назначаете персональную цену на товар? Со временем в вашей 1С сложилась непростая логика ценообразования и формирования...
В MIT представили интерактивный инструмент, который дает понять, почему интеллектуальная система принимает то или иное решение. В этом материале — о том, как он работает.