Подпись Шнорра

Сегодня мы поговорим про одно из важнейших обновлений сети Биткоин, представленных в 2021 году: внедрение подписи Шнорра(BIP340), ставшей альтернативой подписи ECDSA, про которую мы уже рассказывали в одной из предыдущих статей. Данная подпись была введена в Биткоин вместе с протоколом Taproot, описанный в BIP341 и BIP342. В одной из следующих статей мы расскажем об этом протоколе, работающим в связке с подписью Шнорра. Сегодня же давайте остановимся подробнее на самой подписи и ответим на ряд вопросов:

• Чем плоха подпись ECDSA?
• Как работает подпись Шнорра?
• В чём преимущества подписи Шнорра?
• Что дало Биткоину введение подписи Шнорра?

Однако обо всём по порядку. Сначала ответим на первый вопрос и попытаемся понять, чем же всё-таки плоха подпись ECDSA, столько лет служившая Биткоину(да и не только ему) верой и правдой.

Недостатки подписи ECDSA.

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

1. Безопасность. Несмотря на такую долгую и надёжную историю использования подписи ECDSA, в отличие от подписи Шнорра, не обладает свойством сильной невозможности подделки при атаке по выбранному сообщению SUF-CMA (Strong Existential Unforgeability under Chosen Message Attack). Подпись ECDSA обладает лишь свойством EUF-CMA (Existential Unforgeability under Chosen Message Attack), которое является более слабой версией SUF-CMA. В частности, как нам известно, подпись ECDSA обладает свойством податливости(malleability), то есть, если (r,s) - действительная подпись сообщения M, то подпись (r,-s mod n) тоже будет приниматься как действительная подпись для сообщения M

2. Нелинейность и невозможность агрегирования. Ни для кого не секрет, что проблема масштабируемости является узким местом любого блокчейна. В случае с ECDSA эта проблема в особенности проявляется в контексте использования мультиподписи. Так, если мы хотим создать на базе ECDSA мультиподпись 2 из 2, нам придётся включить в скрипт Биткоин транзакции две подписи и два открытых ключа, что существенно повышает размер и цену транзакции. А представьте теперь, что нам понадобилось использовать подпись 5 из 5 или 8 из 8. Как мы увидим дальше, подпись Шнорра успешно борется с этим посредством своей линейности. К сожалению, ECDSA не обладает такими свойствами, что является серьёзным недостатком.

3. Податливость(Malleability). В отличие от подписи Шнорра, ECDSA подвержена проблеме податливости подписи, что в свою очередь приводит к проблеме податливости транзакций. Подробнее о том, что такое ковкость подписи и как с ней бороться, мы рассказывал в этой статье.

Подпись Шнорра.

Теперь поговорим о самой подписи Шнорра и о том как она устроена. Начнём с определением её параметров:

• E/𝔽ₚ - эллиптическая кривая над конечным полем 𝔽ₚ. При внедрении подписи Шнорра в Биткоин кривая не меняется и так же, как и для ECDSA, используется кривая secp256k1.
• G - группа точек эллиптической кривой E/𝔽ₚ с заданной операцией сложения точек.
• P - порождающая точка группы G=<P>, то есть любая точка D группы G может быть выражена через точку группы G как D=d·P.
• 𝒪 - бесконечно удалённая точка, играющая роль нейтрального элемента в группе G. Другими словами, для любой точки D группы G выполняется равенство D+𝒪=𝒪+D=D.
• n - порядок точки P, то есть n·P=𝒪.
• H - некоторая криптографическая хэш-функция, например, SHA256.
• a∊{2,...,n-1} - секретный ключ.
• A=a·P =(x₁,y₁)- открытый ключ.
• M - сообщение.

Теперь рассмотрим алгоритмы подписания и проверки подписи Шнорра.

Алгоритм генерации подписи:

1. Выбирается случайное число k, такое что 1<k<n.

2. Вычисляется точка R=k·P=(x,y).

3. Вычисляется хеш-значение e=H(x||x₁||M).

4. Вычисляется s=k-a·e mod n.

5. Подписью является пара sign=(x,s).

Алгоритм проверки подписи:

1. Вычисляется точка R'=s·P.

2. Вычисляется e=h(x||x₁||M).

3. Если R-R'=e·A, то подпись принимается. В противном случае подпись отклоняется

Корректность:

R'=s·P=(k-de)·P=k·P-e·(a·P)=R-e·A то есть e·A=R-R'

Преимущества подписи Шнорра по сравнению с подписью ECDSA.

• Безопасность. Подпись Шнорра обладает свойством SUF-CMA, что, в свою очередь, показывает, что в отличие от ECDSA, подпись Шнорра не обладает свойством податливости.
• Линейность. Подпись Шнорра предоставляет возможность создания агрегированной подписи, проверяемой агрегированным открытым ключом. То есть, например, у нас есть два пользователя U₁ и U₂, обладающие ключевыми парами (a₁,P₁=a₁·P) и (a₂,P₂=a₂·P) соответственно. С помощью своих секретных ключей a₁ и a₂ эти пользователи генерируют подписи sig₁ и sig₂. Тогда агрегированная подпись sig вычисляется как sig₁+sig₂, а проверяться она будет с помощью агрегированного открытого ключа P=P₁+P₂.
• Размер подписи и открытого ключа. Подпись Шнорра немного выигрывает как по размеру самой подписи, так и открытого ключа. Открытый ключ подписи Шнорра в BIP-340, в отличие от подписи ECDSA, не требует дополнительного байта, позволяющего определить, какая точка A=(x,y) или -A=(x,-y) является открытым ключом. Это происходит из-за того, что в BIP-340 зафиксировано, что открытыми ключам рассматриваются только точки с чётной y координатой. Заметим, что так как кривая secp256k1 определена над полем 𝔽ₚ, где p - большое простое число(>2), то p является нечетным числом. Тогда, если y - чётное число, то -y mod p=p-y - не чётное число. Аналогично, если y - не чётное число, то -y mod p=p-y - чётное число.

• Конфиденциальность и выигрыш по размеру при использовании мультиподписи n-из-n. Главное достоинство подписи Шнорра напрямую вытекает из свойства линейности. В случае подписи ECDSA в Биткоине, мультиподпись n-из-n представляет собой n обычных подписей, созданных с помощью n секретных ключей и проверяющихся с помощью n соответствующих открытых ключей. Поэтому в скриптах при использовании подписи ECDSA мы увидим n обычных подписей и n открытых ключей. В случае подписи Шнорра мы агрегируем n подписей в одну, складывая их. Аналогично, складывая n соответствующих открытых ключей, мы получим один агрегированный открытый ключ. Это определяет два больших плюса подписи Шнорра: большая экономия по размеру при использовании подписи Шнорра для построения мультиподписи и лучшая конфиденциальность пользователей. Если с первым всё очевидно, мультиподпись n-из-n на базе подписи Шнорра будет более чем в n раз меньше чем аналогичная мультиподпись, построенная на базе подписи ECDSA. То второй плюс требует пояснение. Дело в том, что при кластеризации адресов пользователей и дальнейшей их идентификации одним из определяющих факторов может быть паттерн скриптов, используемых адресами конкретного пользователя. Например, необычная мультиподпись, скажем, 4-из-4. В случае подписи Шнорра, агрегированная подпись и агрегированный ключ для внешнего наблюдателя будут выглядеть как обычная подпись и обычный открытый ключ подписи Шнорра, что не позволит определить факт наличия в скриптах, используемых адресами определённого пользователя, мультподписи и её структуры.

Таким образом, повышается уровень конфиденциальности пользователя. Однако заметим, что одной подписи Шнорра для этого недостаточно. Так, например, скрипты, связанные с протоколом Lightning Network, используют мультиподпись, и структура этих скриптов общеизвестна. Поэтому, если внешний наблюдатель увидеть скрипт, один в один повторяющий скрипт, используемый в протоколе Lightning Network, но при этом содержащий обычную подпись, он может сделать вывод, что на самом деле в этом скрипте используется мультиподпись, агрегированная за счёт свойства линейности подписи Шнорра. На практике данную проблему решает протокол Taproot, представленный в BIP-341 и введённый одновременно с BIP-340. Можно сказать, что данные предложения(BIP-340,BIP-341) дополняют друг друга и совместно повышают уровень конфиденциальности пользователя в контексте используемых скриптов.

Таким образом, сегодня мы рассмотрели подпись Шнорра, её отличия
и преимущества перед ECDSA. Заметим, что наше описание подписи Шнорра, мы не поднимали отдельные детали её реализации в BIP-340. Кроме того, мы
опустили описание построения и проверки пороговой подписи k-из-n, где k<n(при k=n мы получаем мультиподпись n-из-n) на базе подписи Шнорра в Биткоине. К этим вопросам, мы ещё вернёмся в одной из следующих статей, когда будем говорить о протоколе Taproot. Поэтому оставайтесь на нашем канале, и Вы узнаете ещё больше о Биткоине и других криптовалютах.