Накамото-консенсус: PoW и PoS

BFT давал детерминированную финальность, но требовал знать всех голосующих поимённо. Накамото решил консенсус в открытой анонимной сети, где это невозможно: вместо голосования по головам он голосует работой. Разберём proof-of-work и сложность, правило самой длинной цепи, вероятностную финальность и переход к proof-of-stake с его finality gadgets, которые возвращают детерминированную финальность из прошлого урока.

Идея

У BFT была фатальная для открытой сети дыра: чтобы считать кворум 2f+1, надо знать, сколько всего голосующих. Но в публичной сети любой может создать тысячу узлов бесплатно. Это атака Сивиллы: накрутил личностей, набрал кворум, захватил сеть. Голосование по головам в анонимной сети не работает.

Накамото вывернул задачу: пусть голос стоит дефицитного ресурса, который не подделать накруткой личностей. Тогда влияние зависит не от числа узлов, а от вложенного ресурса, и тысяча пустых нод не даёт ничего. У proof-of-work этот ресурс это вычисления (электричество), у proof-of-stake это заблокированный капитал.

Proof-of-work и сложность

Механика proof-of-work стоит на хеше из урока про хеширование. Чтобы предложить блок, майнер должен найти такой nonce, что хеш заголовка блока окажется меньше целевого порога (target). Раз хеш ведёт себя как случайный (лавинный эффект), угадать nonce нельзя, остаётся перебирать. Чем ниже порог, тем меньше подходящих хешей, тем больше перебора, тем дороже блок. Это и есть сложность.

Ключевой трюк: сеть автоматически подстраивает порог, чтобы блок находился в среднем раз в фиксированное время (у Bitcoin раз в 10 минут), сколько бы мощности ни пришло. Удвоилась мощность сети, сложность вырастет вдвое, интервал останется прежним.

Считает это сама сеть, без координатора, по часам блоков. Bitcoin делает пересчёт ровно раз в 2016 блоков (это и есть один период сложности). При темпе 10 минут на блок 2016 блоков должны занимать 20160 минут, то есть около двух недель. Сеть смотрит, сколько времени реально ушло на последние 2016 блоков, и масштабирует порог пропорционально:

новый_target = старый_target × (фактическое_время / 1209600 секунд)

где 1209600 секунд это те самые две недели. Блоки шли быстрее цели, отношение меньше единицы, порог опускается и сложность растёт; шли медленнее, порог поднимается и сложность падает. Чтобы один скачок мощности не выбросил сеть в крайность, поправку зажимают в коридор от 0.25 до 4: за один период сложность не меняется больше чем вчетверо в любую сторону. Так интервал между блоками держится у 10 минут десятилетиями, пока суммарная мощность выросла в триллионы раз.

Проверка работы тривиальна и односторонняя, как и положено хешу: найти nonce дорого, проверить дёшево.

use sha2::{Digest, Sha256};

/// Заголовок валиден, если двойной SHA-256 начинается с `bits` нулевых бит.
/// Чем больше нулей требуется, тем выше сложность.
fn meets_target(header: &[u8], nonce: u64, leading_zero_bits: u32) -> bool {
    let mut h = Sha256::new();
    h.update(header);
    h.update(nonce.to_le_bytes());
    let first = Sha256::digest(h.finalize()); // двойной SHA-256, как в Bitcoin
    // Считаем ведущие нулевые биты дайджеста.
    let mut zeros = 0u32;
    for byte in first {
        if byte == 0 {
            zeros += 8;
        } else {
            zeros += byte.leading_zeros();
            break;
        }
    }
    zeros >= leading_zero_bits
}

/// Майнинг: перебираем nonce, пока хеш не уложится в порог.
fn mine(header: &[u8], leading_zero_bits: u32) -> u64 {
    (0u64..).find(|&nonce| meets_target(header, nonce, leading_zero_bits)).unwrap()
}

fn main() {
    let nonce = mine(b"block #1", 16); // ищем 16 ведущих нулей: секунды работы
    assert!(meets_target(b"block #1", nonce, 16)); // проверка мгновенна
    println!("найден nonce = {nonce}");
}

Подними leading_zero_bits с 16 до 24, и время поиска вырастет в сотни раз, а проверка останется мгновенной. Это и есть асимметрия, на которой стоит безопасность Bitcoin.

Правило самой длинной цепи

Работа защищает один блок, но узлы должны согласиться о всей истории, причём двое могут найти блок почти одновременно и сеть временно расколется на вилку. Накамото разрешает это правилом выбора цепи: главной считается цепь с наибольшей накопленной работой (упрощённо, самая длинная). Майнеры всегда строят на ней.

Почему это сходится. Пока две вилки равны, сеть в раздумье. Но как только на одну из них ляжет следующий блок, она станет длиннее, все майнеры переключатся на неё, и короткая вилка осиротеет (её блоки становятся stale, а транзакции возвращаются в очередь). Расхождения самозалечиваются, потому что продолжать самую длинную цепь всегда выгоднее, чем упорствовать на короткой.

Отсюда же и защита истории. Чтобы переписать блок в глубине, атакующему мало пересчитать его, надо обогнать всю честную сеть и построить более длинную цепь от точки подмены. А честная сеть тем временем не стоит. Если у атакующего меньше половины мощности, он отстаёт навсегда; стоит ему получить больше половины, он обгоняет, и это атака большинства (она же 51 процент).

У простой «самой длинной цепи» есть слабое место: блоки осиротевших вилок выбрасываются и не считаются за работу, даже если честные майнеры реально их посчитали. Это поощряет того, у кого лучше связность, и теряет часть честного труда. Особенно больно это бьёт по цепям с быстрыми блоками: вилки там случаются чаще, и честного труда пропадает больше. Ответ теоретиков называется GHOST: на каждой развилке брать не самую длинную ветку, а ту, к чьему поддереву привязано больше всего работы, включая осиротевшие блоки. Ethereum на PoW часто записывают в пользователи GHOST, но это миф: полное правило он так и не включил, цепь выбиралась по накопленной суммарной сложности (heaviest chain по total difficulty), то есть по сути тем же правилом Накамото. От GHOST Ethereum взял другое: награды за осиротевшие блоки, которые там зовут uncles. Майнер осиротевшего блока получал часть награды, а майнер, сославшийся на него, добавку, и честный труд на вилках не пропадал совсем зря, хотя на выбор цепи uncles не влияли.

Опаснее то, что переписать концовку можно и без половины мощности. Корыстный майнинг (selfish mining, Eyal и Sirer, 2013): майнер находит блок и прячет его, тайно строя приватную цепь. Когда честные публикуют свой блок, он выкидывает заготовленную длиннее и обесценивает чужую работу. Eyal и Sirer доказали, что такая стратегия приносит больше честной доли уже примерно с трети мощности, а при хорошей связности порог опускается к четверти. То есть граница безопасности накамото-консенсуса по факту ниже наивных 50 процентов.