Проблема двойной траты и византийские генералы

Любопытство

1. Если цифровой файл можно скопировать идеально и мгновенно, что мешает потратить его дважды?
2. Как группе незнакомцев, которых ничто не объединяет, договориться о единой истории без лидера, разрешающего споры?
3. Что делает голос в открытой сети ценнее слова другого человека?

Исследование

1. Цифровой токен — это всего лишь файл. В отличие от наличных денег, его можно скопировать бит в бит без затрат и без потери качества. Если Алиса отправляет Бобу десять единиц, у неё остаётся исходный файл, и она может одновременно отправить те же десять единиц Чарли. До 2008 года каждая работающая система цифровых денег зависела от доверенного эмитента: онлайн-схемы проверяли каждый платёж централизованно, а офлайн-схемы могли выявить двойную трату лишь постфактум.
2. В DigiCash Дэвида Чаума каждый получатель вносил монеты в банк, который сверял каждый серийный номер со своим списком потраченных монет. Reusable Proofs of Work Хэла Финни опирались на единственный сервер с открытым кодом на защищённом оборудовании, отслеживавший потраченные токены. В b-money Вэй Дая предлагались серверы, которые вносили залог и могли быть оштрафованы за мошенничество, но эта схема так и не была реализована. В центре каждой из этих конструкций оставалась доверенная сторона или известная группа.
3. В 1982 году Лесли Лэмпорт, Роберт Шостак и Маршалл Пиз формализовали задачу византийских генералов в журнале ACM Transactions on Programming Languages and Systems. Генералы, окружившие город, должны договориться, атаковать или отступать, но некоторые из них — предатели, рассылающие противоречивые сообщения; сами гонцы при этом надёжны. При неподписанных сообщениях согласие возможно, только если предателей меньше трети (n ≥ 3f+1); если их треть или больше, ни один протокол не может его гарантировать.
4. Классические отказоустойчивые протоколы вроде PBFT требуют известного фиксированного набора участников. Это работает для внутренних банковских реестров, но не в открытых сетях, к которым может присоединиться кто угодно. В 2002 году Джон Дусер описал атаку Сивиллы: противник может создавать неограниченное число фиктивных личностей, чтобы размыть голоса честных участников или захватить кворум. В открытой пиринговой сети личности дёшевы и неисчерпаемы, поэтому любую схему, которая подсчитывает личности, может захватить один участник.
5. Whitepaper Сатоши Накамото решает эту проблему напрямую. В его аннотации биткоин представлен как решение проблемы двойной траты без доверенной третьей стороны. Вместо того чтобы полагаться на личности или доверие к институтам, система привязывает каждый блок к накопленному доказательству работы. Голоса взвешиваются по вычислениям, а их нельзя умножить, выдумывая личности; чтобы переписать историю, злоумышленнику нужно превзойти честную сеть по вычислительной мощности.
6. Результат — вероятностная окончательность. В математическом смысле транзакция никогда не становится окончательной навсегда, но с каждым новым блоком, продлевающим цепочку, она становится всё надёжнее. Пока злоумышленник контролирует меньше половины хешрейта, вероятность отмены экспоненциально падает с каждым подтверждением. Этот компромисс допускает теоретическую возможность отмены ради практической неизменяемости без централизованного контроля. Откройте блок-эксплорер и посмотрите, как с каждой новой высотой блока растёт накопленная работа; именно эти накапливающиеся затраты привязывают реестр к физической реальности.

Ключевые факты

Упражнение девять, шесть, три, один

Проверка фактов

Даты, цифры и утверждения были проверены по приведенным ниже опубликованным источникам.

• L. Lamport, R. Shostak, M. Pease, 'The Byzantine Generals Problem', ACM TOPLAS (1982)
• J. Douceur, 'The Sybil Attack', Peer-to-Peer Systems (2002)
• S. Nakamoto, 'Bitcoin: A Peer-to-Peer Electronic Cash System' (2008)
• M. Castro & B. Liskov, 'Practical Byzantine Fault Tolerance', OSDI (1999)