Алгоритмы консенсуса в блокчейне часть 1

Предлагаем вам к ознакомлению первый из постов цикла принцип DeFi Текст насыщен большим объемом информации, но это того стоит. Именно такие тексты позволяют по-настоящему разобраться в теме.

Одной из самых известных задач о децентрализованном принятии решений является задача византийских генералов. Она звучит следующим образом:

Группа византийских генералов вместе со своими легионами окружили армию врага. Они хотят договориться о времени нападения. Генералы могут общаться, пересылая друг другу сообщения гонцами. Но есть две проблемы:

Часть генералов — предатели, и они будут препятствовать согласованному нападению, распространяя ложную информацию.

Гонцы вынуждены идти через территорию врага, а потому могут быть убиты и не передать сообщение.

Существует ли алгоритм, позволяющий генералам договориться о времени нападения?

Еще в 1982 году был предложен алгоритм, который решает задачу если доля нечестных генералов и недоставленных сообщений достаточно мала. Например, если считать, что гонцы всегда доставляют сообщение, для работы алгоритма достаточно, чтобы доля нечестных генералов была меньше трети.

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

Когда один из майнеров предлагает добавить в блокчейн новую информацию, например новую транзакцию, майнерам необходимо прийти к консенсусу (единогласию) о том, какую именно информацию добавлять в свою локальную копию блокчейна.

Это в точности задача византийских генералов, в которой майнеры — это генералы, а новая информация — время нападения. При этом часть майнеров может быть нечестными, а сообщения между майнеры могут не доходить, например, из-за сбоев в сети.

К сожалению, предложенный в 1982 г. алгоритм не работает на практике, поскольку требует огромного количества сообщений между майнерами. Если майнеров 150, количество необходимых сообщений уже превышает количество атомов в обозримой вселенной.

В 2009 году Сатоши Накамото предложил другой алгоритм, который требует гораздо меньшего количества сообщений, но заставляет майнеров совершать работу. Этот алгоритм получил название Proof of Work, и используется в таких блокчейнах как Bitcoin, Ethereum, Litecoin, Monero, ZCash, и многих других. В следующиих постах Я расскажу, как он работает.