Проблемы криптовалют: proof-of-stake и доказательство хранения

B продолжении цикла статей «Проблемы криптовалют» автор Виталик Бутерин (сооснователь Bitcoin Мagazine и проекта Ethereum) рассматривает основные вопросы, стоящие сейчас перед криптовалютным сообществом, и возможные направления развития биткойна и криптовалют в целом.

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

8. Proof of Stake

Еще один подход к решению проблемы централизации майнинга — устранить майнинг полностью, предложив другой механизм расчета веса узла в консенсус-сети. Самая популярная альтернатива сегодня это «proof-of-stake» (PoS), где вместо изначальной формулы «один процессор — один голос» используется формула «одна единица валюты — один голос».

Простейший PoS-алгоритм требует от майнера, чтобы тот подписал новый блок приватным ключом, соответствующим адресу, на котором лежат его монеты. Блок считается валидным, если sha256(PREVHASH + ADDRESS + TIMESTAMP) <= 2^256 * BALANCE / DIFFICULTY, где PREVHASH — хэш предыдущего блока, ADDRESS — адрес автора подписи с балансом BALANCE, TIMESTAMP — текущее время в секундах в эпохе Unix, DIFFICULTY — изменяемый параметр, используемый для настройки частоты успешных подписей. На первый взгляд, этот алгоритм удовлетворяет базовым требованиям: каждый майнер обладает некоторой случайной вероятностью успеха за единичный отрезок времени, а майнер, обладающий вдвое большим количеством монет в кошельке, удваивает свои шансы.

Тем не менее, этот алгоритм обладает серьезной уязвимостью, известной как «nothing-at-stake». В случае раздвоения блокчейна, неважно, случайно или в результате злонамеренной атаки с целью «переписать историю» и обратить подтвержденную транзакцию, оптимальной стратегией для каждого майнера будет продолжать майнить для обеих цепочек, чтобы получить награду вне зависимости от того, какая из них победит. Таким образом, предполагая наличие большого количества экономически заинтересованных майнеров, злоумышленник может отправить транзакцию в обмен на цифровой товар (обычно другую криптовалюту), получить товар, начать альтернативную цепочку от блока, предшествующего блоку с подтверждением транзакции, и послать те же деньги себе. Такая атака может увенчаться успехом, даже если злоумышленник контролирует всего 1% от общего количества криптовалюты, потому что остальные майнеры будут майнить для обеих ветвей одновременно, а злоумышленник — только для своей.

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

Алгоритм Slasher, реализованный Заком Хессом (Zack Hess), представляет мою собственную попытку решения проблемы proof-of-stake. Ключевая идея состоит в том, что:

1. майнеры для каждого блока определяются заранее, поэтому в случае форка майнер сможет либо майнить на всех ветках одновременно, либо не майнить ни на одной;
2. если обнаружится, что некий майнер подписал два различных блока с одинаковой высотой, эти блоки могут быть лишены вознаграждения.

Этот алгоритм жизнеспособен и эффективен, но он страдает от двух недостатков, значимость которых пока не оценена. Во-первых, если все майнеры для данного блока познакомятся заранее, они могут встретиться и вступить в сговор с целью остановить работу сети. Во-вторых, проблема «nothing-at-stake» остается для атак, начинающих форк более чем 3000 блоками раньше настоящего момента. Это не столь существенная проблема, так как такие атаки легко обнаружить; в этом случае можно автоматически выдавать предупреждения.

Более углубленную дискуссию о proof-of-stake читайте в блоге Ethereum.

Задача: создать PoS-алгоритм, решающий проблему «nothing-at-stake» и проблему долгосрочных атак и не вводящий новых рисков, предполагающих совместные действия менее чем 25% обладателей монет.

Дополнительные предположения и требования

• Ожидаемый доход от майнинга должен быть ограничен произведением k на баланс кошелька майнера, для некоторого k, в предположении, что при общем запасе монет у майнеров в эквиваленте 1 миллиарда долларов майнер с монетами в эквиваленте 1000 долларов мог бы майнить с эффективностью не менее 90% от максимально возможной.
• Алгоритм должен предусматривать механизмы борьбы с атаками, описанными выше, как в краткосрочной, так и в долгосрочной перспективе.

9. Доказательство хранения

Третий подход к проблеме — использование ограниченного вычислительного ресурса, а не вычислительной мощности или валюты. Две лучших альтернативы на роль подобного ресурса — память и пропускная способность канала. Принципиально невозможно построить криптографическое доказательство того, что канал предоставлялся или использовался в прошлом, так что этот показатель должен применяться аккуратно, что будет рассмотрено ниже. В отличие от канала, проверка использования памяти может легко быть реализована вычислительно. Преимущества «доказательства хранения» — абсолютная ASIC-защищенность; тип памяти, которые мы используем в жестких дисках сейчас, уже близок к оптимальному.

Простейший алгоритм для доказательства того, что вы обладаете файлом с N блоками — это построить на его основе дерево Мёркле, опубликовать его корень, и для каждых k блоков публиковать доказательство на основе дерева Мёркле для i-го блока, где i — это хэш предыдущего блока по модулю N. Тем не менее, этот алгоритм ограничен, потому что является лишь составной частью возможного решения, но не готовым решением. Для того, чтобы превратить эту идею в криптовалюту, требуется определять, какие файлы хранятся, кто хранит эти файлы, в какой степени и каким образом система будет обеспечивать избыточность, и, если файлы исходят от самих пользователей, как препятствовать оптимизации через сжатие и долгосрочным атакам.

На данный момент последние работы в этой области — проекты Permacoin и Torcoin, решающие некоторые проблемы proof-of-storage с помощью двух идей. Во-первых, пользователи не должны обладать правом выбора, какие файлы им хранить. Напротив, файлы должны выбираться случайно на основании публичного ключа, а пользователи должны быть обязаны хранить все назначенные им файлы под угрозой полного неполучения вознаграждения. Та же идея, используемая в Torcoin в контексте proof-of-bandwidth, предотвращает атаки, при которых пользователь хранит только свои собственные файлы. Во-вторых, цифровая подпись, похожая на подпись Лэмпорта, может использоваться для того, чтобы пользователи хранили свой приватный ключ и хранили свои файлы локально; в результате, загрузка файлов в облако больше не выглядит жизнеспособной стратегией. Это в некоторой степени и обеспечивает избыточность.

Тем не менее, проблема Permacoin заключается в том, что остается непонятным, какие файлы следует хранить; выпуск криптовалюты мог бы теоретически оплачивать работу в эквиваленте миллиардов долларов в год, но не существует единого статического архива, стоимость хранения которого исчислялась бы миллиардами. В идеальном случае, система должна позволять добавлять новые файлы или даже давать пользователям право выгружать собственные, но без создания новых уязвимостей.

Задача: создать валюту, использующую proof-of-storage в качестве механизма консенсуса и распределения.

Дополнительные предположения и требования

• Валюта должна быть способна увеличивать объем хранимых данных; система не должна сломаться, если жесткие диски продолжат становиться дешевле и эффективнее.
• Валюта должна быть максимально полезна. Как минимум, валюта должна позволять людям выгружать собственные файлы и хранить их в сети с минимальным объемом служебных криптографических данных, хотя в идеальном случае валюта должна делать выбор в пользу файлов, являющихся общественным благом, предоставляя обществу ценность в обмен на излишки выпущенной валюты.
• Ожидаемый доход от майнинга должен быть в идеале линейным либо слегка суперлинейным, то есть должен быть ограничен выражением ks/(1-s) для некоторого k, где s — доля майнера относительно всей сети.
• Система должна быть максимально устойчива к централизации майнинг-пулов, возникающей из-за небольшой суперлинейности.
• Система должна быть устойчива к атакам типа «nothing-at-stake» и к долгосрочным атакам.
• Система должна быть устойчива к атакам, в ходе которых злоумышленник убеждает пользователей выгружать в систему специальным образом составленные данные.

По материалам Ethereum wiki. Автор: Виталик Бутерин.

Продолжение следует.