Аудит криптовалютного кошелька — это возможность для третьей стороны («аудитора») видеть транзакции этого кошелька и рассчитывать его корректный актуальный баланс без права на трату средств.

В статье рассматриваются различные способы обеспечения такой возможности в криптовалютном протоколе CryptoNote 2.0 [1], где аудит реализован лишь частично: с помощью трекингового ключа можно распознавать входящие транзакции, но для распознавания исходящих нужен полный набор ключей.

Материал рассчитан на читателей, знакомых с темой блокчейна и «классических» криптовалют, а также с основами криптографии на эллиптических кривых.

Содержание

1. Введение
2. Базовые сведения о криптографии на эллиптических кривых
3. Учет средств и расчет баланса в CryptoNote
4. Вариант 1/3. Bytecoin Auditable Coins
? 4.1. tx.version < amethyst, legacy address
? 4.2. tx.version ? amethyst
? 4.3. tx.version ? amethyst, legacy address
? 4.4. tx.version ? amethyst, amethyst address
? 4.5. Сравнение подписей транзакций CryptoNote и Bytecoin Amethyst
5. Вариант 2/3. Исследования аудита в CryptoNote от Anton Sokolov
6. Вариант 3/3. Аудит через ограничение на подмешивание выходов
7. Заключение
Литература

1. Введение

Что такое CryptoNote?

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

В 2014 году в криптовалютной среде появились упоминания [2] о проекте, который назывался Bytecoin. Проект не являлся форком Bitcoin или другого открытого проекта и имел совершенно новую кодовую базу, что было крайне необычно для того времени. Его основная концепция сводилась к реализации privacy-технологии, которую называли CryptoNote. Приватность обеспечивалась двумя механизмами: стелс-адресами и подмешиванием входов с использованием кольцевой подписи (ее еще называли в то время «микшер на блокчейне»). Поскольку в то время Zcash существовал только в теории, технология оказалась весьма конкурентоспособной и вызвала большой резонанс в криптовалютном сообществе.

Вскоре группа энтузиастов, проявившая интерес к одному из первых форков этой технологии, а затем и перехватившая инициативу в этом форке, своими энергичными действиями сумела привлечь наибольшее внимание к технологии как среди сообщества так и среди инвесторов. Этот форк назывался BitMonero [3, 4], однако довольно скоро он был переименован в Monero.

В дальнейшем оба проекта — Bytecoin и Monero — развивались технологически разными путями: если Bytecoin оставался закрытым анонимным проектом, то Monero превратился в крупный community-driven проект с очень большим количеством участников и разработчиков. Тем не менее, они оба являются развитием CryptoNote технологии.

Понятие аудита и его приложения

В отличие от классического «псевдонимного» блокчейна типа Bitcoin, в котором любой желающий, сканируя блокчейн, может тривиально подсчитать балансы любого адреса, в приватном блокчейне, в частности, в CryptoNote, эта задача едва ли осуществима без дополнительных знаний. Во-первых, благодаря технологии стелс-адресов, в блокчейне вообще отсутствуют упоминания каких-либо адресов (это свойство обычно обозначается как anonymity). Во-вторых, в силу того, что благодаря кольцевой подписи вход транзакции не указывает на один конкретный выход родительской транзакции, а указывает, в общем случае, на множество вероятных выходов, отследить движение средств также не представляется возможным (это свойство называется untraceability).

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

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

Об авторе и цели публикации

Автор данного материала является одним из основных разработчиков проекта Zano — проекта, основанного на CryptoNote, который развивался несколько лет теми же руками, которыми был написан оригинальный код технологии.

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

2. Базовые сведения о криптографии на эллиптических кривых

Протокол CryptoNote использует эллиптическую кривую из схемы цифровой подписи с открытым ключом ed25519 [5].

Напомним основные параметры этой кривой и дадим дополнительные определения.

1. Зафиксировано большое простое число $$.
   Все операции происходят в целых числах в конечном поле $$ вычетов по модулю $$.
2. Задана эллиптическая кривая над полем $$, обозначаемая $$:
   $$
   где $$ (отношение вычисляется в $$ и является целым числом).
   Важным является факт ее симметрии относительно $$ и $$.
3. Над множеством точек кривой геометрически определена операция, для любых двух точек дающая третью: $$, условно называемая «сложением», и задан нейтральный элемент, как точка, лежащая в бесконечности (это подробно рассмотрено в [6]). Эта операция не выводит за пределы множества, обладает ассоциативностью, коммутативностью и наличием обратного элемента, благодаря чему все точки кривой вкупе с ней образуют абелеву группу, обозначаемую $$.
   Порядок этой группы (число всех точек): $$, где $$ (кофактор) и $$.
4. Каждая точка кривой задается своими координатами $$. Поскольку координаты связаны уравнением кривой, это представление избыточно, и поэтому при реализации криптографических функций для экономии используется только координата $$, кодируемая как 256-битное число.
   $$-координата, в соответствии с симметричностью кривой (см. уравнение), может быть только одним из двух вариантов, выбор которого кодируется как старший бит числа, представляющего $$-координату.
5. Зафиксирована специальная точка кривой $$. Точка задается $$-координатой, из двух возможных вариантов x выбирается положительный.
6. Сложение (см. п. 3) точки $$ с самой собой $$ раз определяет операцию умножения ($$, опускается в формулах) на целое число, образующую замкнутую мультипликативную группу $$, порядок которой меньше, чем $$:
   $$,
   при этом
   $$.
7. Открытый ключ $$ — это точка эллиптической кривой, принадлежащая группе $$:
   $$
8. Секретный ключ $$, или скаляр, соответствующий открытому ключу $$ — это такое целое число, что:
   $$
   Секретный ключ, также как и открытый (см. выше), кодируется как 256-битное число.
9. Определена основная хеш-функция $$ (в коде и других источниках обозначается как cn_fast_hash). Она вычисляет 32-байтный хеш по произвольному набору данных:$$
10. Хеш-функция $$ ($$ означает scalar) по произвольным данным выдает число, являющееся скаляром, т.е. валидным секретным ключом:
    $$
    $$ может быть реализована тривиально через $$:
    $$
11. Хеш-функция $$ ($$ означает point — точка кривой) по произвольным данным выдает элемент группы $$, то есть, валидный открытый ключ:
    $$
    Реализация этой хеш-функции представляет определенную сложность по той причине, что во-первых, не любой набор 256 бит можно декодировать в точку эллиптической кривой (см. п. 4), а во-вторых, не любая точка кривой принадлежит группе $$ (см. п. 6).
    Одним из тривиальных способов реализации $$ является последовательное хеширование данных $$ до тех пор, пока результат не станет возможным декодировать в точку $$.
    В CryptoNote используется более сложный и эффективный подход, реализованный в виде функции ge_fromfe_frombytes_vartime, который подробно рассмотрен в работе [7].
    Определим функцию, детерминированно преобразующую произвольные 256 бит в элемент группы $$ как:
    $$
    В CryptoNote хеш-функция $$ реализована так:
    $$

3. Учет средств и расчет баланса в CryptoNote

Вспомним, как происходит отправка средств и расчет баланса в оригинальной версии протокола.

Алиса, отправляя деньги Бобу, формирует выходы своей транзакции следующим образом (рис. 3.1).

1. У Боба есть пара закрытых ключей $$. Он вычисляет свой адрес как пару соответствующих открытых ключей $$ и опубликовывает его или отправляет Алисе.
2. Алиса выбирает случайный секретный ключ транзакции $$ и вычисляет открытый ключ $$, который записывает в специальное поле extra транзакции.
3. Для каждого выхода Алиса вычисляет стелс-адрес (one-time destination key):
   $$, где $$ — порядковый номер выхода.
4. Алиса подписывает и отправляет транзакцию.

Сторонний наблюдатель, анализируя стелс-адреса $$, не может сказать, предназначен ли конкретный выход Бобу, и даже не может определить, предназначены ли разные выходы с ключами $$ и $$ одному получателю.

Чтобы принять деньги, Боб анализирует все транзакции в блокчейне следующим образом (рис. 3.2).
5. Используя свой секретный ключ $$, Боб вычисляет для каждого выхода $$ (где $$ — порядковый номер выхода, $$ — открытый spend-ключ Боба).
Если $$, то это означает, что он является получателем данного выхода и может его потратить, вычислив соответствующий секретный ключ.Поэтому Боб увеличивает баланс своего кошелька на номинал данного выхода.

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

6. Боб, используя свои секретные ключи $$, вычисляет закрытый ключ $$ к стелс-адресу $$, то есть такой, что $$.

7. Боб рассчитывает key image: $$ и записывает его, номинал и ссылку на соответствующий выход во вход своей транзакции для Кэрол.
Следует обратить внимание на то, что, во-первых, вычислить key image может только владелец секретного spend-ключа $$ (корректность этого будет удостоверена кольцевой подписью), и во-вторых, третья сторона не сможет связать key image $$ и соответствующий стелс-адрес $$.

8. Боб уменьшает баланс своего кошелька на номинал используемого выхода в п. 6.

9. Боб формирует выходы в транзакции для Кэрол в соответствии с п.п. 2-3. После чего подписывает транзакцию и отправляет.

Если предположить, что Боб утратил всю историю своих операций, но по-прежнему владеет своими секретными ключами $$, то он сможет восстановить историю транзакций и рассчитать свой текущий баланс следующим образом (рис. 3.4).

10. Боб сканирует весь блокчейн и анализирует все транзакции на предмет наличия выходов, адресованных ему (см. п. 5).

11. При нахождении такого выхода $$, Боб увеличивает баланс своего кошелька на величину номинала.
Затем, используя свой секретный spend-ключ $$ вычисляет соответствующий секретный ключ выхода $$ (п. 6) и key image $$ (п. 7). После чего записывает key image, $$ и другие данные платежа в таблицу.

12. Если при дальнейшем сканировании блокчейна Боб обнаружит во входе некоторой транзакции key image, имеющийся в таблице, это будет означать, что данная транзакция была когда-то сформирована Бобом. Поэтому он уменьшит баланс своего кошелька на величину номинала входа.

Действуя таким образом, Боб восстановит актуальный баланс своего кошелька.

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

Таким образом, для расчета баланса кошелька Боба необходимо знать оба секретных ключа $$.

Если Боб передаст аудитору Дену оба своих секретных ключа $$, это будет равносильно передаче самих средств, так как Ден, обладая $$, сможет их потратить. Поэтому полноценный аудит кошельков в рамках оригинального протокола CryptoNote невозможен.

В следующих разделах мы рассмотрим варианты модификации протокола, обладающие такой возможностью.

Отметим, что секретный ключ транзакции $$ Алисе имеет смысл сохранять (что и происходит в некоторых реализациях протокола). Любой, кто знает $$ для некоторой транзакции, может проверить, относится ли выход $$ этой транзакции к заданному адресу $$, просто повторяя вычисления из п.3:

$$

и сравнивая результат с $$.

Этот факт Алиса может, например, использовать, чтобы доказать, что она перевела деньги именно Бобу.

Вычислить целевой адрес $$ по выходу, даже зная $$, нельзя.

4. Вариант 1/3. Bytecoin Auditable Coins

В момент своего появления Bytecoin был первой и единственной реализацией протокола CryptoNote, поэтому ему были свойственны все особенности и ограничения, рассмотренные в предыдущем разделе.

7 февраля 2019 года разработчики выпустили ([20]) версию 3.4.0 Amethyst, содержащую ряд улучшений и изменений CryptoNote, которые мы сейчас рассмотрим. Большая часть информации этого раздела была получена путем анализа исходного кода Bytecoin, так как официальной документации не предоставлено.

В рамках тематики этой статьи, наиболее интересным изменением стала возможность для обычных кошельков создавать специальные копии — auditable wallet (AW), обладающие двумя свойствами:

1. AW не может потратить средства из основного кошелька;
2. баланс AW всегда совпадает с балансом основного кошелька. Невозможно изменить баланс основного кошелька так, чтобы это не отразилось на балансе AW.

Однако, такой функциональностью обладают только адреса кошельков новых версий, так называемые, amethyst-адреса. С существующими адресами и аккаунтами обеспечивается обратная совместимость, они теперь называются legacy-адреса. Реализация новой функциональности стала возможна только в транзакциях новой версии, поскольку разработчики поменяли формат выходов, поэтому в сети Bytecoin в данный момент циркулируют как транзакции старого формата, так и новые. Транзакции нового формата также поддерживают два типа адресов: amethyst и legacy, поэтому в конечном счете мы имеем три варианта криптографических схем:

1. tx.version < amethyst, legacy address;
2. tx.version ? amethyst, legacy address;
3. tx.version ? amethyst, amethyst address.

Рассмотрим их более подробно.

4.1. tx.version < amethyst, legacy address

Это оригинальная схема CryptoNote, но с детерминированной генерацией $$.

Аккаунт кошелька представлен секретным ключом $$ и хешем $$. Секретный view-ключ $$ детерминированно генерируется как функция от $$.

Секретный ключ $$ транзакции теперь выбирается не случайно, а вычисляется при помощи $$:

$$, где $$

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

Баланс кошелька вычисляется аналогично оригинальному CryptoNote (см. раздел 3), то есть, для учета исходящих платежей необходим секретный spend-ключ $$.

В случае, если в локальном хранилище кошелька будут сохранены все адреса, на которые когда-либо осуществлялся перевод средств, то существует возможность рассчитать верный баланс без привлечения секретного spend-ключа $$ следующим образом:

1. Алиса сканирует транзакции в блокчейне и ведет учет входящих платежей при помощи секретного view-ключа $$, как было описано в разделе 3, и увеличивает баланс.
2. Также для каждого выхода каждой транзакции Алиса перебирает все адреса $$ на которые когда-либо осуществлялись переводы и вычисляет:
   $$
   Если $$, то данный выход является исходящим платежом Алисы на адрес $$ и она уменьшает баланс.

Так Алиса рассчитает баланс используя только $$ и $$.

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

4.2. tx.version ? amethyst

Как уже было отмечено выше, начиная с версии 3.4.0 Amethyst в Bytecoin изменился формат транзакций. Если tx.version ? amethyst, то выходы транзакции имеют другой формат.

Теперь каждый выход, помимо номинала amount и открытого ключа P_i, содержит также дополнительный открытый ключ Q_i (обозначаемый в коде как encrypted_secret) и дополнительный байт, содержащий зашифрованный тип адреса, amethyst или legacy (именуемый в коде encrypted_address_type). Эти структуры схематично показаны на рис. 4.2.

Таким образом, размер каждого выхода увеличился на 33 байта.

Для каждого выхода i тип адреса кодируется и декодируется следующим образом:

encrypted_address_type(i) = (H(oi) & 255) xor address_tag

где:

$$ (обозначается в коде как output_seed),

address_tag равен 0 для legacy-адресов и 1 для ametyst-адресов.

4.3. tx.version ? amethyst, legacy address

Аккаунт кошелька также представлен секретным ключом $$ и хешем $$, на основе которого детерминированно генерируется секретный view-ключ $$.

Алиса, отправляя деньги Бобу на его адрес $$ формирует выходы своей транзакции следующим образом:

? 1. Вычисляет $$, затем для каждого выхода $$:
? 2. $$ (в коде обозначается как output_shared_secret)
? 3. $$
? 4. $$ (при этом $$, однако view-ключ $$ получателя неизвестен)
? 5. Пара $$ — открытые ключи выхода $$.

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

? 6. Для каждой транзакции вычисляет $$, затем для каждого выхода $$:
? 7. $$
? 8. $$
? 9. Если $$ совпадает с открытым ключом $$ Боба, то этот выход предназначен ему и он увеличивает баланс своего кошелька на соответствующий номинал.

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

? 10. Используя свои секретные ключи $$ и $$, вычисляет секретную часть $$:
? ? $$
? ? $$, при этом легко видеть, что $$ (см. п. 3).
? 11. Боб рассчитывает key image: $$ и записывает его, номинал и ссылку на соответствующий выход во вход своей транзакции для Кэрол.
? 12. Боб уменьшает баланс своего кошелька на номинал используемого выхода.
? 13. Боб формирует выходы в транзакции для Кэрол в соответствии с п.п. 1-5. После чего подписывает транзакцию и отправляет.

Особенностью данной схемы, в отличии от CryptoNote, является то, что любой, кому Алиса передаст свой секретный хеш $$, сможет вычислить адрес получателя $$ для любой транзакции Алисы:

? 14. $$
? 15. $$
? 16. $$

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

Поскольку в данной схеме вычисление key image также требует знания секретного spend-ключа $$, то проблема аудита, то есть, вычисления точного баланса кошелька без передачи прав на трату средств, остается не решенной.

4.4. tx.version ? amethyst, amethyst address

Константа H

Для работы этой криптографической схемы требуется введение новой константы — точки $$, элемента группы $$, причем порядок точки $$ неизвестен. Иными словами, это некоторый зафиксированный открытый ключ, секретная часть которого гарантировано неизвестна и вероятность ее нахождения пренебрежимо мала:

$$, где $$ — неизвестное число.

Например, можно задать $$ так, как предлагается в [8]:

$$

Разработчики Bytecoin не вычисляют константу, а задают ее численно, без каких-либо указаний на природу ее происхождения:

bytecoin/src/crypto/crypto_helpers.hpp, line 67

constexpr P3 H{ge_p3{{7329926, -15101362, 31411471, 7614783, 27996851, -3197071, -11157635, -6878293, 466949, -7986503},    {5858699, 5096796, 21321203, -7536921, -5553480, -11439507, -5627669, 15045946, 19977121, 5275251},    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0},    {23443568, -5110398, -8776029, -4345135, 6889568, -14710814, 7474843, 3279062, 14550766, -7453428}}};

Однако поиск этой числовой последовательности показал ([9]), что ими используется та же константа, что и в Monero для RingCT, способ вычисления которой и его обоснование рассмотрены в [8].

Поскольку $$ принадлежит группе $$, то можно сказать, что $$ так же порождает группу $$, как и базовая точка $$.

Это означает, что $$

Множественные несвязываемые адреса (unlinkable addresses)

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

Рассматриваемая же схема позволяет на одном и том же наборе секретных ключей генерировать неограниченное количество публичных адресов. При этом:

1. адреса генерируются детерминированно из первоначального набора секретов;
2. эти адреса не могут быть связаны между собой, т.е. сторонний наблюдатель не сможет вычислить, что они принадлежат одному аккаунту;
3. проверка входящих транзакций и учет баланса для $$ множественных адресов будет вычислительно проще, чем проверка $$ аккаунтов в обычной схеме.

Аккаунт кошелька представлен секретным ключом $$ и хешем $$, также, как и в предыдущей схеме. Однако на основе хеша $$ теперь детерминированно генерируется не только секретный view-ключ $$, но и дополнительный секретный audit-ключ $$.

Процесс генерации i-го адреса происходит следующим образом (рис. 4.4.2).
? 1. Вычисляется $$ и $$
? 2. $$
? 3. $$
? 4. пара $$ является $$-ым публичным адресом данного аккаунта.

Заметим, что для расчета достаточно знать следующие величины:
? • $$
? • $$
? • $$
? • $$

Величины $$ и $$ предрассчитываются при создании аккаунта и рассматриваются как безопасные в том смысле, что зная их, нельзя вычислить $$ или $$.

Сгенерированные адреса хранятся локально в контейнере, оптимизированном для поиска по полю $$.

Формирование выходов при отправке средств

Алиса, отправляя деньги Бобу на его адрес $$ формирует выходы своей транзакции следующим образом (рис. 4.4.3).
? 1. Вычисляет $$, затем для каждого выхода $$:
? 2. $$
? 3. $$
? 4. Пара $$ — открытые ключи выхода $$.

Учет входящих платежей

Чтобы принять деньги, Боб анализирует все транзакции следующим образом (рис. 4.4.4.).

1. Для каждого выхода $$, используя секретный view-ключ $$, Боб вычисляет:$$ (output_shared_secret в коде)
2. $$
3. После чего пытается найти $$ в списке своих адресов. Если находит, то это означает, что данный выход переводит деньги Бобу. Он увеличивает баланс для соответствующего адреса.

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

Формирование исходящих платежей

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

1. $$ (output_shared_secret в коде)
2. $$
3. $$
4. Вычисляет key image $$
5. Боб уменьшает баланс, относящийся к его адресу $$ на величину номинала соответствующего выхода.
6. Боб формирует выходы транзакций, подписывает ее и отправляет.

Видно, что для вычисления key image требуется знание не только секретного view-ключа $$, но и $$.

Важной особенностью данной схемы является возможность вычисления key image (а значит, и учета своих исходящих платежей, следовательно — расчет баланса) без использования секретного spend-ключа $$.

Раскрытие адресов получателей для аудита

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

Происходит это следующим образом (рис. 4.4.5).
Предположим, что Алиса передала $$ и $$ Кэрол. Тогда Кэрол:

1. Восстановит секретные ключи $$ и $$, восстановит список адресов Алисы.
2. Будет сканировать блокчейн и для каждого выхода $$ каждой транзакции будет определять, является ли он входящим платежом, пытаясь найти
   $$
   среди адресов Алисы.
3. Если найдет, то Кэрол увеличит баланс соответствующего адреса и, при помощи $$ и $$, вычислит key image (см. выше) и сохранит его локально.
4. Если среди входов транзакций встретится key image Алисы, то это будет означать, что данная транзакция — исходящий платеж Алисы. Кэрол восстановит адреса получателей для всех выходов этой транзакции:
   $$
   $$
   и уменьшит баланс соответствующего адреса Алисы на величину номинала входа.

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

Чтобы сгенерировать список своих адресов:
? • $$
? • $$
? • $$
? • $$

Чтобы распознать только входящие платежи:
? • $$
? • $$
? • $$

Чтобы произвести аудит, т.е. рассчитать баланс по своим адресам, без раскрытия адресов получателей:
? • $$
? • $$
? • $$

Чтобы произвести аудит, т.е. рассчитать баланс по своим адресам, и раскрыть при этом адреса получателей:
? • $$
? • $$

4.5. Сравнение подписей транзакций CryptoNote и Bytecoin Amethyst

Структуры данных и размеры подписей

Как было отмечено выше, реализация возможности проводить аудит кошельков, не раскрывая секретный spend-ключ, потребовала от разработчиков Bytecoin Amethyst увеличения размера данных, передаваемых в каждом выходе транзакции: по сравнению с оригинальным протоколом передается один открытый ключ и 1 байт для идентификации типа адреса. Итого, 33 байта на выход.

В CryptoNote у транзакции подписывается отдельно каждый ее вход. Для каждого открытого ключа $$ некоторого выхода, на который ссылается данный вход, в подпись записывается пара скаляров $$ общим размером 64 байта. (Вход может ссылаться на несколько выходов, лишь один из которых — настоящий, а остальные служат для анонимизации перевода.)

Таким образом, если в транзакции $$ входов, каждый из которых ссылается на $$ выходов, то общий размер подписи в байтах можно выразить как:

$$

Минимальный размер подписи для транзакции составляет 64 байта (один вход, который тратит один выход напрямую).

В Bytecoin Amethyst подписывается вся транзакция целиком, и соответствующая структура данных усложнена (рис. 4.5.1).
Для каждого входа транзакции в подпись записывается точка, два скаляра и еще $$ скаляров. Ко всей подписи также добавляется еще один скаляр. Итого, общий размер подписи в байтах можно выразить как:

$$

Минимальный размер подписи для транзакции составляет 160 байт (один вход, который тратит один выход напрямую).

Видно, что обе функции растут пропорционально произведению $$

Чтобы сравнить различие размеров подписи транзакции более наглядно, рассчитаем их для наиболее характерных величин $$ и $$ и составим таблицу (рис. 4.5.2).
Как легко можно видеть, в ситуации, когда подмешивание выходов отсутствует и происходит прямая трата средств ($$), либо когда подмешивается один выход ($$), размер подписи Bytecoin больше, чем CryptoNote до 150%.

При подмешивание двух выходов ($$) размеры подписей в той и другой схемах практически совпадают.

При дальнейшем увеличении числа подмешиваемых выходов, размер подписи Bytecoin оказывается меньше.

Стоит отметить, что разработчики Bytecoin с выходом версии 3.4.0 Amethyst в целях увеличения анонимности установили минимальное число подмешиваемых выходов равным 3 [10]. В таких условиях подпись Bytecoin будет обладать меньшим размером.

Трудоемкость проверки подписи

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

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

В CryptoNote и Bytecoin используется несколько основных примитивов (см. раздел 2). В таблице на рис. 4.5.3. приведено характерное время выполнения самых часто используемых примитивов на современном middle-end компьютере с процессором Core i5-6500 (для сравнения использовался оригинальный исходный код, скомпилированный в Microsoft Visual Studio 2017 со всеми возможными оптимизациями по скорости).
Результаты, полученные из тестов в Bytecoin и CryptoNote хорошо согласуются между собой. Легко видеть, что наибольший вклад будет давать операция умножения скаляра на точку, и, в меньшей степени, процедура вычисления хеш-функции $$, при этом операции сложения двух точек и вычисления хеш-функции $$ не будут существенно влиять на сложность.

Рассмотрим процедуру проверки кольцевой подписи CryptoNote (рис. 4.5.4, процедура генерации подписи подробно рассмотрена в [1] и здесь рассматриваться не будет).
Как уже было отмечено, в CryptoNote подписывается отдельно каждый вход транзакции, соответственно, и проверяется также каждый вход отдельно. Поэтому, проверяющий для каждого входа транзакции проверяет соответствующую строку (на рисунке) подписи следующим образом.

1. Для каждой пары значений $$ и $$ при помощи key-image входа $$ и открытого ключа $$ очередного выхода, на который ссылается данный вход, вычисляются величины:$$
   $$
   (при этом индекс j пробегает значение от 0 до $$)
2. Вычисляется сумма $$ всех $$.
3. Вычисляется хеш $$)
   где tx_prefix_hash — хеш префиксной части транзакции (без подписи).
4. Проверяется равенство $$. Если оно выполняется, то кольцевая подпись считается действительной.

Оценим число операций умножения скаляра на точку и вычисления хеша $$.

Каждое вычисление $$ и $$ требует по два скалярных умножения. Число пар $$ соответствует числу подмешиваемых выходов $$ для каждого входа. Поэтому имеем:

$$

При этом хеш-функция $$ используется однократно при каждом вычислении $$, следовательно:

$$

Теперь рассмотрим алгоритм проверки кольцевой подписи в Bytecoin Amethyst (рис. 4.5.5).
Проверяется целиком вся подпись, для всех входов сразу. Происходит это так:

1. В хеш-буфер записывается префиксный хеш транзакции (без подписи).
2. Для каждого входа $$ (строка подписи на рисунке):
3. Вычисляется $$ по всем данным хеш-буфера и результат сравнивается с величиной $$.Подпись считается действительной, если равенство соблюдается.

Оценим число операций умножения скаляра на точку и вычисления хеша $$.

Каждое вычисление $$ и $$ требует по два скалярных умножения, плюс вычисление $$ требует трех скалярных умножений. Число пар $$ соответствует числу подмешиваемых выходов $$ для каждого входа. Поэтому имеем:

$$

При этом хеш-функция $$ используется однократно при каждом вычислении $$ и однократно для вычисления $$ для каждого из входов, следовательно:

$$

Чтобы наглядно сравнить вычислительную сложность обоих алгоритмов на типовых данных, введем следующую метрику. Сложим число операций скалярного умножения и операций вычисления $$ с весами, пропорциональными характерному времени выполнения этих операций:

$$

Затем сравним относительные результаты для CryptoNote и Byteсoin в процентах (рис. 4.5.6).
Как видно, проверка подписи Bytecoin является значительно более трудоемкой операцией.

Однако, как уже было отмечено выше, в Bytecoin с версии 3.4.0 Amethyst в целях увеличения анонимности установлено минимальное число подмешиваемых выходов равным 3 [10], поэтому худшее практическое значение не превысит 25% (в теории).

Подытожим:

1. Размер каждого выхода увеличивается на открытый ключ $$ — 32 байта.
2. Размер кольцевой подписи варьирует в сравнении с размером подписи CryptoNote в зависимости от числа подмешиваемых выходов (при большом их числе оказывается меньше):
   $$
3. Вычислительная сложность выше, чем в CryptoNote и значительно зависит от числа подмешиваемых выходов:
   $$
   $$

5. Вариант 2/3. Исследования аудита в CryptoNote от Anton Sokolov

Осенью 2019 года на площадке Medium.com была опубликована серия эссе [11, 12, 13, 14, 15, 18] о проблеме аудита в CryptoNote и возможных способах ее решения под авторством Anton Sokolov. В ней с теоретических позиций рассматриваются несколько вариантов модификации оригинального протокола таким образом, чтобы решить задачу аудита для третьей стороны.

Рассмотрим последнюю из них [15] как наиболее оптимизированную. Будем сокращенно обозначать ее как «AS».

Примечание: для единообразия изложения spend-ключи и далее будут обозначаться буквами $$ и $$, view-ключи — буквами $$ и $$, несмотря на то, что в оригинальных работах используются $$, $$ и $$, $$ соответственно.

Формирование выходов

Аккаунт кошелька представлен набором не двух, как в CryptoNote, а трех секретных ключей $$: view-, spend- и audit-ключи соответственно.

Совокупность трех открытых ключей $$ представляет публичный адрес этого аккаунта.

Алиса, отправляя деньги бобу, действует следующим образом (рис. 5.1).

1. Боб опубликовывает свой адрес, поэтому Алиса знает его открытые ключи $$, $$ и $$.
2. Так же, как и в CryptoNote, Алиса выбирает случайный секретный ключ транзакции $$ и вычисляет открытый ключ $$, который записывает в специальное поле extra транзакции.
3. Для каждого выхода Алиса вычисляет не один, а два стелс-адреса $$ и $$. Первый рассчитывается аналогично CryptoNote:
   $$
   Второй иначе:
   $$
   Порядковый номер выхода в оригинальной работе здесь не используется, однако, разумно предположить, что это сделано для упрощения и на практике он будет одним из аргументов функции $$ по аналогии с CryptoNote (см. раздел 3).
4. Алиса подписывает и отправляет транзакцию.

Сторонний наблюдатель не сможет связать $$ и $$ с адресом Боба.

Распознавание входящих платежей и формирование входов

Чтобы принять и потратить деньги, Боб действует следующим образом (рис. 5.2).

1. Используя свой секретный view-ключ $$, Боб стелс-адрес $$ каждого выхода сравнивает с точкой:
   $$
   (этот шаг аналогичен CryptoNote)
2. В случае, если равенство выполняется, это означает, что данный выход адресован Бобу. Он увеличивает свой баланс на величину номинала выхода.
3. При необходимости перевести полученные средства Кэрол, Боб, используя свои секретные spend- и audit-ключи $$ и $$, вычисляет два key image: $$ и $$. Первый — аналогично CryptoNote:
   $$
   и дополнительный:
   $$
   $$
   Затем записывает их, номинал и ссылку на соответствующий выход во вход своей транзакции для Кэрол.
4. Затем Боб формирует выходы транзакции для Кэрол, уменьшает свой баланс пропорционально потраченным выходам, подписывает транзакцию и отправляет.

Как видно, здесь так же, как и в CryptoNote третья сторона — Аудитор — обладая только секретным view-ключом $$, сможет распознать только входящие переводы.

Аудит

Если же Аудитор располагает также секретным audit-ключом $$, то он сможет распознать исходящие платежи Боба и рассчитать его баланс следующим образом:

1. Для каждого входящего платежа Аудитор будет рассчитывать и запоминать дополнительный key image $$ в локальном хранилище:
   $$
   $$
   
2. Если во входах какой-либо из транзакций блокчейна дополнительный key image $$ совпадёт с одним из сохраненных, то это будет означать, что данная транзакция является исходящим платежом Боба. Аудитор уменьшит баланс на номинал соответствующего входа.

Таким образом, Аудитор, обладая набором ключей $$ сможет распознать в блокчейне входящие и исходящие переводы Боба и восстановить его корректный баланс. При этом потратить средства Аудитор не сможет, т.к. без секретного spend-ключа $$ он не сможет вычислить основной key image $$.

Задача решена.

Кольцевая подпись

Применив идеи из работы [16], автору удалось уменьшить размер подписи по сравнению с CryptoNote: теперь, для каждого входа в подписи хранится только $$ скаляр (рис. 5.3).
Таким образом, размер подписи уменьшается почти вдвое.

Рассмотрим вычислительную сложность ее проверки. Схема проверки подписи представлена на рис. 5.4.
Этот алгоритм очень похож по структуре на используемый в CryptoNote (см. рис. 4.5.4). Проверка осуществляется раздельно для каждого входа и состоит в последовательном вычислении значений $$, $$, $$, $$ для всех выходов, использованных для подмешивания в данном входе. В результате, цикл из $$ должен замкнуться и величина $$ должна совпасть с $$, в этом случае подпись считается действительной.

Вычислительная сложность алгоритма определяется шестью операциями скалярного умножения и одним вычислением хеш-фукнции $$ на итерацию, число который есть произведение $$.

Сравнение с CryptoNote по данным и вычислительной нагрузке

1. Размер адреса увеличивается на 50%, т.к. адрес теперь представляет совокупность трех открытых ключей: $$, а не двух $$.
   Кодированное представление адреса увеличится примерно на столько же: например, стандартный Zano-адрес, содержащий два открытых ключа, занимает 97 символов:
   

   ZxD5UBX5PM3RTsEtTRd9ATUFxXyocoQzDRk3baVBahuWQJRK8QHTUT9GQM7jk7GoedK5B2nP4HxSPDpuLHvizpwj2q99bmz7t

   
   Аналогичный Zano-адрес, содержащий три открытых ключа будет иметь длину порядка 141 символа:
   

   ZxD5UBX5PM3RTsEtTRd9ATUFxXyocoQzDRk3baVBahuWQJRK8QHTUT9GQM7jk7GoedK5B2nP4HxSPDpuLHvizpwjcenhnGbhpJFLk8vkhJywHCcht4d9EKA7CHHav1H6QPpB1cLsTvPfj

2. Размер каждого выхода увеличивается на дополнительный стелс-адрес $$ — 32 байта.
3. Размер каждого входа увеличивается на дополнительный key image $$ — 32 байта.
4. Размер кольцевой подписи меньше, чем в CryptoNote:
   $$
5. Вычислительная сложность выше, чем в CryptoNote:
   $$
   $$

6. Вариант 3/3. Аудит через ограничение на подмешивание выходов

Рассмотрим еще один способ реализации аудита в CryptoNote.

Атрибут выхода mix_attr

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

Структуру выходов CryptoNote и Bytecoin (рис. 4.2) мы можем теперь дополнить таким образом (рис. 6.1.).
Правило ядра, ограничивающее подмешивание в зависимости от mix_attr, таково:

1. Если mix_attr = 0, то ограничений нет. Данный выход может использоваться для подмешивания с другими выходами в любых комбинациях. Это — значение по-умолчанию.
2. Если mix_attr = 1, то данный выход может быть потрачен только непосредственно, без подмешивания, и не может быть использован для подмешивания к другим выходам.
3. Если mix_attr ? 2, то данный выход может быть потрачен только при подмешивании других, при этом общее число использованных выходов не должно быть меньше величины mix_attr.

Главной особенностью этого нововведения является п. 3, что позволяет увеличить untraceability (неотслеживаемость связей) за счет исключения ситуаций, когда выход, уже использованный в подмешивании, тратится его владельцем непосредственно (это подробно рассмотрено в [19]).

Однако, в контексте данной статьи, нас будет интересовать п. 2, то есть ситуация, когда mix_attr = 1 и выход, помеченный таким образом, может быть потрачен только непосредственно. Это ограничение проиллюстрировано на рис. 6.2.
Так как output #2 имеет mix_attr = 1, то он не может быть смешан с другими выходами, вне зависимости от их значений атрибута mix_attr. Он может быть только потрачен непосредственно, как output #0.

Эту особенность можно использовать для организации аудита.

Аудит при помощи mix_attr = 1

Как было отмечено в разделе 3, если в рамках оригинального протокола CryptoNote аудитор Ден получит от Боба секретный ключ $$, он сможет распознать входящие транзакции, но не сможет распознать исходящие, поэтому точный расчет баланса невозможен.

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

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

Схема работы будет выглядеть следующим образом (рис. 6.3).

1. Боб сообщает Алисе свой публичный адрес $$, а также просит ее во всех выходах, адресованных ему, поставить атрибут mix_attr в значение 1 (ниже рассмотрим, как это можно реализовать технически).
2. Боб передает аудитору Дену свой секретный view-ключ $$.
3. Алиса отправляет Бобу транзакцию по обычной схеме CryptoNote. В выходах, адресованных Бобу она ставит mix_attr = 1.
4. Ден сканирует все транзакции в блокчейне и с помощью секретного view-ключа Боба проверяет для каждого выхода $$ (где $$ — порядковый номер выхода, $$ — открытый spend-ключ Боба). Если равенство выполняется, то данный выход адресован Бобу.
   Ден убеждается, что mix_attr == 1, добавляет данный выход в список и увеличивает баланс на величину номинала выхода.
5. Ден также проверяет все входы всех транзакций, и если один из входов ссылается на UTXO Боба из списка, то это означает, что данная транзакция — исходящий платеж Боба. Благодаря ограничению mix_attr = 1, данных вход не может подмешивать другие выходы, а значит он тратит выход Боба непосредственно, и Ден может быть уверен, что это исходящий платеж Боба.Ден уменьшает баланс на величину номинала входа.

Таким образом, Ден сможет рассчитать корректный баланс кошелька Боба, не получая доступа к его секретному spend-ключу $$.

Особенности схемы

Особенность 1. Важно, чтобы отправляющая сторона (Алиса) поставила mix_attr в значение 1 при отправке транзакции. Если Алиса этого не сделает, то средства придут Бобу, однако в дальнейшем Ден не сможет однозначно сказать, потратил их Боб или нет, так как любой другой пользователь сможет использовать данных выход для подмешивания.

Один из вариантов решения — введение адресов особого типа, содержащих те же два открытых ключа $$, но упакованных отличным от стандартного образом. Алиса, отправляя средства на адрес такого типа, будет знать о необходимости установить mix_attr = 1 для соответствующих выходов.

Особенность 2. Использование адресов особого типа не обязывает Алису устанавливать нужное значение атрибута для выходов. Она может отправить средства не сделав этого, однако, это будет сразу же выявлено как Бобом, так и аудитором Деном.

Особенность 3. В данной схеме возможность аудита достигается ценой предельного уменьшения untraceability (неотслеживаемости связей). Это не представляет особой проблемы в случае, если возможность аудита предоставлена неограниченному кругу лиц. Например, благотворительный фонд может опубликовать адрес для пожертвований вместе с секретным view-ключом, благодаря чему любой желающий сможет выступить в качестве аудитора и рассчитать актуальный баланс его кошелька. Важно, что при этом анонимность входящих переводов остается стандартной для CryptoNote (можно использовать большое число $$). Однако, анонимность исходящих платежей будет ограничена невозможностью подмешивать произвольные выходы.

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

Большими достоинствами этого варианта являются простота реализации и отсутствие дополнительной нагрузки по вычислениям и данным.

7. Заключение

Мы рассмотрели три варианта добавления возможности проведения аудита в протокол CryptoNote: Bytecoin Amethyst, теоретическая схема AS от Anton Sokolov и использование mix_attr (обозначим как MA).

Относительное изменение размера кольцевой подписи для всех вариантов, кроме Bytecoin (BCN), не зависит от $$, поэтому рассмотрим $$ (минимальный) и $$ (рис. 7.1).
Примечание. $$ — число входов в транзакции, $$ — число выходов, ассоциированных с каждым входом транзакции. Если $$ то это означает, что для увеличения untraceability каждый вход ссылается более чем на один выход какой-то другой транзакции и при этом нельзя установить, какой из них реальный.

Лучший результат показывает схема AS, давая уменьшение размера кольцевой подписи в широком диапазоне числа подмешиваемых выходов ($$). Bytecoin также дает хороший результат при $$ (как уже было отмечено, в Bytecoin Amethyst для повышения untraceability было введено ограничение на минимальное число $$ равное 3).

Схема MA никаких улучшений в части размера кольцевой подписи не предлагает.

Сравним теперь трудоемкость процедуры проверки кольцевой подписи. Для этого будем использовать метрику, упоминавшуюся выше, а именно возьмем сумму операций скалярного произведения и вычисления хеш-функции $$ с весами, пропорциональными их времени выполнения на типичном современном процессоре:

$$

Имеем следующую картину (рис. 7.2).
При прямой трате средств ($$) схемы AS и Bytecoin требуют существенно большего объема вычислений для проверки подписи.

При подмешивании выходов ($$) схема Bytecoin Amethyst выглядит предпочтительнее AS, однако последний рассмотренный вариант MA остается непревзойденным.

Подведем окончательный итог, приняв во внимание такие факторы, как увеличение размера адреса, входов и выходов транзакций (рис. 7.3).
Bytecoin сохраняет удобную для конечного пользователя длину адреса, в то время как схема Anton Sokolov увеличивает его на 50%. Это не влияет непосредственно на размер блокчейна (хотя адрес отправителя в зашифрованном виде может передаваться в extra транзакции при желании последнего, например) и вычислительную сложность, однако незначительно влияет на удобство использования. В схеме MA размер адреса остается равным 64 байтам, однако требуется способ отличать адреса, предназначенные для аудита, от обычных.

Варианты реализации аудита Bytecoin и AS подразумевают добавление одной точки (32 байт) к каждому выходу транзакции, однако, размер входа остается неизменным только для Bytecoin.

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

Схема AS, напротив, описана строго и предложена к обсуждению в криптосообществе [17].

Схема MA не имеет строго описанного формального доказательства, однако, в силу ее крайней простоты, оно представляется излишним.

Литература

1. Nicolas van Saberhagen, «CryptoNote v 2.0»
2. Анонс Bytecoin на форуме bitcointalk.org
3. Анонс Bitmonero на форуме bitcointalk.org
4. Репозиторий Bitmonero в Github
5. Bernstein et al. «Ed25519: high-speed high-security signatures»
6. PatientZero, «Доступно о криптографии на эллиптических кривых»
7. Shen Noether, «Understanding ge_fromfe_frombytes_vartime»
8. Shen Noether, MRL, «Ring confidential transactions»
9. Коммит, задающий численно константу H в коде Monero
10. Bytecoin blog — Auditable coins
11. Anton Sokolov, «Cryptonote auditability. How to append a wallet balance audit.»
12. Anton Sokolov, «Discussion for the auditable wallets Variant 1 and 2»
13. Anton Sokolov, «The unlinkable auditable Variant 3»
14. Anton Sokolov, «The auditable variant 4. Memory efficiency and security question.»
15. Anton Sokolov, «Multi-signature with LSAG. One more memory efficient approach to auditable wallets.»
16. Abe, Ohkubo, Suzuki, «1-out-of-n Signatures from a Variety of Keys» (AOS)
17. Anton Sokolov, «Cryptonote auditability and efficient scheme for anonymous key vector proof»
18. Anton Sokolov, «Practical approach for appending auditable wallets to the Cryptonote»
19. «Boolberry Solves CryptoNote Issues»
20. «Bytecoin Amethyst Stable Release Extended Technical Description»