Utreexo: компресиране на много UTXO Bitcoin

Хей Хабр!

В биткойн мрежата всички възли чрез консенсус се споразумяват за набор от UTXO: колко монети са налични за харчене, за кого точно и при какви условия. Наборът UTXO е минималният набор от данни, необходими за възел на валидатор, без който възелът няма да може да провери валидността на входящите транзакции и блоковете, които ги съдържат.

В тази връзка се правят опити по всякакъв възможен начин да се намали съхраненото представяне на този набор, да се компресира, без да се губят гаранции за сигурност. Колкото по-малък е обемът на съхранените данни, толкова по-ниски са изискванията за дисково пространство на възела на валидатора, което прави стартирането на възел на валидатор евтино, позволява ви да разширите мрежата и по този начин да увеличите стабилността на мрежата.

В тази публикация ще публикуваме прототип на Rust на скорошно предложение от съавтор Хартия Lightning Network, Тадеус Дриджа - Utreexo: динамичен акумулатор, базиран на хеш, оптимизиран за набора Bitcoin UTXO, което позволява намаляване на изискванията за дисково пространство за валидиращи възли.

Какъв е проблемът?

Един от вечните проблеми на биткойн е неговата мащабируемост. Идеята за „вашата собствена банка“ изисква участниците в мрежата да водят записи за всички средства, налични за използване. В биткойн наличните средства се изразяват като набор от неизразходвани изходи - UTXO-набор. Въпреки че това не е особено интуитивно представяне, то е полезно по отношение на производителността на внедряването спрямо представяне, в което всеки „портфейл“ има „салдо“ като отделен запис и също така добавя поверителност (напр. CoinJoin).

Важно е да се прави разлика между историята на транзакциите (това, което се нарича блокчейн) и текущото състояние на системата. Историята на биткойн транзакциите в момента заема около 200 GB дисково пространство и продължава да расте. Състоянието на системата обаче е много по-малко, от порядъка на 4 GB, и взема предвид само факта, че някой в ​​момента притежава монети. Обемът на тези данни също се увеличава с времето, но с много по-бавна скорост и понякога дори има тенденция да намалява (вижте CDPV).

Леките клиенти (SPV) търгуват гаранции за сигурност за възможността да не съхраняват минимално състояние (UTXO-набор), освен частни ключове.

UTXO и UTXO-комплект

UTXO (Unspent Transaction Output) е неизразходваният изход от транзакция, крайната точка на пътуването на всеки сатоши, прехвърлен в транзакции. Неизразходваните изходи стават входове за нови транзакции и по този начин се изразходват (разходват) и премахват от UTXO-набора.

Новите UTXO винаги се създават чрез транзакции:

• coinbase транзакции без входове: създайте нови UTXO, когато копачите издават монети
• редовни транзакции: създайте нови UTXO, докато изразходвате определен набор от съществуващи UTXO

Процес на работа с UTXO:

Портфейлите отчитат броя монети, налични за харчене (салдо) въз основа на количеството UTXO, достъпно за този портфейл за харчене.

Всеки валидиращ възел, за да предотврати двойни опити за харчене, трябва да наблюдава набора всички UTXO при проверка всеки сделки всеки блок.

Възелът трябва да има логика:

• Допълнения към UTXO-set
• Изтривания от UTXO-set
• Проверка на наличието на един UTXO в комплект

Има начини да се намалят изискванията за съхранена информация за набор, като същевременно се запази възможността за добавяне и премахване на елементи, проверка и доказване на съществуването на елемент в набор, използвайки криптографски акумулатори.

Батерии за UTXO

Идеята за използване на батерии за съхранение на множество UTXO беше обсъдено по-рано.

UTXO-наборът се изгражда в движение, по време на първоначалното изтегляне на блок (IBD), съхранява се изцяло и постоянно, докато съдържанието му се променя след обработка на транзакции от всеки нов и правилен блок на мрежата. Този процес изисква изтегляне на приблизително 200 GB блокови данни и проверка на стотици милиони цифрови подписи. След като IBD процесът приключи, най-важното е, че UTXO-наборът ще заема около 4 GB.

При акумулаторите обаче правилата за консенсус за средствата се свеждат до проверка и генериране на криптографски доказателства, а тежестта за проследяване на наличните средства се прехвърля върху собственика на тези средства, който предоставя доказателство за тяхното съществуване и собственост.

Акумулатор може да се нарече компактно представяне на набор. Размерът на съхраненото представяне трябва да бъде или постоянен или да се увеличи сублинейно по отношение на кардиналността на набора и размера на самия елемент, например , където n е мощността на съхраненото множество.

В този случай акумулаторът трябва да позволява генериране на доказателство за включването на елемент в набора (доказателство за включване) и да позволява ефективна проверка на това доказателство.

Батерията се нарича динамичен if ви позволява да добавяте елементи и премахвате елементи от набор.

Пример за такава батерия би бил RSA акумулатор, предложен от Boneh, Bunz, Fisch през декември 2018 г. Такъв акумулатор има постоянен размер на съхраненото представяне, но изисква присъствие споделена тайна (доверена настройка). Това изискване отрича приложимостта на такъв акумулатор за ненадеждни мрежи като биткойн, тъй като изтичането на данни по време на тайно генериране може да позволи на нападателите да създадат фалшиво доказателство за съществуването на UTXO, мамейки възли с UTXO-набор, базиран на такъв акумулатор.

Utreexo

Дизайнът на Utreexo, предложен от Thaddeus Dryja, прави възможно създаването динамичен батерия без доверена настройка.

Utreexo е гора от перфектни двоични файлове Меркле дървета и е развитие на идеите, представени в Ефективни асинхронни акумулатори за разпределени pki, добавяйки възможност за премахване на елементи от набор.

Логическа структура на батерията

Батерийните клетки са подредени в гора от идеални двоични дървета. Дърветата са подредени по височина. Това представяне е избрано като най-визуално и ви позволява да визуализирате сливането на дървета по време на операции на батерията.

Авторът отбелязва, че тъй като всички дървета в гората са идеални, тяхната височина се изразява като степен на две, точно както всяко естествено число може да бъде представено като сбор от степени на две. Съответно всеки набор от листа може да бъде групиран в двоични дървета и във всички случаи добавянето на нов елемент изисква знания само за коренните възли на съхранените дървета.

По този начин съхраненото представяне на акумулатора на Utreexo е списък от коренни възли (корен на Merkle), а не цялата гора от дървета.

Нека представим списъка с коренни елементи като Vec<Option<Hash>>. Тип по избор Option<Hash> показва, че коренният елемент може да липсва, което означава, че в акумулатора няма дърво с подходяща височина.

/// SHA-256 хеш
#[derive(Copy, Clone, Hash, Eq, PartialEq)]
pub struct Hash(pub [u8; 32]);

#[derive(Debug, Clone)]
pub struct Utreexo {
    pub roots: Vec<Option<Hash>>,
}

impl Utreexo {
    pub fn new(capacity: usize) -> Self {
        Utreexo {
            roots: vec![None; capacity],
        }
    }
}

Добавяне на елементи

Първо, нека опишем функцията parent(), който разпознава родителския възел за два дадени елемента.

функция parent().

Тъй като използваме дървета на Merkle, родителят на всеки от двата възела е един възел, който съхранява хеша на конкатенацията на хешовете на дъщерните възли:

fn hash(bytes: &[u8]) -> Hash {
    let mut sha = Sha256::new();
    sha.input(bytes);
    let res = sha.result();
    let mut res_bytes = [0u8; 32];
    res_bytes.copy_from_slice(res.as_slice());

    Hash(res_bytes)
}

fn parent(left: &Hash, right: &Hash) -> Hash {
    let concat = left
        .0
        .into_iter()
        .chain(right.0.into_iter())
        .map(|b| *b)
        .collect::<Vec<_>>();

    hash(&concat[..])
}

Авторът отбелязва, че за предотвратяване на атаките, описани от Шарл Буйае, Пиер-Ален Фуке, Ади Шамир и Себастиен Цимер в
Втори предобразни атаки срещу дитъринг хеш функции, в допълнение към двата хеша, към конкатенацията трябва да се добави и височината вътре в дървото.

Докато добавяте елементи към акумулатора, трябва да следите кои основни елементи се променят. Следвайки пътя на промяна на основните елементи за всеки елемент, който добавяте, можете по-късно да създадете доказателство за присъствието на тези елементи.

Проследявайте промените, докато ги добавяте

За да проследим направените промени, нека декларираме структурата Update, който ще съхранява данни за промените на възлите.

#[derive(Debug)]
pub struct Update<'a> {
    pub utreexo: &'a mut Utreexo,
    // ProofStep хранит "соседа" элемента и его положение
    pub updated: HashMap<Hash, ProofStep>,
}

За да добавите елемент към батерията, трябва:

• Създайте масив от кошници с коренни елементи new_roots и поставете съществуващите основни елементи там, по един за всяка кофа:

Код

let mut new_roots = Vec::new();

for root in self.roots.iter() {
    let mut vec = Vec::<Hash>::new();
    if let Some(hash) = root {
        vec.push(*hash);
    }

    new_roots.push(vec);
}

• Добавете елементите за добавяне (масив insertions) към първата количка new_roots[0]:

Код

new_roots[0].extend_from_slice(insertions);

• Обединете елементите, добавени в първата кошница с останалите:
  • За всички колички с повече от един артикул:
    1. Вземете два елемента от края на кошницата, изчислете техния родител, премахнете и двата елемента
    2. Добавете изчисления родител към следващата количка

Код

for i in 0..new_roots.len() {
    while new_roots[i].len() > 1 {
        // Объединяем два элемента в один и удаляем их
        let a = new_roots[i][new_roots[i].len() - 2];
        let b = new_roots[i][new_roots[i].len() - 1];
        new_roots[i].pop();
        new_roots[i].pop();
        let hash = self.parent(&a, &b);

        // Наращиваем количество корзин если требуется
        if new_roots.len() <= i + 1 {
            new_roots.push(vec![]);
        }

        // Помещаем элемент в следующую корзину
        new_roots[i + 1].push(hash);

        // Не забываем отслеживать изменения;
        // это пригодится для генерации доказательства добавления элементов
        updated.insert(a, ProofStep { hash: b, is_left: false });
        updated.insert(b, ProofStep {hash: a, is_left: true });
    }
}

• Преместете основните елементи от кошчетата към резултантния акумулаторен масив

Код

for (i, bucket) in new_roots.into_iter().enumerate() {
    // Наращиваем аккумулятор если требуется
    if self.roots.len() <= i {
        self.roots.push(None);
    }

    if bucket.is_empty() {
        self.roots[i] = None;
    } else {
        self.roots[i] = Some(bucket[0]);
    }
}

Създаване на доказателство за добавени елементи

Доказателство за включване на клетката в батерията (Proof) ще служи като Пътят Меркъл, състоящ се от верига ProofStep. Ако пътят не води до никъде, тогава доказателството е невярно.

/// Единичный шаг на пути к элементу в дереве Меркла.
#[derive(Debug, Copy, Clone)]
pub struct ProofStep {
    pub hash: Hash,
    pub is_left: bool,
}

/// Доказательство включения элемента. Содержит сам элемент и путь к нему.
#[derive(Debug, Clone)]
pub struct Proof {
    pub steps: Vec<ProofStep>,
    pub leaf: Hash,
}

Използване на информацията, получена по-рано при добавяне на елемент (структура Update), можете да създадете доказателство, че към батерията е добавен елемент. За да направим това, преминаваме през таблицата с направени промени и добавяме всяка стъпка към пътя на Merkle, което впоследствие ще служи като доказателство:

Код

impl<'a> Update<'a> {
    pub fn prove(&self, leaf: &Hash) -> Proof {
        let mut proof = Proof {
            steps: vec![],
            leaf: *leaf,
        };

        let mut item = *leaf;
        while let Some(s) = self.updated.get(&item) {
            proof.steps.push(*s);
            item = parent(&item, &s);
        }

        proof
    }
}

Процес на създаване на доказателство

Проверка на доказателството за елемент

Проверката на доказателството за включване на елемент се свежда до следване на пътя на Merkle, докато не доведе до съществуващ основен елемент:

pub fn verify(&self, proof: &Proof) -> bool {
    let n = proof.steps.len();
    if n >= self.roots.len() {
        return false;
    }

    let expected = self.roots[n];
    if let Some(expected) = expected {
        let mut current_parent = proof.leaf;
        for s in proof.steps.iter() {
            current_parent = if s.is_left {
                parent(&s.hash, &current_parent)
            } else {
                parent(&current_parent, &s.hash)
            };
        }

        current_parent == expected
    } else {
        false
    }
}

Визуално:

Процес на проверка на доказателството за A

Премахване на елементи

За да премахнете клетка от батерия, трябва да предоставите валидни доказателства, че клетката е там. Използвайки данните от доказателството, е възможно да се изчислят нови коренни елементи на акумулатора, за които даденото доказателство вече няма да е вярно.

Алгоритъмът е следният:

1. Както при добавянето, ние организираме набор от празни кошници, съответстващи на дървета Merkle с височина, равна на степен две от индекса на кошницата
2. Вмъкваме елементи от стъпалата на пътеката Merkle в кошниците; индексът на кошницата е равен на номера на текущата стъпка
3. Премахваме основния елемент, до който води пътят от доказателството
4. Както при добавянето, ние изчисляваме нови коренни елементи, като комбинираме елементи от кошници по двойки и преместваме резултата от обединението в следващата кошница

Код

fn delete(&self, proof: &Proof, new_roots: &mut Vec<Vec<Hash>>) -> Result<(), ()> {
    if self.roots.len() < proof.steps.len() || self.roots.get(proof.steps.len()).is_none() {
        return Err(());
    }

    let mut height = 0;
    let mut hash = proof.leaf;
    let mut s;

    loop {
        if height < new_roots.len() {
            let (index, ok) = self.find_root(&hash, &new_roots[height]);
            if ok {
                // Remove hash from new_roots
                new_roots[height].remove(index);

                loop {
                    if height >= proof.steps.len() {
                        if !self.roots[height]
                            .and_then(|h| Some(h == hash))
                            .unwrap_or(false)
                        {
                            return Err(());
                        }

                        return Ok(());
                    }

                    s = proof.steps[height];
                    hash = self.parent(&hash, &s);
                    height += 1;
                }
            }
        }

        if height >= proof.steps.len() {
            return Err(());
        }

        while height > new_roots.len() {
            new_roots.push(vec![]);
        }

        s = proof.steps[height];
        new_roots[height].push(s.hash);
        hash = self.parent(&hash, &s);
        height += 1;
    }
}

Процесът на премахване на елемент "А":

Интегриране в съществуваща мрежа

Използвайки предложения акумулатор, възлите могат да избегнат използването на DB за съхраняване на всички UTXO, като същевременно могат да променят UTXO-набора. Възниква обаче проблемът с работата с доказателства.

Нека извикаме възела на валидатора, който използва UTXO акумулатора компактен (възел с компактно състояние), а валидаторът без акумулатор е пълен (пълен възел). Съществуването на два класа възли създава проблем за интегрирането им в една мрежа, тъй като компактните възли изискват доказателство за съществуването на UTXO, които се изразходват в транзакции, докато пълните възли не изискват. Ако всички мрежови възли не преминат едновременно и по координиран начин към използване на Utreexo, тогава компактните възли ще бъдат изоставени и няма да могат да работят в биткойн мрежата.

За да се реши проблемът с интегрирането на компактни възли в мрежата, се предлага да се въведе допълнителен клас възли - мостове. Мостовият възел е пълен възел, който също така съхранява батерията на Utreexo и доказателството за включване всички UTXO от UTXO-set. Мостовете изчисляват нови хешове и актуализират акумулатора и доказателствата, когато пристигнат нови блокове транзакции. Поддържането и актуализирането на акумулатора и доказателствата не налага допълнително изчислително натоварване на такива възли. Мостовете жертват дисково пространство: трябва да поддържат нещата организирани хешове, в сравнение с хешове за компактни възли, където n е мощността на набора UTXO.

Мрежова архитектура

Мостовете позволяват постепенно добавяне на компактни възли към мрежата, без да се променя софтуерът на съществуващите възли. Пълните възли работят както преди, разпределяйки транзакции и блокове помежду си. Мостовите възли са пълни възли, които допълнително съхраняват данни за батерията на Utreexo и набор от доказателства за включване за всички UTXO за сега. Мостовият възел не се рекламира като такъв, преструвайки се на пълен възел за всички пълни възли и компактен възел за всички компактни. Въпреки че мостовете свързват двете мрежи заедно, те всъщност трябва да ги свържат само в една посока: от съществуващи пълни възли към компактни възли. Това е възможно, защото форматът на транзакцията не трябва да се променя и UTXO доказателствата за компактни възли могат да бъдат отхвърлени, така че всеки компактен възел може по подобен начин да излъчва транзакции към всички участници в мрежата без участието на мостови възли.

Заключение

Разгледахме батерията Utreexo и внедрихме нейния прототип в Rust. Разгледахме мрежовата архитектура, която ще позволи интегрирането на базирани на батерии възли. Предимството на компактните уловки е размерът на съхранените данни, който зависи логаритмично от мощността на набора UTXO, което значително намалява изискванията за дисково пространство и производителност на съхранение за такива възли. Недостатъкът е допълнителният възлов трафик за предаване на доказателства, но техниките за агрегиране на доказателства (когато едно доказателство доказва съществуването на няколко елемента) и кеширането могат да помогнат за поддържане на трафика в приемливи граници.

Позоваването:

• GitHub на прототипа на Utreexo в Rust
• Тадеус Дриджа - Utreexo: динамичен акумулатор, базиран на хеш, оптимизиран за набора Bitcoin UTXO
• Анимирани илюстрации от статията

Източник: www.habr.com