Когда подписи Шнорра станут частью Биткойна, можно ли будет проверять каждый блок только одной проверкой подписи?

В недавнем докладе Питер Вуилле рассказал об ускорении проверки при использовании подписей Шнорра и различных алгоритмах проверки нескольких подписей.

Действительно ли возможно проверить один единственный блок, объединив ключи и подписи всех транзакций? (Теоретически даже больше транзакций в нескольких блоках)

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

(Оставляя в стороне политику радикальных изменений протокола) Можем ли мы даже сэкономить больше места, если примем заголовок блока, чтобы включить одну совокупную подпись Шнорре для блока и исключить все подписи Шнорра отдельных транзакций в этом блоке?

Я что-то пропустил? В докладе не было подробностей, а лишь упоминалась идея.

Ответы (1)

Да, одна проверка на блок, но не одна подпись на блок.

Чтобы устранить путаницу, здесь задействованы 3 различные технологии:

  • (1) неинтерактивная агрегация — это возможность третьей стороны (у которой нет закрытых ключей) объединять несколько подписей, каждая со своим сообщением и открытым ключом, в единую подпись, которую может проверить тот, кто знает все сообщения и открытые ключи.
  • (2) интерактивная агрегация — то же самое, но когда подписавшие должны знать об агрегации и общаться друг с другом для совместного создания единой подписи.
  • (3) пакетная проверка — это возможность верификатора проверить, являются ли несколько кортежей (публичный ключ, сообщение, подпись) действительными или нет, быстрее, чем проверка отдельных подписей. Если один или несколько кортежей недействительны, в этом случае верификатор не узнает, какие именно.

Подписи Шнорра (и любые другие известные схемы подписи на основе дискретного логарифма) поддерживают (2) и (3), но не (1).

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

Из-за (2) лучшее, на что мы можем надеяться (пока мы ограничены подписями на основе DL), — это одна подпись на транзакцию. Даже для этого требуется перекрестная агрегация входных данных, которая имеет сложности, помимо реализации подписей Шнорра в цепочке (см., например, этот пост ).

Однако из-за (3) правильно, что может быть одна проверка на блок, но не одна подпись на блок. Ускорение, которое возможно благодаря пакетной проверке, на самом деле становится нетривиальным. Каждая из 4 строк представляет собой метод оптимизации, который в настоящее время реализован в libsecp256k1, который выбирает лучший вариант в зависимости от размера проблемы и ограничений памяти.

Ускорение пакетной проверки

(*) Существует форма неинтерактивной «полуагрегации» для подписей на основе DL, при которой N подписей могут быть неинтерактивно объединены в одну подпись размером (1+N)/2 исходных подписи. Это можно использовать для блоков, хотя выгода не так велика, и есть сложности, связанные с агрегацией всего блока, которые делают ее менее интересной.

Думаю, мне нужно снова прочитать подробности, но разве идея простой модели открытого ключа и конструкции musig не заключалась в том, чтобы неинтерактивная агрегация стала возможной? Или я должен был попросить подписи musig? Я думал, что musig — это именно та схема, которая в настоящее время предназначена для использования, когда люди говорят о schnorr. Пока не отмечайте как правильный, так как у меня все еще есть открытые вопросы (вероятно, это моя вина)
MuSig допускает неинтерактивную настройку — подписание остается интерактивным.
И MuSig — это лишь одна из вещей, которую кошелек может использовать, когда существует проверка Шнорра в цепочке (поскольку подписи, полученные в результате подписания MuSig, совместимы с верификатором Шнорра). Существуют конструкции (интерактивная установка), которые позволяют вам построить k-of-n, например, с одним ключом или даже с произвольными и/или комбинациями участников.
«Существует форма неинтерактивной «полуагрегации» для подписей на основе DL, где N подписей могут быть неинтерактивно объединены в одну подпись размером (1+N)/2 исходных подписи». -- Нельзя ли повторить это за O(log(N)) итераций?
@Martin Schwarz Что вы подразумеваете под повторением? Конструкция (для Шнорра) состоит в том, что вы объединяете (R1,s1),..., (Rn,sn) в (R1,...,Rn,s), где s = H(L,1)*s1 + . .. + H(L,n)*sn и L = H(R1,...Rn,P1,...,Pn,m1,...,mn), Pi — открытые ключи, mi — сообщения .
Ага, понятно. Хорошо, это не работает.
Только сегодня увидел - очень красивая фигурка, почему бы не включить в бип-шнорр?
Когда подписи Шнорра станут частью Биткойна, можно ли будет проверять каждый блок только одной проверкой подписи?
СпросиСетьПолитика конфиденциальности1y, 0v