HotStuff и линейный BFT

PBFT - первый практический BFT-алгоритм - работает при 20 нодах. При 100 нодах он генерирует 10 000 сообщений на каждую фазу, а при смене сбойного лидера запускает отдельный протокол ещё тяжелее. В 2018 году команда VMware Research (по заказу Facebook для проекта Libra) задалась вопросом: можно ли сделать BFT с линейной коммуникацией, где смена лидера стоит столько же, сколько обычный раунд? Результат - HotStuff: протокол, который масштабируется до сотен валидаторов и адаптируется к реальной скорости сети.

• **Aptos** (наследник Meta Diem) использует AptosBFT на базе HotStuff - 160 000+ tx/s при 100 валидаторах с finality менее 1 секунды
• **Flow** (блокчейн от Dapper Labs, создатели CryptoKitties и NBA Top Shot) построен на варианте HotStuff с разделением ролей между нодами
• **Sui** (от Mysten Labs, бывшая команда Diem) использует Narwhal + Bullshark - DAG-расширение идей HotStuff для параллельного упорядочивания транзакций

Предварительные знания

• BFT Consensus: PBFT and variants

Three-phase voting и chained QC

В классическом PBFT блок проходит через три фазы: **pre-prepare**, **prepare**, **commit**. HotStuff переосмысливает этот процесс: каждая фаза завершается формированием **Quorum Certificate (QC)** - криптографического доказательства, что более 2/3 валидаторов проголосовали «за».

Три фазы HotStuff: 1. **Prepare** - лидер предлагает блок, валидаторы голосуют. Результат: `prepareQC` - доказательство, что блок принят к рассмотрению. 2. **Pre-commit** - лидер рассылает `prepareQC`, валидаторы подтверждают. Результат: `precommitQC` - блок «заблокирован» (locked), валидаторы не будут голосовать за конфликтующий блок в этом раунде. 3. **Commit** - лидер рассылает `precommitQC`, валидаторы финализируют. Результат: `commitQC` - блок необратимо зафиксирован.

Почему нельзя обойтись двумя фазами? Представьте: лидер раунда 5 предложил блок B, валидаторы проголосовали в фазе Prepare. Лидер упал, приходит новый лидер раунда 6. Он не знает, сколько валидаторов уже «залочились» на блок B. Если он предложит конфликтующий блок B', часть сети может финализировать B, а часть - B'. **Фаза Pre-commit** гарантирует, что перед финализацией все честные ноды явно подтвердили блокировку - и новый лидер может это проверить.

**Chained QC** - ключевая инновация. Каждый QC ссылается на предыдущий, образуя цепочку: `prepareQC → precommitQC → commitQC`. Это позволяет новому лидеру восстановить полную картину, просто получив последний QC - не нужно опрашивать всех валидаторов заново.

Лидер, O(n) и threshold signatures

Главная боль PBFT - **квадратичная сложность коммуникации**. В фазе prepare каждый валидатор отправляет своё сообщение **каждому** другому. При 100 валидаторах это `100 × 99 = 9 900` сообщений за одну фазу. При 1000 валидаторах - почти **миллион**. Именно поэтому PBFT на практике не масштабируется дальше ~20 нод.

В HotStuff коммуникация построена по схеме «звезда»: **лидер** раунда - центральный узел. Валидаторы отправляют голоса **только лидеру**, лидер агрегирует их в QC и рассылает результат обратно. Вместо `O(n²)` сообщений - `O(n)`: n голосов к лидеру + 1 broadcast от лидера.

Но есть проблема: если каждый валидатор отправляет отдельную подпись, QC будет содержать n подписей. Проверка n подписей - снова `O(n)` для каждой ноды. Решение - **threshold signatures**.

**View change** - смена лидера при его отказе - главное преимущество HotStuff перед PBFT. В PBFT view change - отдельный тяжёлый протокол с `O(n²)` сообщениями. В HotStuff view change **встроен** в обычный раунд: новый лидер просто начинает новый раунд, собирая последние QC от валидаторов. Стоимость: `O(n)` - как обычный раунд.

Pipelining: совмещение фаз

Три фазы для каждого блока - это три раунда коммуникации. При latency 100 мс между нодами, каждый блок финализируется за ~300 мс. Можно ли быстрее? Да - через **pipelining**: совмещение фаз разных блоков в одном раунде.

Идея pipelining: когда лидер предлагает новый блок `B_{k+1}`, этот блок одновременно служит **голосом за pre-commit блока `B_k`**. Следующий блок `B_{k+2}` - голос за commit блока `B_k` и за pre-commit блока `B_{k+1}`. Каждый новый блок продвигает предыдущие блоки по конвейеру.

В Chained HotStuff лидер **ротируется каждый раунд**. Лидер раунда k предлагает блок, собирает голоса и формирует QC. Лидер раунда k+1 включает этот QC в свой новый блок - тем самым «проталкивая» предыдущие блоки по конвейеру к финализации.

**Цена pipelining**: финализация блока всё ещё требует 3 раунда (three-chain), но **throughput** возрастает: после «разогрева» конвейера каждый раунд финализирует один блок. Latency для отдельного блока не уменьшилась, а вот пропускная способность выросла втрое.

Optimistic responsiveness

Классические BFT-протоколы привязаны к **таймаутам**. Валидатор ждёт фиксированное время (например, 5 секунд), и если не получил сообщение - считает лидера сбойным. Проблема: timeout нужно выбирать с запасом, потому что сеть непредсказуема. Результат - протокол работает со скоростью таймаута, а не со скоростью сети.

HotStuff вводит свойство **optimistic responsiveness**: при честном лидере скорость протокола определяется **реальной задержкой сети** (actual network delay, δ), а не заранее установленным таймаутом (Δ). Если сообщения доставляются за 50 мс - блок финализируется за ~150 мс (3 × 50 мс). Если за 10 мс - за 30 мс.

**Aptos** (наследник Diem) использует AptosBFT - оптимизированный HotStuff. В бенчмарках 2024 года Aptos показывал **160 000+ tx/s** при 100 валидаторах с finality ~0.9 секунды. Для сравнения: Tendermint (Cosmos Hub) - ~10 000 tx/s при ~6 секундах finality.

Ключевые идеи

• **Three-phase voting** с chained QC: Prepare → Pre-commit → Commit. Фаза Pre-commit решает проблему безопасной смены лидера, которую двухфазные протоколы решить не могут
• **Лидер-центричная звезда** вместо all-to-all: коммуникация `O(n)` вместо PBFT `O(n²)`. Threshold signatures (BLS) агрегируют n подписей в одну, делая QC компактным и быстро проверяемым
• **Pipelining**: три блока в полёте одновременно. Каждый новый блок - голос за предыдущий. Throughput: 1 финализация за раунд в устоявшемся режиме
• **Optimistic responsiveness**: при честном лидере скорость = реальная задержка сети (δ), а не таймаут (Δ). View change стоит O(n) - как обычный раунд, а не отдельный тяжёлый протокол
• Помните 10 000 сообщений PBFT при 100 нодах из начала урока? HotStuff сжимает это до ~200 сообщений за фазу, а смену лидера делает такой же дешёвой, как обычный раунд. Именно поэтому проекты уровня Aptos и Flow выбрали HotStuff, а не PBFT

Связанные темы

HotStuff - эволюция BFT-консенсуса, стоящая между классическим PBFT и современными гибридными протоколами:

• BFT-консенсус: PBFT и варианты — HotStuff решает главную проблему PBFT - квадратичную коммуникацию и тяжёлый view change - сохраняя BFT-гарантии safety и liveness
• Tendermint и Cosmos консенсус — Tendermint - timeout-based BFT с двумя фазами. HotStuff добавляет третью фазу для безопасного view change и optimistic responsiveness вместо привязки к таймаутам
• Gasper: консенсус Ethereum 2.0 — Gasper объединяет Casper FFG (finality) и LMD-GHOST (fork choice) - гибридный подход, в то время как HotStuff - чистый BFT с линейной коммуникацией

Вопросы для размышления

• HotStuff полагается на лидера для агрегации голосов. Если лидер - единая точка отказа, не делает ли это протокол уязвимым к целенаправленным DDoS-атакам на текущего лидера? Как можно защититься от этого?
• Aptos заявляет 160 000 tx/s, а Cosmos Hub - около 10 000 tx/s. Насколько эта разница обусловлена выбором консенсуса (HotStuff vs Tendermint), а насколько - другими факторами (execution engine, параллелизм, аппаратные требования)?
• DAG-based протоколы (Narwhal, Bullshark) развивают идеи HotStuff, убирая единого лидера. Если можно обойтись без лидера - зачем HotStuff его вводил? Какой компромисс выбирают DAG-протоколы?

Связанные уроки

• dist-10-byzantine