Hashcash

Анна хоче надіслати Павлові електронного листа. Ще одна копія майже нічого їй не коштує, але таку саму перевагу має розсилач мільйонів рекламних повідомлень. Hashcash додає невелику перешкоду: комп’ютер відправника спершу створює обчислювальну марку. Витрачаються час та енергія, а не гроші на поштові послуги. Adam Back оголосив про свою реалізацію 28 березня 1997 року, а 2002 року опублікував технічний опис. Подібну ідею ще 1992 року досліджували Cynthia Dwork і Moni Naor. Hashcash є частиною цієї історії пошуку засобів проти зловживання мережею. [1] [12]

Хеш — це відбиток фіксованої довжини, обчислений із даних. Програма Анни змінює пробне значення в марці й знову обчислює відбиток, доки той не починається з потрібної кількості нульових бітів. Біт — двійкова цифра: нуль або одиниця. Для b нулів імовірність успіху однієї спроби приблизно дорівнює 2^-b, а середня кількість спроб — 2^b. За b = 20 це в середньому 1048576 обчислень, а не обов’язкове точне число. Іноді щастить одразу, іноді пошук триває довше. Павло перевіряє готову марку одним обчисленням хешу, але окремо має перевірити її дані та правила приймання. [10] [11]

Якби Анна могла додати одну марку до мільйона листів, перешкода втратила б сенс. Тому марка вказує конкретного одержувача або сервіс і дату. Одержувач перевіряє чинність та обліковує прийняті марки, щоб відхиляти повторне використання, тобто replay. Самі дата чи прив’язка до вмісту не завадять повторно надіслати той самий лист. У Hashcash немає спільного глобального реєстру витрачання: потрібну перевірку виконує сервіс-одержувач. Правильний хеш ще не означає, що марку можна прийняти знову. [11] [12]

Необхідну складність задає сервіс-одержувач. Кожен додатковий нульовий біт приблизно подвоює середню роботу. Слабка вимога майже не затримує спамера, сильна обтяжує і звичайну людину. Тому число 20 — приклад, а не вічний стандарт безпеки. До того ж однакова кількість спроб займає різний час на старому телефоні й швидкому комп’ютері. Сервіс має враховувати продуктивність пристроїв, строк чинності та власні можливості. Hashcash не змушує всіх витрачати однакову кількість секунд. [10] [11]

Обчислення не відрізняє порядну людину від нападника. Спамер із багатьма комп’ютерами або ботнетом, мережею захоплених пристроїв, може розподілити роботу й перекласти частину витрат на інших людей. Тим часом звичайний користувач витрачає заряд батареї. Hashcash покликаний змінити економіку атаки, а не гарантувати зникнення спаму. Марка також не шифрує лист, не підтверджує справжнє ім’я відправника та не гарантує доставку. Це одна з умов приймання, яку сервіс може поєднувати з іншим захистом. [10]

Версія 1 має формат 1:bits:date:resource:ext:rand:counter. Поля означають версію, заявлену складність, дату, одержувача чи сервіс, розширення, випадкове значення та змінюваний лічильник. Поле bits вказує, скільки початкових нульових бітів, за твердженням відправника, має відбиток, а не скільки спроб насправді виконав комп’ютер. Ці назви є частиною технічного формату й не перекладаються. Класична реалізація обчислює SHA-1 для всього рядка. Умову має виконувати справжній відбиток, а не лише число, вписане в bits. Це опис історичного формату, а не рекомендація SHA-1 для нових безпекових рішень. Bitcoin використовує інший формат даних та іншу хеш-функцію. [11] [13]

Тут шукають вхідні дані, відбиток яких має наперед визначений початок. Такі вхідні дані називають partial preimage: їхній відбиток відповідає заданій частині, а решта відбитка може бути довільною. Колізія натомість виникає, коли два різні набори даних дають однаковий відбиток. У деяких історичних текстах ужито менш точний вираз partial collision, але для розуміння роботи різниця важлива. Атака, що знаходить колізії SHA-1, не розв’язує автоматично задачу потрібного початку. Це, однак, не робить SHA-1 доречним універсальним вибором для сучасної безпеки. [10] [11] [13]

У 2004 році Hal Finney представив RPOW, Reusable Proofs of Work. Користувач міг подати доказ роботи й отримати новий токен; під час подальшої передачі старий токен ставав недійсним і замінювався новим. Повторне використання не означало необмежене копіювання тієї самої марки. Система спиралася на сервер із захищеним модулем IBM 4758 і віддалену перевірку виконуваної програми. Це зменшувало довіру до оператора, але зберігало припущення щодо обладнання та виробника. RPOW був експериментальним попередником, а не децентралізованим консенсусом Bitcoin. [7] [15]

Bitcoin Whitepaper прямо посилається на Hashcash Бека. Сатоші використав ту саму нерівність витрат: для пошуку потрібні повторні спроби, а перевірка проста. Майнери Bitcoin шукають дійсний заголовок блока, що узагальнює блок транзакцій і посилається на попередній блок. Вони застосовують double SHA-256, тобто два послідовні обчислення SHA-256, і порівнюють результат із числовою межею target. Це не поштова марка SHA-1, покладена в гаманець. Спільним є принцип, а не вся система. [8] [14]

Поштова оплата задає ціну окремого запиту. Грошам також потрібна відповідь, який із двох суперечливих переказів чинний. Bitcoin з’єднує блоки, а його вузли обирають серед дійсних гілок ланцюг із найбільшою накопиченою роботою. Вузли — комп’ютери, що перевіряють правила, — контролюють також транзакції та дозволений випуск монет. Навіть величезна робота не зробить недійсну транзакцію дійсною. Hashcash надав важливу складову; лише її поєднання з іншими правилами дозволило вести спільну грошову історію без центрального адміністратора. [8] [9]