Чт. Авг 5th, 2021
    BFT, Free TON, Validators

    В основе процедуры формирования блоков блокчейна Free TON лежит консенсус семейства Byzantine Fault Tolerant (BFT) алгоритма Proof-of-Stake (PoS)

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

    Задача Византийских Генералов: удаленный консенсус

    В 1982 году была описана Задача Византийских Генералов. Ее суть в том, что генерал со своими лейтенантами, командующими армиями, должен договориться о нападении на врага или отступлении, то есть прийти к консенсусу.

    Генерал отдает приказ каждому лейтенанту отдельно через гонцов. А лейтенанты обмениваются между собой таким же образом информацией о приказе. Затем каждый лейтенант на основе полученной информации от всех других лейтенантов и генерала принимает решение напасть или отступить. Нюанс задачи заключается в том, что сам генерал или любой лейтенант (или несколько) могут оказаться предателями.

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

    Задача Византийских Генералов для четырех участников

    Рассмотрим частный случай: есть генерал и три лейтенанта. Генерал, Лейтенант 1 и Лейтенант 2 — на одной стороне. Лейтенант 3 — предатель. Таким образом всего четыре участника, условие 3/4 > 2/3 соблюдается.

    Как достигается консенсус в этом случае:

    Шаг 1

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

    Шаг 2

    Лейтенанты обмениваются между собой приказами. 

    Верные лейтенанты (Лейтенант 1 и Лейтенант 2) обмениваются с двумя другими приказом генерала — Y. 

    Предатель, то есть Лейтенант 3 отправляет иное значение (некое Х) Лейтенанту 1 и Лейтенанту 2.

    Шаг 3

    Каждый Лейтенант принимает решение как большинство из полученной информации.

    Лейтенант 1 выбирает из Y от генерала, Y от Лейтенанта 2 и X от Лейтенанта 3. 

    Его решение — Y.

    Лейтенант 2 выбирает из Y от генерала, Y от Лейтенанта 1 и X от Лейтенанта 3. 

    Его решение — Y.

    Лейтенант 3 выбирает из Y от генерала, Y от Лейтенанта 2 и Y от Лейтенанта 3. 

    Так как он предатель, то его решение может быть любым.

    Вывод

    Два лейтенанта из трех принимают одинаковое решение — Y — оно же является приказом генерала. Консенсус достигнут.

    Вышеописанный метод принятия решений на основе преобладающего большинства (больше 2/3) в полученной информации называется Византийская отказоустойчивость.

    Задача Византийских Генералов в алгоритме достижения консенсуса Free TON

    Блокчейн Free TON использует Byzantine Fault Tolerant (BFT) для достижения консенсуса по принятию или отказу в транзакциях.

    Как это происходит во Free TON, какие этапы проходят для достижения консенсуса?

    1. Выбор валидаторов на основании стейка.
    2. Запуск сеанса проверки.
    3. Несколько раундов генерации блока.

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

    В ходе раунда валидаторы:

    • обмениваются сообщениями о кандидатах в блоки;
    • проверяют кандидатов; 
    • выбирают кандидатов для голосования;
    • голосуют за них, подписывая кандидата на блок своими личными ключами.

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

    Если блок получает не менее 2/3 всех весов (отсеченный вес), он автоматически побеждает в конкретном туре голосования и принимается. Если 2/3 голосов за оговоренное время не набрано — раунд пропускается и блок не формируется. Если за несколько раундов согласие так и не достигнуто, новые выборы валидаторов решат эту проблему и консенсус будет достигнут. Невозможно злонамеренное влияние недобросовестных валидаторов, если их меньше 1/3.

    Итогом достижения консенсуса является появление следующего блока в цепочке блоков. А весь описанный процесс достижения консенсуса для Free TON назван алгоритмом Catchain.

    Задача Византийских Генералов: использование в других блокчейнах

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

    • В протоколе PBFT (Practical Byzantine Fault Tolerance) лидер слота меняется в случае неудовлетворительной работы, а в Catchain — каждый раунд.
    • Tendermint протокол наиболее близок к Catchain, но отличается тем, что время для каждого раунда засекается в нем на локальных часах. В Cathain же — глобально синхронизированные часы. 
    • Algorand протокол схож с Free TON, а его отличие выражается в секретном принципе, по которому реализованы выборы валидаторов для голосования.

    ____________________

    Использование во Free TON метода достижения консенсуса Proof-of-stake BFT наряду с распределенной архитектурой блокчейна делают его быстрейшим и одним из самых надежных среди всех аналогов.

    14
    0