Открыть список
Как стать автором
Обновить

Более эффективная запись массивов в постоянную память смарт-контракта в Solidity

ПрограммированиеSolidity
В последнее время, мне пришлось немного поработать с блокчейном Ethereum. Идея, над которой я работал, требовала хранить прямо в блокчейне некоторое достаточно большое количество целых чисел, так, чтобы смарт-контракт имел к ним удобный доступ. Большинство уроков по разработке смарт-контрактов говорят нам «не храните много данных в блокчейне, это дорого!». Но сколько это «много», и с какого количества цена становится слишком высокой для практического использования? Это мне надо было выяснить, потому что нам наши данные выносить офф-чейн было никак нельзя, рушилась вся затея.

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

Для начала, я решил быстро прикинуть — получится ли у нас? Давайте возьмём стандартный, широко распространённый тип контракта — токен ERC20. По крайней мере, такой контракт хранит в блокчейне соответствие адресов людей, который купили токены, их балансам. В реальности, хранятся только балансы, каждый из которых занимает 32 байта (на деле здесь экономить не имеет смысла из-за особенностей Solidity и EVM). У более-менее успешного токена легко могут быть десятки тысяч обладателей, и таким образом получаем, что хранить в блокчейне около 320000 байт — вполне допустимо. А нам больше и не надо!

Наивный подход


Ну что же, попробуем наши данные сохранить. Значительная их часть — 8-битные целые беззнаковые числа, поэтому передадим их массив в контракт, и попробуем записать их в постоянную память:

uint8[] m_test;
function test(uint8[] data) public
{
    m_test = data;
}

Опаньки! Эта функция кушает газ, как не в себя. Попытка сохранить 100 значений обошлась нам в 814033 газа, по 8100 газа на байт!

Выдохнем, и сделаем шаг назад, к теории. Какая минимальная стоимость (в газе) сохранения данных в блокчейне Ethereum? Надо помнить, что данные сохраняются блоками по 32 байта. EVM умеет читать или писать только сразу целый блок, поэтому в идеале записываемые данные надо упаковывать максимально эффективно, чтобы одной командой записи сразу сохранить побольше. Потому что эта самая команда записи — SSTORE — сама по себе стоит 20000 газа (если мы пишем в ячейку памяти, в которую ещё не писали до этого). Так что наш теоретический минимум, игнорируя все прочие расходы, около 625 газа на байт. Далеко не те 8100, которые мы получили в примере выше! Теперь время закопаться поглубже и выяснить, кто жрёт наш газ, и как это прекратить.

Первым нашим порывом должно быть посмотреть на код, сгенерированный компилятором Solidity из нашей одинокой строчки (m_test = data), потому что больше-то и смотреть нечего. Это хороший, правильный порыв, который ознакомит нас с ужасающим фактом — компилятор в этом месте нагенерировал каких-то древних ужасов, которые с первого взгляда и не поймёшь! Окинув листинг быстрым взглядом, видим там не только SSTORE (что ожидаемо), но и SLOAD (загрузка из постоянной памяти) и даже EXP (возведение в экспоненту)! В целом всё это выглядит очень дорогим способом записывать данные. А хуже всего, что становится совершенно очевидно, что SSTORE вызывается слишком, слишком часто. Что же тут происходит?

Несколько вещей. Выясняется, что хранить 8-битные целые числа — это почти худшее, что можно делать с EVM/Solidity (статья, ссылку на которую я привёл в начале, об этом говорит). Мы теряем производительность (а значит платим больше газа) на каждом шагу. Во-первых, когда мы передаём массив 8-битных значений на вход нашей функции, каждое из них расширяется до 256 бит. То есть, только на размере данных транзакции мы уже проигрываем в 32 раза! Мило! Впрочем, внимательный читатель заметит, что стоимость за сохранённый байт, всё же, лишь в 13 раз выше теоретического минимума, а не в 32, а значит во время сохранение в постоянную память контракта всё уже не так плохо. Дело вот в чём: Solidity при сохранении таки упаковывает данные, и в постоянной памяти контракта наши 8-битные числа будут храниться максимально эффективным образом, по 32 штуки в каждом блоке памяти. Это порождает вопрос, а как происходит преобразование «256-битных» неупакованных чисел, пришедших нам во входных данных функции в упакованный вид? Ответ — «самым дурацким способом, который я могу себе представить».

Если записать всё происходящее в упрощённом виде, то наша одинокая строчка кода превращается в жутковатый цикл:

for(uint i = 0; i < data.length; ++i)
{
    // Читаем один байт из входящих данных, конвертируя его из 256-bit в 8-bit
    uint8 from_value = uint8(data[i]);
    
    // Читаем 32-байтный блок из постоянной памяти - для этого придётся сделать некоторое количество дополнительных вычислений, которые мы здесь опустим
    uint256 to_value = get_storage_data_at_offset(m_test, i);
    
    // Дописываем новый байт в нужное место блока (это тоже вам не 2 бита переслать)
    add_byte_to_value(to_value, i % 32, from_value);
    
    // Записываем 32-байтный блок обратно в постоянную память
    set_storage_data_at_offset(m_test, i, to_value);
}

На то, как выглядит этот код, почти не влияет включение или отключение оптимизации (во всяком случае, в версии компилятора Solidity 0.4.24), и, как можно заметить, он зовёт SSTORE (как часть set_storage_data_at_offset) в 32 раза чаще, чем надо (по разу на каждое 8-битное число, а не один раз на 32 таких числа). От полного фиаско нас спасает лишь то, что повторная запись в ту же ячейку стоит не 20000, а 5000 газа. Так что каждые 32 байта стоят нам 20000+5000*31 = 125000 газа, или примерно 4000 газа на байт. Остальная часть стоимости, которую мы видели выше, происходит из чтения памяти (тоже не дешёвая операция) и прочих вычислений, спрятанных в коде выше в функциях (а их там много).

Ну, с компилятором мы ничего поделать не можем, поэтому будем искать пуговицу. Тут только остаётся сделать вывод, что не надо передавать и сохранять в контракте массивы 8-битных чисел таким образом.

Простое решение для 8-битных чисел


А каким надо? А таким:

bytes m_test;
function test(bytes data) public
{
    m_test = data;
}

Эксплуатируем во все поля типа bytes. При таком подходе, сохранение 100 значений обойдётся в 129914 газа — всего в 1300 газа за байт, в 6 раз лучше, чем при использовании uint8[]! Платой за это будет некоторое неудобство — элементы массива типа bytes имеют типа bytes1, который не конвертируется автоматически ни к одному из обычных целочисленных типов, поэтому в нужных местах придётся расставить явное приведение типов. Не очень приятно, но выигрыш в 6 раз по стоимости записи, думаю, того стоит! И, да, мы немного проиграем при работе с этими данными потом, при чтении, по сравнению с хранением каждого числа как 256-битного, но тут уже начинает иметь значение масштаб: выигрыш от сохранения тысячи-другой 8-битных чисел в упакованном виде может, в зависимости от задачи, перевесить потери при их чтении потом.

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

Дополнительно отмечу, что чем больше данных сохраняешь за раз — тем меньше выходит стоимость за байт, что наводит на мысль, что часть стоимость — фиксированная. Например, если сохранять 3000 значений, то при подходе с bytes получаем 900 газа за байт.

Более общее решение


Ну, что, всё хорошо, что хорошо кончается, да? Но наши проблемы-то тут не кончились, потому что иногда хочется записать в память контракта не только 8-битные числа, но и другие типы данных, которые не являются прямым соответствием типу bytes. То есть, понятно, что в буфер байтов можно закодировать вообще всё, что угодно, но вот доставать это потом оттуда может быть уже не удобно, и даже дорого из-за лишних телодвижений по преобразованию «сырой» памяти к нужному типу. Так что функция, которая сохраняет переданный массив bytes в массив нужного типа нам всё же пригодится. Она довольно простая, но мне потребовалось много времени, чтобы найти всю необходимую информацию и разобраться в EVM и JULIA, чтобы её написать, причём всё это не было собрано в одном месте. Поэтому, думаю, будет полезно, если я здесь приведу то, что накопал.

Для начала, поговорим о том, как Solidity сохраняет массив в памяти. Массивы — это понятие, которое только в рамках Solidity и существует, EVM ничего о них не знает, а просто хранит виртуальный массив из 2^256 32-байтных блоков. Понятно, что пустые блоки не хранятся, а на самом деле, мы имеем таблицу непустых блоков, ключом которой является 256-битное число. И именно это число принимают на вход команды EVM SSTORE и SLOAD (это не совсем очевидно из документации).

Чтобы хранить массивы, Solidity делает такую хитрую штуку: во-первых, «главный» блок массив выделяется под него где-то в постоянной памяти, в обычном порядке размещения членов контракта (или структуры, но это отдельная песня), как если бы это было обычное 256-битное число. Это гарантирует, что массив получает себе один полный блок, независимо от прочих хранимых переменных. В этом блоке сохраняется длинна массива. Но поскольку заранее она не известна, и может меняться (мы здесь говорим о динамических массивах), то авторам Solidity надо было придумать, куда бы засунуть данные массива так, чтобы они случайно не пересеклись с данными другого массива. Строго говоря, это неразрешимая задача: если создать два массива длинной более 2^128, то они гарантированно пересекутся, где их не размещай, но на практике так делать никто не должен, поэтому используется такой простой трюк: берётся хэш SHA3 от номера главного блока массива, и полученное число используется как ключ в таблице блоков (которых, напоминаю, 2^256). По этому ключу, размещается первый блок данных массива, а остальные — последовательно после него, если надо. Вероятность столкновения не-гигантских массивов крайне мала.

Таким образом, в теории, всё что нам нужно — это найти, где лежат данные массива, и скопировать переданный нам буфер байтов поблочно. Пока мы работаем с типами размером меньше половины блока, мы будем хоть немножко, но выигрывать у «наивного» решения, генерируемого компилятором.

Остаётся только одна проблема — если всё так вот и сделать, то байты в нашем массиве получатся задом наперёд. Потому что EVM — big-endian. Проще и эффективнее всего, конечно, разворачивать байты при отсылке, но для простоты API я решил делать это в коде контракта. Если вы хотите ещё немного сэкономить — смело выбрасывайте эту часть функции, и делайте всё в момент отправки.

Вот функция, которая у меня получилась для превращения массива байт в массив 64-битных знаковых целых (впрочем, она может быть легко адаптирована к другим типам):

function assign_int64_storage_from_bytes(int64[] storage to, bytes memory from) internal
{
    // Изменяем размер целевого массива. Поскольку мы пишем код для int64, то у нас будет 8 байт на значение (sizeof в Solidity нет :( )
    to.length = from.length / 8;
    
    // Вычисляем адрес начала данных массива, взяв SHA3 от номера его главного блока
    uint256 addr;
    bytes32 base;
    assembly{
        // keccak256 работает с памятью, а не со стэком, поэтому сначала нам надо записать номер блока в память
        mstore(addr, to_slot)
        base := keccak256(addr, 32)
    }
    
    uint i = 0;
    for(uint offset = 0; offset < from.length; offset += 32)
    {
        // Загружаем 32-байтный блок из исходного массива
        // Не забываем пропустить первые 32 байта - у массивов, находящихся в памяти, в них лежит длина
        uint256 tmp;
        assembly{
            tmp := mload(add(from, add(offset,32)))
        }
        
        // Обращаем порядок байт. Надо полагать, это можно сделать гораздо эффективнее, но это оставим как задачу для читателей.
        for(uint b = 0; b < 16; ++b)
        {
            uint shift = b*8;
            uint shift2 = (256 - (b+1)*8);
            
            uint low = (tmp & (0xFF << shift)) >> shift;
            uint high = (tmp & (0xFF << shift2)) >> shift2;
            
            tmp = tmp & ~( (0xFF << shift) | (0xFF << shift2));
            tmp = tmp | (low << shift2) | (high << shift);
        }
        
        // Записываем данные в постоянную память
        assembly{
            sstore(add(base, i), tmp)
        }
        i += 1;
    }
}

С 64-битными числами мы выигрываем не так много, как с 8-битными, по сравнению с кодом, который генерирует компилятор, но тем не менее эта функция тратит 718466 газа (7184 газа на число, 898 газа на байт) против 1003225 у наивного решения (1003 газа на число, 1254 на байт), что делает её использование достаточно осмысленным. И как уже говорилось выше, можно сэкономить ещё, убрав обращение байт на вызывающую сторону.

Стоит отметить, что лимит газа на блок в Ethereum устанавливает предел тому, сколько данных мы можем записать в ходе одной транзакции. Что ещё хуже, дописывать данные в уже заполненный массив — гораздо более сложная задача, кроме тех случаев, когда последний использованный блок массива был заполнен до предела (в каковом случае можно использовать ту же функция, но с другим отступом). На текущий момент, лимит газа на блок составляет около 6 миллионов, что значит, что мы более-менее можем сохранить 6Кб данных за раз, а на деле — даже меньше, за счёт прочих трат.

Грядущие изменения


Грядущие в октябре изменения в сети Ethereum, которые произойдут с активацией EIPов, входящих в Constantinople, должны привести к тому, что сохранять данные станет проще и дешевле — EIP 1087 предполагает, что плата за сохранение данных будет браться не за каждую команду SSTORE, а за количество изменённых блоков, что сделает наивный подход, используемый компилятором, почти таким же выгодным, как написанный вручную код на JULIA (но не совсем — много лишних телодвижений там останется, особенно для 8-битных значений). Планируемый в будущем переход на WebAssembly в качестве базового языка EVM ещё сильнее изменит картину, но это пока очень отдалённая перспектива, а задачи решать надо уже сейчас.

Этот пост не претендует на звание самого лучшего решения поставленной проблемы, и я буду рад, если кто-то предложит более эффективное — я пока только начал осваиваться с Ethereum, и мог упустить из виду какие-то особенность EVM, которые могли бы мне помочь. Но в моих поисках по сети я не видел ничего по этой проблеме, и может быть приведённые выше размышления и код будут для кого-то полезны как отправная точка для оптимизации.
Теги:solidityethereumblockchainмассивыоптимизация
Хабы: Программирование Solidity
Всего голосов 8: ↑7 и ↓1 +6
Просмотры2.2K

Похожие публикации

Аудит и оптимизация QA-процессов
21 мая 202113 000 ₽Лаборатория Качества
Программирование на Python: Введение
18 октября 202130 000 ₽Сетевая Академия ЛАНИТ
SMM-менеджер
13 мая 2021Цена по запросуGeekBrains

Лучшие публикации за сутки