Доказательство выполнения работы (англ. proof-of-work, POW, PoW) — принцип защиты сетевых систем от злоупотребления услугами (например, от DoS-атак, организации рассылок спама или публикации своей, альтернативной, версии цепочек блоков в блокчейн). Идея в том, что можно настолько усложнить клиенту доступ к обращениям на сервер, что злоупотребления массовыми обращениями станут принципиально нерентабельными. Для этого при каждом обращении к серверу клиент должен предоставить результат выполнения некоторой достаточно длительной работы (например, решение задачи), результат которой легко и быстро проверяется на стороне сервера (см. односторонняя функция). Главная особенность применяемых вычислений заключается в асимметрии затрат времени — они значительны на нахождение решения и весьма малы для проверки[1]. Подобные схемы также известны как client puzzle (функция клиентской головоломки), computational puzzle (вычислительная головоломка), или CPU pricing function.
Не следует путать этот способ защиты с капчами, которые предлагают задачи, лёгкие для человека, но трудные или вовсе неразрешимые для компьютера. Доказательство выполнения работы изначально ориентировано на нахождение решения по заранее известному алгоритму за некоторое конечное время, но для проверки полученного решения требуется относительно малое количество операций[1]. Наибольшее распространение и развитие POW-технологии получили в криптовалютных системах.
Впервые выдвижение требования доказательства выполнения работы приведено в статье «Pricing via Processing or Combatting Junk Mail»[1] в 1993 году. Авторы предложили следующую идею: для доступа к общему ресурсу пользователь должен вычислить некоторую функцию, весьма сложную и ресурсоёмкую, но при этом решаемую за приемлемое время. Вычисление функции на стороне клиента должно быть гораздо сложнее, чем проверка результата на стороне сервера. Одним из обязательных требований к функции является её неамортизируемость — при нахождении нескольких решений времени требовалось бы пропорционально их количеству. По предположению авторов, подобные дополнительные расчёты не создают препятствий для отправки нескольких обычных писем с компьютера рядового пользователя, но необходимость постоянных вычислений делает отправку спама очень ресурсоёмкой. По независимым оценкам, подобные системы приводят фактически к существенному ограничению количества писем, которые возможно отправить за день с одного компьютера[2].
В 1997 году Адам Бэк запустил проект Hashcash, посвящённый защите от спама. Задача формулировалась следующим образом: «Найти такое значение x, что хеш SHA(x) содержал бы N старших нулевых бит».
В 1999 году появляется термин proof of work — использован он был в статье «Proofs of Work and Bread Pudding Protocols» (авторы — Маркус Якобссон и Ари Джуелс) в журнале Communications and Multimedia Security[3].