Доказ виконаної роботи

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

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

Прикладом POW-захисту може служити система Hashcash^[2] , яка використовує хешування часткової інверсії при відправці електронною поштою. Для розрахунку відповідного заголовка потрібно близько 2⁵² хеш-обчислень, які треба перераховувати для кожної відправки. Необхідність постійного перерахунку робить відправку спаму дуже ресурсномісткою, але не створює перешкод для відправки звичайної пошти. При цьому для перевірки коректності обчисленого коду використовується одноразове обчислення SHA-1 із заздалегідь підготовленою міткою.

Інші варіанти доказів виконання роботи використовують як базові елементи складної криптографічної системи. Наприклад, у системі Біткойн використовується багаторівневе хешування — хеш попереднього блоку стає елементом подальшого. Таким чином немає можливості змінити блок без зміни хешів у всіх наступних блоках. Але не всякий хеш визнається істинним — шістнадцяткове значення хеш-суми повинно бути менше значення спеціального параметра, що визначає складність майнінгу. Для пошуку такої хеш-суми потрібен її багаторазовий перерахунок з перебором довільних значень параметра nonce. Складність підбирається таким чином, щоб при використанні всієї обчислювальної потужності мережі середній час знаходження хешу було близьким до деякого заданого значення. Наприклад, час формування блоку в мережі Біткойн становить близько 10 хвилин. Відповідно, будь-яка зміна інформації в сформованому блоці потребує аналогічної витрати обчислювальних ресурсів для перерахунку хешу зміненого блоку і кожного наступного. При цьому перевірка цілісності ланцюжка обмежена одноразовим обчисленням хешів поточного блоку і попереднього, що не призводить до істотних затримок.

Потенційна уразливість

Експерти продовжують обговорювати, чи є POW-захист досить ефективною проти DoS-атак і спаму^[3][4]. У теорії алгоритмів існує гіпотеза про приблизну кількість часу на пошук рішення і на перевірку істинності запропонованого рішення. Це одне з семи завдань тисячоліття, за вирішення якої Математичний інститут Клея призначив премію в мільйон доларів США.

Див. також

• CAPTCHA
• Біткойн
• Асиметричні алгоритми шифрування
• Одностороння функція
• Атака 51 %

Примітки

1. Lachtar, Nada; Elkhail, Abdulrahman Abu; Bacha, Anys; Malik, Hafiz (2020-07). A Cross-Stack Approach Towards Defending Against Cryptojacking. IEEE Computer Architecture Letters. Т. 19, № 2. с. 126—129. doi:10.1109/LCA.2020.3017457. ISSN 1556-6064. Процитовано 20 березня 2023.
2. ftp://sunsite.icm.edu.pl/site/replay.old/programs/hashcash/hashcash.pdf
3. Архівована копія (PDF). Архів оригіналу (PDF) за 20 січня 2017. Процитовано 17 жовтня 2016.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)
4. Архівована копія (PDF). Архів оригіналу (PDF) за 29 квітня 2016. Процитовано 17 жовтня 2016.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)