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

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

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

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

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

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

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

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

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

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

  1. Hashcash — A Denial of Service Counter-Measure (2002)
  2. (May 2004) «Proof-of-work proves not to work». WEIS 04.
  3. (June 2006) «Proof of Work can work». Fifth Workshop on the Economics of Information Security.