Utreexo: बहुत सारे UTXO बिटकॉइन को कंप्रेस करना

नमस्कार, हेब्र!

बिटकॉइन नेटवर्क पर, सभी नोड्स कई UTXO पर आम सहमति से सहमत हैं: खर्च करने के लिए कितने सिक्के उपलब्ध हैं, किसको, और किन शर्तों के तहत। UTXOs का एक सेट एक डेटा सेट है जो एक सत्यापनकर्ता नोड के लिए न्यूनतम आवश्यक है, जिसके बिना एक नोड आने वाले लेनदेन की वैधता और उन्हें युक्त ब्लॉक को सत्यापित नहीं कर सकता है।

इस संबंध में, सुरक्षा गारंटी के नुकसान के बिना इसे संपीड़ित करने के लिए, इस सेट के संग्रहीत प्रतिनिधित्व को कम करने के लिए हर तरह से प्रयास किए जाते हैं। संग्रहीत डेटा की मात्रा जितनी कम होगी, सत्यापनकर्ता नोड के डिस्क स्थान के लिए कम आवश्यकताएं, जो सत्यापनकर्ता नोड को सस्ते में लॉन्च करती है, आपको नेटवर्क का विस्तार करने की अनुमति देती है और जिससे नेटवर्क स्थिरता में वृद्धि होती है।

इस नोट में, हम लाइटनिंग नेटवर्क पेपर के सह-लेखक, थेडियस ड्रेजा - यूट्रीक्सो: के एक हालिया प्रस्ताव के रस्ट प्रोटोटाइप को कवर करेंगे , बिटकॉइन UTXO सेट के लिए अनुकूलित एक गतिशील हैश-आधारित संचायक , जो सत्यापनकर्ता नोड्स के लिए डिस्क स्थान की आवश्यकताओं को पूरा करता है।

क्या समस्या है?

बिटकॉइन की शाश्वत समस्याओं में से एक इसकी मापनीयता थी। "एक बैंक के मालिक" के विचार को उपयोग के लिए सभी उपलब्ध निधियों का ट्रैक रखने के लिए नेटवर्क प्रतिभागियों की आवश्यकता होती है। बिटकॉइन में, उपलब्ध फंडों को अनपेक्षित आउटपुट के सेट के रूप में व्यक्त किया जाता है - UTXO- सेट। हालांकि यह बहुत सहज दृष्टिकोण नहीं है, यह कार्यान्वयन प्रदर्शन के मामले में फायदेमंद है, एक ऐसे दृश्य की तुलना में जिसमें प्रत्येक बटुए में एक अलग प्रविष्टि के रूप में "संतुलन" होता है, और गोपनीयता भी जोड़ता है (उदाहरण के लिए, CoinJoin काम प्रदान करता है)।

लेन-देन के इतिहास (जिसे ब्लॉकचेन कहा जाता है) और सिस्टम की वर्तमान स्थिति के बीच अंतर करना महत्वपूर्ण है। वर्तमान में बिटकॉइन का लेन-देन इतिहास लगभग 200 जीबी डिस्क स्थान पर है, और बढ़ता रहता है। हालांकि, सिस्टम की स्थिति बहुत छोटी है, लगभग 4 जीबी है, और केवल इस तथ्य को ध्यान में रखता है कि कोई वर्तमान में सिक्कों का मालिक है। इन आंकड़ों की मात्रा भी समय के साथ बढ़ती जाती है, लेकिन बहुत कम दर पर और कभी-कभी घट भी जाती है (देखें KDPV)।

लाइट क्लाइंट (एसपीवी) निजी कुंजी को छोड़कर किसी भी न्यूनतम राज्य (यूटीएक्सओ-सेट) को स्टोर नहीं करने की क्षमता के लिए सुरक्षा की गारंटी देता है।

UTXO और UTXO- सेट

UTXO (Unspent Transaction Output) - बिना लेन-देन के उत्पादन, लेनदेन में प्रेषित प्रत्येक सटोशी की यात्रा का समापन बिंदु। अनिर्दिष्ट आउटपुट नए लेनदेन के इनपुट बन जाते हैं और उसी समय खर्च होते हैं और यूटीएक्सओ-सेट से हटा दिए जाते हैं।

नए UTXO हमेशा लेनदेन द्वारा बनाए जाते हैं:

• बिना इनपुट के कॉइनबेस लेनदेन: खनिकों द्वारा सिक्कों के मुद्दे के दौरान नए UTXO बनाएं
• पारंपरिक लेनदेन: मौजूदा UTXO के कुछ सेट खर्च करते हुए नए UTXO बनाएं

UTXO के साथ काम करने की प्रक्रिया:

बटुए खर्च करने के लिए इस बटुए के लिए उपलब्ध UTXO की राशि के आधार पर खर्च (शेष) के लिए उपलब्ध सिक्कों की संख्या पर विचार करते हैं।

प्रत्येक सत्यापनकर्ता नोड, डबल खर्च के प्रयासों को रोकने के लिए, प्रत्येक ब्लॉक के प्रत्येक लेनदेन के सत्यापन के दौरान सभी UTXOs के संग्रह को ट्रैक करना चाहिए।

नोड में तर्क होना चाहिए:

• UTXO- सेट के अतिरिक्त
• UTXO- सेट विलोपन
• सेट में एकल UTXO की उपस्थिति के लिए जाँच करता है

सेट के बारे में संग्रहीत जानकारी के लिए आवश्यकताओं को कम करने के तरीके हैं, जबकि तत्वों को जोड़ने और हटाने की क्षमता बरकरार रखते हुए, क्रिप्टोग्राफ़िक बैटरी का उपयोग करके सेट में एक तत्व के अस्तित्व की जांच करें और साबित करें।

UTXO के लिए बैटरियों

कई यूटीएक्सओ को स्टोर करने के लिए बैटरी का उपयोग करने के विचार पर पहले चर्चा की गई है ।

UTXO- सेट को ब्लॉक चेन (IBD, प्रारंभिक ब्लॉक डाउनलोड) के प्रारंभिक लोडिंग के दौरान फ्लाई पर बनाया गया है, इसे पूर्ण और लगातार संग्रहीत किया जाता है, जबकि इसकी सामग्री प्रत्येक नए और सही नेटवर्क ब्लॉक से लेनदेन को संसाधित करने के बाद बदलती है। इस प्रक्रिया में लगभग 200 GB डेटा ब्लॉक डाउनलोड करने और लाखों डिजिटल हस्ताक्षर सत्यापित करने की आवश्यकता होती है। IBD प्रक्रिया पूरी होने के बाद, सूखे अवशेषों में UTXO- सेट लगभग 4 GB का होगा।

हालांकि, बैटरियों का उपयोग करते समय, फंडों के बारे में आम सहमति नियम क्रिप्टोग्राफिक सबूतों की जांच करने और उत्पन्न करने के लिए नीचे आते हैं, और उपलब्ध फंडों पर नज़र रखने का बोझ इन फंडों के मालिक के कंधों पर रखा जाता है, जो उनकी उपस्थिति और स्वामित्व का सबूत प्रदान करता है।

बैटरी को सेट का एक कॉम्पैक्ट प्रतिनिधित्व कहा जा सकता है। संग्रहीत दृश्य का आकार, इस मामले में, या तो स्थिर होना चाहिए $$$O (1)$, या उदाहरण के लिए, तत्व के सेट और आकार की शक्ति के सापेक्ष उदासीनता बढ़ाते हैं $$$O (लॉग (n))$जहाँ n संग्रहित सेट की शक्ति है।

इस मामले में, संचायक को सेट में एक तत्व को शामिल करने के प्रमाण (समावेश प्रमाण) को उत्पन्न करने की अनुमति देनी चाहिए और इसे इस प्रमाण को प्रभावी ढंग से सत्यापित करने में सक्षम करना चाहिए।

एक बैटरी को गतिशील कहा जाता है यदि यह आपको आइटम जोड़ने और सेट से आइटम निकालने की अनुमति देता है।

इस तरह की बैटरी का एक उदाहरण दिसंबर 2018 में बोन, बंज, फिस्क द्वारा प्रस्तावित आरएसए बैटरी है । ऐसी बैटरी में संग्रहीत दृश्य का एक निरंतर आकार होता है, लेकिन इसके लिए एक साझा रहस्य (विश्वसनीय सेटअप) की आवश्यकता होती है। यह आवश्यकता बिटकॉइन जैसे भरोसेमंद नेटवर्क के लिए इस तरह के संचायक की प्रयोज्यता को नकारती है, क्योंकि एक गुप्त पीढ़ी के दौरान डेटा रिसाव हमलावरों को इस तरह के एक संचायक के आधार पर UTXO- सेट के साथ नोड्स को स्पूफ़ करके UTXO के अस्तित्व के नकली सबूत बनाने की अनुमति दे सकता है।

Utreexo

Utreexo का प्रस्तावित थाडेस ड्रेजा डिज़ाइन आपको विश्वसनीय-सेटअप के बिना एक गतिशील बैटरी बनाने की अनुमति देता है।

Utreexo आदर्श बाइनरी मर्कल पेड़ों का एक जंगल है और वितरित पक्की के लिए कुशल अतुल्यकालिक संचयकों में प्रस्तुत विचारों का विकास है, जो सेट से तत्वों को निकालने की क्षमता को जोड़ता है।

बैटरी की तार्किक संरचना

बैटरी कोशिकाओं को सही बाइनरी पेड़ों के जंगल में व्यवस्थित किया जाता है। पेड़ों को ऊंचाई के आधार पर ऑर्डर किया जाता है। इस प्रस्तुति को सबसे दृश्य के रूप में चुना गया था और आपको बैटरी पर संचालन के दौरान पेड़ों के विलय की कल्पना करने की अनुमति मिलती है।

लेखक नोट करता है कि चूंकि जंगल में सभी पेड़ परिपूर्ण हैं, उनकी ऊंचाई दो की शक्ति द्वारा व्यक्त की जाती है, जैसे किसी भी प्राकृतिक संख्या को दो की शक्तियों के योग के रूप में दर्शाया जा सकता है। तदनुसार, शीट्स के किसी भी सेट को बाइनरी पेड़ों के रूप में वर्गीकृत किया जा सकता है, और सभी मामलों में, एक नए तत्व को जोड़ने के लिए केवल संग्रहीत पेड़ों के रूट नोड्स के बारे में ज्ञान की आवश्यकता होती है।

इस प्रकार, 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() फ़ंक्शन का वर्णन करते हैं, जो दो दिए गए तत्वों के लिए मूल नोड को पहचानता है।

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

बैटरी में आइटम जोड़ते समय, आपको यह ध्यान रखने की आवश्यकता है कि कौन से रूट आइटम बदल रहे हैं। जोड़े गए प्रत्येक तत्व के लिए मूल तत्वों को बदलने के मार्ग का अनुसरण करते हुए, आप बाद में इन तत्वों की उपस्थिति का प्रमाण बना सकते हैं।

 #[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); } 

• पहली टोकरी new_roots[0] में जोड़े गए तत्वों ( insertions सरणी) को जोड़ें:

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

आइटम "ए" को हटाने की प्रक्रिया:

मौजूदा नेटवर्क में एकीकरण

प्रस्तावित बैटरी का उपयोग करते हुए, नोड्स सभी UTXO को संग्रहीत करने के लिए डेटाबेस का उपयोग करने से इनकार कर सकते हैं, जबकि UTXO- सेट को बदलने की क्षमता बनाए रखते हैं। हालांकि, सबूत के साथ काम करने की समस्या है।

हम एक सत्यापनकर्ता नोड कहेंगे जो UTXO बैटरी कॉम्पैक्ट (कॉम्पैक्ट-स्टेट नोड) का उपयोग करता है, और बैटरी के बिना एक सत्यापनकर्ता - पूर्ण (पूर्ण नोड)। नोड्स के दो वर्गों का अस्तित्व उन्हें एकल नेटवर्क में एकीकृत करने की समस्या पैदा करता है, क्योंकि कॉम्पैक्ट नोड्स को UTXO के अस्तित्व के प्रमाण की आवश्यकता होती है, जो लेनदेन में खर्च होता है, लेकिन पूर्ण नोड्स नहीं करते हैं। यदि एक ही समय में और समन्वित तरीके से नेटवर्क के सभी नोड्स Utreexo पर स्विच नहीं करते हैं, तो कॉम्पैक्ट नोड्स पीछे रह जाएंगे और बिटकॉइन नेटवर्क पर काम नहीं कर पाएंगे।

नेटवर्क में कॉम्पैक्ट नोड्स को एकीकृत करने की समस्या को हल करने के लिए, नोड्स - पुलों का एक अतिरिक्त वर्ग पेश करना प्रस्तावित है। एक पुल नोड एक पूर्ण नोड है, जो अन्य बातों के अलावा, यूटीएक्सओ बैटरी और यूटीएक्सओ-सेट से सभी यूटीएक्सओ के लिए साक्ष्य शामिल करता है। पुल नए हैश की गणना करते हैं और बैटरी और साक्ष्य को अपडेट करते हैं क्योंकि नए ब्लॉक लेनदेन के साथ आते हैं। बैटरी और सबूतों का समर्थन और अद्यतन करना ऐसे नोड्स पर अतिरिक्त कम्प्यूटेशनल भार नहीं डालता है। पुल डिस्क स्थान को बलिदान करते हैं: क्रम को क्रम में रखें $$$2 एन$की तुलना में हैश $$$log (n)$कॉम्पैक्ट नोड्स के लिए हैश, जहाँ n सेट UTXO की शक्ति है।

नेटवर्क आर्किटेक्चर

पुल मौजूदा नोड्स के सॉफ्टवेयर को बदलने के बिना नेटवर्क में कॉम्पैक्ट नोड्स को धीरे-धीरे जोड़ना संभव बनाता है। पूर्ण नोड्स पहले की तरह काम करते हैं, आपस में लेनदेन और ब्लॉक वितरित करते हैं। ब्रिज नोड्स पूर्ण नोड्स हैं जो इसके अलावा यूट्रीक्सो बैटरी डेटा और वर्तमान में सभी UTXO के लिए शामिल किए जाने के साक्ष्य को संग्रहीत करते हैं। ब्रिज नोड खुद को इस तरह से विज्ञापित नहीं करता है, सभी पूर्ण नोड के लिए एक पूर्ण नोड होने का नाटक करता है और सभी कॉम्पैक्ट नोड के लिए एक कॉम्पैक्ट नोड है। हालांकि पुल दोनों नेटवर्क को एक साथ जोड़ते हैं, वास्तव में, उन्हें केवल एक दिशा में कनेक्ट करने की आवश्यकता होती है: मौजूदा पूर्ण नोड्स से कॉम्पैक्ट नोड्स तक। यह संभव है क्योंकि लेन-देन प्रारूप को बदलने की आवश्यकता नहीं है, और कॉम्पैक्ट नोड्स के लिए UTXO के लिए सबूतों को छोड़ दिया जा सकता है, इसलिए कोई भी कॉम्पैक्ट नोड उसी तरह से सभी नेटवर्क प्रतिभागियों को लेन-देन भेज सकता है, जैसे कि पुल नोड्स की भागीदारी के बिना।

निष्कर्ष

हमने Utreexo बैटरी की समीक्षा की और Rust में इसके प्रोटोटाइप को लागू किया। हमने नेटवर्क आर्किटेक्चर की जांच की, जो बैटरी के आधार पर नोड्स को एकीकृत करेगा। कॉम्पैक्ट कैच का लाभ संग्रहीत डेटा का आकार है, जो कई UTXO की शक्ति पर लघुगणक निर्भर करता है, जो इस तरह के नोड्स के लिए डिस्क स्थान की आवश्यकताओं और भंडारण प्रदर्शन को बहुत कम करता है। नुकसान सबूत के हस्तांतरण के लिए अतिरिक्त नोड ट्रैफ़िक है, लेकिन साक्ष्य एकत्रीकरण तकनीक (जब एक प्रमाण कई तत्वों के अस्तित्व को साबित करता है) और कैशिंग स्वीकार्य सीमा के भीतर यातायात को बनाए रखने में मदद कर सकता है।

संदर्भ :

• यूट्रीक्सो रस्ट प्रोटोटाइप गिटहब
• थेडियस ड्रूजा - यूट्रीक्सो: बिटकॉइन UTXO सेट के लिए अनुकूलित एक गतिशील हैश-आधारित संचायक
• एक लेख से एनिमेटेड कलाकृति