«Алгоритмы консенсуса»: Подтверждение доли и доказательство работы
«Как узлам сети достичь одинаковой точки зрения на журнал транзакций блокчейна в распределенной сети при условии, что произвольные узлы могут «падать» или зависать, руководствуясь лишь общими правилами обработки сообщений в сети?»
О том, как достигается консенсус в блокчейнах, мы поговорим в нашем сегодняшнем материале.
/ изображение jgbarah CC
Структура и узлы блокчейн-сетей
В любой блокчейн-сети передаются два основных типа сообщений — транзакции и блоки (которые, в свою очередь, являются списками транзакций). Транзакции формируются участниками системы и их алгоритм консенсуса не касается: для того чтобы инициировать, скажем, отправку биткойнов, никакого соглашения не надо, достаточно знать правильный ключ. Блоки — совсем другое дело. Они являются основным продуктом алгоритма консенсуса и определяют, в каком порядке транзакции будут включены в журнал транзакций.
Зачем нужны эти сложности? Оказывается, без согласования между узлами сети возможна повторная трата средств (double spending). Предположим, у Евы есть 1 биткойн. Она может сформировать две транзакции, согласно которым этот биткойн переходит Алисе и Бобу. Если Алиса и Боб никак не согласовывают свою историю транзакций, они оба примут платеж Евы, поскольку транзакции будут подписаны электронной подписью Евы, а до выполнения транзакции у Евы действительно был этот биткойн! Поэтому участникам сети нужно согласовывать журналы транзакций. Тогда успешно выполнится только одна из транзакций Евы, а вторая станет некорректной — средства Евы будут уже потрачены.
Можно ли обойтись без блоков, включая транзакции в журнал по отдельности? Теоретически да, но на практике блоки экономят объем трафика и вычислительные ресурсы узлов сети. Кроме того, у них есть и другие преимущества в контексте конкретных алгоритмов консенсуса — оказывается, что со слишком частыми блоками работа блокчейна становится нестабильной.
Блоки создаются особой категорией узлов сети блокчейна — так называемыми узлами консенсуса. В случае биткойна и других криптовалют эти узлы называют майнерами, поскольку они вознаграждаются за свою работу (майнинг) генерацией новых порций криптовалюты. Майнеры активно участвуют в формировании блокчейна, постоянно группируя входящие транзакции в блоки и распространяя их по сети.
Второй тип — узлы аудита. Они не участвуют в процессе консенсуса, однако имеют у себя полную копию блокчейна. «Аудиторы» регулярно проверяют работу майнеров и занимаются распределением нагрузки по сети, выполняя функцию своеобразной сети доставки контента (CDN) для данных блокчейна.
Третий тип узлов — это легкие клиенты. Легкими они называются потому, что не имеют полной версии блокчейна и содержат лишь те данные, которые важны для узла. По этой причине они являются хорошим вариантом для организации криптовалютного кошелька — всей картины сети такой клиент не даст, но позволит эффективно отслеживать баланс пользователя. Легкие клиенты требуют меньше вычислительных ресурсов и объемов памяти, поэтому могут работать на мобильных платформах.
Биткойн-блокчейн является одним из крупнейших блокчейнов. По данным сайта bitnodes, 8 апреля 2017 года в биткойн-сети наблюдалось 7025 узлов с полной копией блокчейна. Большая часть из них — это узлы аудита; продуктивных майнеров в сети не так уж много — несколько десятков. Отметим, что количество узлов в несколько раз меньше числа участников сети биткойн (которых более 13 миллионов). Так получается потому, что пользователи не обязаны хранить локальную копию блокчейна для отправки транзакций — достаточно хранить закрытые ключи, при помощи которых транзакции подписываются.
Консенсус
Задача распределенного консенсуса не специфична для блокчейнов и имеет хорошо проверенные решения для многих других распределенных систем (например, баз данных NoSQL). Даже задача консенсуса, в котором узлы могут вести себя «по-плохому», — задача византийского консенсуса — впервые была сформулирована в 80-х годах прошлого века, а методы её решения появились в конце 90-х.
Но биткойн и другие блокчейны от предыдущих наработок отличаются условиями работы сети. В обычных алгоритмах византийского консенсуса у узлов сети есть «личности», выражаемые через цифровые подписи или сходные криптопримитивы, а сам список узлов известен заранее или меняется редко, но предсказуемо. В биткойн-блокчейне все наоборот.
Участники сети не только заранее неизвестны, но и могут свободно подключаться или отключаться от сети. При этом блокчейн, являясь децентрализованной системой, имеет определенные свойства: устойчивость к цензуре (никто не может запретить майнить криптовалюту) и объективность (для определения текущей версии журнала транзакций не нужно доверие неким авторитетным источникам — корень доверия находится в самом блокчейне).
Из-за этого обычные алгоритмы византийского консенсуса для блокчейна не подходят. Поэтому было предложено множество различных алгоритмов, среди которых выделяются две основные категории: алгоритмы на основе доказательства работы (proof-of-work) и алгоритмы на основе подтверждения доли (proof-of-stake).
Доказательство работы — PoW
Доказательство работы было «изобретено» задолго до биткойна еще в начале 90-х и применялось в ином контексте: для защиты от спама. Например, один вариант доказательства работы (Hashcash) был предложен английским криптографом Адамом Бэком (Adam Back), который сейчас является генеральным директором одного из крупнейших блокчейн-стартапов.
В случае доказательства работы хеш сообщения, объединенного со специальным полем (nonce), должен быть меньше определенного значения (или начинаться с определенного числа нулевых битов). Nonce не несет смысла для самого сообщения — это поле перебирается автором доказательства, пока не будет найдено подходящее значение. Название «доказательство работы» отражает тот факт, что для нахождения nonce надо совершить вычислительную работу, ожидаемое количество которой измеримо. Например, если нужно, чтобы первые 16 бит хеша равнялись нулю, то в среднем нужно перебрать 65536 значений nonce.
Проиллюстрировать это можно с помощью программы на Python:
import itertools
from hashlib import sha256
# Интерпретирует последовательность символов как little-endian число
to_long = lambda x: sum(ord(b) << (8*i) for i, b in enumerate(x))
# Комбинирует nonce и сообщение для вычисления хэша.
combine = lambda nonce, msg: str(nonce) + ":" + msg
# Проверяет доказательство работы
def verify_pow(msg, nonce, difficulty):
h = sha256(combine(nonce, msg)).digest()
# Равны ли первые difficulty битов хеша нулю?
return to_long(h) % (1 << difficulty) == 0
# Создает доказательство работы для сообщения
def create_pow(msg, difficulty):
for nonce in itertools.count(0):
if verify_pow(msg, nonce, difficulty): return nonce
msg = "blockchain"
nonce = create_pow(msg, 16)
combine(nonce, msg), sha256(combine(nonce, msg)).hexdigest()
#43952:blockchain 000027b5022f88d2da21bd2802268966050f5a0b031058ce4562939c13727303Уточнение насчет ожидаемого количества работы является важным. Теоретически, при сильном везении, подходящий nonce можно найти очень быстро. Если программу выше запустить с сообщением «Bl0Ckchain», то получится, что значение nonce равняется 6571, а это в десять раз меньше ожидаемого. Поэтому, глядя на доказательство работы, можно лишь оценить затраченные на него ресурсы, однако для высокой сложности доказательства (то есть ожидаемого количества выполненной работы) эта оценка будет достаточно точна.
Доказательство работы похоже на цифровые подписи — оно обеспечивает целостность сообщения, так как вероятность того, что один и тот же nonce подойдет для различных сообщений, очень мала. Доказательства также легко проверяются — достаточно провести лишь одну операцию хеширования. В отличие от подписей, создание доказательства работы не требует знания секретов, но «потребляет» больше вычислительных ресурсов. Например, в приведенной выше программе на создание доказательства работы для сообщения «blockchain» сложностью 32 бита требуется несколько часов вычислений на обычном персональном компьютере, однако проверяется это доказательство практически мгновенно.
sha256("5263268363:blockchain") = 000000007cf39dfc8fccae534b39b5f362c16891abca02d0e7b1dbd5a129ee17PoW и консенсус
Использование PoW для консенсуса — пожалуй, самая большая инновация оригинальной статьи о биткойне. Соответствующий алгоритм консенсуса получил вполне академическое название — консенсус Накамото. Сатоши (автор или авторы статьи) предложил «подписывать» каждый создаваемый блок доказательством работы, сложность которого зависит от общей вычислительной сложности сети биткойна. Такой подход дает несколько преимуществ:
- Консенсус Накамото решает главный бич анонимных сетей — атаки Сибиллы, в которых злоумышленник создает кучу фейковых узлов, чтобы «задавить» получившимся большинством мнение честных пользователей. Чтобы обладать мнением в консенсусе Накамото, нужно обладать реальной вычислительной мощностью, которую нельзя подделать, и которая не требует никакой дополнительной аутентификации — она сама по себе привязывает узлы к реальному миру.
- Доказательство нельзя подделать и «перенести» на другие блоки. Таким образом, майнеры не могут воровать доказательства друг у друга.
- Более того, доказательства нельзя заготовить впрок — в каждый блок входит ссылка на предыдущий, поэтому начать работать над доказательством можно только после появления предыдущего блока в сети.
- Доказательства работы обеспечивают честность — награда каждого майнера пропорциональна его вычислительной мощности (хешрейту). Если у майнера есть 10% хешрейта от всей сети, то он будет в среднем создавать 10% блоков и получать 10% награды.
- Поскольку на создание доказательства тратятся реальные ресурсы (которые в случае биткойна измеряются тысячами долларов в минуту), у майнеров возникает совершенно новый стимул действовать в рамках протокола — нечестное поведение немедленно лишает их реальных денег.
Доказательства работы используются узлами биткойна для определения состояния системы. Актуальный журнал транзакций определяется как цепочка блоков с наибольшей суммарной сложностью доказательств работы. Майнеры, соответственно, должны искать блок поверх этой цепочки. Но, теоретически, никто не запрещает создавать новые блоки на основе какого-то старого блока (иногда случаются расщепления — форки — блокчейна, потому что два майнера находят новый блок практически одновременно). Однако намеренные форки невыгодны экономически, потому что блоки из побочных ветвей блокчейна никем не учитываются и не приносят их создателям никакой прибыли — одни затраты на нахождение доказательства работы.
Консенсус Накамото обеспечивает два ключевых требования к блокчейну, которые мы выделили ранее. Из-за того, что доказательство работы не привязывается к личностям майнеров (в отличие от цифровых подписей/сертификатов), обеспечивается устойчивость к цензуре. А за счет того, что доказательства работы быстро проверяются и не требуют для проверки ничего, кроме блокчейна, достигается объективность протокола.
Консенсус Накамото устойчив к атакам на сеть блокчейна, причем его безопасность достаточно хорошо исследована теоретически (в отличие от более новых предложений для блокчейнов). В оригинальной статье отмечено, что сеть биткойна продолжит адекватно функционировать, даже если половина майнеров начнет злонамеренную активность. Если же среди майнеров появится злонамеренное большинство (так называемая атака 51%), они смогут игнорировать блоки от всех остальных майнеров, чтобы забрать себе всю награду в сети, или, например, мошенничать, производя повторную трату средств за счет намеренных форков блокчейна. Однако при этом отметим, даже если все майнеры в сети сговорятся, они не смогут обойти базовые механизмы безопасности биткойна — например, не смогут похитить биткойны пользователей.
Биткойн — самая мощная сеть, использующая доказательство работы. За одну секунду майнеры биткойна вычисляют более трех квинтиллионов (3∙1018) хешей. 32-битное доказательство (которое вычисляется на компьютере несколько часов) — это минимальная сложность в биткойне, которую можно было наблюдать лишь в самом начале работы сети. Это связано с тем, что сложность доказательства автоматически регулируется так, чтобы биткойн-сеть находила в среднем один блок в 10 минут. При увеличении хешрейта сети растет и сложность — сейчас сложность одного доказательства составляет около 70 бит. Соответственно, hex-запись хеша блока должна начинаться с 17 нулей.
Альтернативы для PoW
У консенсуса Накамото есть свойство, которое многими воспринимается как большой недостаток, — для обеспечения безопасности нужно «работать», то есть производить доказательства работы. Вычисления, которые выполняются в рамках PoW, не служат никакой полезной цели, и это архитектурная особенность. Оказывается, очень сложно придумать доказательство работы, которое бы выполняло общественно полезную роль. Поэтому может показаться, что ресурсы (прежде всего, электричество) на майнинг тратятся впустую (если не считать, что они тратятся на обеспечение безопасности).
Помимо этого, майнинг все же подвержен проблеме централизации. Более 70% хешрейта биткойна на данный момент находится в одной стране — Китае. Многие криптовалюты пытаются децентрализовать майнинг за счет использования доказательств работы, которые экономически невыгодно вычислять на специализированном оборудовании, однако с таким подходом возникает другая проблема — если сделать выгодным майнинг биткойнов с помощью домашних компьютеров, то арендовать оборудование для атаки (или создать для нее ботнет) станет существенно дешевле и проще.
Пытаясь решить эти проблемы, сообщество предлагает множество алгоритмов консенсуса, которые не требуют «работы». Самая популярная категория таких алгоритмов основана на доказательствах доли (proof-of-stake, PoS). Доказательство доли похоже на доказательство работы, только вместо совершения определенной работы автор показывает, что у него есть доля в системе (например, в виде ненулевого баланса криптовалюты). Получается, что для майнинга с PoS достаточно «запастись» криптовалютой, после чего просто получать с нее «проценты».
Однако у доказательства доли есть неприятный недостаток в сравнении с PoW: поскольку доказательства доли базируются не на реальном мире (вычислительная мощность), а на чём-то внутри самого блокчейна (баланс криптовалюты), задача построения надежного PoS-алгоритма оказывается нетривиальной.
В простейших вариантах PoS-консенсуса возникают проблемы с базовыми свойствами. Оказывается, что в них самым экономически выгодным поведением является размножение форков блокчейна для повторной траты средств. Были созданы более сложные варианты доказательства доли, без явных дыр в безопасности; такие алгоритмы возвращают в консенсус фактор экономической ответственности за счет обязательного залога, который конфискуется в случае некорректного поведения участника.
У криптографического сообщества все еще остаются сомнения насчет возможности надежных алгоритмов с доказательством доли. Возможно, планируемый переход на доказательство доли блокчейна Ethereum — второго по объему рынка публичного блокчейна — расставит все точки над i.
Кроме доказательства доли, блокчейн-энтузиасты экспериментируют и с другими алгоритмами «proof-of-*». Например, Брэм Коэн (Bram Cohen), создатель протокола BitTorrent, недавно предложил использовать для консенсуса в блокчейнах доказательство локального хранения файлов (proof-of-space), то есть заменить вычислительную мощность в PoW на дисковое пространство. Однако по степени зрелости подобные инициативы еще сильнее отстают от алгоритмов доказательства работы, чем proof-of-stake.
P.S. А вот еще небольшая подборка наших материалов:
- Подтверждение доли и доказательство выполнения работы (PoS vs PoW)
- Безопасность в блокчейне — почему это важно?
- Механизмы вознаграждения в контексте безопасности биткойна
- Недостающее звено интернета: 5 фактов о биткойн-блокчейне, которые должны знать все
