Алгоритмы / Proof-of-Work

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

Применение:

• Hashcash использует ресурсоёмкое по причине заданного многократного повторения хеширование при отправке по электронной почте и однократное хэширование для проверки;
• Bitcoin использует связное ресурсоёмкое (по причине искуственно налагаемых условий к результатам) хеширование для добавления блоков транзакций в цепочку и однократное хэширование текущего и предыдущего блоков для проверки.

Существует гипотетическая уязвимость данного типа алгоритмов, так как в теории алгоритмов существует не доказанная гипотеза о примерном равенстве времени на поиск решения и на проверку истинности предложенного решения.