छोटे सिक्कों को जमा किए बिना बीटीसी लेनदेन कैसे करें

भेजने के लिए सिक्के चुनते समय कई बिटकॉइन बड़े पैमाने पर इस्तेमाल करते हैं, जिनमें से शेष राशि भेजी गई राशि से अधिक होती है। इस तरह के प्रत्येक लेनदेन के बाद, एक परिवर्तन सिक्का बनता है। कुछ समय बाद, पूरे बटुए को 0.001 (फिलहाल $ 10) के आदेश के ऐसे सिक्कों के साथ उखाड़ दिया गया है, जो पहले से ही खर्च करने के लिए कुछ भी नहीं है। जब, एक बार फिर, मुझे लेन-देन करने की आवश्यकता हुई, तो मेरे साथ यह हुआ कि क्या लेनदेन को इकट्ठा करना संभव था, ताकि कोई बदलाव न हो। बटुए ने एक और बड़े सिक्के को "काट" करने की पेशकश की, इसलिए मैंने आवश्यक राशि एकत्र करने के लिए अपने हाथों से सिक्के लेने का फैसला किया। हालांकि, यह इतना सरल नहीं निकला: योग या तो वांछित मूल्य से कम हो गया या बहुत अधिक हो गया। नतीजतन, मैंने फैसला किया कि एक एल्गोरिथ्म होना चाहिए जिसके साथ आप सिक्कों से वांछित राशि एकत्र कर सकते हैं या थोड़ा और। यह पता चला कि यह न केवल संभव है, बल्कि इतनी अच्छी तरह से काम करता है जिसने मुझे यह लेख लिखा। लेकिन पहले बातें पहले।

बैकपैक समस्या

बैकपैक समस्या को व्यापक रूप से जाना जाता है: बैकपैक में यथासंभव मूल्यवान चीजों को पैक करने के लिए, बशर्ते कि बैकपैक की क्षमता सीमित हो। इस मामले में, हमारे पास 0-1 बैकपैक समस्या का मामला है , क्योंकि प्रत्येक आइटम (सिक्का) केवल एक बार बैकपैक में पैकिंग के लिए उपलब्ध है। इसके अलावा, प्रत्येक "आइटम" का वजन इसके मूल्य के साथ मेल खाता है, इसलिए हम एक और भी विशेष मामले के साथ काम कर रहे हैं, सबसेट के योग की समस्या । विकिपीडिया एक आनुवंशिक एल्गोरिथ्म का उपयोग करने का सुझाव देता है, लेकिन मैंने गतिशील प्रोग्रामिंग का उपयोग करके एक सटीक समाधान की तलाश करने का फैसला किया, क्योंकि यह संसाधनों के मामले में काफी विश्वसनीय है और सरल दिखता है।

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

एक उदाहरण है। मान लीजिए हमारे पास ऐसे सिक्के हैं: 0.1 बीटीसी, 0.002 बीटीसी, 0.00832423 बीटीसी। और हमें 0.01 बीटीसी भेजने की आवश्यकता है। हमें ऐसे सिक्के मिलेंगे, जिनकी मात्रा अधिकतम होगी, लेकिन हमारे सिक्कों की कुल राशि के बराबर या उससे कम है, जो भेजी गई राशि है, यानी ऐसी संख्या: 0.1 + 0.002 + 0.00832423 - 0.01 = 0.10032423। इस मामले में, एक साधारण खोज से पता चलता है कि यह 0.1 का सिक्का है। हम इसे छोड़ देते हैं, जिसका अर्थ है कि हम बाकी को भेजते हैं: 0.002 बीटीसी और 0.00832423 बीटीसी, जो कुल में 0.01032423 बीटीसी देते हैं, जो 0.01 बीटीसी से अधिक है और हमें सूट करता है। (सही है, कमीशन लगभग $ 3 निकला, लेकिन मान लीजिए कि नेटवर्क व्यस्त है और हम भेजना जल्द से जल्द करना चाहते हैं।)

आयोग

लेन-देन की फीस लेने के लिए, मैंने प्रत्येक इनपुट सिक्के को संशोधित किया, जो कि एक इनपुट के रूप में लेन-देन में शामिल करने के लिए भुगतान करना होगा, इसकी शेष राशि को कम करना। यह इनपुट और कमीशन के आकार (उदाहरण के लिए, प्रति बाइट 2 संतोषी) को जानकर किया जा सकता है। इसके अलावा, मैंने भेजी जाने वाली राशि को संशोधित किया, इसमें लेनदेन के उस हिस्से की कीमत को जोड़ा गया जो चयनित सिक्कों पर निर्भर नहीं करता है: शीर्षक और निकास (एस)। उपयोगकर्ता झंडे का उपयोग करके इन सभी मापदंडों को निर्दिष्ट कर सकता है। आप सामान्य रूप से आयोगों के लिए समायोजन को अक्षम कर सकते हैं 0 बाइट्स का कमीशन प्रति बाइट।

मैंने पते के विभिन्न संस्करणों में इनपुट और आउटपुट के आकार के बारे में जानकारी ली (क्लासिक, लिपटे सेगविट और देशी सेगविट यहाँ से: https://bitcoin.stackexchange.com/a/84006

एल्गोरिदम और कार्यान्वयन

मैंने तुरंत आनुवंशिक एल्गोरिथ्म को गिरा दिया, शायद व्यर्थ। सटीक एल्गोरिदम पर ध्यान केंद्रित किया। मेरा पहला प्रयास सभी संयोजनों की संपूर्ण खोज के माध्यम से महसूस करना था, लेकिन 40 सिक्कों पर भी इसने घंटों तक काम किया और इसे छोड़ना पड़ा। फिर मैंने विकिपीडिया पर सुझाए गए गतिशील प्रोग्रामिंग की कोशिश की। इसमें, आप पूरे मैट्रिक्स को स्मृति में नहीं रख सकते हैं, लेकिन केवल वर्तमान और पिछली पंक्तियों में। इसके अलावा, हमें मूल्य को संग्रहीत करने की आवश्यकता नहीं है, क्योंकि यह वजन के साथ मेल खाता है और स्तंभ संख्या है। लेकिन हमें संयोजन को याद रखने की आवश्यकता है - मैंने इसे एक बिटसेट के रूप में संग्रहीत करने का निर्णय लिया। इसके अलावा, आप केवल एक पंक्ति को स्टोर कर सकते हैं, अगली पंक्ति को इसमें से बना सकते हैं। प्रत्येक nonzero row record अपनी जगह पर बना रहता है और इसे एक सेल में दाईं ओर (यदि यह पहले वहां खाली था) कोशिकाओं की एक निश्चित संख्या के साथ कॉपी किया जाता है। यदि आप रिवर्स ऑर्डर में जाते हैं, तो सेल के माध्यम से छंटनी होती है जिसमें "कूद" जाता है, तो आप सब कुछ सही ढंग से भर सकते हैं:

वर्तमान पंक्ति में प्रत्येक नॉनज़ेरो सेल अगली पंक्ति में ही उत्पन्न होती है और सही संख्या में कोशिकाओं की एक निश्चित संख्या (जोड़े गए सिक्के के मूल्य के बराबर) के लिए दूसरी सेल बनती है। यदि उस सेल में पहले से ही एक मूल्य है, तो सबसे बड़ी संख्या में चयनित (जो कि लेन-देन में शामिल नहीं है) "जीतता है" सिक्के, क्योंकि हम संभव के रूप में कुछ सिक्के भेजना चाहते हैं, अन्य चीजें समान हैं।

एक सेल पर मैं एक बिटसेट के लिए 8 बाइट्स खर्च करता हूं, और सेल की संख्या 0 से शेष राशि की संभावित संख्या के बराबर है जो भेजे गए सिक्कों की मात्रा को घटाती है। उदाहरण के लिए, यदि बटुए में केवल 1 बिटकॉइन है, और 0.1 भेजा जाता है, तो 100'000'000-10'000'000 = 90'000'000 सेल होंगे, प्रत्येक 8 बाइट्स, जो कि 720 मेगाबाइट है - एक आधुनिक कंप्यूटर के लिए थोड़ा सा। यदि सिक्कों की संख्या 32 से कम है, तो प्रति सिक्का 4 बाइट्स का उपयोग करना संभव होगा, लेकिन मैंने इसे अनुकूलित नहीं किया। इसके अलावा, यदि 64 से अधिक सिक्के हैं, तो कार्यक्रम काम नहीं करता है - यह भी मनमाना लंबाई का एक बिटसेट बनाकर तय किया जाएगा। अंत में, आप संतुलन में अंतिम संकेत को त्याग सकते हैं, थोड़ा सटीकता खो सकते हैं, लेकिन स्मृति में 10 बार जीत सकते हैं। लेकिन अभी तक यह ऐसा करेगा।

मैंने प्रोग्राम को चेंजलेस कहा और इसे गिटलैब पर रखा: gitlab.com/starius/changeless । यह गो में लिखा है, गो गेट का उपयोग करके असेंबल किया जाता है, हमेशा की तरह। CI में एकत्र लिनक्स, विंडोज, मैक के लिए बायनेरिज़ उपलब्ध हैं।

जब मैंने असली सिक्कों के साथ कार्यक्रम शुरू किया, तो मैं आश्चर्यचकित था कि उसने आवश्यक संयोजन को कितनी सही तरीके से उठाया। जब सिक्कों की संख्या बड़ी होती है, तो लगभग किसी भी राशि के सिक्के की शेष राशि के साथ ही सटीकता के साथ चयन किया जा सकता है! आप 1 satoshi के लिए आवश्यक राशि को बदलते हैं और कार्यक्रम इस राशि के लिए सिक्कों के बिल्कुल अलग संयोजन देता है। नीचे 0 से 1 बिटकॉइन के शेष के साथ 50 यादृच्छिक सिक्कों पर काम करने का एक उदाहरण है।

 $ 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।

सिक्के के संतुलन की सूची कैसे प्राप्त करें

इलेक्टोरल प्रोग्राम के लिए, मुझे यह तरीका मिला (कंसोल कमांड):

 ' '.join((x["value"]) for x in listunspent()) 

यदि आप कुछ सिक्कों को बाहर करना चाहते हैं, उदाहरण के लिए एक निश्चित पते पर, तो यह इस तरह किया जा सकता है:

 ' '.join((x["value"]) for x in listunspent() if x["address"] != "bad address") 

अन्य पर्स के लिए, मुझे ऐसा आसान तरीका नहीं मिला और मुझे इसे अपने हाथों से वापस लेना पड़ा।