20 февраля 2021

Как работает алгоритм консенсуса Free TON, разработанный Николаем Дуровым

Процесс производства блоков в сети Free TON основан на разновидности алгоритма Proof-of-Stake под названием «Византийская отказоустойчивость» (Byzantine Fault Tolerance, BFT).

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

Задача византийских генералов

Механизм «Византийской отказоустойчивости» относится к «Задаче византийских генералов», описанной в 1982 году. Это логическая задача о том, как византийский генерал должен договориться о совместных действиях на поле боя со своими лейтенантами, каждый из которых командует отдельным отрядом.

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

При этом один или несколько офицеров являются предателями. Чтобы достигнуть консенсуса, нужно, чтобы две трети участников были честными и смогли согласовать свои решения.

Пример решения задачи

Представим, что есть генерал и 3 лейтенанта. Генерал, Лейтенант 1 и Лейтенант 2 лояльны, а Лейтенант 3 — предатель. Для достижения консенсуса необходимо 3 решения. Вот, как это можно сделать:

Шаг 1. Генерал посылает приказ к атаке (значение Y) с указанием точного времени действия.

Шаг 2. Лейтенанты обмениваются приказами между собой. Лояльные офицеры (Лейтенант 1 и Лейтенант 2) передают эту значение Y двум другим. Но предатель (Лейтенант 3) пересылает другое значение (X) двум лояльным офицерам. 

Шаг 3. Каждый лейтенант принимает личное решение на основании решений от других участников. 

Лейтенант 1 получает значение Y от генерала, Y от Лейтенанта 2 и X от Лейтенанта 3 (предателя) и выбирает Y.

Лейтенант 2 получает значение Y от генерала, Y от Лейтенанта 2 и X от Лейтенанта 3 (предателя) и выбирает Y.

Лейтенант 3 получает Y от генерала, Y от Лейтенанта 1 и Y от Лейтенанта 2. Но так как он предатель, то может принять любое решение из двух (Y или X).

Вывод. Два из трех лейтенантов приняли одно и то же решение — Y. Но это также приказ от генерала. Консенсус был достигнут. Данный метод, основанный на принятии решений на основе решений двух третей других участников и называется «Византийская отказоустойчивость» (BFT). 

BFT-алгоритм в сети Free TON

Алгоритм BFT необходим для достижения консенсуса всех участников сети (валидаторов) о включении или транзакций в новый блок или их отклонении в случае ошибки (или злоумышленных действий).

В блокчейне Free TON используется частная версия BFT под названием Catchain. Она была разработана Николаем Дуровым. Его работа, посвященная Catchain, доступна на сайте ton.org, где Telegram публиковал файлы и документацию TON. Подробное описание алгоритма консенсуса Catchain смотрите на сайте для разработчиков Free TON.

Этапы достижения консенсуса в Catchain:

  1. Выбор валидаторов на основе размера доли (стейка), то есть количестве монет, которые валидатор задействует для производства блоков.
  2. Начало процесса верификации.
  3. Несколько раундов производства блока.

В каждом раунде несколько валидаторов автоматически выбираются для производства блоков, а один валидатор отвечает за голосование о генерации блока. Вес голоса каждого участника пропорционален размеру стейка — чем больше число монет, тем больше голос. Время каждого раунда ограничено. Для децентрализации работы каждый раунд валидаторы меняются ролями.

В течение каждого раунда валидаторы:

  1. Обмениваются сообщениями о возможных блоках («кандидатах»).
  2. Проверяют их.
  3. Выбирают «кандидатов».
  4. Голосуют за выбор одного из них путем подписей своими приватными ключами.

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

Если претендующий блок получает по крайней мере две трети всего «веса» голосов, он принимается в данном раунде и добавляется в общую цепь. Если две трети голосов не отданы за какого-то «кандидата» в назначенное время, происходит новое голосование. Влияние злоумышленников на голосование исключено, пока их «вес» в голосовании составляет менее одной трети.

В результате достижения консенсуса появляется новый блок в блокчейне Free TON.

Сравнение Catchain с другими BFT-алгоритмами

Алгоритм BFT применяется и в других (но не во всех) PoS-сетях. Близкими к Catchain в этом отношении являются PBFT (Practical Byzantine Fault Tolerance), Tendermint и Algorand.

PBFT. Старший из этого списка, алгоритм PBFT был описан в 1999 году Мигелем Кастро и Барбарой Лисков. В нем лидер меняется в ходе процесса достижения консенсуса только, если плохо работает. В Catchain лидер меняется каждый раунд случайным образом. Кроме того, в PBFT все ноды обмениваются сообщениями между собой, тогда как в Catchain число сообщений намного меньше: исходящее сообщение передается только небольшой группе соседей, которые рассылают их дальше.

Tendermint. Этот алгоритм наиболее близок к Catchain по сравнению с остальными. В нем «лидирующая» нода также меняется каждый раунд. Но если ноды в Tendermint используют локальное время для вычисления таймаутов, в Catchain они синхронизированы по единому глобальному времени. В обоих сетях используется Gossip-протокол для распространения сообщений.

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