BFT-консенсус: византийские генералы

Raft держался на доверии: узлы честны, врать не умеют. В публичной сети это наивно, узел будет лгать, если выгодно. Византийский консенсус решает ту же задачу согласия, но против предательства. Разберём задачу византийских генералов, протокол PBFT, его наследников Tendermint и HotStuff, и знаменитую границу в одну треть, ниже которой ложь бессильна, а выше бесполезна любая криптография.

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

Лэмпорт, Шостак и Пиз в 1982 году одели проблему в притчу. Несколько генералов окружили город, у каждого свой отряд, связь только через гонцов. Они должны согласованно атаковать или отступить: вместе атакуют, побеждают; половина атакует, а половина отступила, гибнут. Беда в том, что среди генералов есть предатели, которые шлют одним «атакуем», другим «отступаем», лишь бы расколоть честных.

Византийская отказоустойчивость это и есть способность честных генералов договориться вопреки предателям. Это сильнее crash-модели из прошлого урока: там молчащий узел был худшим случаем, здесь узел активно сеет рознь, причём разную в разные стороны. Кворум большинства Raft тут рушится: предатель голосует за две несовместимые записи сразу, и честное большинство не складывается.

Первый же результат притчи жёсткий: согласие достижимо, только если предателей строго меньше трети. С тремя генералами и одним предателем честные двое уже не могут отличить, кто врёт. Нужен запас, и он выражается формулой.

Оговорка, чтобы дальше не споткнуться. Треть у Лэмпорта это граница для устных сообщений: получатель не может доказать третьему, что именно ему сказали, и предатель врёт безнаказанно. Если сообщения подписаны (гонец несёт письмо с печатью, которую не подделать), в синхронной сети та же статья решает задачу при любом числе предателей: две разные подписанные команды от одного генерала сами изобличают его. Но в честной модели интернета, частичной синхронности, порог в треть возвращается даже с подписями: это результат Дворка, Линч и Стокмайера, о которых ниже. Поэтому PBFT и его наследники подписывают каждое сообщение, а с границей f < N/3 всё равно живут: подписи не отменяют её, они лишь не дают предателю говорить от чужого имени.

А разве это вообще возможно

В уроке про CFT был приговор FLP: в полностью асинхронной сети, где сообщение может опоздать на сколько угодно, детерминированный консенсус невозможен даже с одним падающим узлом. Тем более против предателей. Так на чём же стоят PBFT и его наследники.

На компромиссе. Дворк, Линч и Стокмайер в 1988 году описали модель частичной синхронности. Идея тонкая: безопасность (два честных узла не зафиксируют разные блоки) держится всегда, даже пока сеть штормит и сообщения теряются. А вот живость (сеть в итоге продвинется) обещана только после GST, когда задержки придут в норму. FLP так и обходят: жертвуют не безопасностью, а гарантией скорости. Пока сеть лежит, BFT-цепочка честно встаёт колом и ждёт, лишь бы не расколоться. Этот размен между «никогда не противоречить» и «всегда двигаться» ты ещё увидишь в Tendermint, который выбирает первое.

Граница в одну треть

Вот центральная цифра блока: чтобы пережить f византийских узлов, нужно N ≥ 3f + 1. Не 2f+1, как в Raft, а 3f+1. Откуда лишний f.

В Raft кворум 2f+1 гарантировал, что два большинства пересекаются хотя бы в одном узле, и этот узел не даст принять два разных решения. Но теперь общий узел может оказаться предателем и спокойно подтвердить оба решения. Значит мало одного пересечения, нужно, чтобы в пересечении был хотя бы один честный узел. Считаем: BFT-кворум берут 2f+1. Два кворума по 2f+1 в кластере из N пересекаются как минимум в 2(2f+1) − N узлах. При N = 3f+1 это f+1 узлов, и раз предателей всего f, хотя бы один из пересечения честен. Он и есть свидетель, который не подпишет противоречие. А чтобы кворум 2f+1 вообще набирался при f неотвечающих, нужно N − f ≥ 2f+1, то есть снова N ≥ 3f+1.

Покрути границу: добавляй врущих узлов и смотри, в какой момент безопасность исчезает, а кворум двух третей перестаёт гарантировать честного свидетеля.

всего узлов N: 4врущих f: 1

☠

✓

✓

✓

порог N≥3f+1 терпит: ⌊(N-1)/3⌋ = 1кворум 2f+1: 3честных: 3

Врущих 1 не больше 1. Любой кворум из 3 узлов содержит минимум 2 честных, и два кворума пересекаются по честному узлу: он не подпишет два разных блока. Безопасность цела.

остановить сеть: захватить 2 из 4 (сорвать кворум честных)диктовать историю: захватить 3 из 4 (набрать кворум самому)

Откуда треть. Кворум берут 2f+1. Чтобы он существовал в кластере, где f узлов могут не ответить, нужно N − f ≥ 2f+1, то есть N ≥ 3f+1. Тогда два любых кворума пересекаются минимум в f+1 узлах, и хотя бы один из них честный. Стоит врунам перевалить треть, и это пересечение перестаёт гарантировать честного свидетеля.

Проверка границы руками:

/// Сколько византийских узлов выдерживает кластер размера n: ⌊(n-1)/3⌋.
fn byzantine_tolerance(n: usize) -> usize {
    (n - 1) / 3
}

/// BFT-кворум: 2f+1, при n = 3f+1 это две трети с округлением вверх.
fn bft_quorum(n: usize) -> usize {
    n - byzantine_tolerance(n)
}

fn main() {
    assert_eq!(byzantine_tolerance(4), 1); // 4 узла терпят 1 предателя
    assert_eq!(byzantine_tolerance(7), 2); // 7 терпят 2
    assert_eq!(bft_quorum(4), 3); // нужно 3 из 4 подписей
    assert_eq!(bft_quorum(7), 5); // 5 из 7
    // Минимум для одного предателя это 4 узла, не 3.
    assert_eq!(3 * 1 + 1, 4);
}

Цифра «две трети» (2f+1 из 3f+1) это и есть пресловутый порог 67 процентов, который ты встретишь в Cosmos, Tendermint и proof-of-stake сетях Ethereum. И тут важно различать две совсем разные силы:

• Треть останавливает сеть. Стоит трети голосующей доли замолчать или отколоться, кворум 2f+1 уже не набирается, и честное большинство ничего не финализирует. В Cosmos цепочка просто встаёт (halt) и ждёт. В Ethereum после четырёх эпох без финализации включается inactivity leak: стейк ушедших валидаторов медленно сгорает, пока оставшиеся снова не наберут две трети, и финальность возвращается. Это атака на живость, не на безопасность: историю переписать нельзя, можно только подвесить.
• Две трети диктуют историю. Перевалив две трети, атакующий набирает кворум в одиночку и может зафиксировать два противоречащих блока (двойная трата) или цензурировать кого угодно. Тут уже никакая криптография не спасает: подписи честны, доли просто на стороне врага. Поэтому BFT-сети ценят порог трети дороже половины, ниже которой держатся Raft и Nakamoto.