Ковенанти Bitcoin: новий підхід до реалізації з витратами 50 мільйонів доларів без нових опкодів

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

Протягом останнього року чи двох було висунуто безліч пропозицій щодо розширень для ковенантів у Bitcoin, але серед експертів завжди існувало певне підозріння, що ковенанти можуть бути можливими і без таких розширень. Це підтверджується двома аспектами: розширенням репертуару раніше вважалися неможливими обчислень у Script (вершинам якого стало впровадження кожного опкоду RISC-V у проекті BitVM) та серією `майже-невдач`, в яких розробники Bitcoin знайшли способи, яким чином ковенанти могли б бути можливими, якби не деякі незрозумілі історичні особливості системи.

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

Незважаючи на космічні витрати на використання ColliderScript, його налаштування є досить дешевим, і таке налаштування (поряд із звичайним механізмом витрат, використовуючи Taproot для розділення обох) може врятувати ваші монети в разі, якщо квантовий комп`ютер несподівано з`явиться та зруйнує систему.

Безсумніву, багато читачів, прочитавши ці твердження, піднімають одну брову до неба. Коли ви закінчите читати цю статтю, інша буде такою ж високою.

Ковенанти

Контекст цього обговорення, для тих, хто не знайомий, полягає в тому, що Bitcoin має вбудовану мову програмування, звану Bitcoin Script, яка використовується для авторизації витрат монет. У своїх найперших днях Script містив широкий набір арифметичних опкодів, які могли бути використані для реалізації будь-яких обчислень. Але влітку 2010 року Сатоші відключив багато з них, щоб зупинити серію серйозних помилок. (Повернення до версії Script до 2010 року є метою Великого проекту відновлення Script; OP_CAT є менш амбіційною пропозицією в тому ж напрямку.) Ідея ковенантів — транзакцій, які використовують Script для контролю кількості та призначення своїх монет — з`явилася лише через кілька років, і усвідомлення того, що ці опкоди були б достатніми для реалізації ковенантів, з`явилося ще пізніше. До того часу спільнота стала надто великою і обережною, щоб просто `включити` старі опкоди так, як вони були відключені.

Історія

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

Незважаючи на ці зміни, зусилля в Script тривали, так само як і у вірі в те, що якимось чином може бути знайдено крайній випадок, який дозволить підтримку ковенантів у Bitcoin. У ранніх 2020-х роках два моменти в особливості викликали хвилювання. Один із них — моє власне відкриття, що підписні ковенанти не зникли разом з відновленням публічного ключа, і що, якщо ми отримали б навіть один відключений опкод назад — OP_CAT — цього було б достатньо для досить ефективної побудови ковенанта. Іншим був BitVM, новий спосіб виконання великих обчислень у Script через декілька транзакцій, що надихнуло величезну кількість досліджень з основних обчислень у межах окремих транзакцій.

Функціональне шифрування та PIPEs

Також було помічено, що з деякою виправданою логікою може бути можливим виконати ковенанти повністю в рамках самих підписів, не залишаючи Big Script. Цю ідею висловив Джеремі Рубін у своїй статті `FE`d Up Covenants`, в якій було описано, як реалізувати ковенанти, використовуючи гіпотетичний криптографічний примітив, званий функціональним шифруванням. Через кілька місяців Міша Коморов запропонував конкретну схему під назвою PIPEs, яка, здається, робить цю гіпотетичну ідею реальністю.

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

Цей огляд приводить нас до сучасної ситуації: ми хотіли б знайти спосіб реалізації ковенантів, використовуючи існуючу форму Bitcoin Script, і ми вважаємо, що спосіб зробити це полягає в знаходженні певного моста між `Великим Script` транзакційними підписами та `Малим Script` для довільних обчислень. Здається, що жоден опкод не може безпосередньо сформувати цей міст (див. Додаток A в нашій статті для класифікації всіх опкодів за їх розміром входу та виходу). Міст, якщо він існував, був би певною конструкцією, яка брала одне велике об`єкт і демонструвала, що воно точно дорівнює конкатенації кількох маленьких об`єктів. На основі нашої класифікації опкодів, це неможливо.

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

Що це означає? Ну, нагадаємо про винагороду за колізію хеш-функції, про яку ми згадали раніше. Принцип цієї винагороди полягає в тому, що будь-хто, хто може `колізувати` хеш-функцію, надаючи два введення, які мають один і той же хеш-вихід, може довести в Великому Script, що вони це зробили, і тим самим отримати винагороду. Оскільки простір введення хеш-функції набагато більший (усі байтові рядки до 520 байтів) ніж вихідний простір (байтові рядки точно 32 байти), з математичної точки зору має існувати безліч таких колізій. І все ж, з виключенням SHA1, ніхто не знайшов швидшого способу знайти ці колізії, ніж просто повторно викликати хеш-функцію і перевіряти, чи відповідає результат попередній спробі.

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

Якщо ми уявимо, що SHA1 і RIPEMD160 можуть бути обчислені так само ефективно, як Bitcoin ASIC обчислює SHA256, тоді вартість такого обчислення становитиме приблизно таку ж, як 200 блоків, або близько 625 BTC (46 мільйонів доларів). Це велика сума грошей, але багато людей мають доступ до такої суми, тому це можливо.

Щоб знайти потрійну колізію, або три введення, які оцінюють до одного й того ж, знадобиться близько 2^110 роботи, навіть за дуже оптимістичних припущень щодо доступу до пам`яті. Щоб отримати це число, нам потрібно додати ще один фактор у 16 мільйонів до нашої вартості — що доводить загальну суму до понад 700 трильйонів доларів. Це також величезні гроші, до яких ніхто зараз не має доступу.

Основна ідея нашої конструкції така: щоб довести, що серія маленьких об`єктів еквівалентна одному великому об`єкту, ми спочатку знаходимо колізію хешу між нашим цільовим об`єктом (який ми припускаємо, що можна якимось чином повторно рандомізувати, інакше ми б займалися `пошуком другого зображення`, а не пошуком колізій, що було б набагато важче) та `об`єктом, що перевіряє еквівалентність`. Ці об`єкти, що перевіряють еквівалентність, будуються таким чином, щоб їх можна було легко маніпулювати як у Великому Script, так і у Малому Script.

Наша конструкція тоді перевіряє у Bitcoin Script те, що наш великий об`єкт колізує з нашим об`єктом перевірки еквівалентності (використовуючи рівно ті ж методи, що й у випадку з винагородою за колізію хешу) та що наша серія малих об`єктів також колізує з об`єктом перевірки еквівалентності (використовуючи складні конструкції частково запозичені з проекту BitVM, та детально описані в статті). Якщо ці перевірки пройдуть, тоді або наші малі та великі об`єкти були однаковими, або користувач знайшов потрійну колізію: два різні об`єкти, які обидва колізують з тестером. За нашою аргументацією вище, це неможливо.

Висновок

Об`єднання Малого Script та Великого Script є найважчою частиною нашої конструкції ковенанту. Щоб перейти від цього мосту до реального ковенанту, існує кілька інших кроків, які є порівняно простими. Зокрема, сценарій ковенанту спочатку просить користувача підписати транзакцію, використовуючи спеціальний `генераторний ключ`, який ми можемо перевірити, використовуючи опкод OP_CHECKSIG. Використовуючи міст, ми розбиваємо цей підпис на 4-байтові частини. Потім ми перевіряємо, що його нонсу також дорівнює генераторному ключу, що легко зробити, як тільки підпис розбито. Нарешті, ми використовуємо техніки з трюку Шнорра для виводу даних транзакції з підпису, які можуть бути обмежені в будь-який спосіб, що бажає ковенант.

Існує кілька інших речей, які ми можемо зробити: Додаток C описує конструкцію кільцевого підпису, яка дозволила б монетам підписуватися одним з набору публічних ключів, не розкриваючи, який із них було використано. У цьому випадку ми використовуємо міст, щоб розбити публічний ключ, а не підпис. Такий підхід дає нам значне покращення ефективності відносно конструкції ковенанту з технічних причин, пов`язаних з Taproot і детально описаних у статті.

Останнє застосування, на яке я хочу звернути увагу, обговорюється коротко в Розділі 7.2 статті, це те, що ми можемо використовувати нашу конструкцію ковенанту, щоб витягти хеш транзакції з підпису Шнорра, а потім просто повторно підписати хеш, використовуючи підпис Лампорт.

Чому ми б це робили? Як було наведено в вище зазначеному посиланні, підпис Лампортом цього способу робить його квантово-безпечним підписом на даних транзакції; якщо ця конструкція була б єдиним способом підпису для деяких монет, вони були б імунними до крадіжки з боку квантового комп`ютера.

Звичайно, оскільки наша конструкція вимагає десятків мільйонів доларів для використання, ніхто не зробить цю конструкцію єдиним способом підпису для своїх монет. Але нічого не заважає комусь додати цю конструкцію до своїх монет, на додаток до їх існуючих неквантово-безпечних методів витрат.

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

Звичайно, їм доведеться витратити десятки мільйонів доларів, щоб зробити це, але це значно краще, ніж `неможливо`! І ми очікуємо і сподіваємося бачити, що ця вартість знизиться до неймовірних масштабів, оскільки люди будують на наших дослідженнях.

Ця стаття є гостьовою публікацією Ендрю Поелстри. Висловлені думки є виключно його власними і не обов`язково відображають думку BTC Inc або Bitcoin Magazine.