Консенсус и форки: самая тяжёлая цепь

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

Идея

Из урока 16 мы помним: узел хранит дерево блоков, потому что форки неизбежны. Теперь нужно правило, какая ветка дерева главная. Правило Накамото из урока 11 тут становится кодом: главной считается ветка с наибольшей накопленной работой, а не самая длинная по числу блоков (помним из урока 15: при смене сложности длина и работа расходятся).

Когда приходит блок, удлиняющий побочную ветку так, что она перевешивает текущую, узел делает реорганизацию: откатывает состояние до общего предка и проигрывает новую ветку. Это «самозалечивание форка» из урока 11, и сейчас мы увидим, какой ценой.

Хранилище: блок плюс накопленная работа

Каждый блок храним вместе с накопленной до него работой, чтобы сравнивать ветки за константу. Здесь же живут две константы узла, которые мы обещали в уроке про P2P.

/// Фиксированная эмиссия за блок (без комиссий). В реальной сети она убывает
/// (halving у Bitcoin); у нас константа, чтобы не отвлекаться.
pub const BLOCK_REWARD: u64 = 50;

/// Сколько транзакций влезает в блок (грубый лимит, аналог лимита газа/веса).
pub const MAX_BLOCK_TXS: usize = 512;

/// Запись о блоке плюс накопленная до него работа.
struct Entry {
    block: Block,
    cumulative_work: u128,  // сумма work(bits) по всем блокам до этого включительно
}

/// Дерево блоков с выбором самой тяжёлой ветки.
pub struct Blockchain {
    entries: HashMap<Hash, Entry>,
    genesis: Hash,
    tip: Hash,
}

Цепь рождается из genesis-блока, и даже ему узел не верит на слово: genesis проходит те же проверки, что обычный блок, только без родителя.

impl Blockchain {
    /// Заводит цепь из genesis-блока. Genesis проверяется как обычный блок, но
    /// без родителя; его состояние (coinbase) должно быть валидным.
    pub fn new(genesis: Block) -> Result<Blockchain, ChainError> {
        if genesis.header.parent != Hash::ZERO || genesis.header.height != 0 {
            return Err(ChainError::BadHeight);
        }
        if !genesis.merkle_root_matches() {
            return Err(ChainError::BadMerkleRoot);
        }
        if !header_meets_target(&genesis.header) {
            return Err(ChainError::BadProofOfWork);
        }
        // Genesis обязан давать валидное стартовое состояние.
        let mut state = State::new();
        state.apply_block(&genesis, BLOCK_REWARD).map_err(ChainError::BadState)?;

        let hash = genesis.hash();
        let cumulative_work = pow::work(genesis.header.bits);
        let mut entries = HashMap::new();
        entries.insert(hash, Entry { block: genesis, cumulative_work });
        Ok(Blockchain { entries, genesis: hash, tip: hash })
    }
}

Приём блока: все правила разом

Сначала словарь: как может закончиться приём блока и почему блок могут выгнать.

/// Чем закончился приём блока.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum AddOutcome {
    /// Блок продолжил текущую главную цепь: вершина сдвинулась вперёд.
    Extended,
    /// Блок сохранён, но лежит на более лёгкой ветке: вершина не сдвинулась.
    SideChain,
    /// Побочная ветка перевесила: реорганизация. reverted это транзакции
    /// откатанных блоков, applied это транзакции новой ветки.
    Reorg {
        reverted: Vec<Transaction>,
        applied: Vec<Transaction>,
    },
}

/// Почему блок отвергнут.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ChainError {
    /// Блок с таким хешем уже есть.
    Duplicate,
    /// Родитель неизвестен: блок-сирота (буфер сирот мы не держим).
    UnknownParent,
    /// Высота не равна высоте родителя плюс один.
    BadHeight,
    /// Хеш не уложился в собственную сложность: работа не сделана.
    BadProofOfWork,
    /// Корень Меркла в заголовке не сходится с телом.
    BadMerkleRoot,
    /// Сложность блока не та, что предписывает правило подстройки.
    BadDifficulty { expected: u32, got: u32 },
    /// Переход состояния невалиден (плохой nonce, нехватка средств и т.п.).
    BadState(StateError),
}

add_block это место, где сходятся все проверки блока из прошлых уроков: работа сделана (PoW), связывание верное (высота, родитель), сложность та, что предписана подстройкой, и переход состояния валиден. Только пройдя всё, блок попадает в дерево, и лишь потом мы решаем, двигать ли вершину.

impl Blockchain {
    pub fn add_block(&mut self, block: Block) -> Result<AddOutcome, ChainError> {
        let hash = block.hash();
        if self.entries.contains_key(&hash) {
            return Err(ChainError::Duplicate);
        }
        let parent = self.entries.get(&block.header.parent).ok_or(ChainError::UnknownParent)?;
        if block.header.height != parent.block.header.height + 1 {
            return Err(ChainError::BadHeight);
        }
        if !block.merkle_root_matches() {
            return Err(ChainError::BadMerkleRoot);
        }
        if !header_meets_target(&block.header) {
            return Err(ChainError::BadProofOfWork);
        }
        let expected = self.expected_bits(&parent.block);
        if block.header.bits != expected {
            return Err(ChainError::BadDifficulty { expected, got: block.header.bits });
        }
        // Переход состояния: берём состояние родителя и применяем блок.
        let parent_work = parent.cumulative_work;
        let mut state = self.state_at(block.header.parent)?;
        state.apply_block(&block, BLOCK_REWARD).map_err(ChainError::BadState)?;

        let cumulative_work = parent_work + pow::work(block.header.bits);
        let old_tip = self.tip;
        let best_work = self.entries[&old_tip].cumulative_work;
        self.entries.insert(hash, Entry { block, cumulative_work });

        if cumulative_work <= best_work {
            return Ok(AddOutcome::SideChain); // ветка не перевесила
        }
        let parent_hash = self.entries[&hash].block.header.parent;
        self.tip = hash;
        if parent_hash == old_tip {
            Ok(AddOutcome::Extended)
        } else {
            let (reverted, applied) = self.diff_branches(old_tip, hash);
            Ok(AddOutcome::Reorg { reverted, applied })
        }
    }
}

Назовём три исхода прямо. Extended: блок продолжил текущую цепь, вершина шагнула вперёд. SideChain: блок валиден и сохранён, но его ветка легче, вершина на месте. Reorg: побочная ветка перевесила, вершина переехала на другую ветку, и надо разобраться с транзакциями.

Проверка expected_bits заслуживает собственного листинга: сложность блока узел не берёт из блока на веру, а вычисляет сам по правилу подстройки из урока про майнинг. Содержательный момент здесь это якорь окна: на границе ретаргета мы отступаем на 15 шагов назад по ветке родителя, охватывая окно в 16 блоков, а не идём по главной цепи. Поэтому побочная ветка честно считает собственную сложность, даже когда главная цепь смотрит в другую сторону.

impl Blockchain {
    /// Сложность, которую обязан нести ребёнок блока parent. На границе окна
    /// подстройки (высота кратна RETARGET_INTERVAL) считаем новую по времени
    /// последних RETARGET_INTERVAL блоков, иначе наследуем сложность родителя.
    pub fn expected_bits(&self, parent: &Block) -> u32 {
        let child_height = parent.header.height + 1;
        if !child_height.is_multiple_of(pow::RETARGET_INTERVAL) {
            return parent.header.bits;
        }
        // Идём на RETARGET_INTERVAL - 1 шагов назад от родителя: якорь окна.
        let mut anchor = parent.hash();
        for _ in 0..(pow::RETARGET_INTERVAL - 1) {
            anchor = match self.entries.get(&anchor) {
                Some(e) => e.block.header.parent,
                None => return parent.header.bits,
            };
        }
        let Some(first) = self.entries.get(&anchor) else {
            return parent.header.bits;
        };
        let timespan = parent.header.timestamp.saturating_sub(first.block.header.timestamp);
        pow::retarget(parent.header.bits, timespan)
    }
}

И ещё одна развилка, спрятанная в одном знаке. Сравнение cumulative_work <= best_work строгое в пользу текущей вершины: ветка равной работы её не двигает. Это правило first-seen: из двух одинаково тяжёлых веток узел держится той, которую увидел первой, и ждёт, пока одна перевесит. Альтернатива, которую всерьёз обсуждали в работах про selfish mining: при равенстве выбирать случайно. Эгоистичному майнеру, который придерживает намайненные блоки и публикует их в момент появления честного конкурента, first-seen выгоден, если у него хорошие связи: он выигрывает гонку доставки и его блок оказывается «первым увиденным» у большинства. Случайный выбор срезает это преимущество примерно вдвое, делая selfish mining больнее. Мы всё же берём first-seen: поведение узла воспроизводимо в тестах, а случайность в правиле выбора это управляемый, но всё-таки недетерминизм. Заметь, сеть он не расколет: выбор вершины локален и временен, применение блоков остаётся детерминированным.