Кратко

  • Функция ценообразования 1992 года должна была быть умеренно трудной для вычисления, лёгкой для проверки и не позволять распределять одну вычислительную затрату между множеством получателей.
  • Исключения входили в архитектуру: орган ценообразования мог выдавать быстрый путь доверенным агентам, а получатель — освобождать знакомых корреспондентов. Позднейшая работа с памятью показала, как разное оборудование меняет фактическую цену.

Преимущество нежелательной рассылки не в том, что первое письмо бесплатно. Почти бесплатна следующая копия. Текст и программа используются снова, тогда как внимание, хранение и фильтрация оплачиваются каждым получателем заново.

В работе Pricing via Processing or Combatting Junk Mail, предварительная версия которой была представлена на CRYPTO ’92, Cynthia Dwork и Moni Naor перенесли цену на сам запрос. Отправитель вычисляет умеренно сложную функцию, прикладывает результат к письму, а принимающая система дёшево проверяет его до доставки.

Главным было не простое расходование процессорного времени. Функция не должна была допускать амортизацию: решение одной задачи не обязано заметно удешевлять длинную серию следующих. Если однажды купленное доказательство годится для миллиона адресов, оно остаётся фиксированным расходом и не меняет экономику массовой отправки.

Доказательство, принадлежащее запросу

Вход мог включать сообщение, время и адрес назначения. Новый получатель означал новую задачу; изменённый текст — тоже. Временная метка позволяла отклонять устаревший результат. Повторяемое злоумышленником действие тем самым требовало повторяемой работы.

Проверка должна быть намного дешевле создания. Иначе атакующий сможет присылать дешёвые подделки, вынуждая сервер дорого их отвергать, и защитный механизм сам усилит отказ в обслуживании. Требовалась обратная асимметрия: запрашивающая сторона несёт расход, управляющий ресурсом принимает лёгкое решение.

Предложенные функции заимствовали идеи из теории чисел и намеренно ослабленных криптографических конструкций: извлечение квадратных корней по модулю простого числа, вариант Fiat–Shamir и повторное применение взломанной схемы Ong–Schnorr–Shamir. Целью была не непреодолимая защита секрета, а настраиваемая ступень между лёгким и практически невозможным.

Авторы отмечали, что теория мало говорит об «умеренно трудных» функциях. Криптография часто спрашивает, можно ли перейти стену. Цена должна учитывать, сколько переходов выполняется параллельно, помогает ли предварительная подготовка и когда быстрые машины сделают ступень ниже. Экономическое правило оказалось встроено в алгоритм.

Исключение указывает на управляющего

Большой объём не всегда означает злоупотребление. Объявление конференции или профессиональная рассылка могут быть нужны тысячам людей. Полная цена для каждой копии подавляла бы полезную групповую связь вместе со спамом.

Поэтому в статье предусмотрен быстрый путь. Орган ценообразования может дать доверенным агентам сведения, удешевляющие вычисление; одобренная массовая почта получает масштаб на условиях управляющего. Получатель отдельно ведёт список постоянных корреспондентов, которым доказательство не нужно, и список безусловно запрещённых отправителей.

Эти детали лишают математический барьер видимости нейтральности. Кто-то выбирает функцию, трудность и обладателей быстрого пути. Получатель выбирает границу знакомых отношений. Вычисление подтверждает расход, но не решает, какая организация заслуживает освобождения.

Дешёвый способ вычислить функцию цены отличается от утечки ключа шифрования. Если им пользуются немногие, ущерб ограничен; массовая эксплуатация проявится возвращением злоупотребления, после чего функцию или ключ можно заменить. Но для этого всё равно нужен субъект, способный заметить отклонение, установить новую цену и провести переход.

Оборудование меняет счёт

В 2003 году Dwork, Andrew Goldberg и Naor вернулись к вопросу в On Memory-Bound Functions for Fighting Spam. Работа, ограниченная процессором, занимает разное время на быстром сервере и старом компьютере. Массовый отправитель может купить скидку, недоступную обычному пользователю.

Авторы исследовали разбросанные обращения к памяти, поскольку задержки памяти на испытанных машинах различались меньше, чем скорость процессоров. Отправитель должен был выполнять много независимых обращений, а проверяющий — гораздо меньше или ни одного. Доказательство привязывалось к сообщению, отправителю, получателю и дате; повторы и просроченные результаты отвергались.

Экспериментальный результат имел границы: конкретная реализация работала примерно в четыре раза медленнее на устройстве 233 МГц, чем на станции 3,06 ГГц. Это не доказывает равенство любых устройств. Авторы даже усомнились, всегда ли оно нужно: дорогая аппаратура для спамера может быть полезным барьером, а слабый клиент — передать вычисление сервису. Распределение цены осталось частью проекта.

Влияние не означает тождество

Запись Harvard о публикации, интеллектуальная биография Dwork и страница Microsoft Research помещают работу в широкую карьеру, включающую распределённые системы, криптографию, дифференциальную приватность и алгоритмическую справедливость. Harvard отмечает её влияние на криптовалюты.

Но линия влияния не делает текст 1992 года описанием Bitcoin. В нём нет цепочного консенсуса, выпуска или выбора ветви. Его долговечный предмет иной: перед доступом к ресурсу потребовать свидетельство намеренно понесённой, привязанной к запросу и неповторно используемой стоимости.

Работа разделяет пять вопросов: какой ресурс дефицитен? к какому запросу привязано вычисление? можно ли его заранее подготовить, продать, повторить или амортизировать? сколько стоит проверка? кто меняет цену и выдаёт исключения? Название «доказательство работы» само на них не отвечает.