Доказ виконаної роботи Див. також | Примітки | Навігаційне менюрвиправивши або дописавши її
КриптографіяКриптовалюти
англ.DoS-атакспамукапчіHashcash«біткоїнів»хеш-сумимайнінгу«Біткоїн»DoS-атакспамутеорії алгоритмівгіпотезаМатематичний інститут Клеядоларів США
Доказ виконання роботи (англ. Proof-of-work, POW) — принцип захисту систем від зловживання послугами (наприклад, DoS-атак або розсилок спаму), заснований на необхідності виконання стороною, яка робить запит (клієнтом) деякої досить складної тривалої роботи (POW-завдання, одностороння функція), результат якої легко і швидко перевіряється стороною, що обробляє запит (сервером) . Головна особливість цих схем полягає в асиметрії витрат часу — тривалість для ініціатора запиту і висока швидкість для відповіді. Подібні схеми також відомі як client puzzle (функція клієнтської головоломки), computational puzzle (обчислювальна головоломка), або CPU pricing function.
Не слід плутати цей спосіб захисту з капчі, які пропонують завдання, легкі для людини, але складні або зовсім нерозв'язні для комп'ютера. POW-завдання не призначені для людини, їх рішення комп'ютером завжди досяжне, але вимагає виконання великої кількості операцій. При цьому для перевірки отриманого рішення потрібна відносно мала кількість операцій.
Прикладом POW-захисту може служити система Hashcash[1] , яка використовує хешування часткової інверсії при відправці по електронній пошті. Для розрахунку відповідного заголовка потрібно близько 252 хеш-обчислень, які треба перераховувати для кожної відправки. Необхідність постійного перерахунку робить відправку спаму дуже ресурсномісткою, але не створює перешкод для відправки звичайної пошти. При цьому для перевірки коректності обчисленого коду використовується одноразове обчислення SHA-1 із заздалегідь підготовленою міткою.
Інші варіанти доказів виконання роботи використовують як базові елементи складної криптографічної системи. Наприклад, у системі «біткоїнів» використовується багаторівневе хешування — хеш попереднього блоку стає елементом подальшого. Таким чином немає можливості змінити блок без зміни хешів у всіх наступних блоках. Але не всякий хеш визнається істинним — шістнадцяткове значення хеш-суми повинно бути менше значення спеціального параметра, що визначає складність майнінгу. Для пошуку такої хеш-суми потрібен її багаторазовий перерахунок з перебором довільних значень параметра nonce. Складність підбирається таким чином, щоб при використанні всієї обчислювальної потужності мережі середній час знаходження хешу було близьким до деякого заданого значення. Наприклад, час формування блоку в мережі «Біткоїн» становить близько 10 хвилин. Відповідно, будь-яка зміна інформації в сформованому блоці потребує аналогічної витрати обчислювальних ресурсів для перерахунку хешу зміненого блоку і кожного наступного. При цьому перевірка цілісності ланцюжка обмежена одноразовим обчисленням хешів поточного блоку і попереднього, що не призводить до істотних затримок.
Потенційна уразливість |
Експерти продовжують обговорювати, чи є POW-захист досить ефективною проти DoS-атак і спаму[2][3]. У теорії алгоритмів існує гіпотеза про приблизну кількість часу на пошук рішення і на перевірку істинності запропонованого рішення. Це одне з семи завдань тисячоліття, за вирішення якої Математичний інститут Клея призначив премію в мільйон доларів США.
Див. також |
- Капча
- Біткоїн
- Асиметричні алгоритми шифрування
- Одностороння функція
Примітки |
↑ ftp://sunsite.icm.edu.pl/site/replay.old/programs/hashcash/hashcash.pdf
↑ http://www.cl.cam.ac.uk/~rnc1/proofwork.pdf
↑ http://www.econinfosec.org/archive/weis2006/docs/50.pdf
| |||||||||||||||||||||||||||||||||||
Категорії
Вікісховище
Список | Це незавершена стаття з криптографії. Ви можете допомогти проекту, виправивши або дописавши її. |
Портал «Програмування»
Портал «Інформаційні технології»
