Привет всем из мира авось-программирования Solidity.

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

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

Динамические массивы

Вы можете перебрать все возможные сгенерированные адреса динамических массивов для первых нескольких слотов статических (то есть заданных в переменных контракта) данных. Это сделать очень просто. Каждый динамический массив (то есть область его данных) располагается по адресу, вычисленному какkeccak256от адреса слота, где он располагается. То есть динамический массив, объявленный первой переменной, расположится по адресуkeccak256(0), второй переменной - по адресуkeccak256(1)и так далее. Самая маленькая разница между такими адресами, вычисленными для первых1024слотов, будет около2^{235}, (учитывая также разницу между нулевым адресом и самым маленьким адресом массива, и самым большим адресом массива и самым большим возможным адресом). Таким образом, поскольку элементы массивов располагаются по адресам, непосредственно следующим за вычисленным начальным адресом массива, вы можете совершенно безопасно располагать не менее2^{235}эдементов данных размером1 слот в каждом таком массиве, плюс примерно столько же - в статической (начальной) области данных контракта, при условии, что больше никаких динамических данных в вашем контракте нет.

Маппинги

В отличие от динамических массивов, адрес каждого значения маппинга вычисляется отдельно, какkeccak256(concat(s,k))гдеsэто слот маппинга,kэто ключ маппинга (для простых типов), аconcat()соединяет побайтное представление своих параметров.

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

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

В исследовании, изучается полный набор адресов, сгенерированный из ключей заданной битовой шириныM, в пространстве адресов сокращенной битовой шириныKгдеM < K.

Основные выводы

Все рассмотренные в исследовании случаи позволяют сделать следующий вывод: если вы используете ключ маппинга шириной в половину или больше ширины адресного пространства (при ширине адресного пространства "настоящей" EVM составляющей256бит, это будет128бит), то перебирая все ключи, вы совершенно точно наткнетесь на коллизию. То есть использование например, адреса счета или контракта шириной160бит в качестве ключа маппинга, в этом смысле, безопасным точно не является.

Комментарии (1)


  1. pnaydanovgoo
    14.05.2025 05:09

    Красивая конечно теория!

    Что касается массивов

    > вы можете совершенно безопасно располагать не менее2^{235}элементов данных размером слот в каждом таком массиве

    Мне просто стало интересно, сколько будут занимать такие данные, жпт говорит, что это. примерно ~10⁷⁰ гигабайт. Это просто физически невозможно провернуть в Ethereum. Это огромное число.

    Что касается маппингов

    На сколько я понимаю коллизии могут возникнуть в использовании keccak256, но не mapping, потому что mapping использует хеш(key, slot). Так как для получения коллизии нужен один mapping, в котором два ключа дадут одинаковый хеш.

    Но тут у меня вопрос, на сколько симуляция на урезанном адресном пространстве валидно? Симуляция keccak256 на K < 256 битах не отражает реальность, потому что в EVM хеш всегда 256-битный на сколько я понимаю.

    На мой взгляд бояться наступления коллизий надо при использовании assembly вставок. Вот там, когда ручками по слотам ходишь легко допустить ошибку.