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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Proof-of-work»)
Перейти к: навигация, поиск

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

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

Примером POW-защиты может служить система Hashcash[1], которая использует хеширование частичной инверсии при отправке по электронной почте. Для расчёта соответствующего заголовка требуется около 252 хэш-вычислений, которые надо пересчитывать для каждой отправки. По предположению авторов, дополнительные расчёты не создают препятствий для отправки нескольких обычных писем, но необходимость постоянного пересчёта делает отправку спама очень ресурсоемкой (по независимым оценкам подобные системы приводят фактически к существенному ограничению количества писем, которые возможно отправить за день с одного компьютера[2]). При этом проверка корректности вычисленного кода является быстрой — используется однократное вычисление SHA-1 с заранее подготовленной меткой.

Другие варианты доказательства выполнения работы используют как базовые элементы сложные криптографические системы. Например, в системе «Биткойн» используется многоуровневое хеширование — хеш предыдущего блока становится элементом последующего. Таким образом нет возможности изменить блок без изменения хешей во всех последующих блоках. Но не всякий хеш признаётся истинным — шестнадцатеричное значение хеш-суммы должно быть меньше значения специального параметра, определяющего сложность майнинга. Для поиска такой хеш-суммы требуется её многократный пересчёт с перебором произвольных значений параметра nonce. Сложность подбирается таким образом, чтобы при использовании всей вычислительной мощи сети биткоин-майнеров среднее время нахождения хеша было близко к некоторому заданному значению. Например, время формирования блока в сети «Биткойн» составляет около 10 минут. Соответственно, любое изменение информации в сформированном блоке потребует аналогичной затраты вычислительных ресурсов для пересчёта хеша изменённого блока и каждого последующего. При этом проверка целостности цепочки ограничена однократным вычислением хешей текущего блока и предыдущего, что не приводит к существенным задержкам.

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

Эксперты продолжают обсуждать, является ли POW-защита достаточно эффективной против DoS-атак и спама[3][4]. В теории алгоритмов существует гипотеза о примерном равенстве времени на поиск решения и на проверку истинности предложенного решения. Это одна из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в миллион долларов США.

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

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

  1. Hashcash — A Denial of Service Counter-Measure (2002) (англ.)
  2. «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»
  3. (May 2004) «Proof-of-work proves not to work». WEIS 04.
  4. (June 2006) «Proof of Work can work». Fifth Workshop on the Economics of Information Security.