Цифровая подпись является “виртуальной скрепой” практически любого блокчейн-проекта. В подавляющем большинстве проектов используется подпись, практически не отличающаяся от подписи, используемой в сети Bitcoin(а именно ECDSA на кривой secp256k1). Однако, создание цифровой подписи для проектов, в которых “приватность” пользователей играет существенную роль, часто превращается в сложный акробатический номер, базирующийся на передовых достижениях в области дискретной математики и криптографии.
Дело в том, что в отличие от обычных блокчейн-проектов, где в транзакции явно указано, какая монета тратится из какого кошелька, в прайваси блокчейнах используются разные способы запутывания “следов”. Одними из первых, кто занимался решением этой задачи, был проект CryptoNote, в котором была реализована схема с кольцевой подписью. Такая схема, вместо явного указания на транзакцию-источник монет, позволяет включить в подпись группу из случайных транзакций, не связанных с этим переводом. Таким образом, сторонний наблюдатель не догадывается, из какой именно транзакции-источника на самом деле берутся деньги. Известно только, что отправитель доказал свое право владения одной из них. Такие “подмешанные” транзакции называются “mixins” или “decoys”, а их количество определяет так называемый “anonymity set”.
Самым узнаваемым проектом, построенным на базе CryptoNote, на сегодняшний день является Monero. За последние несколько лет участники этого проекта внедрили целый ряд улучшений, скрыли значения сумм переводов, а также усовершенствовали саму подпись. Тем не менее, существенной проблемой остается размер подписи и ее производительность, которые линейно зависят от количества элементов кольцевой подписи или же от размера кольца, и это накладывает определенные ограничения на уровень анонимности (на момент написания статьи, в Monero по умолчанию используется anonymity set 10).
В настоящее время, в рамках проекта Zano мы работаем над созданием такой подписи, в которой зависимость ее размера от количества decoys была бы логарифмической, что в свою очередь позволило бы нам значительно увеличить anonymity set, и, следовательно, повысить уровень приватности. Несколько месяцев назад у Anton Sokolov возникла интересная идея по реализации такой подписи , и после того, как он ее сформулировал и опубликовал ее базовые теоретические аспекты, мы решили объединить усилия, Антон присоединился к нашей команде и сейчас мы активно изучаем возможности построения технологии на базе этой подписи.
Если вы круто шарите в математике, то ознакомиться с этой работой можно здесь (работа периодически редактируется с учетом комментариев оппонентов). Однако, многие члены нашего сообщества, не являющиеся инженерами или математиками, просили нас в общих словах разъяснить суть идеи подписи и принципа ее работы. Мы задумались о том, как это лучше сделать, и Антон придумал довольно интересную аналогию в виде “барной метафоры”, приведенной ниже.
Возможно, прочтенное покажется вам каким-то сюром, и это нормально, т.к. описанное там на самом деле происходит “в другом измерении” и может странно восприниматься человеком со здоровой психикой. Этот текст мы писали для того, чтобы попытаться наглядно проиллюстрировать отправную концепцию этой теории, и, разумеется, такая метафора не объясняет полностью всю суть, это своего рода тизер, который может упростить понимание всей работы в целом.
Конкурс в баре
В городе есть бар. Горожане, посетители бара, обладают хорошим вкусом и всегда могут отличить на вкус один напиток от другого. Под напитками понимаются смеси разных компонентов, например, рома, водки, вина, фруктовых соков и т.п. Два напитка считаются одинаковыми, если процентное соотношение всех компонентов в одном из напитков равно процентному соотношению всех компонентов в другом напитке. В противном случае, напитки считаются разными.
Владелец бара объявляет конкурс, принять участие в котором может любой посетитель, желающий сыграть против владельца бара. Задача участника состоит в том, чтобы воспроизвести напиток, который при нем сделает бармен, но при этом участник должен следовать заранее определенной процедуре смешивания напитков, и если в конце всей процедуры выяснится, что сделанный участником напиток совпадает с напитком, сделанным барменом, то считается, что участнику удалось “пройти процедуру валидации” (или же сломать подпись и опровергнуть теорию). Если участнику удастся пройти процедуру валидации и, при этом, в его первоначальном бокале окажется смесь алкогольных и цитрусовых напитков, то он выигрывает, и владелец бара отдает ему даром всю выпивку с полок.
Для того, чтобы не отходить далеко от канвы математических рассуждений, представим себе, что в баре есть устройство, позволяющее смешивать напитки в определенных пропорциях. Например, в устройство можно вставить по бутылке водки и рома (или две емкости с какими-либо другими напитками), указать пропорцию 449/17, и получить на выходе емкость с напитком, содержащим 449 единиц водки на 17 единиц рома. Также в баре есть генератор случайных равномерно распределенных пропорций от 1/100000 до 100000/1. Конструкции устройства смешивания и генератора пропорций открытые, в правильности их работы никто не сомневается. Также, для полноты картины, в баре есть электронный дегустатор, которому на вход наливают два напитка, и у него загорается зеленая лампочка, если напитки одинаковые, и красная, если напитки разные. Электронный дегустатор никогда не ошибается, это могут подтвердить все жители города.
У бармена есть четыре больших ящика с одинаковыми бутылками рома, водки, лимонного и апельсинового соков, и в этом могут убедиться все. Так же всем известно, что если составить какой-либо напиток из этих четырех компонентов, то идентичный по вкусу напиток из других компонентов или из этих же самых компонентов с другим процентным соотношением составить невозможно. Под другими компонентами понимаются напитки, изготовленные из других продуктов, например, граната или молока. Смеси вышеперечисленных четырех компонентов не считаются другими компонентами.
Шаг 1: Итак, игра начинается с того, что участник ставит на свой стол бокал, помеченный буквой Z, с напитком, известным только ему. Участнику известны соотношения компонентов напитка в этом бокале, т.е. он знает рецепт приготовления содержимого Z, но держит этот рецепт в секрете. Известно только то, что согласно условиям, участник должен добавлять в Z и цитрус, и алкоголь. Вдобавок, участник ставит на стол второй помеченный H1 бокал с некоторым выбранным им самим содержимым, рецепт приготовления которого может быть ему как известен, так и неизвестен, т.е. участник волен налить в бокал H1 все что угодно.
Шаг 2: бармен получает пропорцию с11 от генератора случайных пропорций, смешивает ром и водку в этой пропорции и ставит на барную стойку бокал R1 с полученным алкогольным напитком. Затем, бармен получает пропорцию с13 от генератора случайных пропорций, смешивает лимонный и апельсиновый соки в этой пропорции и ставит на барную стойку бокал R2 с полученным цитрусовым напитком. Все посетители бара, включая самого участника, видят значения с11 и с13, а также то, что бармен готовит содержимое бокалов R1 и R2 из указанных компонентов и в указанных пропорциях.
Шаг 3: участник, зная пропорции с11 и с13, берет по части содержимого своих бокалов Z и H1 и смешивает их в некоторой определяемой им пропорции r1, и ставит на стол третий бокал S1 c полученной смесью. Участник может показать значение r1 всем, включая бармена, хотя бармену оно неинтересно. Все, включая бармена, следят только за тем, чтобы в бокале S1 была смесь только содержимого из Z и H1. Затем, участник каким-то образом готовит содержимое четвертого бокала H2 и ставит его на стол. Участник может показать всем, как он готовит содержимое H2, а может и не показывать. В бокал H2 участник волен налить все что угодно и в каких угодно пропорциях, и даже, как и в бокал H1, налить совершенно неизвестную жидкость.
Шаг 4: бармен получает пропорцию с2 от генератора случайных пропорций, смешивает содержимое бокалов R1 и R2 в этой пропорции и ставит на барную стойку бокал R с полученным алкогольно-цитрусовым напитком. Все видят пропорцию с2, а также то, что содержимое R честно получено в этой пропорции из содержимого R1 и R2.
Шаг 5: участник, зная теперь еще и пропорцию с2, смешивает содержимое бокалов S1 и H2 в некоторой определяемой им пропорции r2 и наливает результат в пятый бокал S2, который ставит на стол. Все следят за тем, чтобы в S2 было налито только содержимое бокалов S1 и H2.
Шаг 6: электронному дегустатору наливают из бокалов R и S2. Если загорелась красная лампочка, то игра заканчивается ничем, участник платит за использованные напитки. Если загорелась зеленая лампочка, то процедура валидации считается пройденной.
Теперь проводится финальная проверка: участник сообщает всем рецепт, т.е. компоненты и процентный состав содержимого своего бокала Z. Бармен готовит указанный состав и открыто сравнивает его на электронном дегустаторе с остатками содержимого в бокале Z, тем самым позволяя всем убедиться в том, что участник правильно назвал рецепт содержимого Z. Если участник дал неправильный ответ, то игра заканчивается ничем, участник платит за использованные напитки. Если же согласно рецепту оказалось, что в бокале Z присутствуют одновременно алкоголь и цитрусовый сок, то участник выигрывает и забирает себе всю выпивку с полок бара, которой там много.
Иными словами, в этой игре процедура валидации составлена владельцем бара так, чтобы участник не смог подобрать нужные соотношения смесей для получения аналога R при условии, что в бокале Z присутствуют компоненты обоих смесей, а именно: крепкий алкоголь (ром и водка) и цитрусовые (лимонный и апельсиновый сок). Зеленая лампочка никогда не загорается при сравнении R и S2, если в Z находится, например, смесь ром-апельсиновый сок или ром-водка-лимонный сок, или же водка-лимонный-апельсиновый сок, и т.д. Вернее, в таких случаях она может загореться только с пренебрежимо малой вероятностью, и владелец бара, который немного шарит в математике, об этом знает.
Для посетителей бара это может быть неочевидно, они рассуждают приблизительно так: допустим, мы не будем добавлять в бокал Z никаких других компонентов кроме рома, водки, лимонного и апельсинового соков, потому что если мы добавим что-то еще, например, молоко, то оно обязательно будет присутствовать в S2 и, таким образом, в S2 всегда будет что-то, отличающееся от R. Но если мы нальем в Z, например, ром и лимонный сок, то зная c11, c13, c2 и обладая возможностью выбирать содержимое H1, H2 и пропорции r1, r2, мы всегда сможем уравновесить состав S2 так, чтобы он стал идентичной версией R.
Таким образом, посетители бара начинают участвовать в конкурсе, стараясь обмануть процедуру валидации. Но, увы, никто из них не способен подобрать H1, а затем и r1 и H1 в ответ на c11 и c13, затем r2 в ответ на c2 так, чтобы составы S2 и R оказались одинаковыми, если в Z присутствуют в ненулевых пропорциях алкоголь и цитрусовый сок.
Со временем становится понятно, что если налить в бокал Z, например, только алкоголь, т.е. смесь рома и водки, налить в H1 чистую водку, затем подобрать r1 так, чтобы в S1 получилось то же самое, что и в R1, а в H2 налить лимонно-апельсиновую смесь в пропорции c13, то в S2 можно легко получить то же самое, что и в R.
Часть 2
Видя угасающий интерес к игре, владелец бара объявляет о том, что теперь, если игра не закончилась на пятом шаге процедуры валидации, то финальная проверка будет более мягкой. Теперь финальная проверка будет следующей: если доказано, что в бокале Z находится только алкоголь, то достаточно предоставить доказательство того, что в одном из бокалов H1 или S1 присутствует цитрусовый сок, и тогда участник выигрывает. Если же доказано, что в Z находится только цитрусовый состав, то достаточно предоставить доказательство того, что в одном из бокалов H1 или S1 присутствует алкоголь, и тогда участник тоже выигрывает.
Но, опять никто не может выиграть и забрать всю выпивку с полок бара. Тогда владелец приносит и устанавливает в баре некоторый аппарат под названием “Инвертор Напитков”. Этот аппарат принимает на вход бокал любого, даже неизвестного напитка и возвращает на выходе бокал с таким же количеством анти-напитка. Например, если подать инвертору напитков на вход бокал водки, то на выходе получится бокал с таким же количеством анти-водки или минус-водки. Если теперь налить в бокал определенное количество единиц водки и столько же единиц минус-водки, то на выходе окажется пустой бокал. То же самое будет, если добавить единицу минус-водки в бокал, где есть по три единицы джина и рома, а затем результат добавить в бокал с четырьмя единицами водки. В этом случае получится бокал с тремя равными частями джина, рома и водки.
Владелец бара объявляет о том, что теперь при составлении содержимого всех бокалов в игре можно использовать генератор анти-напитков. В генератор случайных пропорций добавляют отрицательные пропорции, то есть, один из компонентов при смешивании пропускается через анти-генератор. Процедура валидации остается прежней, только с одним условием: никакое из соотношений r1 и r2 не должно быть нулевым, а также ни один из бокалов во время валидации не должен оказаться пустым. Под чистой алкогольной смесью теперь понимается смесь, состоящая только из алкогольных компонентов, добавленных в положительной или отрицательной пропорции, точно так же как и в случае с чистой цитрусовой смесью.
Ну уж теперь, казалось бы, процедуру валидации и облегченную проверку можно будет обойти и выиграть. Однако, по-прежнему никто не в состоянии подобрать H1, затем r1 и H1 в ответ на c11 и c13, затем r2 в ответ на c2 так, чтобы составы S2 и R оказались идентичными, если в Z, H1 и S1 присутствует что-то, отличающееся либо от чистой смеси рома и водки, либо от смеси лимона и апельсина.
Часть 3
Процедура валидации, придуманная владельцем бара, похожа на криптографическую схему Lin2-Xor леммы в драфте на eprint. Заметив это сходство, горожане интересуются, почему смеси напитков в бокалах ведут себя как элементы циклической группы простого порядка, где discrete logarithm problem is hard, или даже как точки основной подгруппы криптографической кривой ed25519, используемой в системе Zano?
Ответ прост: при условии наличия генератора анти-напитков, смеси напитков в бокалах обладают теми же свойствами, что и точки основной подгруппы кривой ed25519. Вернее, у точек на ed25519, конечно же, больше интересных свойств, но свойства, используемые в Lin2-Xor лемме, те же самые.
Поэтому, если кто-то из участников конкурса все-таки сможет выиграть всю выпивку с полок, это будет подразумевать опровержение Lin2-Xor-леммы.
Каким образом такие чистые напитки, как ром, водка, лимонный и апельсиновый соки в емкостях у бармена соответствуют точкам (элементам группы) P1, Q1, P2, Q2 в условии леммы? Точки P1, Q1, P2, Q2 обязаны быть такими, чтобы ни одна из них не являлась линейной комбинацией (смесью) других из этого же набора. Это достигается путем применения идеальной хэш-функции на точках кривой. То же самое проделываются и с базовыми напитками. Например, лимонный сок не должен получаться путем смешивания рома, водки и апельсинового сока в любых, в том числе и отрицательных пропорциях.
Это во многом похоже на метафору со смешиванием красок, только существует всего лишь три базовых цвета красок, из которых по всеобщему убеждению составляются все другие цвета. С напитками легче: можно добавить к этим четырем еще сколько угодно, и их удобно объединять в пары, например, вино красное и белое, молоко и йогурт…, можно смешивать даже кока-колу с пепси-колой. Кстати, объединение в пары чисто условное, для наглядности.
Теоретически, для объяснения можно было бы использовать многомерные линейные пространства, но считается, что пытаться представить себе воочию четырехмерное пространство вредно для здоровья, поэтому пока-что выбраны напитки. Тем не менее, говоря откровенно, уравнения для барных напитков те же самые, что и для многомерных линейных пространств.
Следует уточнить что означает “единица напитка” в терминах точек на криптографической кривой, ведь мы не можем отмерить “единицу точки на кривой”, мы можем оперировать только самой точкой, т.е., умножать ее на число, делить, инвертировать, и складывать с другими точками. Да, как такового понятия “единица точки на кривой” нет, но во всех процедурах конкурса “единицы напитка” берутся только в соотношении к “единицам другого напитка”, т.е. “единицы” используются только для составления пропорций. А из точек кривой, т.к. они умножаются на числа и складываются, также можно создавать пропорции.
И для напитков, и для точек кривой, если задана пропорция двух напитков (точек), не представляется возможным разгадать соотношение компонентов в ней не обладая какой-то дополнительной информацией, например, рецепта приготовления. Что касается линейных пространств, для них напитков с базисом из компонентов типа водки, рома, соков и т.д., равно как и для линейного пространства точек криптографической кривой с базисом из хэшей точек на кривой, не задана функция “inner product”, поэтому проекции и длины в этих пространствах не определены.
Является ли сравнение напитков на электронном дегустаторе сравнением точек на равенство? Почти, только с тем отличием, что электронный дегустатор менее критичен к напиткам, чем проверка на равенство. Электронный дегустатор не чувствителен к объему напитков на входе, т.е. в терминах точек он сравнивает две точки с точностью до какого-то известного числа, на которое одна из них умножается. Таким образом, дегустатор не уменьшает шансы участников на обман процедуры верификации по сравнению с использованием чистой проверки на равенство для точек.
Часть 4
Еще одним важным элементом новой подписи является Lin2-Selector лемма, и для ее описания в контексте той же барной метафоры мы снова поменяем игру следующим образом: теперь у бармена есть не четыре, а восемь базовых напитков: ром и водка, лимонный и апельсиновый соки, красное и белое вино, швепс и кока-кола. Если участнику удастся составить в бокале Z что-то отличное от одного из четырех: только крепкий алкоголь, только цитрусовый сок, только винная смесь, только газировка, и пройти процедуру валидации с финальной проверкой, то он выигрывает.
Процедура валидации теперь немного удлиняется. Вместо двух первых шагов, на которых, с одной стороны, бармен генерирует случайные пропорции вначале (с11, с13), а затем с2, и, соответственно, смешивает базовые напитки, а с другой стороны, участник составляет вначале пропорцию и бокал (r1, H2), а затем пропорцию r2, и смешивает свои напитки, теперь происходят три шага. Со стороны бармена эти три шага выглядят как генерация (с11, с13), затем (с21, с23), затем с3, и, соответственно, смешивание. Co стороны участника три шага выглядят как составление (r1, H2), затем (r2, H3), затем r3, и смешивание.
При этом оказывается, что процедура валидации пропускает только указанные выше четыре смеси, и непонятно, как ее можно обмануть. Более того, если у бармена будет шестнадцать базовых напитков и он будет генерировать (с11, с13), (с21, с23), (с31, с33), с4, а участник будет генерировать (r1, H2), (r2, H3), (r3, H4), r4, то процедура валидации будет пропускать только восемь смесей пар базовых напитков. Таким же образом можно использовать 32 базовых напитка, 64, 128 и т.д., и получать одну из, соответственно, 16, 32, 64 смесей пар напитков. Это протокол Lin2-Selector леммы.
Вернемся к точкам на криптографической кривой. Если взять, скажем, 1024 базовых точек, объединенных в 512 пар, то протокол Lin2-Selector леммы позволяет выбрать линейную комбинацию точек из ровно одной пары, не пропуская никакие другие точки или комбинации. При этом требуется порядка log(1024) шагов, т.к. каждое удвоение базового набора точек требует прибавления одного шага в процедуру верификации.
Если провести аналогию с Merkle Tree, то, не вдаваясь в детали реализации, там так же, для доказательства принадлежности некоторого элемента к некоторому фиксированному множеству элементов требуется создать журнал шагов. Основное отличие состоит в том, что в Merkle Tree мы обязаны раскрыть тот элемент, для которого мы доказываем принадлежность к фиксированному множеству. В протоколе Lin2-Selector леммы мы достаточно легко можем хорошо скрыть тот элемент, для которого мы доказываем принадлежность к множеству.
В терминах игры в баре, корень Merkle Tree представляет из себя подобие бокала R, приготавливаемого барменом, хотя действия бармена для Merkle tree отличаются. А доказательство принадлежности напитка в стакане Z множеству базовых напитков представляет из себя последовательность из log числа бокалов H1, H2, H3, …. При этом для Merkle tree критически важны как состав содержимого бокалов, так и точный объем содержимого. В то же время, для протокола Lin2-Selector леммы объем содержимого бокалов не важен, важны только пропорции компонентов. В случае с Merkle Tree обойтись одними пропорциями никак нельзя.
Постойте, но ведь Merkle tree это не интерактивная структура данных, а протокол Lin2-Selector леммы и конкурс в баре - это интерактивные игры между двумя участниками, как же в таком случае сравнивать не интерактивную структуру с интерактивной игрой? Сравнивать можно, дело в том, что в криптографии многие интерактивные игры переводятся в неинтерактивные с помощью приема, называемого эвристикой Фиата-Шамира. Это настолько широко применяемый прием, что мы на нем не будем останавливаться, и рассматриваем неинтерактивную и интерактивную версии протоколов Lin2-Xor и Lin2-Selector одновременно. Т.е. мы сравниваем неинтерактивную версию протокола Lin2-Selector леммы и неинтерактивное Merkle tree.
Согласно Lin2-Selector лемме, чтобы скрыть элемент множества, доказывающий предоставляет не сам элемент множества, а этот элемент умноженный на какой-то секретный скаляр, а также предоставляет доказательство для него. Т.е. доказывающий предоставляет не тот конкретный бокал с апельсиновым соком, который у него есть, а, скажем, 1/379 этого бокала, и держит число 1/379 в секрете. А хорошо ли это скрывает апельсиновый сок в бокале? Ну, конкретно апельсиновый сок это не скрывает никак, но если ме говорим о точках криптографической кривой, то скрывает абсолютно, также, как например публичный ключ полностью скрывает приватный ключ. Это обусловлено тем свойством криптографической кривой, что discrete logarithm problem is hard на ней.
Может возникнуть логичный вопрос, зачем нужны пары элементов? Пары элементов нужны только для того, чтобы применять Lin2-Xor и Lin2-Selector леммы, это техническая необходимость. Мы делаем один из элементов в каждой из пар таким, чтобы доказывающий не мог его смешивать с другими элементами, это легко сделать. К слову, этот технический элемент только добавляет анонимности.
Как сказанное выше соотносится с линкинг тегом, не забыли ли мы про него? А линкинг тег формата CryptoNote (совсем немного модифицированный) нам только помогает, т.к. если смешать этот линкинг тег с публичным стелс-адресом, то у нас получается как раз линейно независимый базовый элемент, который нам нужен в Lin2-Xor и Lin2-Selector леммах. Чтобы получить log-size ring signature, мы составляем базовые элементы кольца именно таким образом, а затем отправитель анонимно доказывает, что он знает приватный ключ одного из этих элементов.
Заключение
Надеюсь, вам понравилась статья. Ну а если кто-то заметил ошибки тут или в самой работе, пишите нам - мы всегда рады оппонентам!
