Кто слышал страшные слова ZK-Proof но боялся спросить, что они значат - велкам под кат

Пролог

ZK-Proof aka Zero-Knowledge Proof, оно же доказательство с нулевым разглашением - это семейство криптографических протоколов, позволяющих одному участнику (доказывающему) убедить другого участника (проверяющего) в том, что он владеет некой информацией, известной лишь ему, не раскрывая при этом эту информацию. Эти протоколы имеют ряд интересных применений, такие например, как новые алгоритмы аутентификации. А также широко используются в криптовалютах.

Но понять, как эти протоколы устроены, не так то просто! В этом посте я приведу свой перевод статьи “How to Explain Zero-Knowledge Protocols to Your Children” by Jean-Jacques Quisquater and others, объясняющей в формате детской сказки, как это работает.

Али-Баба и волшебная пещера

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

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

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

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

Али мог снова сказать себе, как делал до этого, что беглецу просто повезло, как и тридацти девяти воришкам, бывшим до него. Но это объяснение было настолько притянуто за уши, что даже Али-Баба не поверил ему. Удача всех сорока разбойников была слишком большой, чтобы произойти по воле случая. Только один шанс на триллион, что всем сорока в этой ситуации удалось спастись! Тогда Али-Баба сказал себе, что должно быть другое, более подходящее объяснение. Он начал подозревать, что в пещере есть какой-то секрет!

И вот Али-Баба вновь отправился в пещеру, чтобы разгадать этот секрет. Он спрятался за мешками в конце правого туннеля, и начал ждать. После долгого и мучительного ожидания, он увидел вора, скрывающегося от погони. Тот прибежал в конец туннеля и произнёс “Сезам, откройся!”. На глазах изумленного Али, стена пещеры раздвинулась, пропустив вора, и вновь замкнулась, как ни в чем не бывало. Прибежавший торговец, приследовавший вора, был очень расстроен, обнаружив лишь Али-Бабу, спрятавшегося за мешками в конце туннеля. Вор убежал. Но Али был счастлив! Он разгадал секрет Таинственной Пещеры!

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

Судьба рукописи

Много лет спустя, в Средневековье, прекраснейшая рукопись Али-Бабы попала в Италию. А в наши дни она уже оказалась в США, неподалеку от Бостона. И в последнее время привлекла пристальное внимание многочисленных исследователей. Через расшифровку оставленнных Али-Бабой намеков, им удалось даже разгадать новое заклинание!

Несколько археологических раскопок спустя, в руинах старого Багдада удалось отыскать ту самую пещеру. Шутка ли, она оказалась не мифом! И, несмотря на прошедшие столетия, волшебные слова все еще работали. Взбудораженные открытием, исследователи прошли через ту самую стену, разделяющую два туннеля пещеры.

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

Первым делом, телеканал снял детальный тур по пещере, включая оба туннеля-тупика. Мик Али зашел один и прошел в один из туннелей. После него в пещеру зашёл оператор, дойдя только до разветвления. Там он подбросил монетку, чтобы выбрать “право” или “лево”. Орёл означал, что Мику Али нужно выйти из правого туннеля. Решка означала, что ему нужно выйти из левого туннеля. Выпал орёл, так что репортёр сказал громко: “Мик, выходи справа”. Что Мик и сделал.

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

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

Репортёр-завистник

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

Но шутки ради, Мик сказал новому репортёру, что фильм он может снять и без знания секретной фразы. Хитрый репортёр думал думал, и наконец понял. Он сказал себе: “Я даже знаю актёра, похожего на Мика Али как две капли воды”.

И второй репортаж был снят. В процессе съёмок половина дублей была выброшена, потому что двойник Мика не знал, как перейти из одного туннеля в другой! Но ушлый репортёр продолжал снимать дубль за дублем, пока не набрал сорок успешных, на которых актёр выходил из заданного монеткой туннеля.

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

Симулирующая эксперимент запись не раскрывала секретной фразы. Но ведь и оригинальная запись тоже не раскрывала её. Репортёр, снявший эксклюзивный репортаж, был убеждён Миком Али, что тот знает заклинание. Но он не в состоянии передать это убеждение ни судьям, ни даже зрителям его передачи.

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

Параллельные тесты

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

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

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

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

Предварительный сговор

Всё это очень заинтриговало европейских учёных. Они сделали наблюдение, справедливое для обоих случаев - и последовательного, и параллельного. Чтобы сократить время съёмок, ушлый репортёр и двойник Мика Али могли бы заблаговременно договориться, откуда тот будет выходить каждый из сорока раз. После чего репортёр будет делать вид, что случайным порядком просит выйти двойника то слева то справа. А двойник, помня последовательность, о которой они договорились заранее, выйдет все разы из правильного туннеля.

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

Один тест, один секрет

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

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

Эпилог

Итак, дети мои, вы услышали сегодня историю от том, как Али-Баба прознал секрет таинственной пещеры, а также о том, как его потомок, учёный Мик Али, доказал репортёру, что знает секрет, не раскрывая его тому. Бескрайнее множество людей видело Мика по телевизору, он стал знаменитым и стал путешествовать по всему миру. Он до сих пор не раскрыл заклинания таинственной пещеры, но смог убедить много-много людей в том, что знает его. Подобное хранение секретов напоминает мне о Меркле c Хеллманом и их бездонном рюкзаке. Но это уже совсем другая история…