EVM вглубь: пишем виртуальную машину

Мы обошли EVM кругами: смарт-контракт как идея, аккаунты, состояние, газ. Теперь заглянем внутрь и напишем машину сами. И это не новая для тебя территория: виртуальную машину ты уже собирал в эмуляторе bcpu (урок 36 раздела Rust), а стековые машины разбирал в Bitcoin Script (урок 21) и WASM (урок 67 раздела Rust). EVM это та же идея с двумя поворотами: слово в 256 бит и цена в газе за каждый шаг.

Идея

EVM это цикл «взять опкод, исполнить, повторить». Отличия от bcpu:

• Слово 256 бит, а не 16. Такая ширина выбрана под криптографию: хеш keccak256 и адреса удобно ложатся в одно слово.
• Стек вместо регистров: до 1024 слов, операнды снимаются с вершины.
• Газометр: каждый шаг списывает газ, кончился газ, машина встала.
• Три области данных: memory (временная), storage (постоянная), calldata (аргументы вызова).

Соберём всё это по слоям.

Слово в 256 бит руками

В обычных языках нет 256-битного целого, поэтому сделаем его сами: четыре u64 в little-endian. Вся арифметика по модулю 2^256, ровно как переполнение у обычных целых из урока 19 раздела Rust, только шире.

/// Слово EVM это ровно 256 бит: четыре u64 в little-endian (limbs[0] младший).
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct U256([u64; 4]);

impl U256 {
    /// Сложение по модулю 2^256: складываем limb за limb с переносом,
    /// перенос за 256-й бит просто отбрасываем.
    pub fn wrapping_add(self, other: U256) -> U256 {
        let mut r = [0u64; 4];
        let mut carry = 0u64;
        for (i, slot) in r.iter_mut().enumerate() {
            let (s1, c1) = self.0[i].overflowing_add(other.0[i]);
            let (s2, c2) = s1.overflowing_add(carry);
            *slot = s2;
            carry = u64::from(c1) + u64::from(c2);
        }
        U256(r)
    }
}

Из-за модуля 2^256 максимум плюс один даёт ноль, молча, без ошибки. Это и есть переполнение uint256, на котором горели контракты до версии Solidity 0.8 (проверь в виджете ниже пресет «переполнение»).

Деление руками поинтереснее: 256-битного деления в столбик у процессора нет, делаем бит за битом.

/// Деление с остатком бит за битом (256 итераций сдвига-вычитания).
/// Семантика EVM: деление на ноль это не паника, а ноль.
pub fn div_rem(self, divisor: U256) -> (U256, U256) {
    if divisor.is_zero() {
        return (U256::ZERO, U256::ZERO);
    }
    let mut quotient = U256::ZERO;
    let mut remainder = U256::ZERO;
    for i in (0..256).rev() {
        remainder = remainder.shl(1); // сдвигаем остаток влево
        if self.bit(i) {
            remainder.0[0] |= 1; // заводим очередной бит делимого
        }
        if remainder >= divisor {
            remainder = remainder.wrapping_sub(divisor);
            quotient.0[i / 64] |= 1u64 << (i % 64);
        }
    }
    (quotient, remainder)
}

Это два самых поучительных метода, остальной тип U256 собран из тех же приёмов: пройти по четырём limb, аккуратно пронести перенос или бит. Приведём сигнатуры того, чем будет пользоваться интерпретатор ниже:

impl U256 {
    pub const ZERO: U256;                            // ноль
    pub const ONE: U256;                             // единица
    pub const MAX: U256;                             // 2^256 - 1

    pub const fn from_u64(value: u64) -> U256;       // поднять u64 в 256-битное слово
    pub fn is_zero(&self) -> bool;
    pub fn low_u64(&self) -> u64;                    // младшие 64 бита
    pub fn as_usize_saturating(&self) -> usize;      // индекс памяти; не влезло, usize::MAX
    pub fn from_be_bytes(bytes: &[u8; 32]) -> U256;  // 32 байта big-endian в слово
    pub fn to_be_bytes(&self) -> [u8; 32];           // и обратно
    pub fn from_big_endian(bytes: &[u8]) -> U256;    // хвост до 32 байт, для PUSH
    pub fn bit(&self, index: usize) -> bool;         // i-й бит, считая от младшего
    pub fn byte(&self, index: usize) -> u8;          // i-й байт, считая от старшего (BYTE)
    pub fn wrapping_sub(self, other: U256) -> U256;  // вычитание по модулю 2^256
    pub fn wrapping_mul(self, other: U256) -> U256;  // умножение столбиком по limb
    pub fn pow(self, exponent: U256) -> U256;        // EXP: квадрат и умножь
    pub fn shl(self, shift: usize) -> U256;          // сдвиг влево (SHL)
    pub fn shr(self, shift: usize) -> U256;          // сдвиг вправо (SHR)
}

Сравнения и побитовые операции добавляются обычными трейтами (Ord, BitAnd, BitOr, BitXor, Not). Отдельного слова заслуживает as_usize_saturating: если слово не влезает в usize, возвращаем usize::MAX. Для интерпретатора это безопасно: такое смещение упрётся в цену расширения памяти и остановит машину по газу, а не попытается выделить эксабайты.

Диспетчер опкодов

Сердце машины это match по байту опкода, ровно как декодер bcpu (урок 38 раздела Rust). Состояние машины это стек, память, газ, хранилище и указатель pc.

use std::collections::{HashMap, HashSet};

pub struct Machine {
    pub code: Vec<u8>,
    pub pc: usize,
    pub stack: Vec<U256>,
    pub memory: Vec<u8>,
    pub gas: u64,
    pub storage: HashMap<U256, U256>,
    pub calldata: Vec<u8>,
    pub returned: Vec<u8>, // последние возвращённые данные (RETURN и REVERT)
    jumpdests: HashSet<usize>, // валидные цели перехода, посчитаны заранее
}

/// Итог исполнения: вернули данные, откатились, штатно встали или упали.
pub enum ExecResult {
    Return(Vec<u8>),
    Revert(Vec<u8>),
    Stop,
    Halt(Error),
}

pub enum Error {
    StackUnderflow,
    StackOverflow,
    OutOfGas,
    InvalidJump,
    InvalidOpcode(u8),
}

Один шаг: списать статическую цену опкода, потом исполнить. Кончился газ, машина встаёт с ошибкой out of gas (OutOfGas).

impl Machine {
    /// Исполняет ровно один опкод. None это «продолжаем», Some это «остановились».
    /// На этом строится и обычный прогон, и пошаговый отладчик для виджета.
    pub fn step(&mut self) -> Option<ExecResult> {
        let op = match self.code.get(self.pc) {
            Some(&op) => op,
            None => return Some(ExecResult::Stop), // за концом кода это STOP
        };
        if let Err(err) = self.charge(static_cost(op)) {
            return Some(ExecResult::Halt(err));
        }
        match self.exec(op) {
            Ok(None) => None,
            Ok(Some(result)) => Some(result),
            Err(err) => Some(ExecResult::Halt(err)),
        }
    }
}

Тарифы: сколько стоит опкод

Откуда step берёт цену? Из таблицы тарифов. Имена констант мы сохранили в духе жёлтой книги (yellow paper), чтобы ты узнавал их в документации EVM:

Тариф	Газ	Опкоды
G_ZERO	0	STOP, RETURN, REVERT
G_JUMPDEST	1	JUMPDEST
G_BASE	2	POP, PC, MSIZE, GAS, CALLER, CALLVALUE, CALLDATASIZE
G_VERYLOW	3	почти вся арифметика, PUSH, DUP, SWAP, MLOAD, MSTORE
G_LOW	5	MUL, DIV, MOD
G_MID	8	ADDMOD, MULMOD, JUMP
G_HIGH	10	JUMPI, EXP (базовая часть)
G_KECCAK256	30	KECCAK256, плюс G_KECCAK256_WORD = 6 за каждое слово входа
G_COPY_WORD	3	CALLDATACOPY, за каждое слово копии
G_MEMORY	3	линейная часть расширения памяти
G_SLOAD	100	SLOAD
G_SSTORE	2900	SSTORE

Это сознательное упрощение. В настоящем EVM цены тоньше: холодный и горячий доступ к хранилищу (EIP-2929), возвраты газа при обнулении слота, переходные состояния SSTORE. Нам важен сам механизм (работа стоит газа, газ кончается, машина встаёт), а не попадание в цену mainnet до единицы: значения близки к жёлтой книге, чтобы порядок был правдоподобным.

Раздаёт тарифы функция static_cost. Имена вроде STOP или MLOAD в ней это константы с байтами опкодов из соседнего модуля (STOP = 0x00, ADD = 0x01, те же байты, что в диспетчере ниже):

/// Статическая цена опкода: то, что списывается всегда, ещё до исполнения.
/// Динамические надбавки (слова keccak, копирование calldata, расширение
/// памяти) считаются отдельно прямо в интерпретаторе.
pub fn static_cost(op: u8) -> u64 {
    use opcode::*;
    match op {
        STOP | RETURN | REVERT => G_ZERO,
        JUMPDEST => G_JUMPDEST,
        POP | PC | MSIZE | GAS | CALLER | CALLVALUE | CALLDATASIZE => G_BASE,
        ADD | SUB | LT | GT | EQ | ISZERO | AND | OR | XOR | NOT | BYTE | SHL | SHR
        | CALLDATALOAD | MLOAD | MSTORE | MSTORE8 => G_VERYLOW,
        MUL | DIV | MOD => G_LOW,
        ADDMOD | MULMOD | JUMP => G_MID,
        JUMPI | EXP => G_HIGH,
        KECCAK256 => G_KECCAK256,
        CALLDATACOPY => G_VERYLOW,
        SLOAD => G_SLOAD,
        SSTORE => G_SSTORE,
        PUSH1..=PUSH32 | DUP1..=DUP16 | SWAP1..=SWAP16 => G_VERYLOW,
        // Неизвестный опкод всё равно оборвёт выполнение отдельной ошибкой,
        // цена тут роли не играет.
        _ => G_ZERO,
    }
}