Продолжаем переводить крутые статьи с сайта Bytecoin.org. Сегодня — «Alternatives for Proof of Work, Part 2: Proof of Activity, Proof of Burn, Proof of Capacity, and Byzantine Generals» Рэя Паттерсона (Ray Patterson). Часть 1 можно найти тут.
Итак, энергоэффективность Proof of Stake – это палка о двух концах. С одной стороны, энергия-то не тратится, с другой – без этих трат модель распределенного консенсуса выглядит несколько неустойчиво.
Какие еще аргументы можно привести? Против PoS не раз высказывается мнение, что эта схема «делает богатых богаче». И в самом деле: тот, у кого больше всех монет, будет находить больше всех блоков и получать больше всех прибыли, увеличивая число этих монет. На самом деле, в таком виде это обвинение можно высказать и в лицо PoW: тот, кто вложил больше всех денег в железо, будет получать и больший доход, это естественно.
Но картина начинает выглядеть по-другому, если мы говорим о криптовалюте… где PoS начинает работать с первого блока. И используется для эмиссии новых денег. Тот, кто имеет, скажем, 10% от всех монет на старте, будет находить 10% всех блоков, и значит получать 10% эмиссии. То есть, купив вначале 10 монет из 100 возможных, он будет иметь 100 тысяч из миллиона через некоторое время. Неплохая сделка, да?
Как видите, проблема с PoS возникает, когда этого самого ограниченного ресурса – монет – в системе ОЧЕНЬ ограниченное количество. Абсолютные величины становятся гораздо важнее относительных – а ведь модель безопасности блокчейна оперирует именно относительными величинами («половина мощностей сети должна быть под контролем честных участников»).
Кроме того, PoS не решает вопрос о начальном распределении монет. То есть решает – но «нечестно». До сих пор еще не умолкают обвинения в сторону Pure PoS-based валюты NXT, где практически вся денежная масса оказалась в руках нескольких десятков человек.
Вывод таков: чистая PoS система не слишком приспособлена для выживания в дикой среде криптовалют. Но что если скрестить ее с PoW?
Стандартная гибридная схема, совмещающая PoW и PoS, по факту реализована в очень многих клонах PeerCoin, как и в нем самом. Блоки PoW ищутся наравне с блоками PoS, т.е. блокчейн состоит из блоков обоих типов.
Какие преимущества это дает? Во-первых, «переписать историю» уже совсем не так просто, т.е. PoW-блоки могут служить некоторого рода чекпоинтами, если учитывать суммарную сложность работы во всей цепочке. Транзакции, которые включены в блоки с «реальной» работой внушают большее доверия продавцам. Во-вторых, через PoW блоки может производиться «честная» эмиссия новых денег, а PoS рассматриваться как «ежегодный доход от депозита».
Однако проблема с nothing-on-stake все же остается: искать PoS-блоки можно на любой высоте. Возникает идея: использовать в одном блоке одновременно оба подхода, чтобы, так сказать, и накормить Stake-волка, и уберечь электрическую овцу. Мечту об этих электроовцах воплотили в жизнь (пока только на бумаге) в 2014 году Iddo Bentov et al и назвали Proof of Activity (PoA).
В PoA каждый блок является продуктом совместного участия как PoW, так и PoS-майнера. И основной момент здесь в том, что холдеры вступают в игру лишь после того, как некоторая работа произведена PoW-участниками. Иными словами, даже если существует некий владелец 50% монет, то он не может единолично управлять созданием новых блоков. Во-первых, при больших значениях N ему приходится считаться с другими холдерами (если N=3, то вероятность «быть выбранным» единолично – 0.5*0.5*0.5 = 12,5%). Во-вторых, PoW-майнеры могут просто-напросто его игнорировать: то есть «выбрасывать» те заготовки блоков, которые дают возможность «монополисту» подписывать блоки.
Как было сказано, пока PoA остается лишь теоретическим проектом. А жаль…
Конечно же, кроме PoW и PoS предлагались и другие proof-of-choose-your-name: в интернете всегда не хватает доказательств.
Proof of burn работает именно так, как вы и подумали: вместо сжигания электричества нужно уничтожать цифровые монеты. Нет, форматировать жесткий диск не нужно. «Сжигание» происходит путем отправки денег на такой адрес, с которого гарантированно нельзя их потратить. Например, на адрес, который является хэшом случайного числа, – шансы подобрать к нему соответствующий публичный и приватный ключи ничтожно малы.
Итак, избавляясь таким образом от своих монет, вы получаете право на пожизненный майнинг, который тоже устроен как лотерея среди всех владельцев сожженных монет. И, понятно дело, чем больше вы сожгли – тем больше ваши шансы. По сути, это как покупка за монеты виртуального PoW-железа, которое никогда не испортится. Или как PoS-депозит, который уже не вернуть обратно.
Такой способ, как отмечает и сам автор, не подходит для раннего этапа развития криптовалюты. Но хорошо (в том числе и с экономической точки зрения) должен служить «в зрелые годы», когда основная денежная масса уже сгенерирована.
Proof of Capacity представляет собой реализацию популярной идеи «мегабайты как ресурсы». Ничего сжигать-уничтожать не нужно, но необходимо выделить существенный объем дискового пространства, чтобы включиться в майнинг. Помимо энергоэффективности такого решения, есть и другой момент: защита от ботнета. Довольно сложно установить на компьютере жертвы майнер, который бы незаметно отхватил бы пару терабайт.
Алгоритм создает на диске много крупных блоков данных, которые получаются многократным хэшированием из вашего публичного ключа и случайных чисел. Из последнего заголовка блока мы получаем число-индекс, и берем в каждом нашем большом блоке данных небольшой кусочек с эти индексом. Чем больше места выделили – тем больше кусочков у нас есть. Дальше как обычно: хэш от кусочка и последнего заголовка должен быть меньше, чем цель (с учетом текущей сложности). Короче говоря, каждый ваш мегабайт HDD – это дополнительный лотерейный билет в майнинге.
Данная реализация, мягко говоря, не идеальна. Во-первых, в ней остается проблема nothing on stake: вы можете мгновенно пробежаться по всем своим терабайтам, чтобы проверить свои шансы в альтернативной цепочке, как и в случае PoS. То есть одновременно майнить сразу несколько цепочек, не затрачивая лишних ресурсов. Во-вторых, обращения к диску занимают довольно существенное время и, вероятно, эффективнее будет просто генерировать новые chunks на лету с помощью простого ASIC. Тогда мы просто получаем PoW-алгоритм.
Существует также похожая концепция с «мегабайтами» – Proof-of-Storage, но там выделенное место используется всеми участниками как совместное облачное хранилище. Эта идея довольно интересная, но одно ее описание будет слишком велико для данной статьи. Вы можете ознакомиться с дизайном системы на сайте.
Я подозреваю, что существует еще десятки различных proof-of-look-mum-no-hands, о которых мало кто слышал. Возможно, среди них есть свои жемчужины.
В computer science есть задача под названием «Проблема Византиских генералов». Она формулируется так:
Какое отношение это имеет к криптовалютам? Ответ на это дает сам Сатоши: с помощью механизма Proof of work генералы могут справиться с этой задачей (которая, вообще говоря, является довольно сложной на практике – а для двух генералов и вовсе нерешаемой!). По сути, им необходим алгоритм как раз для установления распределенного консенсуса – способ узнать, «как думает большинство», и самому внести свой вклад.
В криптовалюте генералы – это узлы сети, а их сообщения – это цепочка блоков: истинной считается та, что длиннее (точнее, над которой было произведено больше работы). Тут есть одно важное замечание: в модели Сатоши мы получаем вероятностное решение («если атакующий имеет долю хэшрейта x%, то он сможет обмануть сеть с вероятностью y%»), в то время как классическая задача подразумевает детермированный алгоритм. Подробнее о различиях и формальном подходе вы можете прочитать тут.
Сатоши покинул сцену до появления на ней Proof of Stake и других альтернатив, поэтому мы вряд ли узнаем его мнение об их применимости к задаче Византийских генералов. Очевидно, что все не так просто: чистый PoS, как мы видели, не столь безопасен, как чистый PoW (no free lunch). Другие варианты – гибридные протоколы или совсем иные подходы – справляются ли они? Вопрос пока открыт.
PoW vs PoS: что еще?
Итак, энергоэффективность Proof of Stake – это палка о двух концах. С одной стороны, энергия-то не тратится, с другой – без этих трат модель распределенного консенсуса выглядит несколько неустойчиво.
Какие еще аргументы можно привести? Против PoS не раз высказывается мнение, что эта схема «делает богатых богаче». И в самом деле: тот, у кого больше всех монет, будет находить больше всех блоков и получать больше всех прибыли, увеличивая число этих монет. На самом деле, в таком виде это обвинение можно высказать и в лицо PoW: тот, кто вложил больше всех денег в железо, будет получать и больший доход, это естественно.
Но картина начинает выглядеть по-другому, если мы говорим о криптовалюте… где PoS начинает работать с первого блока. И используется для эмиссии новых денег. Тот, кто имеет, скажем, 10% от всех монет на старте, будет находить 10% всех блоков, и значит получать 10% эмиссии. То есть, купив вначале 10 монет из 100 возможных, он будет иметь 100 тысяч из миллиона через некоторое время. Неплохая сделка, да?
Как видите, проблема с PoS возникает, когда этого самого ограниченного ресурса – монет – в системе ОЧЕНЬ ограниченное количество. Абсолютные величины становятся гораздо важнее относительных – а ведь модель безопасности блокчейна оперирует именно относительными величинами («половина мощностей сети должна быть под контролем честных участников»).
Кроме того, PoS не решает вопрос о начальном распределении монет. То есть решает – но «нечестно». До сих пор еще не умолкают обвинения в сторону Pure PoS-based валюты NXT, где практически вся денежная масса оказалась в руках нескольких десятков человек.
Вывод таков: чистая PoS система не слишком приспособлена для выживания в дикой среде криптовалют. Но что если скрестить ее с PoW?
Гибридные системы. Proof-of-Activity
Стандартная гибридная схема, совмещающая PoW и PoS, по факту реализована в очень многих клонах PeerCoin, как и в нем самом. Блоки PoW ищутся наравне с блоками PoS, т.е. блокчейн состоит из блоков обоих типов.
Какие преимущества это дает? Во-первых, «переписать историю» уже совсем не так просто, т.е. PoW-блоки могут служить некоторого рода чекпоинтами, если учитывать суммарную сложность работы во всей цепочке. Транзакции, которые включены в блоки с «реальной» работой внушают большее доверия продавцам. Во-вторых, через PoW блоки может производиться «честная» эмиссия новых денег, а PoS рассматриваться как «ежегодный доход от депозита».
Однако проблема с nothing-on-stake все же остается: искать PoS-блоки можно на любой высоте. Возникает идея: использовать в одном блоке одновременно оба подхода, чтобы, так сказать, и накормить Stake-волка, и уберечь электрическую овцу. Мечту об этих электроовцах воплотили в жизнь (пока только на бумаге) в 2014 году Iddo Bentov et al и назвали Proof of Activity (PoA).
Как работает PoA
PoA работает довольно просто:
Замечания:
- Сначала работает PoW майнер: ищет хэш, удовлетворяющий сложности… все как обычно.
- Найдя такой хэш, он отправляет все данные в сеть, однако это еще не блок, а только «заготовка». Таких заготовок может появиться несколько.
- Хэш блока (256 псевдослучаных бит) интерпретируется как N чисел. Каждому числу однозначно соответствует какой-то сатоши (например, если пронумеровать все эмитированные монетки с первого блока).
- С каждым сатоши, в свою очередь, связан один-единственный публичный ключ его текущего владельца. То есть так мы опеределили N случаных владельцев.
- «Заготовка» блока превращается в полноценный блок, как только все N владельцев поставят свои подписи на этом блоке (теми ключами, которые определены на шаге 4).
- Если кто-то из холдеров (signers) в этот момент недоступен (или не участвует в майнинге по личным соображениям), не беда. PoW-майнеры продолжают свою работу, генерируя все новые «заготовки» с различными наборами холдеров-кандидатов.
- Рано или поздно (в зависимости от процента участников онлайн) какой-то блок будет подписан N раз. Награда за блок распределеяется между PoW-майнером и всеми N холдерами.
Замечания:
- Протокол, очевидно, требует постоянного обмена данными. Чтобы уменьшить трафик, «заготовка» блока не включает в себя список транзакций. Их набирает последний холдер, финализируя блок.
- Если N=3, а онлайн около 10% пользователей, то очевидно, что в среднем PoW-майнеры произведут около 10*10*10 = 1000 «заготовок», пока не будет подписана какая-то одна. Но при размере сообщений порядка сотни байт – это несущественно.
В PoA каждый блок является продуктом совместного участия как PoW, так и PoS-майнера. И основной момент здесь в том, что холдеры вступают в игру лишь после того, как некоторая работа произведена PoW-участниками. Иными словами, даже если существует некий владелец 50% монет, то он не может единолично управлять созданием новых блоков. Во-первых, при больших значениях N ему приходится считаться с другими холдерами (если N=3, то вероятность «быть выбранным» единолично – 0.5*0.5*0.5 = 12,5%). Во-вторых, PoW-майнеры могут просто-напросто его игнорировать: то есть «выбрасывать» те заготовки блоков, которые дают возможность «монополисту» подписывать блоки.
Как было сказано, пока PoA остается лишь теоретическим проектом. А жаль…
Немного экзотики
Конечно же, кроме PoW и PoS предлагались и другие proof-of-choose-your-name: в интернете всегда не хватает доказательств.
Proof of burn работает именно так, как вы и подумали: вместо сжигания электричества нужно уничтожать цифровые монеты. Нет, форматировать жесткий диск не нужно. «Сжигание» происходит путем отправки денег на такой адрес, с которого гарантированно нельзя их потратить. Например, на адрес, который является хэшом случайного числа, – шансы подобрать к нему соответствующий публичный и приватный ключи ничтожно малы.
Итак, избавляясь таким образом от своих монет, вы получаете право на пожизненный майнинг, который тоже устроен как лотерея среди всех владельцев сожженных монет. И, понятно дело, чем больше вы сожгли – тем больше ваши шансы. По сути, это как покупка за монеты виртуального PoW-железа, которое никогда не испортится. Или как PoS-депозит, который уже не вернуть обратно.
Такой способ, как отмечает и сам автор, не подходит для раннего этапа развития криптовалюты. Но хорошо (в том числе и с экономической точки зрения) должен служить «в зрелые годы», когда основная денежная масса уже сгенерирована.
Proof of Capacity представляет собой реализацию популярной идеи «мегабайты как ресурсы». Ничего сжигать-уничтожать не нужно, но необходимо выделить существенный объем дискового пространства, чтобы включиться в майнинг. Помимо энергоэффективности такого решения, есть и другой момент: защита от ботнета. Довольно сложно установить на компьютере жертвы майнер, который бы незаметно отхватил бы пару терабайт.
Алгоритм создает на диске много крупных блоков данных, которые получаются многократным хэшированием из вашего публичного ключа и случайных чисел. Из последнего заголовка блока мы получаем число-индекс, и берем в каждом нашем большом блоке данных небольшой кусочек с эти индексом. Чем больше места выделили – тем больше кусочков у нас есть. Дальше как обычно: хэш от кусочка и последнего заголовка должен быть меньше, чем цель (с учетом текущей сложности). Короче говоря, каждый ваш мегабайт HDD – это дополнительный лотерейный билет в майнинге.
Данная реализация, мягко говоря, не идеальна. Во-первых, в ней остается проблема nothing on stake: вы можете мгновенно пробежаться по всем своим терабайтам, чтобы проверить свои шансы в альтернативной цепочке, как и в случае PoS. То есть одновременно майнить сразу несколько цепочек, не затрачивая лишних ресурсов. Во-вторых, обращения к диску занимают довольно существенное время и, вероятно, эффективнее будет просто генерировать новые chunks на лету с помощью простого ASIC. Тогда мы просто получаем PoW-алгоритм.
Существует также похожая концепция с «мегабайтами» – Proof-of-Storage, но там выделенное место используется всеми участниками как совместное облачное хранилище. Эта идея довольно интересная, но одно ее описание будет слишком велико для данной статьи. Вы можете ознакомиться с дизайном системы на сайте.
Я подозреваю, что существует еще десятки различных proof-of-look-mum-no-hands, о которых мало кто слышал. Возможно, среди них есть свои жемчужины.
Математическое дополнение: при чем тут генералы?
В computer science есть задача под названием «Проблема Византиских генералов». Она формулируется так:
Византия. В ночь перед великим сражением, Византийская армия содержит n легионов. Каждый из них подчиняется своему генералу. У всей византийской армии есть главнокомандующий, руководящий генералами. Империя находится в упадке, и среди генералов, включая главнокомандующего, могут быть предатели. В течение всей ночи каждый из генералов получает от предводителя приказ о действии на утро. Это может быть один из двух вариантов: «атаковать» или «отступать». Если все честные генералы атакуют — они одержат победу. Если все отступят — им удастся сохранить армию. Если часть атакуют, а часть отступят — они терпят поражение. Если главнокомандующий предатель, он может дать разным генералам разные приказы, следовательно, его приказы не стоит выполнять беспрекословно. Если же каждый генерал будет действовать независимо от других, результаты битвы также могут быть плачевными. Поэтому генералы нуждаются в обмене информацией друг с другом, чтобы прийти к соглашению.
Какое отношение это имеет к криптовалютам? Ответ на это дает сам Сатоши: с помощью механизма Proof of work генералы могут справиться с этой задачей (которая, вообще говоря, является довольно сложной на практике – а для двух генералов и вовсе нерешаемой!). По сути, им необходим алгоритм как раз для установления распределенного консенсуса – способ узнать, «как думает большинство», и самому внести свой вклад.
В криптовалюте генералы – это узлы сети, а их сообщения – это цепочка блоков: истинной считается та, что длиннее (точнее, над которой было произведено больше работы). Тут есть одно важное замечание: в модели Сатоши мы получаем вероятностное решение («если атакующий имеет долю хэшрейта x%, то он сможет обмануть сеть с вероятностью y%»), в то время как классическая задача подразумевает детермированный алгоритм. Подробнее о различиях и формальном подходе вы можете прочитать тут.
Сатоши покинул сцену до появления на ней Proof of Stake и других альтернатив, поэтому мы вряд ли узнаем его мнение об их применимости к задаче Византийских генералов. Очевидно, что все не так просто: чистый PoS, как мы видели, не столь безопасен, как чистый PoW (no free lunch). Другие варианты – гибридные протоколы или совсем иные подходы – справляются ли они? Вопрос пока открыт.
