في هذه المقالة ، أصف بإيجاز الحاجة إلى عملاء خفيفين في Bitcoin ولماذا تخدم "مرشحات الكتلة المدمجة" هذه الحاجة بشكل أفضل من "فلاتر Bloom". ثم أشرح بالتفصيل كيف يعمل مرشح الكتلة الكثيفة ، من خلال تجول خطوة بخطوة لبناء مثل هذا الفلتر على شبكة اختبار.
معنى مرشح الكتلة
عميل Bitcoin الخفيف (برنامج Bitcoin light) هو برنامج لا يهدف إلى تخزين blockchain من Bitcoin ولكن لدعم محفظة Bitcoin. هذا يعني أنه يجب أن يكون قادرًا على بث المعاملات إلى الشبكة ، ولكن الأهم من ذلك ، يجب أن يكون قادرًا على العثور على معاملات جديدة من السلسلة المتعلقة بهذه المحفظة. هناك نوعان من هذه المعاملات ذات الصلة: إرسال الأموال إلى هذه المحفظة (إنشاء مخرجات جديدة لعنوان هذه المحفظة) ، وإنفاق أحد UTXOs التي تتحكم فيها هذه المحفظة.
ما هو الخطأ في مرشحات bloom؟
قبل BIP 158 ، كان الأسلوب الأكثر شيوعًا للعملاء الخفيفين هو مرشح Bloom الموصوف في BIP 371. نمط مرشح Bloom هو أنك تأخذ جميع كائنات البيانات التي تهتم بها (على سبيل المثال ، المفاتيح العامة للبرنامج النصي لـ UTXOs التي تم إنفاقها وإنشاءها) ، وتجزئتها واحدة تلو الأخرى عدة مرات ، وإضافة كل نتيجة إلى In صورة نقطية تسمى "مرشح الازهار". يمثل هذا المرشح ما تهتم به. بعد ذلك ، ترسل هذا الفلتر إلى عقدة Bitcoin التي تثق بها وتطلب منهم إرسال كل ما يطابق هذا الفلتر.
تكمن المشكلة في أن هذه العملية ليست خاصة جدًا ، لأنك لا تزال تسرّب بعض المعلومات إلى عقدة Bitcoin التي تقبل الفلتر. يمكنهم معرفة الصفقات التي تهتم بها والصفقات التي لا تهتم بها على الإطلاق ؛ لا يمكنهم أيضًا إرسال أشياء تطابق المرشحات. لذلك ، فهي ليست مثالية للعملاء الخفيفين. ولكن في الوقت نفسه ، فهي ليست مثالية لعقد Bitcoin التي تخدم العملاء الخفيفين. في كل مرة ترسل فيها عامل تصفية ، يتعين عليهم تحميل الكتلة ذات الصلة من القرص ثم تحديد ما إذا كانت هناك معاملات تطابق الفلتر الخاص بك. فقط استمر في إرسال عوامل تصفية مزيفة ويمكنك تفجيرها - بشكل أساسي هجوم DOS. إن إنشاء مرشح يتطلب القليل من الطاقة ، ولكنه يتطلب الكثير من الطاقة للاستجابة لمثل هذا الطلب.
مرشح كتلة كثيفة
حسنًا ، السمات التي نحتاجها هي:
خصوصية أقوى
عدم تناسق تحميل العميل والخادم أقل. أي أنه يجب أن يكون هناك عمل أقل يجب القيام به على جانب الخادم.
ثقة أقل. لا يحتاج العملاء الخفيفون إلى القلق بشأن عدم قيام الخادم بإعادة المعاملات ذات الصلة.
باستخدام عامل تصفية كتلة كثيفة ، سيقوم الخادم (العقدة الكاملة) بإنشاء مرشح محدد لكل كتلة ، بما في ذلك جميع كائنات البيانات في هذه الكتلة. يجب حساب هذا المرشح مرة واحدة فقط وتخزينه إلى الأبد. إذا طلب العميل الخفيف مرشحًا لكتلة معينة ، فلا يوجد عدم تناسق هنا - لأن الخادم لا يحتاج إلى القيام بأي عمل أكثر من العميل الطالب. يمكن للعميل الخفيف أيضًا اختيار مصادر معلومات متعددة لتنزيل الكتلة الكاملة للتأكد من أنها متسقة ؛ علاوة على ذلك ، يمكن للعميل الخفيف دائمًا تنزيل الكتلة الكاملة للتحقق مما إذا كان الفلتر الذي يوفره الخادم صحيحًا (يطابق الكتلة ذات الصلة) محتوى). فائدة أخرى هي أنه أكثر خصوصية بهذه الطريقة. لم يعد العميل الخفيف بحاجة إلى إرسال بصمة البيانات التي يريدها إلى الخادم. كما يصبح من الصعب تحليل نشاط العميل الخفيف. بعد أن يحصل العميل الخفيف على هذا المرشح من الخادم ، فإنه يتحقق مما إذا كان المرشح يحتوي على البيانات التي يريدها ، وإذا كان الأمر كذلك ، فإن العميل الخفيف يطلب الكتلة الكاملة. وتجدر الإشارة أيضًا إلى أنه من أجل خدمة العملاء الخفيفين بهذه الطريقة ، تحتاج العقد الكاملة إلى الاستمرار في استخدام هذه المرشحات ، وقد يرغب العملاء الخفيفون أيضًا في الاستمرار في عدد قليل من المرشحات ، لذلك اجعل المرشحات خفيفة قدر الإمكان. الكمية مهمة جدًا ( وهذا هو سبب تسميته "مرشح الكتلة الكثيفة").
جيد جدًا! نحن الآن ندخل في الأشياء النادرة. كيف يتم إنشاء هذا الفلتر؟ كيف تبدو؟
ما هي احتياجاتنا؟
نريد وضع بصمة كائن معين في الفلتر ، بحيث عندما يرغب العملاء في التحقق مما إذا كانت الكتلة تحتوي على شيء متعلق بأنفسهم ، يمكنهم تعداد جميع الكائنات والتحقق من عامل التصفية ما إذا كان سيتطابق مع هذه الكائنات.
نريد أن يكون هذا المرشح صغيرًا بقدر الإمكان.
في الجوهر ، ما نريده هو شيء يمكن أن يلخص بعض المعلومات عن كتلة بحجم أصغر بكثير من الكتلة.
المعلومات الأساسية الموجودة في المرشح هي: المفتاح العام للبرنامج النصي لكل إدخال لكل معاملة (أي ، المفتاح العام للبرنامج النصي لكل UTXO مستهلك) ، والمفتاح العام للبرنامج النصي لكل إخراج من كل معاملة. في الأساس مثل هذا:
كائنات = {spk1، spk2، spk3، spk4، ...، spkN} // قائمة بالمفاتيح العمومية للبرنامج النصي N
من الناحية الفنية ، يمكننا التوقف هنا - يمكن لقائمة المفاتيح العامة للبرنامج النصي أن تعمل أيضًا كمرشح خاص بنا. هذه نسخة مكثفة من الكتلة تحتوي على المعلومات التي يحتاجها العملاء الخفيفون. باستخدام هذه القائمة ، يمكن للعميل الخفيف تأكيد 100٪ ما إذا كانت هناك معاملة ذات فائدة في الكتلة. لكن هذه القائمة كبيرة جدًا. لذلك ، فإن جميع خطواتنا التالية هي جعل هذه القائمة مضغوطة قدر الإمكان. هذا هو المكان الذي تصبح فيه الأشياء مثيرة للاهتمام.
أولاً ، يمكننا تحويل كل كائن إلى رقم ضمن نطاق معين ، وجعل رقم كل كائن موزعًا بالتساوي ضمن هذا النطاق. لنفترض أن لدينا 10 كائنات (N = 10) ، ثم لدينا نوع من الوظائف التي تحول كل كائن إلى رقم. لنفترض أننا اخترنا النطاق [0 ، 10] (بما أن لدينا 10 كائنات). الآن ، ستأخذ وظيفة "التجزئة إلى الرقم" كل كائن كمدخل وتنتج رقمًا بالحجم [0 ، 10] على التوالي. يتم توزيع الأرقام بالتساوي عبر هذا النطاق. هذا يعني أنه بعد الفرز ، سننتهي برسم بياني مثل هذا (في حالة مثالية جدًا جدًا):
بادئ ذي بدء ، هذا رائع لأننا قللنا بشكل كبير حجم بصمة كل كائن. الآن كل كائن هو مجرد رقم. لذلك ، يبدو مرشحنا الجديد كما يلي:
الأرقام: = {1،2،3،4،5،6،7،8،9،10}
يقوم العميل الخفيف بتنزيل مثل هذا الفلتر ، على أمل معرفة ما إذا كان الكائن الذي يبحث عنه يطابق المرشح. يأخذون فقط الكائن الذي يهتمون به ويقومون بتشغيل نفس وظيفة "التجزئة إلى الرقم" لمعرفة ما إذا كانت النتيجة في هذا الفلتر. أين المشكلة؟ المشكلة هي أن الأرقام الموجودة في الفلتر تستهلك بالفعل كل الاحتمالات في تلك المساحة! هذا يعني أنه بغض النظر عن الكائنات التي يهتم بها العميل الخفيف ، يجب أن تتطابق النتيجة الرقمية الناتجة مع هذا المرشح. بمعنى آخر ، يحتوي هذا المرشح على "معدل إيجابي خاطئ" بقيمة 1 (ملاحظة المترجم: تعني "إيجابية كاذبة" هنا أن الكتلة قد لا تحتوي على النتيجة التي حصل عليها المرشح هي نعم). ليس جيد جدا. كما يوضح أيضًا أنه في عملية ضغط البيانات لإنشاء الفلتر ، نفقد الكثير من المعلومات. نحن بحاجة إلى معدل إيجابي خاطئ أعلى. بعد ذلك ، افترض أننا نريد أن يكون المعدل الإيجابي الخاطئ 5. ثم يمكننا جعل الكائنات الموجودة في الكتلة تتطابق بالتساوي مع الأرقام الموجودة في النطاق [0 ، 50]:
يبدو أفضل بهذه الطريقة. إذا كنت عميلاً وقمت بتنزيل مثل هذا الفلتر ، فأنا بحاجة إلى التحقق مما إذا كان الكائن الذي أهتم به موجودًا في الكتلة المقابلة من خلال الفلتر ، وسيقل احتمال أن يقول الفلتر نعم ولكن ليس في الكتلة (إيجابية خاطئة) إلى 1/5. رائع ، نحن الآن نرسم 10 كائنات إلى أرقام بين 0 و 50. هذه القائمة الجديدة من الأرقام هي مرشحنا. مرة أخرى ، يمكننا التوقف في أي وقت ، ومع ذلك ، يمكننا ضغطها أكثر!
لدينا الآن قائمة مرتبة من الأرقام موزعة بالتساوي في الفترة [0 ، 50]. نعلم أن هناك 10 أرقام في هذه القائمة. هذا يعني أنه يمكننا استنتاج أن * الاختلاف * بين رقمين متجاورين في قائمة الأرقام المرتبة هذه من المرجح أن يكون 5. بشكل عام ، إذا كان لدينا N كائنات ونريد معدل إيجابي خاطئ لـ M ، فيجب أن يكون حجم المساحة N \ * M. وهذا يعني أن حجم هذه الأرقام يجب أن يكون بين 0 و N \ * M ، ولكن (بعد الفرز) فإن احتمال الاستيفاء لرقمين متجاورين تم فحصهما هو M. ويجب تخزين M أصغر من الرقم في مساحة N \ * M. لذلك ، بدلاً من تخزين كل رقم فردي ، يمكننا تخزين الفرق بين رقمين متجاورين. في المثال أعلاه ، هذا يعني أنه بدلاً من تخزين [0 ، 5 ، 10 ، 15 ، 20 ، 25 ، 30 ، 35 ، 40 ، 45 ، 50] كمرشح ، نقوم بتخزين [0 ، 5 ، 5 ، 5 ، 5 ، 5 ، 5 ، 5 ، 5 ، 5] ، والتي من السهل إعادة بناء القائمة الأولية. إذا قمت بتقليص الحجم ، فمن الواضح أن تخزين الرقم 50 يستغرق مساحة أكبر من تخزين الرقم 5. لكن لماذا تتوقف عند هذا الحد؟ دعونا نضغط أكثر من ذلك بقليل!
الخطوة التالية هي استخدام "ترميز جولومب رايس". يمكن لطريقة التشفير هذه ترميز قائمة حيث يكون كل رقم في الجدول قريبًا جدًا من رقم معين. وقائمتنا هي ذلك بالضبط! من المحتمل أن يكون كل رقم من الأرقام في قائمتنا قريبًا من 5 (أو قريبًا من المعدل الإيجابي الخاطئ ، وهو M) ، لذلك خذ حاصل كل رقم على M (اقسم كل رقم على 5 وتجاهل أسقط الباقي) ، سيكون على الأرجح 0 (إذا كان الرقم أقل بقليل من 5) أو 1 (إذا كان الرقم أكبر قليلاً من 5). من الممكن أيضًا أن يكون حاصل القسمة 2 ، 3 ، إلخ ، لكن الاحتمال أصغر بكثير. عظيم! لذا يمكننا الاستفادة من هذا: سنستخدم أقل عدد ممكن من البتات لتشفير حاصل القسمة الأصغر ، بينما نستخدم المزيد من عملات البيتكوين لتشفير حواجز أكبر ، ولكن أقل احتمالية. بعد ذلك ، نحتاج أيضًا إلى ترميز الباقي (لأننا نريد أن نكون قادرين على إعادة بناء القائمة بأكملها تمامًا) ، والتي ستكون دائمًا في النطاق [0 ، M - 1] (في هذه الحالة [0 ، 4]). بالنسبة لبرنامج التشفير ، نستخدم التعيينات التالية:
من السهل فهم التعيين أعلاه: يشير عدد الأرقام 1s إلى حاصل القسمة الذي نريد ترميزه ، ويشير 0 إلى نهاية ترميز حاصل القسمة. لذلك ، لكل رقم في قائمتنا ، يمكننا استخدام الجدول أعلاه لتشفير حاصل القسمة ، ثم تحويل الباقي إلى ثنائي باستخدام bittruck الذي يمكن أن يمثل قيمة قصوى لـ M-1. هنا الباقي هو 4 ، وهناك حاجة إلى 3 بتات فقط. فيما يلي جدول يوضح الباقي المحتمل وتشفيراتها على سبيل المثال لدينا:
لذلك ، من الناحية المثالية ، سيتم ترميز قائمتنا [0 ، 5 ، 5 ، 5 ، 5 ، 5 ، 5 ، 5 ، 5 ، 5 ، 5] على النحو التالي:
قبل أن ننتقل إلى حالة أكثر واقعية ، دعنا نرى ما إذا كان بإمكاننا استعادة قائمتنا الأصلية باستخدام هذا الفلتر.
الآن ما لدينا هو "0000100001000010000100001000010000100001000010000". نحن نعرف كود Golomb-Rice ، ونعلم أن M هو 5 (لأن هذا سيكون معرفة عامة ، ومعروف لكل من يستخدم بناء المرشح هذا). بما أننا نعلم أن M تساوي 5 ، فإننا نعلم أنه سيكون هناك 3 بتات لتشفير الباقي. لذلك ، يمكننا تحويل هذا الفلتر إلى قائمة مصفوفة "حاصل الباقي" التالية:
حسنًا يا عزيزي ، دعنا نرى كيف يمكننا إنشاء مثل هذا المرشح من الكتل.
يمكن العثور على الكود الكامل المستخدم هنا في مستودع جيثب هذا. سأعرض فقط بعض قصاصات الكود الكاذب هنا. جوهر هذا الكود هو وظيفة تسمى buildFilter ، والتي يمكن استخدامها من قبل عملاء البيتكوين لاستدعاء bitcoind والكتل المقابلة. تبدو الوظيفة كما يلي:
func constructFilter (bc \ * bitcoind.Bitcoind، block bitcoind.Block) ([] بايت ، خطأ) {
// 1 يجمع كل العناصر من الكتلة التي نريد إضافتها إلى عامل التصفية
// 2 حول هذه الكائنات إلى أرقام وفرزها
// 3 احصل على الفرق بين عددين متجاورين في قائمة الأرقام المصنفة
// 4 استخدم ترميز Golomb-Rice لترميز هذه الاختلافات
}
لذا ، فإن الخطوة الأولى هي جمع كل الكائنات من الكتلة التي نريد إضافتها إلى الفلتر. بدءًا من BIP ، نعلم أن هذه الكائنات تشمل جميع المفاتيح العامة للبرنامج النصي المستنفد ، وكل مفتاح عام للبرنامج النصي الناتج. يضع BIP أيضًا بعض القواعد الإضافية: نتخطى المدخلات إلى معاملة coinbase (وهو أمر غير منطقي لأنه لا يحتوي على مدخلات) ، ونمرر جميع مخرجات OP \ _RETURN. نقوم أيضًا بإلغاء تكرار البيانات. إذا كان هناك مفتاحان عموميان متطابقان للبرنامج النصي ، فإننا نضيفه مرة واحدة فقط إلى عامل التصفية.
// قائمة الكائنات التي نرغب في إضافتها إلى عامل التصفية
// قم بتضمين جميع المفاتيح العامة للبرنامج النصي المستنفد ، وكل مفتاح عام لبرنامج نصي الإخراج
// نحن نستخدم "خريطة" ، والتي تزيل المفاتيح العامة للبرنامج النصي المكرر
كائنات: = جعل (الخريطة [string] هيكل {})
// تسهيل كل معاملة في الكتلة
بالنسبة إلى i ، tx: = range block.Tx {
// إضافة مفتاح عام للبرنامج النصي لكل إخراج
// في قائمة الأشياء لدينا
لـ \ _ ، txOut: = النطاق tx.Vout {
PubKey: = txOut.PubKey
إذا كان len (PubKey) == 0 {
يكمل
}
// تخطي إذا تم إخراج OP \ _RETURN (0x6a)
إذا spk [0] == 0x6a {
يكمل
}
أشياء [skpStr] = هيكل {} {}
}
// لا تضيف مدخلات معاملة coinbase
إذا كنت == 0 {
يكمل
}
// لكل إدخال ، احصل على المفتاح العام للبرنامج النصي الخاص به
لـ \ _، txIn: = النطاق tx.Vin {
prevTx ، يخطئ: = bc.GetRawTransaction (txIn.Txid)
إذا أخطأت! = لا شيء {
العودة لا شيء ، يخطئ
}
PubKey: = prevTx.Vout [txIn.Vout] .PubKey
إذا كان len (PubKey) == 0 {
يكمل
}
أشياء [spkStr] = هيكل {} {}
}
}
حسنًا ، الآن يتم جمع كل الكائنات. الآن ، نحدد المتغير N ليكون طول الرسم البياني للكائن. هنا ، N تساوي 85.
الخطوة التالية هي تحويل كائننا إلى أرقام موزعة بشكل موحد على فترة. مرة أخرى ، يعتمد النطاق على مدى ارتفاع المعدل الإيجابي الخاطئ الذي تريده. يعرف BIP158 الثابت M بأنه 784931. هذا يعني أن احتمال وجود موجب خاطئ هو 1 في 784931. تمامًا كما فعلنا من قبل ، نأخذ المعدل الإيجابي الخاطئ M مضروبًا في N ونحصل على نطاق توزيع جميع الأرقام. نحدد هذا النطاق على أنه F ، أي F = M \ * N. هنا ، F = 66719135. لن أخوض في تفاصيل الوظائف التي تعين الكائنات على الأرقام (يمكنك العثور على التفاصيل في مستودع جيثب المرتبط أعلاه). كل ما تحتاج إلى معرفته هو أنه يأخذ كإدخال للكائن ، والثابت F (الذي يحدد النطاق الذي يحتاج الكائن إلى تعيينه) ، ومفتاح (تجزئة الكتلة). بمجرد حصولنا على جميع الأرقام ، نقوم بفرز القائمة بترتيب تصاعدي ثم إنشاء قائمة جديدة تسمى الاختلافات التي تحتوي على الفرق بين رقمين متجاورين في قائمة الأرقام المصنفة.
الأرقام: = make ([] uint64، 0، N)
// التكرار بين جميع الكائنات وتحويلها إلى أرقام موزعة بالتساوي في النطاق [0 ، F]
// وتخزين هذه الأرقام كقائمة أرقام
لـ o: = كائنات النطاق {
// باستخدام المفتاح المحدد ، والحد الأقصى للرقم (F) وبايت الكائن (س) ،
// تحويل الكائن إلى رقم بين 0 و F.
v: = convertToNumber (b، F، key)
أرقام = إلحاق (أرقام ، ت)
}
// فرز قائمة الأرقام
sort.Slice (أرقام ، func (i، j int) bool {إرجاع الأرقام [i] <أرقام [j] })
// تحويل قائمة الأرقام إلى قائمة الاختلافات
الاختلافات: = make ([] uint64، N)
بالنسبة إلى i ، num: = أرقام النطاق {
إذا كنت == 0 {
اختلافات [i] = عدد
يكمل
}
اختلافات [i] = num - أرقام [i-1]
}
عظيم! هذه صورة تعرض قائمة بالأرقام والاختلافات.
أثناء التصغير ، يتم توزيع 85 رقمًا بالتساوي في جميع أنحاء المساحة! لذا فإن القيم الموجودة في قائمة الاختلافات صغيرة جدًا أيضًا.
الخطوة الأخيرة هي ترميز قائمة الاختلافات باستخدام ترميز Golomb-Rice. تذكر من الشرح السابق أننا بحاجة إلى قسمة كل فرق على القيمة الأكثر احتمالًا ثم ترميز حاصل القسمة والباقي. في مثالنا السابق ، قلت إن القيمة الأكثر ترجيحًا هي M ، والباقي سيكون بين [0 ، M]. ومع ذلك ، لا يقوم BIP158 بهذا ، كما وجدنا 2 ، وهي ليست المعلمة التي تقلل حجم المرشح النهائي. لذلك بدلاً من استخدام M ، نحدد ثابتًا جديدًا P ونستخدم 2 ^ P كمعامل Golomb-Rice. يتم تعريف P على أنه 19. هذا يعني أننا نقسم كل فرق على 2 ^ 19 للحصول على حاصل القسمة والباقي ، والباقي يتم ترميزه في ثنائي بـ 19 بت.
عامل التصفية: = bstream.NewBStreamWriter (0)
// لكل قيمة في قائمة الفروق ، احصل على حاصل القسمة والباقي بالقسمة على 2 ^ P.
لـ \ _ ، د: = اختلافات النطاق {
q: = math.Floor (float64 (d) /math.Exp2 (float64 (P)))
r: = d - uint64 (math.Exp2 (float64 (P)) \ * q)
// التشفير
بالنسبة إلى i: = 0 ؛ أنا <int (q) ؛ أنا ++ {
filter.WriteBit (صحيح)
}
filter.WriteBit (خطأ)
filter.WriteBits (ص ، ف)
}
بالضبط نفس المرشح الذي حصلنا عليه في bitcoind باستثناء أول وحدتي بايت! لماذا يوجد اختلاف في أول 2 بايت؟ لأن BIP تقول أن قيمة N تحتاج إلى تشفيرها بتنسيق CompactSize وتظهر أمام المرشح بحيث يمكن فك تشفيرها بواسطة جهاز الاستقبال. يتم ذلك عن طريق:
fd: = filter.Bytes ()
بايت المخزن المؤقت
زيادة حجم (سلك. IntSerializeSize (uint64 (N)) + len (fd))
يخطئ = wire.WriteInt (& عازلة، 0، uint64 (N))
إذا أخطأت! = لا شيء {
العودة لا شيء ، يخطئ
}
\ _ ، يخطئ = المخزن المؤقت. اكتب (fd)
إذا أخطأت! = لا شيء {
العودة لا شيء ، يخطئ
}
إذا قمنا الآن بطباعة الفلتر مرة أخرى ، فسنجد أنه مطابق تمامًا لنتائج bitcoind:
ومع ذلك ، ما أفهمه شخصيًا هو أنه لا توجد حاجة لإضافة N إلى الفلتر. إذا كنت تعرف قيمة P ، فيمكنك إيجاد قيمة N. دعنا نرى ما إذا كان بإمكاننا استعادة قائمة الأرقام الأصلية باستخدام إخراج المرشح الأول:
ب: = bstream.NewBStreamReader (عامل التصفية)
(
أرقام [] uint64
prevNum uint64
)
ل {
// اقرأ حاصل القسمة من سلسلة البايت. أول 0 تم العثور عليه يشير إلى نهاية حاصل القسمة
// قبل مواجهة 0 ، يمثل الرقم 1 حاصل القسمة
س uint64
c ، يخطئ: = b.ReadBit ()
إذا أخطأت! = لا شيء {
العودة يخطئ
}
ل ج {
ف ++
ج ، يخطئ = ب.ReadBit ()
إذا كانت الأخطاء (يخطئ ، io.EOF) {
استراحة
} وإلا إذا أخطأت! = لا شيء {
العودة يخطئ
}
}
// تقوم بتات P التالية بترميز الباقي
r ، يخطئ: = b.ReadBits (P)
إذا كانت الأخطاء (يخطئ ، io.EOF) {
استراحة
} وإلا إذا أخطأت! = لا شيء {
العودة يخطئ
}
n: = q \ * uint64 (math.Exp2 (float64 (P))) + r
الأسطوانات: = n + prevNum
أرقام = إلحاق (أرقام ، عدد)
prevNum = عدد
}
fmt.Println (أرقام)
تنتج العملية المذكورة أعلاه نفس قائمة الأرقام ، لذا يمكننا إعادة بنائها دون معرفة N. لذلك لست متأكدًا من الأساس المنطقي لإضافة N إلى الفلتر. إذا كنت تعرف سبب وجوب تضمين N ، فيرجى إبلاغي بذلك!
شكرا للقراءة!
شاهد النسخة الأصلية
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
وأوضح BIP 158 كتلة مرشح كثيف
بقلم ايل موتون
في هذه المقالة ، أصف بإيجاز الحاجة إلى عملاء خفيفين في Bitcoin ولماذا تخدم "مرشحات الكتلة المدمجة" هذه الحاجة بشكل أفضل من "فلاتر Bloom". ثم أشرح بالتفصيل كيف يعمل مرشح الكتلة الكثيفة ، من خلال تجول خطوة بخطوة لبناء مثل هذا الفلتر على شبكة اختبار.
معنى مرشح الكتلة
عميل Bitcoin الخفيف (برنامج Bitcoin light) هو برنامج لا يهدف إلى تخزين blockchain من Bitcoin ولكن لدعم محفظة Bitcoin. هذا يعني أنه يجب أن يكون قادرًا على بث المعاملات إلى الشبكة ، ولكن الأهم من ذلك ، يجب أن يكون قادرًا على العثور على معاملات جديدة من السلسلة المتعلقة بهذه المحفظة. هناك نوعان من هذه المعاملات ذات الصلة: إرسال الأموال إلى هذه المحفظة (إنشاء مخرجات جديدة لعنوان هذه المحفظة) ، وإنفاق أحد UTXOs التي تتحكم فيها هذه المحفظة.
ما هو الخطأ في مرشحات bloom؟
قبل BIP 158 ، كان الأسلوب الأكثر شيوعًا للعملاء الخفيفين هو مرشح Bloom الموصوف في BIP 371. نمط مرشح Bloom هو أنك تأخذ جميع كائنات البيانات التي تهتم بها (على سبيل المثال ، المفاتيح العامة للبرنامج النصي لـ UTXOs التي تم إنفاقها وإنشاءها) ، وتجزئتها واحدة تلو الأخرى عدة مرات ، وإضافة كل نتيجة إلى In صورة نقطية تسمى "مرشح الازهار". يمثل هذا المرشح ما تهتم به. بعد ذلك ، ترسل هذا الفلتر إلى عقدة Bitcoin التي تثق بها وتطلب منهم إرسال كل ما يطابق هذا الفلتر.
تكمن المشكلة في أن هذه العملية ليست خاصة جدًا ، لأنك لا تزال تسرّب بعض المعلومات إلى عقدة Bitcoin التي تقبل الفلتر. يمكنهم معرفة الصفقات التي تهتم بها والصفقات التي لا تهتم بها على الإطلاق ؛ لا يمكنهم أيضًا إرسال أشياء تطابق المرشحات. لذلك ، فهي ليست مثالية للعملاء الخفيفين. ولكن في الوقت نفسه ، فهي ليست مثالية لعقد Bitcoin التي تخدم العملاء الخفيفين. في كل مرة ترسل فيها عامل تصفية ، يتعين عليهم تحميل الكتلة ذات الصلة من القرص ثم تحديد ما إذا كانت هناك معاملات تطابق الفلتر الخاص بك. فقط استمر في إرسال عوامل تصفية مزيفة ويمكنك تفجيرها - بشكل أساسي هجوم DOS. إن إنشاء مرشح يتطلب القليل من الطاقة ، ولكنه يتطلب الكثير من الطاقة للاستجابة لمثل هذا الطلب.
مرشح كتلة كثيفة
حسنًا ، السمات التي نحتاجها هي:
باستخدام عامل تصفية كتلة كثيفة ، سيقوم الخادم (العقدة الكاملة) بإنشاء مرشح محدد لكل كتلة ، بما في ذلك جميع كائنات البيانات في هذه الكتلة. يجب حساب هذا المرشح مرة واحدة فقط وتخزينه إلى الأبد. إذا طلب العميل الخفيف مرشحًا لكتلة معينة ، فلا يوجد عدم تناسق هنا - لأن الخادم لا يحتاج إلى القيام بأي عمل أكثر من العميل الطالب. يمكن للعميل الخفيف أيضًا اختيار مصادر معلومات متعددة لتنزيل الكتلة الكاملة للتأكد من أنها متسقة ؛ علاوة على ذلك ، يمكن للعميل الخفيف دائمًا تنزيل الكتلة الكاملة للتحقق مما إذا كان الفلتر الذي يوفره الخادم صحيحًا (يطابق الكتلة ذات الصلة) محتوى). فائدة أخرى هي أنه أكثر خصوصية بهذه الطريقة. لم يعد العميل الخفيف بحاجة إلى إرسال بصمة البيانات التي يريدها إلى الخادم. كما يصبح من الصعب تحليل نشاط العميل الخفيف. بعد أن يحصل العميل الخفيف على هذا المرشح من الخادم ، فإنه يتحقق مما إذا كان المرشح يحتوي على البيانات التي يريدها ، وإذا كان الأمر كذلك ، فإن العميل الخفيف يطلب الكتلة الكاملة. وتجدر الإشارة أيضًا إلى أنه من أجل خدمة العملاء الخفيفين بهذه الطريقة ، تحتاج العقد الكاملة إلى الاستمرار في استخدام هذه المرشحات ، وقد يرغب العملاء الخفيفون أيضًا في الاستمرار في عدد قليل من المرشحات ، لذلك اجعل المرشحات خفيفة قدر الإمكان. الكمية مهمة جدًا ( وهذا هو سبب تسميته "مرشح الكتلة الكثيفة").
جيد جدًا! نحن الآن ندخل في الأشياء النادرة. كيف يتم إنشاء هذا الفلتر؟ كيف تبدو؟
ما هي احتياجاتنا؟
المعلومات الأساسية الموجودة في المرشح هي: المفتاح العام للبرنامج النصي لكل إدخال لكل معاملة (أي ، المفتاح العام للبرنامج النصي لكل UTXO مستهلك) ، والمفتاح العام للبرنامج النصي لكل إخراج من كل معاملة. في الأساس مثل هذا:
كائنات = {spk1، spk2، spk3، spk4، ...، spkN} // قائمة بالمفاتيح العمومية للبرنامج النصي N
من الناحية الفنية ، يمكننا التوقف هنا - يمكن لقائمة المفاتيح العامة للبرنامج النصي أن تعمل أيضًا كمرشح خاص بنا. هذه نسخة مكثفة من الكتلة تحتوي على المعلومات التي يحتاجها العملاء الخفيفون. باستخدام هذه القائمة ، يمكن للعميل الخفيف تأكيد 100٪ ما إذا كانت هناك معاملة ذات فائدة في الكتلة. لكن هذه القائمة كبيرة جدًا. لذلك ، فإن جميع خطواتنا التالية هي جعل هذه القائمة مضغوطة قدر الإمكان. هذا هو المكان الذي تصبح فيه الأشياء مثيرة للاهتمام.
أولاً ، يمكننا تحويل كل كائن إلى رقم ضمن نطاق معين ، وجعل رقم كل كائن موزعًا بالتساوي ضمن هذا النطاق. لنفترض أن لدينا 10 كائنات (N = 10) ، ثم لدينا نوع من الوظائف التي تحول كل كائن إلى رقم. لنفترض أننا اخترنا النطاق [0 ، 10] (بما أن لدينا 10 كائنات). الآن ، ستأخذ وظيفة "التجزئة إلى الرقم" كل كائن كمدخل وتنتج رقمًا بالحجم [0 ، 10] على التوالي. يتم توزيع الأرقام بالتساوي عبر هذا النطاق. هذا يعني أنه بعد الفرز ، سننتهي برسم بياني مثل هذا (في حالة مثالية جدًا جدًا):
الأرقام: = {1،2،3،4،5،6،7،8،9،10}
يقوم العميل الخفيف بتنزيل مثل هذا الفلتر ، على أمل معرفة ما إذا كان الكائن الذي يبحث عنه يطابق المرشح. يأخذون فقط الكائن الذي يهتمون به ويقومون بتشغيل نفس وظيفة "التجزئة إلى الرقم" لمعرفة ما إذا كانت النتيجة في هذا الفلتر. أين المشكلة؟ المشكلة هي أن الأرقام الموجودة في الفلتر تستهلك بالفعل كل الاحتمالات في تلك المساحة! هذا يعني أنه بغض النظر عن الكائنات التي يهتم بها العميل الخفيف ، يجب أن تتطابق النتيجة الرقمية الناتجة مع هذا المرشح. بمعنى آخر ، يحتوي هذا المرشح على "معدل إيجابي خاطئ" بقيمة 1 (ملاحظة المترجم: تعني "إيجابية كاذبة" هنا أن الكتلة قد لا تحتوي على النتيجة التي حصل عليها المرشح هي نعم). ليس جيد جدا. كما يوضح أيضًا أنه في عملية ضغط البيانات لإنشاء الفلتر ، نفقد الكثير من المعلومات. نحن بحاجة إلى معدل إيجابي خاطئ أعلى. بعد ذلك ، افترض أننا نريد أن يكون المعدل الإيجابي الخاطئ 5. ثم يمكننا جعل الكائنات الموجودة في الكتلة تتطابق بالتساوي مع الأرقام الموجودة في النطاق [0 ، 50]:
لدينا الآن قائمة مرتبة من الأرقام موزعة بالتساوي في الفترة [0 ، 50]. نعلم أن هناك 10 أرقام في هذه القائمة. هذا يعني أنه يمكننا استنتاج أن * الاختلاف * بين رقمين متجاورين في قائمة الأرقام المرتبة هذه من المرجح أن يكون 5. بشكل عام ، إذا كان لدينا N كائنات ونريد معدل إيجابي خاطئ لـ M ، فيجب أن يكون حجم المساحة N \ * M. وهذا يعني أن حجم هذه الأرقام يجب أن يكون بين 0 و N \ * M ، ولكن (بعد الفرز) فإن احتمال الاستيفاء لرقمين متجاورين تم فحصهما هو M. ويجب تخزين M أصغر من الرقم في مساحة N \ * M. لذلك ، بدلاً من تخزين كل رقم فردي ، يمكننا تخزين الفرق بين رقمين متجاورين. في المثال أعلاه ، هذا يعني أنه بدلاً من تخزين [0 ، 5 ، 10 ، 15 ، 20 ، 25 ، 30 ، 35 ، 40 ، 45 ، 50] كمرشح ، نقوم بتخزين [0 ، 5 ، 5 ، 5 ، 5 ، 5 ، 5 ، 5 ، 5 ، 5] ، والتي من السهل إعادة بناء القائمة الأولية. إذا قمت بتقليص الحجم ، فمن الواضح أن تخزين الرقم 50 يستغرق مساحة أكبر من تخزين الرقم 5. لكن لماذا تتوقف عند هذا الحد؟ دعونا نضغط أكثر من ذلك بقليل!
الخطوة التالية هي استخدام "ترميز جولومب رايس". يمكن لطريقة التشفير هذه ترميز قائمة حيث يكون كل رقم في الجدول قريبًا جدًا من رقم معين. وقائمتنا هي ذلك بالضبط! من المحتمل أن يكون كل رقم من الأرقام في قائمتنا قريبًا من 5 (أو قريبًا من المعدل الإيجابي الخاطئ ، وهو M) ، لذلك خذ حاصل كل رقم على M (اقسم كل رقم على 5 وتجاهل أسقط الباقي) ، سيكون على الأرجح 0 (إذا كان الرقم أقل بقليل من 5) أو 1 (إذا كان الرقم أكبر قليلاً من 5). من الممكن أيضًا أن يكون حاصل القسمة 2 ، 3 ، إلخ ، لكن الاحتمال أصغر بكثير. عظيم! لذا يمكننا الاستفادة من هذا: سنستخدم أقل عدد ممكن من البتات لتشفير حاصل القسمة الأصغر ، بينما نستخدم المزيد من عملات البيتكوين لتشفير حواجز أكبر ، ولكن أقل احتمالية. بعد ذلك ، نحتاج أيضًا إلى ترميز الباقي (لأننا نريد أن نكون قادرين على إعادة بناء القائمة بأكملها تمامًا) ، والتي ستكون دائمًا في النطاق [0 ، M - 1] (في هذه الحالة [0 ، 4]). بالنسبة لبرنامج التشفير ، نستخدم التعيينات التالية:
0000 10000 10000 10000 10000 10000 10000 10000 10000 10000
قبل أن ننتقل إلى حالة أكثر واقعية ، دعنا نرى ما إذا كان بإمكاننا استعادة قائمتنا الأصلية باستخدام هذا الفلتر.
الآن ما لدينا هو "0000100001000010000100001000010000100001000010000". نحن نعرف كود Golomb-Rice ، ونعلم أن M هو 5 (لأن هذا سيكون معرفة عامة ، ومعروف لكل من يستخدم بناء المرشح هذا). بما أننا نعلم أن M تساوي 5 ، فإننا نعلم أنه سيكون هناك 3 بتات لتشفير الباقي. لذلك ، يمكننا تحويل هذا الفلتر إلى قائمة مصفوفة "حاصل الباقي" التالية:
[(0 ، 0) ، (1 ، 0) ، (1 ، 0) ، (1 ، 0) ، (1 ، 0) ، (1 ، 0) ، (1 ، 0) ، (1 ، 0) ، ( 1 ، 0) ، (1 ، 0)]
مع العلم أن حاصل القسمة يتم الحصول عليه عن طريق القسمة على M (5) ، يمكننا استرداد:
[0 ، 5 ، 5 ، 5 ، 5 ، 5 ، 5 ، 5 ، 5 ، 5]
نعلم أيضًا أن هذه القائمة تمثل الفرق بين رقمين متجاورين ، لذا يمكننا استعادة القائمة الأصلية:
[0 ، 5 ، 10 ، 15 ، 20 ، 25 ، 30 ، 35 ، 40 ، 45 ، 50]
مثال أكثر واقعية
سنحاول الآن إنشاء مرشح لكتلة اختبار Bitcoin حقيقية. سأستخدم الكتلة 2101914. دعونا نرى كيف يبدو مرشحها:
بيتكوين- cli getblockhash 2101914 000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c $ bitcoin-cli getblockfilter 000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c { تصفية 15255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0b0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f1 0a92f6d70c4f522aa6877558f62b34b56ade12fa2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270 "، "الرأس": "8d0cd8353342930209ac7027be150e679bbc7c65cc62bb8392968e43a6ea3bfe" }
حسنًا يا عزيزي ، دعنا نرى كيف يمكننا إنشاء مثل هذا المرشح من الكتل.
يمكن العثور على الكود الكامل المستخدم هنا في مستودع جيثب هذا. سأعرض فقط بعض قصاصات الكود الكاذب هنا. جوهر هذا الكود هو وظيفة تسمى buildFilter ، والتي يمكن استخدامها من قبل عملاء البيتكوين لاستدعاء bitcoind والكتل المقابلة. تبدو الوظيفة كما يلي:
func constructFilter (bc \ * bitcoind.Bitcoind، block bitcoind.Block) ([] بايت ، خطأ) { // 1 يجمع كل العناصر من الكتلة التي نريد إضافتها إلى عامل التصفية // 2 حول هذه الكائنات إلى أرقام وفرزها // 3 احصل على الفرق بين عددين متجاورين في قائمة الأرقام المصنفة // 4 استخدم ترميز Golomb-Rice لترميز هذه الاختلافات }
لذا ، فإن الخطوة الأولى هي جمع كل الكائنات من الكتلة التي نريد إضافتها إلى الفلتر. بدءًا من BIP ، نعلم أن هذه الكائنات تشمل جميع المفاتيح العامة للبرنامج النصي المستنفد ، وكل مفتاح عام للبرنامج النصي الناتج. يضع BIP أيضًا بعض القواعد الإضافية: نتخطى المدخلات إلى معاملة coinbase (وهو أمر غير منطقي لأنه لا يحتوي على مدخلات) ، ونمرر جميع مخرجات OP \ _RETURN. نقوم أيضًا بإلغاء تكرار البيانات. إذا كان هناك مفتاحان عموميان متطابقان للبرنامج النصي ، فإننا نضيفه مرة واحدة فقط إلى عامل التصفية.
// قائمة الكائنات التي نرغب في إضافتها إلى عامل التصفية // قم بتضمين جميع المفاتيح العامة للبرنامج النصي المستنفد ، وكل مفتاح عام لبرنامج نصي الإخراج // نحن نستخدم "خريطة" ، والتي تزيل المفاتيح العامة للبرنامج النصي المكرر كائنات: = جعل (الخريطة [string] هيكل {}) // تسهيل كل معاملة في الكتلة بالنسبة إلى i ، tx: = range block.Tx { // إضافة مفتاح عام للبرنامج النصي لكل إخراج // في قائمة الأشياء لدينا لـ \ _ ، txOut: = النطاق tx.Vout { PubKey: = txOut.PubKey إذا كان len (PubKey) == 0 { يكمل } // تخطي إذا تم إخراج OP \ _RETURN (0x6a) إذا spk [0] == 0x6a { يكمل } أشياء [skpStr] = هيكل {} {} } // لا تضيف مدخلات معاملة coinbase إذا كنت == 0 { يكمل } // لكل إدخال ، احصل على المفتاح العام للبرنامج النصي الخاص به لـ \ _، txIn: = النطاق tx.Vin { prevTx ، يخطئ: = bc.GetRawTransaction (txIn.Txid) إذا أخطأت! = لا شيء { العودة لا شيء ، يخطئ } PubKey: = prevTx.Vout [txIn.Vout] .PubKey إذا كان len (PubKey) == 0 { يكمل } أشياء [spkStr] = هيكل {} {} } }
حسنًا ، الآن يتم جمع كل الكائنات. الآن ، نحدد المتغير N ليكون طول الرسم البياني للكائن. هنا ، N تساوي 85.
الخطوة التالية هي تحويل كائننا إلى أرقام موزعة بشكل موحد على فترة. مرة أخرى ، يعتمد النطاق على مدى ارتفاع المعدل الإيجابي الخاطئ الذي تريده. يعرف BIP158 الثابت M بأنه 784931. هذا يعني أن احتمال وجود موجب خاطئ هو 1 في 784931. تمامًا كما فعلنا من قبل ، نأخذ المعدل الإيجابي الخاطئ M مضروبًا في N ونحصل على نطاق توزيع جميع الأرقام. نحدد هذا النطاق على أنه F ، أي F = M \ * N. هنا ، F = 66719135. لن أخوض في تفاصيل الوظائف التي تعين الكائنات على الأرقام (يمكنك العثور على التفاصيل في مستودع جيثب المرتبط أعلاه). كل ما تحتاج إلى معرفته هو أنه يأخذ كإدخال للكائن ، والثابت F (الذي يحدد النطاق الذي يحتاج الكائن إلى تعيينه) ، ومفتاح (تجزئة الكتلة). بمجرد حصولنا على جميع الأرقام ، نقوم بفرز القائمة بترتيب تصاعدي ثم إنشاء قائمة جديدة تسمى الاختلافات التي تحتوي على الفرق بين رقمين متجاورين في قائمة الأرقام المصنفة.
الأرقام: = make ([] uint64، 0، N) // التكرار بين جميع الكائنات وتحويلها إلى أرقام موزعة بالتساوي في النطاق [0 ، F] // وتخزين هذه الأرقام كقائمة أرقام لـ o: = كائنات النطاق { // باستخدام المفتاح المحدد ، والحد الأقصى للرقم (F) وبايت الكائن (س) ، // تحويل الكائن إلى رقم بين 0 و F. v: = convertToNumber (b، F، key) أرقام = إلحاق (أرقام ، ت) } // فرز قائمة الأرقام sort.Slice (أرقام ، func (i، j int) bool {إرجاع الأرقام [i] <أرقام [j] }) // تحويل قائمة الأرقام إلى قائمة الاختلافات الاختلافات: = make ([] uint64، N) بالنسبة إلى i ، num: = أرقام النطاق { إذا كنت == 0 { اختلافات [i] = عدد يكمل } اختلافات [i] = num - أرقام [i-1] }
عظيم! هذه صورة تعرض قائمة بالأرقام والاختلافات.
الخطوة الأخيرة هي ترميز قائمة الاختلافات باستخدام ترميز Golomb-Rice. تذكر من الشرح السابق أننا بحاجة إلى قسمة كل فرق على القيمة الأكثر احتمالًا ثم ترميز حاصل القسمة والباقي. في مثالنا السابق ، قلت إن القيمة الأكثر ترجيحًا هي M ، والباقي سيكون بين [0 ، M]. ومع ذلك ، لا يقوم BIP158 بهذا ، كما وجدنا 2 ، وهي ليست المعلمة التي تقلل حجم المرشح النهائي. لذلك بدلاً من استخدام M ، نحدد ثابتًا جديدًا P ونستخدم 2 ^ P كمعامل Golomb-Rice. يتم تعريف P على أنه 19. هذا يعني أننا نقسم كل فرق على 2 ^ 19 للحصول على حاصل القسمة والباقي ، والباقي يتم ترميزه في ثنائي بـ 19 بت.
عامل التصفية: = bstream.NewBStreamWriter (0) // لكل قيمة في قائمة الفروق ، احصل على حاصل القسمة والباقي بالقسمة على 2 ^ P. لـ \ _ ، د: = اختلافات النطاق { q: = math.Floor (float64 (d) /math.Exp2 (float64 (P))) r: = d - uint64 (math.Exp2 (float64 (P)) \ * q) // التشفير بالنسبة إلى i: = 0 ؛ أنا <int (q) ؛ أنا ++ { filter.WriteBit (صحيح) } filter.WriteBit (خطأ) filter.WriteBits (ص ، ف) }
عظيم! الآن يمكننا إخراج المرشح ، والحصول على:
71d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864023833f2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0b0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade12fa2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
بالضبط نفس المرشح الذي حصلنا عليه في bitcoind باستثناء أول وحدتي بايت! لماذا يوجد اختلاف في أول 2 بايت؟ لأن BIP تقول أن قيمة N تحتاج إلى تشفيرها بتنسيق CompactSize وتظهر أمام المرشح بحيث يمكن فك تشفيرها بواسطة جهاز الاستقبال. يتم ذلك عن طريق:
fd: = filter.Bytes () بايت المخزن المؤقت زيادة حجم (سلك. IntSerializeSize (uint64 (N)) + len (fd)) يخطئ = wire.WriteInt (& عازلة، 0، uint64 (N)) إذا أخطأت! = لا شيء { العودة لا شيء ، يخطئ } \ _ ، يخطئ = المخزن المؤقت. اكتب (fd) إذا أخطأت! = لا شيء { العودة لا شيء ، يخطئ }
إذا قمنا الآن بطباعة الفلتر مرة أخرى ، فسنجد أنه مطابق تمامًا لنتائج bitcoind:
5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864023833f2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0b0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade12fa2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
نجاح!
ومع ذلك ، ما أفهمه شخصيًا هو أنه لا توجد حاجة لإضافة N إلى الفلتر. إذا كنت تعرف قيمة P ، فيمكنك إيجاد قيمة N. دعنا نرى ما إذا كان بإمكاننا استعادة قائمة الأرقام الأصلية باستخدام إخراج المرشح الأول:
ب: = bstream.NewBStreamReader (عامل التصفية) ( أرقام [] uint64 prevNum uint64 ) ل { // اقرأ حاصل القسمة من سلسلة البايت. أول 0 تم العثور عليه يشير إلى نهاية حاصل القسمة // قبل مواجهة 0 ، يمثل الرقم 1 حاصل القسمة س uint64 c ، يخطئ: = b.ReadBit () إذا أخطأت! = لا شيء { العودة يخطئ } ل ج { ف ++ ج ، يخطئ = ب.ReadBit () إذا كانت الأخطاء (يخطئ ، io.EOF) { استراحة } وإلا إذا أخطأت! = لا شيء { العودة يخطئ } } // تقوم بتات P التالية بترميز الباقي r ، يخطئ: = b.ReadBits (P) إذا كانت الأخطاء (يخطئ ، io.EOF) { استراحة } وإلا إذا أخطأت! = لا شيء { العودة يخطئ } n: = q \ * uint64 (math.Exp2 (float64 (P))) + r الأسطوانات: = n + prevNum أرقام = إلحاق (أرقام ، عدد) prevNum = عدد } fmt.Println (أرقام)
تنتج العملية المذكورة أعلاه نفس قائمة الأرقام ، لذا يمكننا إعادة بنائها دون معرفة N. لذلك لست متأكدًا من الأساس المنطقي لإضافة N إلى الفلتر. إذا كنت تعرف سبب وجوب تضمين N ، فيرجى إبلاغي بذلك!
شكرا للقراءة!