Доказательство работы

Система, регулирующая формирование блоков в блокчейне

Доказательство работы ( PoW ) — это форма криптографического доказательства , в которой одна сторона ( доказывающая ) доказывает другим ( проверяющим ), что было затрачено определенное количество определенных вычислительных усилий. ^[1] Контролеры могут впоследствии подтвердить эти расходы с минимальными усилиями со своей стороны. Эта концепция была изобретена Мони Наором и Синтией Дворк в 1993 году как способ предотвращения атак типа «отказ в обслуживании» и других злоупотреблений услугами, таких как спам в сети, путем требования некоторой работы от запрашивающей службы, обычно подразумевающей время обработки компьютером. Термин «доказательство работы» был впервые придуман и формализован в статье Маркуса Якобссона и Ари Джуэлса в 1999 году. ^{[2] [3]} Эта концепция была адаптирована к цифровым токенам Хэлом Финни в 2004 году посредством идеи «многоразового доказательства работы» с использованием 160-битного безопасного алгоритма хеширования 1 (SHA-1). ^{[4] [5]}

Доказательство работы позже было популяризировано Биткойном как основа для консенсуса в не требующей разрешения децентрализованной сети, в которой майнеры конкурируют за добавление блоков и добычу новой валюты, причем вероятность успеха каждого майнера пропорциональна затраченным вычислительным усилиям. PoW и PoS ( доказательство доли ) остаются двумя наиболее известными механизмами сдерживания Сивиллы . В контексте криптовалют это наиболее распространенные механизмы. ^[6]

Ключевой особенностью схем доказательства работы является их асимметрия: работа ( вычисление) должна быть умеренно сложной (но выполнимой) со стороны проверяющей или запрашивающей стороны, но легко проверяемой проверяющей стороной или поставщиком услуг. Эта идея также известна как функция стоимости ЦП, клиентская головоломка , вычислительная головоломка или функция ценообразования ЦП. Еще одной общей особенностью являются встроенные структуры стимулирования , которые вознаграждают за выделение вычислительных мощностей сети в виде криптовалюты. ^{[7] [8]}

Целью алгоритмов доказательства работы является не доказательство того, что определенная работа была выполнена или что вычислительная головоломка была «решена», а предотвращение манипулирования данными путем установления больших требований к энергии и аппаратному контролю, чтобы иметь возможность сделать это. ^[7] Системы Proof-of-Work подвергаются критике со стороны экологов за их энергопотребление. ^[9]

Фон

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

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

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

0000000000000756af69e2ffbdb930261873cd71

Могут ли системы PoW действительно решить конкретную проблему отказа в обслуживании, например проблему спама, является предметом споров; ^{[10] [11]} система должна сделать рассылку спам-сообщений навязчиво непродуктивной для спамера, но также не должна мешать законным пользователям отправлять свои сообщения. Другими словами, настоящий пользователь не должен столкнуться с какими-либо трудностями при отправке электронного письма, но спамеру электронной почты придется затратить значительный объем вычислительной мощности для одновременной отправки большого количества электронных писем. Системы Proof-of-Work используются другими, более сложными криптографическими системами, такими как биткойн , который использует систему, аналогичную Hashcash. ^[10]

Варианты

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

• Протоколы запрос-ответ предполагают прямую интерактивную связь между запрашивающим (клиентом) и провайдером (сервером). Поставщик выбирает вызов, скажем, элемент в наборе со свойством, запрашивающий находит в наборе соответствующий ответ, который отправляется обратно и проверяется поставщиком. Поскольку провайдер выбирает задачу на месте, ее сложность можно адаптировать к текущей нагрузке. Работа на стороне запрашивающей стороны может быть ограниченной, если протокол запроса-ответа имеет известное решение (выбранное поставщиком) или известно, что он существует в ограниченном пространстве поиска.

• Протоколы решения-проверки не предполагают такой связи: в результате проблема должна быть создана сама собой до того, как запрашивающая сторона будет искать решение, а провайдер должен проверить как выбор проблемы, так и найденное решение. Большинство таких схем представляют собой неограниченные вероятностные итеративные процедуры, такие как Hashcash .

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

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

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

• Привязка к процессору , когда вычисления выполняются со скоростью процессора, которая сильно варьируется во времени , а также от высокопроизводительного сервера до недорогих портативных устройств. ^[12]
• С привязкой к памяти ^{[13] [14] [15] [16]} , где скорость вычислений ограничена доступом к основной памяти (либо задержкой, либо пропускной способностью), производительность которой, как ожидается, будет менее чувствительна к развитию оборудования.
• С привязкой к сети ^[17] , если клиент должен выполнить мало вычислений, но должен собрать некоторые токены с удаленных серверов перед запросом к конечному поставщику услуг. В этом смысле работа на самом деле не выполняется запрашивающей стороной, но она в любом случае вызывает задержки из-за задержки получения необходимых токенов.

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

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

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

• Целый квадратный корень по модулю большого простого числа ^{[3] [ сомнительно ]}
• Ослабление сигнатур Фиата – Шамира ^[3]
• Подпись Онга-Шнорра-Шамира нарушена Поллардом ^[3]
• Частичная инверсия хеша ^{[18] [19] [2]} Эта статья формализует идею доказательства работы и представляет «зависимую идею протокола хлебного пудинга», систему «многоразового использования доказательства работы» (RPoW). . ^[20]
• Хэш-последовательности ^[21]
• Пазлы ^[22]
• Головоломка на основе Диффи-Хеллмана ^[23]
• Умеренный ^[13]
• Мбаунд ^[14]
• Хоккайдо ^[15]
• Цикл кукушки ^[16]
• На основе дерева Меркла ^[24]
• Протокол головоломки с гидом ^[17]

Доказательство полезной работы (PoUW)

На конференции IACR Crypto 2022 исследователи представили документ, описывающий Ofelimos, протокол блокчейна с механизмом консенсуса , основанным на «доказательстве полезной работы» (PoUW). Вместо того, чтобы майнеры тратили энергию на решение сложных, но по сути бесполезных головоломок для проверки транзакций, Ofelimos достигает консенсуса, одновременно предоставляя децентрализованное решение задач оптимизации . Протокол построен на основе двойного параллельного локального поиска (DPLS), алгоритма локального поиска, который используется в качестве компонента PoUW. В статье приводится пример реализации варианта WalkSAT — алгоритма локального поиска для решения булевых задач. ^[25]

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

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

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

Потребление электроэнергии в биткойнах по состоянию на 2021 год ^[26]

С момента создания Биткойна доказательство работы было преобладающей конструкцией одноранговой криптовалюты. Исследования оценили общее энергопотребление при майнинге криптовалют. ^[27] Механизм PoW требует огромного количества вычислительных ресурсов, которые потребляют значительное количество электроэнергии. По оценкам Кембриджского университета на 2018 год , энергопотребление Биткойна приравнивается к энергопотреблению Швейцарии . ^[6]

Изменение истории

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

ASIC и майнинговые пулы

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

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

Проблемы окружающей среды

Эти майнеры соревнуются за решение крипто-задач в блокчейне Биткойна , и их решения должны быть согласованы всеми узлами и достигнуты консенсуса. Затем решения используются для проверки транзакций, добавления блоков и генерации новых биткойнов. Майнеры получают вознаграждение за решение этих головоломок и успешное добавление новых блоков. Однако процесс майнинга в стиле Биткойн очень энергозатратен, поскольку доказательство работы имеет форму лотерейного механизма. Базовая вычислительная работа не имеет другого применения, кроме обеспечения безопасности сети, которая обеспечивает открытый доступ и должна работать в враждебных условиях. Майнерам приходится использовать много энергии, чтобы добавить в блокчейн новый блок, содержащий транзакцию. Энергия, используемая в этом соревновании, — это то, что принципиально обеспечивает биткойну уровень безопасности и устойчивости к атакам. Кроме того, майнерам приходится инвестировать в компьютерное оборудование, требующее больших площадей, в качестве фиксированной стоимости. ^[34]

В январе 2022 года заместитель председателя Европейского управления по ценным бумагам и рынкам Эрик Тедин призвал ЕС запретить модель доказательства работы в пользу модели доказательства доли из-за ее более низких выбросов энергии. ^[35]

В ноябре 2022 года штат Нью-Йорк ввел двухлетний мораторий на майнинг криптовалют, который не полностью использует возобновляемую энергию в качестве источника энергии в течение двух лет. Существующим горнодобывающим компаниям будет предоставлено право продолжать добычу без использования возобновляемых источников энергии, но им не будет разрешено расширять или продлевать разрешения с государством, ни одним новым горнодобывающим компаниям, которые не полностью используют возобновляемые источники энергии, также не будет разрешено начинать работу. добыча полезных ископаемых. ^[36]

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

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

Примечания

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

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

1. Лахтар, Нада; Эльхаил, Абдулрахман Абу; Бача, Анис; Малик, Хафиз (01 июля 2020 г.). «Межстековый подход к защите от криптоджекинга». Письма IEEE по компьютерной архитектуре . 19 (2): 126–129. дои : 10.1109/LCA.2020.3017457 . ISSN  1556-6056. S2CID  222070383.
2. Якобссон, Маркус; Джулс, Ари (1999). «Доказательства работы и протоколы хлебного пудинга». Безопасные информационные сети: безопасность связи и мультимедиа . Издательство Kluwer Academic: 258–272. дои : 10.1007/978-0-387-35568-9_18 .
3. Дворк, Синтия ; Наор, Мони (1993). «Ценообразование посредством обработки или борьбы с нежелательной почтой». Достижения криптологии — КРИПТО' 92 . Конспекты лекций по информатике. Том. 740. Спрингер. стр. 139–147. дои : 10.1007/3-540-48071-4_10 . ISBN 978-3-540-57340-1.
4. «RPOW - Многоразовые доказательства работы» . nakamotoinstitute.org . Проверено 17 января 2024 г.
5. «Что такое доказательство работы (PoW) в блокчейне?». Инвестопедия . Проверено 17 января 2024 г.
6. «Криптовалюты и блокчейн» (PDF) . Европейский парламент . июль 2018 года . Проверено 29 октября 2020 г. два наиболее известных, а в контексте криптовалют также наиболее часто используемые
7. «Доказательство работы, объясненное простыми словами - Цепной бюллетень» . Chainbulletin.com . Проверено 1 апреля 2023 г.
8. «Единственная криптоистория, которая вам нужна, Мэтт Левайн» . Bloomberg.com . Проверено 1 апреля 2023 г.
9. Хариф, Ольга (30 ноября 2021 г.). «Анализ | Пока, майнеры! Как будут работать большие изменения в Ethereum» . Вашингтон Пост . Новости Блумберга . Проверено 13 января 2022 г.
10. Лори, Бен; Клейтон, Ричард (май 2004 г.). «Доказательство работы не работает». Семинар по экономике информационной безопасности 2004г .
11. Лю, Дебин; Кэмп, Л. Жан (июнь 2006 г.). «Доказательство работы может работать — Пятый семинар по экономике информационной безопасности».
12. Насколько мощным был компьютер Аполлона-11? Конкретное сравнение, показывающее, насколько разные классы устройств имеют разную вычислительную мощность.
13. Абади, Мартин ; Берроуз, Майк; Манасс, Марк; Воббер, Тед (2005). «Умеренно сложные функции, ограниченные памятью». 5 (2): 299–327. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
14. Дворк, Синтия ; Гольдберг, Эндрю ; Наор, Мони (2003). «О функциях, связанных с памятью, для борьбы со спамом». Достижения криптологии — КРИПТО 2003 . Конспекты лекций по информатике. Том. 2729. Спрингер. стр. 426–444. дои : 10.1007/978-3-540-45146-4_25 . ISBN 978-3-540-40674-7.
15. Коэльо, Фабьен (2005). «Экспоненциальные функции с привязкой к памяти для протоколов проверки работоспособности». Архив ePrint по криптологии, отчет .
16. Тромп, Джон (2015). «Цикл кукушки: теоретико-графовое доказательство работы с привязкой к памяти» (PDF) . Финансовая криптография и безопасность данных . Конспекты лекций по информатике. Том. 8976. Спрингер. стр. 49–62. дои : 10.1007/978-3-662-48051-9_4. ISBN 978-3-662-48050-2.
17. Аблиз, Мехмуд; Знати, Тайеб (декабрь 2009 г.). «Экскурсионная головоломка по предотвращению отказов в обслуживании». Ежегодная конференция по приложениям компьютерной безопасности 2009 г. Гонолулу, Гавайи. стр. 279–288. CiteSeerX 10.1.1.597.6304 . дои : 10.1109/ACSAC.2009.33. ISBN  978-1-4244-5327-6. S2CID  14434713.{{cite book}}: CS1 maint: location missing publisher (link)
18. Назад, Адам. «ХэшКэш».Популярная система PoW. Впервые анонсировано в марте 1997 года.
19. Габбер, Эран; Якобссон, Маркус; Матиас, Йоси; Майер, Ален Дж. (1998). «Ограничение нежелательной почты с помощью безопасной классификации». Финансовая криптография .^{[ мертвая ссылка ]}
20. Ван, Сяо-Фэн; Райтер, Майкл (май 2003 г.). «Защита от атак типа «отказ в обслуживании» с помощью аукционов-головоломок» (PDF) . Симпозиум IEEE по безопасности и конфиденциальности '03 . Архивировано из оригинала (PDF) 3 марта 2016 г. Проверено 15 апреля 2013 г.
21. Франклин, Мэтью К .; Малхи, Георгин (1997). «Контролируемый учет с облегченной безопасностью» . Финансовая криптография . Конспекты лекций по информатике. Том. 1318. стр. 151–160. дои : 10.1007/3-540-63594-7_75. ISBN 978-3-540-63594-9.Обновленная версия от 4 мая 1998 г.
22. Джулс, Ари; Брейнард, Джон (1999). «Загадки клиента: криптографическая защита от атак с исчерпанием соединения». НДСС 99 .
23. Уотерс, Брент; Джулс, Ари; Халдерман, Джон А.; Фельтен, Эдвард В. (2004). «Новые методы аутсорсинга головоломок клиентов для устойчивости к DoS» (PDF) . 11-я конференция ACM по компьютерной и коммуникационной безопасности .
24. Коэльо, Фабьен (2007). «Протокол доказательства работы (почти) с постоянными усилиями, основанный на деревьях Меркла». Архив ePrint по криптологии, отчет .
25. Фитци, Матиас. «Комбинаторная оптимизация посредством доказательства полезной работы» (PDF) . Конференция IACR Crypto 2022 . Проверено 9 сентября 2022 г.
26. «Кембриджский индекс потребления электроэнергии в биткойнах (CBECI)» . www.cbeci.org . Проверено 20 февраля 2020 г.
27. «Кембриджский индекс потребления электроэнергии в биткойнах» . Кембриджский центр альтернативных финансов . Проверено 30 сентября 2020 г.
28. Майкл Дж. Кейси; Пол Винья (16 июня 2014 г.). «Краткосрочные меры по предотвращению «атаки 51%»». Денежный бит . Уолл Стрит Джорнал . Проверено 30 июня 2014 г.
29. Обзор пулов для майнинга биткойнов на сайте Blockchain.info.
30. Что такое ASIC-майнер на digitaltrends.com
31. Ворик, Дэвид (13 мая 2018 г.). «Состояние майнинга криптовалюты».
32. tevador/RandomX: Алгоритм доказательства работы, основанный на случайном выполнении кода на Github
33. Савва Шанаев; Арина Шураева; Михаил Васенин; Максим Кузнецов (2019). «Ценность криптовалюты и атаки 51%: данные исследований событий». Журнал альтернативных инвестиций . 22 (3): 65–77. дои : 10.3905/jai.2019.1.081. S2CID  211422987.
34. Киян, Павел; Канч, д'Артис; Райчанёва, Мирослава (21 октября 2021 г.). «Экономическая зависимость безопасности биткойнов». Прикладная экономика . 53 (49): 5738–5755. дои : 10.1080/00036846.2021.1931003 . HDL : 10419/251105 . ISSN  0003-6846. S2CID  231942439.
35. Бейтман, Том (19 января 2022 г.). «Запретите майнинг криптовалюты с доказательством работы для экономии энергии, — говорит регулятор ЕС». Евроньюс . Проверено 22 января 2022 г.
36. Сигалос, Маккензи (23 ноября 2022 г.). «Губернатор Нью-Йорка подписывает первый в своем роде закон о борьбе с майнингом биткойнов — вот все, что в нем есть». CNBC . Проверено 4 декабря 2022 г.

Внешние ссылки

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