Меню
ГлавнаяТелефон

Доказательство с нулевым разглашением. Мысленный эксперимент с машинами времени. Хорошо, и что же все это означает

Использование доказательства с нулевым разглашением конфиденциальной информации можно пояснить на конкретном примере. Предположим, что имеется пещера. Вход в пещеру находится в точке А, а в точке В пещера разветвляется на две половины - С и D. У пещеры есть секрет: только тот, кто знает волшебные слова, может открыть дверь, расположенную между С и D.

Антону волшебные слова известны, Борису - нет. Антон хочет доказать Борису, что знает волшебные слова, но так, чтобы Борис по-прежнему оставался в неведении относительно этих слов. Тогда Антон может воспользоваться следующим протоколом:

1. Борис стоит в точке А.

2. По своему выбору Антон подходит к двери либо со стороны точки С,

либо со стороны точки D.

3. Борис перемещается в точку В.

4. Борис приказывает Антону появиться или через левый проход к двери,

или через правый.

5. Антон подчиняется приказу Бориса, в случае необходимости используя

волшебные слова, чтобы пройти через дверь.

6. Шаги 1-5 повторяются n раз, где n - параметр протокола.

Допустим, что у Бориса есть видеокамера, с помощью которой он фиксирует все исчезновения Антона в недрах пещеры и все его последующие появления. Если Борис покажет записи всех n экспериментов, произведенных им совместно с Антоном, могут ли эти записи послужить доказательством знания Антоном волшебных слов для другого человека (например, для Владимира)?

Вряд ли. Владимир никогда не сможет удостовериться в том, что Антон каждый раз предварительно не сообщал Борису о своих намерениях, чтобы потом Борис приказывал ему выходить именно с той стороны двери, с какой Антон зашел. Или что из сделанной видеозаписи не вырезаны все неудачные эксперименты, в ходе которых Антон не смог выполнить распоряжения Бориса.

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

Протокол доказательства с нулевым разглашением срабатывает в силу того, что не зная волшебных слов, Антон может выходить только с той стороны, с которой зашел. Следовательно лишь в 50% всех случаев Антон сумеет обмануть Бориса, догадавшись, с какой именно стороны тот попросит его выйти. Если количество экспериментов равно n, то Антон успешно пройдет все испытания только в одном случае из 2 n . На практике можно ограничиться n=16. Если Антон правильно исполнит приказ Бориса во всех 16-ти случаях, значит он и правда знает секрет волшебных слов.

Пример с пещерой является наглядным, но имеет существенный изъян. Борису значительно проще проследить, как в точке В Антон поворачивает в одну сторону, а потом появляется с противоположной стороны. Протокол доказательства с нулевым разглашением здесь попросту не нужен.

Поэтому предположим, что Антону известны не какие-то там волшебные слова, типа “Сезам, откройся”. Нет, Антон владеет более интересной информацией - он первым сумел найти решение этой труднорешаемой задачи. Чтобы доказать данный факт Борису, Антону совсем не обязательно всем и каждому демонстрировать свое решение. Ему достаточно применить следующий протокол доказательства с нулевым разглашением конфиденциальной информации:

1. Антон использует имеющуюся у него информацию и сгенерированное

случайное число, чтобы свести труднорешаемую задачу к другой труднорешаемой задаче, изоморфной исходной задаче. Затем Антон решает эту новую задачу.

2. Антон задействует протокол предсказания бита для найденного на

шаге 1 решения, чтобы впоследствии, если у Бориса возникнет необходимость ознакомиться с этим решением, Борис мог бы достоверно убедиться, что предъявленное Антоном решение действительно было получено им на шаге 1.

3. Антон показывает новую труднорешаемую задачу Борису,

4. Борис просит Антона или доказать, что две труднорешаемые задачи

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

5. Антон выполняет просьбу Бориса.

6. Антон и Борис повторяют шаги 1-6 n раз, где n - параметр

протокола.

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

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

Пост-квантовые доказательства с нулевым разглашением – протоколы доказательства с нулевым разглашением знаний , которые квантово-устойчивы.

Квантово-устойчивыми системами/протоколами, считаются такие системы/протоколы, которые нельзя скомпрометировать, используя мощность вычислений квантового компьютера. Термин квантово-устойчивости вводится в пост-квантовой криптографии.

Contents

Постановка задачи защиты информации

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

ZKBoo

ZKBoo опирается на протокол конфиденциального вычисления (MPC) . В ZKBoo идей является замена MPC на (2,3)-разложение цепи.

Построения доказательства происходит по следующей схеме:

1) P вычисляет f с использованием декомпозиции и фиксирует 3 состояния;

2) P отправляет обязательства и выходные данные каждого состояния предварительно использовав эвристику FS;

3) В ответ приходит какие 2 из 3 состояний открываются для каждого N запуска;

4) V выполняет проверку выходных данных на полноту восстановления; проверяет, что каждое из 2 открытых состояний вычислено корректно и вычисляет корректность вычисления вызова.

Количество запусков, выбирается так что бы ошибка была незначительной, так что бы возможность попадания злоумышленника во все запуски была минимальной.

ZKB++

ZKB++ является модифицированной версией ZKBoo.

1) Разложение: в View1 и View2, P должен включать k(i), поскольку x(i) может быть детерминистически вычислен V;

2) Не включение входных данных: входные доли, генерирующиеся псевдослучайно, используя k(i), не нужно включать их в представление, когда e = 1. Данные нужно отправлять, только в случае, если e = 2 или e = 3, поскольку для третьего состояния, входные данные не могут быть получены из начального, так как генерируются псевдослучайно, используя k(i);

3) Без отправки обязательств;

4) Отсутствие дополнительно случайной последовательности для обязательств;

5) Без учета выходных данных: выходные данные могут быть вычислены из остальной части доказательств;

6) Не включение состояния-представления: V может пересчитывать состояние, учитывая только случайные k(e) и k(e+1).

Полная схема ZKB++ представлена на рисунке 1.

Улучшения предпринятые для оптимизации ZKBoo уменьшает размер доказательств в 2 раза для ZKB++.

Красивая терминология является одним из достоинств современной криптографии. Названия панк-групп или ников на Tumbl - вот на что похожи криптографические термины, такие, как "трудный предикат" (hard-core predicate), "функция с секретом" (trapdoor function), или "невозможный дифференциальный криптоанализ" (impossible differential cryptanalysis). Мне кажется, что еще более красиво звучит такой термин, как "нулевое разглашение (zero knowledge) ".

Но красота термина "нулевое разглашение" приводит к злоупотреблению им. Людям сразу кажется, что нулевое разглашение становится синонимом слов "очень, очень безопасно". Из-за этого данные слова добавляют к названиям систем безопасности и анонимных сетей – что на самом деле не имеет ничего общего с протоколом "нулевое разглашение".

Всё это мы сказали для того, чтобы подчеркнуть главное: доказательство с нулевым разглашением (zero knowledge proof) является одним из самых мощных инструментов криптографии из когда-либо разработанных. Но, к сожалению, оно относительно мало изучено. Попробуем дать не математическое объяснение того, что делает ZK (zero knowledge) таким особенным. Здесь мы будем говорить о некоторых актуальных протоколах ZK.

Происхождение нулевого разглашения

До Голдвассера и других, большинство работ в этой области фокусировались на системах доказательства правильности. То есть, на случаях, когда злоумышленник - Испытатель пытается провернуть трюк с Контролёром, подсовывая ему ложное значение. Но Голдвассер, Микали и Ракофф рассмотрели противоположную сторону этой проблемы. Вместо того, чтобы беспокоится только об Испытателе, они спросили: что произойдёт, если вы не доверяете Контролёру?

Особо их обеспокоила возможность утечки информации. Конкретно, они задались вопросом, сколько дополнительной информации получит Контролёр в ходе доказательства самого факта, что утверждение верно?

Важно отметить, что это не просто теоретический интерес. Есть реальные, практические приложения, в которых эти вещи важны.

Вот одно из них: представьте, что клиент в реальном мире хочет войти на веб-сервер, используя пароль. Стандартный подход к проблеме "в реальном мире" включает в себя хранение хэшированной версии пароля на сервере. Логин в такой системе рассматривается как вид "подтверждения", что хэш предоставленного пароля это выход хэширующей функции действующего пароля. И, что более важно, как "подтверждение" того, что клиент действительно знает пароль.

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

То, что предложили Голдвассер, Микали и Ракофф, стало надеждой на появление новых методов подтверждения. В случае полной реализации, доказательства с нулевым разглашением смогут дать подтверждение в описанной выше задаче. При этом не разгласив ни одного бита информации, которая соответствует тому, что "это утверждение верно".

Пример из "реального мира"

До сих пор мы разговаривали о довольно абстрактных вещах. Давайте пойдём вперёд и приведём реальный пример (слегка безумный) для протокола "нулевое разглашение".

Чтобы мне было проще объяснить этот пример, давайте представим, что я магнат телекоммуникаций и нахожусь в процессе развёртывания новой сотовой сети. Моя сетевая структура представлена ниже на этом графе. Каждая вершина графа представляет собой мобильный передатчик, и соединяющие линии (грани) показывают места, где две соты перекрываются. В этих местах передатчики будут создавать друг другу помехи. Хорошо, что моя сетевая структура позволяет настроить каждую башню в одном из трёх частотных диапазонов, чтобы избежать такого влияния.

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


Конечно, многие из вас уже заметили. То, что я описал здесь - только частный случай знаменитой теоретической проблемы. Она носит название "проблемы раскраски графа в три цвета ". Вы можете также знать об одной очень интересной особенности этой проблемы. Для некоторых графов очень трудно найти решение или даже определить, что такое решение существует. Задача раскраски графа в три цвета (и поиск ответа на вопрос, существует ли такое решение для данного случая), как известно, относятся к разряду NP-полных задач .

Само собой разумеется, что вышеописанные игрушечные загадки решить просто. Но если бы это не было так просто? Например, представьте, что моя сеть сотовой связи была очень большой и сложной. В этом случае мне бы не хватило вычислительной мощности, чтобы найти решение. В этом случае, было бы желательно поручить решение проблемы кому-нибудь ещё. Тому, у кого достаточно вычислительной мощности. Например, я мог бы попросить Google решить эту задачу.

Но есть одна проблема.

Предположим, что Google уделит мне столько, сколько нужно вычислительных мощностей для того, чтобы найти решение правильной раскраски моего графа. Я, конечно, не собираюсь платить им, пока не буду уверен в том, что у них есть это решение. В то же время, Google не собирается предоставить мне копию решения до тех пор, пока я не оплачу её. Мы в тупике.

В реальной жизни здравый смысл подсказывает нам ответ на эту дилемму, который включает в себя услуги юристов и эскроу-счета. Но здесь мы говорим не о реальной жизни, а о криптографии. И, если вы когда-нибудь читали работы криптографов, то уже знаете, что единственный способ найти решение проблемы - придумать полностью сумасшедшее техническое решение. Сумасшедшее техническое решение (со шляпами)

Представим, что сотрудники Google проконсультировались у Сильвио Микали из MIT, а он расспросил своих коллег Оде Голдрих (Oded Goldreich) и Ави Виджерсон (Avi Wigderson). Посоветовавшись, они разработали протокол, который настолько красив, что даже не требует компьютеров. Будет использоваться большой склад с запасом цветных карандашей и бумаги. Ещё понадобится большое количество шляп.

Рассмотрим, как это работает

Сначала я войду в помещение склада и застелю пол бумагой, чтобы создать пространство для представления моей сотовой сети. Затем я покину склад. Google теперь может войти, перемешать коллекцию карандашей и выбрать три любых цвета (например, красный / голубой / фиолетовый, как в этом примере), и цвет, которым будет обозначено решение. Заметим, что какой конкретно цвет используется, значения не имеет.

Перед тем, как покинуть склад, Google накрывает каждую вершину шляпой. Когда я вернусь, это всё, что я увижу:


Очевидно, что такой подход отлично защитит секрет Google. Но это совсем не поможет мне. Возможно, Google заполняет цвета в случайном, а значит, в неправильном порядке. А может быть, они вообще не заполняли ничего.

Чтобы убедить меня в том, что задача действительно решалась, Google даёт мне возможность "проверить" их результат раскраски графа. Я имею право выбрать, в случайном порядке, одну грань этого графа (то есть, по одной линии между двумя соседними шляпами). Google будет удалять эти две шляпы, показывая мне небольшую часть решения:


Обратите внимание, что у моего эксперимента есть два возможных исхода:

Если две показанные вершины имеют один и тот же цвет (или же вообще не окрашены!) тогда я точно буду уверен, что Google обманывает меня. В этом случае я не заплачу Google даже цента. Если две показанные вершины имеют различные цвета, значит, Google в этом случае не обманывает меня.

Надеюсь, первое утверждение очевидно. Второе потребует более подробного объяснения. Проблема в том, что если даже эксперимент был успешным, Google по-прежнему может обманывать меня. Всё-таки, я заглянул всего лишь под две шляпы. Если существует E различных рёбер в графе, то Google с большой долей вероятности может предоставить ошибочное решение. Например, после одного теста они обманывают меня с вероятностью (E-1) / E (что для 1000 граней будет составлять 99.9%).

К счастью, у Google есть ответ на этот вопрос. Мы просто запустим протокол снова!

Мы берём чистую бумагу для создания новой копии графа. Google теперь берёт новую случайную перетасовку трёх цветных карандашей. Затем они заполняют граф верным решением, но используя новый случайный набор трёх цветов.

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

Такое событие может произойти - но его вероятность будет ещё ниже. Вероятность того, что Google одурачит меня два раза подряд, составляет (E-1) / E * (E-1) / E (или около 99.8% вероятности для нашего примера с 1000 граней).

К счастью, мы не должны останавливаться на двух попытках. Мы будем пробовать снова и снова, пока не убедимся, что Google, с высокой долей вероятности, говорит правду.

Я призываю вас не верить мне на слово. Опробуйте этот Javascript, и убедитесь в этом самостоятельно.

Обратите внимание, что я никогда не уверен полностью, что Google честен – всегда остаётся крошечная вероятность, что они обманывают меня. Но, после большого количества итераций (E ^ 2, как в нашем случае) я в конце концов дойду до точки, в которой Google обманывает меня с пренебрежимо малой вероятностью – достаточной для применения на практике. После этого я спокойно могу отдать деньги Google.

Важно, что Google в этом случае также защищён. Если я попытаюсь узнать что-либо, сохраняя и анализируя заметки между запусками протокола, то потерплю неудачу Это вызвано тем, что Google при каждой итерации использует цвета, выбранные в случайном порядке. Ограниченная информация, которую я могу получить, не даст мне ничего. Для меня не существует способа связать эти данные воедино.

Что делает этот пример "нулевым разглашением"?

Я пытаюсь убедить вас, что этот протокол не позволяет просочиться информации о решении Google. Но вам не нужно верить мне на слово! Первое правило криптографов заключается в том, чтобы никогда не верить таким вещам без доказательств.

Голдвассер, Микали и Ракофф предложили три критерия, которым должен отвечать каждый протокол "нулевое разглашение". Неформально их можно описать так:

Полнота. Если Google говорит мне правду, то я должен получить убедительные доказательства этого (доказательства с высокой вероятностью). Надёжность. Google может убедить меня только в том случае, если действительно говорит правду. "Нулевое разглашение" (этот критерий действительно так и называется). Я не должен узнать ничего больше, кроме полученного решения Google.

Мы уже обсудили аргументы в пользу полноты. Протокол в конечном счёте убедит меня (с пренебрежимо малой вероятностью ошибки), если запустить его достаточное число раз. Надёжность тоже достаточно легко показать. Если Google попытается обмануть меня, я обнаружу это в подавляющем большинстве случаев.

Самым сложным свойством осталось "нулевое разглашение". Чтобы разобраться в нём, сделаем довольно странный мысленный эксперимент.

Мысленный эксперимент с машинами времени

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

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

Таким образом, отпадает использование машины времени для увеличения времени на выполнение работы. Но всё-таки, оказалось, что эта весьма ограниченная технология может использоваться, чтобы обмануть меня.

Я действительно не знаю, что здесь происходит. Но кажется, это кстати.

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

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

По сути, машина времени позволяет Google "починить" любой неудачный вход в протокол таким образом, чтобы я ничего не заподозрил. Так как плохие результаты будут происходить только в 1/3 случаев, ожидаемое время выполнения протокола (с точки зрения Google) только незначительно больше, чем в случае честного выполнения протокола. С моей точки зрения, я даже не знаю, что эти путешествия во времени происходят.

Этот последний пункт является наиболее важным. С моей точки зрения, я одинаково взаимодействую с протоколом, есть машина времени или её нет. И всё же, стоит отметить ещё раз - в версии с машиной времени Google не имеет абсолютно никакой информации о том, как нужно раскрасить граф.

И что же из этого следует?

То, что мы только что показали - теоретический пример. В мире, где время бежит только вперёд, и никто не может обмануть меня с машиной времени, протокол с использованием шляп работает правильно. После E ^ 2 раундов его запуска я должен убедиться (не полностью, но с пренебрежимо малой вероятностью обмана), что граф окрашен правильно и Google обеспечил верную информацию.

Если же временем можно манипулировать (в частности, если Google может "перемотать время"), то он может подделать протокол, даже если вообще не имеет информации о том, как должен быть окрашен граф.

С моей точки зрения, какая разница между этими двумя протоколами? Они имеют одинаковое статистическое распределение и передают одинаковое количество полезной информации.

Верьте или не верьте, это доказывает нечто очень важное.

В частности, предполагается, что я (Контролёр) (Verifier) имею какую-то стратегию, которая позволит "извлечь" полезную информацию о том, как Google производит окрашивание, в случае запуска честного протокола. Тогда моя стратегия должна так же хорошо работать в том случае, если меня дурачат с машиной времени. Запуски протокола, с моей точки зрения, статистически идентичны. Я физически не могу показать разницу.

Таким образом, полностью идентично количество информации, которое я получу в "реальном эксперименте" и "эксперименте с машиной времени". Количество информации, которое Google вкладывает в случае эксперимента с "машиной времени", в точности равно нулю. Следовательно, даже в реальном мире не произойдёт утечки информации. Осталось только показать, что у компьютерщиков есть машина времени (тсс, это секрет).

Как избавиться от шляп и машин времени

Конечно, на самом деле мы не хотели бы запускать протокол, пользуясь шляпами. И даже у Google (скорее всего) нет настоящей машины времени.

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

К счастью, у нас есть прекрасный инструмент для этого приложения. Он называется цифровой схемой обязательства (digital commitment scheme). Схема обязательства позволяет одной из сторон создать для сообщения "обязательство", сохраняя при этом его в секрете, а позже открыть "обязательство", чтобы посмотреть, что внутри. Они могут быть построены из различных компонентов, в том числе из сильных криптографических функций хэширования.

Получив схему обязательства, мы собрали все компоненты, чтобы запустить в электронном виде протокол нулевого разглашения. Испытатель сначала кодирует окраску вершин в виде набора цифровых сообщений (например, числами 0, 1, 2), затем генерирует цифровые обязательства для каждой. Эти обязательства пересылаются для Контролёра. Когда Контролёр открывает один край, Испытатель показывает значения для обязательств, которые соответствуют двум вершинам.

Так нам удалось избавиться от шляп. Но как мы докажем, что этот протокол имеет нулевое разглашение?

Но мы ведь сейчас находимся в цифровом мире. Поэтому нам не нужна машина времени, чтобы подтвердить то, что протокол работает. Ключевая хитрость заключается в том, что протокол будет работать не между двумя людьми, а между двумя различными компьютерными программами (или, говоря более формально, двумя вероятностными машинами Тьюринга (probabilistic Turing machines.)

Сейчас мы можем доказать следующую теорему: если Контролёр собирается извлечь полезную информацию при обычном запуске протокола, он получит то же количество полезной информации, что и при "обманном" запуске протокола, где Испытатель не вложил никакой информации с самого начала.

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


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

В конечном счёте, то, что мы получаем, можно представить в виде теоремы. Если для Контролёра существует компьютерная программа, которая успешно извлекает полезную информацию от Испытателя (интерактивно работая с протоколом), то Испытатель может использовать трюк с перемоткой программы, подсовывая Контролёру случайные решения. Используется логика, которую мы уже применяли выше: если Контролёр успешно может извлечь информацию, запустив реальный протокол, значит, он получит то же количество информации, запустив поддельный протокол, основанный на перемотке программы назад. Но так как поддельный протокол не передаёт полезных данных, нет никакой информации, которую можно извлечь. Таким образом, информация, которую может извлечь Контролёр, всегда равняется нулю.

Что же из этого всего следует?

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

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

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

Доказательства для всех NP!

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

Проще говоря, Голдрих, Микали и Виджерсон доказали , что "эффективные" ZK существуют для обширного класса полезных задач. Многие из них являются гораздо более интересными, чем задача о присвоении частот в сотовой сети.

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

Вместо итогов

Конечно, сразу начать использовать этот протокол на практике было бы безумно глупо. Его вычислительная стоимость будет включать в себя общий размер первоначального заявления и свидетельства, плюс стоимость перевода задачи в граф, и ещё E ^ 2 запусков протокола, которые необходимы для того, чтобы убедиться в правильности решения. Теоретически это "эффективно", но так как общая стоимость доказательства будет многочленом от длины входа, на практике это не применимо.

Так что мы пока что доказали только то, что такие доказательства возможны. Осталось найти такие доказательства, которые являются достаточно практичными для реального использования.

Примечания

* Формально, целью интерактивного доказательства является убеждение Контролёра, что определённая строка принадлежит какому-либо языку. Обычно Испытатель в задачах имеет неограниченную мощность, а Контролёр ограничен в возможности расчётов.

** Этот пример основан на оригинальном решении Голдвассера, Микали и Ракофф, и учебном примере с использованием шляп, который разработал Сильвио Микали.

****** Простой пример обязательства может быть построен с использованием примера хэширующей функции. Для создания обязательства значения "x" мы просто генерируем некоторую (достаточно длинную) строку случайных чисел, которую назовём "соль", и выходное обязательство C = хэш (соль || x). Чтобы открыть обязательство, вы просто открываете "x" и "соль". Любой желающий может проверить, что первоначальное обязательство действует, пересчитав хэш повторно. Это безопасный метод при некоторых, умеренно сильных, предположениях о самой функции.

Мы уже рассматривали, что такое Zk-SNARK или протокол доказательства с нулевым разглашением простыми словами, но в данной статье мы хотели бы больше углубиться в техническую часть данного явления.

Протокол доказательства с нулевым разглашением: как это работает?

Итак, напомним, что доказательство с нулевым соглашением позволяет доказать, что вы являетесь владельцем какой-либо информации без раскрытия ее содержания. Для реализации данной концепции потребуется введение сразу 3 алгоритмов, которые обозначим GK, P и V. Рассмотрим их назначение:

  • GK – это генератор ключей, который принимает инпут α и программу C, генерируя два ключа: ключ проверки для пруфера PK и ключ верификации для верификации VK. Эти ключи являются открытыми для всех сторон, участвующих в доказательстве.
  • P – это пользователей, которому для доказательства необходимо использовать 3 типа входных данных: 1) ключ проверки PK; 2) рандомный инпут X, который будет общедоступным для сторон; 3) заявление, которое необходимо доказать, не раскрывая его значения – W. Сам алгоритм P порождает доказательство Proof, которое будет удовлетворять следующие условия: Proof = P (PK; X; W).
  • V – алгоритм верификатора, который возвращает логическую переменную. Она может быть представлена в двух значениях: TRUE (правда) или FALS (ложь). Итак, верификатор принимает следующие входные данные V(VK; X; Proof), на основании которых он определяет правда это или ложь.

Так работает протокол доказательства с нулевым разглашением. Единственное, о чем хотелось бы поговорить отдельно, – значение α, упомянутое в пункте про GK. Дело в том, что данный параметр существенно усложняет использование Zk-SNARK в реальных приложениях, ведь каждый, кто им владеет, может создать ложный Proof, на который система вернет True. С этой проблемой очень долго боролись разработчики ZCash, криптовалюты, которая использует технологию нулевого доказательства.

Одна из лучших сторон современной криптографии - это ее прекрасная терминология. Можно создать сколько угодно панк-групп с названиями вроде Hardcore Predicate, Trapdoor Function или Impossible Differential Cryptanalysis. Однако есть термин, который превосходит все остальные. Это Zero Knowledge Proof - «доказательство с нулевым разглашением» .

Термин «с нулевым разглашением» настолько привлекателен, что это приводит к проблемам. Люди используют его неправильно, предполагая, что нулевое разглашение - это синоним «очень-очень надежной безопасности» . Из-за этого его используют с чем угодно - в том числе с системами шифрования и сетями анонимизации - которые на самом деле не имеют никакого отношения к протоколам с нулевым разглашением.

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

История нулевого разглашения

Концепцию «нулевого разглашения» впервые предложили в 1980-х исследователи из MIT Шафи Гольдвассер (Shafi Goldwasser), Сильвио Микали (Silvio Micali) и Чарльз Рекофф (Charles Rackoff). Они изучали проблемы, связанные с интерактивными системами доказательства - теоретическими системами, в которых одна сторона («Prover» - Доказывающий), обменивающаяся сообщениями со второй стороной («Verifier» - Проверяющий), пытается убедить ее в истинности какого-либо математического утверждения.*

До Гольдвассер и ее коллег работы в этой области в основном фокусировались на корректности системы доказательства. Иначе говоря, ученые рассматривали ситуации, в которых злой Доказывающий пытался «обманным путем убедить» Проверяющего поверить в ложное утверждение. Гольдвассер, Микали и Рекофф перевернули проблему с ног на голову. Вместо того чтобы беспокоиться только о Доказывающем, они решили рассмотреть, что происходит, если вы не доверяете Проверяющему.

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

Важно отметить, что это было сделано не просто из теоретического интереса - у таких задач есть реальные сферы применения. Вот один из таких сценариев: представьте, что пользователь в реальном мире хочет войти на веб-сервер с помощью пароля. Стандартный «реалистичный» подход к этой проблеме включает сохранение хешированной версии пароля на сервере. Таким образом, вход на сервер можно рассматривать как своеобразное «доказательство» того, что хеш пароля является результатом применения хеш-функции к какому-то паролю и что клиент на самом деле знает пароль.

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

То, что предложили Гольдвассер, Микали и Рекофф, возродило надежду на реализацию доказательств с нулевым разглашением, доказуемо не сообщающих никакой информации, кроме одного бита, означающего «это утверждение истинно».

Пример из «реального мира»

Пока наше обсуждение довольно абстрактно, так что давайте рассмотрим «реальный» пример (немного безумного) протокола с нулевым разглашением.

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

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

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

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

Но это приводит к проблеме.

Предположим, что Google выделит значительную долю своей вычислительной инфраструктуры на поиск способа раскраски моего графа. Разумеется, я не собираюсь платить им, пока не узнаю, что они на самом деле нашли такой способ, но в то же время Google не собирается предоставлять мне копию решения, пока я им не заплачу. Мы оказались в тупике.

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

Сумасшедшее техническое решение (с шляпами!)

Заметьте, что я никогда не буду абсолютно уверен в честности Google - всегда будет хотя бы крошечная вероятность того, что Google меня обманывает. Однако после большого количества итераций (а именно E ^2 ) моя уверенность вырастет до точки, в которой вероятность обмана Google пренебрежимо мала - достаточно мала, чтобы во всех практических задачах ей можно было пренебречь. В таком случае я могу безопасно отдать Google мои деньги.

Нам необходимо знать, что Google также в безопасности. Даже если я пытаюсь узнать что-то о решении Google, сохраняя заметки между запусками протокола, это не должно иметь значения. Я в тупике из-за того, что Google рандомизирует выбор цветов в разных итерациях протокола. Ограниченная информация, которую я получаю, бесполезна, и у меня нет никакого способа связать данные разных итераций.

Что делает это «нулевым разглашением»?

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

Гольдвассер, Микали и Рекофф предложили три свойства, которым должен удовлетворять любой протокол с нулевым разглашением. Неформально их можно выразить так:

  1. Полнота (completeness ). Если Google говорит правду, то в итоге сможет убедить меня (по крайней мере, с высокой вероятностью).
  2. Корректность (soundness ). Google может убедить меня в правильности решения только в том случае, если на самом деле говорит правду.
  3. Нулевое разглашение (zero — knowledgeness ) . Я больше ничего не узнаю о решении Google.

Аргумент в пользу полноты мы уже обсудили. Протокол таков, что после достаточного количества повторений Google в итоге убедит меня (с пренебрежимо малой вероятностью ошибки). Продемонстрировать корректность этого протокола тоже довольно легко. Если Google когда-либо попытается обмануть меня, я почти наверняка обнаружу предательство.

Затруднения здесь вызывает третье свойство, но чтобы понять это, нам нужно провести очень странный мысленный эксперимент.

Мысленный эксперимент (с машинами времени)

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

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

Таким образом, вариант с использованием машины времени для получения дополнительного рабочего времени отпадает. Тем не менее, оказывается, что даже эта очень ограниченная технология все же может быть использована с тем, чтобы обмануть меня.

Понятия не имею, что здесь происходит, но мне показалось, что картинка вполне подходит.

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

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

По сути, машина времени позволяет Google «восстанавливаться» от любых неприятностей, которые происходят во время выполнения их фальшивого протокола, из-за чего мне все кажется нормальным. Поскольку удачная попытка оспорить протокол происходит лишь примерно в 1/3 попыток, ожидаемое время выполнения протокола (с точки зрения Google) лишь умеренно больше, чем время выполнения честного протокола. Что касается меня, то я даже не подозреваю, что происходят путешествия во времени.

Последний момент наиболее важен. На самом деле с моей точки зрения незнание того, что задействована машина времени, приводит к точно такому же взаимодействию, что и реальность. Статистически они идентичны. И все же, снова стоит отметить, что в версии с машиной времени у Google совершенно нет информации о том, как раскрасить граф.

К чему это все?

То, что мы только что рассмотрели - это пример симуляции . Заметьте, что в мире, где время движется только вперед и никто не может обмануть меня с помощью машины времени, протокол со шляпами корректен , то есть после E ^2 раундов я должен быть убежден (за вычетом пренебрежимо малой вероятности), что граф на самом деле можно раскрасить и что Google располагает действительным решением.

Мы только что показали, что если время течет не только вперед - точнее говоря, если Google может «перематывать» мое представление о времени - то Google может подделать действительный запуск протокола даже без информации о фактической раскраск e графа.

Какова с моей точки зрения разница между двумя вариантами протокола? Если рассматривать их статистическое распределение, разницы нет никакой - оба сообщают примерно одинаковый объем полезной информации.

Хотите - верьте, хотите - нет, но это доказывает кое-что очень важное.

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

Таким образом, если объем информации, который я могу извлечь, в «реальном эксперименте» и «эксперименте с машиной времени» идентичен, но объем информации, которую предоставляет Google в эксперименте с «машиной времени», в точности нулевой, это предполагает, что даже в реальном мире протокол должен не выдавать никакой полезной информации. Остается только показать, что у информатиков есть машины времени. Да, у нас они есть! (Это тщательно скрываемый секрет.)

Избавляемся от шляп (и машин времени)

Конечно, на самом деле мы не хотим выполнять протокол с шляпами и даже у Google нет настоящей машины времени (наверное).

Чтобы связать все вместе, нам сначала нужно перенести наш протокол в цифровой мир. Это требует, чтобы мы сконструировали цифровой эквивалент «шляпы» - что-то, что одновременно скрывает цифровое значение и при этом «привязывает» создателя к нему («обязывает»), чтобы он не мог передумать постфактум.

К счастью, у нас есть идеальный инструмент для этого, который называется цифровой схемой обязательства . Схема обязательства позволяет одной стороне «выразить обязательство» для конкретного сообщения, сохранив его при этом в «секретном конверте», а затем позднее «раскрыть» конверт с обязательством, чтобы показать, что внутри. Обязательства можно создавать из раличных ингредиентов, включая (надежные) криптографические хеш-функции.***

Со схемой обязательства у нас есть все, что нужно для электронного выполнения протокола с нулевым разглашением. Доказывающий сначала кодирует расцветку вершин как набор цифровых сообщений (например, с помощью чисел 0, 1, 2), а затем генерирует для каждого из них цифровые обязательства. Эти обязательства пересылаются Проверяющему. Когда Проверяющий оспаривает решение для какого-то ребра, Доказывающий просто обнародует значения для обязательств, соответствующих двум вершинам.

Так мы устранили шляпы, но как доказать, что это протокол с нулевым разглашением?

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

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

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

Пример перемотки снимков виртуальных машин. Первоначальная виртуальная машина воспроизводится вперед, возвращается к первоначальному снимку, а затем выполняется другая ветвь.

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

В конечном итоге мы получаем следующую теорему. Если существует какая-либо компьютерная программа Проверяющего, которая успешно извлекает информацию, интерактивно выполняя этот протокол с некоторым Доказывающим, мы можем просто использовать хитрость с перемоткой, чтобы выразить обязательство для случайного решения, а затем «обмануть» Проверяющего, перематывая программу, пока не пройдем испытание. Имеет место та же логика, что и выше: если бы такой Проверяющий преуспел в извлечении информации после выполнения реального протокола, то он мог бы извлечь тот же объем информации из симулированного протокола с перемоткой. Но поскольку симулированному протоколу не передается никакая информация, то и извлечь нечего. Следовательно, объем информации, которую Проверяющий может извлечь, равен нулю.

Хорошо, и что же все это означает?

Итак, по приведенному выше анализу мы знаем, что протокол полон и корректен. Аргумент в пользу корректности выстаивает всегда, когда мы знаем, что никто не манипулирует временем - т. е. что программа Проверяющего выполняется нормально и никто не перематывает его выполнение.

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

У всего этого есть важное преимущество. Поскольку любой легко может «подделать» запись протокола даже после того как система Google докажет мне, что у нее есть решение, я не могу заново воспроизвести запись протокола, чтобы доказать что-либо кому-либо другому (скажем, судье). Это объясняется тем, что у судьи не было бы никакой гарантии, что видео было записано честно и что я не отредактировал его так же, как могла сделать система Google с помощью машины времени. Это означает, что сама запись протокола не содержит информации. Протокол имеет смысл только в том случае, если я сам участвовал в нем и уверен, что это происходило в реальном времени.

Доказательства для всех NP!

Если вы дочитали до этого места, я уверен, что вы готовы к большим новостям. А именно, вы готовы узнать, что трехцветные сотовые сети не такая уж интересная проблема - по крайней мере, сама по себе.

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

Этот результат одним махом - благодаря Голдрайху , Микали и Видждерсону - доказывает, что «эффективные» доказательства с нулевым разглашением существуют для широкого класса полезных утверждений, многие из которых гораздо более интересны, чем назначение частот сотовым сетям. Вы просто находите утверждение (в классе NP), которое хотите доказать, такое как наш приведенный выше пример хеш-функции, а затем преобразуете его в экземпляр проблемы 3-х цветов. После этого вы просто запускаете цифровую версию протокола с шляпами.

Подведем итоги

Конечно, на самом деле запускать этот протокол для интересных утверждений было бы очень странно и глупо, потому что это требовало бы выполнения огромного объема работы. Теоретически это «эффективно», потому что общие затраты на доказательства росли бы полиномиально в зависимости от размера входных данных, но на практике они были бы совершенно другими.

Таким образом, мы пока показали лишь, что такие доказательства возможны . Сам же поиск доказательств, достаточно практичных для использования в реальном мире, остается на нашу долю.

В других сообщениях я расскажу о некоторых из них - а именно эффективных доказательствах разных полезных утверждений. Я приведу некоторые примеры (из реальных приложений), где такие приемы были использованы. Также по запросу одного из читателей я расскажу, почему мне так не нравится протокол SRP (Secure Remote Password).

Примечания

* Формально цель интерактивного доказательства - убедить Проверяющего, что конкретная строка принадлежит некоторому языку. Обычно Доказывающий очень (неограниченно) могуществен, а Проверяющий ограничен в вычислительных ресурсах.

** Этот пример основан на оригинальном решении Гольдвассер, Микали и Рекоффа, а обучающий пример со шляпами - на объяснении, которое дал Сильвио Микали. Я отвечаю только за ошибки, если таковые найдутся.

*** Простой пример обязательства можно построить с использованием хеш-функции. Чтобы создать обязательство для значения «x», просто сгенерируйте некоторую (достаточно длинную) строку случайных чисел, которую мы будем называть «солью» (salt), и выведите обязательство C = Hash (salt || x ) . Чтобы обнародовать обязательство, вы просто демонстрируете «x» и соль. Любой может убедиться, что оригинальное обязательство действительно, пересчитав хеш. Это безопасно, если выполнены некоторые (умеренно строгие) требования к самой функции.

Мэтью Грин (Matthew Green)