Доказательство выполнения работы () — принцип защиты сетевых систем от злоупотребления услугами (например, от DoS-атак, организации рассылок спама или публикации своей, альтернативной, версии цепочек блоков в блокчейн). Идея в том, что можно настолько усложнить клиенту доступ к обращениям на сервер, что злоупотребления массовыми обращениями станут принципиально нерентабельными. Для этого при каждом обращении к серверу клиент должен предоставить результат выполнения некоторой достаточно длительной работы (например, решение задачи), результат которой легко и быстро проверяется на стороне сервера (см. односторонняя функция). Главная особенность применяемых вычислений заключается в асимметрии затрат времени — они значительны на нахождение решения и весьма малы для проверки Pricing via Processing or Combatting Junk Mail (1993). Подобные схемы также известны как (функция клиентской головоломки), (вычислительная головоломка) или .
Не следует путать этот способ защиты с капчами, которые предлагают задачи, лёгкие для человека, но трудные или вовсе неразрешимые для компьютера. Доказательство выполнения работы изначально ориентировано на нахождение решения по заранее известному алгоритму за некоторое конечное время, но для проверки полученного решения требуется относительно малое количество операций. Наибольшее распространение и развитие POW-технологии получили в криптовалютных системах.
История Впервые выдвижение требования доказательства выполнения работы приведено в статье «Pricing via Processing or Combatting Junk Mail» в 1993 году. Авторы предложили следующую идею: для доступа к общему ресурсу пользователь должен вычислить некоторую функцию, весьма сложную и ресурсоёмкую, но при этом решаемую за приемлемое время. Вычисление функции на стороне клиента должно быть гораздо сложнее, чем проверка результата на стороне сервера. Одним из обязательных требований к функции является её неамортизируемость — при нахождении нескольких решений времени требовалось бы пропорционально их количеству. По предположению авторов, подобные дополнительные расчёты не создают препятствий для отправки нескольких обычных писем с компьютера рядового пользователя, но необходимость постоянных вычислений делает отправку спама очень ресурсоёмкой. По независимым оценкам, подобные системы приводят фактически к существенному ограничению количества писем, которые возможно отправить за день с одного компьютера«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».
В 1997 году Адам Бэк запустил проект Hashcash, посвящённый защите от спама. Задача формулировалась следующим образом: «Найти такое значение x, что хеш SHA(x) содержал бы N старших нулевых бит».
В 1999 году появляется термин proof of work — использован он был в статье «Proofs of Work and Bread Pudding Protocols» (авторы — Маркус Якобссон и Ари Джуелс) в журнале Communications and Multimedia SecurityProofs of Work and Bread Pudding Protocols (1999).
16 августа 2004 года Хэл Финни в своём письме на форуме шифропанков предложил использовать многоразовое доказательство выполнения работы () для организации электронной валюты RPOW — Reusable Proofs of Work (2004).
Вскоре Сатоси Накамото предложил криптовалюту биткойн, где доказательство выполнения работы использовано для значительного усложнения двойного расходования. Было предложено нахождение хеша блока информации через функцию SHA-256 с подбором параметров, чтобы у результата заданное число старших бит было нулевым. В дальнейшем в других криптовалютах (например Litecoin) вместо SHA-256 стали применяться KDF, такие как scrypt, bcrypt, PBKDF2 и другие The Proof-of-Work in Cryptocurrencies: Brief History. Part 1 (2015).
Примеры применяемых функций Список наиболее распространённых функций, применяемых в системах доказательства выполнения работы: Хеширование частичной инверсии. Наиболее известное применение — система Hashcash Hashcash — A Denial of Service Counter-Measure (2002), которая использует хеширование частичной инверсии при отправке по электронной почте. Для расчёта заголовка одного письма требуется около 252 хеш-вычислений, которые надо пересчитывать для каждого нового письма. При этом проверка корректности вычисленного кода является быстрой — используется однократное вычисление SHA-1 с заранее подготовленной меткой Popular proof-of-work system. First announce in March 1997.. Функции, основанные на деревьях Меркла. Самый известный пример применения данного варианта можно найти в системе Bitcoin, где в качестве доказательства выполнения работы используется многоуровневое хеширование — хеш предыдущего блока становится элементом последующего. Таким образом, нет возможности изменить блок без изменения хешей во всех последующих блоках. При этом проверка целостности всей цепочки ограничена однократным вычислением хешей текущего блока и предыдущего. Хеш признаётся истинным только в том случае, если значение какой-либо характеристики хеш-суммы удовлетворяет выбранному критерию, например в биткойне - количество младших нулей хеш-суммы больше или равно значению специального параметра, определяющего сложность майнинга, требуемую в данный момент для поддержания запланированной скорости появления новых блоков. Для поиска такой хеш-суммы требуется её многократный пересчёт с перебором произвольных значений параметра nonceBitcoin: A Peer-to-Peer Electronic Cash System . Квадратичный вычет по модулю большого простого числа Подпись по протоколу Фиата — Шамира Функция на основе протокола Диффи — Хеллмана Функция, ограниченная по памяти (:en:Memory bound function) Кукушкино хеширование
Потенциальные уязвимости и атаки на информационные системы, основанные на POW Эксперты продолжают обсуждать, является ли POW-защита достаточно эффективной против DoS-атак и спама.
Атака 51 %
Биткойн, как и многие другие криптовалюты, потенциально может подвергаться «атаке 51 %»: если под контролем злоумышленника находится больше половины всех вычислительных мощностей сети, то у него появляется возможность подтверждать только свои блоки, при этом игнорируя чужие. Это не только позволяет ему получать всю эмитирующуюся при этом криптовалюту, но и блокировать все или выбранные транзакции, что потенциально может приводить к «исчезновению» со счетов криптовалюты, полученной по тем транзакциям, которые не будут включены в новый вариант блокчейна.
Двойное расходование Двойное расходование (двойная трата) — повторная передача одних и тех же активов. Данная атака делится на несколько подтипов.
Атака типа «гонки» (). Злоумышленник совершает транзакцию X, оплачивая покупку товара, одновременно переводя эти же деньги на другой свой счёт транзакцией Y. Если продавец не стал ждать подтверждения транзакции и отгрузил товар, то он пошёл на большой риск, так как есть вероятность 50%, что транзакция Y может попасть в истинную цепочку, причём эта вероятность повышается в случае, если злоумышленник целенаправленно выбирает узлы сети для проведения той или иной операцииAttacks in the World of Cryptocurrencies .
Атака Финни заключается в следующем: злоумышленник пытается найти блок, который содержит его транзакцию Y. Однако как только блок обнаруживается, атакующий отправляет транзакцию X, после чего он покупает товар. Продавец дожидается подтверждения транзакции X и отгружает товар. Если в этот момент появляется блок с транзакцией Y, то создаётся ситуация развилки, в которой майнеры должны выбрать один из двух блоков для продолжения цепочки блокчейна. При сосредоточении большого количества вычислительных ресурсов в руках злоумышленника, он может значительно увеличить вероятность выбора блока с операцией Y. Таким образом подтверждённая транзакция не является гарантированно валиднойAnalysis of hashrate-based double-spending (2012).
Эгоистичный майнинг При эгоистичном майнинге () целью злоумышленника является контроль над сетью при том, что он обладает вычислительными ресурсами суммарной мощностью менее 50 %. Это достигается за счёт того, что злоумышленник заявляет, что его пул более выгоден для майнинга, чем другие пулы, что привлекает сторонних майнеров. Атакующий публикует блоки таким образом, чтобы вычислительные ресурсы других майнеров и пулов были потрачены впустую. Приблизительный ход алгоритма такой: Пул тайно от всех майнит свою приватную цепочку. Если пул находит новый блок для своей приватной цепи, то: Если оригинальная цепочка разветвилась, то атакующий публикует свой блок, таким образом его цепочка становится длиннее и становится истинной, а цепь честных майнеров отбрасывается. Если развилки пока нет, то пул продолжает тайно майнить свою приватную цепь, наращивая отрыв. Если публичная цепь находит блок для общедоступной цепи, то: Если публичная цепь опережает тайную, то пул злоумышленника отбрасывает свои неопубликованные блоки и начинает майнить с нового публичного блока. Если цепи сравнялись, то пул злоумышленника публикует все свои блоки, таким образом уходя в отрыв в своей цепи. Если публичная цепь отстаёт на некоторое количество (N) блоков от приватной, то пул публикует на один блок больше (N+1), что изолирует новый честный блок. Почти при каждом исходе честные майнеры оказываются в проигрыше, что вынуждает их присоединиться к преступному пулуAttacks in the World of Cryptocurrencies (2015).
Критика информационных систем на основе POW Противники POW-подхода, помимо ряда потенциальных проблем с безопасностью, выделяют следующие недостатки: Вероятность успешного создания следующего блока майнером прямо пропорциональна вычислительным мощностям, которыми он обладает, что приводит к постоянному наращиванию количества и качества оборудования каждого участника сети. Таким образом, майнинг с применением POW-алгоритмов требует чрезвычайно много электроэнергии. Поэтому POW-подход является не самым лучшим решением с точки зрения энергоэффективностиBitcoin Energy Consumption Index Ethereum Energy Consumption Index (beta) . Результаты вычисления хеш-функций нигде, кроме как в самой сети, не нужны. С момента появления технологии сообщество пыталось придумать способ направить все вычислительные ресурсы сети на решение какой-либо полезной математической или промышленной задачи, но в чистом виде это не удалось реализоватьThe Proof-of-Work in Cryptocurrencies: Brief History. Part 2 . Попытки избавиться от недостатков POW привели к появлению POS (, доказательство доли владения) и многочисленных гибридных вариантов.
Примеры гибридных технологий Примеры гибридных схем, совмещающих идеи POS и POW, можно найти во многих криптовалютах. В них блокчейн состоит из блоков обоих типов, что делает переписывание историй транзакций непростой задачей, так как POW-блоки служат контрольными точками, если брать во внимание суммарную сложность работы во всей цепочке. Обычно в таких алгоритмах POW-блоки служат показателями реальной работы, что даёт дополнительную гарантию надёжности для продавцов при работе с транзакциями. POW-блоки можно использовать для эмиссии валюты, а POS-блоки - рассматривать как потенциальный доход от депозитаAlternatives for Proof of Work, Part 2 (2015).
Proof of activity Нереализованный пока прототип алгоритма, заключающийся в том, что холдеры вступают в общий процесс только после проведения некоторой работы POW-участниками, что уменьшает шансы на атаку 51 %, так как мажоритарный владелец не сможет единолично контролировать создание новых блоковProof of Activity: Extending Bitcoin’s Proof of Work via Proof of Stake .
Принцип работы алгоритма: POW-майнер ищет хеш соответствующей сложности. Найденный хеш отправляется в сеть, при этом являясь не блоком, а лишь первым шагом, своеобразным шаблоном, необходимым для его создания. Хеш, состоящий из 256 псевдослучайных бит, интерпретируется как N чисел, к каждому из которых в соответствие ставится один сатоси. Устанавливается взаимно однозначная связь между каждым сатоси и публичным ключом его текущего владельца.