Доказательство выполнения работы
Доказательство выполнения работы (англ. Proof-of-work, POW, PoW) — принцип защиты распределенных систем от злоупотребления услугами (например, DoS-атак или рассылок спама), основанный на необходимости выполнения запрашивающей стороной некоторой достаточно сложной длительной работы (POW-задачи), результат которой легко и быстро проверяется обслуживающей стороной (односторонняя функция). Главная особенность этих схем заключается в асимметрии затрат времени — длительность для инициатора запроса и высокая скорость для ответа. Подобные схемы также известны как client puzzle (функция клиентской головоломки), computational puzzle (вычислительная головоломка), или CPU pricing function.
Не следует путать этот способ защиты с капчами, которые предлагают задачи, лёгкие для человека, но трудноразрешимые или вовсе неразрешимые для компьютера. POW-задачи изначально не предназначены для человека, их решение компьютером всегда достижимо в конечные сроки, но требует выполнения большого количества операций. При этом для проверки полученного решения требуется относительно малое количество операций.
Примером POW-защиты может служить система Hashcash[1], которая использует хеширование частичной инверсии при отправке по электронной почте. Для расчёта соответствующего заголовка требуется около 252 хэш-вычислений, которые надо пересчитывать для каждой отправки. Необходимость постоянного пересчета делает отправку спама очень ресурсоемкой, но не создает препятствий для отправки обычной почты. При этом для проверки корректности вычисленного кода используется однократное вычисление SHA-1 с заранее подготовленной меткой.
Другие варианты доказательства выполнения работы используют как базовые элементы сложные криптографические системы. Например, в системе «Биткойн» используется многоуровневое хеширование — хеш предыдущего блока становится элементом последующего. Таким образом нет возможности изменить блок без изменения хешей во всех последующих блоках. Но не всякий хеш признаётся истинным — шестнадцатеричное значение хеш-суммы должно быть меньше значения специального параметра, определяющего сложность майнинга. Для поиска такой хеш-суммы требуется её многократный пересчёт с перебором произвольных значений параметра nonce. Сложность подбирается таким образом, чтобы при использовании всей вычислительной мощи сети биткоин-майнеров среднее время нахождения хеша было близко к некоторому заданному значению. Например, время формирования блока в сети «Биткойн» составляет около 10 минут. Соответственно, любое изменение информации в сформированном блоке потребует аналогичной затраты вычислительных ресурсов для пересчёта хеша изменённого блока и каждого последующего. При этом проверка целостности цепочки ограничена однократным вычислением хешей текущего блока и предыдущего, что не приводит к существенным задержкам.
Потенциальная уязвимость
Эксперты продолжают обсуждать, является ли POW-защита достаточно эффективной против DoS-атак и спама[2][3]. В теории алгоритмов существует гипотеза о примерном равенстве времени на поиск решения и на проверку истинности предложенного решения. Это одна из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в миллион долларов США.
См. также
- Proof-of-stake
- Капча
- Bitmessage
- Равенство классов P и NP
- Криптосистема с открытым ключом
- Односторонняя функция
Напишите отзыв о статье "Доказательство выполнения работы"
Примечания
- ↑ Hashcash — A Denial of Service Counter-Measure (2002) (англ.)
- ↑ (May 2004) «[www.cl.cam.ac.uk/~rnc1/proofwork.pdf Proof-of-work proves not to work]». WEIS 04.
- ↑ (June 2006) «[weis2006.econinfosec.org/docs/50.pdf Proof of Work can work]». Fifth Workshop on the Economics of Information Security.
Отрывок, характеризующий Доказательство выполнения работы
– А шуба где? – сказал Долохов. – Эй, Игнатка! Поди к Матрене Матвеевне, спроси шубу, салоп соболий. Я слыхал, как увозят, – сказал Долохов, подмигнув. – Ведь она выскочит ни жива, ни мертва, в чем дома сидела; чуть замешкаешься, тут и слезы, и папаша, и мамаша, и сейчас озябла и назад, – а ты в шубу принимай сразу и неси в сани.Лакей принес женский лисий салоп.
– Дурак, я тебе сказал соболий. Эй, Матрешка, соболий! – крикнул он так, что далеко по комнатам раздался его голос.
Красивая, худая и бледная цыганка, с блестящими, черными глазами и с черными, курчавыми сизого отлива волосами, в красной шали, выбежала с собольим салопом на руке.
– Что ж, мне не жаль, ты возьми, – сказала она, видимо робея перед своим господином и жалея салопа.
Долохов, не отвечая ей, взял шубу, накинул ее на Матрешу и закутал ее.
– Вот так, – сказал Долохов. – И потом вот так, – сказал он, и поднял ей около головы воротник, оставляя его только перед лицом немного открытым. – Потом вот так, видишь? – и он придвинул голову Анатоля к отверстию, оставленному воротником, из которого виднелась блестящая улыбка Матреши.
– Ну прощай, Матреша, – сказал Анатоль, целуя ее. – Эх, кончена моя гульба здесь! Стешке кланяйся. Ну, прощай! Прощай, Матреша; ты мне пожелай счастья.
– Ну, дай то вам Бог, князь, счастья большого, – сказала Матреша, с своим цыганским акцентом.
У крыльца стояли две тройки, двое молодцов ямщиков держали их. Балага сел на переднюю тройку, и, высоко поднимая локти, неторопливо разобрал вожжи. Анатоль и Долохов сели к нему. Макарин, Хвостиков и лакей сели в другую тройку.
– Готовы, что ль? – спросил Балага.
– Пущай! – крикнул он, заматывая вокруг рук вожжи, и тройка понесла бить вниз по Никитскому бульвару.
– Тпрру! Поди, эй!… Тпрру, – только слышался крик Балаги и молодца, сидевшего на козлах. На Арбатской площади тройка зацепила карету, что то затрещало, послышался крик, и тройка полетела по Арбату.
Дав два конца по Подновинскому Балага стал сдерживать и, вернувшись назад, остановил лошадей у перекрестка Старой Конюшенной.
Молодец соскочил держать под уздцы лошадей, Анатоль с Долоховым пошли по тротуару. Подходя к воротам, Долохов свистнул. Свисток отозвался ему и вслед за тем выбежала горничная.
– На двор войдите, а то видно, сейчас выйдет, – сказала она.
Долохов остался у ворот. Анатоль вошел за горничной на двор, поворотил за угол и вбежал на крыльцо.
Гаврило, огромный выездной лакей Марьи Дмитриевны, встретил Анатоля.
– К барыне пожалуйте, – басом сказал лакей, загораживая дорогу от двери.
– К какой барыне? Да ты кто? – запыхавшимся шопотом спрашивал Анатоль.
– Пожалуйте, приказано привесть.
– Курагин! назад, – кричал Долохов. – Измена! Назад!
Долохов у калитки, у которой он остановился, боролся с дворником, пытавшимся запереть за вошедшим Анатолем калитку. Долохов последним усилием оттолкнул дворника и схватив за руку выбежавшего Анатоля, выдернул его за калитку и побежал с ним назад к тройке.
Марья Дмитриевна, застав заплаканную Соню в коридоре, заставила ее во всем признаться. Перехватив записку Наташи и прочтя ее, Марья Дмитриевна с запиской в руке взошла к Наташе.
– Мерзавка, бесстыдница, – сказала она ей. – Слышать ничего не хочу! – Оттолкнув удивленными, но сухими глазами глядящую на нее Наташу, она заперла ее на ключ и приказав дворнику пропустить в ворота тех людей, которые придут нынче вечером, но не выпускать их, а лакею приказав привести этих людей к себе, села в гостиной, ожидая похитителей.
Когда Гаврило пришел доложить Марье Дмитриевне, что приходившие люди убежали, она нахмурившись встала и заложив назад руки, долго ходила по комнатам, обдумывая то, что ей делать. В 12 часу ночи она, ощупав ключ в кармане, пошла к комнате Наташи. Соня, рыдая, сидела в коридоре.
