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