Доказательство выполнения работы

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Доказательство выполнения работы (англ. Proof-of-work, POW, PoW) — принцип защиты распределенных систем от злоупотребления услугами (например, DoS-атак или рассылок спама), основанный на необходимости выполнения запрашивающей стороной некоторой достаточно сложной длительной работы (POW-задачи), результат которой легко и быстро проверяется обслуживающей стороной (односторонняя функция). Главная особенность этих схем заключается в асимметрии затрат времени — затраты значительны для инициатора запроса и весьма малы для проверяющего.[1] Подобные схемы также известны как client puzzle (функция клиентской головоломки), computational puzzle (вычислительная головоломка), или CPU pricing function.

Не следует путать этот способ защиты с капчами, которые предлагают задачи, лёгкие для человека, но трудноразрешимые или вовсе неразрешимые для компьютера. POW-задачи предназначены для вычислительных систем, их решение компьютером всегда достижимо в конечные сроки, но требует выполнения большого количества операций, а для проверки полученного решения требуется относительно малое количество операций.[2] Наибольшее распространение и развитие POW-технологии получили в криптовалютных системах.

История Развития[править | править вики-текст]

Впервые идея Proof-of-work, прозвучала в статье «Pricing via Processing or Combatting Junk Mail» [3] в 1993 году, авторы предложили следующую идею: для доступа к общему ресурсу, пользователь должен вычислить некоторую функцию, весьма сложную и ресурсоемкую, но при этом решаемую за приемлемое время. Вычисление функции на стороне клиента должно быть гораздо сложнее, чем проверка результата на стороне сервера. Одним из обязательных условий является то, что функция не должна быть амортизируемой, то есть при решении нескольких функций времени требовалось бы пропорционально их количеству. По предположению, подобные дополнительные расчёты не создают препятствий для отправки нескольких обычных писем с компьютера рядового пользователя, но необходимость постоянных вычислений делает отправку спама очень ресурсоемкой для злоумышленников. По независимым оценкам подобные системы приводят фактически к существенному ограничению количества писем, которые возможно отправить за день с одного компьютера[4]).

В 1997 году Адам Бэк запустил проект Hashcash[5], посвященный защите от спама. Задача формулировалась следующим образом: «Найти такое значение x, что хеш SHA(x) содержал бы N старших нулевых бит».

В 1999 году появляется термин Proof-of-Work — использован он был в статье «Proofs of Work and Bread Pudding Protocols» (авторы — Маркус Якобссон и Ари Джуелс) в журнале Communications and Multimedia Security.[6]

16 августа 2004 года Хэл Финни в своем письме к шифропанкам предложил использовать многоразовое доказательство выполнения работы (англ. Reusable-roofs-of-Work, RPOW, RPoW) как электронную валюту, то есть токены — доказательства являются монетами.[7]

Однако вскоре Сатоси Накамото модернизировал эту идею таким образом, что PoW был использован как средство достижения распределенного совместного принятия решения, то есть единого мнения о том, какую версию блокчейна считать верной. Hashcash была выбрана как основа для POW, а вычисляемой функцией стала SHA-256. В дальнейшем в других криптовалютах (например Litecoin) вместо SHA-256 стали применяться KDF, такие как scrypt, bcrypt, PBKDF2 и так далее.[8]

Примеры POW функций[править | править вики-текст]

Список наиболее распространенных POW функций:

  • Хеширование частичной инверсии. Наиболее известное применение- это система Hashcash[9], которая использует хеширование частичной инверсии при отправке по электронной почте. Для расчёта соответствующего заголовка требуется около 252 хэш-вычислений, которые надо пересчитывать для каждой отправки. При этом проверка корректности вычисленного кода является быстрой — используется однократное вычисление SHA-1 с заранее подготовленной меткой.[10][11] [12]
  • Функции основанные на деревьях Меркля.[13] Самый известный пример применения данного варианта можно найти в системе Bitcoin, где в качестве доказательства выполнения работы используется многоуровневое хеширование — хеш предыдущего блока становится элементом последующего. Таким образом нет возможности изменить блок без изменения хешей во всех последующих блоках. При этом проверка целостности всей цепочки ограничена однократным вычислением хешей текущего блока и предыдущего. Хеш признаётся истинным только в том случае, если значение хеш-суммы меньше значения специального параметра, определяющего сложность майнинга. Для поиска такой хеш-суммы требуется её многократный пересчёт с перебором произвольных значений параметра nonce. [14]
  • Квадратичный вычет по модулю большего простого числа[15]
  • Подпись по Протоколу Фиата — Шамира [15]
  • Функция на основе Протокола Диффи — Хеллмана [16]
  • Функция ограниченная по памяти [17]
  • Кукушкино хеширование[18]

Потенциальные уязвимости и атаки на информационные системы, основанные на POW[править | править вики-текст]

Эксперты продолжают обсуждать, является ли POW-защита достаточно эффективной против DoS-атак и спама[19][20].

Атака 51 %[править | править вики-текст]

На ранних этапах существования Bitcoin как и многие другие криптовалюты уязвим к «атаке 51 %»: если в руках злоумышленника находится больше половины всех вычислительных мощностей в сети, то у него появляется возможность подтверждать только свои блоки, при этом игнорируя чужие, что позволяет ему получать 100 % всех производимых биткойнов, а также блокировать любые транзакции. Как вариант атакующий может переписать всю историю генерации блоков, начиная с определенного момента в прошлом. В результате он может догнать и обогнать текущую цепочку блокчейна, сделав свой вариант валидным. Как итог, деньги, хранящиеся в кошельках пользователей на протяжении продолжительного периода, пропадут.[21]

Двойное расходование[править | править вики-текст]

Двойное расходование (двойная трата) — повторная передача одних и тех же активов. Данная атака делится на несколько подтипов.

  • Атака типа «гонки»(англ. Race Attack). Злоумышленник совершает транзакцию X, оплачивая покупку товара, одновременно переводя эти же деньги на другой свой счет транзакцией Y. Если продавец не стал ждать подтверждения транзакции и отгрузил товар, то он пошел на большой риск, так как есть 50 % вероятность, что транзакция Y может попасть в истинную цепочку, причем эта вероятность повышается в случае, если злоумышленник целенаправленно выбирает узлы сети для проведения той или иной операции.[22]
  • Атака Финни заключается в следующем: злоумышленник пытается найти блок, который содержит его транзакцию Y. Однако как только блок обнаруживается, атакующий отправляет транзакцию X, после чего он покупает товар. Продавец дожидается подтверждения транзакции X и отгружает товар. Если в этот момент появляется блок с транзакцией Y, то создается ситуация развилки, в которой майнеры должны выбрать один из двух блоков для продолжения цепочки блокчейна. При сосредоточении большого количества вычислительных ресурсов в руках злоумышленника, он может значительно увеличить вероятность выбора блока с операцией Y. Таким образом подтвержденная транзакция не является гарантированно валидной.[23]

Эгоистичный майнинг[править | править вики-текст]

При эгоистичном майнинге (англ. selfish mining) целью злоумышленника является контроль над сетью при том, что он обладает вычислительными ресурсами, суммарной мощностью менее 50 %. Это достигается за счет того, что злоумышленник заявляет, что его пул более выгодный для майнинга, чем другие пулы, что привлекает сторонних майнеров. Атакующий публикует блоки таким образом, чтобы вычислительные ресурсы других майнеров и пулов были потрачены впустую. Приблизительный ход алгоритма такой:

  1. Пул тайно от всех майнит свою приватную цепочку.
  2. Если пул находит новый блок для своей приватной цепи, то:
    1. если оригинальная цепочка разветвилась, то атакующий публикует свой блок, таким образом его цепочка становится длиннее и становится истинной, а цепь честных майнеров отбрасывается.
    2. Если развилки пока нету, то пул продолжает тайно майнить свою приватную цепь, наращивая отрыв.
  3. Если публичная цепь находит блок для общедоступной цепи, то:
    1. Если публичная цепь опережает тайную, то пул злоумышленника отбрасывает свои неопубликованные блоки, и начинает майнить с нового публичного блока.
    2. Если цепи сравнялись, то пул злоумышленника публикует все свои блоки, таким образом уходя в отрыв в своей цепи.
    3. Если публичная цепь отстает на некоторое количество (N) блоков от приватной, то пул публикует на один блок больше (N+1), что изолирует новый честный блок.

Почти при каждом исходе честные майнеры оказываются в проигрыше, что вынуждает их присоединиться к преступному пулу.[24]

Критика информационных систем на основе POW[править | править вики-текст]

Противники POW подхода, помимо ряда потенциальных проблем с безопасностью, выделяют следующие недостатки:

  • Вероятность успешного создания следующего блока майнером прямо пропорциональна вычислительным мощностям, которыми он обладает, что приводит к постоянному наращиванию количества и качества оборудования каждого участника сети. Таким образом, майнинг с применением POW алгоритмов требует чрезвычайно много электроэнергии. Поэтому POW подход является не самым лучшим решением с точки зрения энергоэффективности. [25][26]
  • Результаты вычисления хэш-функций нигде, кроме как в самой сети, не нужны. С момента появления технологии сообщество пыталось придумать способ направить все вычислительные ресурсы сети на решение какой-либо полезной математической или промышленной задачи, но в чистом виде это не удалось реализовать.[27]

Попытки избавиться от недостатков POW привели к появлению POS и многочисленных гибридных вариантов.

Примеры гибридных технологий[править | править вики-текст]

Примеры гибридных схем, совмещающих идеи POS и POW можно найти во многих криптовалютах. В них блокчейн состоит из блоков обоих типов, что делает переписывание историй транзакций непростой задачей, так как POW блоки служат контрольными точками, если брать во внимание суммарную сложность работы во всей цепочке. Обычно в таких алгоритмах POW блоки служат показателями реальной работы, что дает дополнительную гарантию надежности для продавцов при работе с транзакциями. POW блоки можно использовать для эмиссии валюты, а POS блоки рассматривать как потенциальный доход от депозита.[28]

Proof of Activity[править | править вики-текст]

Не реализованный пока прототип алгоритма, заключающийся в том что холдеры вступают в общий процесс, только после проведения некоторой работы POW участниками, что уменьшает шансы на атаку 51 %, так как мажоритарный владелец не сможет единолично контролировать создание новых блоков.[29]

Принцип работы алгоритма:

  1. POW майнер ищет хэш соответствующей сложности.
  2. Найденный хэш отправляется в сеть, при этом являясь не блоком, а лишь первым шагом, своеобразным шаблоном, необходимым для его создания.
  3. Хэш, состоящий из 256 псевдослучайных бит, интерпретируется как N чисел, к каждому из которых в соответствие ставится один сатоши.
  4. Устанавливается взаимно однозначная связь между каждым сатоши и публичным ключом его текущего владельца.
  5. Как только все N владельцев поставят свои подписи на этом блоке, на выходе получается полноценный блок.
  6. В случае, если один из холдеров не доступен или не участвует в майнинге, то остальные майнеры продолжают генерировать шаблоны с различными комбинациями холдеров-кандидатов.
  7. В какой-то момент необходимый блок будет подписан нужное количество раз. Награда за блок распределяется между POW майнером и всеми N холдерами.

Proof of Burn[править | править вики-текст]

Деньги отправляются на адрес, являющийся хешем случайного числа, с этого адреса их гарантированно нельзя потратить, так как вероятность подобрать ключи к нему стремится к нулю. Взамен майнер получает постоянный шанс найти PoB блок и получить за него награду. Майнинг в данном случае устроен так, что шансы на успех зависят от количества сожженных монет. Проводя аналогии, сжигание- это как невозвратный POS депозит или инвестиции в виртуальное железо для POW майнинга. С экономической точки зрения данный алгоритм лучше подходит для поздних этапов развития криптовалюты, когда уже сгенерирована большая часть денежной массы.[30]

Proof of Capacity[править | править вики-текст]

Алгоритм Proof of Capacity (или Proofs of Space) заключается в следующем: для майнинга необходимо выделить существенный объем памяти на компьютере, после чего многократным хэшированием из публичного ключа и случайных чисел создается большое количество крупных блоков данных. В каждом блоке данных из последнего заголовка получаем индекс, после чего выбираем небольшой кусочек блока с этим индексом, чанк (англ. Chunk). Чем больше памяти выделено, тем больше получаем чанков. Должно выполняться условие, что хеш чанка и последнего заголовка должен быть меньше чем цель. Таким образом, каждый мегабайт памяти используется как аналог лотерейного билета и увеличивает шанс на успех при майнинге.[31]


Энергетическая неэффективность[править | править вики-текст]

Системы на основе POW являются чрезвычайно ресурсоёмкими.

  • В 2013 году совокупная вычислительная мощность, затрачиваемая на POW в сети Bitcoin, обогнала в 256 раз топ-500 самых мощных на тот год суперкомпьютеров в мире вместе взятых.[32]
  • В 2017 году на полное оформление одной транзакции в системе Bitcoin требовалось затратить в среднем 163 кВт⋅ч энергии. Таким количеством энергии можно в течение пяти с половиной дней полностью обеспечивать нужды семьи, состоящей из трех человек и проживающей в небольшом одноэтажном доме. На майнинг криптовалют в сетях Bitcoin и Ethereum суммарно уходило энергии больше чем потребляло всё население Сирии[33][34].

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Pricing via Processing or Combatting Junk Mail (1993) (англ.)
  2. Pricing via Processing or Combatting Junk Mail (1993) (англ.)
  3. Pricing via Processing or Combatting Junk Mail (1993) (англ.)
  4. «Proof-of-Work» Proves Not to Work, 2004 «If we try to make it uneconomic to send spam then we must restrict senders to 1,750 messages a day»
  5. Hashcash.org (англ.)
  6. Proofs of Work and Bread Pudding Protocols (1999) (англ.)
  7. RPOW — Reusable Proofs of Work (2004) (англ.)
  8. The Proof-of-Work in Cryptocurrencies: Brief History. Part 1 (2015) (англ.)
  9. Hashcash — A Denial of Service Counter-Measure (2002) (англ.)
  10. Back, Adam HashCash. Popular proof-of-work system. First announce in March 1997.
  11. (1998) «Curbing junk e-mail via secure classification». Financial Cryptography: 198–213.
  12. (May 2003) «Defending against denial-of-service attacks with puzzle auctions». IEEE Symposium on Security and Privacy '03.
  13. Coelho, Fabien An (almost) constant-effort solution-verification proof-of-work protocol based on Merkle trees. Cryptology ePrint Archive, Report.
  14. Bitcoin: A Peer-to-Peer Electronic Cash System (англ.)
  15. 1 2 (1993) «Pricing via Processing, Or, Combatting Junk Mail, Advances in Cryptology». CRYPTO’92: Lecture Notes in Computer Science No. 740 (Springer): 139–147.
  16. (2004) «New client puzzle outsourcing techniques for DoS resistance». 11th ACM Conference on Computer and Communications Security.
  17. (2003) «On memory-bound functions for fighting spam». Advances in Cryptology: CRYPTO 2003 (Springer) 2729: 426–444.
  18. Tromp, John Cuckoo Cycle; a memory bound graph-theoretic proof-of-work 49–62. Springer (2015).
  19. (May 2004) «Proof-of-work proves not to work». WEIS 04.
  20. (June 2006) «Proof of Work can work». Fifth Workshop on the Economics of Information Security.
  21. Bitcoin: A Peer-to-Peer Electronic Cash System (англ.)
  22. Attacks in the World of Cryptocurrencies (англ.)
  23. Analysis of hashrate-based double-spending(2012) (англ.)
  24. Attacks in the World of Cryptocurrencies(2015) (англ.)
  25. Bitcoin Energy Consumption Index (англ.)
  26. Ethereum Energy Consumption Index (beta) (англ.)
  27. The Proof-of-Work in Cryptocurrencies: Brief History. Part 2  (англ.)
  28. Alternatives for Proof of Work, Part 2 (2015) (англ.)
  29. Proof of Activity: Extending Bitcoin’s Proof of Work via Proof of Stake (англ.)
  30. A Peer-to-Peer Crypto-Currency with Proof-of-Burn «Mining without Powerful Hardware»(2014) (англ.)
  31. Proofs of Space: When Space is of the Essence (англ.)
  32. Global Bitcoin Computing Power Now 256 Times Faster Than Top 500 Supercomputers, Combined! (2013) (англ.)
  33. Bitcoin Energy Consumption Index (англ.)
  34. Ethereum Energy Consumption Index (beta) (англ.)