Pull to refresh
48
6
Всеволод Новиков @nnseva

User

Send message

Еще немного про надежное программирование в Solidity

Исследуем хранилище EVM

Я уже писал что для хранения маппингов и динамических массивов (в том числе строк и байтовых массивов длиннее 32 байт) в Solidity, в качестве адреса объекта в постоянном хранилище, используется хеш-ключ keccak256. Это делает возможным (хоть и весьма маловероятным) возникновение коллизий при обращении к разным сохраненным объектам, что приведет к порче данных при записи объектов по совпавшим или близким адресам.

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

Однако, меня заинтересовало внутреннее устройство хранилища. 256 бит ширины адреса и константная стоимость записи слота требует нетривиальных решений с точки зрения реализации. И они нашлись у разработчиков EVM. Для хранения слотов хранилища, они используют modified Merkle-Patricia Trie который, как вы уже наверно догадываетесь ... да, именно, использует все тот же keccak256 для вычисления адреса слота в хранилище. Адрес вычисляется, какkeccak256(concat(contract, slot)) где contract - это адрес контракта, а slot - это адрес в адресном пространстве хранилища.

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

Если вы прочитали статью, вы уже наверно заметили, что вычисление адреса данных маппинга в хранилище и адреса слота хранилища для хранения в modified Merkle-Patricia Trie подозрительно похожи. Эксперимент это подтвердил. Коллизии при полном переборе номеров слотов начинают возникать, как только битовая ширина номера слота превышает половину ширины адресного пространства. Таким образом, почти бесконечный размер хранилища 2^{256} съеживается до значительно более скромных 2^{128}. Иначе говоря, из всех 2^{256} слотов хранилища, вам надежно доступны только 2^{128} из них (эксперимент, как вы понимаете, перебирал те слоты, которые сосредоточены в начале хранилища с точки зрения их номеров).

А что, если посмотреть, как будут возникать коллизии в маппингах, с учетом того, как возникают коллизии при сохранении слотов хранилища? Я попробую и расскажу об этом в следующий раз.

Tags:
Rating0
Comments0

Проблема распределения памяти хранилища в Solidity

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

Как хранятся данные смарт-контракта в хранилище

В адресном пространстве хранилища (2**256 слов размером 32 байта), все постоянные переменные контракта фиксированного размера хранятся в самом его начале (самые младшие адреса). Однако, язык Solidity предоставляет возможность хранить и динамические переменные, которые могут менять свой размер. Язык позволяет использовать две разновидности таких переменных, динамический массив и отображение.

В Solidity (и в других языках смарт-контрактов, с которыми мне удалось бегло ознакомиться) для хранения динамических данных используется хитрый трюк, связанный с функцией криптографического хеширования keccak (в смарт-контрактах используется keccak256, которая возвращает хеш размером 256 бит).

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

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

Так в чем проблема?

Проблема в том, что же делать, если пересечение данных все-таки случилось.

Вероятность такого события - ничтожная, учитывая ширину адреса, с одной стороны, и объем данных, характерных для контрактов, с другой. Фактически, насколько можно понять из доступной на сегодня информации, до сих пор в сетях, поддерживающих EVM, нет ни одного зафиксированного случая пересечения ключей, выработанных посредством keccak на основании разных исходных данных.

Однако, начиная работать со смарт-контрактами, мне бы не хотелось стать тем счастливчиком, который наткнется на пересечение ключей в своем смарт-контракте первым. Насколько я понимаю, никакой диагностики пересечения ключей (и тем более, пересечения массивов, разбросанных функцией keccak в адресном пространстве хранилища) не предусмотрено, а результат такого пересечения для контракта - катастрофический, сравнимый с доступом к неинициализированной памяти в C++.

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

Что делать?

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

Tags:
Total votes 2: ↑2 and ↓0+2
Comments6

Information

Rating
1,392-nd
Location
Нижний Новгород, Нижегородская обл., Россия
Date of birth
Registered
Activity