Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Фон [ править ]

Одна популярная система, используемая в Hashcash , использует частичную инверсию хэша, чтобы доказать, что работа была выполнена, в качестве токена доброй воли для отправки электронного письма . Например, следующий заголовок представляет около 2 52 вычислений хеша для отправки сообщения [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. [4]

Варианты [ править ]

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

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

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

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

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

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

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

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

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

  • Целочисленный квадратный корень по модулю большого простого числа [2] [ сомнительно - обсудить ]
  • Ослабить сигнатуры Fiat – Shamir [2]
  • Подпись Онга – Шнорра – Шамира, нарушенная Поллардом [2]
  • Частичная инверсия хэша [12] [13] [1] Эта статья формализует идею доказательства работы и вводит «зависимую идею протокола хлебного пудинга », систему «доказательства работы многократного использования» (RPoW) . [14]
  • Последовательности хеширования [15]
  • Пазлы [16]
  • Головоломка на основе Диффи-Хеллмана [17]
  • Умеренный [7]
  • Мбаунд [8]
  • Хоккайдо [9]
  • Цикл кукушки [10]
  • На основе дерева Меркла [18]
  • Протокол головоломки с гидом [11]

Многоразовые доказательства работы [ править ]

Компьютерный ученый Хэл Финни построил на идее доказательства работы систему, в которой использовалось многоразовое доказательство работы (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 's Программное обеспечение RPoW было опубликовано (подBSD- подобная лицензия), любой достаточно осведомленный программист мог, проверив код, убедиться, что программное обеспечение (и, как следствие, сервер RPoW) никогда не выдавало новый токен, кроме как в обмен на потраченный токен равной стоимости.

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

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

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

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

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

Энергопотребление [ править ]

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

Модификация истории [ править ]

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

ASIC и пулы для майнинга [ править ]

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

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

См. Также [ править ]

  • Биткойн
  • Bitmessage
  • Криптовалюта
  • Доказательство авторитета
  • Доказательство ожога
  • Доказательство личности
  • Доказательство места
  • Доказательство ставки
  • Подтверждение прошедшего времени
  • Консенсус (информатика)

Заметки [ править ]

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

Ссылки [ править ]

  1. ^ a b c Якобссон, Маркус; Джулс, Ари (1999). «Доказательства работы и протоколы хлебного пудинга» . Защищенные информационные сети: безопасность коммуникаций и мультимедиа . Kluwer Academic Publishers: 258–272. DOI : 10.1007 / 978-0-387-35568-9_18 .
  2. ^ a b c d Дворк, Синтия ; Наор, Мони (1993). «Ценообразование посредством обработки или борьбы с нежелательной почтой, достижения в области криптологии» . CRYPTO'92: Конспект лекций по информатике № 740 . Springer: 139–147. DOI : 10.1007 / 3-540-48071-4_10 .
  3. ^ a b «Криптовалюты и блокчейн» (PDF) . Европейский парламент . Июль 2018 . Проверено 29 октября 2020 года . два наиболее известных - и в контексте криптовалют также наиболее часто используемые
  4. ^ а б Лори, Бен; Клейтон, Ричард (май 2004 г.). «Доказательство работы не работает». Практикум по экономике информационной безопасности 2004 года .
  5. ^ Лю, Дебин; Кэмп, Л. Жан (июнь 2006 г.). «Proof of Work может работать - Пятый семинар по экономике информационной безопасности» .
  6. ^ Насколько мощным был компьютер «Аполлон-11»? , конкретное сравнение, показывающее, насколько разные классы устройств имеют разную вычислительную мощность.
  7. ^ а б Абади, Мартин ; Берроуз, Майк; Манассе, Марк; Воббер, Тед (2005). «Умеренно сложные функции, связанные с памятью» . 5 (2): 299–327. Цитировать журнал требует |journal=( помощь )
  8. ^ a b Дворк, Синтия ; Гольдберг, Эндрю ; Наор, Мони (2003). «О функциях борьбы со спамом с привязкой к памяти» . Достижения в криптологии: CRYPTO 2003 . Конспект лекций по информатике. Springer. 2729 : 426–444. DOI : 10.1007 / 978-3-540-45146-4_25 . ISBN 978-3-540-40674-7.
  9. ^ a b Коэльо, Фабьен (2005). «Экспоненциальные функции с ограничением памяти для протоколов доказательства работы» . Cryptology ePrint Archive, Report .
  10. ^ a b Тромп, Джон (2015). «Цикл кукушки; теоретико-графическое доказательство работы с ограничением памяти» (PDF) . Финансовая криптография и безопасность данных: BITCOIN 2015 . Конспект лекций по информатике. Springer. 8976 : 49–62. DOI : 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 . DOI : 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 . DOI : 10.1007 / 3-540-63594-7_75 . ISBN 978-3-540-63594-9. Обновленная версия от 4 мая 1998 г.
  16. ^ Джуэлс, Ари; Брейнард, Джон (1999). «Клиентские головоломки: криптографическая защита от атак с истощением соединения». НДСС 99 .
  17. ^ Уотерс, Брент; Джуэлс, Ари; Halderman, John A .; Фелтен, Эдвард В. (2004). «Новые методы аутсорсинга клиентской головоломки для защиты от DoS-атак» (PDF) . 11-я конференция ACM по компьютерной и коммуникационной безопасности .
  18. ^ Коэльо, Фабьен (2007). «Протокол доказательства работы (почти) постоянных усилий для проверки решения, основанный на деревьях Меркла» . Cryptology ePrint Archive, Report .
  19. ^ «Многоразовые доказательства работы» . Архивировано из оригинального 22 декабря 2007 года.
  20. ^ «Кембриджский индекс потребления электроэнергии в биткойнах» . Кембриджский центр альтернативных финансов . Проверено 30 сентября 2020 .
  21. ^ Майкл Дж. Кейси; Поль Винья (16 июня 2014 г.). «Краткосрочные исправления для предотвращения« атаки 51% » » . Деньги бьют . Wall Street Journal . Проверено 30 июня 2014 года .
  22. ^ Обзор пулов майнинга биткойнов на blockchain.info
  23. ^ Что такое ASIC- майнер на digitaltrends.com
  24. ^ Vorick, Дэвид (13 мая 2018). «Состояние майнинга криптовалюты» .
  25. ^ Савва Шанаев, Арина Шураева, Михаил Васенин и Максим Кузнецов (2019). «Стоимость криптовалюты и атаки 51%: данные исследований событий» . Журнал альтернативных инвестиций . 22 (3): 65–77. DOI : 10.3905 / jai.2019.1.081 . S2CID 211422987 . CS1 maint: использует параметр авторов ( ссылка )

Внешние ссылки [ править ]

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