26 августа 1998 года Хэл Финни выступил на конференции Crypto 98 с докладом "A zero-knowledge proof of possession of a pre-image of a SHA-1 hash"

Хэл Финни на Crypto 98 рассказывал о практической реализации элегантного криптографического метода, который позволял доказывать владение секретом (в данном случае, данными, соответствующими хэшу SHA-1), не раскрывая его. Это был важный шаг в применении теории нулевых разглашений к реальным задачам безопасности и приватности, что было ключевой темой для сообщества шифропанков и впоследствии стало одной из основ философии криптовалют.

Это выступление Хэла Финни было важным и очень своевременным докладом в области криптографии и безопасности. Если кратко, он рассказывал о практической реализации «доказательства с нулевым разглашением» (Zero-Knowledge Proof, ZKP) для конкретной задачи: доказать, что вы знаете исходные данные (прообраз) для заданного хэша SHA-1, не раскрывая при этом сами эти данные.

Суть доклада

Проблема: Как убедить кого-то («верификатора»), что вы знаете некий секрет X, не показывая его? При этом верификатор должен быть на 100% уверен в вашем знании.
Конкретный пример: Допустим, есть хэш-значение H = SHA-1(X). Вы хотите доказать, что знаете X, который дает именно этот хэш H, но не хотите раскрывать X в открытом виде (например, потому что X является вашим паролем, приватным ключом или другой ценной информацией).
Решение: Хэл Финни описывал протокол, основанный на одном из классических вариантов ZKP — «Доказательстве с нулевым разглашением для изоморфизма графов». Идея этого протокола (в упрощенном виде) выглядит так:

Входные данные: У вас есть два графа, которые изоморфны (имеют одинаковую структуру, но по-разному обозначены). Знание изоморфизма (правила перестановки вершин, чтобы превратить один граф в другой) — это и есть ваш секрет X.
Протокол:

Шаг 1 (Привязка): Вы создаете новый граф, изоморфный первому (и, следовательно, второму), и отправляете его хэш (по сути, обязательство) верификатору.
Шаг 2 (Запрос): Верификатор бросает вам «монетку» (запрос) и просит вас либо:

Вариант А: Показать изоморфизм между вашим новым графом и первым исходным графом.
Вариант Б: Показать изоморфизм между вашим новым графом и вторым исходным графом.

Шаг 3 (Ответ): Вы выполняете запрос.
Это повторяется много раз.

Почему это «нулевое разглашение»? В каждом раунде вы раскрываете лишь часть информации, которая бесполезна сама по себе. Даже если верификатор будет пытаться жульничать, он не сможет из собранных фрагментов восстановить полный изоморфизм (ваш секрет X). Однако если вы не знаете изоморфизм, вы не сможете правильно отвечать на оба типа запросов в каждом раунде, и рано или поздно вас поймают на ошибке.

Связь с SHA-1: Финни не доказывал знание изоморфизма графов напрямую. Вместо этого он показал, как преобразовать знание прообраза X для хэша H в форму, эквивалентную задаче об изоморфизме графов. Таким образом, протокол ZKP для графов можно было использовать для доказательства знания X.

Зачем это было нужно в 1998 году?

Контекст этого выступления крайне важен:

Crypto 98 — одна из главных мировых конференций по криптографии.
Август 1998 — пик развития шифропанка и ранних идей цифровых денег (e-cash), анонимности и цифровых псевдонимов.
ZKP — это мощнейший инструмент для таких систем. Он позволяет, например:

Анонимные учетные записи: Доказать, что у вас есть право доступа (знаете пароль), не передавая сам пароль и не раскрывая вашу личность.
Аутентификация без раскрытия секрета: Сервер может хранить только хэши паролей, а вы можете доказать, что знаете пароль, никогда не отправляя его даже в зашифрованном виде.
Конфиденциальные вычисления: Доказать, что вы выполнили вычисление корректно, не раскрывая его входных данных.

Связь с Биткоином и Сатоши Накамото

Это выступление особенно интересно сегодня, потому что Хэл Финни стал одним из первых и самых известных сторонников Биткоина, получив первую в истории транзакцию от Сатоши Накамото.

Его глубокие знания в области криптографии, практической криптографии (он был разработчиком PGP) и такие доклады, как этот, показывают, что он был идеально подготовлен к тому, чтобы понять и оценить гениальность Биткоина.
Доклад демонстрирует его интерес к фундаментальным проблемам конфиденциальности и безопасности, которые лежат в основе философии Биткоина.
Хотя сам протокол, описанный в докладе, не используется напрямую в Биткоине, концепции криптографических обязательств и доказательств являются его краеугольным камнем.