🥇Utreexo: فشرده سازی بسیاری از بیت کوین های UTXO

هی هابر!

در شبکه بیت‌کوین، همه گره‌ها، از طریق اجماع، بر روی مجموعه‌ای از UTXOها به توافق می‌رسند: چند سکه برای خرج کردن، دقیقاً برای چه کسی و تحت چه شرایطی در دسترس است. مجموعه UTXO حداقل مجموعه داده های مورد نیاز برای یک گره اعتبار سنجی است که بدون آن گره نمی تواند اعتبار تراکنش های دریافتی و بلوک های حاوی آنها را تأیید کند.

در این راستا به هر طریق ممکن تلاش می شود تا بازنمایی ذخیره شده این مجموعه کاهش یابد و بدون از دست دادن ضمانت های امنیتی فشرده شود. هرچه حجم داده های ذخیره شده کمتر باشد، فضای دیسک مورد نیاز گره اعتبارسنجی کمتر است، که راه اندازی یک گره اعتبارسنجی را ارزان می کند، به شما امکان می دهد شبکه را گسترش دهید و در نتیجه پایداری شبکه را افزایش دهید.

در این پست ما یک نمونه اولیه Rust از یک پیشنهاد اخیر از یک نویسنده مشترک را ارسال خواهیم کرد کاغذ شبکه لایتنینگ, تادئوس درایجا - Utreexo: یک انباشته مبتنی بر هش پویا که برای مجموعه بیت کوین UTXO بهینه شده است، که امکان کاهش فضای دیسک مورد نیاز برای گره های اعتبارسنجی را فراهم می کند.

مشکل چیه؟

یکی از مشکلات همیشگی بیت کوین مقیاس پذیری آن بوده است. ایده "بانک خود شما" به مشارکت کنندگان شبکه نیاز دارد که سوابق تمام وجوه موجود برای استفاده را نگه دارند. در بیت کوین، وجوه موجود به عنوان مجموعه ای از خروجی های خرج نشده بیان می شود - مجموعه ای UTXO. در حالی که این یک نمایش بصری خاص نیست، از نظر عملکرد اجرایی نسبت به نمایشی که در آن هر "کیف پول" یک "موجودی" به عنوان ورودی جداگانه دارد، سودمند است و همچنین حریم خصوصی را اضافه می کند (به عنوان مثال. coinjo).

تمایز بین تاریخچه تراکنش ها (آنچه بلاک چین نامیده می شود) و وضعیت فعلی سیستم مهم است. تاریخچه تراکنش بیت کوین در حال حاضر حدود 200 گیگابایت فضای دیسک را اشغال می کند و همچنان در حال رشد است. با این حال، وضعیت سیستم بسیار کوچکتر است، در حد 4 گیگابایت، و فقط این واقعیت را در نظر می گیرد که شخصی در حال حاضر صاحب سکه است. حجم این داده ها نیز در طول زمان افزایش می یابد، اما با سرعت بسیار کمتری و گاهی اوقات حتی تمایل به کاهش دارد (به CDPV مراجعه کنید).

مشتریان Light (SPV) تضمین های امنیتی را برای توانایی ذخیره هیچ حداقل حالت (مجموعه UTXO) به جز کلیدهای خصوصی تجارت می کنند.

UTXO و UTXO-set

UTXO (خروجی تراکنش مصرف نشده) خروجی تراکنش خرج نشده است، نقطه پایان سفر هر ساتوشی که در تراکنش ها منتقل می شود. خروجی های خرج نشده به ورودی تراکنش های جدید تبدیل می شوند و بنابراین خرج می شوند (خرج می شوند) و از مجموعه UTXO حذف می شوند.

UTXO های جدید همیشه توسط تراکنش ها ایجاد می شوند:

تراکنش‌های coinbase بدون ورودی: زمانی که ماینرها سکه صادر می‌کنند، UTXOهای جدیدی ایجاد کنید
تراکنش های منظم: UTXO های جدید ایجاد کنید در حالی که مجموعه خاصی از UTXO های موجود را صرف می کنید

فرآیند کار با UTXO:

کیف پول‌ها تعداد سکه‌های موجود برای خرج کردن (موجودی) را بر اساس مقدار UTXO موجود در این کیف پول برای خرج کردن حساب می‌کنند.

هر گره اعتبار سنجی، برای جلوگیری از تلاش های مضاعف، باید مجموعه را نظارت کند از همه UTXO هنگام بررسی هر یک معاملات از هر کدام مسدود کردن.

گره باید منطق داشته باشد:

موارد اضافه شده به مجموعه UTXO
حذف از UTXO-set
بررسی وجود یک UTXO منفرد در یک مجموعه

راه هایی برای کاهش الزامات اطلاعات ذخیره شده در مورد یک مجموعه وجود دارد، در حالی که توانایی افزودن و حذف عناصر، بررسی و اثبات وجود یک عنصر در یک مجموعه با استفاده از انباشته های رمزنگاری.

باتری برای UTXO

ایده استفاده از باتری برای ذخیره چندین UTXO مورد بحث قرار گرفت زودتر.

مجموعه UTXO در حین دانلود بلوک اولیه (IBD) ساخته می شود، به طور کامل و دائمی ذخیره می شود، در حالی که محتویات آن پس از پردازش تراکنش ها از هر بلوک جدید و صحیح شبکه تغییر می کند. این فرآیند به دانلود تقریباً 200 گیگابایت داده بلوک و تأیید صدها میلیون امضای دیجیتال نیاز دارد. پس از تکمیل فرآیند IBD، نتیجه این است که مجموعه UTXO حدود 4 گیگابایت را اشغال خواهد کرد.

با این حال، با انباشته‌کننده‌ها، قواعد اجماع برای وجوه به تأیید و تولید شواهد رمزنگاری کاهش می‌یابد و بار ردیابی وجوه موجود به عهده مالک آن وجوه است که اثبات وجود و مالکیت آنها را ارائه می‌کند.

یک انباشته را می توان نمایش فشرده یک مجموعه نامید. اندازه نمایش ذخیره شده باید ثابت باشد ، یا با توجه به کاردینالیته مجموعه و اندازه خود عنصر به صورت زیرخطی افزایش می یابد، برای مثال ، که در آن n کاردینالیته مجموعه ذخیره شده است.

در این مورد، انباشتگر باید اجازه ایجاد یک اثبات در مورد گنجاندن یک عنصر در مجموعه را بدهد (اثبات گنجاندن) و تأیید مؤثر این اثبات را ممکن کند.

باتری نامیده می شود پویا if به شما امکان می دهد عناصر را اضافه کنید و عناصر را از یک مجموعه حذف کنید.

نمونه ای از چنین باتری می تواند باشد Acumulator 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

از آنجایی که ما از درختان مرکل استفاده می کنیم، والد هر یک از دو گره یک گره است که هش هش گره های فرزند را ذخیره می کند:

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[..])
}

نویسنده اشاره می کند که برای جلوگیری از حملات توصیف شده توسط چارلز بولاگه، پیر آلن فوکو، آدی شامیر و سباستین زیمر در
دومین حمله 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
    }
}

فرآیند ایجاد یک اثبات

بررسی اثبات برای یک عنصر

بررسی اثبات گنجاندن یک عنصر به دنبال کردن مسیر 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

حذف اقلام

برای حذف سلول از باتری، باید شواهد معتبری ارائه کنید که سلول در آنجا وجود دارد. با استفاده از داده های اثبات، می توان عناصر ریشه جدیدی از انباشته را محاسبه کرد که اثبات داده شده دیگر برای آنها صادق نخواهد بود.

الگوریتم به شرح زیر است:

همانند علاوه بر این، مجموعه ای از سبدهای خالی مربوط به درختان مرکل را با ارتفاعی برابر با توان دو از شاخص سبد سازماندهی می کنیم.
ما عناصر را از مراحل مسیر مرکل در سبدها وارد می کنیم. شاخص سبد برابر با تعداد گام فعلی است
عنصر ریشه ای را که مسیر از اثبات به آن منتهی می شود حذف می کنیم
همانند افزودن، عناصر ریشه جدید را با ترکیب عناصر از سبدها به صورت جفت و انتقال نتیجه اتحاد به سبد بعدی محاسبه می کنیم.

رمز

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

فرآیند حذف عنصر "A":

ادغام در یک شبکه موجود

با استفاده از انباشتگر پیشنهادی، گره ها می توانند از استفاده از DB برای ذخیره همه UTXO ها اجتناب کنند در حالی که هنوز می توانند مجموعه UTXO را تغییر دهند. با این حال، مشکل کار با شواهد به وجود می آید.

بیایید گره اعتبار سنجی را که از انباشت کننده UTXO استفاده می کند، فراخوانی کنیم فشرده - جمع و جور (گره حالت فشرده)، و اعتباردهنده بدون انباشته است کامل (گره کامل). وجود دو کلاس از گره ها برای ادغام آنها در یک شبکه مشکل ایجاد می کند، زیرا گره های فشرده نیاز به اثبات وجود UTXO دارند، که در تراکنش ها صرف می شوند، در حالی که گره های کامل این کار را نمی کنند. اگر همه گره‌های شبکه به طور همزمان و هماهنگ به استفاده از Utreexo تغییر ندهند، گره‌های فشرده عقب مانده و نمی‌توانند در شبکه بیت‌کوین کار کنند.

برای حل مشکل ادغام گره های فشرده در شبکه، پیشنهاد می شود یک کلاس اضافی از گره ها معرفی شود - پل ها. گره پل یک گره کامل است که باتری Utreexo و ضد روشن شدن را نیز ذخیره می کند از همه UTXO از UTXO-set. پل‌ها هش‌های جدید را محاسبه می‌کنند و با رسیدن بلوک‌های جدید تراکنش‌ها، انباشتگر و اثبات‌ها را به‌روزرسانی می‌کنند. نگهداری و به روز رسانی انباشتگر و اثبات بار محاسباتی اضافی بر چنین گره هایی تحمیل نمی کند. پل ها فضای دیسک را قربانی می کنند: نیاز به مرتب نگه داشتن چیزها هش، در مقایسه با هش برای گره های فشرده، که در آن n قدرت مجموعه UTXO است.

معماری شبکه

پل ها امکان افزودن تدریجی گره های فشرده به شبکه را بدون تغییر نرم افزار گره های موجود فراهم می کنند. گره های کامل مانند قبل عمل می کنند و تراکنش ها و بلوک ها را بین خود توزیع می کنند. گره های پل، گره های کاملی هستند که به علاوه داده های باتری Utreexo و مجموعه ای از اثبات های گنجاندن را ذخیره می کنند. از همه UTXO در حال حاضر. گره پل خودش را به این شکل تبلیغ نمی کند و وانمود می کند که یک گره کامل برای همه گره های کامل و یک گره فشرده برای همه گره های فشرده است. اگرچه پل ها هر دو شبکه را به هم متصل می کنند، اما در واقع فقط باید آنها را در یک جهت متصل کنند: از گره های کامل موجود تا گره های فشرده. این امکان پذیر است زیرا قالب تراکنش نیازی به تغییر ندارد و اثبات UTXO برای گره های فشرده می تواند کنار گذاشته شود، بنابراین هر گره فشرده می تواند به طور مشابه تراکنش ها را برای همه شرکت کنندگان شبکه بدون مشارکت گره های پل پخش کند.

نتیجه

ما به باتری Utreexo نگاه کردیم و نمونه اولیه آن را در Rust پیاده سازی کردیم. ما به معماری شبکه نگاه کردیم که امکان ادغام گره های مبتنی بر باتری را فراهم می کند. مزیت گیره های فشرده اندازه داده های ذخیره شده است که از نظر لگاریتمی به توان مجموعه UTXO ها بستگی دارد که نیاز به فضای دیسک و عملکرد ذخیره سازی برای چنین گره هایی را تا حد زیادی کاهش می دهد. نقطه ضعف، ترافیک گره اضافی برای انتقال اثبات است، اما تکنیک های تجمیع شواهد (زمانی که یک اثبات وجود چندین عنصر را ثابت می کند) و حافظه پنهان می تواند به حفظ ترافیک در محدوده های قابل قبول کمک کند.

مراجع:

منبع: www.habr.com

Utreexo: فشرده سازی بسیاری از بیت کوین های UTXO

مشکل چیه؟

UTXO و UTXO-set

باتری برای UTXO

Utreexo

ساختار منطقی باتری

افزودن عناصر

ایجاد یک اثبات برای عناصر اضافه شده

بررسی اثبات برای یک عنصر

حذف اقلام

ادغام در یک شبکه موجود

معماری شبکه

نتیجه

اضافه کردن نظر انصراف از پاسخ