Использование RSA-подписей Solidity для предпродаж и раздач

Подписи Solidity RSA для раздач и предпродаж: превосходство ECDSA и Merkle Trees по эффективности использования газа

Автор Сутан Сомадева и Майкл Берк

Введение

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

Для этого есть три проверенных решения: сопоставления, деревья Меркла и подписи ECDSA.

Относительные достоинства этих подходов уже были обсуждалось в другом месте, поэтому подведем итоги:

* Проверка подписи ECDSA (газ: 29 293) * с использованием доказательств Меркла (Gas: 30 517 128 адресов)

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

Из-за этого Merkle Trees и подписи ECDSA (используя предварительную компиляцию ecerecover, или еще лучше, более безопасная оболочка, опубликованная OpenZeppelin), часто предпочтительнее сопоставлений. Стоимость газа (для покупателя) при выполнении проверки подписи ECDSA составляет 29 293 газа. Это включает 21 000 для инициации транзакции, поэтому стоимость ECDSA составляет 8 293. Обратите внимание, что это включает в себя чтение адреса подписи из хранилища, но это необходимо, иначе мы не сможем сделать подписи недействительными.

Деревья Меркла различаются по стоимости в зависимости от размера дерева (более крупные деревья требуют более крупных доказательств Меркла), но если в дереве Меркла содержится более 1000 адресов, проверка адреса будет стоить не менее 32 000 газа (или больше). Эта стоимость явно ниже, чем у ECDSA.

Таким образом, цель состоит в том, чтобы превзойти ECDSA, который стоит 8 293 газа. Чтобы решения оставались одинаковыми, альтернативное решение должно:

1. Возможность аннулировать разрешенные адреса. Деревья Меркла могут изменить свой корень, ECDSA могут изменить свой адрес подписи, а сопоставления могут установить значение false.
2. Не возлагать на продавца существенное бремя расходов, как это делают сопоставления.
3. Стоимость для покупателя менее 8200 единиц газа (включая нагрузку на хранилище).
4. Не подвергать риску безопасность

Предпосылки

Чтобы понять предлагаемую методологию, читатель должен быть знаком со следующими темами:

* Предварительно скомпилированные смарт-контракты (рекомендуется к прочтению, обмен стеками) * Метаморфические контракты (введение, рекомендуется к прочтению) * Списки доступа (рекомендуется к прочтению) * Как использовать цифровые подписи и соответствующие варианты их использования в блокчейн-приложениях. * Как рассчитывается стоимость газа, особенно в отношении данных вызовов, кодов операций, хранилища и использования памяти.

Алгоритм RSA

Если мы хотим значительно превзойти ECDSA, нам нужно найти другой криптографический алгоритм, который позволяет подтвердить принадлежность к набору. ECDSA на самом деле является более новой и более крутой версией оригинального алгоритма цифровой подписи RSA. ECDSA полагается на то, что дискретные логарифмы над эллиптическими кривыми являются жесткими (отсюда и название — алгоритм цифровой подписи на эллиптических кривых). RSA (названный в честь его авторов, Ривеста, Шамира, Адлемана) полагается на большие целые числа, которые трудно разложить на множители. Что касается возраста, RSA была опубликована в 1970-х годах, но ECDSA стала официальной спецификацией в начале 2000-х годов.

Мы не будем подробно объяснять RSA здесь, но необходимо выполнить некоторые предварительные требования.

Подписавшаяся сторона выбирает два больших простых числа p и q и перемножает их вместе, чтобы получить n. Этот n является первой частью открытого ключа. Во-вторых, подписывающая сторона выбирает небольшое простое число e (в нашем случае может быть жестко запрограммировано на 3) и публикует пару (n, e). как открытый ключ. За кулисами подписывающая сторона вычисляет

t = (p - 1) * (q - 1)
d = t^(-1) % n

Число d является закрытым ключом. Если бы злоумышленник мог разложить n на p и q, то вычисление d было бы тривиальным. Но известно, что разложение целых чисел сложно. Чтобы подписать сообщение, подписывающая сторона хеширует сообщение m, чтобы получить h, и возводит h в степень d. То есть

s = h(m) ^ d % n

Затем подписывающая сторона публикует (m, s) в качестве сообщения и подписи.

Затем верификатор хэширует m и возводит его в степень e mod n. Помните, что e и n — это открытый ключ. Если и только если

s == s ^ e % n

тогда подпись действительна для открытого ключа (n, e). Обратите внимание, что если n чрезвычайно велико, то вероятность того, что s == s ^ e % n по случайному совпадению, исчезающе мала. Если равенство подтверждается, мы знаем, что подпись действительна для открытого ключа.

Чтобы сделать это в Ethereum, мы просто подпишем адрес как

s = buyerAddress ^ d % n

и смарт-контракт проверит

msg.sender == s ^ e % n

Использование только 256 бит небезопасно

Мы говорим, что «разлагать на множители целые числа сложно», но очевидно, что это подразумевает, что число должно быть достаточно большим. Например, 33 состоит из двух простых чисел, и его разложить несложно. К счастью, в вызове факторинга RSA у нас есть реальные эталонные показатели того, чего может достичь современное оборудование.

Чтобы уточнить, количество «бит» относится к размеру открытого ключа. Следовательно, когда мы говорим «RSA 2048», это означает, что число n, модуль, имеет 2048 бит. При сравнении размеров ключей важно помнить, что каждый дополнительный бит удваивает размер числа. Таким образом, 700 бит экспоненциально более безопасны, чем 350 бит, а не в два раза безопаснее.

До сих пор самый большой ключ, который нужно было взломать (рассчитать), имел 829 бит, и для этого требовался современный суперкомпьютер. Команда использовала примерно 2700 ядер-лет ЦП, используя ЦП Intel Xeon Gold 6130 с тактовой частотой 2,1 ГГц. Самый дешевый 16-ядерный процессор на AWS стоит 0,40 цента в час, поэтому стоимость взлома этого ключа составляет порядка 9,4 миллиона долларов. Даже с учетом щедрых скидок от поставщика облачных услуг стоимость исчисляется миллионами.

Модульная арифметика с более чем 256 битами в Solidity

Эфириум поддерживает только 32-байтовые типы данных, поэтому по умолчанию мы не можем выполнить

s ^ e % n

К счастью, блокчейн Ethereum добавил предварительно скомпилированный контракт в EIP 198 специально для поддержки модульной арифметики. Чтобы использовать его, основание, экспонента и модуль должны быть загружены в память в закодированном формате abi. Затем вызывается контракт, расположенный по адресу 0x05.

Хранение открытого ключа становится проблемой, если вы используете безопасное количество битов. Если размер ключа составляет 1024 бита, требуется 4 слота для хранения. Для чтения открытого ключа из хранилища потребуется четыре операции SLOAD, всего 8400 газов. Это само по себе уже менее эффективно, чем решение ECDSA, рассмотренное выше.

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

Однако ключевой идеей является хранение открытого ключа в байт-коде, а не в хранилище. Чтение байт-кода внешнего контракта (EXTCODECOPY) стоит 2 600 газа, что намного меньше, чем 8 400 газа при чтении каждой части открытого ключа в четыре штуки.

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

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

Аннулирование открытого ключа с помощью шаблона метаморфического контракта

Смарт-контракт создается путем загрузки байт-кода развертывания в память, а затем возврата диапазона байт-кода, содержащего код среды выполнения. Подробнее см. здесь.

Когда смарт-контракт создается с помощью команды create2, адрес контракта можно предсказать заранее. Адрес вычисляется из комбинации соли, средства развертывания и байт-кода инициализации. Если контракт самоуничтожается, можно развернуть новый контракт по тому же адресу.

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

Таким образом, у нас может быть смарт-контракт, первые k байт которого предназначены для самоуничтожения при определенных условиях, а остальные байты — просто открытый ключ RSA.

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

Экономия дополнительных 100 единиц газа с помощью списков доступа

EIP 2930 добавлен новый тип транзакции, который позволяет пользователю заранее указать, какие адреса и слоты хранения будет доступ. Это позволяет узлам предварительно извлекать эти значения из хранилища, тем самым ускоряя время выполнения. Использование транзакции списка доступа при вызове внешнего контракта может сэкономить 100 газа. Обратите внимание, что это сохранение не применяется, когда смарт-контракт обращается к своей собственной переменной хранилища. Поскольку этот дизайн предпродажной раздачи RSA основан на внешнем контракте для хранения открытого ключа, использование списка доступа уместно.

Сравнительные показатели: стоимость газа и размер ключа

Большая часть расходов на газ связана с очень большими данными о звонках в результате больших подписей. Если размер ключа установлен на 1024 бита, то данные вызова будут 128 байт. Каждый байт стоит 16 газов, поэтому общая стоимость газа только для того, чтобы иметь данные о звонках, составляет 2 048 газов.

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

Почему это экономит газ по сравнению с ECDSA

Эталонные показатели ясно показывают, что чем больше ключ (и, следовательно, подпись), тем выше стоимость газа. В нашем дизайне используется тот факт, что предварительная компиляция назначает низкую цену для повышения числа до малой мощности. Стоимость выполнения предварительно скомпилированного контракта при таких условиях в 0x05 составляет всего несколько сотен газа по сравнению с тысячами за выполнение прекомпиляции для ECDSA.

Выбор размера ключа

Хотя ключ длиной 829 бит был учтен, для этого требуется современный суперкомпьютер. Для таких приложений, как раздача токенов с более низкой стоимостью или выставление NFT на предварительную продажу, у злоумышленника нет стимула тратить от шестизначной суммы до миллиона долларов, чтобы факторизовать открытый ключ и получить NFT на предварительной продаже. Самые дорогие токены Ethereum на данный момент (Fidenza и Bored Ape Yacht Club) стоит примерно 100 000 долларов США за штуку, поэтому для подавляющего большинства приложений взлом открытого ключа злоумышленнику экономически невыгодно.

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

Ключевые контрольные показатели размера

Это было выполнено с помощью компилятора Solidity версии 0.8.17 с оптимизатором, установленным на 1 миллион

* RSA-896 (Газ: 27 040) * РСА-960 (Газ: 27 115) * РСА-1024 (Газ: 27 311) * RSA-2048 (Газ: 29 901)

Заключение

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

Наша работа является лишь доказательством концепции на данном этапе. Разработчикам рекомендуется соблюдать осторожность при использовании кода в рабочей среде.

Этот проект создали Сутан Сомадева и Майкл Берк. в рамках учебного курса RareSkills Solidity. Реализация кода и модульные тесты находятся на github.

Также опубликовано здесь.