Перевод Применение доказательств Bulletproofs в транзакциях Monero

Тема в разделе "Статьи", создана пользователем Mr. Pickles, 27 июн 2018.

  1. Mr. Pickles

    Команда форума Модератор Редактор

    Регистрация:
    11 сен 2017
    Сообщения:
    206
    Симпатии:
    60
    MONERO
    Research Lab


    Sarang Noether
    Monero Research Lab
    5 марта 2018 г.
    sarang.noether@protonmail.com


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

    1. Вступление

    Реализация передачи средств Monero путём совершения конфиденциальных транзакций происходит при помощи гомоморфных обязательств. В каждом входе и в каждом выходе сумма, включая комиссию, представлена обязательством в форме upload_2018-6-27_17-43-29.png , где upload_2018-6-27_17-43-51.png и upload_2018-6-27_17-43-57.png являются генераторами эллиптических кривых, upload_2018-6-27_17-44-16.png является суммой, а upload_2018-6-27_17-44-25.png — маской. Не зная обязательства, третья сторона не сможет определить сумму. Тем не менее третьей стороне не составит труда убедиться в том, что транзакция является сбалансированной (то есть разница между суммами входа и выхода является нулевой). Гомоморфизм обязательств таков, что разница в обязательствах должна быть сама по себе обязательством по сведению к нулю.

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

    В настоящее время при проведении конфиденциальных транзакций Monero используются побитовые доказательства диапазона Борромео (Borromean bitwise range proofs). Для того чтобы сформировать доказательство, в обязательстве upload_2018-6-27_17-46-30.png указывается сумма upload_2018-6-27_17-46-41.png с некоторой длиной в битах upload_2018-6-27_17-46-51.png (в случае с Monero upload_2018-6-27_17-48-18.png ), и доказывающая сторона генерирует отдельное обязательство для каждого бита. После этого, доказывающая сторона генерирует кольцевую подпись Борромео, в которой видно, что для каждого соответствующего каждое обязательство относится либо к upload_2018-6-27_17-47-20.png , либо к upload_2018-6-27_17-47-26.png , а значит сумма, к которой относится обязательство, лежит в пределах заданного диапазона.

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

    2. Bulletproofs

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

    Подробности структуры Bulletproofs, касающиеся как доказывающей, так и проверяющей стороны, описаны в работе, поэтому мы не станем дублировать их в этой записке. Тем не менее несколько определений могут пригодиться, когда речь зайдёт о масштабировании. Стандартное доказательство Bulletproof, которое служит для демонстрации того, что сума находится в пределах диапазона, составляющего upload_2018-6-27_22-5-37.png бит, upload_2018-6-27_22-5-49.png , называется доказательством одиночного выхода (single-output proof) или одиночным доказательством (1-proof). Однако доказывающая сторона может построить одиночное доказательство, демонстрирующее, что upload_2018-6-27_22-6-28.png отдельных сумм (с отдельными произвольными масками) находится в пределах диапазона upload_2018-6-27_22-6-41.png , где upload_2018-6-27_22-6-51.png является степенью двойки. Такое доказательство называется совокупным (aggregate proof) или, что будет более точным, m-доказательством (m-proof). Схема построена таким образом, что доказательство одиночного выхода заведомо является m-доказательством, где upload_2018-6-27_22-7-18.png (что упрощает код). Важно отметить, что структура совокупного доказательства требует, чтобы доказывающей стороне была известна каждая сумма и маска. А это означает, что даже несмотря на практичность нахождения всех выходов транзакции в пределах одного совокупного доказательства с точки зрения экономии места, третья сторона не сможет взять существующие доказательства и построить из них совокупное доказательство как в пределах отдельно взятой транзакции, так и между различными транзакциями.

    Преимущества Bulletproofs с точки зрения масштабирования размера можно рассматривать по двум уровням.

    1. Длина диапазона в битах. Размер доказательства Bulletproof увеличивается логарифмически в зависимости от количества бит в пределах диапазона. В случае c побитовыми доказательствами диапазона размер доказательства растёт линейно с количеством битов.

    2. Количество сумм в совокупном доказательстве. Размер доказательства Bulletproof увеличивается логарифмически в зависимости от количества сумм в отдельно взятом совокупном доказательстве. В случае c побитовыми доказательствами диапазона размер доказательства растёт линейно с количеством битов (так как для каждой суммы было необходимо своё доказательство).​

    Эффективность доказательств рассматривается нами ниже.

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

    3. Варианты оптимизации

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

    3.1 Обозначение групп кривых

    Настоящая работа написана исходя из общей групповой структуры, поэтому действия, относящиеся к группе скалярных величин, записаны мультипликативно (например, upload_2018-6-27_22-9-20.png ). В случае наличия групп эллиптических кривых, вместо этого нами используется дополнительное обозначение (например, upload_2018-6-27_22-9-28.png ) и регистр, что позволяет без труда отличить точки кривой и скалярные величины. Это сделано исключительно из соображений простоты обозначения.

    3.2 Обозначение исходных точек

    Во всей работе обязательства по сумме выражены как upload_2018-6-27_22-9-57.png , где upload_2018-6-27_22-10-2.png и upload_2018-6-27_22-10-9.png являются определёнными (но произвольными) постоянными генераторами групп эллиптических кривых. В нашем варианте реализации мы производим взаимную замену ролей upload_2018-6-27_22-10-21.png и upload_2018-6-27_22-10-26.png , чтобы обеспечить соответствие применения существующих исходных точек, использующихся в обязательствах где-либо в кодовой базе Monero. Следует отметить, что отмеченные коэффициентами точки кривой upload_2018-6-27_22-10-32.png и upload_2018-6-27_22-10-40.png не изменяются подобным образом.

    3.3 Вызовы Фиата-Шамира

    Для того чтобы сделать схему Bulletproofs неинтерактивной, мы следуем основному документу и используем вызовы Фиата-Шамира, вычисленные путём хеширования матрицы доказательства вплоть до того момента, пока не понадобится новый вызов. Для этого вводится кольцевой хеш, который в качестве входа использует предыдущий вызов и любые новые элементы доказательства. Доказывающая сторона и проверяющая сторона вычисляют эти вызовы идентичным образом.

    3.4 Переменная внутреннего произведения

    Переменная внутреннего произведения в Протоколе 1 основного документа Bulletproofs использует рекурсию, чтобы сжать размер входящих векторов до одиночных элементов. Эти входы включают в себя определённые генераторы групп кривых upload_2018-6-27_22-12-55.png и upload_2018-6-27_22-12-59.png , которые вычисляются нами при помощи индексированной хеш-функции. Для проверяющей стороны у нас есть несколько вариантов оптимизации этого протокола.

    Сначала мы видим, что точки кривой в Уравнении (10) фактически являются линейными комбинациями upload_2018-6-27_22-13-8.png и upload_2018-6-27_22-13-11.png , которые используют скалярные вызовы в уравнениях (24)-(25). Затем нами отмечается, что точка upload_2018-6-27_22-13-32.png в уравнении (62) переходит в Протокол 1, о чём говорится в Разделе 4.2 основного документа. Так как точка кривой содержит линейную комбинацию тех же генераторов группы, что и Протокол 1, мы можем выгодно использовать это и вычислить отдельную линейную комбинацию, а не производить вычисление Уравнений (62) и (10) по отдельности.

    На деле мы заменяем Уравнения (62) и (10) следующей проверкой, где

    upload_2018-6-27_22-13-40.png

    upload_2018-6-27_22-13-49.png
    Обозначения в большинстве случаев те же, что были использованы в основной работе. Тем не менее мы используем обозначение upload_2018-6-27_22-14-20.png , чтобы представить круговые вызовы в Строках (21)-(22), а также , чтобы обозначить вызов в Строках (32)-(33). Это сделано во избежание повторного использования символов. Скалярные величины upload_2018-6-27_22-14-28.png и upload_2018-6-27_22-14-34.png вычисляются следующим образом. Коэффициент upload_2018-6-27_22-14-41.png выражается по битам, при этом upload_2018-6-27_22-14-50.png является наименее значимым битом. Тогда,

    upload_2018-6-27_22-15-4.png

    upload_2018-6-27_22-15-12.png
    Данный вариант оптимизации применим только к проверяющей стороне.

    3.5 Групповая верификация

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

    Групповая верификация разбивается на две проверки, выполняемые после итерации по каждому доказательству в группе. Во время итерации проверяющая сторона сохраняет текущие суммы из каждого доказательства, а затем проводит первую проверку для Уравнения (61):

    upload_2018-6-27_22-16-23.png
    Второй этап проверки осуществляется подобным образом:

    upload_2018-6-27_22-16-38.png
    В данном случае каждая сумма с коэффициентом upload_2018-6-27_22-16-56.png переходит на каждое доказательство в группе, а upload_2018-6-27_22-17-1.png является коэффициентом взвешивания, случайно (не детерминированно) выбранным проверяющей стороной. Это гарантирует, что, за исключением ничтожно малой вероятности, проверки будут успешными, если каждое взятое по отдельности доказательство будет действительным. Злоумышленник не сможет выборочно выдать группу, содержащую недействительные доказательства, чтобы обмануть проверяющую сторону. Преимущество данного подхода состоит в том, что суммы могут быть вычислены как большие многоэкспоненциальные действия после того, как будут собраны скалярные величины всех доказательств.

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

    4. Размер доказательства

    Вместе с обязательством по сумме upload_2018-6-27_22-17-29.png одно побитовое доказательстве диапазона Борромео занимает 6,2 Кбайта. Транзакция с upload_2018-6-27_22-17-47.png выходов, следовательно, требует 6,2 upload_2018-6-27_22-17-35.png Кбайта пространства. m-доказательство (в 64-битном диапазоне) требует 2 lg upload_2018-6-27_22-17-59.png + 17 элементов группы и 5 скалярных величин, каждая из которых занимает 32 байта. В Таблице 1 продемонстрирована экономия места, которую обеспечивают доказательства Bulletproofs для нескольких значений upload_2018-6-27_22-18-24.png .

    1.jpg
    Таблица 1. Размер (в байтах) m доказательств Борромео относительно размера m-доказательств
    При использовании данных блокчейна Monero по распределению количества выходов по транзакциям, применение Bulletproofs позволило бы сократить общий размер доказательств диапазона на 94%.


    Были взяты данные блоков с 1 400 000 по 1 500 000


    Источник: Application of Bulletproofs in Monero Transactions


    Перевод:
    Mr. Pickles (@v1docq47)
    Редактирование:
    Agent LvM (@LvMi4)
    Коррекция:
    Kukima (@Kukima)

     
    #1 Mr. Pickles, 27 июн 2018
    Последнее редактирование: 27 июн 2018
    LeD XIII и TheFuzzStone нравится это.
  • О нас

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