MonadBFT

1 секундаДвухфазный консенсус HotStuff с конвейерным управлением

MonadBFT - это высокопроизводительный механизм консенсуса для достижения согласия относительно упорядочивания транзакций в условиях частично синхронного состояния при наличии византийских акторов. Он является производным от HotStuff с улучшением, предложенным в Jolteon/DiemBFT/Fast-HotStuff, который заключается в сокращении количества раундов с трех до двух путем использования квадратичной сложности связи в случае истечения времени ожидания лидера.

MonadBFT - это конвейерный двухфазный алгоритм BFT с оптимистичной отзывчивостью и линейной сложностью связи в типовом случае и квадратичной сложностью связи в случае истечения времени ожидания. Как и в большинстве BFT-алгоритмов, связь происходит по фазам; на каждой фазе лидер отправляет подписанное сообщение избирателям, которые отправляют подписанные ответы следующему лидеру. Конвейеризация позволяет кворумному сертификату (QC) или сертификату времени ожидания (TC) для блока k присоединяться к предложению для блока k+1.

Краткие факты

Механизм сопротивления Сибиллам
Proof-of-Stake, PoS

Время блока

1 секунда

Окончательность

Одиночный слот

Допускается делегирование

Да

Mempool

См. Общий пул транзакций.

Протокол консенсуса

MonadBFT - это конвейерный механизм консенсуса, который проходит в раундах. Ниже приведено высокоуровневое интуитивное понимание протокола.

Как обычно, допустим, что есть n = 3f+1 узлов, где f - максимальное количество византийских узлов, т.е. 2f+1 (т.е. 2/3) узлов являются невизантийскими. В обсуждении ниже давайте также рассмотрим все узлы как имеющие равный вес доли; на практике все пороги могут быть выражены в терминах веса доли, а не в количестве узлов.

  • На каждом раунде лидер отправляет новый блок, а также либо QC (кворумный сертификат), либо TC (сертификат тайм-аута) для предыдущего раунда.

  • Каждый валидатор проверяет этот блок на соответствие протоколу и, если он согласен, отправляет подписанные голоса YES лидеру следующего раунда. Этот лидер получает QC (кворумный сертификат), агрегируя (посредством пороговых подписей) голоса YES от 2f+1 валидаторов. Следует отметить, что в этом случае коммуникация линейна: лидер отправляет блок валидаторам, а валидаторы напрямую отправляют свои голоса следующему лидеру.

    • В противном случае, если валидатор не получает действительный блок в течение заранее определенного времени, он мультикастит подписанное сообщение о тайм-ауте всем своим сверстникам. Это сообщение о тайм-ауте также включает самый высокий QC, который видел валидатор. Если какой-либо валидатор накапливает 2f+1 сообщений о тайм-ауте, он собирает их (снова посредством пороговых подписей) в TC (сертификат тайм-аута), который он затем отправляет напрямую следующему лидеру.

  • Каждый валидатор завершает блок, предложенный в раунде k, после получения QC для раунда k+1 (т.е. в коммуникации от лидера раунда k+2). Конкретно:

    • Алиса, лидер раунда k, отправляет новый блок всем (вместе с QC или TC для раунда k-1; давайте это проигнорируем, так как это не важно).

    • Если 2f+1 валидаторов голосуют YES за этот блок, отправив свои голоса Бобу (лидеру раунда k+1), то блок в k+1 будет включать QC для раунда k. Однако видеть QC для раунда k в этот момент не достаточно для того, чтобы Валерия, валидатор, знала, что блок в раунде k был зафиксирован, так как (например) Боб мог быть злонамеренным и отправить блок только Валерии. Все, что может сделать Валерия, - это проголосовать за блок k+1, отправляя свои голоса Чарли (лидеру раунда k+2).

    • Если 2f+1 валидаторов голосуют YES за блок k+1, то Чарли публикует QC для раунда k+1, а также предложение блока для раунда k+2. Как только Валерия получает этот блок, она знает, что блок из раунда k (блок Алисы) окончательно зафиксирован.

    • Предположим, что Боб действовал злонамеренно, либо отправив недействительное предложение блока на раунд k+1, либо отправив его менее чем 2f+1 валидаторам. Тогда по крайней мере f+1 валидаторов получат тайм-аут, что приведет к тайм-ауту других невизантийских валидаторов, что приведет к тому, что хотя бы один из валидаторов создаст TC для раунда k+1. Затем Чарли опубликует TC для раунда k+1 в своем предложении (ему придется это сделать, чтобы сделать предложение, потому что для раунда k+1 не будет доступен QC).

    • Мы называем эту процедуру фиксации правилом обязательного подтверждения двух цепей, потому что как только валидатор видит 2 смежных сертифицированных блока B и B', он может подтвердить B и всех его предков.

Ссылки:

Много-подписные BLS

Сертификаты (QC и TC) могут быть наивно реализованы как вектор подписей ECDSA на кривой secp256k1. Эти сертификаты явные и легко строятся и проверяются. Однако размер сертификата линеен по числу подписантов. Это ограничивает масштабирование, потому что сертификат включается в почти каждое сообщение о согласии, кроме сообщения о голосовании.

Парная много-подписная подпись на кривой BLS12-381 помогает решить проблему масштабирования. Подписи могут быть инкрементально агрегированы в одну подпись. Проверка единственной действительной агрегированной подписи обеспечивает доказательство того, что доли, связанные с открытыми ключами, все подписались на сообщение.

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

PreviousКонсенсусNextОбщий пул транзакций (Mempool)

Last updated