Проблема консенсуса: зачем и как

Три человека решают, куда идти ужинать. Один из них всегда врёт каждому разное. Кажется невинной задачей, но в 1982 году Лесли Лэмпорт доказал, что при трёх участниках и одном лжеце согласие невозможно в принципе. Это не вопрос хитрости или алгоритма - это математический закон. Тот же закон определяет, почему биткоин-транзакция подтверждается 60 минут, а Cosmos Hub однажды полностью остановился на полчаса.

• **Bitcoin** обрабатывает 50+ млрд переводов ежемесячно без единого арбитра - Nakamoto consensus позволяет тысячам анонимных нод договариваться, кто кому сколько должен
• **Cosmos Hub (Tendermint)** предпочитает остановку, а не ошибку: в 2023 году сеть замерла на 30 минут при сбое валидаторов - safety важнее liveness
• **Ethereum** после The Merge совмещает оба подхода: продолжает работать при fork (liveness), но через 2 эпохи (~13 мин) даёт экономическую finality с миллиардными штрафами за отмену

Лэмпорт и генералы, которых не было

Лесли Лэмпорт - учёный, более известный как создатель LaTeX и Paxos. Задачу византийских генералов он сформулировал не из интереса к военной истории, а для описания сбоев в компьютерных системах NASA: бортовые компьютеры космических аппаратов должны продолжать работу, даже если один из модулей начинает выдавать неверные данные. Лэмпорт выбрал метафору с византийскими генералами потому, что «предатель» точно описывает поведение сбойного компьютера: он не просто молчит, а активно отправляет ложные данные, причём разные - разным получателям.

Без формализации Byzantine fault tolerance не было бы ни PBFT, ни Tendermint, ни Bitcoin. Лэмпорт дал языковой инструмент для описания проблемы - а это первый шаг к её решению.

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

• P2P networks and gossip protocols

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

Представьте: пять армий окружили крепость. Атаковать можно только **одновременно** - иначе поражение. Генералы обмениваются посыльными, но один из генералов - **предатель**. Он посылает одним «атакуем», другим «отступаем». Как честным генералам договориться?

Это **задача византийских генералов** (Byzantine Generals Problem), сформулированная Лесли Лэмпортом в 1982 году. Она моделирует фундаментальную проблему: как достичь согласия в сети, где **участники не доверяют друг другу** и некоторые из них могут **активно вредить**.

В блокчейне «генералы» - это ноды, «посыльные» - сетевые сообщения, а «предатели» - злонамеренные или взломанные узлы. Каждый раз, когда Bitcoin-нода получает блок, она решает задачу: **этот блок валиден, или узел-отправитель пытается обмануть сеть?**

**Результат Лэмпорта:** задача разрешима, только если предателей **строго менее 1/3** от общего числа генералов. При 3 генералах и 1 предателе - решения **не существует**. Это фундаментальное ограничение, а не недостаток конкретного алгоритма.

Crash Fault vs Byzantine Fault

Не все сбои одинаковы. Сервер может **упасть** (перестать отвечать) - это Crash Fault. Или он может **врать** (отправлять разные ответы разным нодам) - это Byzantine Fault. Разница между ними определяет, сколько нод может выйти из строя.

Почему порог различается? При **Crash Fault** упавшая нода просто молчит - остальные это замечают и игнорируют. При **Byzantine Fault** злонамеренная нода активно обманывает: отправляет узлу A одно значение, а узлу B - другое. Для нейтрализации такой атаки нужно больше «голосов».

**CAP-теорема** (Brewer, 2000) добавляет ещё одно ограничение. Распределённая система не может одновременно гарантировать все три свойства: - **Consistency** - все ноды видят одинаковые данные - **Availability** - каждый запрос получает ответ - **Partition tolerance** - система работает при разрыве сети

В реальных сетях **разрывы (partitions) неизбежны** - кабели рвутся, дата-центры теряют связь. Поэтому на практике выбор всегда между **CP** (консистентность при разрыве) и **AP** (доступность при разрыве). Bitcoin выбрал AP - сеть продолжает работать при разрыве, но могут возникнуть временные fork.

Finality: когда транзакция необратима

Вы отправили 1 BTC и видите подтверждение. Можно ли быть уверенным, что транзакция **никогда** не отменится? Ответ зависит от типа **finality** - гарантии необратимости.

Существует два принципиально разных подхода: **Probabilistic finality** - вероятность отмены уменьшается с каждым новым блоком, но теоретически никогда не достигает нуля. Bitcoin работает именно так. **Deterministic (absolute) finality** - после подтверждения транзакция необратима **математически**. BFT-протоколы (Tendermint, HotStuff) дают такую гарантию.

**Почему именно 6 подтверждений в Bitcoin?** При 10% hashrate у атакующего вероятность отмены после 6 блоков - менее 0.00002%. Это примерно 60 минут ожидания (6 блоков × ~10 мин). Для крупных сумм биржи ждут 12-60 подтверждений.

**Ethereum** после The Merge (2022) перешёл на PoS с «экономической finality»: каждые 6.4 минуты (1 эпоха) валидаторы голосуют за блоки. Через 2 эпохи (~13 минут) блок получает finality - его отмена потребует уничтожения ETH на миллиарды долларов (slashing).

Liveness и Safety: невозможный компромисс

Каждый протокол консенсуса балансирует между двумя фундаментальными свойствами: **Safety** (безопасность): все честные ноды соглашаются на **одно и то же** значение. Нет противоречий, нет fork. «Лучше не принять решение, чем принять неправильное». **Liveness** (живучесть): система **продолжает работать** и принимает новые транзакции. Не зависает, не останавливается. «Система всегда делает прогресс».

В 1985 году Fischer, Lynch и Paterson доказали **FLP impossibility** - один из самых важных результатов в распределённых системах: *В асинхронной сети (где нет гарантированного времени доставки сообщений) невозможен детерминистический протокол консенсуса, который гарантирует и safety, и liveness, если хотя бы одна нода может выйти из строя.*

**FLP impossibility** не означает, что консенсус невозможен! Он означает, что нужно **ослабить** одно из условий: допустить вероятностное решение (Bitcoin), ввести таймауты (PBFT), или предположить частичную синхронность (Tendermint).

**FLP impossibility** - это не абстрактная теорема. Каждый раз, когда вы видите обещание «наш протокол гарантирует и безопасность, и доступность» - ищите скрытые допущения. Обычно это «при условии частичной синхронности» или «если менее 1/3 нод offline».

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

• **Задача византийских генералов** - фундаментальная проблема согласия при наличии предателей. Решение возможно только если честных участников **более 2/3** (для BFT) или **более 1/2** (для CFT)
• **Crash Fault vs Byzantine Fault** - упавший узел (молчит) vs злонамеренный узел (врёт). BFT строже: `3f+1` нод для f сбоев, CFT мягче: `2f+1`
• **Finality** - бывает probabilistic (Bitcoin: вероятность отмены → 0 с каждым блоком) и deterministic (Tendermint: необратимо после кворума 2/3+1)
• **Safety vs Liveness** - FLP impossibility: невозможно гарантировать оба свойства в асинхронной сети. Bitcoin выбирает liveness (работает всегда, но fork возможен), Tendermint - safety (нет fork, но может остановиться)
• Помните задачу с тремя людьми и рестораном из начала урока? Три человека, один лжец - и Лэмпорт доказал, что согласие невозможно. Каждый блокчейн-протокол - это инженерный ответ на этот математический запрет: обойти нельзя, но можно выбрать, чем пожертвовать

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

Консенсус - фундамент, на котором строятся конкретные протоколы:

• P2P-сети и gossip протоколы — Консенсус работает поверх P2P-сети - gossip доставляет сообщения между нодами
• Proof of Work — Nakamoto consensus - решение задачи византийских генералов через вычислительную работу и longest chain rule
• Proof of Stake — Альтернатива PoW: экономическая ставка вместо вычислений, экономическая finality через slashing
• BFT-протоколы — PBFT, Tendermint, HotStuff - конкретные реализации Byzantine Fault Tolerance с deterministic finality

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

• Bitcoin существует 15+ лет и ни разу не нарушил safety (двойная трата в основной сети не произошла). Означает ли это, что probabilistic finality на практике не уступает deterministic? Или мы просто пока не столкнулись с достаточно мотивированным атакующим?
• CAP-теорема заставляет выбирать между consistency и availability при разрыве сети. Если бы вы проектировали систему международных банковских переводов - что бы вы выбрали и почему?
• FLP impossibility доказана для детерминистических протоколов. Bitcoin обходит это ограничение через рандомизацию (PoW - кто первый найдёт хеш). Какие другие способы обхода FLP вы можете придумать?

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

• bc-04-p2p — Consensus is about nodes in a P2P network agreeing; P2P network structure is the prerequisite
• bc-14-pow — Proof of Work is the first concrete consensus mechanism; this lesson provides the abstract foundation
• bc-15-pos — Proof of Stake is the second major consensus family; needs the abstract intro
• bc-16-bft — BFT consensus (PBFT, Tendermint) is the classical consensus family; intro lesson is the prerequisite
• dist-10-byzantine