Еще немного про надежное программирование в Solidity
Исследуем хранилище EVM
Я уже писал что для хранения маппингов и динамических массивов (в том числе строк и байтовых массивов длиннее 32 байт) в Solidity, в качестве адреса объекта в постоянном хранилище, используется хеш-ключ . Это делает возможным (хоть и весьма маловероятным) возникновение коллизий при обращении к разным сохраненным объектам, что приведет к порче данных при записи объектов по совпавшим или близким адресам.
Проведя некоторые эксперименты с сокращенной шириной адресов и ключей, я выяснил, что полный перебор всех ключей не будет давать коллизий, только если суммарная битовая ширина ключа маппинга и занятой маппингами области слотов не превышает половины битовой ширины адресного пространства. Это правило стабильно сохраняется при росте битовой ширины адресного пространства в экспериментах. Таким образом, по индукции, использование ключей маппингов не шире 128 бит можно считать безопасным в этом смысле.
Однако, меня заинтересовало внутреннее устройство хранилища. 256 бит ширины адреса и константная стоимость записи слота требует нетривиальных решений с точки зрения реализации. И они нашлись у разработчиков EVM. Для хранения слотов хранилища, они используют modified Merkle-Patricia Trie который, как вы уже наверно догадываетесь ... да, именно, использует все тот же для вычисления адреса слота в хранилище. Адрес вычисляется, как
где
- это адрес контракта, а
- это адрес в адресном пространстве хранилища.
Конечно, я продолжил эксперименты, с целю выяснить, а что будет, когда я начну заполнять это почти безразмерное хранилище своими данными? Немного поправив уже разработанный алгоритм эксперимента, я стал искать коллизии на сокращенном адресном пространстве.
Если вы прочитали статью, вы уже наверно заметили, что вычисление адреса данных маппинга в хранилище и адреса слота хранилища для хранения в modified Merkle-Patricia Trie подозрительно похожи. Эксперимент это подтвердил. Коллизии при полном переборе номеров слотов начинают возникать, как только битовая ширина номера слота превышает половину ширины адресного пространства. Таким образом, почти бесконечный размер хранилища съеживается до значительно более скромных
. Иначе говоря, из всех
слотов хранилища, вам надежно доступны только
из них (эксперимент, как вы понимаете, перебирал те слоты, которые сосредоточены в начале хранилища с точки зрения их номеров).
А что, если посмотреть, как будут возникать коллизии в маппингах, с учетом того, как возникают коллизии при сохранении слотов хранилища? Я попробую и расскажу об этом в следующий раз.