Обмен электронных валют по самому выгодному курсу!
 


Kurbetsoft
Доступно в Google PlayBLS-подписи: лучшая альтернатива подписям Шнорра

Настоящая статья посвящена подписям Боне – Линна – Шахама (BLS) и их замечательным свойствам, невозможным в подписях Шнорра. Напомним, ровно год назад мы публиковали подробную статью, посвящённую подписям Шнорра, с которой желательно ознакомиться перед тем, как читать сегодняшнюю статью.

Вкратце, что мы знаем на данный момент:

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

Подписи Шнорра великолепны – при правильном подходе можно скомбинировать все подписи и публичные ключи транзакции в один ключ и одну подпись, и никто не узнает, что они соответствуют нескольким ключам. Также валидация блока может проходить быстрее – можно проверить все подписи сразу. Однако есть несколько проблем:

  • Схема мультиподписи требует нескольких коммуникационных циклов. Это может быть очень неудобно в случае холодного хранения.
  • При агрегировании подписей мы вынуждены полагаться на генератор случайных чисел – мы не можем выбрать случайную точку R детерминистически, как в случае ECDSA.
  • Схема мультиподписи m-из-n имеет сложности – необходимо создать дерево Меркла для публичных ключей, которое может быть достаточно большим при больших m и n.
  • Невозможно скомбинировать все подписи блока в одну.

BLS-подписи способны решить всё вышеперечисленное. Случайные числа вообще не нужны; все подписи блока можно скомбинировать в одну; мультиподписи m-из-n очень просты; и нет необходимости в нескольких коммуникационных циклах между подписантами. Кроме того, BLS-подписи в два раза короче подписей Шнорра и ECDSA – подпись представляет собой не пару, а единственную точку на кривой. Звучит впечатляюще! Давайте рассмотрим, как это работает.

Магия BLS-подписей

Прежде всего, нужны две новые конструкции – хеширование в кривую и спаривание кривых.

Хеширование в кривую

Обычно в случае подписей ECDSA и Шнорра мы хешируем сообщение и используем этот хеш в алгоритме подписи как число. Для BLS-подписей нужен слегка модифицированный алгоритм, хеширующий непосредственно в эллиптическую кривую. Самый простой способ – хешировать сообщение как обычно и рассматривать результат как x-координату точки. Эллиптические кривые (вроде используемой в Биткойне) обычно имеют порядка 2 точки в 256 степени, и алгоритм хеширования SHA-256 также даёт 256-битный результат. Но для каждой валидной x-координаты есть две точки с положительной и отрицательной y-координатой (потому что если (x,y) находится на кривой y²=x³+ax+b, то (x,-y) также находится на кривой). Это значит, что наш хеш может с вероятностью примерно 50% найти две точки для некоторого x и с вероятностью 50% не найти ни одной.

Пример хеширования в эллиптическую кривую y²=x³+7, заданную в конечном поле по модулю 23. Только половина всех x-координат имеет точки. Здесь только третья попытка увенчалась успехом.

Чтобы найти точку для любого сообщения, можно попытаться хешировать несколько раз, присоединяя к сообщению число и увеличивая его в случае неудачи. Если hash(m||0) не находит точку, мы пробуем hash(m||1)hash(m||2) и т. д., пока не найдём подходящий результат. Затем достаточно выбрать одну из двух соответствующих точек, например с меньшим y.

Спаривание кривых

Нам также нужна особая функция, которая берёт две точки P и Q на кривой (или на двух разных кривых) и сводит их к числу:

e(P, Q) → n

От этой функции также требуется одно важное свойство. Если у нас есть некоторое секретное число x и две точки P и Q, то мы должны получить одинаковый результат независимо от того, какую точку умножить на это число:

e(x×P, Q) = e(P, x×Q)

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

e(a×P, b×Q) = e(P, ab×Q) = e(ab×P, Q) = e(P, Q)^(ab)

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

Важно заметить, что мы не можем здесь использовать любую эллиптическую кривую (в частности, стандартная кривая Биткойна secp256k1 не подойдёт). Чтобы сделать функцию эффективной и безопасной, нужно использовать особые кривые из «дружественного к спариванию» семейства.

Схема BLS-подписи

Теперь у нас есть всё необходимое для построения BLS-подписи. Наш приватный ключ – это некое секретное число pk, публичный ключ – P = pk×G , а подписываемое сообщение – m.

Чтобы вычислить подпись, мы хешируем наше сообщение в кривую H(m) и умножаем результирующую точку на наш приватный ключ: S = pk×H(m). Вот и всё! Больше ничего – ни случайных чисел, ни дополнительных операций, только хеш умножить на приватный ключ! Наша подпись – это просто одна точка на кривой, занимающая всего 33 байта в сжатом формате сериализации!

Генерирование BLS-подписи. Чтобы получить подпись, мы умножаем хеш сообщения на приватный ключ.

Чтобы верифицировать эту подпись, можно взять наш публичный ключ P и проверить условие:

e(P, H(m)) = e(G, S)

Оно истинно благодаря замечательному свойству описанной выше функции спаривания:

e(P, H(m)) = e(pk×G, H(m)) = e(G, pk×H(m)) = e(G, S)

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

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

Агрегирование подписей

Давайте скомбинируем все подписи блока! Представим, что у нас есть блок с 1000 транзакций и каждая транзакция содержит подпись Si, публичный ключ Pi и подписываемое сообщение mi. Зачем хранить все подписи, если их можно объединить? В конце концов, нам важно лишь, чтобы все подписи блока были действительными. Агрегированная подпись будет представлять собой всего лишь сумму всех подписей блока:

S = S1+S2+…+S1000

Чтобы верифицировать блок, нужно проверить, выполняется ли следующее равенство:

e(G, S) = e(P1, H(m1))⋅e(P2, H(m2))⋅…⋅e(P1000, H(m1000))

Если присмотреться, то можно увидеть, что оно действительно выполняется:

e(G, S) = e(G, S1+S2+…+S1000) = e(G, S1)⋅e(G, S2)⋅…⋅e(G, S1000) = e(G, pk1×H(m1))⋅…⋅e(G, pk1000×H(m1000)) = e(pk1×G, H(m1))⋅…⋅e(pk1000×G, H(m1000)) = e(P1, H(m1))⋅e(P2, H(m2))⋅…⋅e(P1000, H(m1000))

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

Агрегирование ключей и мультиподпись n-из-n

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

Простой способ их скомбинировать – сложить все подписи и ключи. В результате получим подпись S=S1+S2+S3 и ключ P=P1+P2+P3. Легко увидеть, что действительно всё то же уравнение для верификации:

e(G, S) = e(P, H(m))

e(G, S) = e(G, S1+S2+S3) = e(G, (pk1+pk2+pk3)×H(m)) = e((pk1+pk2+pk3)×G, H(m)) = e(P1+P2+P3, H(m)) = e(P, H(m))

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

S = a1×S1+a2×S2+a3×S3

P = a1×P1+a2×P2+a3×P3

Здесь коэффициенты подписей и ключей вычисляются детерминистически из публичного ключа подписанта и всех остальных публичных ключей:

ai = hash(Pi, {P1,P2,P3})

Например, это может быть просто конкатенация публичного ключа подписанта и всего множества публичных ключей, используемых для подписи: ai = hash(Pi||P1||P2||P3).

По-прежнему действительно то же уравнение для верификации. В доказательстве будут дополнительные коэффициенты ai, но логика остаётся той же.

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

Схема мультиподписи подгруппы (мультиподпись m-из-n)

Часто мы не хотим использовать схему мультиподписи n-из-n, а предпочитаем m-из-n, например 2-из-3. Мы не хотим потерять все деньги только потому, что потеряли один из ключей. Было бы замечательно использовать в таком сценарии агрегирование ключей. В случае подписей Шнорра это возможно с помощью дерева Меркла для публичных ключей. Это не самый эффективный, но действенный способ. К сожалению, при больших значениях m и n размер дерева Меркла растёт экспоненциально.

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

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

Фаза настройки

Каждое из наших устройств имеет номер подписанта i = 1,2,3, обозначающий его место во множестве, приватный ключ pki и соответствующий публичный ключ Pi = pki×G. Мы рассчитываем агрегированный публичный ключ точно так же, как раньше:

P = a1×P1+a2×P2+a3×P3, ai = hash(Pi, {P1,P2,P3})

Теперь каждое устройство должно с помощью подписи подтвердить, что номер i входит в наш агрегированный публичный ключ (для каждого i), подписи должны быть агрегированы и результат сохранён на соответствующем устройстве:

MKi = (a1⋅pk1)×H(P, i)+(a2⋅pk2)×H(P, i)+(a3⋅pk3)×H(P, i)

Эту подпись мы будем называть «ключом участия», и она будет использоваться позже. Каждый ключ участия – это действенная подпись n-из-n сообщения H(P,i). Это значит, что:

e(G, MKi)=e(P, H(P,i))

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

Подпись

Допустим теперь, что мы хотим подписать транзакцию только ключами pk1 и pk3. Генерируем две подписи S1 и S3:

S1 = pk1×H(P, m)+MK1, S3=pk3×H(P, m)+MK3

и слагаем их, чтобы получить одну подпись и ключ:

(S’, P’) = (S1+S3, P1+P3)

Я пишу здесь P’ и S’, чтобы подчеркнуть, что эти ключ и подпись подписаны только подмножеством подписантов и это не тот же агрегированный ключ P для всех подписантов. Чтобы верифицировать эту подпись 2-из-3, нужно проверить условие:

e(G, S’) = e(P’, H(P, m))⋅e(P, H(P, 1)+H(P, 3))

Мы помним, что ключи участия MK1 и MK3 – это действительные подписи для сообщений H(P, 1) и H(P, 3), подписанных агрегированным ключом P, поэтому:

e(G, S’) = e(G, S1+S3)=e(G, pk1×H(P, m)+pk3×H(P, m)+MK1+MK3) =e(G, pk1×H(P, m)+pk3×H(P, m))⋅e(G, MK1+MK3)=e(pk1×G+pk3×G, H(P, m))⋅e(P, H(P, 1)+H(P, 3))=e(P’, H(P, m))⋅e(P, H(P, 1)+H(P, 3))

Вот и всё. Чуть сложнее, чем n-из-n, но всё же понятно.

Возможная реализация

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

OP_2

OP_CHECK_BLS_MULTISIG

Здесь OP_2 говорит, что требуется два ключа для подписи сообщения. Мы нигде не говорим, что всего есть 3 подписанта, так что никто не может сказать, идёт ли речь о мультиподписи 2-из-3 или 2-из-100. Позже мы также не раскрываем эту информацию.

Чтобы расходовать этот выход, необходимо предоставить ключ P’, подпись S’ и индексы участвующих подписантов – в нашем случае числа 1 и 3. Сценарий разблокировки может выглядеть так:

OP_1 OP_3

Комбинация этих сценариев даёт нам всю необходимую информацию. OP_1 и OP_3 говорят нам, что нужно вычислить хеши H(P, 1) и H(P, 3), после чего у нас есть всё необходимое, чтобы верифицировать транзакцию.

Следовательно, для любых m и n достаточно:

  • одного агрегированного публичного ключа P в сценарии блокировки;
  • одного агрегированного публичного ключа участвующих подписантов P’;
  • одной агрегированной подписи S’;
  • m чисел с индексами подписантов.

Очень компактно и красиво!

Лишь одно мне здесь не нравится… Обычно мы используем адреса лишь единожды – мы генерируем новые приватные ключи и адреса с помощью таких методов, как BIP32. Но для каждого нового множества приватных ключей также нужно множество новых ключей участия. Один способ реализовать это без повторения каждый раз фазы настройки – это сгенерировать большое количество ключей, например 1000, и получить соответствующие ключи участия. В конце концов, их длина всего 32 байта. Тогда нам придётся повторить фазу настройки только после использования всей 1000 адресов.

Недостатки

Из вышеизложенного может показаться, будто BLS-подписи идеальны. Но это не так. Мы не учитывали сложность спаривания и рассматривали нашу волшебную функцию e(P, Q) как эффективную и безопасную. Это не совсем так.

Спаривание не так эффективно

Верификация BLS-подписей на несколько порядков сложнее, чем в случае ECDSA. Агрегирование подписей всей 1000 транзакций блока требует вычисления 1000 спариваний, поэтому на верификацию одной небольшой подписи блока может понадобиться больше времени, чем на верификацию 1000 отдельных подписей ECDSA. Единственное достигаемое преимущество – возможность поместить в блок больше транзакций, так как агрегированная подпись занимает лишь ~32 байта.

В отличие от BLS-подписей, подписи Шнорра очень эффективны – их можно валидировать все вместе, и этот процесс в три раза эффективнее, чем в случае ECDSA. Вопрос лишь в том, что для нас важнее.

Доказательство безопасности сложнее

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

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

В завершение

BLS-подписи поразительны: можно комбинировать все подписи блока в одну; можно использовать агрегирование ключей и схему мультиподписи m-из-n без дополнительных коммуникационных циклов; не нужно полагаться на генераторы случайных чисел; и сама схема кажется очень простой и красивой. Тем не менее ещё есть над чем работать, и на стандартизацию и оптимизацию понадобится некоторое время. Но я надеюсь, что когда-нибудь этот алгоритм подписей станет достаточно хорошим для включения в протокол Биткойна и мы сможем использовать все эти замечательные свойства меньших и лучше агрегируемых подписей.

Источник




[vkontakte] [facebook] [twitter] [odnoklassniki] [mail.ru] [livejournal]

Каталог сайтов