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

proof-of-workB продолжении цикла статей «Проблемы криптовалют» автор Виталик Бутерин (сооснователь 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% от максимально возможной.
  • Алгоритм должен предусматривать механизмы борьбы с атаками, описанными выше, как в краткосрочной, так и в долгосрочной перспективе.

trinity

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. Автор: Виталик Бутерин.

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



Categories: Инфраструктура, Криптография, Общество, Теория, Технологии, Футурология, Экономика

Tags:

Leave a Reply

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

Notify of
avatar
trackback
В чём проблема «Proof of Stake»? – Bit•Новости

[…] Процесс майнинга, возможно, слишком расточителен для окружающей среды (в плане расхода электроэнергии) и оправданно беспокоит людей, озабоченных вопросом сохранения окружающей среды. Это главная причина, по которой многие питают надежды относительно альтернативной идеи под названием «Proof of Stake». […]

trackback
Виталик Бутерин победил Цукерберга — EthereumClassic

[…] […]

trackback
Проблемы криптовалют: децентрализованные автономные организации | Bit•Новости

[…] достижения консенсуса в децентрализованной сети (3, 4) и об экономических основах криптоэкономики (5, 6, 7). В […]

trackback
Проблемы криптовалют: метрики | Bit•Новости

[…] достижения консенсуса в децентрализованной сети (3, 4) и об экономических основах криптоэкономики (5, 6). В […]

trackback
Проблемы криптовалют: репутация | Bit•Новости

[…] достижения консенсуса в децентрализованной сети (3, 4) и об экономических основах криптоэкономики (5). В этой […]

Вася
Гость
А у меня возник вопрос насчет долгосрочных атак в системе с PoW (как в биткоине). Современные АСИК’и майнят намного быстрее чем в 2009 г. Сложность майнинга биткоина примерно до 32000 блока оставалась равна 1, т. е. тогда майнил только Сатоши. Я беру например хеш этого 32000 блока и начинаю майнить 32001 блок вставляя там фиктивное время = время 32000 блока + 10 мин. Потом опять майню 32002 блок и вставляю фиктивное время = фиктивное время моего 32001 блока + 10 мин. и т. д. Так с современным АСИКом я быстро дойду например до 2015 г. так как сложность майнинга в… Read more »
at
Гость

Они скажут «Д-давай, досвидания!»

Lerik
Гость

Добавьте еще недавно появившуюся Proof-Of-Capacity технологию, где для доказательства так же используется место на диске, но к сожалению, заполненном заранее подготовленными данными.

Пока единственная, использующая этот принцип, криптовалюта — Burst, форк NXT.

Анонимно
Гость

http://storj.io/
http://maidsafe.net/
Проекты работают в этом направлении.

Анонимно
Гость

Такая атака может увенчаться успехом, даже если злоумышленник контролирует всего 1% от общего количества криптовалюты, потому что остальные майнеры будут майнить для обеих ветвей одновременно, а злоумышленник — только для своей.
Что за бред я сейчас прочитал? Это что, заказная статья из NSA?

Анонимно
Гость

Почините разметку.

Гога
Гость

Виталик Бутерин чувствует отсутствие интереса к своему Ethereum и пытается умничать 🙂

Анонимно
Гость

Отсутствие интереса, говорите? Ооок…

http://www.wtn.net/summit-2014/2014-world-technology-awards-winners

(категория IT SOFTWARE)

Гога
Гость
Поднимать шум и устраивать лекции могут многие. Но сколько раз нужно обмануть доверчивых хомяков, что бы они перестали вкладывать бабло в чьи то теории? 5, 10 а может 100 раз. Потенциал крипто рынка большой и Виталик это прекрасно использует. Но будет ли это работать на практике, большой вопрос. Сейчас он нашел спонсоров на свой проект, но сколько он протянет, до пересмотра и создания более продвинутой концепции? Можно долго создавать новые крипто валюты, комбинируя разные технологии и снова и снова находя спонсоров готовых поверить в новую идею, но рано или поздно поток желающих инвесторов иссякнет. Так лучше наблюдать за этими экспериментами… Read more »
Анонимно
Гость

А в чем проблема? Для PoS так и есть.

Анонимно
Гость

Неправда

at
Гость
Виталик, если ты меня слышишь, ответь — как ты собираешься мотивировать людей использовать свою разработку? Как добьешься сетевого эффекта, чтобы более 10% всех пользующихся деньгами людей перешли на твою разработку? Как? Деньги сами по себе не естественны. Какой бы алгоритм ни использовался, как бы их не майнили, но именно из-за своей неестественности цивилизации использую Насилие для насаждения валют. А Этериуму, как и Биткоину, расчитывающему на Выгоду, нужны иные способы мотивировать людей к своему использованию. Это другая парадигма мышления. Выгодные деньги еще никогда не существовали в таких масштабах. Сможешь ли ты убедить людей использовать свой Этериум чем-то иным, кроме заумных статей… Read more »
Алексей
Гость

Уже тошнит от статей Бутерина. Мне он уже напоминает Мавроди (Бутерин) со своей МММ (Etherium).

Andriy
Гость

В Этериуме транзакции будут стоить очень мало, а не так как в биткоине, может быть, это привлечет сначала поклонников криптовалют, а после и остальное общество, по ходу популяризации криптовалют

Гога
Гость

Также мало как движение дерьма в канализации? )

wpDiscuz