Hashcash

Анна хочет отправить Павлу электронное письмо. Ещё одна копия почти ничего ей не стоит, но такое же преимущество есть у отправителя миллионов рекламных сообщений. Hashcash добавляет небольшое препятствие: компьютер отправителя сначала создаёт вычислительную марку. Затраты — время и энергия, а не деньги почте. Adam Back объявил о своей реализации 28 марта 1997 года и опубликовал техническое описание в 2002 году. Похожую идею Cynthia Dwork и Moni Naor исследовали ещё в 1992 году. 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]