MuSig: Новый стандарт мультиподписи
Blockstream Research

MuSig: Новый стандарт мультиподписи

Andrew Poelstra

Биткоин и связанные с ним блокчейны, такие как Liquid от Blockstream, используют алгоритм подписи ECDSA для верификации владенияи перевода монет, хранящихся в системе. Это было техническое решение, осуществленное   в 2008, на основании находящихся в широком использовании и незапатентованных систем цифровых подписей, существующих на тот момент. Однако у ECDSA наблюдается ряд серьезных технических ограничений. В частности, мультиподписи и пороговые (threshold) подписи – это подписи, которые создаются кворумом независимых сторон, а не одним человеком, – и их очень трудно создать при помощи ECDSA. У подписей ECDSA сложная алгебраическая структура, которая делает их негибкими и сложными в работе, заставляя разработчиков использовать Биткоин Скрипт для таких приложений, как кросс-чейн атомарные свопы или Lightning, которые можно реализовать более компактно и конфиденциально  при помощи схемы гибких подписей.

При том, что уровень развития цифровых подписей значительно продвинулся с 2008 года, в альтернативных схемах цифровых подписей, описанных в различных публикациях, игнорируется множество практических требований, которые необходимо учитывать для их применения на практике. В частности, в этих схемах часто предполагается, что подписанты имеют полный контроль над тем, как и когда эти ключи генерируются; что у них всегда есть доступ к ‘генерации полной случайности’; что у них есть постоянная, надежная и защищенная память. На деле пользователи Биткоин часто имеют ограниченный доступ к собственным ключам, они мало контролируют конкретный механизм генерирования ключей и не имеют никакого контроля над тем, каким образом внешние стороны используют генерируемые ими адреса. Чтобы разрешить эту проблему, мы запустили инициативу по созданию новой схемы подписей и приложили много инженерных усилий для ее надежной реализации..

Вступление

В первой половине прошлого года мы с криптографом Blockstream Питером Велле (Pieter Wuille) совместно с Янником Сеурином (Yannick Seurin) и Грегори Максвеллом (Gregory Maxwell) опубликовали новую схему мультиподписи под названием MuSig. Этой схемой мультиподписи обеспечивается доказуемая безопасность даже от вступивших в сговор подписантов-злоумышленников, и создаются подписи, которые невозможно отличить от обыкновенных подписей Шнорра с одним подписантом.

С тех пор мы превратили MuSig из академической статьи в пригодный для использования код, и на этой неделе мы совместили этот код с secp256k1-zkp, форком secp256k1, надежной криптографической библиотекой, которую использует Bitcoin Core и которую мы расширили, добавив поддержку конфиденциальных транзакций (Confidential Transaction) для Elements и Liquid.

Поскольку Биткоин-сообщество исследует применение подписей Шнорра в Биткоин, мы надеемся, что наш код в результате будет объединен с библиотекой secp256k1, использующейся Bitcoin Core и множеством других проектов.

Наш код создает подписи, совместимые с BIP-schnorr, а также может создавать переходные подписи (‘adaptor signatures’), которые могут включать Lightning в бесскриптовом скрипте  (‘scriptless script’)

Зачем нужен MuSig?

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

  1. Короткие подписи постоянного размера, которые выглядят одинаково для верификаторов независимо от набора подписантов. В блокчейн-системе скорость проверки является наиболее важным фактором, и нет смысла загружать верификаторов сведениями о составе подписантов больше, чем необходимо для предотвращения кражи. Еще одно преимущество состоит в том, что подписи MuSig повышают уровень конфиденциальности, поскольку скрывают конкретную политику подписанта.
  2. Доказуемая безопасность простой модели открытого ключа. Это означает, что подписанты могут свободно участвовать в мультиподписи при помощи обыкновенных пар ключей, без необходимости предоставлять дополнительную информацию о конкретных способах, которыми эти ключи создаются или контролируются. Информацию о генерировании ключей может быть достаточно сложно предоставить в контексте Биткоин, так как у различных подписантов различные правила управления ключами с различным набором ограничений. Кроме зависимости от генерирования ключей, эта информация может плохо взаимодействовать с Taproot, предлагаемым расширением Биткоин, в котором в открытых подписных ключах может кодироваться дополнительная семантика.

Кроме того, со времени сообщения о создании MuSig, мы узнали, что во множестве опубликованных схем подписей, включая ранее неопубликованную версию MuSig, на самом деле не обеспечивается безопасность! Этот вопрос мы изучим отдельно в другом блоге, а пока что достаточно сказать, что нам предстоит проделать много работы для того, чтобы разработать схему мультиподписи, подходящую для Bitcoin и Liquid.

Подводные камни и разработка безопасного API

Как и в отношении всех математических описаний протоколов мультиподписи, опубликованная версия MuSig предполагает, что в течение всего процесса подписания у участников есть доступ к устойчивой, легко обновляемой памяти, не поддающейся ‘возвращению’ в предыдущее состояние злоумышленниками. Также предполагается, что подписанты имеют доступ к источникам случайности, неотличимым от равномерно распределенных. К сожалению, реальный мир не такой простой, и мы потратили много энергии на разработку API, который можно было бы использовать в самых разных сценариях без возникновения ситуаций, когда  ограничения оборудования или несформулированные предположения приведут к потере секретных ключей.

При создании подписей MuSig, таких как подписи Шнорра или ECDSA, используется секретное однократно используемое число (ОИЧ) (nonce), которое должно создаваться случайным образом. Любое отклонение от однородности, даже на один бит, может привести к потере секретного ключа или краже денег.

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

Однородная случайность

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

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

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

К решению последнего момента – невозможности проверки – существуют некоторые творческие подходы, которые мы изучим в следующем посте. А пока мы решили запрашивать от пользователей API предоставления уникального номера сеанса для каждого сеанса подписей. ОИЧ создаются при помощи хеширования секрета подписанта, набора подписантов, подлежащего подписи сообщения, и, наконец – этого уникального ввода в текущий сеанс. Пользователи с доступом к генератору случайных чисел могут использовать его для создания ID сеансов, а те, которые имеют доступ к постоянной памяти могут просто воспользоваться счетчиком.

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

Атаки повторного воспроизведения

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

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

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

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

Для защиты подписантов, которые могут сериализировать устаревшее состояние и перезапуститься из него, наш API просто не поддерживает сериализацию сеансов подписи.

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

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

Заключение и дальнейшее развитие событий

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

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

В будущем мы также обсудим некоторые некоторые методы, позволяющие сделать случайность ОИЧ более безопасной и более проверяемой.. В частности, при помощи приема под названием sign-to-contract хост может исключить возможность возникновения смещения со стороны неблагонадежного генератора случайных чисел аппаратного кошелька.

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

Мы рады этой возможности; будем делиться результатами нашей работы по мере их разработки.

Наш код находится в открытом доступе на GitHub; предлагаем с ним попрактиковаться и предоставить отзывы!

If you have specific preferences, please, mark the topic(s) you would like to read: