تفضل العديد من محافظ البيتكوين عند اختيار عملات معدنية لإرسالها استخدام عملة كبيرة ، يكون رصيدها أكبر من المبلغ المرسل. بعد كل معاملة من هذا القبيل ، يتم تشكيل عملة التغيير. بعد مرور بعض الوقت ، أصبحت المحفظة بأكملها متضخمة بهذه العملات البالغة 0.001 (حوالي 10 دولارات في الوقت الحالي) ، وهو ما لا يوجد بالفعل شيء يمكن إنفاقه عليه. عندما ، مرة أخرى ، كنت بحاجة لإجراء صفقة ، حدث لي ما إذا كان من الممكن تجميع المعاملة بحيث لم يكن هناك تغيير. عرضت المحفظة بعناد "قطع" عملة أكبر أخرى ، لذلك قررت أن أختار العملات المعدنية بيدي لجمع المبلغ اللازم. ومع ذلك ، فقد تبين أن هذا ليس بهذه البساطة: فقد تبين أن المبلغ أقل من القيمة المطلوبة أو تجاوزه كثيرًا. نتيجة لذلك ، قررت أنه يجب أن يكون هناك خوارزمية يمكنك من خلالها جمع المبلغ المرغوب فيه من العملات المعدنية أو أكثر من ذلك بقليل. اتضح أن هذا ليس ممكنًا فحسب ، ولكنه يعمل بشكل جيد مما جعلني أكتب هذه المقالة. لكن أول الأشياء أولا.
مشكلة الظهر
مشكلة الظهر معروفة على نطاق واسع: لتعبئة أكبر عدد ممكن من الأشياء القيمة في حقيبة الظهر ، بشرط أن تكون سعة حقيبة الظهر محدودة. في هذه الحالة ، لدينا حالة مشكلة ظهور حقيبة الظهر 0-1 ، حيث أن كل عنصر (عملة معدنية) متاح للتعبئة في حقيبة الظهر مرة واحدة فقط. بالإضافة إلى ذلك ، يتزامن وزن كل "عنصر" مع قيمته ، لذلك نحن نتعامل مع حالة خاصة أكثر ، مشكلة مجموع المجموعات الفرعية . تقترح ويكيبيديا استخدام خوارزمية وراثية ، لكنني قررت البحث عن حل دقيق باستخدام البرمجة الديناميكية ، حيث أن هذا ممكن التحقيق من حيث الموارد ويبدو بسيطًا.
لتقليل مشكلة اختيار العملات المعدنية لمهمة حقيبة الظهر ، تحتاج إلى إجراء تحويل صغير لبيانات الإدخال. والحقيقة هي أن حل مشكلة الحقيبة (على وجه التحديد ، مجموع المجموعات الفرعية) سيمنحنا مجموعة فرعية من المجموعة الأصلية التي لا يتجاوز الحد الأقصى للمبلغ المعلمة (سعة حمل حقيبة الظهر). لكننا غير راضين عن مزيج العملات ، حيث نعطي المبلغ أقل من المبلغ الذي نريد إرساله. ومع ذلك ، فإننا نشعر بالراحة مع مجموعات متفوقة قليلاً. على سبيل المثال ، إذا احتجنا إلى إرسال 0.005 عملة بيتكوين ، ووجدنا مجموعة تعطي 0.00499 ، فهي غير مجدية لنا ، لأنها أقل من المبلغ الذي يريده البائع. لكن إذا وجدنا 0.005001 ، فهذا صحيح. يمكن استخدام satoshiki الإضافي كعمولة (سنتحدث عن ذلك بالتفصيل أدناه) أو نقدمها إلى البائع إذا كان يسمح بإرسال مبلغ أكبر. لذلك ، بمساعدة مشكلة حقيبة الظهر ، نحتاج إلى اختيار ليس العملات المعدنية التي يجب إرسالها ، ولكن يجب عليك أن تترك تلك العملات. ثم "النقص" إلى الحد الأقصى سوف يتحول إلى "تمثال نصفي" من حيث المشكلة الأصلية.
مثال لنفترض أن لدينا مثل هذه العملات: 0.1 BTC ، 0.002 BTC ، 0.00832423 BTC. ونحن بحاجة إلى إرسال 0.01 BTC. سنجد مثل هذه العملات المعدنية ، التي سيكون مجموعها الحد الأقصى ، ولكن أقل من أو يساوي المبلغ الإجمالي لعملاتنا مطروحًا منها المبلغ المرسل ، أي ، هذا الرقم: 0.1 + 0.002 + 0.00832423 - 0.01 = 0.10032423. في هذه الحالة ، يجد بحث بسيط أنه عملة 0.1. نتركها ، مما يعني أننا نرسل الباقي: 0.002 BTC و 0.00832423 BTC ، والتي تعطي إجمالاً 0.01032423 BTC ، وهو أكثر من 0.01 BTC وتناسبنا. (صحيح ، لقد حصلت العمولة على حوالي 3 دولارات ، ولكن دعنا نقول أن الشبكة مشغولة ونريد أن نجعل الإرسال في أسرع وقت ممكن.)
لجنة
لأخذ رسوم المعاملات في الاعتبار ، قمت بتعديل كل عملة إدخال ، مما قلل من رصيدها بالمبلغ الذي يجب دفعه لإدراجها في المعاملة كمدخل. يمكن القيام بذلك عن طريق معرفة حجم الإدخال والعمولة (على سبيل المثال ، 2 satoshi لكل بايت). بالإضافة إلى ذلك ، قمت بتعديل المبلغ المراد إرساله ، مضيفًا إليه سعر جزء المعاملة الذي لا يعتمد على العملات المحددة: الرأس والخروج (العملات). يمكن للمستخدم تحديد كل هذه المعلمات باستخدام الأعلام. يمكنك أيضًا تعطيل التعديل للعمولات بشكل عام عن طريق تحديد عمولة 0 Satoshi لكل بايت.
أخذت معلومات عن أحجام المدخلات والمخرجات في إصدارات مختلفة من العناوين (الكلاسيكية ، والملفوفة segwit segwit الأصلي من هنا: https://bitcoin.stackexchange.com/a/84006
الخوارزميات والتنفيذ
أسقطت على الفور الخوارزمية الجينية ، ربما دون جدوى. تركز على خوارزميات دقيقة. كانت محاولتي الأولى أن أدرك من خلال البحث الشامل لجميع المجموعات ، ولكن حتى على 40 قطعة نقدية كانت تعمل لساعات وكان عليها أن تتخلى عنها. ثم جربت البرمجة الديناميكية المقترحة على ويكيبيديا . في ذلك ، لا يمكنك أن تبقي في الذاكرة المصفوفة بأكملها ، ولكن فقط الصفوف الحالية والسابقة. بالإضافة إلى ذلك ، لسنا بحاجة إلى تخزين القيمة ، لأنها تتزامن مع الوزن وهي رقم العمود. لكننا بحاجة إلى تذكر المجموعة - قررت تخزينها في شكل مجموعة صغيرة. بالإضافة إلى ذلك ، يمكنك تخزين صف واحد فقط ، وبناء الصف التالي في مكانه. يظل كل سجل صف غير صفري في مكانه ويتم نسخه (مع إضافة البتة المقابلة) إلى خلية أخرى عددًا معينًا من الخلايا إلى اليمين (إذا كان فارغًا من قبل). إذا قمت بالترتيب العكسي ، وتصنيف الخلية التي ينتقل إليها "القفز" ، يمكنك ملء كل شيء بشكل صحيح:
تنشئ كل خلية غير صفرية في الصف الحالي في الصف التالي نفسه وخلية أخرى لعدد معين من الخلايا (يساوي قيمة العملة المضافة) إلى اليمين. إذا كانت هناك بالفعل قيمة في تلك الخلية ، فإن الخيار الذي يحتوي على أكبر عدد من العملات المختارة (أي ، غير المدرجة في المعاملة) "يفوز" ، لأننا نريد أن نرسل أقل عدد ممكن من العملات ، وأشياء أخرى متساوية.
في خلية واحدة ، أقضي 8 بايتات على مجموعة بتات ، وعدد الخلايا يساوي عدد ممكن من الأرصدة من 0 إلى كمية العملات المعدنية مطروحًا منها المبلغ المرسل. على سبيل المثال ، إذا كان هناك محفظة بيتكوين واحدة فقط في المحفظة وتم إرسال 0.1 ، فستكون هناك خلايا 100000000000000000000000000000 = 90000000 ، كل منها 8 بايتات ، أي 720 ميغابايت - قليلاً للكمبيوتر الحديث. إذا كان عدد العملات المعدنية أقل من 32 ، فسيكون من الممكن استخدام 4 بايت لكل عملة ، لكنني لم أحسنها. بالإضافة إلى ذلك ، إذا كان هناك أكثر من 64 قطعة نقدية ، فإن البرنامج لا يعمل - سيتعين أيضًا إصلاح ذلك عن طريق إنشاء مجموعة من القطع الطولية التعسفية. أخيرًا ، يمكنك تجاهل آخر علامة في الأرصدة ، وفقدان القليل من الدقة ، ولكن الفوز في الذاكرة 10 مرات. ولكن حتى الآن سوف تفعل.
اتصلت بالبرنامج بلا تغيير ووضعته على gitlab: gitlab.com/starius/changeless . هو مكتوب في الذهاب ، وتجميعها باستخدام go get ، كالعادة. تتوفر ثنائيات لنظام التشغيل Linux و Windows و Mac والتي تم جمعها في CI.
عندما أطلقت البرنامج بعملات معدنية حقيقية ، أدهشتني مدى دقة اختيارها للمزيج الضروري. عندما يكون عدد العملات المعدنية كبيرًا ، يمكن تحديد أي مبلغ تقريبًا يتناسب مع أرصدة العملات بدقة تصل إلى satoshi! يمكنك تغيير المبلغ المطلوب لـ 1 satoshi ويعطي البرنامج مجموعة مختلفة تمامًا من العملات لهذا المبلغ بالضبط. فيما يلي مثال على العمل على 50 قطعة نقدية عشوائية بأرصدة من 0 إلى 1 عملة بيتكوين.
$ cat coins50.txt 0.01331611 0.03906237 0.04847086 0.08453118 0.09748168 0.10395389 0.10619825 0.12156721 0.12923149 0.13587973 0.14798976 0.16053788 0.19011834 0.21570038 0.21946913 0.31861430 0.33435508 0.33718842 0.33789473 0.35976748 0.37360122 0.44944553 0.47572926 0.49927495 0.50992142 0.53062326 0.53079433 0.53542072 0.54715225 0.55019714 0.55313907 0.56656642 0.56673333 0.65879650 0.66228482 0.68424322 0.70436496 0.75638055 0.79095597 0.82438005 0.83684407 0.85151564 0.86862948 0.90054250 0.90239402 0.91636213 0.93087757 0.93579251 0.97207439 0.98248384 $ changeless -amount 10.00000000 -coins coins50.txt Processing item 50/50. 0.09748168 + 0.33435508 + 0.47572926 + 0.53542072 + 0.66228482 + 0.70436496 + 0.75638055 + 0.82438005 + 0.9005425 + 0.90239402 + 0.91636213 + 0.93579251 + 0.97207439 + 0.98248384 = 10.00004651 Tx size: 2118 vBytes. Total fees: 0.00004651 BTC (2.2 sats/vByte). $ changeless -amount 10.00000001 -coins coins50.txt Processing item 50/50. 0.01331611 + 0.09748168 + 0.53079433 + 0.56656642 + 0.70436496 + 0.75638055 + 0.82438005 + 0.86862948 + 0.9005425 + 0.91636213 + 0.93087757 + 0.93579251 + 0.97207439 + 0.98248384 = 10.00004652 Tx size: 2118 vBytes. Total fees: 0.00004651 BTC (2.2 sats/vByte).
تمكن البرنامج من التقاط مجموعات من العملات المعدنية لإرسال 10 عملة بيتكوين بالضبط و 10.00000001 عملة بيتكوين بالضبط (10 عملة بيتكوين و 1 ساتوشي). لرؤية هذا ، يجب عليك طرح العمولة من كمية العملات المعدنية: 10.00004651 - 0.00004651 = 10 ، 10.00004652 - 0.00004651 = 10.00000001.
كيفية الحصول على قائمة أرصدة العملة
بالنسبة لبرنامج Electrum ، وجدت هذه الطريقة (أمر وحدة التحكم):
' '.join((x["value"]) for x in listunspent())
إذا كنت ترغب في استبعاد عملات معدنية معينة ، على سبيل المثال في عنوان معين ، فيمكن القيام بذلك على النحو التالي:
' '.join((x["value"]) for x in listunspent() if x["address"] != "bad address")
بالنسبة لمحافظ أخرى ، لم أجد هذه الطريقة السهلة واضطررت إلى إعادة كتابتها بيدي.