22/06/2019
Шри Аравинда Кришнан Тайгараян является аспирантом Университета Эрлангена — Нюрнберга, Германия, под руководством профессора Доминика Шрёдера (Dominique Schroeder). Специализируется в анализе теоретических формулировок и различных проблем, связанных с блокчейном и криптовалютами, в частности, с конфиденциальностью, анонимностью, масштабируемостью и другими вопросами.
Аннотация
Для обеспечения анонимности и конфиденциальности Monero использует протокол кольцевых конфиденциальных транзакций RingCT. Предшествующие попытки анализа схем RingCT были либо неформальными, им не хватало фундаментальной функциональности, либо они использовали нежелательные допуски доверенной настройки. Более того, используемая в настоящее время Monero схема RingCT ограничивает ряд анонимов из-за размера доказательства траты, который растёт линейно с размером кольца. В качестве решения этих проблем нами предлагается первая полная и точная формализация RingCT. Затем нами также предлагается типовая конструкция RingCT и доказательство её безопасности в рамках нашей формальной модели безопасности. Дополняя нашу типовую конструкцию эффективными доказательствами с нулевым разглашением конфиденциальной информации, расширяющими доказательства Bulletproofs, мы получаем Omniring — первую схему RingCT, которая 1) не требует доверенных настроек или попарного объединения, 2) обладает логарифмическим доказательством размера кольца и 3) позволяет использовать одно и то же кольцо всеми исходными счетами транзакции. Omniring позволяет значительно повысить уровень анонимности без ущерба для производительности.
Стенограмма:
Итак, всем доброго утра, я рад видеть вас на моём выступлении. Для начала я должен отметить, что для меня большая ответственность открывать эту конференцию своим докладом. Посмотрим, насколько хорошо я смогу справиться с этим делом.
Спасибо за вступление, я буду говорить о нашей работе под названием Omniring. Она в основном сфокусирована на формализации функций кольцевых конфиденциальных транзакций, гарантий безопасности. Также нами предлагается эффективная структура, которая может практически немедленно быть реализована криптовалютой Monero.
Итак, конфиденциальные кольцевые транзакции предполагают наличие трёх компонентов: первым является анонимность отправителя, затем идёт конфиденциальность суммы, а затем — анонимность получателя. И именно это в настоящее время используется Monero для обеспечения конфиденциальности и анонимности. Анонимность отправителя гарантируется примитивом, схожим со связываемой кольцевой подписью и обеспечивающим анонимность и ряд анонимов, а также возможность обнаружения попыток двойной траты.
Немного остановимся на вступлении, начнём с кольцевых подписей. Верификатор может проверить подпись на документе, подписанном от лица ряда анонимов. В этом случае красному пользователю известно, что документ был подписан одним из этих трёх пользователей, но ему неизвестно, кто точно сделал это.
Перейдём от кольцевых подписей к связываемым кольцевым подписям, где верификатор может связать между собой две подписи, если обе они были подписаны одним и тем же подписантом из ряда анонимов. В случае Monero это аналогичным образом позволяет обнаруживать атаки с попыткой двойных трат. Хорошо, итак, следующим компонентом является конфиденциальность суммы, которая достигается при помощи обязательств Педерсена. Таким образом, сумма скрывается внутри обязательства, но сохраняется возможность проверки, являются суммы пропорциональными или нет. Рассмотрим это подробнее на примере: зелёный пользователь закладывает сумму, равную 23, в обязательство, так, и отправляет данное обязательство вот этому красному пользователю. Безусловно, злоумышленнику неизвестно, что находится внутри обязательства, пока не известно, и не будет известно впоследствии. Затем ключ, информация, открывающая обязательство, передаётся красному пользователю, который теперь может открыть обязательство и проверить… проверить сумму, которая была внутри него. Злоумышленник или любой внешний пользователь может проверить, являются ли суммы в этих обязательствах, которые зелёный пользователь передал красному пользователю, действительно пропорциональными. Это единственная информация, которую может получить внешний пользователь.
Третьим компонентом является анонимность получателя, которая обеспечивается так называемыми скрытыми адресами. Я напрямую перейду к объяснению того, что собой представляют скрытые адреса. Итак, в данном случае синий пользователь, который хочет получить деньги, отправляет свой долгосрочный адрес, который является главным публичным ключом для других пользователей, от которых он и хочет получить деньги. Красный пользователь подписывает некоторую сумму денег и отправляет её пользователю, никто не знает кому, и это происходит снова и снова. Но суть в том, что адреса всех этих трёх получателей на самом деле были выведены на основе этого главного публичного ключа, который был выдан синим пользователем. Но злоумышленник не знает этого, что он не знает, что все эти новые получатели на самом деле принадлежат одному и тому же пользователю. Таким образом, адреса получателей неотделимы друг от друга.
Хорошо, итак, каковы же свойства RingCT, связанные с обеспечением безопасности? Первым является сбалансированность, то есть сумма, которая есть у пользователя, это именно та сумма, которую он тратит, и не более того. И очевидно, пользователь не должен осуществлять двойной траты. Таким образом, достигается анонимность: обеспечивается анонимность отправителя, анонимность получателя, а сумма транзакции также скрыта.
Третьим свойством является невозможность «оговора», то есть злоумышленник не может подписать действительный документ от лица честного пользователя. Также это свойство можно рассматривать в качестве невозможности подделки цифровой подписи. Почему нам необходимо формализовать функционал и гарантии безопасности? Потому что это создаёт конкретное основание для разработки ваших протоколов, для понимания, какие гарантии безопасности обеспечивает протокол. И как только понятия безопасности будут формализованы, то вы получите множество протоколов, которые можно будет сравнить на базе их эффективности, и так далее и тому подобное. И тут нет повода для беспокойства, вроде: «Ох, этот протокол даёт мне одну гарантию, а другой протокол иную». Это компромисс. Об этом более не придётся беспокоиться. Это просто даёт основу для сравнения различных протоколов.
Естественно, если вы заканчиваете без формализации, временами могут возникать проблемы, и в одной из наших работ нами была рассмотрена возможность атаки с отрицанием траты (на базе модели Zerocoin). В нашем случае злоумышленник мог создать транзакцию и использовать тег честного пользователя, и потратить транзакцию, которая была бы действительной. Теперь, если злоумышленник решит сделать это, честный пользователь, когда бы он не вышел онлайн или же когда бы он не попытался потратить свою транзакцию с тем же тегом, всё всегда закончится двойной тратой, поскольку пользователи могут связать эти теги, и им будет известно, что по этому тегу уже были потрачены деньги. Таким образом, злоумышленник принуждает честного пользователя не тратить эти деньги. И мы выяснили, что этот баг был характерен для множества монет, и также баг был в формальной модели, которая изначально была предложена в 2016. Но не в самой схеме, а в модели гарантии безопасности.
Уже было сделано две попытки формализации RingCT. Первая состоялась в 2017, попытка реализации версии RingCT 2.0., тогда не получилось формализовать скрытые адреса и, таким образом, не была охвачена гарантия анонимности получателя. И определения безопасности были слабоваты в том смысле, что не было охвачено множество сценариев, и закончилось всё необходимостью использования доверенных настроек с целью повышения эффективности предложенной конструкции. Самой последней попыткой стала версия RingCT 3.0. Вы можете видеть все итерации и цифры. Определение анонимности в данном случае разделяется между анонимностью получателя и анонимностью отправителя, и неясно, обеспечивают ли эти два определения в совокупности анонимность всей системы. Определения сбалансированности были чуточку слабы в сравнении с тем, что предлагается нами, в том смысле, что либо ограничивалась мощь злоумышленника, либо усиливались допуски.
Чтобы кратко описать то, что сделали мы. Прежде всего, нами предлагается сильная модель, в том смысле, что мы охватываем скрытые адреса, обеспечивающие анонимность получателя. Также мы охватываем проблему «просматриваемости» и отслеживаемости, которая актуальна для Monero сегодня. В конечном счёте мы даём сильные гарантии безопасности с точки зрения сбалансированности и анонимности, обеспечивающие гарантию всеобъемлющей анонимности. И нами создаётся «кольцо всевластия», раз уж мы говорим о кольцах, которое позволит повысить эффективность и анонимность. Я вернусь к этому позднее. У нас меньше допусков, в том смысле, что нам не приходится полагаться на какие-либо внешние безопасные каналы между пользователями — всё делается в реестре.
Теперь я перейду непосредственно к формализации функций. Пользователи, очевидно, хотят настроиться и подсоединиться к сети. Поэтому сначала пользователь запускает и настраивает алгоритм, генерирующий публичные параметры, необходимые для реализации схемы RingCT. Затем создаются скрытые адреса, необходимо создать этот одноразовый адрес на базе алгоритма создания ключа скрытых адресов, который выводит главный публичный ключ и главный секретный ключ, что делается один раз. Транзакция в нашем варианте формализации, по сути, представляет собой кольцо счетов, тегов счетов, которые тратят деньги, и целевых счетов, а также некоторое произвольное сообщение или метаданные.
Как вы производите трату? Чтобы потратить средства, пользователю сначала необходимо узнать, какие счета являются целевыми, на какие счета он будет отправлять деньги. Он запускает вот этот алгоритм создания одноразового счёта. Он берёт главный публичный ключ получателя и сумму, которую хочет передать получателю, алгоритм выдаёт ключ монеты для этой монеты и счёт целевого пользователя. Этот ключ монеты можно считать «фактором ослепления» или «фактором случайности», который включается в обязательство по монете. Как только адрес получения или целевой счёт будут заданы, пользователю станет понятно, куда отправлять деньги. Затем запускается алгоритм траты, который берёт кольцо счетов и исходный счёт, с которого будут отправлены деньги, целевой счёт, на который необходимо отправить деньги, и некое сообщение. На выходе получается подпись или доказательство траты, которое публикуется в реестре.
Как только доказательство траты транзакции попадёт в реестр, необходимо будет проверить, что всё сделано, как надо, поэтому алгоритм верификации проверяет пропорциональность сумм между исходными счетами и целевыми счетами и, во избежание двойной траты, проверяет, не повторяются ли теги. Также он проводит критически важную проверку, в какой момент счета, используемые в кольцах, стали целевыми. Пользователь не может генерировать новый счёт из воздуха и включать его в кольцо.
Переходим к получению. Деньги были отправлены получателю, и теперь ему необходимо сделать что-то, чтобы полученные им средства снова можно было потратить. Поэтому он запускает алгоритм получения, который берёт главный секретный ключ этого получателя, а также целевой счёт, который был указан в транзакции, и алгоритм выдаёт ключ монеты, который необходимо знать, сумму, одноразовый секретный ключ и тег. При наличии этой информации средства можно будет потратить, когда это будет необходимо для чего-либо. Но необходимо выполнить ещё одну дополнительную проверку. Когда получатель раз за разом в различное время принимает средства, ему необходимо знать, что каждый раз получаемый им тег будет другим, в противном случае он может дважды получить деньги с одним и тем же тегом, но сможет потратить этот тег лишь единожды. Это означает, что пользователь может потратить полученные средства только один раз, и ему необходимо гарантировать это.
Такие образом, наш вариант реализации структуры RingCT осуществляется в два этапа. На первом этапе мы создаём общую структуру, где отправитель, кем бы он ни был, производит трату, использует сложный язык и забрасывает всё в бокс «подписи знания» (Signature of Knowledge, SoK), из которого выводится доказательство траты. На следующем этапе я расскажу о подписи знания. Следующий этап необходим для реализации подписи знания. Мы опираемся на концепцию Bulletproofs, которая была предложена Бунсом и др. в 2018 году. Следует отметить, что она уже используется Monero для обоснования доказательств диапазона суммы, когда отправителю необходимо доказать, что сумма, скрытая в доказательстве, находится в пределах определённого диапазона. Ему необходимо делать это, и для этого уже используются Bulletproofs. Bulletproofs позволяют доказать алгебраические отношения между цифрами, но, к сожалению, они сами по себе не подразумевают использования кольцевых подписей или RingCT. Здесь ещё требуется немного поработать и расширить эти доказательства до RingCT. Таким образом, мы расширяем концепцию Bulletproofs до системы доказательств с нулевым разглашением конфиденциальной информации, где отношения могут быть доказаны посредством дискретного логарифма (DLOG), и заметьте, что наше доказательство может работать не только с алгебраическими отношениями чисел, но и с групповыми элементами. Это немного техническая сторона, которую постараюсь пройти побыстрее.
Этап 1 является наивысшей ключевой точкой типовой структуры. Мы используем систему шифрования публичного ключа для обеспечения возможности просмотра и отслеживания, чем устраняем какие-либо допуски, связанные с использованием безопасных каналов между пользователями. И вот тут появляется «кольцо всевластия». У нас может быть множество трат, что означает траты с множества счетов с одним и тем же кольцом, и нам абсолютно не нужно создавать отдельное кольцо для каждой траты. Это даёт нам k из kn схемы обеспечения анонимности, где k обозначает количество счетов, с которых вы хотите произвести трату, а kn обозначает размер кольца. И если один из ключей или одна из трат с этих счетов будет деанонимизирована, у нас всё ещё будет оставаться k-1 из kn-1. Давайте я покажу это наглядно. Так как это первое выступление сегодня. Допустим, есть аккаунты, происходит трата с использованием трёх колец. Стрелками показано, кто фактически совершает трату. Допустим, первый парень, синий парень, деанонимизируется, и это означает, что всё кольцо становится бесполезным с точки зрения анонимности двух других отправителей. Но теперь, предположим, что у вас одно кольцо и множество отправителей, в данном случае их трое, и если один из них будет деанонимизирован, то будет раскрыт только его ключ, который уже никак не влияет на анонимность остальных отправителей — у вас по-прежнему есть большое кольцо, обеспечивающее анонимность двух других счетов. Вот такую возможность обеспечивает наша типовая структура.
Теперь перейдём к реализации нашей схемы Omniring. Это первый раз, по-моему, когда Omniring упоминаются. Итак, мы реализуем схему шифрования публичного ключа, эллиптическую кривую, интегрированную в схему шифрования из Shoup'01. У нас есть обязательства Педерсена для конфиденциальных транзакций. У нас есть псевдослучайная функция (PRF) для присвоения счетам тегов, и мы реализуем подпись знания, наш расширенный вариант Bulletproofs, который я вам вкратце сейчас обрисовываю.
Доказательства Bulletproofs — как они работают? Как я уже говорил, они подтверждают доказательства диапазона суммы, они указывают, что это значение находится в пределах определённого диапазона. То есть они представляют это значение в выражении вектора a и вектора b, и обязательства по этому вектору в форме заглавной A на этапе номер два. И они доказывают это сложное отношение, чтобы продемонстрировать, что сумма действительно находится в пределах определённого диапазона.
Ключевым недостатком обоснования правильности этого доказательства является то, что доказывающей стороне неизвестно какого-либо нетривиального представления дискретного логарифма идентичности относительно основания, на котором было фактически сгенерировано обязательство A. В нашем случае мы хотим, чтобы участие в кольце было таким, чтобы было некоторое кольцо ключей, а вам бы было необходимо доказать знание индекса Portecle, то есть секретного ключа Portecle для получения кольцевой подписи RingCT. В данном случае проблема заключается в том, чтобы включить это отношение в обязательство A, которое я показывал ранее. А ещё более важной проблемой, по сути, является доказывающая сторона, как бы отправитель совершал трату и он может узнать отношения между различными ключами кольца по дискретному логарифму. Это не позволяет нам использовать доказательство надёжности Bulletproofs как таковое. Так что нам необходимо сделать что-то иное, и мы делаем это. Мы делаем это фактически путём обязательства, поэтому a с другим основанием, где вектор g, который использовался нами до этого, заменяется вектором gw, который гарантирует, что отношения между ключами кольца по дискретному логарифму более не будут известны доказывающей стороне. Теперь у вас есть обязательство для этого нового основания, вы, как и раньше, дважды запускаете систему Bulletproofs и получаете свидетельство и доказательство надёжности. Двукратное использование Bulletproofs потенциально может потребовать некоторых затрат и некоторой оптимизации, которая будет довольно простой. То есть в конечном счёте вы сможете использовать Bulletproofs только один раз.
Хорошо, итак, мы прошли первый и второй этапы Omniring, мы реализовали схему, и у нас есть некоторая оптимизация, так что мы можем позаимствовать технику групповой верификации, которая также используется Bulletproofs. К сожалению, Исследовательской лабораторией Monero были найдены некоторые ошибки в представленных нами числах, и причина этих ошибок заключается в том, что, по сути, наше доказательство безопасности не позволяет нам улучшиться настолько, насколько нам хотелось бы. Но сейчас мы работаем над исправлениями, и мы надеемся, что мы получим то, на что надеялись до этого, я надеюсь. Мы бы могли сделать размер транзакции логарифмически пропорциональным размеру кольца. Я имею в виду, конечно же, что размер доказательства станет логарифмическим, поскольку мы прекратим использовать Bulletproofs. И настроенный целевой счёт, и настроенные исходные счета обычно малы, так что всё прекрасно. Как правило, всё кольцо отправляется как часть транзакции, а это означает, что размер транзакции может быть линейно пропорционален размеру кольца, которое вы отправляете. Но мы могли бы использовать логарифмическое описание размера кольца, прибегнув к технике Чатора и Грина, представленной в 2018 и названной техникой «выборки восстановления». Это означает, что теперь у нас есть не только доказательства логарифмического размера, но и транзакции логарифмического размера.
Асимптотически я знаю, что это неинтересно, но я всё-таки немного перейду к конкретным цифрам. Итак, асимптотически, просто чтобы сравнить некоторые структуры, которые у нас имеются к этому моменту. Как вы могли заметить, первой являются доказательства диапазона Bulletproofs Monero, которые используются в настоящее время. Подпись или размер доказательства траты находится в линейной зависимости от размера кольца, а в случае с 2.0 уже более не зависят от размера кольца, но следует отметить, что они используют попарное объединение и доверенные настройки для достижения эффективности, и у них есть реально глубоко скрытые в структуре коэффициенты. В версии RingCT 3.0 размер доказательства уже получился длиннее размера кольца, но доказательство диапазона и доказательство RingCT не интегрируются в одну систему, как у нас, и поэтому в исходной концепции множится коэффициент размера, а у нас, по сути, он находится внутри логарифмического выражения, вот здесь.
Что насчёт конкретных цифр? Размер доказательства в выражении групповых элементов, который на сегодня использует размер кольца равный одиннадцати, в случае с Omniring составляет что-то от двадцати до тридцати групповых элементов, в то время как сегодня Monero использует от тридцати до сорока. Как видите, по мере увеличения размера кольца разница становится более очевидной. Если вы захотите, чтобы размер кольца составлял 128, то значение Omniring будет по-прежнему составлять около тридцати, в то время как в настоящее время у Monero он взлетел бы до семисот. Это размер доказательства.
Что насчёт времени, необходимого для вычисления доказательства такого размера? На сегодняшний день Omniring требует чуть больше времени, чем Monero, но ненамного. По мере увеличения размера кольца разница немного вырастет, но не достигнет непозволительного предела. Гораздо важнее время верификации. Тут следует отметить, что эти цифры указаны без учёта групповой верификации, над которой мы по-прежнему работаем. В случае с Omniring по мере увеличения размера кольца время, необходимое для верификации, составит менее нескольких десятых в миллисекундах, в то время как в случае с Monero оно возрастает, разницу можно увидеть здесь. И мы надеемся, что в случае с групповой верификацией цифры будут лучше.
Можно ли использовать Omniring в Monero уже сегодня? Я надеюсь, что кто-то думает над этим. Если да, то вы сможете. Нам необходимо изменить язык, который должен быть совместим с тегами, которые в настоящее время используются Monero, так что, как только вы начнёте использовать Omniring, схема должна будет иметь обратную совместимость с тем, что использовалось Monero вплоть до сегодняшнего дня. Таким образом, получится предотвратить и возможность двойной траты. Если вы измените этот язык, заметьте, мы сохраним эффективность, которая была показана мною асимптотически, а также конкретную эффективность, которая была мною показана только что. Мы по-прежнему можем видеть цифры.
И чтобы как-то завершить моё выступление. Очень важно формулировать функции и гарантии безопасности при разработке системы. В частности, учитывая ту критическую и монетарную важность, что играет Monero в сегодняшнем мире, и в случае с выбором кольца, согласно RingCT, когда вы выбираете ключи, которые войдут в ваше кольцо, это критически важно, и мы активно работаем над решением проблемы. Вскоре должна выйти соответствующая статья. Наша типовая структура, продемонстрированная мною, которой я вкратце коснулся, совместима с любыми будущими криптографическими усовершенствованиями, которые могут быть реализованы. С точки зрения систем доказательства, каких угодно, это доказательство будущего. Структура Omniring, предполагающая использование одного кольца для множества трат, фактически гарантирует, что вы сможете использовать кольца большого размера. А это означает повышение уровня анонимности, а также большую анонимность ключей траты, которые вы используете в Monero. Таким образом, это подразумевает повышение уровня анонимности Monero в целом.
Это всё. Спасибо за внимание. Пожалуйста, ознакомьтесь с нашей работой, это новая публикация, 580, это наш код. А теперь, пожалуйста, ваши вопросы.
Перевод: Mr. Pickles
Редактирование: Agent LvM
Коррекция: Kukima