Алгоритм консенсуса - это процедура, которая позволяет нодам сети придти к соглашению по её состоянию.
Существует множество видов алгоритмов консенсуса: Proof-of-Work, Proof-of-Stake, Delegated Proof-Of-Stake, Proof-of-Capacity и многие другие.
Сегодня мы поговорим о самом старом и известном протоколе, использующемся в криптовалютах: Proof-of-Work(PoW) или доказательство работы. Не смотря на то, что появление PoW часто ассоциируют с Биткоином, идея данного алгоритма возникла намного раньше.
Впервые этот алгоритм был описан в работе [1] Синтии Дворк и Мони Наора в 1993 году. Протокол предлагался как механизм противодействия почтовому спаму и требовал от пользователей решения трудоемкой, но выполнимой математической задачи. В своей статье, в частности, Дворк и Наор предложили три подхода, которые могут быть использованы:
- Нахождение квадратного корня по модулю простого числа.
- Подделка подписи Фиата-Шамира с ослабленными параметрами безопасности.
- Подделка подписи Онга-Шнорра-Шамира.
Результаты решения таких задач прилагались к письмам и достаточно легко могли быть проверены получателем. Сам по себе протокол не избавлял систему от возможности рассылки спама, но вычислительные затраты, необходимые для решения таких умеренных по сложности математических задачи, делали спам-рассылку весьма дорогим удовольствием.
Аналогичный подход представил в 1997 году Адам Блэк, в своей системе противодействия спаму - Hashcash. Однако в качестве математической задачи, на которой базировался PoW, была использована частичная коллизия хеш-функции. С хэш-функциями Вы подробнее можете познакомится в этой статье:
То есть, предполагался поиск хэш-значения, у которого бы часть битов совпадало с исходным шаблоном. Задавался шаблон, например, некоторая строка, от которой вычислялось хэш-значение(использовалась функция sha1), и количество бит, которое должно совпасть у искомого хэш-значения с заданным шаблоном. Причем в данном случае можно было усложнять задачу в зависимости от количество выбранных бит совпадения. Чем больше бит, тем сложнее найти подходящее хэш-значение.
В Биткоин сети PoW обеспечивает защиту от атак двойной траты, не позволяя пользователю потратить одни и те же монеты дважды. И именно вариант, предложенный Адамом Блэком, лег в основу алгоритма PoW, что Сатоши Накамото и отмечает в вайтпейпере Биткоина.
В одной из следующих статей мы ещё вернёмся к вопросам, связанным с майнингом и структурой блока. Сейчас же мы вкратце коснемся этих тем, чтобы пояснить как работает PoW.
Для генерации нового блока майнер берёт набор неподтвержденных транзакций. Затем он добавляет к нему заголовок блока, включающий в себя хэш-значение предыдущего блока для связывания его с новым блоком, а также специальное число nonce. Задача майнера заключается в том, чтобы найти хэш-значение от этих данных, удовлетворяющее заданному шаблону. Поиск ведётся посредством перебора и изменения величины nonce. Шаблон представляет из себя некоторое целевое числовое значение и при переборе майнер ищет хэш-значение, которое численно будет меньше заданного целевого шаблона. Поэтому майнер, перебирая различные значения nonce, получает новый заголовок блока и при его хэшировании получает абсолютно новое хэш-значение. Например, как показано ниже, заголовок блока - это Block header 1, где nonce пусть равен 1. Если полученное хэш-значение от этих данных удовлетворяет шаблону, то новый блок добавляется к цепочки блоков Биткоина, и майнер получает награду за проделанную работу и создание нового блока.
Если же полученное хэш-значение не удовлетворяет шаблону, то майнер продолжает перебор, меняя nonce, например на 2 и получая новый заголовок Block header 2.
Этот процесс повторяется до тех пор, пока майнера не найдёт подходящее хэш-значение или пока другой майнер его не опередить. В этом случае ему нужно будет взять новый набор транзакций и повторить весь процесс заново.
На сегодняшний день PoW один из самых используемых и эффективных алгоритмов консенсуса в мире криптовалют. В дальнейшем мы поговорим про других алгоритмы консенсуса, в частности Proof-of-Stake и сравним их с PoW.
[1] Cynthia Dwork and Noni Naor. “Pricing via Processing, Or, Combatting Junk Mail, Advances in Cryptology”. CRYPTO’92: Lecture Notes in Computer Science No. 740. Springer: 139–147.
