Механизмы подписей Шнорра и Taproot: подробный обзор

Механизмы подписей Шнорра и Taproot: подробный обзор

• 1

  Что такое схема подписей Шнорра?

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

• 2

  Кто и когда изобрел схему подписей Шнорра?

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

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

  Предложенная Шнорром схема является модификацией схем Эль-Гамаля (1985) и Фиата-Шамира (1986), но имеет меньший размер подписи, а также использует наработки криптографа Дэвида Чаума .

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

Каковы ключевые технические особенности подписей Шнорра и их преимущества над ECDSA?

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

Шнорра

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

Негибкость

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

Линейность

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

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

Подписи Шнорра и Taproot в мультиподписных транзакциях

• В мультиподписных транзакциях M-из-n частичные подписи известны как пороговые подписи.
• В мультиподписи 3-из-5 мы имеем M=3 подписи (из n=5) как часть входов транзакции.
• Мультиподписным транзакциям M-из-n необходимо как минимум M подписантов и верификация каждой подписи.
• С помощью подписей Шнорра M подписей агрегируются в единую подпись.

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

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

Одна подпись для всех участников

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

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

• По своему размеру подписи Шнорра на 11% меньше существующих подписей, которые занимают приблизительно 70–72 байт в транзакции. Поскольку они занимают меньше места в блокчейне (их фиксированный размер – 64 байта), это позволяет уменьшить размер транзакции и снизить комиссии.
• Также, если транзакция биткоина содержит множество входов, каждому из них нужна отдельная подпись. Для транзакции биткоинов, контролируемых многими подписантами, каждый подписант должен поставить отдельную подпись ECDSA. Эти подписи подтверждаются индивидуально. Чтобы эффективно верифицировать группу подписей, необходимо использовать математические расчеты.
• Благодаря подписям Шнорра всем входам понадобится только одна объединенная подпись. Включение в транзакцию одной подписи дает дополнительные возможности для других транзакций. Уменьшение размера транзакций для мультиподписных транзакций позволяет уменьшить комиссии. Агрегирование ключей позволяет отказаться от проверки каждого индивидуального входа и ускорить процесс подтверждения.

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

4

Реализация подписей Шнорра в биткоине

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

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

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

5

Taproot (BIP-341)

• Taproot (BIP-341) – это дополнение к схеме Шнорра, которое расширяет функционал подписей и предлагает новый способ определения условий расходования.

• Данная технология является следующим этапом эволюции биткоина.

6

История создания Taproot

• Taproot был разработан и предложен специалистом в 2018 году.

Разработчик 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

• Какие возможности дает Taproot?

Taproot — это расширение возможностей мультиподписных транзакций с помощью подписей Шнорра. Оно позволяет придавать видимость стандартных транзакций для группы типов транзакций, включая одиночные траты, мультиподписи, траты с использованием наиболее распространенных подписантов и закрытие каналов в Lightning Network, атомарные свопы и другие протоколы. Taproot позволяет придавать совместному результату в блокчейне вид расходов одного ключа, что освобождает пространство для более сложных транзакций. Решение MAST также играет важную роль в понимании Taproot. Технологию MAST (абстрактное синтаксическое дерево на базе дерева Меркла) предложил в 2016 году разработчик Джонсон Лау.

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

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

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

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

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

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

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

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

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

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

Недостатки MAST и возможное решение проблемы

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

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

9

Преимущества Taproot перед MAST

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-Script-Hash.

Подписывайтесь на канал Cryptoit в YouTube !