ColliderScript: Как ковенанты в Bitcoin могут работать без новых опкодов и стоимостью 50 миллионов долларов

ColliderScript: Ковенант на Bitcoin стоимостью 50 миллионов долларов без новых опкодов

За последние пару лет было предложено множество идей касаемо расширений для ковенантов в Bitcoin, однако у экспертов всегда оставалось сомнение, что ковенанты могут быть реализованы и без таких расширений. Доказательства этого пришли в двух формах: расширяющийся репертуар ранее невообразимых вычислений в Script (который culminates в проекте BitVM по внедрению каждого опкода RISC-V) и ряд `почти успешных попыток`, с помощью которых разработчики Bitcoin нашли способы, которые могли бы позволить ковенанты, если бы не какие-то неясные исторические особенности системы.

Этан Хайлман, Авиу Леви, Виктор Коболов и я разработали схему, которая подтверждает, что это подозрение было обоснованным. Наша схема, ColliderScript, позволяет использовать ковенанты в Bitcoin уже сегодня, при довольно разумных криптографических предпосылках и вероятной стоимости около 50 миллионов долларов за транзакцию (плюс некоторые расходы на исследования и разработки оборудования).

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

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

Ковенанты

Контекст этой дискуссии, для тех, кто незнаком, заключается в том, что Bitcoin имеет встроенный язык программирования, называемый Bitcoin Script, который используется для авторизации расходов монет. В свои ранние дни Script содержал богатый набор арифметических опкодов, которые можно было использовать для реализации произвольных вычислений. Но летом 2010 года Сатоши отключил многие из них, чтобы устранить ряд серьезных ошибок. (Возврат к вариантам Script до 2010 года является целью проекта Великой Реставрации Script; OP_CAT является менее амбициозным предложением в том же направлении.) Идея ковенантов — транзакций, которые используют Script для контроля за количеством и направлением их монет — не появлялась еще несколько лет, и осознание того, что эти опкоды были бы достаточны для реализации ковенантов, пришло еще позже. К тому времени сообщество стало слишком большим и осторожным, чтобы просто `включать` старые опкоды так же, как они были отключены.

Ковенанты — это гипотетические конструкции Script, которые позволили бы пользователям контролировать не только условия, при которых монеты тратятся, но и их направление. Это основа для многих предполагаемых конструкций на Bitcoin — от сейфов и ограниченных по количеству кошельков до новых механизмов сборов, таких как платежные пулы, и менее желательных конструкций, таких как децентрализованные финансы и MEV. На обсуждение desirability ковенантов было потрачено миллионы слов, и обсуждалось, как они изменят природу Bitcoin.

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

История

На протяжении многих лет развилась традиция находить творческие способы делать нетривиальные вещи, даже с ограниченным Script. Lightning Network была одним из таких случаев, как и менее известные идеи, такие как вероятностные платежи или вознаграждения за коллизии для хеш-функций. Неясные пограничные случаи, такие как ошибка SIGHASH_SINGLE или использование восстановления открытого ключа для получения `хеш-транзакции` в интерпретаторе Script, были замечены и исследованы, но никто не нашел способа сделать их полезными. Тем временем Bitcoin сам эволюционировал, становясь более четко определенным, и закрывая многие из этих дверей.

Несмотря на эти изменения, хакинг Script продолжался, как и вера среди ярых сторонников, что каким-то образом может быть найден какой-то крайний случай, который позволит поддерживать ковенанты в Bitcoin. В начале 2020-х годов два принципиальных события произвели фурор. Одним из них было мое собственное открытие, что основанные на сигнатурe ковенанты не исчезли с восстановлением открытых ключей, и что, в частности, если бы у нас был хотя бы один отключенный опкод — OP_CAT — этого было бы достаточно для достаточно эффективной конструкции ковенанта. Вторым событием был BitVM, новый способ выполнения больших вычислений в Script через множество транзакций, который вдохновил огромное количество исследований базовых вычислений в рамках одной транзакции.

Эти два события вдохновили много активности и восторга вокруг ковенантов, но они также кристаллизовали наши мысли о фундаментальных ограничениях Script. В частности, показалось, что ковенанты могут быть невозможны без новых опкодов, поскольку данные транзакции вводятся в Script только через 64-байтовые сигнатуры и 32-байтовые открытые ключи, в то время как опкоды, поддерживающие BitVM, могут работать только с 4-байтовыми объектами. Это разделение было обозначено как `Маленький Script` и `Большой Script`, и поиск моста между этими двумя стал синонимичным (по крайней мере, в моем понимании) поиску конструкции ковенанта.

Функциональное шифрование и PIPE

Также было замечено, что с помощью немного непростой математики можно полностью реализовать ковенанты внутри самих сигнатур, не покидая Большой Script. Эта идея была сформулирована Джереми Рубином в его статье о ковенантах, основанных на функциональном шифровании. Спустя несколько месяцев Миша Коморов предложил конкретную схему под названием PIPEs, которая, по всей видимости, делает эту гипотетическую идею реальностью.

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

ColliderScript

Этот обзор приводит нас к текущей ситуации: мы хотели бы найти способ реализовать ковенанты, используя существующую форму Bitcoin Script, и мы считаем, что это можно сделать, найдя некоторый мост между `Большим Script` транзакционных сигнатур и `Маленьким Script` произвольных вычислений. Похоже, что ни один опкод не может непосредственно образовать этот мост (см. Приложение A к нашей статье для классификации всех опкодов по их размеру ввода и вывода). Мост, если он существует, был бы какой-то конструкцией, которая взяла бы один большой объект и доказала бы, что он точно равен конкатенации нескольких маленьких объектов. Похоже, согласно нашей классификации опкодов, это невозможно.

Однако в криптографии мы часто ослабляем понятия, такие как `точно равно`, вместо этого используя понятия `компьютерно неотличимо` или `статистически неотличимо`, и таким образом избегаем результатов невозможности. Возможно, используя встроенные криптографические конструкции Большого Script — хеши и сигнатуры эллиптической кривой — и отражая их, используя конструкции BitVM в Маленьком Script, мы могли бы найти способ показать, что большой объект `компьютерно неотличим` от серии маленьких? С помощью ColliderScript мы именно это и сделали.

Что это значит? Ну, вспомним о вознаграждении за коллизию хеш-функции, о которой мы упоминали ранее. Предположение этого вознаграждения в том, что любой, кто может `коллизировать` хеш-функцию, предоставляя два ввода, имеющих одинаковый хеш-выход, может доказать это в Большом Script и таким образом требовать вознаграждение. Поскольку пространство ввода хеш-функции гораздо больше (все байтовые строки размером до 520 байт), чем пространство выхода (байтовые строки точно 32 байта), с математической точки зрения должно быть много таких коллизий. И все же, за исключением SHA1, никто не нашел более быстрого способа нахождения этих коллизий, чем просто повторно вызывать хеш-функцию и смотреть, совпадает ли результат с ранней попыткой.

Это означает, что в среднем для хеш-функции 160 бит, такой как SHA1 или RIPEMD160, пользователю потребуется выполнить по крайней мере 2^80 работы, или миллион миллионов миллионов миллионов итераций, чтобы найти коллизию. (В случае SHA1 существует короткий путь, если пользователь может использовать вводы определенной формы; но наша конструкция запрещает это, так что для наших целей мы можем игнорировать эту атаку.) Это предполагает, что у пользователя есть эффективно бесконечное количество памяти для работы; с более реалистичными предположениями нам нужно добавить еще один фактор где-то сто.

Если мы представим, что SHA1 и RIPEMD160 могут быть вычислены так же эффективно, как вычисляет Bitcoin ASICs SHA256, тогда стоимость такого вычисления будет примерно равна 200 блокам, или около 625 BTC (46 миллионов долларов). Это много денег, но многие люди имеют доступ к такой сумме, так что это возможно.

Чтобы найти тройную коллизию, или три ввода, которые оцениваются в одно и то же, потребуется около 2^110 работы, даже с очень щедрыми предположениями о доступе к памяти. Чтобы получить это число, нам нужно добавить еще один фактор 16 миллионов к нашей стоимости — что приводит нас к более чем 700 триллионов долларов. Это также много денег, и суммы, доступной для кого-то сегодня, нет.

Суть нашей конструкции заключается в следующем: чтобы доказать, что серия маленьких объектов эквивалентна одному большому объекту, мы сначала находим хеш-коллизию между нашим целевым объектом (который мы предполагаем, может быть перерандомизирован каким-то образом, иначе мы бы делали `поиск второго предобраза`, а не поиск коллизии, что было бы гораздо сложнее) и `объектом-тестером эквивалентности`. Эти объекты-тестеры эквивалентности конструктивным образом создаются так, чтобы их легко было манипулировать как в Большом Script, так и в Маленьком Script.

Наша конструкция затем проверяет в Bitcoin Script, что наш большой объект коллидирует с нашим объектом-тестером эквивалентности (используя точно те же методы, что и в вознаграждении за коллизию хеш-функции) и что наша серия маленьких объектов коллидирует с тестером эквивалентности (используя сложные конструкции, частично заимствованные из проекта BitVM и подробно описанные в статье). Если эти проверки пройдены, то либо наши маленькие и большие объекты были одинаковыми, либо пользователь нашел тройную коллизию: два разных объекта, которые оба коллидируют с тестером. По нашему аргументу, это невозможно.

Заключение

Соединение Маленького Script и Большого Script — самая трудная часть нашей конструкции ковенанта. Чтобы перейти от этого моста к настоящему ковенанту, необходимо сделать еще несколько шагов, которые сравнительно легки. В частности, скрипт ковенанта сначала запрашивает пользователя о подписании транзакции с помощью специального `генераторного ключа`, который мы можем проверить с помощью опкода OP_CHECKSIG. Используя мост, мы разбиваем эту сигнатуру на 4-байтовые кусочки. Затем мы проверяем, что ее nonce также равен генераторному ключу, что легко сделать, как только сигнатура разбита. Наконец, мы используем техники из трюка Шнора, чтобы извлечь данные транзакции из сигнатуры, которые затем можно ограничить любым способом, который требует ковенант.

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

Последнее применение, на которое я хочу обратить внимание, обсуждаемое вкратце в разделе 7.2 статьи, заключается в том, что мы можем использовать нашу конструкцию ковенанта, чтобы извлечь хеш транзакции из сигнатуры Шнора, а затем просто повторно подписать хеш, используя сигнатуру Лампорт.

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

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

Таким образом, если мы проснемся завтра и обнаружим, что существуют дешевые квантовые компьютеры, способные разрушить подписи Bitcoin, мы могли бы предложить экстренное мягкое форк, который отключил бы все сигнатуры эллиптической кривой, включая как расходование ключей Taproot, так и опкод OP_CHECKSIG. Это фактически заморозило бы монеты всех; но если альтернатива заключалась в том, что монеты каждого были бы свободно доступны для кражи, возможно, это бы не имело значения. Если бы это отключение сигнатурного мягкого форка позволило использовать опкод OP_CHECKSIG, когда он вызывается с генераторным ключом (такие подписи не обеспечивают никакой безопасности и полезны как строительный блок для сложных конструкций Script, таких как наша), тогда пользователи нашей конструкции сигнатуры Лампорт могли бы продолжать свободно расходовать свои монеты, не опасаясь ареста или кражи.

Конечно, им придется потратить десятки миллионов долларов на это, но это гораздо лучше, чем `невозможно`! И мы ожидаем и надеемся, что эта стоимость будетdramatically снижена, так как люди строят на наших исследованиях.

Эта статья является гостевым постом Эндрю Пелстры. Мнения, высказанные в ней, являются исключительно его собственными и не обязательно отражают позиции BTC Inc или Bitcoin Magazine.