Utreexo: ضغط الكثير من UTXO Bitcoin

مرحبا يا هبر!

على شبكة Bitcoin ، تتفق جميع العقد بالإجماع على العديد من UTXOs: كم عدد العملات المعدنية المتاحة للإنفاق ولمن وتحت أي ظروف. مجموعة من UTXOs هي مجموعة بيانات تكون ضرورية الحد الأدنى لعقدة المدقق ، والتي بدونها لا يمكن للعقدة التحقق من صحة المعاملات الواردة والكتل التي تحتوي عليها.

في هذا الصدد ، تُبذل محاولات بكل طريقة لتقليص التمثيل المخزن لهذه المجموعة ، لضغطها دون فقدان الضمانات الأمنية. كلما كان حجم البيانات المخزنة أصغر ، قلت متطلبات مساحة القرص لعقدة المصادقة ، مما يجعل تشغيل عقدة المصادقة رخيصة ، مما يسمح لك بتوسيع الشبكة وبالتالي زيادة استقرار الشبكة.

في هذه المذكرة ، سنغطي النموذج الأولي للصدأ لاقتراح حديث من مؤلف مشارك في Lightning Network Paper ، Thaddeus Dryja - Utreexo: مُراكم ديناميكي قائم على التجزئة تم تحسينه من أجل مجموعة Bitcoin UTXO ، مما يقلل من متطلبات مساحة القرص لعُقد المدقق.

ما هي المشكلة؟

واحدة من المشاكل الأبدية من Bitcoin كانت قابلية التوسع. تتطلب فكرة "امتلاك بنك" من المشاركين في الشبكة متابعة جميع الأموال المتاحة للاستخدام. في بيتكوين ، يتم التعبير عن الأموال المتاحة كمجموعة من المخرجات غير المنفقة - مجموعة UTXO. على الرغم من أن هذه ليست طريقة عرض بديهية للغاية ، إلا أنها مفيدة من حيث أداء التنفيذ ، مقارنةً بالمنظر الذي يكون لكل محفظة "توازن" كإدخال منفصل ، وتضيف أيضًا الخصوصية (على سبيل المثال ، يوفر CoinJoin العمل).

من المهم التمييز بين محفوظات المعاملة (ما يسمى blockchain) والحالة الحالية للنظام. يشغل سجل معاملات Bitcoin حاليًا حوالي 200 جيجابايت من مساحة القرص ، ويستمر في النمو. ومع ذلك ، فإن حالة النظام أصغر بكثير ، حوالي 4 جيجابايت ، ولا تأخذ في الاعتبار سوى حقيقة أن شخصًا ما يمتلك عملات معدنية في الوقت الحالي. يزداد حجم هذه البيانات أيضًا بمرور الوقت ، ولكن بمعدل أقل كثيرًا وفي بعض الأحيان يميل إلى الانخفاض (انظر KDPV).

يقوم عملاء Light (SPV) بتبادل ضمانات الأمان للقدرة على عدم تخزين أي حالة دنيا (مجموعة UTXO) ، باستثناء المفاتيح الخاصة.

UTXO ومجموعة UTXO

UTXO (مخرجات المعاملات غير المنفقة) - مخرجات المعاملات غير المنفقة ، وهي نقطة نهاية رحلة كل ساتوشي يتم إرسالها في المعاملات. تصبح المخرجات غير المنفقة مدخلات للمعاملات الجديدة وفي الوقت نفسه تنفق وتم إزالتها من مجموعة UTXO.

يتم إنشاء UTXOs جديدة دائما عن طريق المعاملات:

• معاملات coinbase بدون مدخلات: أنشئ UTXOs جديدة أثناء إصدار العملات من قبل عمال المناجم
• المعاملات التقليدية: إنشاء UTXOs جديدة ، في حين تنفق بعض مجموعة من UTXOs الحالية

عملية العمل مع UTXO:

تأخذ المحافظ في الاعتبار عدد العملات المتاحة للإنفاق (الرصيد) بناءً على مقدار UTXO المتاح لهذه المحفظة للإنفاق.

يجب على كل عقدة مصادقة ، لمنع محاولات الإنفاق المزدوج ، تتبع جمع كل UTXOs أثناء التحقق من كل معاملة من كل كتلة.

يجب أن يكون للعقدة المنطق:

• الإضافات إلى مجموعة UTXO
• الحذف مجموعة UTXO
• يتحقق من وجود UTXO واحد في المجموعة

هناك طرق لتقليل متطلبات المعلومات المخزنة حول المجموعة ، مع الحفاظ على القدرة على إضافة وإزالة العناصر ، والتحقق من وجود عنصر في المجموعة وإثبات وجوده باستخدام بطاريات تشفير .

بطاريات UTXO

لقد تمت مناقشة فكرة استخدام البطاريات لتخزين العديد من UTXOs من قبل .

تم تصميم UTXO-set على الطاير ، أثناء التحميل الأولي لسلسلة الكتل (IBD ، تنزيل الكتل الأولي) ، يتم تخزينه بشكل كامل ومستمر ، بينما تتغير محتوياته بعد معالجة المعاملات من كل كتلة شبكة جديدة وصحيحة. تتطلب هذه العملية تنزيل حوالي 200 جيجابايت من كتل البيانات والتحقق من مئات الملايين من التوقيعات الرقمية. بعد اكتمال عملية IBD ، في البقايا الجافة ، ستشغل مجموعة UTXO حوالي 4 جيجابايت.

ومع ذلك ، عند استخدام البطاريات ، تتوقف قواعد الإجماع المتعلقة بالأموال على التحقق من أدلة التشفير وتوليدها ، ويقع عبء تتبع الأموال المتوفرة على عاتق مالك هذه الأموال ، مما يوفر دليلًا على وجودها وملكيتها.

يمكن أن تسمى البطارية تمثيل مضغوط للمجموعة. يجب أن يكون حجم العرض المخزن ، في هذه الحالة ، ثابتًا $$$O (1)$أو زيادة نسبة الخط الفرعي إلى قوة مجموعة وحجم العنصر نفسه ، على سبيل المثال $$$O (log (n))$حيث n هي قوة المجموعة المخزنة.

في هذه الحالة ، يجب أن يسمح المجمع بتوليد دليل على إدراج عنصر في المجموعة (دليل التضمين) وتمكينه من التحقق من هذا الإثبات بشكل فعال.

تسمى البطارية ديناميكية إذا سمحت لك بإضافة عناصر وإزالة عناصر من المجموعة.

مثال على هذه البطارية هي بطارية RSA التي اقترحها بونه ، بونز ، فيش في ديسمبر 2018 . تحتوي هذه البطارية على حجم ثابت للعرض المخزن ، ولكنها تتطلب سرًا مشتركًا (إعداد موثوق). ينفي هذا المطلب إمكانية تطبيق هذا المجمع على الشبكات غير الموثوق بها مثل Bitcoin ، حيث أن تسرب البيانات أثناء توليد السر قد يسمح للمهاجمين بإنشاء دليل مزيف على وجود UTXO من خلال خداع العقد باستخدام مجموعة UTXO استنادًا إلى مثل هذا المجمع.

Utreexo

يتيح لك تصميم Thaddeus Dryja المقترح من Utreexo إنشاء بطارية ديناميكية دون إعداد موثوق به.

Utreexo عبارة عن مجموعة من أشجار Merkle Trees الثنائية المثالية وهي عبارة عن تطور للأفكار المقدمة في مراكم فعالة غير متزامنة لـ 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() ، والتي تتعرف على العقدة الأصل لعنصرين معينين.

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

• أضف العناصر المضافة (صفيف 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 ) سيكون مسار Merkle ، الذي يتكون من سلسلة من 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 ) ، يمكنك إنشاء دليل على إضافة العنصر إلى البطارية. للقيام بذلك ، نلتف حول جدول التغييرات التي تم إجراؤها ونضيف كل خطوة إلى مسار Merkle ، والتي ستكون بمثابة دليل لاحقًا:

 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. كما هو الحال مع الإضافة ، نقوم بتنظيم مجموعة من السلال الفارغة المقابلة لأشجار Merkle بارتفاع يساوي اثنين من فهرس السلة
2. إدراج عناصر من خطوات مسار Merkle في السلال ؛ مؤشر سلة يساوي رقم الخطوة الحالية
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 ، فسيتم ترك العقد المدمجة ولن تكون قادرة على العمل على شبكة Bitcoin.

لحل مشكلة دمج العقد المدمجة في الشبكة ، يُقترح تقديم فئة إضافية من العقد - الجسور . العقدة الجسرية هي عقدة كاملة تقوم ، من بين أشياء أخرى ، بتخزين بطارية Utreexo وأدلة التضمين لجميع UTXOs من مجموعة UTXO. تقوم الجسور بحساب التجزئة الجديدة وتحديث البطارية والأدلة عند وصول كتل جديدة مع المعاملات. لا يدعم دعم وتحديث البطارية والأدلة تحميلًا حسابيًا إضافيًا على هذه العقد. تضاريس الجسور مساحة القرص: الحفاظ على النظام بالترتيب $$ التجزئة مقارنة ب $$$log (n)$تجزئة للعقد المدمجة ، حيث n هي قوة مجموعة UTXO.

هندسة الشبكات

تتيح الجسور إضافة العقد المدمجة تدريجياً إلى الشبكة دون تغيير برنامج العقد الحالية. العقد الكاملة تعمل كما كان من قبل ، وتوزع المعاملات وكتل فيما بينها. العقد الموصولة عبارة عن عقد كاملة تخزّن بالإضافة إلى ذلك بيانات بطارية Utreexo ومجموعة من أدلة التضمين لجميع UTXO في الوقت الحالي. لا تعلن عقدة الجسر عن نفسها على هذا النحو ، حيث تتظاهر بأنها عقدة كاملة لجميع العقد الكاملة وعقدة مدمجة لجميع العقد المدمجة. على الرغم من أن الجسور تربط كلتا الشبكتين معًا ، في الواقع ، يجب أن تكون متصلاً في اتجاه واحد فقط: من العقد الكاملة الموجودة إلى العقد المدمجة. هذا ممكن لأن تنسيق المعاملة لا يحتاج إلى تغيير ، ويمكن تجاهل دليل UTXO للعقد المدمجة ، بحيث يمكن لأي عقدة مدمجة إرسال المعاملات إلى جميع المشتركين في الشبكة بالطريقة نفسها دون مشاركة العقد.

استنتاج

استعرضنا بطارية Utreexo ونفذنا نموذجها الأولي في Rust. درسنا بنية الشبكة ، والتي ستدمج العقد على أساس البطارية. تتمثل ميزة catch catch في حجم البيانات المخزنة ، والتي تعتمد لوغاريتمياً على قوة العديد من UTXOs ، مما يقلل بشكل كبير من متطلبات مساحة القرص وأداء التخزين لمثل هذه العقد. العيب هو حركة مرور عقدة إضافية لنقل الأدلة ، ولكن تقنيات تجميع الأدلة (عندما يثبت أحد الأدلة وجود عدة عناصر) والتخزين المؤقت يمكن أن يساعد في الحفاظ على حركة المرور ضمن حدود مقبولة.

المراجع

• Utreexo الصدأ النموذج جيثب
• Thaddeus Dryja - Utreexo: تراكم ديناميكي قائم على البعثرة محسّن لمجموعة Bitcoin UTXO
• الأعمال الفنية المتحركة من مقال