Алгоритмы консенсуса в блокчейне
Одной из самых известных задач о децентрализованном принятии решений является задача византийских генералов. Она звучит следующим образом:
Группа византийских генералов вместе со своими легионами окружили армию врага. Они хотят договориться о времени нападения. Генералы могут общаться, пересылая друг другу сообщения гонцами. Но есть две проблемы:
Часть генералов — предатели, и они будут препятствовать согласованному нападению, распространяя ложную информацию.
Гонцы вынуждены идти через территорию врага, а потому могут быть убиты и не передать сообщение.
Существует ли алгоритм, позволяющий генералам договориться о времени нападения?
Еще в 1982 году был предложен алгоритм, который решает задачу если доля нечестных генералов и недоставленных сообщений достаточно мала. Например, если считать, что гонцы всегда доставляют сообщение, для работы алгоритма достаточно, чтобы доля нечестных генералов была меньше трети.
Задача византийских генералов имеет непосредственное отношение к блокчейну. Напомню, что в децентрализованной системе информация распределена между пользователями.
В сети Биткоин, например, каждый майнер хранит свою локальную версию блокчейна, содержащую все когда-либо совершенные транзакции. При этом для отсутствия форков (разногласий), локальные версии всех майнеров должны совпадать.
Когда один из майнеров предлагает добавить в блокчейн новую информацию, например новую транзакцию, майнерам необходимо прийти к консенсусу (единогласию) о том, какую именно информацию добавлять в свою локальную копию блокчейна.
Это в точности задача византийских генералов, в которой майнеры — это генералы, а новая информация — время нападения. При этом часть майнеров может быть нечестными, а сообщения между майнеры могут не доходить, например, из-за сбоев в сети.
К сожалению, предложенный в 1982 г. алгоритм не работает на практике, поскольку требует огромного количества сообщений между майнерами. Если майнеров 150, количество необходимых сообщений уже превышает количество атомов в обозримой вселенной.
В 2009 году Сатоши Накамото предложил другой алгоритм, который требует гораздо меньшего количества сообщений, но заставляет майнеров совершать работу. Этот алгоритм получил название Proof of Work, и используется в таких блокчейнах как Bitcoin, Litecoin, Monero, ZCash, и многих других.
Что такое Proof of Work? (POW)
PoW (Proof of Work) — Если говорить простым языком, то это механизм в криптовалюте, который подтверждает, что сеть работает честно и безопасно. Он основан на решении сложных математических задач.
Майнеры используют вычислительные мощности для решения математической задачи, относящейся к каждому блоку транзакций. Эта задача может быть решена только путем перебора различных входных данных до тех пор, пока не будет найдено нужное значение. Первый майнер, решивший задачу, передает решение в сеть, а другие майнеры проверяют его, прежде чем добавить блок в цепочку.
Чтобы добавить блок в блокчейн с алгоритмом PoW, майнер должен первым найти достоверный хеш этого блока, применяя для этого вычислительные ресурсы своего устройства. Машины, созданные специально для выполнения этой функции (ASIC), способны вычислять триллионы уникальных хешей каждую секунду.
Шансы добавить блок в качестве одиночного майнера определяются количеством хешей, которые устройство майнера вычисляет в секунду, по отношению к общему количеству хешей, которые каждую секунду вычисляют все машины в сети. Как правило, блоки добываются крупными пулами, объединяющие мощности тысяч устройств участвующих в пуле пользователей.
Но также существует другой алгоритм работы криптовалют, который также набрал популярность благодаря своим потенциальным преимуществам перед PoW, к примеру нашумевший PoS алгоритм о котором мы поговорим в следующей статье.