Utreexo: דחיסת UTXO ביטקוין רבים

היי הבר!

ברשת הביטקוין, כל הצמתים, באמצעות קונצנזוס, מסכימים על קבוצה של UTXOs: כמה מטבעות זמינים להוצאה, למי בדיוק ובאילו תנאים. ערכת UTXO היא קבוצת הנתונים המינימלית הנדרשת לצומת אימות, שבלעדיה הצומת לא יוכל לאמת את תקפותן של עסקאות נכנסות והבלוקים המכילים אותן.

בהקשר זה, נעשים ניסיונות בכל דרך אפשרית לצמצם את הייצוג המאוחסן של סט זה, לדחוס אותו מבלי לאבד ערבויות אבטחה. ככל שנפח הנתונים המאוחסנים קטן יותר, כך דרישות שטח הדיסק של צומת האימות נמוכות יותר, מה שהופך את השקת צומת האימות לזולה, מאפשרת להרחיב את הרשת ובכך להגביר את יציבות הרשת.

בפוסט זה נפרסם אב טיפוס של Rust של הצעה אחרונה של מחבר שותף נייר רשת ברק, תאדאוס דרייה - Utreexo: מצבר דינמי מבוסס hash המותאם לסט הביטקוין UTXO, המאפשר צמצום דרישות שטח הדיסק עבור צמתי אימות.

מה הבעיה?

אחת הבעיות המתמשכות של ביטקוין הייתה יכולת ההרחבה שלו. הרעיון של "בנק משלך" מחייב את משתתפי הרשת לשמור תיעוד של כל הכספים הזמינים לשימוש. בביטקוין, הכספים הזמינים מתבטאים כסט של תפוקות שלא הוצאו - סט UTXO. אמנם זה לא ייצוג אינטואיטיבי במיוחד, אבל הוא מועיל מבחינת ביצועי היישום על פני ייצוג שבו לכל "ארנק" יש "יתרה" כערך נפרד, וגם מוסיף פרטיות (למשל. מטבעות).

חשוב להבחין בין היסטוריית העסקאות (מה שנקרא בלוקצ'יין) לבין המצב הנוכחי של המערכת. היסטוריית עסקאות הביטקוין תופסת כיום כ-200 ג'יגה-בייט של שטח דיסק, וממשיכה לגדול. עם זאת, מצב המערכת קטן בהרבה, בסדר גודל של 4 ג'יגה-בייט, ולוקח בחשבון רק את העובדה שלמישהו יש כרגע מטבעות. גם נפח הנתונים הללו גדל עם הזמן, אך בקצב הרבה יותר איטי ולעיתים אף נוטה לרדת (ראה CDPV).

לקוחות קלים (SPVs) מחליפים ערבויות אבטחה עבור היכולת לאחסן שום מצב מינימום (סט UTXO) מלבד מפתחות פרטיים.

UTXO ו-UTXO-סט

UTXO (Unspent Transaction Output) הוא פלט העסקה שלא הוצאה, נקודת הסיום של המסע של כל סאטושי המועבר בעסקאות. פלטים שלא הוצאו הופכים לתשומות של עסקאות חדשות ובכך מוציאות (מבזבזות) ומוסרות מ-UTXO-סט.

UTXOs חדשים נוצרים תמיד על ידי עסקאות:

• עסקאות בסיס מטבעות ללא תשומות: צור UTXOs חדשים כאשר כורים מנפיקים מטבעות
• עסקאות רגילות: צור UTXOs חדשים תוך הוצאת קבוצה מסוימת של UTXOs קיימים

תהליך העבודה עם UTXO:

ארנקים סופרים את מספר המטבעות הזמינים להוצאה (יתרה) בהתבסס על כמות ה-UTXO הזמינה לארנק הזה להוצאה.

כל צומת מאמת, כדי למנוע ניסיונות הוצאה כפולים, חייב לפקח על הסט כל UTXO בעת בדיקה כל עסקאות כל לַחסוֹם.

הצומת חייב להיות בעל היגיון:

• תוספות לסט UTXO
• מחיקות מ-UTXO-set
• בדיקת נוכחות של UTXO בודד בסט

ישנן דרכים לצמצם את הדרישות למידע מאוחסן על סט, תוך שמירה על היכולת להוסיף ולהסיר אלמנטים, לבדוק ולהוכיח את קיומו של אלמנט בסט באמצעות מצברים קריפטוגרפיים.

סוללות עבור UTXO

הרעיון של שימוש בסוללות לאחסון UTXO מרובים מדובר מוקדם יותר.

ערכת ה-UTXO נבנית תוך כדי תנועה, במהלך הורדת הבלוק הראשוני (IBD), מאוחסנת במלואה ולתמיד, בעוד שתכולתה משתנה לאחר עיבוד עסקאות מכל בלוק חדש ונכון של הרשת. תהליך זה דורש הורדה של כ-200 GB של נתוני בלוק ואימות של מאות מיליוני חתימות דיגיטליות. לאחר השלמת תהליך ה-IBD, השורה התחתונה היא שה-UTXO-סט יתפוס כ-4 GB.

עם זאת, עם מצברים, כללי הקונצנזוס לכספים מצטמצמים לאימות והפקת הוכחות קריפטוגרפיות, ונטל המעקב אחר כספים זמינים מועבר לבעלים של אותם כספים, אשר מספק הוכחה לקיומם ובעלותם.

מצבר יכול להיקרא ייצוג קומפקטי של קבוצה. גודל הייצוג המאוחסן חייב להיות קבוע , או להגדיל באופן תת-ליניארי ביחס לקרדינליות של הסט וגודל האלמנט עצמו, למשל , כאשר n הוא הקרדינליות של הקבוצה המאוחסנת.

במקרה זה, המצבר צריך לאפשר הפקת הוכחה להכללת רכיב בקבוצה (הוכחת הכללה) ולאפשר לאמת הוכחה זו ביעילות.

הסוללה נקראת דינמי if מאפשר לך להוסיף אלמנטים ולהסיר אלמנטים מקבוצה.

דוגמה לסוללה כזו תהיה מצבר RSA שהוצע על ידי Boneh, Bunz, Fisch בדצמבר 2018. לצבר כזה יש גודל קבוע של ייצוג מאוחסן, אבל דורש נוכחות סוד משותף (התקנה מהימנה). דרישה זו שוללת את תחולתו של מצבר כזה עבור רשתות חסרות אמון כמו ביטקוין, שכן דליפת נתונים במהלך יצירת סוד יכולה לאפשר לתוקפים ליצור הוכחה כוזבת לקיומו של UTXO, להונות צמתים עם ערכת UTXO המבוססת על מצבר כזה.

אוטריקסו

עיצוב Utreexo שהוצע על ידי Thaddeus Dryja מאפשר ליצור דינמי צובר без הגדרה מהימנה.

Utreexo הוא יער של בינארי מושלם מרקל טריס והוא פיתוח של הרעיונות המוצגים ב מצברים אסינכרוניים יעילים עבור pki מבוזר, הוספת היכולת להסיר אלמנטים מקבוצה.

מבנה לוגי של הסוללה

תאי הסוללה מסודרים ביער של עצים בינאריים אידיאליים. עצים מסודרים לפי גובה. ייצוג זה נבחר כחזותי ביותר ומאפשר לדמיין את מיזוג העצים במהלך פעולות על הסוללה.

המחבר מציין כי מאחר שכל העצים ביער הם אידיאליים, גובהם מתבטא בחזקת שתיים, כפי שניתן לייצג כל מספר טבעי כסכום של חזקות שתיים. בהתאם, ניתן לקבץ כל קבוצה של עלים לעצים בינאריים, ובכל המקרים, הוספת אלמנט חדש דורשת ידע רק על צמתי השורש של עצים מאוחסנים.

לפיכך, הייצוג המאוחסן של מצבר Utreexo הוא רשימה של צמתי שורש (שורש מרקל), ולא כל יער העצים.

בואו נציג את רשימת רכיבי השורש כ 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()

מכיוון שאנו משתמשים בעצי מרקל, האב של כל אחד משני הצמתים הוא צומת אחד המאחסן את ה-hash של שרשור הגיבובים של הצמתים הצאצאים:

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

המחבר מציין שכדי למנוע את ההתקפות שתוארו על ידי שארל בוילה, פייר אלן פוקה, עדי שמיר וסבסטיאן צימר ב
התקפות קדם-תמונה שניות על פונקציות hash משומרות, בנוסף לשני הגיבובים, יש להוסיף לשרשור גם את הגובה בתוך העץ.

כאשר אתה מוסיף אלמנטים לצובר, עליך לעקוב אחר רכיבי השורש שהשתנו. על ידי ביצוע הנתיב של שינוי רכיבי השורש עבור כל אלמנט שתוסיף, תוכל לבנות מאוחר יותר הוכחה לנוכחותם של אלמנטים אלו.

עקוב אחר שינויים תוך כדי הוספתם

כדי לעקוב אחר השינויים שבוצעו, בואו נכריז על המבנה 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
    }
}

בְּבִירוּר:

תהליך בדיקת ההוכחה עבור א

הסרת פריטים

כדי להסיר תא מסוללה, עליך לספק הוכחה תקפה לכך שהתא נמצא שם. באמצעות הנתונים מההוכחה, ניתן לחשב רכיבי שורש חדשים של המצבר שההוכחה שניתנה לא תהיה נכונה יותר עבורם.

האלגוריתם הוא כדלקמן:

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

תהליך הסרת רכיב "A":

שילוב ברשת קיימת

באמצעות המצבר המוצע, צמתים יכולים להימנע משימוש ב-DB כדי לאחסן את כל ה-UTXOs ועדיין להיות מסוגלים לשנות את ערכת ה-UTXO. עם זאת, מתעוררת בעיית העבודה עם ראיות.

בואו נקרא לצומת האימות שמשתמש בצובר UTXO קוֹמפָּקטִי (צומת מצב קומפקטי), והמאמת ללא מצבר הוא להשלים (צומת מלא). קיומם של שני מחלקות של צמתים יוצר בעיה בשילובם לרשת אחת, שכן צמתים קומפקטיים דורשים הוכחה לקיומם של UTXOs, המושקעים בטרנזקציות, בעוד צמתים מלאים לא. אם כל צמתי הרשת לא יעברו במקביל ובאופן מתואם לשימוש ב-Utreexo, אזי צמתים קומפקטיים יישארו מאחור ולא יוכלו לפעול ברשת הביטקוין.

כדי לפתור את הבעיה של שילוב צמתים קומפקטיים ברשת, מוצע להציג מחלקה נוספת של צמתים - גשרים. צומת גשר הוא צומת שלם המאחסן גם את סוללת Utreexo והוכחת הפעלה עבור כל UTXO מבית UTXO-set. גשרים מחשבים גיבוב חדשים ומעדכנים את המצבר וההוכחות עם הגעת בלוקים חדשים של עסקאות. תחזוקה ועדכון של המצבר וההוכחות לא מטילה עומס חישובי נוסף על צמתים כאלה. גשרים מקריבים שטח דיסק: צריך לשמור על סדר hashes, לעומת hashes עבור צמתים קומפקטיים, כאשר n הוא העוצמה של ערכת UTXO.

ארכיטקטורת רשת

גשרים מאפשרים להוסיף בהדרגה צמתים קומפקטיים לרשת מבלי לשנות את התוכנה של צמתים קיימים. צמתים מלאים פועלים כבעבר, ומפיצים בינם לבין עצמם עסקאות וחסימות. צמתי גשר הם צמתים מלאים המאחסנים בנוסף נתוני סוללה של Utreexo וקבוצה של הוכחות הכללה עבור כל UTXO לעת עתה. צומת הגשר אינו מפרסם את עצמו ככזה, ומתיימר להיות צומת מלא עבור כל הצמתים המלאים וצומת קומפקטי עבור כל הצמתים הקומפקטיים. למרות שגשרים מחברים את שתי הרשתות יחד, הם למעשה צריכים לחבר אותם רק בכיוון אחד: מצמתים מלאים קיימים ועד צמתים קומפקטיים. זה אפשרי מכיוון שאין צורך לשנות את פורמט העסקאות, וניתן לזרוק הוכחות UTXO עבור צמתים קומפקטיים, כך שכל צומת קומפקטי יכול באופן דומה לשדר טרנזקציות לכל משתתפי הרשת ללא השתתפות של צמתי גשר.

מסקנה

הסתכלנו על סוללת Utreexo ויישמנו את אב הטיפוס שלה ב- Rust. בדקנו את ארכיטקטורת הרשת שתאפשר שילוב של צמתים מבוססי סוללה. היתרון של תפיסות קומפקטיות הוא גודל הנתונים המאוחסנים, שתלוי לוגריתמית בעוצמת סט ה-UTXOs, מה שמפחית מאוד את הדרישות לשטח דיסק וביצועי אחסון עבור צמתים כאלה. החיסרון הוא תעבורת הצומת הנוספת להעברת הוכחות, אך טכניקות צבירת ראיות (כאשר הוכחה אחת מוכיחה את קיומם של מספר אלמנטים) ושמירה במטמון יכולות לעזור לשמור על תנועה בגבולות מקובלים.

תזכור:

• GitHub של אב טיפוס של Utreexo ב-Rust
• תאדאוס דרייה - Utreexo: מצבר דינמי מבוסס hash המותאם לסט הביטקוין UTXO
• איורים מונפשים מתוך המאמר

מקור: www.habr.com