23/06/2019
Саранг Ноезер (Sarang Noether) является математиком и криптографом и занимается исследованиями и разработкой в составе Исследовательской лаборатории Monero. Он обладает большим опытом в обучении и выступлениях по всему миру в области математики, технологий и прикладной криптографии.
Аннотация
Протокол транзакций Monero использует несколько криптографических конструкций, работающих в тандеме; сюда входят связываемые кольцевые подписи, обязательства Педерсена и доказательства диапазона. Каждый из компонентов модели транзакций предполагает наличие издержек, которые влияют на параметры производительности сети и опыт пользовательского взаимодействия. В рамках данного выступления будут рассмотрены прошлые и нынешние попытки улучшения пространства транзакций и временных параметров. Нами будут рассмотрены протокол Bulletproofs, используемый для доказательств диапазона, изменения в связи элемента Педерсена с целью сокращения размера выхода, а также компактные LSAG-подписи, позволяющие оптимизировать кольцевые подписи. Предполагается, что для понимания этих конструкций не требуется никакого предварительного опыта, поэтому выступление будет доступным для каждого!
Стенограмма:
Шурэ: Следующим выступит Саранг Ноезер, один из оплачиваемых членов Исследовательской лаборатории Monero, и он расскажет об эффективности транзакций тогда и сейчас.
Саранг: Приветствую всех, я снова с вами. Я случайно появлялся в течение всей конференции, чтобы помогать по необходимости, и сегодня уже я сам расскажу вам об эффективности транзакций, немного о том, какой она была тогда и какой она является сегодня. Частично моя цель состоит в том, чтобы создать у слушателей представление о том, как транзакции развивались со временем с точки зрения размера и эффективности временных параметров, а также рассказать, что мы делаем, чтобы улучшить их.
Итак, я не стану говорить о новых причудливых решениях, связанных с масштабированием, мы поговорим о вещах, которыми мы занимались в прошлом, и это будет прекрасной возможностью, чтобы представить, куда транзакции, возможно, будут двигаться в ближайшем будущем. Так, клик, теперь я понимаю, чем все недовольны, ха! Ха-ха! Спасибо. Нет, О’Кей, продолжаем. Всё хорошо. Итак, начну с обычной оговорки: я выступаю от своего имени. Исследовательская лаборатория Monero — это рабочая группа в рамках проекта Monero. Но каждый её член работает как бы сам по себе в соответствии со своей исследовательской повесткой, поэтому я здесь буду выступать от своего лица, и что касается финансов — я получаю финансовую поддержку от сообщества Monero через систему CCS, что уже упомянул Брендон.
Прежде всего, что имею в виду, когда говорю об эффективности транзакций? То, о чём я говорю, вообще никак не связано с анонимностью, несмотря на то, что эффективность транзакций со временем может открыть дверь к изменению параметров в рамках протокола, что повлияет и на анонимность. Такие вещи, как размер кольца, могут служить наиболее распространённым примером, но мы рассмотрим конкретные аспекты эффективности, первым из которых является пространство. Это ракета, которая летит в космосе. Вторым аспектом является время генерирования, то есть, если я хочу создать транзакцию, чтобы перевести какие-то средства со своего кошелька кому-то ещё, это определённо займёт какое-то количество времени, необходимого для создания подписей и различного вида конструкций. На всё это требуется уйма времени, а третьим аспектом является время верификации, которое заботит нас гораздо больше, потому что, например, если я являюсь устройством, которое входит в сеть, и мне нужно по ней получить доступ к блокчейну, а затем верифицировать его, чтобы убедиться в том, что все транзакции в нём действительны, и каждая из них потребует какого-либо времени на верификацию. Эти три аспекта интересны, поскольку между ними наблюдается некоторое взаимодействие, и существуют различные прецеденты, которые объясняют, почему нам следует рассматривать их влияние друг на друга, так как пространство, очевидно, пропускная способность и хранение важны. Пожалуй, нам придётся таскать за собой блокчейн вечно, если только мы не найдём какое-то новое хитрое решение, чтобы исправить это. Итак, разрастание блокчейна с увеличением размера транзакций представляет собой проблему, которую мы хотим свести к минимуму, что в равной степени касается и пропускной способности сети. Транзакции очень велики, что влияет на пропускную способность.
Что касается времени генерирования. Как правило, этот вопрос волнует нас немного меньше. У некоторых не особо производительных устройств с ограниченными вычислительными возможностями могут возникнуть проблемы с этим, и, конечно же, в крайнем случае мы могли бы настроить наши сетевые параметры так, чтобы всё… мы могли бы увеличить размер кольца прямо сейчас, задав ему практически любое значение, но это сильно бы повлияло на время генерирования, например. Если бы время создания транзакций составляло минуту, это бы затруднило использование, поэтому мы стараемся свести его по возможности к минимуму, но генерирование транзакций — это лишь одноразовое событие, если я хочу отправить средства, и у меня это занимает всего пару секунд. Возможно, это вообще не проблема для моего устройства. Но время верификации связано с тем, что вы будете делать снова и снова, если я синхронизирую узел, мне приходится синхронизировать и верифицировать множество транзакций, для верификации каждой из них мне требуется время, которое должно быть по возможности минимальным, что-то порядка секунды уже будет для нас неприемлемым, мы говорим о времени порядка миллисекунды.
Существуют различные уровни, на которых мы можем это оптимизировать, и я говорю о различных уровнях, потому что некоторые из них очень низки, а некоторые немного выше. Одним из них являются низкоуровневые криптографические операции, и мы немного меняем их время от времени. В основе лежит большой объём данных библиотек, чтобы можно было реализовать различные виды аппаратного ускорения, что по большей части не касается темы этого выступления. Но мы заберёмся немного повыше и поговорим о других конструкциях, имеющих отношение к таким вещам, как доказательства диапазона, а также о том, что мы строим на основе этих низкоуровневых криптографических операций. А также я расскажу о параметрах протокола, которые мы просто можем изменять по желанию, но которые влияют на удобство использования. Опять же, размер кольца является самым распространённым примером, мы можем изменить его, когда захотим, в соответствии с протоколом, но существуют причины, по которым мы изменяем или не изменяем его до определённого значения.
Теперь, что касается конкретно этого выступления. В первую очередь, я буду говорить о конструкциях, но и всё остальное также задействовано, и один из примеров — наш классический график роста блокчейна. Вы видите, как он рос со временем. Я уверенно могу сказать, где здесь были введены кольцевые конфиденциальные транзакции, когда мы начали скрывать суммы и обязательства. Я дам вам подсказку, это то место, где он поднимается всё выше и выше, и выше, и я уверен, вы, скорее всего, увидите, когда были реализованы Bulletproofs, что очень сильно сказалось на росте блокчейна, а также времени верификации, когда уровень сглаживается, не сильно сглаживается, но всё же, уже гораздо лучше. Таким образом, мы будем говорить об этом.
Когда мы конкретно говорим об эффективности транзакций, мы касаемся идеи кольцевых подписей. Мы много говорили о кольцевых подписях, об идее их развития со временем. Протокол конфиденциальных транзакций, который используется нами для сокрытия сумм и доказательства баланса, фактически был реализован в кольцевых подписях, поэтому мы имеем дело со своего рода многоуровневой кольцевой подписью. Звучит, как многоуровневый маркетинг… Итак, многоуровневая кольцевая подпись, связанная с доказательством владения ключом. Безусловно, одного из множества ключей, того, который вы тратите. Также, по сути, это помогает продемонстрировать баланс транзакции при помощи некоторых крутых вещей, включая алгебраические свойства обязательств, о которых не обязательно говорить. Также это помогает гарантировать, что генерируемый образ ключа и образы ключей, которые сохраняются, создаются на основе подписей. Можно считать, что они используются для проверки на предмет отсутствия двойной траты, если кто-то решит создать образ ключа нечестным способом, и вы столкнётесь с попыткой двойной траты. Это могло бы получиться, но к счастью, так как нам известно, что схема подписи является доказуемо правильной, нам удаётся избежать этой проблемы.
Таким образом, мы рассмотрим, как кольцевые подписи развивались со временем, и что нам делать с этим. Вторая вещь, которая будет рассмотрена нами, связана с данными выходов. Кольцевые подписи связаны как с входами, так и выходами. Но их масштаб, в первую очередь, основан на количестве входов, а это, конечно же, определяет, какой будет наша кольцевая подпись, и конечно, у нас будет иная кольцевая подпись, если мы потратим множество входов, у каждого из которых будет собственное кольцо с выходом, который действительно тратится и ложными выходами. Но с точки зрения данных выходов, когда я генерирую выходы, предназначенные для вас, возможно, для меня или, возможно, для какого-то другого лица, с выходами должно происходить нечто иное, но есть две вещи, которые мы должны быть в состоянии успешно передать — сумма и маска.
С суммой всё понятно — каждый выход имеет связанную с ним сумму в Monero, которую я собираюсь потратить с этим сгенерированным выходом, но следует также помнить и о том, что мы скрываем суммы и мы делаем это при помощи так называемого обязательства Педерсена. При этом берётся сумма и некоторые секретные данные, которые в идеале никто не знает и которые мы называем маской, обозначим их как R, и в обязательстве всё это смешивается алгебраически таким образом, что реально невозможно взять и всё просто разобрать обратно, и мы делаем с этим пару вещей в одном случае. Переносимся в левую сторону диаграммы, мне необходимо безопасно передать эти определённые элементы, сумму V и маску R, получателю. Получателю необходимо знать сумму, чтобы убедиться в том, что всё правильно, а также получателю необходимо знать маску, чтобы получатель мог использовать эти средства впоследствии. В противном случае над средствами теряется контроль. Поэтому нам необходимо сообщить это, и мы поговорим о том, как сделать это более эффективно. Поэтому я изобразил это серым на своей небольшое цветной схеме.
Затем мы берём эти небольшие части данных и помещаем их в так называемое обязательство Педерсена, мы даём обязательство в правой части и в результате получаем некий алгебраический объект, который можем использовать и который нам понадобится, который мы позднее в конечном счёте включим в кольцевую подпись, чтобы доказать баланс транзакции, не раскрывая суммы, но у нас также будет связанная с ним часть, называемая доказательством диапазона, а доказательство диапазона, по сути, является способом доказательства того, что сумма находится в каком-то разумном диапазоне, без раскрытия конфиденциальной информации, и мы делаем это для того, чтобы эффективно предотвратить что-то вроде отрицательных значений или выхода за допустимые пределы. Если бы мы этого не сделали, открылась бы возможность сознательного или не сознательного построения транзакций, баланс которой был бы нормальным, но всё закончилось бы отправкой абсурдных сумм денег, и причиной этому послужило используемое нами математическое решение, предполагающее использование конечных полей, в чём мы были не так уж и заинтересованы, но достаточно будет сказать, что доказательства диапазона очень важны, так как они демонстрируют, что со временем мы достаточно хорошо оптимизировали их, о чём свидетельствует, как некоторые могли догадаться, реализация протокола Bulletproofs.
Теперь давайте поговорим о кольцевых подписях, и что мы сделали с ними. В настоящее время нами используется схема под названием MLSAG. Я не буду расшифровывать, что это означает, в нашем случае это не важно, но, по сути, они используются для доказательства владения выходами, которые тратятся нами, без раскрытия конкретного выхода, который тратится на самом деле. Идея состоит в построении группы выходов, один из которых является тем, который действительно тратится, а другие при этом являются ложными, и берутся из блокчейна. Но, как я уже сказал, этот тип кольцевой подписи демонстрирует нечто большее. В частности, он показывает, что вами контролируется один выход из набора, но не раскрывается какой именно. При отсутствии внешней информации нам также необходимо доказать, что образ ключа, используемый для обнаружения возможной двойной траты, был сгенерирован честно и правильно. Это исключает возможность создания образа ключа, который не тратился ранее, но который по факту используется для двойной траты. И третье, что обеспечивают такие подписи — сокрытие баланса суммы транзакций путём использования математического решения в рамках обязательств Педерсена, о которых мы говорили ранее.
В данном случае, и об этом ещё будут говорить во время последующей сессии, посвящённой протоколам, в данном случае оборотная сторона состоит в том, что могут найтись способы, позволяющие обойти это, и в том, что они масштабируются линейно с размером кольца как по занимаемому месту, так и по времени подписания и времени верификации. А это означает, что если мы решим просто удвоить размер кольца, то мы, по сути, увеличим не только размер кольцевой подписи, но и время, необходимое для её создания, а также время, необходимо для её верификации, так что, с точки зрения масштабирования, всё не так уж и хорошо. Могли бы мы использовать до тысячи членов кольца прямо сейчас? Ну, могли бы, но масштабирование сделает этот шаг совершенно бесполезным.
Итак, какие новые горячие темы у нас есть на этот момент? Это пока не было нами реализовано, но уже существует новая схема под названием CLSAG, где C означает «компактные» или «сжатые», или что-то в этом роде — мы не сильны в придумывании названий. Изначально схема была предложена анонимным контрибьютором. Случайно. На GitHub есть соответствующая ветка, которая обновлялась впоследствии другими контрибьюторами Monero, включая меня и Брендона. Схема была формализована, была доказана её правильность, и в конченом счёте в сотрудничестве с Moneromoo был разработан код. Идея, лежащая в основе CLSAG в основном состоит в замене существующей схемы кольцевой MLSAG-подписи, так как математически она делает всё то же самое, всё то, что было мной указано и касалось баланса, владения и образа ключа, но делает всё это в разы эффективнее, а также вместо использования различных ключей подписания выходов и ключей подписания обязательств показывает всё это вместе.
Вместо того чтобы включать всё это в подпись по отдельности, что требует больше места и времени, схема использует технику линейного комбинирования, чтобы безопасно «утрамбовать» всё это. Это технический термин. Мы сжимаем всё это. Но данную операцию необходимо производить с осторожностью, в противном случае, вы потом намучаетесь со всем этим. Но если вы сжимаете всё с осторожностью, эти ключи выходов с ключами обязательства, у вас получится произвести замену того, что использовалось нами до этого, но новая схема будет более эффективной.
Сейчас всё по-прежнему масштабируется линейно, и если я решу увеличить размер кольца, то я также увеличу и размер CLSAG-подписи. Но радует то, что если сравнить их с соответствующей существующей схемой MLSAG, новые подписи будут меньше и потребуют меньше времени на создание и верификацию, то есть масштабирование останется тем же, но в целом они будут лучше, в частности, с точки зрения безопасности, которая формально доказана, чем старые.
Насколько они будут хороши? У меня есть графики, где красный означает «плохо», а зелёный означает «хорошо». Так что если вы не любите математику или числа, для вас красный — это плохо, а зелёный — это хорошо. Что касается размера, в текущей версии размер кольца равен одиннадцати. Таким образом, десять ложных выходов и один действительный выход траты, входящие в MLSAG, занимают 768 байт. Мы переключаемся, и у нас снова всё получается, когда мы хотим этого. Мы хотим, чтобы всё это прошло надлежащий аудит при этом размере кольца. CLSAG при эквивалентном размере подписи занимает 448 байт.
Это фантастика — в сущности, чем больше становится размер кольца, тем ближе мы становимся к сокращению на половину… Кому-то там это нравится, судя по всему. Итак, такой размер подписи — это просто фантастика! А что у нас по времени? Тут тоже всё хорошо. Не настолько хорошо, как с размером. Размер просто фантастический. Когда в Monero мы можем что-то сократить вдвое, то это просто восхитительно. Но и с точки времени все тоже довольно неплохо. Слева я обозначил время подписания, которое является частью времени создания транзакции, и, как уже было мною сказано, для нас это всегда мене важно чем то, что указано справа, важнее верификации. Опять же, это показатели, полученные с использованием типовой машины — что-то вроде Opteron с 2,1 гигагерца или что-то подобное. Так что ваши показатели могут быть и другими.
Но в этом конкретном случае время подписания с использованием существующей MLSAG-подписи с размером равным 11 составило около 13 миллисекунд, что не так плохо. Получается, что время подписания с использованием CLSAG составит около 11,5 миллисекунд. Так что всё неплохо, и время верификации составляет примерно 13 миллисекунд, в случае с MLSAG, а при использовании CLSAG снижается примерно до 10,3. А это, если мне не изменяет память, примерно на 20% быстрее, что просто фантастика. Пока такое увеличение касается, к сожалению, только CLSAG, но не времени синхронизации. Но, опять же, это означает, что любые CLSAG-подписи, которые будут генерироваться нами, если забегать вперёд, будут верифицироваться быстрее, чем верифицировались бы, не реализуй мы этот код. Мы могли бы несколько ускорить MLSAG, но показатели не были бы столь же хороши.
Вот, что можно сказать о кольцевых подписях — у нас есть возможность для их значительного улучшения, и схема CLSAG, по сути, готова к реализации. Таким образом, нам бы хотелось, чтобы схема прошла аудит, а также была подвергнута независимому анализу, и тогда мы сможем вообще без каких-либо сложностей реализовать её в Monero. Но я предлагаю также поговорить и об обязательствах. Нас всех пугают обязательства, но не стоит их бояться. Обязательства — это благо. Как я уже сказал, все суммы представлены алгебраической структурой под названием обязательство Педерсена. У неё глобальная фиксированная основа, если вам интересно. Но, по сути, я алгебраически складываю всё это вместе на эллиптической кривой, сумму и маску, и, как я уже сказал, получателю необходимо знать сумму и маску, мы их обозначили как V&R, чтобы восстановить это обязательство и позже использовать в кольцевой подписи, чтобы потратить выход. Но мне не хотелось бы, чтобы кто-то ещё знал эти значения.
Ранее оба значения, по сути, шифровались, и я беру это в кавычки, это была очень прямолинейная схема обфускации, которая использовала что-то вроде модульного наращивания, они шифровались с использованием определённого общего секрета транзакции, который был известен и отправителю, и получателю, и если вам интересно, то это была хеш-функция, которая строилась таким вот образом, а если вам не интересно — тоже хорошо. Итак, чтобы скрыть значение, мы брали это значение и применяли к нему итерированные хеши. Таким образом, оно было известно только отправителю и получателю. Никто другой не смог бы восстановить его, и у нас получалось зашифрованное значение, зашифрованная сумма, и мы делали похожее с маской R, используя немного иной итерированный хеш.
Идея состоит в том, что если вы не являетесь ни отправителем, ни получателем, вы не сможете сгенерировать такое смещение и не сможете восстановить сумму. Если же вы являетесь получателем, то вы сможете провести простую арифметическую операцию и как бы отменить это, и узнать сумму и маску, а затем сможете поступать со своими средствами, как вам захочется. И это неплохо. Но тут нам на ум пришло новое горячее умное решение. Мы поняли, что эта конструкция несколько затратная, в частности, потому что они генерируются произвольным образом, вспомните, я говорил, что вся маска Педерсена является некоторым случайным значением. Предполагается, что есть некое случайно сгенерированное значение, известное только отправителю и получателю. Но если оно генерируется случайным образом, и маска, и эта скрытая версия маски, они являются случайными и известны только отправителю и получателю.
Таким образом, в данном случае зачем нам вообще включать эту специально созданную версию зашифрованной маски с транзакцию? Вместо этого, если мы более не станем отправлять её, вместо этого отправитель и получатель могут совместно вычислять эту выглядящую случайной маску Педерсена. Просто на основе хеш-функции того, что им известно, и мы добавляем немного вот этой «соли», чтобы всё некоторым образом смешать и чтобы никто не смог случайно использовать это впоследствии. Оказывается, если сделать это и не включать те данные, которые мы включали ранее, то экономится довольно небольшой объём, но и не настолько, чтобы его игнорировать — 32 байта на выход. И следует, конечно же, помнить о том, что каждая транзакция содержит, как минимум, два выхода, а выплаты пулов могут включать до шестнадцати выходов, так что масштабируется всё довольно неплохо — мы получаем небольшую экономию.
Всё же по факту и это затратно. И тут снова приходит горячее умное решение. Оказывается, сума не может превышать восьми байтов или 64 бит. Помните о том, что мы ограничиваем сумму этими доказательствами диапазона, о чём мы поговорим позже, но, по сути, мы по-прежнему представляем эту сумму в виде большого скалярного значения в поле, с которым работаем. Выходит 32 байта, как и в случае со всеми нашими алгебраическими величинами, представленными 32 байтами. Таким образом, в данном случае решение состояло в том, чтобы вместо обфускации и отправки 32 байтов, которые реально представляют 8-байтовую сумму, ограничить представление суммы известным фиксированным ограниченным 8-байтовым значением, а затем скрыть его, используя операцию исключающего ИЛИ, чтобы сэкономить по 24 байта на каждом выходе. Как мы сделали это математически - получатель может вернуть всё обратно, используя ту же операцию исключающего ИЛИ и восстановить всё полное 32-байтовое скалярное значение, с которым позже можно будет совершать математические операции.
Таким образом, если вы любите математику, то это было сделано так, если же вы не любите математику, то вот график, помните, красным показано прошлое решение, которое хуже, а зелёным — хорошее решение, которое новое. Мы видим, что ранее эти два значения занимали 64 байта, что не так уж и много для глобальной схемы. Когда мы говорим о транзакциях, мы считаем в килобайтах, но и это значение нельзя не учитывать. Мы смогли снизить его аж до восьми, и это здорово. Я даже не вписал восьмёрку внизу. Это настолько мало, что я считаю, что это очень хорошее, хоть и маленькое улучшение. Как бы то ни было, это улучшение с точки зрения размера всей транзакции. Это ничего не дало с точки зрения эффективности по времени, но с точки зрения места — это значит много. Последняя вещь, о которой я хотел бы рассказать, уже реализована нами. И, кстати, мы о ней уже говорили. Она также уже была реализована, CLSAG-подписи пока не были, а это было. И следующая вещь, о которой мы будем говорить, доказательства диапазона, также была реализована. По невероятной причине доказательства диапазона наделали много шума, а всё потому, что они были очень и очень большими. Итак, как я уже сказал, суммы представлены в виде обязательств. Это основная тема моего выступления. А баланс доказывается путём совершения некоторых алгебраических операций с этими доказательствами. Вы можете складывать и вычитать их самым непосредственным образом, и суммы должны быть, как я говорил, ограничены во избежание выхода за пределы, в результате которого мы можем получить транзакцию, которая будет сбалансирована так, что произойдёт абсолютная глупость, и вы выплатите самому себе кучу денег. Таким образом, нам необходимо показать, что сумма, на которую даётся обязательство, с её случайной маской Педерсена, о которой мы тоже уже говорили, нам необходимо показать, что сумма находится в каком-то фиксированном диапазоне. И как я уже говорил, этот диапазон составляет 64 бита, поэтому мне необходимо доказать, что сумма, выраженная целым числом, будет находиться в пределах диапазона от 0 и 2 до 64.
Итак, общая стратегия как в случае с Bulletproofs, так и с предыдущей версией, заключается в том, чтобы продемонстрировать, что я могу взять это значение V, разложить его на 64 бита, каждый из которых будет либо 0, либо 1, это будут кристально честные биты, которые потом сложатся в правильное значение, но мне не хочется раскрывать, каково значение этих битов. Дело в том, что всё должно произойти без раскрытия конфиденциальной информации, но при этом мне необходимо продемонстрировать, что это заявление истинно и что я разложил значение на честные биты соответствующей длины. Как пример, если моё значение было равно 13 с основанием 10, то есть один, один, ноль, один, в основании два, то я могу разбить его на биты. Так работает двоичное разложение, и я могу использовать это для восстановления значения впоследствии.
Ранее используемый способ предполагал побитовое составление кольцевой подписи, и если вы помните график, на котором я показал разрастание блокчейна, на нём был гигантский скачок, когда все… Внезапный спад графика стал колоссальным. Причина точно заключалась в том, что предшествующий метод был побитовым. Мы называем эти доказательства доказательствами диапазона Борромео. Использовалась немного отличная версия кольцевой подписи, у нас было множество способов использования кольцевых подписей, и одна из них использовалась нами для этого. И в результате для каждого из этих битов создавалось некоторого рода отдельное обязательство, поэтому получалось 64 дополнительных обязательства, каждое из которых было связано с одним из этих битов, и это обязательства имели маски, и когда они суммировались обратно, производились математические операции, и по этим обязательствам, связанным с каждым из битов, строилась кольцевая подпись, чтобы продемонстрировать, какое значение они имеют, нулевое или единичное. А затем, чтобы провести верификацию, было необходимо взять эту большую взвешенную сумму обязательств, чтобы продемонстрировать, что она соответствует правильной сумме, а также верифицировать кольцевую подпись. Таким образом, можно было убедиться в том, какое значение имеет каждый из этих битов, нулевое или единичное.
Что было плохо в этой схеме, так это линейное масштабирование по занимаемому месту и времени в зависимости от количества битов. Таким образом, Bulletproofs стали новой горячей темой. Они сократили это доказательство диапазона до подтверждения внутреннего векторного произведения, и доказательство происходило без раскрытия конфиденциальной информации. Таким образом, новая схема позволили «утрамбовать» их. И что было действительно хорошо в новой схеме, так это то, что она позволяла достигнуть того же самого с теми же обязательствами, но масштабировалась логарифмически. Это гораздо, гораздо медленнее, чем если бы это делалось линейно, и, в частности, доказывающая сторона может включить доказательства диапазона с обязательством по множеству выходов в то же самое доказательство, что делает всё ещё меньше, и выходит, что генерирование и верификация по-прежнему линейны с точки зрения их длины в битах. У нас есть некоторые хитрости, которые позволили бы нам ускорить процесс, и я также могу верифицировать ряд доказательств большой группой практически без каких-либо дополнительных затрат, что здорово, так как когда я верифицирую их, происходит синхронизация с новым узлом. Нам необходимо делать всё это.
Итак, что происходит? При стандартном времени верификации двух выходов по крайней мере в этом случае время доказательства при переходе со схемы старого стиля на схему нового стиля отличается примерно на 50 процентов или около того. Но время верификации, которое нас интересует, в моём случае сокращается с 95 миллисекунд до 21. И это просто фантастика, так как к тому же распространяется и на 16 выходов, которые являются обычным делом для выплат пулов. Снова при увеличении времени доказательства мы имеем значительное сокращение времени верификации. Это показано зелёным цветом. А в случае с групповой верификации дела обстоят ещё лучше. Если бы мы захотели верифицировать группу из 128 различных доказательств, возможно, из разных транзакций с двумя выходами, при использовании старой схемы это заняло бы 12 секунд. А тут мы имеем общее время 420 миллисекунд, что означает сокращение времени верификации на 97%, что великолепно.
Это просто фантастика. А в случае с размером всё ещё лучше: красные доказательства Борромео с увеличением количества выходов также увеличиваются линейно. Это тот случай, когда в случае с Bulletproofs мы не увидим такого увеличения. Масштабирование фантастическое. Оно практически отсутствует. И что это означает? Сложите всё это вместе, и вы поймёте, что из себя представляли типовые транзакции тогда и что они представляют из себя сейчас.
Итак, размер транзакции слева, включающей в себя в среднем два входа и два выхода, составлял около 13 килобайт при всех оптимизациях, которые были проведены. Мы снизили размер до 1,9. Экономия места в целом составила 85% от того, что было, а время верификации сократилось со 121 миллисекунды на транзакцию до 23, и это сократило время верификации ещё на 81%. Всё это выглядит фантастически, люблю я графики, где всё так снижается. Это фантастика. Но следует помнить о том, что это не полные решения с точки зрения масштабирования. Это довольно инкрементальный подход, Bulletproofs, но это всё равно хорошо. Мы имеем инкрементальное улучшение по времени верификации. Такое улучшение хорошо, но оно всё-таки является инкрементальным. Они замедлят рост блокчейна, который всё равно будет продолжаться с количеством проводимых транзакций и выходов, а нам бы хотелось замедлить, ой, извините, ускорить время синхронизации с новыми узлами, максимально сократив время верификации. У нас есть и другие варианты. Некоторые из них подобны этим сублинейным протоколам транзакций с фиксированным количеством ложных выходов, подобным протоколу Omniring, о котором говорилось вчера. Lelantus ещё будет обсуждаться сегодня. Мы можем попытаться перейти к использованию чего-то, что будет обеспечивать полную анонимность транзакций, по сути, вы можете сделать это при помощи Bulletproofs, но у вас останутся проблемы с масштабированием при верификации, можно использовать старые конструкции SNARKs, которые, как нам известно, токсичны, поскольку подразумевают некоторый элемент доверия, но при этом вы получаете хороший уровень масштабирования по времени и месту, если сравнивать с тем, что мы имеем сейчас.
Существуют новые подходы, которые могут оказаться не токсичными. Они обеспечат лучшее масштабирование, чем сейчас, но не такое же или не лучше, чем Bulletproofs. Например, но это не совсем то, где мы хотели бы их применить, примером может служить проведение транзакций вне блокчейна, где будут использоваться такие вещи, как атомные свопы и платёжные каналы, но у нас пока нет для этого нужной системы каналов. Вот что было с транзакциями в прошлом, вот как обстоят с ними дела сегодня. Если вам это будет интересно, у меня есть материалы на GitHub, результаты моих исследований также, в конечном счёте, выкладываются на GitLab. Спасибо, что уделили мне время. Я буду рад ответить на ваши вопросы. Высокие графики — это хорошо, низкие — плохо. Это наш девиз.
Вопрос из зала: Короткий вопрос по атомным свопам. Считаете, это осуществимо? И если да, то когда?
Саранг: Возможно ли и когда, правильно? Атомные свопы — довольно хитрая штука, и необходима определённая система, например, неинтерактивные транзакции возмещения, и необходимо убедиться в том, что математические решения работают, и что они подходят для различных кривых, которые могут использоваться. Monero использует определённый вид эллиптической кривой, который не является обычным для Bitcoin, например. Кроме того, существуют определённые структуры, которые использует Bitcoin. Там бы я смог доказать знание чего-то, используя прообразы хеш-функций, которые не поддерживаются нашим протоколом, но у нас есть некоторые соображения по этому поводу. Есть одна опция, о которой ещё будет говориться сегодня. Так что следите за новостями. То есть у нас уже есть идеи, но они ещё не настолько продуманы, как вы поймёте, поэтому у меня нет хорошего ответа на ваш вопрос. Всё получается не так просто, поскольку протокол Monero не так выразителен, как у Bitcoin, например, многие ходы отличаются. Это не самый удовлетворительный ответ, но это всё, что я могу сказать.
ArcticMine: У меня короткий вопрос. Если бы я собрался поддерживать постоянное время верификации, начиная с текущего состояния, с этого момента, какова твоя оценка, насколько бы удалось повысить смешивание?
Саранг: Оу, это очень интересно — мы получили цифры только по верификации CLSAG-подписи, а тут оказывается, ты бы хотел добавить одного или двоих в группу анонимных подписантов, и чтобы время верификации оставалось таким же, как в случае с 11 участниками и MLSAG. Не представляю. По сути, если у тебя размер кольца будет равен 13, как ты сказал, чтобы мы могли сделать для того, чтобы сохранить то же время верификации, которое имеем сейчас. Немного. Опять же, экономия времени не так важна, если сравнивать с сэкономленным местом.
Вопрос из зала: Я выходил буквально на секунду, поэтому прошу прощения, если упустил этот момент, но что касается CLSAG, как я понял, схема практически готова к запуску. Вы собираетесь переходить на эту схему? Неважно, как будут выглядеть ограничения по размеру колец анонимности, по мере того как мы будем узнавать о них. Как вы считаете, перейдём ли мы на CLSAG, а затем, позже, переключимся на что-то другое, если это что-то будет более многообещающим?
Саранг: Да, я абсолютно уверен в том, что нам следует сделать это. Опять же, это всё зависит от аудита как математической части, так и кода. Всё готово. Нам только осталось убедиться в том, что всё правильно. Да, я считаю, что нет никаких препятствий для перехода на CLSAG в рамках большой схемы. Тут понадобится гораздо меньше усилий, чем для пересмотра всего протокола. Поэтому это то, что мы можем реально сейчас сделать для вас, для наших пользователей, а потом посмотрим, что принесёт нам будущее, потому что тут есть некоторая неопределённость. Понимаете, у нас сейчас есть что-то, и возможно, ещё что-то появится в будущем.
Вопрос из зала: Привет, Саранг! У меня такой двойной вопрос. Транзакции возмещения. Насколько я помню, это то, на что Nak потратил какое-то время.
Саранг: Да.
Вопрос из зала: Мне просто интересно, какую роль они могут сыграть во всём этом?
Саранг: Ммм… да. Тут важно различать интерактивные и не интерактивные транзакции возмещения. Идея, лежащая в основе интерактивных транзакций возмещения, заключается в том, что, по сути, я могу каким-то безопасным образом закодировать адрес возмещения в транзакции. А у Nak была идея, там была пара идей, как реализовать их, но с точки зрения системы, которая понадобится для реализации других вещей, таких как платёжные каналы и атомные свопы. В случае с неинтерактивным возмещением не требуется, чтобы отправитель точно и честно включал эту информацию. И это гораздо сложнее сделать на уровне протокола, и позже ещё будет выступление, которое будет касаться именно того, как реализовать всё это. Я не знаю, ответил ли на твои вопросы.
Вопрос из зала: Ответил. Мой вопрос был двойным, потому что мне хотелось услышать о твоём начальном… твоём изначальном взгляде на недавно появившиеся решения, такие как Omniring, и недавно также появилась пара работ, посвящённых тому, как можно было бы улучшить наши кольцевые подписи. Я хотел спросить, какая работа тебе понравилась?
Саранг: Да, да. Действительно, было опубликовано несколько работ: по Omniring, о которой вы уже слышали, по Lelantus, о которой вы ещё услышите, и была ещё одна под названием rct3 ring CT 3.0, о чём также упоминалось в работе по Omniring. Все работы очень интересны, и во всех описаны немного отличные друг от друга подходы. Проблема в том, что я не вижу, который из них мог бы стать абсолютным победителем, а в случае с Lelantus существует проблема самостоятельной траты, которая требует решения. В случае с Omniring хорошо решена проблема масштабирования. Но вопрос состоит в том, сможем ли выгодно воспользоваться такими вещами, как пакетирование, которые ещё не совсем доработаны, чтобы добиться дополнительного небольшого сокращения абсолютного времени, а в случае с ring ct3 у меня есть вопросы, связанные с пакетированием, на которые у меня пока нет ответов. Так что мне нравятся все эти работы, и мне не терпится дождаться момента, когда из них кто-то станет однозначным победителем, но, как мне кажется, пока они ещё не готовы к этому. Поэтому мы делаем, что можем в данный момент, а также усиленно работаем над тем, чтобы получить что-то лучшее в будущем.
Шурэ: У нас ещё один вопрос.
Саранг: Либо я популярен, либо ужасно выступил.
Вопрос из зала: Ты прекрасно выступил. Графики были великолепными, посмотреть на всё это…
Саранг: Люблю я графики…
Вопрос из зала: Да, посмотреть, как ты всё здорово сделал. Мне интересно…
Саранг: Нет-нет, МЫ сделали это, не я один, это работа множества людей.
Вопрос из зала: Действительно. Заглядывая в далёкое будущее, как ты представляешь себе…
Саранг: Я не заглядывал в далёкое будущее, ну да ладно…
Вопрос из зала: Зато предельно честно. Следующий шаг. Сможем ли мы это повторить? Сможем ли сделать всё лучше, чем когда-либо? И что, по-твоему, могло бы способствовать этому?
Саранг: Я думаю, это такой же вопрос, как вопрос с конечностью вселенной. Например, существуют асимптотические пределы верификации, в которые вы рано или поздно упираетесь. Но если ты спрашиваешь о возможном улучшении современного уровня… Вероятно, ты знаешь, до появления Bulletproofs все думали, что доказательства диапазона всегда будут ужасными, и вдруг оказалось, что они могут быть просто фантастическими. И в случае с MLSAG мы представления не имели, как что-то можно улучшить, а потом случайно возникла идея, и мы поняли, как всё можно сжать. Так что я «никогда не говорю никогда». Но всё же существуют фундаментальные асимптотические пределы вселенной, поэтому лучшее, что нам остаётся, это уменьшить некоторые константы, связанные с ними, сохранить масштабирование, и, как я уже говорил, у MLSAG и у CLSAG одинаковые показатели по масштабированию, но одна из схем однозначно лучше другой в нашем случае. Так что, я надеюсь.
Шурэ: Хорошо, предлагаю всем протянуть Сарангу руку помощи!
Перевод: Mr. Pickles
Редактирование: Agent LvM
Коррекция: Kukima