Проблемы криптовалют: консенсус, ASIC-устойчивость и полезный майнинг

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

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

Консенсус

Один из ключевых элементов алгоритма биткойна — концепция доказательства проделанной работы (proof-of-work). Во многих системах, решающих проблему византийских генералов, уровень безопасности определяется минимальной допустимой долей злонамеренных узлов: например, в контексте передачи секретов, алгоритм Берлекэмпа—Велча с двукратной избыточностью гарантированно обеспечивает желаемый результат, предполагая, что процент злонамеренных узлов не превышает 25% от общего числа узлов в сети. В контексте биткойн-майнинга условие формулируется так: совокупное количество честных узлов должно превышать число узлов в любой скоординированной группе злоумышленников. Тем не менее, все эти гарантии безопасности обладают одним важным общим свойством: должен существовать способ определить, является ли данный узел добросовестным. До биткойна большинство таких алгоритмов обладали высокой вычислительной сложностью и действовали, только если размер сети был небольшим, так чтобы было возможно учесть каждый узел, сопоставив его с владеющей им организацией или человеком.

В биткойн-сети, напротив, узлы многочисленны, по большей части анонимны и могут подключаться к сети и отключаться от нее в любое время. Без тщательного продумывания подсистемы безопасности подобная система будет подвержена так называемой атаке Сибиллы: злоумышленник просто создаст в пять раз больше узлов, чем сеть содержала изначально (либо с одной машины, либо арендуя виртуальный частный сервер, либо используя ботнет), и использует это «большинство», чтобы нарушить работу сети. Существует единственный способ предотвратить такой вид атаки: ввести механизм учета узлов на основе учета некоторого ресурса. Биткойн здесь использует схему, известную как доказательство проделанной работы (proof-of-work, PoW), которая включает в себя решение задач, которые сложно решить, но правильность решения которых легко проверить. Вес узла при достижении консенсуса основан на количестве решений, которые этот узел предоставляет, и биткойн-сеть автоматически вознаграждает узлы, которые предоставляют такие решения (то есть майнеров), новыми биткойнами и комиссиями за транзакции.
PoW-алгоритм биткойна — это простая реализация идеи Hashcash, изобретенной Адамом Беком (Adam Back) в 1995 году (по другим данным — в 1997 году. — прим. пер.). Hashcash-функция работает так:

def hashcash_produce(data, difficulty):
  nonce = random.randrange(2**256)
  while sha256(data + str(nonce)) > 2**256 / difficulty:
  nonce += 1
  return nonce
def hashcash_verify(data, nonce, difficulty):
  return sha256(data + str(nonce)) <= 2**256 / difficulty

Заметим, что в протоколе биткойна размер nonce ограничен 32 битами; на высоких уровнях сложности это приводит к необходимости также манипулировать данными самой транзакции в качестве дополнительного nonce-поля («extranonce»; см также «transaction malleability» — прим. пер.).

Изначально задумка создателя биткойна была очень элегантной: каждый человек будет индивидуально заниматься майнингом на собственном компьютере, в результате чего возникнет в высокой степени децентрализованная сеть без единой точки управления и механизм распределения новых биткойнов среди широкого круга пользователей. На протяжении первых полутора лет существования биткойна система действительно работала. Но летом 2010 года была разработана программа для майнинга, использовавшая возможности массивного параллелизма, доступные для графических процессоров в мощных видеокартах. Такая программа майнила в 10-50 раз эффективнее, чем обычный центральный процессор. В 2013 году специализация сделала следующий шаг: были представлены устройства на специализированных интегральных схемах (application-specific integrated circuits — ASIC), предназначенные исключительно для майнинга биткойнов. Это обеспечило скачок эффективности еще в 10-50 раз. Майнинг на центральных и графических процессорах теперь абсолютно нерентабелен. Существует лишь два способа заняться майнингом сейчас: либо основать многомиллионную компанию по производству ASIC-майнеров, либо купить майнер у одной из таких компаний.

Другая проблема, связанная с описанной выше — централизация пулов. С теоретической точки зрения, функция пула проста: вместо того, чтобы заниматься майнингом в одиночку с небольшим шансом получить награду за блок в размере 25 BTC, можно майнить в пуле и постоянно получать от него выплаты, пропорциональные проделанной работе (например, 0.002 BTC за каждый блок). Существуют как централизованные, так и децентрализованные майнинг-пулы. Тем не менее, децентрализованные пулы требуют от майнеров проверять валидность всего блокчейна, что легко делается на компьютере общего назначения, но не на ASIC-майнере. В результате почти все ASIC-майнеры работают с централизованными пулами. Результаты такой тенденции неутешительны. Сейчас почти 25% вычислительной мощности сети исходит из одной фабрики в Шэньчжэне, и почти 50% сети контролируется одним майнинг-пулом (по состоянию на 14 ноября 2014 года крупнейший пул Disqus Fish, по данным Blockchain.info, обладал 23% мощности сети — прим. пер.).

Вторую из названных проблем несложно ослабить: нужно просто создать алгоритм майнинга, который требовал бы от каждого майнинг-узла хранить блокчейн целиком. Первая же проблема, связанная с централизацией, гораздо сложнее. Существует вероятность, что это проблема со временем разрешится сама собой, и по мере роста биткойн-индустрии майнинг будет естественным путем становиться все менее централизованным, так как в индустрии будут появляться все новые ниши для новых компаний. Но это теоретическое предсказание может не сбыться, и мы должны быть готовы к наихудшему сценарию. К тому же, расходы энергии и стоимость вычисления PoW в том виде, в котором они находятся сейчас, могут быть полностью устранены. Рассмотрим возможные усовершенствования алгоритмов распределенного консенсуса.

ASIC-resistant PoW

Один подход к решению описанной проблемы заключается в создании PoW-алгоритма на основе вычислений, для которых сложно создать специализированные устройства. Одна из возможных идей включает создание хэш-функции, вычисление которой требует существенного объема памяти и затрудняет создание ASIC, использующих преимущества массивно-параллельной архитектуры. Идея проста, но фундаментально ограничена: если для вычисления функции требуется много памяти, много памяти требуется и для проверки правильности результата. К тому же, существует множество методов аппаратной оптимизации, не связанных с идеями параллелизма. Другой подход подразумевает динамическое создание новой хэш-функции для каждого блока, что затрудняет аппаратную оптимизацию, так как ASIC, оптимизированный для общих вычислений, это просто-напросто центральный процессор. Помимо этих двух, могут существовать и другие стратегии.

В конечном итоге, идеальная защита от ASIC невозможна: для любого алгоритма существуют участки микросхемы, которые в этом алгоритме не используются; в специализированном устройстве они могут быть удалены, что уменьшит его стоимость. С другой стороны, мы хотим достичь не идеальной (теоретической) защиты, а скорее экономической защиты от ASIC. Экономическая защита от ASIC может быть определена следующим образом. Во-первых, заметим, что в неспециализированном окружении прибыль от майнинга сублинейна: каждый владелец компьютера с N единицами неиспользованной вычислительной мощности может увеличивать прибыль от майнинга линейно по затратам вплоть до предела N (на этом этапе дополнительные затраты — это лишь дополнительные расходы на электричество), но для майнинга на уровне выше N требуются как затраты на электричество, так и вложения в дополнительное оборудование. Если стоимость майнинга на специализированном устройстве, включая стоимость исследований и разработки, выше на единицу хэш-мощности, чем стоимость первых N единиц мощности на пользователя, тогда такой алгоритм можно назвать ASIC-защищенным.

Более развернутую дискуссию об ASIC-защите можно прочитать в блоге Ethereum.

Задача: создать две функции, PoWProduce(data,diff) → nonce и PoWVerify(data,nonce,diff) → { 0, 1 }, для использования в качестве альтернативы Hashcash, чтобы производство ASIC для PoWProduce было бы экономически непривлекательно.

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

• Предположительное время работы PoWProduce должно быть линейным по diff.
• Предположительное время работы PoWVerify должно быть не более чем полилогарифмическим по diff.
• Запуск PoWProduce должен быть самым эффективным или очень близким к самому эффективному способом производить числа, на которых PoWVerify возвращала бы 1 (т. е. программная оптимизация должна быть невозможна).
• PoWProduce должна быть суперлинейной в смысле вычислительной сложности или времени: иными словами, ожидаемое количество успешных вычислений PoWProduce на узле с аппаратурой стоимостью N долларов после t секунд должна быть ограничена величиной kNt для некоторого k. Более того, линейность должна наступать быстро: оборудование для майнинга за 1000 долларов должно работать с эффективностью более 90%.
• ASIC-защищенность алгоритма должна быть достаточно строго обоснована методами технического и экономического анализа.

Полезная PoW-функция

Еще одна экономическая проблема, на которую часто указывают противники биткойна, заключается в том, что вычислительная мощность, потраченная на PoW, по сути потрачена впустую. Майнеры круглосуточно вычисляют значения SHA256 (или, в усовершенствованных модификациях, Scrypt), в надежде создать блок с необычайно низким значением хэш-функции. Эта работа не приносит никакой пользы обществу. Традиционные централизованные сети, такие как Paypal и операторы кредитных карт, умудряются обходиться вообще без PoW-вычислений, тогда как экосистема биткойна тратит около миллиона долларов на электричество ежедневно, и это не считая затрат на производство оборудования.

Один из многократно предложенных вариантов решения этой проблемы — использовать в качестве PoW-функции что-то полезное; в качестве кандидата чаще всего называют что-нибудь вроде Folding@home, существующую программу распределенных вычислений, где пользователи проводят вычислительные симуляции свертывания белков, обеспечивая ученых большим массивом данных, которые те используют для изобретения новых лекарств. Проблема, однако, заключается, в том, что результат Folding@home сложно проверить: проверить, правда ли некто проделал вычисления Folding@home корректно или же «срезал углы» с целью увеличить собственную прибыль, не принося никакой пользы исследователям, занимает столько же времени, сколько проведение такого вычисления заново. Если будет разработан простой способ проверить корректность вычисления Folding@home, либо если будет найдена другая общественно полезная вычислительная задача, результаты вычисления которой просто проверить, криптовалюта могла бы действительно принести огромную пользу обществу, не только снимая аргумент противников биткойна о том, что биткойн «впустую тратит энергию», но и предоставляя общественное благо.

Заметим, что уже обозначена главная проблема подобного подхода: если «полезный» PoW-алгоритм реализован корректно, это может потенциально снизить стоимость атаки на сеть. Если полезный PoW полезен в некотором смысле, так что иногда для очень больших сущностей вычисление PoW становится экономически выгодным даже без учета вознаграждения от криптовалютной сети, у таких сущностей могла бы появиться мотивация провести атаку на сеть фактически бесплатно, поскольку вычисления они бы проводили в любом случае. Один из простейших методов борьбы с этим эффектом (грубый и несовершенный) заключается в том, чтобы сделать PoW состоящим наполовину из полезных, а наполовину — из бесполезных вычислений, повышая стоимость атаки до как минимум 50% такой стоимости в случае полностью бесполезной PoW. На практике дополнительные затраты на то, чтобы сделать PoW легко проверяемым, легко могут непроизвольно увеличить вычислительные затраты вдвое. Другой подход — порождать в результате вычисления PoW некое «чистое» общественное благо, то есть такое благо, что никакая индивидуальная сущность сама по себе не сможет получить существенной прибыли от его использования. Предлагаемые решения описанной проблемы должны опираться на строгий анализ.

Задача: создать две функции, PoWProduce(data,diff) → nonce и PoWVerify(data,nonce,diff) → { 0, 1 }, для использования в качестве альтернативы Hashcash, так чтобы значения PoWProduce обладали независимой ценностью.

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

• Предположительное время работы PoWProduce должно быть линейным по diff.
• Предположительное время работы PoWVerify должно быть максимум полилогарифмическим по diff.
• Запуск PoWProduce должен быть самым эффективным или очень близким к самому эффективному способом производить числа, на которых PoWVerify возвращала бы 1 (т. е. программная оптимизация должна быть невозможна).
• PoWProduce должна быть суперлинейной в смысле вычислительной сложности или времени: иными словами, ожидаемое количество успешных вычислений PoWProduce на узле с аппаратурой стоимостью N долларов после t секунд должна быть ограничена величиной kNt для некоторого k. Более того, линейность должна наступать быстро: оборудование для майнинга за 1000 долларов должно работать с эффективностью более 90%.
• Функция PoWProduce должна производить общественное благо, так чтобы общая ценность этого блага для всех превышала бы стоимость всех ресурсов, затраченных на майнинг.
• Система должна быть способна существовать без доверенной третьей стороны. Впрочем, может быть разумно использовать третью сторону как источник исходных данных для полезных вычислений. Если третья сторона будет действовать злонамеренно, ценность общественного блага может быть сведена на нет, но блокчейн при этом не должен быть скомпрометирован.

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

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