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

Еј Хабр!

Во мрежата на Bitcoin, сите јазли, преку консензус, се согласуваат за збир на UTXOs: колку монети се достапни за трошење, на кого точно и под кои услови. Сетот UTXO е минималниот сет на податоци потребни за јазол за валидатор, без кој јазолот нема да може да ја потврди валидноста на дојдовните трансакции и блоковите што ги содржат.

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

Во овој пост ќе објавиме прототип на Rust на неодамнешниот предлог од коавтор Lightning Network Paper, Тадеус Дрија - Utreexo: динамичен акумулатор базиран на хаш оптимизиран за сетот Bitcoin UTXO, што овозможува намалување на барањата за простор на дискот за валидаторските јазли.

Што е проблемот?

Еден од трајните проблеми на Биткоин е неговата приспособливост. Идејата за „ваша сопствена банка“ бара од учесниците во мрежата да водат евиденција за сите средства достапни за користење. Во Bitcoin, расположливите средства се изразуваат како збир на непотрошени резултати - UTXO-сет. Иако ова не е особено интуитивно претставување, тоа е корисно во однос на перформансите на имплементацијата во однос на претставата во која секој „паричник“ има „баланс“ како посебен запис, а исто така додава приватност (на пр. CoinПридружи се).

Важно е да се направи разлика помеѓу историјата на трансакциите (она што се нарекува блокчејн) и моменталната состојба на системот. Историјата на трансакции на биткоин моментално зафаќа околу 200 GB простор на дискот и продолжува да расте. Сепак, состојбата на системот е многу помала, од редот на 4 GB, и го зема предвид само фактот дека некој моментално поседува монети. Обемот на овие податоци исто така се зголемува со текот на времето, но со многу побавно темпо, а понекогаш дури и има тенденција да се намалува (види CDPV).

Лесните клиенти (SPV) тргуваат со безбедносни гаранции за способноста да не се складира минимална состојба (UTXO-сет) освен приватни клучеви.

UTXO и UTXO-сет

UTXO (Unspent Transaction Output) е излезот на непотрошената трансакција, крајната точка на патувањето на секој Сатоши пренесен во трансакциите. Непотрошените излези стануваат влезови на нови трансакции и на тој начин се трошат (трошат) и се отстрануваат од UTXO-множеството.

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

• coinbase трансакции без влезови: креирајте нови UTXO кога рударите издаваат монети
• редовни трансакции: креирајте нови UTXO додека трошите одреден сет на постоечки UTXO

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

Паричниците го бројат бројот на монети достапни за трошење (баланс) врз основа на износот на UTXO што е достапен за овој паричник за трошење.

Секој валидаторски јазол, за да спречи обиди за двојно трошење, мора да го надгледува множеството Сите UTXO при проверка секој трансакции од секоја блок.

Јазолот мора да има логика:

• Дополнувања на UTXO-сет
• Бришење од UTXO-сет
• Проверка на присуство на еден UTXO во комплет

Постојат начини да се намалат барањата за складирани информации за множество, притоа задржувајќи ја способноста за додавање и отстранување елементи, проверка и докажување на постоењето на елемент во множество користејќи криптографски акумулатори.

Батерии за UTXO

Идејата за користење на батерии за складирање на повеќе UTXO се разговараше порано.

UTXO-сетот е изграден во лет, за време на почетното преземање блок (IBD), зачуван целосно и трајно, додека неговата содржина се менува по обработката на трансакциите од секој нов и правилен блок на мрежата. Овој процес бара преземање приближно 200 GB блок податоци и проверка на стотици милиони дигитални потписи. Откако ќе заврши процесот на IBD, во крајна линија е дека UTXO-сетот ќе зафаќа околу 4 GB.

Меѓутоа, кај акумулаторите, правилата за консензус за средствата се сведуваат на верификација и генерирање на криптографски докази, а товарот за следење на расположливите средства се префрла на сопственикот на тие средства, кој обезбедува доказ за нивното постоење и сопственост.

Акумулаторот може да се нарече компактна претстава на множество. Големината на зачуваната претстава мора да биде или константна , или подлинеарно се зголемува во однос на кардиналноста на множеството и големината на самиот елемент, на пример , каде што n е кардиналноста на зачуваното множество.

Во овој случај, акумулаторот треба да овозможи генерирање на доказ за вклучување на елемент во комплетот (доказ за вклучување) и да овозможи ефикасно да се потврди овој доказ.

Батеријата се вика динамичен ако ви дозволува да додадете елементи и да отстраните елементи од множество.

Пример за таква батерија би бил Акумулатор RSA предложен од Boneh, Bunz, Fisch во декември 2018 година. Таквиот акумулатор има постојана големина на складирана репрезентација, но бара присуство споделена тајна (доверливо поставување). Ова барање ја негира применливоста на таков акумулатор за мрежи без доверба како Bitcoin, бидејќи истекувањето на податоци за време на тајното генерирање може да им овозможи на напаѓачите да создадат лажен доказ за постоењето на UTXO, измамувајќи ги јазлите со UTXO-сет базиран на таков акумулатор.

Утреексо

Дизајнот 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(), кој го препознава родителскиот јазол за два дадени елементи.

Функција родител().

Бидејќи користиме 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[..])
}

Авторот забележува дека за да се спречат нападите опишани од Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir и Sebastien Zimmer во
Втори напади на preimage на измешани хаш функции, покрај двата хаши, на конкатенацијата треба да се додаде и висината во внатрешноста на дрвото.

Како што додавате елементи во акумулаторот, треба да следите кои елементи на коренот се менуваат. Следејќи ја патеката на менување на коренските елементи за секој елемент што го додавате, подоцна можете да конструирате доказ за присуството на овие елементи.

Следете ги промените додека ги додавате

За да ги следиме направените промени, ајде да ја декларираме структурата 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), можете да создадете доказ дека е додаден елемент на батеријата. За да го направите ова, ја поминуваме табелата со направени промени и го додаваме секој чекор на патеката на Меркл, што последователно ќе послужи како доказ:

Код

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
    }
}

Процес на создавање доказ

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

Проверката на доказ за вклучување на елемент се сведува на следење на патеката Меркл додека не доведе до постоечки корен елемент:

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
    }
}

Визуелно:

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

Отстранување на предмети

За да отстраните ќелија од батеријата, мора да обезбедите валиден доказ дека ќелијата е таму. Користејќи ги податоците од доказот, можно е да се пресметаат нови коренски елементи на акумулаторот за кои дадениот доказ повеќе нема да биде вистинит.

Алгоритмот е како што следува:

1. Како и со додавањето, организираме збир на празни корпи што одговараат на дрвјата Меркл со висина еднаква на моќноста на два од индексот на кошницата
2. Вметнуваме елементи од чекорите на патеката Меркле во корпите; индексот на кошницата е еднаков на бројот на тековниот чекор
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-сет. Мостовите пресметуваат нови хаши и ги ажурираат акумулаторот и доказите како што пристигнуваат нови блокови на трансакции. Одржувањето и ажурирањето на акумулаторот и доказите не наметнуваат дополнително пресметковно оптоварување на таквите јазли. Мостовите го жртвуваат просторот на дискот: треба работите да се организираат хаши, во споредба со хашови за компактни јазли, каде што n е моќноста на множеството UTXO.

Мрежна архитектура

Мостовите овозможуваат постепено додавање на компактни јазли во мрежата без промена на софтверот на постоечките јазли. Целосните јазли работат како порано, дистрибуирајќи трансакции и блокови меѓу себе. Мостовите јазли се полни јазли кои дополнително ги складираат податоците за батеријата Utreexo и збир на докази за вклучување за Сите UTXO засега. Јазолот на мостот не се рекламира себеси како таков, преправајќи се дека е целосен јазол за сите полни јазли и компактен јазол за сите компактни. Иако мостовите ги поврзуваат двете мрежи заедно, тие всушност треба да ги поврзат само во една насока: од постоечки полни јазли до компактни јазли. Ова е можно бидејќи форматот на трансакцијата не треба да се менува, а UTXO доказите за компактни јазли може да се отфрлат, така што секој компактен јазол може на сличен начин да емитува трансакции до сите учесници во мрежата без учество на јазли на мост.

Заклучок

Ја погледнавме батеријата Utreexo и го имплементиравме нејзиниот прототип во Rust. Ја разгледавме мрежната архитектура која ќе овозможи интеграција на јазли базирани на батерии. Предноста на компактните фаќања е големината на складираните податоци, која логаритамски зависи од моќноста на множеството UTXO, што во голема мера ги намалува барањата за простор на дискот и перформансите за складирање на таквите јазли. Недостаток е дополнителниот сообраќај на јазли за пренос на докази, но техниките за собирање докази (кога еден доказ докажува постоење на неколку елементи) и кеширањето може да помогнат да се задржи сообраќајот во прифатливи граници.

референци:

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

Извор: www.habr.com