Доказательство работы - Proof of work

Доказательство работы (PoW) является формой криптографический доказательство с нулевым разглашением в какой партии ( испытатель) доказывает другим ( верификаторы), что для какой-то цели было затрачено определенное количество вычислительных усилий. В дальнейшем верификаторы могут подтвердить эти расходы с минимальными усилиями со своей стороны. Концепция была изобретена Синтия Дворк и Мони Наор в 1993 году как способ сдерживания атаки отказа в обслуживании и другие злоупотребления услугами, такие как спам в сети, требуя некоторой работы от запрашивающей службы, обычно означающей время обработки на компьютере. Термин «доказательство работы» впервые был придуман и формализован в статье 1999 г. Маркус Якобссон и Ари Джуэлс.[1][2] Позже доказательство работы было популяризировано Биткойн в качестве основы для консенсус в без разрешения блокчейны и криптовалюты, в котором майнеры соревнуются за добавление блоков и чеканку новой валюты, при этом вероятность успеха каждого майнера пропорциональна количеству вычислительных усилий, которые они доказанно затратили. PoW и PoS (Доказательство ставки ) являются двумя наиболее известными механизмами консенсуса и также наиболее часто используются в контексте криптовалют.[3]

Ключевой особенностью схем Proof-of-Work является их асимметрия: работа должна быть умеренно сложной (но выполнимой) со стороны проверяющей или запрашивающей стороны, но легко проверяемой проверяющей стороной или поставщиком услуг. Эта идея также известна как функция стоимости ЦП, загадка клиента, вычислительная головоломка или функция ценообразования ЦП. Он отличается по назначению от CAPTCHA, который предназначен для быстрого решения человеком, но сложен для решения на компьютере.

Фон

Одна популярная система, используемая в Hashcash, использует частичную инверсию хеша, чтобы доказать, что работа была выполнена, в качестве токена доброй воли для отправки электронное письмо. Например, следующий заголовок представляет около 252 хеш-вычисления для отправки сообщения [email protected] 19 января 2038 г .:

X-Hashcash: 1: 52: 380119: [email protected] ::: 9B760005E92F0DAE

Это проверяется одним вычислением, проверяя, что SHA-1 хеш штампа (не указывать название заголовка X-Hashcash: включая двоеточие и любое количество пробелов, следующих за ним до цифры '1') начинается с 52 двоичных нулей, то есть 13 шестнадцатеричных нулей:[1]

0000000000000756af69e2ffbdb930261873cd71

Могут ли системы PoW действительно решить конкретную проблему отказа в обслуживании, такую ​​как проблема спама, является предметом обсуждения;[4][5]система должна сделать рассылку спама навязчиво непродуктивной для спамера, но также не должна препятствовать легитимным пользователям отправлять свои сообщения. Другими словами, настоящий пользователь не должен сталкиваться с какими-либо трудностями при отправке электронной почты, но спамеру электронной почты придется затратить значительные вычислительные мощности для одновременной отправки множества электронных писем. Системы подтверждения работы используются в качестве примитивов другими более сложными криптографическими системами, такими как биткойн который использует систему, аналогичную Hashcash.

Варианты

Существует два класса протоколов доказательства работы.

  • Вызов – ответ протоколы предполагают прямую интерактивную связь между запрашивающей стороной (клиентом) и провайдером (сервером). Поставщик выбирает задачу, скажем, элемент в наборе со свойством, запрашивающая находит соответствующий ответ в наборе, который отправляется обратно и проверяется поставщиком. Поскольку задача выбирается провайдером на месте, ее сложность может быть адаптирована к текущей нагрузке. Работа на стороне запрашивающего может быть ограничена, если протокол запрос-ответ имеет известное решение (выбранное поставщиком) или известно, что он существует в ограниченном пространстве поиска.
Подтверждение работы: response.svg
  • Решение – проверка протоколы не предполагают наличие такой связи: в результате проблема должна быть наложена на себя, прежде чем решение будет найдено запрашивающей стороной, а провайдер должен проверить как выбор проблемы, так и найденное решение. Большинство таких схем представляют собой неограниченные вероятностные итерационные процедуры, такие как Hashcash.
Решение Proof of Work verify.svg

Протоколы известных решений имеют тенденцию иметь немного меньшую дисперсию, чем неограниченные вероятностные протоколы, потому что дисперсия прямоугольное распределение ниже, чем дисперсия распределение Пуассона (с таким же средним).[требуется дальнейшее объяснение ] Общий метод уменьшения дисперсии заключается в использовании нескольких независимых подзадач, поскольку среднее значение нескольких выборок будет иметь меньшую дисперсию.

Существуют также функции с фиксированной стоимостью, такие как головоломка с временным замком.

Более того, базовые функции, используемые этими схемами, могут быть:

  • Привязанный к ЦП где вычисление выполняется со скоростью процессора, который сильно меняется во времени, а также от серверов высокого класса до портативных устройств низкого уровня.[6]
  • Привязанный к памяти[7][8][9][10] где скорость вычислений ограничена доступом к основной памяти (задержкой или пропускной способностью), производительность которых, как ожидается, будет менее чувствительна к эволюции оборудования.
  • Привязанный к сети[11] если клиент должен выполнить небольшое количество вычислений, но должен собрать некоторые токены с удаленных серверов перед тем, как запросить окончательного поставщика услуг. В этом смысле работа на самом деле не выполняется инициатором запроса, но в любом случае возникают задержки из-за задержки получения требуемых токенов.

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

Список функций доказательства работы

Вот список известных функций доказательства работы:

Многоразовые доказательства работы в виде электронных денег

Специалист в области информатики Хэл Финни построена на идее доказательства работы, давая систему, которая использует многоразовое доказательство работы (RPoW).[19]Идея многократного использования доказательств работы для некоторых практических целей возникла еще в 1999 году.[1] Целью Финни для RPoW было токен деньги. Подобно тому, как считается, что ценность золотой монеты определяется стоимостью необработанного золота, необходимого для ее изготовления, ценность токена RPoW гарантируется стоимостью реальных ресурсов, необходимых для «чеканки» токена PoW. В версии RPoW Финни токен PoW является частью Hashcash.

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

Система RPoW Финни отличалась от системы PoW тем, что позволяла случайный обмен токенами без повторения работы, необходимой для их генерации. После того, как кто-то «потратил» токен PoW на веб-сайте, оператор веб-сайта мог обменять этот «потраченный» токен PoW на новый неизрасходованный токен RPoW, который затем можно было потратить на каком-то стороннем веб-сайте, аналогичном оборудованном для приема токенов RPoW. Это сэкономит ресурсы, которые в противном случае необходимы для «чеканки» токена PoW. Защита от подделки токена RPoW была гарантирована удаленная аттестация. Сервер RPoW, который обменивает использованный токен PoW или RPoW на новый токен равной стоимости, использует удаленную аттестацию, чтобы позволить любой заинтересованной стороне проверить, какое программное обеспечение работает на сервере RPoW. Поскольку исходный код программного обеспечения Finney RPoW был опубликован (под BSD -подобно лицензии), любой достаточно осведомленный программист мог, проверив код, убедиться, что программное обеспечение (и, как следствие, сервер RPoW) никогда не выдавало новый токен, кроме как в обмен на потраченный токен равной стоимости.

До 2009 года система Финни была единственной внедренной системой RPoW; он никогда не находил экономически значимого использования.

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

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

В 2009 г. Биткойн сеть вышла в онлайн. Биткойн - это доказательство работы криптовалюта который, как и RPoW Финни, также основан на Hashcash PoW. Но в Биткойне защита от двойного расходования обеспечивается децентрализованным протоколом P2P для отслеживания переводов монет, а не аппаратной функцией доверенных вычислений, используемой RPoW. Биткойн имеет большую надежность, потому что он защищен вычислениями. Биткойны «добываются» с использованием функции подтверждения работы Hashcash отдельными майнерами и проверяются децентрализованными узлами в сети биткойнов P2P.

Сложность периодически корректируется, чтобы время блока около целевого времени.

Потребление энергии

С момента создания Биткойна доказательство работы было преобладающим дизайном одноранговой криптовалюты. Во многих исследованиях изучается потребление энергии при майнинге.[20] Механизм PoW требует огромного количества вычислительных ресурсов, которые потребляют значительное количество электроэнергии. Энергопотребление Биткойна может обеспечить энергию для всей страны.[3]

Однако не известно альтернативного дизайна, который мог бы заменить доказательство работы, но сохранил бы его желательные атрибуты, такие как:[нужна цитата ]

  • майнинг без разрешения
  • справедливое распределение монет
  • защита от многих известных атак
  • возможность загрузки новых узлов во враждебной среде
  • постепенная деградация и восстановление даже в случае успешной атаки или сбоя сети
  • неподдельная и статически проверяемая стоимость

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

ASIC и пулы для майнинга

В сообществе Биткойн есть группы, работающие вместе в пулы для майнинга.[21] Некоторые майнеры используют специализированные интегральные схемы (ASIC) для PoW.[22] Эта тенденция к майнинговым пулам и специализированным ASIC сделала добычу некоторых криптовалют экономически невыгодной для большинства игроков без доступа к новейшим ASIC, близлежащим источникам недорогой энергии или другим особым преимуществам.[23]

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

Смотрите также

Примечания

  • ^ В большинстве систем Unix это можно проверить с помощью команды: echo -n 1: 52: 380119: [email protected] ::: 9B760005E92F0DAE | openssl sha1

Рекомендации

  1. ^ а б c Якобссон, Маркус; Джулс, Ари (1999). "Доказательства работы и протоколы хлебного пудинга". Защищенные информационные сети: безопасность коммуникаций и мультимедиа. Kluwer Academic Publishers: 258–272. Дои:10.1007/978-0-387-35568-9_18.
  2. ^ а б c d Дворк, Синтия; Наор, Мони (1993). «Ценообразование посредством обработки или борьбы с нежелательной почтой, достижения в области криптологии». CRYPTO'92: Конспект лекций по информатике № 740. Springer: 139–147. Дои:10.1007/3-540-48071-4_10.
  3. ^ а б «Криптовалюты и блокчейн» (PDF). Европейский парламент. Июль 2018 г.. Получено 29 октября 2020. два самых известных - и в контексте криптовалют также наиболее часто используемые
  4. ^ Лори, Бен; Клейтон, Ричард (май 2004 г.). «Доказательство работы не работает». Семинар по экономике информационной безопасности 2004 г..
  5. ^ Лю, Дебин; Кэмп, Л. Жан (июнь 2006 г.). «Proof of Work может работать - Пятый семинар по экономике информационной безопасности».
  6. ^ Насколько мощным был компьютер Apollo 11?, конкретное сравнение, которое показывает, насколько разные классы устройств имеют разную вычислительную мощность.
  7. ^ а б Абади, Мартин; Берроуз, Майк; Манассе, Марк; Воббер, Тед (2005). «Умеренно сложные функции, связанные с памятью». 5 (2): 299–327. Цитировать журнал требует | журнал = (помощь)
  8. ^ а б Дворк, Синтия; Гольдберг, Эндрю; Наор, Мони (2003). «О функциях борьбы со спамом, связанных с памятью». Достижения в криптологии: CRYPTO 2003. Конспект лекций по информатике. Springer. 2729: 426–444. Дои:10.1007/978-3-540-45146-4_25. ISBN  978-3-540-40674-7.
  9. ^ а б Коэльо, Фабьен (2005). «Экспоненциальные функции с привязкой к памяти для протоколов подтверждения работы». Cryptology ePrint Archive, Report.
  10. ^ а б Тромп, Джон (2015). "Цикл кукушки; теоретико-графическое доказательство работы с ограничением памяти" (PDF). Финансовая криптография и безопасность данных: BITCOIN 2015. Конспект лекций по информатике. Springer. 8976: 49–62. Дои:10.1007/978-3-662-48051-9_4. ISBN  978-3-662-48050-2.
  11. ^ а б Аблиз, Мехмуд; Знати, Тайеб (декабрь 2009 г.). «Путеводитель по предотвращению отказа в обслуживании». Труды Ежегодной конференции по приложениям компьютерной безопасности (ACSAC) 2009 г.. Гонолулу, Гавайи: 279–288. CiteSeerX  10.1.1.597.6304. Дои:10.1109 / ACSAC.2009.33. ISBN  978-1-4244-5327-6. S2CID  14434713.
  12. ^ Назад, Адам. «HashCash». Популярная система PoW. Впервые заявлено в марте 1997 года.
  13. ^ Габбер, Эран; Якобссон, Маркус; Матиас, Йосси; Майер, Ален Дж. (1998). «Защита от нежелательной почты с помощью безопасной классификации» (PDF). Финансовая криптография: 198–213.
  14. ^ Ван, Сяо-Фэн; Райтер, Майкл (май 2003 г.). «Защита от атак типа« отказ в обслуживании »с помощью аукционов головоломок» (PDF). Симпозиум IEEE по безопасности и конфиденциальности '03.
  15. ^ Франклин, Мэтью К.; Малхи, Далия (1997). «Контролируемый учет с облегченной защитой». Финансовая криптография '97. Конспект лекций по информатике. 1318: 151–160. Дои:10.1007/3-540-63594-7_75. ISBN  978-3-540-63594-9. Обновленная версия от 4 мая 1998 г.
  16. ^ Джуэлс, Ари; Брейнард, Джон (1999). «Клиентские головоломки: криптографическая защита от атак с истощением соединения». NDSS 99.
  17. ^ Waters, Brent; Джуэлс, Ари; Halderman, John A .; Фелтен, Эдвард В. (2004). «Новые методы аутсорсинга клиентских головоломок для защиты от DoS-атак» (PDF). 11-я конференция ACM по компьютерной и коммуникационной безопасности.
  18. ^ Коэльо, Фабьен (2007). «Протокол доказательства работы (почти) постоянных усилий для проверки решения, основанный на деревьях Меркла». Cryptology ePrint Archive, Report.
  19. ^ «Многоразовые доказательства работы». Архивировано из оригинал 22 декабря 2007 г.
  20. ^ «Кембриджский индекс потребления электроэнергии в биткойнах». Кембриджский центр альтернативных финансов. Получено 30 сентября 2020.
  21. ^ Обзор пулов для майнинга биткойнов на blockchain.info
  22. ^ Что такое ASIC-майнер на digitaltrends.com
  23. ^ Ворик, Дэвид (13 мая 2018 г.). «Состояние майнинга криптовалюты».
  24. ^ Савва Шанаев, Арина Шураева, Михаил Васенин и Максим Кузнецов (2019). «Стоимость криптовалюты и 51% атак: данные исследований событий». Журнал альтернативных инвестиций. 22 (3): 65–77. Дои:10.3905 / jai.2019.1.081. S2CID  211422987.CS1 maint: использует параметр авторов (связь)

внешняя ссылка

  • Система Финни на Wayback Machine (архивировано 22 декабря 2007 г.)
  • немного золота Бит золота. Описывает полную денежную систему (включая создание, хранение, анализ и передачу), основанную на функциях подтверждения работы и проблему архитектуры машины, возникающую в результате использования этих функций.