Что такое подписи Шнорра? Что такое Taproot?

Когда Сатоши Накамото начинал работать над Биткойном, один из ключевых моментов, которые необходимо было учесть, заключался в том, какую из схем подписи следует выбрать для открытой и общедоступной финансовой системы. Требования были ясны: нужно было создать алгоритм, который был бы широко используем, понятен, достаточно безопасен, лёгок и, самое главное, с открытым исходным кодом. Из всех доступных на тот момент опций он выбрал ту, что отвечает этим критериям лучше всего: Elliptic Curve Digital Signature Algorithm (алгоритм цифровой подписи, основанный на эллиптических кривых), или ECDSA.

В то время нативная поддержка ECDSA была предусмотрена в OpenSSL, открытом наборе инструментов шифрования, разработанных шифропанками со стажем с целью повышения конфиденциальности онлайн-коммуникаций. По сравнению с другими популярными схемами, ECDSA обладает такими преимуществами, как меньшая требовательность к вычислительным ресурсам и меньшая длина ключей – это полезные свойства для цифровых денег. В то же время он обеспечивает пропорциональный уровень безопасности для таких схем, как RSA: к примеру, 256-битный ECDSA-ключ обладает равноценным в сравнении с 3072-битным RSA-ключом уровнем безопасности при значительно меньшем размере ключа.

Благодаря тяжёлой работе, проделанной Питером Вуйле с коллегами над улучшенной эллиптической кривой, называемой secp256k1, ECDSA Биткойна стал ещё быстрее и эффективнее. Однако ECDSA по-прежнему присущи и некоторые недостатки, которые могут служить достаточным основанием и для полной его замены. После нескольких лет исследований и экспериментов была установлена новая схема подписи, повышающая конфиденциальность и эффективность транзакций Биткойна: схема цифровой подписи Шнорра.

В этой статье я расскажу в общих чертах о многочисленных имплементациях подписей Шнорра и о преимуществах этих подписей. Затем мы поговорим о MuSig, новом стандарте мультиподписи, который может служить основой для внедрения новых биткойн-технологий, таких как Taproot. Наконец, я расскажу вам, как полная реализация подписей Шнорра может нарушить используемую в блокчейн-аналитике эвристику и в то же время способствовать развитию сильного рынка комиссий на основном слое Биткойна.

История появления подписей Шнорра

Притом, что схема цифровых подписей Шнорра обладает множеством преимуществ по сравнению с ECDSA, она определённо не нова. Она была изобретена ещё в 1980 гг. Клаусом-Петером Шнорром, немецким криптографом и академиком, на тот момент профессором и исследователем Франкфуртского университета. В основание предложенной им схемы подписи легли исследования и работы Дэвида Чаума, Тахера Эль-Гамаля, Амоса Фьята и Ади Шамира. Тем не менее, прежде чем опубликовать новую схему, Клаус Шнорр заполнил множество патентов, которые в течение многих лет препятствовали её прямому использованию.

Интересно, что предшественник ECDSA, алгоритм DSA, представлял собой гибрид схем Эль-Гамаля и Шнорра, созданный исключительно для обхода патентов Клауса Шнорра. На самом деле, всего через два месяца после выдачи американского патента Клаусу Шнорру прародитель DSA, Национальный институт стандартов и технологий США (NIST), также оформил патент для своего решения. После этого Клаус Шнорр стал ещё активнее защищать свои патенты и прямо ответил своим критикам в рассылке Coderpunks (ответвлении оригинальной email-рассылки Cypherpunks). Его ответы можно прочитать здесь и здесь (англ.). А здесь можно найти внутреннюю записку NIST с описанием патентных проблем.

В 2008 году, спустя почти два десятилетия после представления схемы подписи Шнорра, срок действия патента Клауса Шнорра истёк. По совпадению, 2008 стал также годом, когда Сатоши Накамото, представил миру Биткойн. Несмотря на то что подписи Шнорра на тот момент уже можно было использовать, они ещё не были стандартизированными или широко используемыми. Вероятно, поэтому Сатоши и остановил свой выбор на ECDSA. И, хотя криптографы и математики часто характеризуют этот алгори, ECDSA до сих пор довольно широко используется, а на тот момент он был более безопасной опцией для Биткойна.

Протокол цифровой подписи

Алгоритм Шнорра также можно использовать и в качестве протокола цифровой подписи сообщения M. Пара ключей используется та же самая, но добавляется однонаправленная хэш-функция H(M).

Генерация подписи

1. Предварительная обработка.
   Пегги выбирает случайное число r, меньшее q, и вычисляет x= g^r \pmod p. Это стадия предварительных вычислений. Стоит отметить, что для подписи разных сообщений могут использоваться одинаковые открытый и закрытый ключи, в то время как число r выбирается заново для каждого сообщения.
2. Пегги объединяет сообщение M и x и хэширует результат для получения первой подписи: S_1=H(M | g^r \bmod p)
3. Пегги вычисляет вторую подпись. Необходимо отметить, что вторая подпись вычисляется по модулю q. S_2=r+wS_1 \bmod q.
4. Пегги отправляет Виктору сообщение M и подписи S_1, S_2.

Проверка подписи

1. Виктор вычисляет X = g^{S_2}y^{S_1}\bmod p (либо X = g^{S_2}y^{-S_1}\bmod p, если вычислять y как y=g^{w}\pmod p).
2. Виктор проверяет, что H(M|X)=S_1. Если это так, то он считает подпись верной.

Эффективность

Основные вычисления для генерации подписи производятся на этапе предварительной обработки и на этапе вычисления wS_1\bmod q, где числа w и S_1 имеют порядок 140 битов, а параметр r — 72 бита. Последнее умножение ничтожно мало по сравнению с модульным умножением в схеме RSA.

Проверка подписи состоит в основном из расчета X = g^{S_2}y^{S_1}, который может быть сделан в среднем за 1.5l + 0.25t вычислений по модулю p, где l = [log_2q] есть длина q в битах.

Более короткая подпись позволяет сократить количество операций для генерации подписи и верификации: в схеме Шнорра O(\log_2q\log_2^2p), а в схеме Эль-Гамаля O(\log^3p).

Пример

Генерация ключей:

1. q = 103 и p = 2267. Причем p = 22q + 1.
2. Выбирается f=2, который является элементов в поле Z_{2267*}. Тогда \frac{p-1}{q} = 22 и g = 2^{22} \bmod 2267 = 354
3. Пегги выбирает ключ w = 30, тогда y = 1206
4. Секретный ключ Пегги — 30, открытый ключ — (103,2267,354,1206).

Подпись сообщения:

1. Пегги нужно подписать сообщение M=1000.
2. Пегги выбирает r = 11 и вычисляет g^r = 354^{11} = 630 mod 2267.
3. Предположим, что сообщение — 1000 , и последовательное соединение означает 1000630 . Также предположим, что хэширование этого значения дает дайджест H(1000630) = 200 . Это означает S_1 = 200 .
4. Пегги вычисляет S_2 = r + wS_1 mod q = 11 + 30*200 mod 103 = 11 + 26 = 37.
5. Пегги отправляет Виктору M=1000, S_1 =200 и S_2 = 37.

Подписи Шнорра в Биткойне

Пропустим на быстрой перемотке ещё одно десятилетие и перенесёмся в сегодняшний день. Схема подписей Шнорра теперь выглядит намного менее эзотерично и её стандартизированные реализации – такие как ed25519 – становятся популярной опцией для некоторых альткойнов. Неформальные разговоры о потенциальной реализации подписей Шнорра в сети Биткойна восходят к этой ветке форума BitcoinTalk, датируемой 2014 годом, но предложение было формализовано только после нескольких лет исследований и экспериментов, когда Питер Вуйле написал Schnorr BIP (Bitcoin Improvement Proposal, «предложение по улучшению Биткойна»). В этом черновике предложения описывается спецификации и технические аспекты потенциальной реализации подписей Шнорра, которые будут обладать следующими преимуществами по сравнению с ECDSA:

• Доказательство безопасности:
  Безопасность подписей Шнорра легко доказывается при использовании в достаточной мере случайной хеш-функции (модель случайных оракулов) и достаточной сложности задачи дискретного логарифмирования в группе точек эллиптической кривой (elliptic curve discrete logarithm problem, ECDLP). Для ECDSA такого доказательства не существует.
• Негибкость:
  ECDSA-подписи по своей природе являются гибкими, что может позволить третьей стороне, не имеющей доступа к секретному ключу, изменить существующую действительную подпись и расходовать средства дважды. Официально эта проблема обсуждалась в BIP62. Для сравнения, подписи Шнорра являются доказуемо негибкими.
• Линейность:
  Подписи Шнорра обладают замечательным свойством: несколько сторон могут совместно создать подпись, действительную для суммы их открытых ключей. Это может служить конструкционным блоком для различных конструкций более высокого уровня, повышающих эффективность и приватность – таких как мультиподписи и прочие смарт-контракты.

Доказательства безопасности подписей Шнорра, а также гарантия их негибкости, дают им явные преимущества над ECDSA. Уже эти два преимущества могут служить достаточным основанием для софт-форка. Но особенно впечатляющим свойством подписей Шнорра является их линейность. В частности, это позволяет нескольким подписантам транзакции с мультиподписью объединять свои открытые ключи в один агрегированный ключ, представляющий всю группу – это свойство называется агрегированием ключей.

Хотя возможность объединения ключей в один может прозвучать несколько тривиально, преимуществ этого не следует недооценивать. Поскольку в ECDSA нет нативной поддержки мультиподписей, в Биткойне их пришлось реализовывать через стандартизированный смарт-контракт (да-да, в Биткойне тоже есть смарт-контракты), называемый Pay-to-ScriptHash (P2SH). Он позволяет пользователям добавлять условия расходования, называемые обременениями, чтобы указать, как могут быть потрачены средства – например, «разблокировать баланс только если сообщение подпишут Боб и Алиса».

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

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

Блокчейн-аналитик: «Определённо, мультиподпись». – Не хорошо.

В примере выше сеть будет знать (1) о существовании транзакции с мультиподписью, (2) о том, сколько адресов участвуют в мультиподписи и (3) о том, кто именно подписал транзакцию. Не здорово для операционной безопасности, особенно для таких вариантов использования, как 2FA. Это плохо с точки зрения конфиденциальности.

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

Блокчейн-аналитик: «Это может быть мультиподписью… Невозможно сказать наверняка…» – Теперь хорошо.

Первая итерация подписей Шнорра в Биткойне упразднит семейство опкодов OP_CHECKSIG и OP_CHECKMULTISIG, используемых в настоящее время с ECDSA, в пользу нового класса опкодов, называемого OP_CHECKDLS. Если не слишком вдаваться в подробности, DLS означает Discrete Log Signature (подпись с дискретным логарифмированием), и это позволяет верифицировать подписи эффективнее и с меньшим количеством опкодов.

Ещё в начале 2020 года Грегори Максвелл, Эндрю Поэлстра, Янник Сеурин и Питер Вуйле опубликовали уайтпэйпер новой, основанной на подписи Шнорра схемы мультиподписи, под названием MuSig. После этой публикации они много работали над переводом предлагаемой схемы мультиподписи в пригодный для использования код.

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

В декабре 2020 года Энтони Таунс стал первым разработчиком Bitcoin Core, подготовившим полуформализованное предложение по активации подписей Шнорра, которое было представлено в рассылке для разработчиков Биткойна. Я ожидаю, что в ближайшие месяцы количество разговоров о потенциальном софт-форке возрастёт.

Подводя итог сказанному, первая итерация MuSig в Биткойне будет обладать поддержкой агрегирования ключей, что может немедленно (1) улучшить конфиденциальность мультиподписей, (2) повысить эффективность проверки транзакций, (3) повысить безопасность за счёт устранения проблем, присущих ECDSA, и (4) обеспечить возможность для интеграции таких смарт-контрактов, как Taproot, о котором мы поговорим в следующем разделе.

И это только начало.

Что такое подписи Шнорра? Что такое Taproot?

Taproot предлагает собственную версию дерева Меркла, именуемую деревом скрипта. Участники могут выбрать расходование с помощью:

• публичного ключа в качества обычной подписи;
• расходование с помощью скрипта.

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

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

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

Taproot использует структуру MAST, чтобы скрыть условия, стоящие за корнем Меркла. Сам корень Меркла в этом сценарии скрывается и позволяет осуществлять посредством ключа прямые траты. В блокчейн отправляется только одиночный ключ – никто не видит, что существуют дополнительные условия.

В комбинации с подписями Шнорра структура MAST скрыта благодаря выходам Taproot. В верхней части дерева Меркла присутствует опция публикации одиночного публичного ключа и подписи. В результате транзакции P2PKH и P2SH выглядят идентично.

Иллюстрацией может служить закрытие Lightning-канала.

Lightning-каналы – это вариации мультиподписи 2-из-2. Вместо того, чтобы закрывать транзакцию с помощью громоздкого скрипта, Шнорр позволяет объединить подписи и представить в виде открытого ключа/подписи Taproot. Когда обе стороны согласны, то результат выглядит так, словно кто-то израсходовал этот выход с помощью обычной подписи, послав на два адреса. Наблюдатель не сможет определить, что это Lightning-канал.

TapBranch – это дерево скрипта (TapTree) для закрытия канала Lightning

Чтобы скрыть структуру MAST, хеш TapBranch на графике выше хешируется с помощью агрегированного публичного ключа (благодаря схеме Шнорра Алиса и Боб могут добавлять свои публичные ключи для создания внутреннего ключа Taproot).

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

Далее измененный публичный ключ добавляется к внутреннему ключу Taproot для создания ключа выхода Taproot. Процесс проиллюстрирован ниже:

Как было сказано, существуют два ключа траты. Путь расходования по умолчанию – это когда Алиса и Боб соглашаются закрыть Lightning-канал, а ключ выхода Taproot гарантирует, что транзакция выглядит как стандартная транзакция P2PKH. В других сценариях используемый скрипт раскрывается, как только монеты потрачены, тогда как все другие опции остаются скрытыми.

В вышеприведенном примере, если Алиса и Боб соглашаются осуществить Lightning-платеж, они могут совместно объединить подписи Шнорра, создать главный публичный ключ, вместе добавить подписи и создать главную подпись.

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

В случае, когда закрытие несовместное, раскрывается только используемый скрипт. Верифицирующие смогут определить, что пороговый публичный ключ был изменен посредством корня Меркла. Однако все остальные опции/скрипты останутся скрытыми.

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

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

Усложненные транзакции позволяют значительно сэкономить на комиссиях, поскольку требующие обработки большого количества данных скрипты уже не должны платить комиссии, суммы которых превышают суммы комиссий в стандартной транзакции Pay-to-Public-Key-Hash. Чем сложнее транзакции, тем выше их эффективность.

Поскольку Taproot позволяет осуществлять усложненные транзакции с помощью всего лишь одной подписи, количество байтов, используемых для агрегированных ключей и подписей, не меняется в зависимости от числа подписантов. При использовании мультиподписи Witness-Script-Hash (P2WSH) каждый дополнительный публичный ключ добавляет 8,5 байтов, а каждая дополнительная подпись – приблизительно 18,25 байтов.

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

Хотя схема Шнорра позволяет придавать мультиподписным транзакциям видимость обычных транзакций Pay-to-Public-Key-Hash, Taproot расширяет круг транзакций, которым можно придать такую видимость (сделать Pay-to-Public-Key-Hash и Pay-to-Script-Hash неотличимыми).