يا هبر!
في شبكة البيتكوين، تتفق جميع العقد، من خلال الإجماع، على مجموعة من UTXOs: كم عدد العملات المعدنية المتاحة للإنفاق، ولمن بالضبط، وتحت أي ظروف. مجموعة UTXO هي الحد الأدنى لمجموعة البيانات المطلوبة لعقدة التحقق من الصحة، والتي بدونها لن تتمكن العقدة من التحقق من صحة المعاملات الواردة والكتل التي تحتوي عليها.
وفي هذا الصدد، تُبذل المحاولات بكل الطرق الممكنة لتقليل التمثيل المخزن لهذه المجموعة، وضغطها دون فقدان ضمانات الأمان. كلما كان حجم البيانات المخزنة أصغر، انخفضت متطلبات مساحة القرص لعقدة التحقق من الصحة، مما يجعل إطلاق عقدة التحقق من الصحة رخيصًا، ويسمح لك بتوسيع الشبكة وبالتالي زيادة استقرار الشبكة.
سننشر في هذا المنشور نموذجًا أوليًا لـ Rust لاقتراح حديث من مؤلف مشارك , - ، مما يسمح بتقليل متطلبات مساحة القرص لعقد التحقق من الصحة.
ما هي المشكلة؟
إحدى المشاكل الدائمة التي تواجهها عملة البيتكوين هي قابليتها للتوسع. تتطلب فكرة "بنكك الخاص" من المشاركين في الشبكة الاحتفاظ بسجلات لجميع الأموال المتاحة للاستخدام. في البيتكوين، يتم التعبير عن الأموال المتاحة كمجموعة من المخرجات غير المنفقة - مجموعة UTXO. على الرغم من أن هذا ليس تمثيلًا بديهيًا بشكل خاص، إلا أنه مفيد من حيث أداء التنفيذ على التمثيل الذي تحتوي فيه كل "محفظة" على "رصيد" كمدخل منفصل، كما يضيف الخصوصية (على سبيل المثال. ).
من المهم التمييز بين تاريخ المعاملات (ما يسمى blockchain) والحالة الحالية للنظام. يشغل سجل معاملات البيتكوين حاليًا حوالي 200 جيجابايت من مساحة القرص، ويستمر في النمو. ومع ذلك، فإن حالة النظام أصغر بكثير، في حدود 4 جيجابايت، وتأخذ في الاعتبار فقط حقيقة أن شخصًا ما يمتلك عملات معدنية حاليًا. يزداد حجم هذه البيانات أيضًا بمرور الوقت، ولكن بمعدل أبطأ بكثير، بل ويميل في بعض الأحيان إلى الانخفاض (انظر CDPV).
يتاجر العملاء الخفيفون (SPV) بضمانات الأمان للقدرة على تخزين أي حالة دنيا (مجموعة UTXO) بخلاف المفاتيح الخاصة.
UTXO ومجموعة UTXO
UTXO (مخرجات المعاملات غير المنفقة) هو مخرجات المعاملات غير المنفقة، ونقطة النهاية لرحلة كل ساتوشي يتم نقله في المعاملات. تصبح المخرجات غير المنفقة مدخلات للمعاملات الجديدة وبالتالي يتم إنفاقها (إنفاقها) وإزالتها من مجموعة UTXO.
يتم دائمًا إنشاء UTXOs الجديدة من خلال المعاملات:
- معاملات Coinbase بدون مدخلات: قم بإنشاء UTXOs جديدة عندما يقوم القائمون بالتعدين بإصدار العملات المعدنية
- المعاملات العادية: إنشاء UTXOs جديدة أثناء إنفاق مجموعة معينة من UTXOs الموجودة
عملية العمل مع UTXO:
تحسب المحافظ عدد العملات المعدنية المتاحة للإنفاق (الرصيد) بناءً على مبلغ UTXO المتاح لهذه المحفظة للإنفاق.
يجب على كل عقدة تحقق، لمنع محاولات الإنفاق المزدوجة، مراقبة المجموعة جميع UTXO عند الفحص كل المعاملات كل حاجز.
يجب أن يكون للعقدة منطق:
- إضافات إلى مجموعة UTXO
- عمليات الحذف من مجموعة UTXO
- التحقق من وجود UTXO واحد في المجموعة
هناك طرق لتقليل متطلبات المعلومات المخزنة حول المجموعة، مع الحفاظ على القدرة على إضافة وإزالة العناصر، والتحقق من وجود عنصر في المجموعة وإثباته باستخدام .
بطاريات UTXO
فكرة استخدام البطاريات لتخزين UTXOs المتعددة .
يتم إنشاء مجموعة UTXO بسرعة، أثناء التنزيل الأولي للكتل (IBD)، ويتم تخزينها بالكامل وبشكل دائم، بينما تتغير محتوياتها بعد معالجة المعاملات من كل كتلة جديدة وصحيحة للشبكة. تتطلب هذه العملية تنزيل ما يقرب من 200 جيجابايت من بيانات الكتلة والتحقق من مئات الملايين من التوقيعات الرقمية. بعد اكتمال عملية IBD، خلاصة القول هي أن مجموعة UTXO ستشغل حوالي 4 جيجابايت.
ومع ذلك، مع المجمعات، يتم تقليل قواعد الإجماع على الأموال إلى التحقق وإنشاء أدلة التشفير، ويتم تحويل عبء تتبع الأموال المتاحة إلى مالك تلك الأموال، الذي يقدم دليلاً على وجودها وملكيتها.
يمكن أن يسمى المجمع تمثيلا مدمجا لمجموعة. يجب أن يكون حجم التمثيل المخزن ثابتًا ، أو زيادة خطية فيما يتعلق بأصل المجموعة وحجم العنصر نفسه، على سبيل المثال ، حيث n هو أصل المجموعة المخزنة.
في هذه الحالة، يجب أن يسمح المجمع بإنشاء دليل على إدراج عنصر في المجموعة (إثبات التضمين) ويجعل من الممكن التحقق من هذا الإثبات بشكل فعال.
البطارية تسمى ديناميكي إذا يسمح لك بإضافة عناصر وإزالة العناصر من المجموعة.
مثال على هذه البطارية سيكون . مثل هذا المجمع له حجم ثابت من التمثيل المخزن، ولكنه يتطلب وجوده سر مشترك (الإعداد الموثوق به). ينفي هذا المطلب إمكانية تطبيق مثل هذا المجمع على الشبكات غير الموثوقة مثل Bitcoin، نظرًا لأن تسرب البيانات أثناء الإنشاء السري يمكن أن يسمح للمهاجمين بإنشاء دليل كاذب على وجود UTXO، وخداع العقد بمجموعة UTXO القائمة على مثل هذا المجمع.
Utreexo
تصميم Utreexo الذي اقترحه Thaddeus Dryja يجعل من الممكن الإنشاء ديناميكي بطارية بدون إعداد موثوق به.
Utreexo عبارة عن غابة من الثنائيات المثالية وهو تطوير للأفكار المقدمة فيه ، إضافة القدرة على إزالة العناصر من المجموعة.
الهيكل المنطقي للبطارية
يتم ترتيب خلايا البطارية في غابة من الأشجار الثنائية المثالية. يتم ترتيب الأشجار حسب الارتفاع. تم اختيار هذا التمثيل باعتباره الأكثر وضوحًا ويسمح لك بتصور دمج الأشجار أثناء العمليات على البطارية.
ويشير المؤلف إلى أنه بما أن جميع الأشجار في الغابة مثالية، فإنه يتم التعبير عن ارتفاعها كقوة لاثنين، تمامًا كما يمكن تمثيل أي عدد طبيعي كمجموع لقوى اثنين. وبناء على ذلك، يمكن تجميع أي مجموعة من الأوراق في أشجار ثنائية، وفي جميع الحالات، فإن إضافة عنصر جديد يتطلب المعرفة فقط حول العقد الجذرية للأشجار المخزنة.
وبالتالي، فإن التمثيل المخزن لمجمع 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()، الذي يتعرف على العقدة الأصلية لعنصرين محددين.
وظيفة الأصل ().
نظرًا لأننا نستخدم أشجار Merkle، فإن الأصل لكل من العقدتين هو عقدة واحدة تخزن تجزئة تسلسل تجزئات العقد الفرعية:
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);
}- إلحاق العناصر المراد إضافتها (array
insertions) إلى العربة الأولىnew_roots[0]:
قانون
new_roots[0].extend_from_slice(insertions);- ادمج العناصر المضافة إلى السلة الأولى مع الباقي:
- لجميع عربات التسوق التي تحتوي على أكثر من عنصر واحد:
- خذ عنصرين من نهاية السلة، واحسب أصلهما، ثم قم بإزالة كلا العنصرين
- أضف الأصل المحسوب إلى سلة التسوق التالية
- لجميع عربات التسوق التي تحتوي على أكثر من عنصر واحد:
قانون
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,
}استخدام المعلومات التي تم الحصول عليها مسبقًا عند إضافة عنصر (structure 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, ¤t_parent)
} else {
parent(¤t_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;
}
}عملية إزالة العنصر "أ":
التكامل في شبكة موجودة
باستخدام المجمع المقترح، يمكن للعقد تجنب استخدام قاعدة بيانات لتخزين جميع UTXOs بينما تظل قادرة على تغيير مجموعة UTXO. ومع ذلك، تنشأ مشكلة العمل مع الأدلة.
لنستدعي عقدة التحقق التي تستخدم مجمع UTXO المدمج (عقدة الحالة المدمجة)، والمدقق بدون تراكم كامل (عقدة كاملة). إن وجود فئتين من العقد يخلق مشكلة لدمجهما في شبكة واحدة، حيث أن العقد المدمجة تتطلب دليلاً على وجود UTXOs، والتي يتم إنفاقها في المعاملات، في حين أن العقد الكاملة لا تفعل ذلك. إذا لم تتحول جميع عقد الشبكة في وقت واحد وبطريقة منسقة إلى استخدام Utreexo، فسيتم ترك العقد المدمجة في الخلف ولن تكون قادرة على العمل على شبكة Bitcoin.
لحل مشكلة دمج العقد المدمجة في الشبكة، يقترح تقديم فئة إضافية من العقد - الجسور. عقدة الجسر هي عقدة كاملة تقوم أيضًا بتخزين بطارية Utreexo وإثبات التشغيل جميع UTXO من مجموعة UTXO. تقوم الجسور بحساب التجزئات الجديدة وتحديث المجمع والبراهين عند وصول كتل جديدة من المعاملات. لا تؤدي صيانة المجمع والبراهين وتحديثهما إلى فرض حمل حسابي إضافي على هذه العقد. تضحي الجسور بمساحة القرص: تحتاج إلى الحفاظ على تنظيم الأشياء التجزئة، مقارنة ب التجزئات للعقد المدمجة، حيث n هي قوة مجموعة UTXO.
هندسة الشبكات
تتيح الجسور إمكانية إضافة العقد المدمجة تدريجيًا إلى الشبكة دون تغيير برنامج العقد الموجودة. تعمل العقد الكاملة كما كانت من قبل، وتوزع المعاملات والكتل فيما بينها. عقد الجسر هي عقد كاملة تقوم بالإضافة إلى ذلك بتخزين بيانات بطارية Utreexo ومجموعة من إثباتات التضمين جميع UTXO في الوقت الحالي. لا تعلن عقدة الجسر عن نفسها على هذا النحو، وتتظاهر بأنها عقدة كاملة لجميع العقد الكاملة وعقدة مدمجة لجميع العقد المدمجة. على الرغم من أن الجسور تربط الشبكتين معًا، إلا أنها في الواقع تحتاج فقط إلى توصيلهما في اتجاه واحد: من العقد الكاملة الموجودة إلى العقد المدمجة. هذا ممكن لأن تنسيق المعاملة لا يحتاج إلى تغيير، ويمكن التخلص من إثباتات UTXO للعقد المدمجة، لذلك يمكن لأي عقدة مدمجة أن تبث المعاملات بالمثل لجميع المشاركين في الشبكة دون مشاركة عقد الجسر.
اختتام
لقد نظرنا إلى بطارية Utreexo وقمنا بتنفيذ نموذجها الأولي في Rust. لقد نظرنا إلى بنية الشبكة التي ستسمح بتكامل العقد القائمة على البطارية. تتمثل ميزة الالتقاطات المدمجة في حجم البيانات المخزنة، والذي يعتمد لوغاريتميًا على قوة مجموعة UTXOs، مما يقلل بشكل كبير من متطلبات مساحة القرص وأداء التخزين لمثل هذه العقد. العيب هو حركة العقدة الإضافية لنقل البراهين، ولكن تقنيات تجميع الأدلة (عندما يثبت دليل واحد وجود عدة عناصر) والتخزين المؤقت يمكن أن يساعد في إبقاء حركة المرور ضمن الحدود المقبولة.
مراجع:
- -
المصدر: www.habr.com