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

Схема подписей Шнорра и технология Taproot – это предложения по улучшению протокола биткоина BIP-340 и BIP-341. 21 января 2020 года разработчик Питер Велле включил в запрос на принятие изменений для софтфорка.

Схему подписей Шнорра предложил в 1991 году немецкий криптограф, профессор Франкфуртского университета Клаус-Петер Шнорр.

Предложенная Шнорром схема является модификацией схем наработки криптографа Дэвида Чаума.

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

Когда Накамото создавал биткоин, он должен был выбрать одну из существующих схем подписи. Ему был необходим простой в использовании и безопасный алгоритм с открытым исходным кодом. Этим требованиям отвечала ECDSA. Предшественник ECDSA, алгоритм DSA, представлял собой гибрид схемы Шнорра и схемы Эль-Гамаля и был создан для обхода патентов Шнорра.

ECDSA в биткоине стала быстрее и эффективнее благодаря работам Питера Велле и его коллег, которые создали улучшенную эллиптическую кривую, secp256k1.

ECDSA имеет отдельные недостатки, и разработчики искали альтернативу. Первые обсуждения возможной реализации подписей Шнорра в сети биткоина состоялись в 2014 году, а спустя несколько лет разработчик Питер Велле опубликовал Schnorr BIP.

Безопасность

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

Подписи Шнорра – более прозрачная прикладная технология, с которой проще работать криптографам.

Негибкость

Подписи Шнорра являются доказуемо негибкими, тогда как ECDSA-подписи – гибкие, что дает третьей стороне, не имеющей доступа к закрытому ключу, возможность изменить существующую действительную подпись и произвести двойную трату.

Линейность

Существенное преимущество подписей Шнорра – свойство линейности, реализуемое за счет линейной математики.

Подписи Шнорра линейны в том смысле, что они могут быть предметом добавления или вычитания. Результат таких операций – действительная подпись, соответствующая тому же сложению (или вычитанию) открытых ключей. В случае ECDSA такая схема не работает – вычитание или добавление таких цифровых подписей не имеет смысла.

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

Уравнения ниже иллюстрируют процесс агрегирования, возможный благодаря свойству линейности подписей Шнорра. Никто, кроме участников, не знает, что за одним открытым ключом/подписью стоят три человека.

В мультиподписных транзакциях M-из-n частичные подписи известны как пороговые подписи. Как показывает график ниже, в мультиподписи 3-из-5 мы имеем M=3 подписи (из n=5) как часть входов транзакции.

Мультиподписным транзакциям M-из-n необходимо как минимум M подписантов и верификация каждой подписи. Чтобы подтвердить владение UTXO мультиподписного ключа, деблокирующий скрипт scriptSig должен содержать число M подписей ECDSA. Размер scriptSigs растет линейно в соответствии с числом M подписей, что увеличивает размер этих транзакций (и сумму транзакционных комиссий).

Кроме того, наблюдатель будет знать, что A, B и C подписали транзакцию, и сможет идентифицировать используемую мультиподписную схему.

С помощью подписей Шнорра M подписей агрегируются в единую подпись. Как только предоставлены открытые ключи и пороговые подписи, транзакция авторизована и выглядит как обычная P2PKH-транзакция.

Подписи Шнорра позволяют создавать только одну подпись для всех M сторон. Деблокирующий скрипт будет иметь одну подпись, представляющую собой агрегат всех подписей участников.

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

Уменьшение размера транзакции и повышение скорости верификации

По своему размеру подписи Шнорра на 11% меньше существующих подписей, которые занимают приблизительно 70–72 байт в транзакции. Поскольку они занимают меньше места в блокчейне (их фиксированный размер – 64 байта), это позволяет уменьшить размер транзакции и снизить комиссии.

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

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

Компактную мультиподпись с ECDSA труднее создать, поскольку такие подписи кодируются по стандарту DER, в отличие от подписей Шнорра, кодировка которых требует меньшего пространства.

BIP-340 – стандартизация подписей Шнорра, позволяющая интегрировать их в протокол биткоина.

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

Если подписи Шнорра имплементируют, обычный пользователь фактически не заметит их появления (за исключением одного символа в адресах SegWit). Подписи Шнорра не заменят ECDSA в биткоине – обе схемы будут сосуществовать.

Taproot (BIP-341) – это вторая часть предложения, включающего Шнорр/Taproot/Tapscript. Если схема Шнорра предлагает новый тип подписи, то Taproot расширяет их функционал, представляя новую версию выхода транзакции и новый способ определения условий расходования.

Taproot близко, или Следующая ступень эволюции биткоина

Технологию Taproot спроектировал и предложил разработчик Bitcoin Core и бывший CTO компании Blockstream Грегори Максвелл .

В апреле 2018 года математик Эндрю Поэлстра опубликовал математическое доказательство безопасности (security proof). В июле того же года инженер Xapo и разработчик Bitcoin Core Энтони Таунс предложил решение, позволяющее увеличить объем данных, используемых Taproot.

6 мая 2019 года Питер Велле опубликовал предложения по улучшению протокола биткоина, в котором представил обновления Taproot в связке с подписями Шнорра и MAST. Для имплементации обновлений в кодовую базу биткоина Велле предложил провести софтфорк.

21 января 2020 года Велле включил Taproot в запрос на принятие изменений для очередного софтфорка.

The Schnorr/Taproot proposal is now published as BIPs 340, 341, and 342; see https://t.co/33uiulO8RA

Note that the assignment of BIP numbers is not any kind of stamp of approval; it just means the process was followed (which includes some amount of public discussion).

— Pieter Wuille (@pwuille) January 24, 2020

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

• использование P2PKH и P2WPKH, т.е., одиночных трат;
• n-из-n траты с MuSig или эквивалентов (аналогичных текущему использованию P2SH и P2WSH 2-из-2 мультиподписей);
• k-из-n (для минимальных значений n) с использованием наиболее распространенного k подписантов;
• закрытия каналов в сети Lightning Network, атомарные свопы и другие протоколы, которые иногда могут приводить к тому, что все стороны согласны с результатом.

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

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

Понимание Taproot требует предварительного понимания решения MAST.

Благодаря наличию SegWit в сети биткоина концепция MAST получила вторую жизнь

Технологию MAST (абстрактное синтаксическое дерево на базе дерева Меркла) предложил в 2016 году разработчик  Джонсон Лау.

MAST предлагает использование новой программы-свидетеля и с помощью дерева Меркла декодирует взаимоисключающие ветви в скрипте.

Дерево Меркла – это структура данных; термин «дерево» описывает структуру его ветвей. Обычно дерево Меркла изображают, как на графике ниже: корень находится вверху, листья – в нижней части графика.

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

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

Этот процесс повторяется и продолжается до тех пор, пока не остается только один идентификатор, именуемый корнем Меркла (Адрес = Хеш (1,2) на графике выше), который уникальным образом идентифицирует весь набор данных в нескольких байтах. Корень Меркла можно рассматривать как «сейф» для монет.

В отличие от Pay-to-Script-Hash (P2SH), MAST позволяет структурировать в дереве Меркла множество условий расходования. При этом раскрываются только выполненные условия: с помощью корня и дерева Меркла подтверждается, что условие находится в дереве Меркла. Остальное дерево остается скрытым.

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

MAST дает следующую возможность: если любые данные в дереве Меркла раскрываются, то корень Меркла и ряд дополнительных данных (именуемых путем Меркла) можно использовать для подтверждения того, что конкретные данные были включены в дерево Меркла. Остальное дерево (и, соответственно, другие условия) остаются хешированными и скрытыми. Это означает, что при условии согласия всех участников раскрывать необходимо только выполненное условие.

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

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

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

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

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 неотличимыми).