Утрееко: компримовање многих УТСО Битцоин-а

Хеј Хабр!

У Битцоин мрежи, сви чворови се консензусом слажу око скупа УТКСО-а: колико кованица је доступно за потрошњу, коме тачно и под којим условима. УТКСО скуп је минимални скуп података који је потребан за чвор валидатора, без којег чвор неће моћи да провери валидност долазних трансакција и блокова који их садрже.

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

У овом посту ћемо објавити Руст прототип недавног предлога коаутора Лигхтнинг Нетворк Папер, Тхаддеус Дрија - Утрееко: динамички акумулатор заснован на хешу оптимизован за Битцоин УТКСО сет, што омогућава смањење захтева за простором на диску за чворове валидатора.

У чему је проблем?

Један од вишегодишњих проблема Битцоин-а је његова скалабилност. Идеја „сопствене банке“ захтева од учесника мреже да воде евиденцију о свим средствима доступним за коришћење. У Битцоин-у, расположива средства су изражена као скуп непотрошених излаза - УТКСО-сет. Иако ово није нарочито интуитиван приказ, он је користан у смислу перформанси имплементације у односу на репрезентацију у којој сваки „новчаник“ има „равнотежу“ као посебан унос, а такође додаје приватност (нпр. ЦоинЈоин).

Важно је разликовати историју трансакција (оно што се назива блокчејн) и тренутно стање система. Историја Битцоин трансакција тренутно заузима око 200 ГБ простора на диску и наставља да расте. Међутим, стање система је много мање, реда величине 4 ГБ, и узима у обзир само чињеницу да неко тренутно поседује новчиће. Обим ових података се такође повећава током времена, али много спорије и понекад чак има тенденцију да се смањи (види ЦДПВ).

Лаки клијенти (СПВ) тргују безбедносним гаранцијама за могућност чувања минималног стања (УТКСО-сет) осим приватних кључева.

УТКСО и УТКСО-сет

УТКСО (Унспент Трансацтион Оутпут) је излаз непотрошене трансакције, крајња тачка путовања сваког Сатосхија пренетог у трансакцијама. Непотрошени излази постају улази нових трансакција и на тај начин се троше (троше) и уклањају из УТКСО скупа.

Нови УТКСО се увек креирају трансакцијама:

• цоинбасе трансакције без улаза: креирајте нове УТКСО када рудари издају новчиће
• редовне трансакције: креирајте нове УТКСО док трошите одређени скуп постојећих УТКСО

Процес рада са УТКСО:

Новчаници броје број кованица доступних за потрошњу (биланс) на основу количине УТКСО-а који је доступан овом новчанику за потрошњу.

Сваки чвор валидатора, да би се спречили покушаји двоструког трошења, мора да надгледа скуп све УТКСО приликом провере сваки трансакције сваки блокирати.

Чвор мора имати логику:

• Додаци за УТКСО-сет
• Брисања из УТКСО-сета
• Провера присуства једног УТКСО у сету

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

Батерије за УТКСО

Идеја о коришћењу батерија за складиштење више УТКСО расправљали раније.

УТКСО-сет се гради у ходу, током иницијалног преузимања блока (ИБД), чува се у потпуности и трајно, док се његов садржај мења након обраде трансакција из сваког новог и исправног блока мреже. Овај процес захтева преузимање приближно 200 ГБ блок података и проверу стотина милиона дигиталних потписа. Након што је ИБД процес завршен, суштина је да ће УТКСО-сет заузимати око 4 ГБ.

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

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

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

Батерија се зове динамичан иф вам омогућава да додате елементе и уклоните елементе из скупа.

Пример такве батерије би био РСА акумулатор који су предложили Бонех, Бунз, Фисцх у децембру 2018. Такав акумулатор има константну величину ускладиштене репрезентације, али захтева присуство заједничка тајна (поуздано подешавање). Овај захтев негира применљивост таквог акумулатора за мреже без поверења као што је Битцоин, пошто цурење података током тајног генерисања може дозволити нападачима да створе лажни доказ постојања УТКСО, обмањујући чворове са УТКСО-сетом заснованим на таквом акумулатору.

Утрееко

Дизајн Утрееко који је предложио Тхаддеус Дрија омогућава стварање динамичан аккумулатор без поуздано подешавање.

Утрееко је шума савршене бинарности Меркле Треес и представља развој идеја представљених у Ефикасни асинхрони акумулатори за дистрибуиране пки, додајући могућност уклањања елемената из скупа.

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

Батеријске ћелије су распоређене у шуми идеалних бинарних стабала. Дрвеће је поређано по висини. Ова репрезентација је изабрана као највизуелнија и омогућава вам да визуелизујете стапање дрвећа током рада на батерији.

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

Дакле, сачувана репрезентација Утрееко акумулатора је листа коренских чворова (Меркле корен), а не цела шума дрвећа.

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

функција родитељ().

Пошто користимо Меркле стабла, родитељ сваког од два чвора је један чвор који чува хеш конкатенације хешова подређених чворова:

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), можете створити доказ да је елемент додат у батерију. Да бисмо то урадили, пролазимо кроз табелу направљених промена и додајемо сваки корак Меркловој путањи, што ће касније послужити као доказ:

Код

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

Процес уклањања елемента "А":

Интеграција у постојећу мрежу

Користећи предложени акумулатор, чворови могу да избегну коришћење ДБ-а за складиштење свих УТКСО-а, а да и даље могу да промене УТКСО-сет. Међутим, јавља се проблем рада са доказима.

Позовимо чвор валидатора који користи УТКСО акумулатор компактан (чвор компактног стања), а валидатор без акумулатора је комплетан (пун чвор). Постојање две класе чворова ствара проблем за њихову интеграцију у једну мрежу, пошто компактни чворови захтевају доказ постојања УТКСО-а који се троше у трансакцијама, док пуни чворови не. Ако сви мрежни чворови не пређу истовремено и на координисан начин на коришћење Утрееко-а, онда ће компактни чворови бити остављени и неће моћи да раде на Битцоин мрежи.

Да би се решио проблем интеграције компактних чворова у мрежу, предлаже се увођење додатне класе чворова - мостови. Мостни чвор је комплетан чвор који такође чува Утрееко батерију и доказ за укључење све УТКСО из УТКСО-сета. Мостови израчунавају нове хешове и ажурирају акумулатор и доказе како стигну нови блокови трансакција. Одржавање и ажурирање акумулатора и доказа не намеће додатно рачунарско оптерећење таквим чворовима. Мостови жртвују простор на диску: потребно је да ствари буду организоване хеш, у поређењу са хеш за компактне чворове, где је н снага УТКСО скупа.

Архитектура мреже

Мостови омогућавају постепено додавање компактних чворова у мрежу без промене софтвера постојећих чворова. Пуни чворови раде као и раније, дистрибуирајући трансакције и блокове међу собом. Мостови чворови су пуни чворови који додатно чувају Утрееко податке о батерији и скуп доказа о укључивању за све УТКСО за сада. Мостни чвор се не оглашава као такав, претварајући се да је пун чвор за све пуне чворове и компактни чвор за све компактне. Иако мостови повезују обе мреже заједно, они заправо треба да их повежу само у једном правцу: од постојећих пуних чворова до компактних чворова. Ово је могуће јер формат трансакције не мора да се мења, а УТКСО докази за компактне чворове могу да се одбаце, тако да сваки компактни чвор може на сличан начин да емитује трансакције свим учесницима мреже без учешћа чворова за премошћивање.

Закључак

Погледали смо Утрееко батерију и имплементирали њен прототип у Руст. Погледали смо мрежну архитектуру која ће омогућити интеграцију чворова заснованих на батеријама. Предност компактних хватача је величина ускладиштених података, која логаритамски зависи од снаге скупа УТКСО, што у великој мери смањује захтеве за простором на диску и перформансама складиштења за такве чворове. Недостатак је додатни саобраћај чворова за преношење доказа, али технике агрегације доказа (када један доказ доказује постојање више елемената) и кеширање могу помоћи да се саобраћај задржи у прихватљивим границама.

референце:

• ГитХуб прототипа Утрееко у Русту
• Тхаддеус Дрија - Утрееко: динамички акумулатор заснован на хешу оптимизован за Битцоин УТКСО сет
• Анимиране илустрације из чланка

Извор: ввв.хабр.цом