Wybór monet

Donate BitcoinPOW.pl : 1LMofGNsTm4tMAzkPZH4qzK2qrLxu2pw2p

https://github.com/bitcoin/bitcoin/blob/57b34599b2deb179ff1bd97ffeab91ec9f904d85/doc/release-notes/release-notes-0.12.0.md

https://github.com/bitcoin/bitcoin/issues/10004

Metoda wyboru monety odnosi się do procesu przeprowadzanego podczas wybierania zestawu niewydanych wyników transakcji (UTXO) z portfela lub konta kryptowalutowego, które mają zostać wykorzystane jako dane wejściowe w każdej transakcji. Najczęściej stosowaną metodą selekcji monet stosowaną obecnie w kryptowalutach opartych na UTXO jest algorytm, który decyduje o pewnym zestawie UTXO, który pasuje do kwoty docelowej i ogranicza opłatę transakcyjną. Jednak w tym podejściu rezygnuje się z korzystnych kosztów utrzymania całej sieci na rzecz niskich opłat transakcyjnych, ponieważ powstaje wiele UTXO o niskiej wartości, znanych jako „kurz”. Z biegiem czasu będzie to miało wpływ na skalowalność i zarządzanie siecią kryptowalut, w miarę powiększania się globalnego zestawu UTXO. Dlatego istnieje pilna potrzeba znalezienia skuteczniejszej metody selekcji monet, odpowiedniej dla kryptowalut opartych na UTXO. W artykule zaproponowano metodę opartą na algorytmie zachłannym i genetycznym do efektywnego wybierania zestawów UTXO w Bitcoinie. Głównym celem tej strategii wyboru monet jest zbliżenie się jak najbliżej celu przy jednoczesnym utrzymaniu i ewentualnie zmniejszeniu liczby wejść UTXO.

Wstęp
W 2008 roku Satoshi Nakamoto opublikował artykuł „Bitcoin: A Peer-to-Peer Electronic Cash System”, w którym opisano zdecentralizowaną architekturę waluty elektronicznej opartą na technologii szyfrowania asymetrycznego, sieci P2P, znaczniku czasu, mechanizmie algorytmu skrótu, algorytmie rozproszonego konsensusu i mechanizm nagrody ekonomicznej [1]. Tymczasem ten artykuł oznaczał także oficjalne narodziny Bitcoina.

W Bitcoin blok to jednostka pamięci używana do publicznego przechowywania kilku transakcji na stałe. Generowanie bloku uznawane jest za eksplorację, czyli proces pakowania transakcji w bloki i znajdowania losowej liczby rozwiązującej problem kryptograficzny.

Może być wielu górników, którzy próbują wygenerować blok jednocześnie. Jednak prawdopodobieństwo wydobycia bloku jest proporcjonalne do mocy mieszającej górnika. Dlatego górnik z większą mocą mieszania ma większe szanse na znalezienie wartości jednorazowej. Kiedy górnik pakuje transakcję w blok, transakcja jest najpierw potwierdzana, a następnie łączona z łańcuchem blokowym. Kiedy ten blok otrzyma sześć kolejnych potwierdzeń bloku, transakcję uważa się za potwierdzoną. Generator transakcji może zaoferować opłatę transakcyjną, aby zwrócić uwagę górników, dzięki czemu jest większe prawdopodobieństwo spakowania i potwierdzenia transakcji.

Bitcoin to zdecentralizowana aplikacja korzystająca z modelu UTXO, w którym UTXO są wykorzystywane jako dane wejściowe transakcji i tworzone przez dane wyjściowe transakcji. Płatnik może tworzyć i transmitować transakcje za pośrednictwem sieci P2P bez konieczności korzystania z platform zewnętrznych. Tego rodzaju struktura może zastąpić zaufaną stronę trzecią. Wszystkie transakcje są przechowywane w bloku w sposób otwarty, przejrzysty i rozproszony. Adresy Bitcoin są odpowiednikiem kont w tradycyjnych systemach finansowych, jednak adresy nie są powiązane z rzeczywistą tożsamością społeczną, co chroni prywatność użytkowników.

Obecnie [2] całkowita liczba portfeli Bitcoin wynosi około 32 miliony. Ponieważ jeden użytkownik może mieć więcej niż jeden portfel, nie można zaobserwować liczby aktywnych użytkowników, jest to również liczba szybko rosnąca, ponieważ coraz więcej osób staje się nowymi użytkownikami Bitcoina. Wraz z rozwojem Bitcoina od czasu do czasu obserwowano wskaźniki napływu dużych transakcji. Blok Bitcoina nie jest w stanie pomieścić ich wszystkich ze względu na ograniczenie polegające na tym, że rozmiar bloku nie może przekraczać 1 MB [3]. Portfel w kryptowalutach opartych na UTXO zarządza kilkoma UTXO należącymi do konkretnych kont. Kiedy właściciel portfela chce zrealizować transakcję, portfel użyje własnej metody selekcji monet, aby wybrać określony zestaw UTXO do sfinansowania tej transakcji.

Metoda selekcji monet stosowana przez Bitcoin to metoda selekcji losowej, która jest mało wydajna, ponieważ nie zawsze może zapewnić osiągnięcie celu, a wraz ze wzrostem UTXO wzrasta również trudność w znalezieniu odpowiedniego dopasowania. Rdzeń Bitcoin definiuje „kurz” jako śladową ilość Bitcoina pozostającą w portfelu lub pod adresem, która nie jest w stanie przetworzyć transakcji, ponieważ jej wartość jest niższa od wymaganej opłaty transakcyjnej. Dust definiujemy jako UTXO, którego wartość jest niższa niż opłata transakcyjna za jego wydanie. Na przykład dane wejściowe Pay to Public Key Hash (P2PKH) mają rozmiar 148 bajtów, dane wyjściowe to 34 bajty, a dodatkowe informacje w danych transakcji to 10 bajtów. Transakcja z dwoma wyjściami powinna zapłacić co najmniej 192 satoshi przy domyślnej minimalnej opłacie transakcyjnej (1 satoshi na bajt). W tym przykładzie, jeśli sygnał wejściowy P2PKH jest niższy niż 192 satoshi, wówczas uznaje się to za „kurz”.

Wytwarzanie pyłu to jedna z wad modelu UTXO. Kiedy użytkownik będzie musiał wygenerować transakcję, rdzeń Bitcoin zastosuje własną strategię, aby wybrać zestaw UTXO na koncie użytkownika [4]. Wybiera UTXO, który przekracza cel i generuje dwie nowe monety, jedną płatną, a drugą jako „zmianę”. Zwykle składa wiele monet, aby osiągnąć docelową kwotę transakcji. Złożoność ta okazuje się mieć dalsze konsekwencje, gdy weźmie się pod uwagę inne czynniki, takie jak opłaty transakcyjne i wytwarzanie pyłu. Należy zauważyć, że opłaty transakcyjne są obliczane na podstawie wyboru monet w transakcji. Należy również pamiętać, że w przypadku szybkiego wydawania dużych monet nastąpi kumulacja monet o niskiej wartości, których transakcja może okazać się niemożliwa ze względu na niższą niż wymagana opłata transakcyjna.

Implikacje te wskazują na pilną potrzebę opracowania skutecznej strategii selekcji monet dla kryptowalut opartych na UTXO. Wysokowydajna metoda selekcji monet to taka, która uwzględnia wybór odpowiedniej liczby UTXO, aby zapobiec wysokim opłatom transakcyjnym, a także zmniejszyć powstawanie kurzu poprzez wcześniejsze wydawanie monet o niskiej wartości. W artykule zaproponowano nową strategię selekcji monet opartą na algorytmie zachłannym i genetycznym. Ma na celu pełne wykorzystanie monet o niskiej wartości w celu osiągnięcia kwoty transakcji, aby zapobiec tworzeniu się kurzu i utrzymać lub nawet zmniejszyć liczbę monet, aby uniknąć nadmiernych opłat transakcyjnych.

Podstawowa struktura danych w Bitcoinie i problem wyboru monety
Struktura transakcji Bitcoin
Model UTXO, który pokazano na rys. 1, jest modelem transakcyjnym wymyślonym przez Satoshi Nakamoto. Każda transakcja ma numer wersji, numer wejść transakcji, kilka wejść i wyjść transakcji oraz czas blokady. Numer wersji i czas blokady zajmują po cztery bajty. Czas blokady określa najwcześniejszy moment ważności transakcji. Transakcję z czasem blokady można włączyć do bloku, jeśli wysokość bloku lub bieżący czas osiągnie wymagany czas blokady transakcji. W przeciwnym razie górnik nie uwzględni tej transakcji w bieżącym bloku [5]. Celem tego czasu blokady jest uniemożliwienie górnikom korzystania z płatnych snajperów [6].

Liczba bajtów zajmowanych przez dane wejściowe i wyjściowe transakcji może się różnić i zależy od ich odpowiednich ilości. Strukturę wejścia transakcyjnego pokazano na rys. 2, a strukturę wyjścia transakcyjnego pokazano na ryc. 3.

Dane wyjściowe transakcji wygenerują nowe UTXO, a dane wejściowe transakcji zużyją UTXO, które są źródłem monet. Pojedyncze dane wyjściowe nie mogą być używane jako dane wejściowe dla wielu transakcji. Jeżeli tak, naruszenie tej zasady nazywa się podwójnym wydatkowaniem [7].

Każda transakcja Bitcoin ma hash transakcji, który jest obliczany dla całej zawartości transakcji przez Secure Hash Algorithm-256 (SHA-256). Hash transakcji nazywany jest także identyfikatorem transakcji, a jego rozmiar wynosi 32 bajty. UTXO jako dane wejściowe transakcji jest wskazywane przez wartość skrótu transakcji, do której się odwołuje, oraz indeks, który zajmuje 4 bajty UTXO na wyjściu transakcji. Pole sekwencji służy do wskazania względnego czasu blokady dla tego wejścia i zajmuje 4 bajty. Wyjście transakcji posiada pole wartości, które wskazuje wartość zawartą w wyjściu transakcji i zajmuje 8 bajtów. Skrypty odblokowujące i blokujące służą odpowiednio do udowodnienia, że wejściowe UTXO są własnością płatnika i że wyjściowe UTXO są zablokowane dla beneficjenta.

W tradycyjnym systemie finansowym nie ma związku między kontem a hasłem, dlatego konto i hasło są przechowywane w wewnętrznej bazie danych. W takich okolicznościach różni użytkownicy nie mogą mieć tego samego numeru konta. Ponieważ system Bitcoin jest zdecentralizowany, nie ma strony trzeciej, która mogłaby wykryć, czy konto jest zduplikowane, dlatego do identyfikacji i weryfikacji potrzebna jest specyficzna matematyczna zależność między kontem a hasłem. Klucz prywatny to liczba, a klucz publiczny jest generowany przez jednokierunkową funkcję szyfrowania zwaną mnożeniem klucza prywatnego przez krzywą eliptyczną. Dla każdego wyniku transakcji istnieje skrypt blokujący zawierający hash klucza publicznego beneficjenta, deklarujący, kto jest beneficjentem tej transakcji. Dla każdego wejścia transakcji istnieje skrypt odblokowujący. Skrypt odblokowujący zapewnia podpis transakcji wygenerowany przez klucz prywatny w celu potwierdzenia beneficjenta wskazanej transakcji. Załóżmy, że ktoś próbuje udawać beneficjenta i generuje skrypt odblokowujący przy użyciu swojego klucza prywatnego. W takim przypadku górnik podczas weryfikacji podpisu stwierdzi, że skrypt odblokowujący nie jest zgodny ze skryptem blokującym i będzie mógł odrzucić transakcję [8].

Istnieją dwa rodzaje transakcji Bitcoin. Jedna to transakcje na bazie monet, a druga to zwykłe transakcje transferowe. Transakcja coinbase jest pierwszą transakcją ze wszystkich powiązanych transakcji w bloku, utworzoną przez górnika, który wygenerował blok. Dane wejściowe transakcji w bazie monet nie zużywają UTXO, ale zawierają dane wejściowe zwane bazą monet. Dane wyjściowe transakcji w bazie monet są podzielone na dwie części: nagrodę w postaci monet wydaną przez system Bitcoin za wydobycie bloku oraz opłaty transakcyjne za wszystkie transakcje w bloku. Regularne transakcje wykorzystują UTXO jako dane wejściowe transakcji (transakcje wspomniane później odnoszą się do zwykłych transakcji transferu). Transakcja może mieć wiele wejść i wyjść transakcji. Suma danych wejściowych transakcji musi być większa lub równa kwocie potrzebnej do transakcji.

Struktura blokowa wejść Bitcoin
Strukturę bloku Bitcoina pokazano na rys. 4. Jak pokazano na rys. 4, blok składa się z magicznej liczby, rozmiaru bloku, nagłówka bloku i transakcji, a rozmiar pierwszych trzech pól jest stały. Rozmiar bloku ma górną granicę. Na przykład Bitcoin wymaga, aby rozmiar bloku był mniejszy lub równy 1 MB, a nagłówek bloku zajmował 80 bajtów. Ponieważ każda transakcja jest rejestrowana w bloku, wielkość transakcji wpływa na liczbę transakcji, które blok może pomieścić [9,10,11,12]. Liczba transakcji jest wprost proporcjonalna do wielkości bloku [13].

Po ponad dziesięciu latach rozwoju liczba transakcji znacznie przekroczyła kwotę, którą można zmieścić na przestrzeni 1 MB. Oznacza to, że część transakcji nie zostanie od razu ujęta w blokach. W systemie Bitcoin transakcje są traktowane priorytetowo według następującego równania:

Gdzie
to wartość i-tej transakcji wejściowej w tej transakcji,
jest wiekiem wejścia i transakcji w tej transakcji, oraz
jest wielkość tej transakcji.

Górnicy najpierw pakują transakcje o wysokim priorytecie w bloki, a następnie te z wysokimi opłatami transakcyjnymi. Transakcje bez opłat i o niskim priorytecie prawdopodobnie będą długo czekać na potwierdzenie [14]. Ponieważ nagroda za wydobycie Bitcoina jest zmniejszana o połowę co cztery lata, opłaty transakcyjne staną się w przyszłości głównym źródłem dochodu górników. [15]. Podnoszenie opłat transakcyjnych w celu przyciągnięcia uwagi górników nie jest zrównoważonym rozwiązaniem, z możliwymi przyszłymi konsekwencjami, takimi jak zbyt wysokie opłaty, które sprawiają, że większa liczba transakcji staje się bezsensowna ekonomicznie. Metoda zaproponowana w tym artykule opiera się na zwiększaniu liczby transakcji, jakie może pomieścić blok, poprzez zmniejszenie rozmiaru transakcji. Z kolei opłata transakcyjna będzie również niższa niż dotychczas przy zmniejszeniu wielkości transakcji.

Problem z kurzem i wyborem monet
Opłata transakcyjna jest ustalana zarówno na podstawie wielkości tej transakcji, jak i stawki opłaty za bajt ustalanej przez całą sieć. Im wyższa opłata transakcyjna ustawiona przez użytkownika dla konkretnej transakcji, tym szybciej transakcja ta zostanie spakowana w blok przez górnika. W artykule pył zdefiniowaliśmy jako UTXO o wartości niższej niż opłata konieczna do jego wydania. Opłatę transakcyjną oblicza się przy założeniu, że w danej transakcji bierze udział tylko jedna transakcja wejściowa i jedna wyjściowa, przy stałej stawce opłaty za bajt. Pył powstaje zwykle w wyniku transakcji o niskiej wartości i wynikających z nich zmian, których system nie może automatycznie usunąć. Spowoduje to wzrost globalnego zestawu UTXO i pozostawi część niewyczerpanych UTXO. Jeśli strategie wyboru monet zostaną odpowiednio zaprojektowane, system zostanie wypełniony takimi UTXO, co może stać się obciążeniem dla zwykłych użytkowników [4].

Aby zbudować transakcję w kryptowalutach przy użyciu modelu UTXO, użytkownik lub portfel musi wybrać z konta określony zestaw UTXO jako dane wejściowe transakcji. W procesie selekcji podstawowym zadaniem jest osiągnięcie kwoty wymaganej do tej transakcji. Dlatego problem doboru monet jest zwykle interpretowany jako problem sumy podzbiorów. W praktyce portfel zaprojektuje własną metodę wyboru monet, a opłata transakcyjna będzie głównym czynnikiem branym pod uwagę przy projektowaniu algorytmu wyboru monet. Jednak wymagana kwota i opłata transakcyjna nie są jedynymi czynnikami przyczyniającymi się do problemu z wyborem monety. Projektując odpowiedni algorytm doboru monet, należy uwzględnić wykorzystanie kurzu, zapewnienie prywatności użytkownika, uwzględnienie specyficznych wymagań użytkownika oraz opłaty transakcyjnej. Dobrze zaprojektowany algorytm selekcji monet może osiągnąć wiele celów optymalizacyjnych, jednocześnie zmniejszając koszty administracyjne systemu. Dlatego uważamy problem doboru monet za wielocelowy problem optymalizacyjny.

Strategia wyboru monet w Bitcoin
Tworząc transakcję w Bitcoinie, w pierwszej kolejności należy znaleźć UTXO należące do tego adresu, czyli znaleźć poprzednie potwierdzone wyniki transakcji, które wskazują na adres. Następnie wybór UTXO spośród dostępnych odbywa się według pewnej metody losowej, aż suma przydzielonych UTXO będzie większa lub równa docelowej kwocie do zapłaty. Metodę stosowaną przez Bitcoin do wyboru UTXO jako danych wejściowych transakcji opisano w następujący sposób, kwota docelowa to kwota do zapłaty (bez opłat transakcyjnych) [16]:

Jeśli istnieje UTXO, którego kwota jest dokładnie równa kwocie docelowej, wybierz UTXO jako dane wejściowe transakcji.

Znajdź UTXO, których kwota jest mniejsza niż kwota docelowa, zsumuj kwotę UTXO jako nTotalLower. Następnie znajdź UTXO, którego kwota jest większa, ale najbliższa kwocie docelowej. Jego ilość nazywa się nLwestLarger.

Jeśli nTotalLower jest mniejsze niż kwota docelowa i istnieje nLowestLarger, jako dane wejściowe transakcji wybierz UTXO, którego kwota wynosi nLowestLarger; jeśli nTotalLower jest mniejsze niż kwota docelowa i nLowestLarger nie istnieje, oznacza to, że saldo jest niewystarczające do spłaty.

Jeśli nTotalLower jest większe niż kwota docelowa, użyj losowego przybliżenia (do 2000 razy), aby znaleźć UTXO jako dane wejściowe transakcji. Suma wybranych kwot UTXO jest najbliższa kwocie docelowej.

Ogólnie rzecz biorąc, metoda selekcji stosowana przez Bitcoin priorytetowo wybiera UTXO, których suma kwot jest najbliższa wartości docelowej w rekurencji losowego wyboru. Strategia ta nie zapewnia dokładności dopasowania wartości docelowej i nie jest skuteczna w minimalizowaniu opłaty transakcyjnej. Co więcej, zastosowany algorytm nie uwzględnia wyniku zmiany transakcji i dlatego pomija powstawanie pyłu. W [4] zbadali ilościowo metodę selekcji monet Bitcoina pod kątem produkcji pyłu i zaobserwowali trend rosnącej liczby nierentownych UTXO.

Powiązana praca
Wśród obfitości badań nad kryptowalutami istnieje niewiele artykułów poświęconych konkretnie metodom selekcji monet. Dlatego nasz przegląd powiązanych prac przygląda się strategiom selekcji, które nadają priorytet dokładności wartości docelowej [17, 18], ulepszają algorytm plecakowy [19] i chronią prywatność użytkowników [20]. W naszej pracy proponujemy metodę selekcji monet, która ma na celu spełnienie dokładnych wymagań docelowych przy jednoczesnym zachowaniu małej i stabilnej liczby wejść UTXO oraz uniknięciu wytwarzania pyłu. W artykule dokonano interpretacji metody poprzez wyjaśnienie stosowanych algorytmów oraz zilustrowano skuteczność poprzez wizualizowane zbiory danych z symulacji. Algorytm selekcji monet stosowany w rdzeniu Bitcoina składa się z około 2000 rund losowych rekurencji w celu znalezienia zestawu UTXO najbliższego docelowemu celowi płatności [17]. Tę strategię selekcji omówiono szczegółowo w części IV.

Praca Erhardta analizuje próbkę różnych portfeli i wdrożone w nich polityki w odniesieniu do wpływu na opłaty transakcyjne i pulę UTXO [18]. Wprowadzono także algorytm Branch’n’Bound pozwalający znaleźć dokładne dopasowanie wartości docelowej transakcji. Opierając się na wynikach eksperymentów ilościowych, Erhardt przedstawia sugestie algorytmowi Bitcoin Core dotyczące metody selekcji monet, która została później przyjęta przez programistów jako metoda dodatkowa. Proponowana metoda wykorzystuje algorytm Branch’n’Bound w celu poszukiwania dokładnego dopasowania wartości docelowej i opiera się na losowaniu losowym, jeśli nie uda się znaleźć dokładnego dopasowania. D.J.Diroff proponuje ulepszenie algorytmu plecakowego, aby osiągnąć cel, jakim jest minimalizacja kosztów, poprzez zapewnienie, że wynik zmiany jednej transakcji będzie dokładnie odpowiadał wartości docelowej późniejszej transakcji [19]. To podejście do klasycznego problemu plecakowego uwzględnia minimalizację wyników zmian, które mogą mieć zbyt małą wartość, co czyni je nieskutecznymi w przypadku innej transakcji. Przyjmując inne podejście, [4, 20] przygląda się obecnemu stanowi sieci kryptowalut, oceniając istniejące obawy i skuteczność strategii ich zwalczania. W artykule Abramowej i Bohme omówiono strategie wyboru monet i problem międzyokresowy, oceniając je z perspektywy prywatności.

W artykule [4] szczegółowo omówiono pył w kryptowalutach opartych na UTXO, a mianowicie Bitcoin, Bitcoin Cash i Litecoin. Ich praca pokazuje, jak ważne jest zaprojektowanie odpowiednich metod selekcji monet, ponieważ obecny stan takich sieci kryptowalut stoi w obliczu bezpośredniego zagrożenia pyłem. Ilustrując trudność globalnego utrzymania sieci wynikającą z jej złożoności, artykuł badawczy podkreśla potencjalne skutki istniejących niedociągnięć obecnych metod selekcji monet. Nasza praca odpowiada na ujawnione obawy, proponując metodę selekcji monet, która zniechęca do tworzenia kurzu, jednocześnie poprawiając ogólną wydajność w kontekście kryptowalut opartych na UTXO.

Strategia selekcji monet oparta na algorytmie zachłannym i algorytmie genetycznym
Komplikacja wyboru monety jest problemem optymalizacyjnym mającym trzy główne cele. Spełnienie podstawowego warunku osiągnięcia wartości docelowej przy zapewnieniu możliwie najmniejszej różnicy, utrzymaniu stosunkowo małej ilości kurzu w portfelu oraz ograniczeniu ilości monet wykorzystywanych w transakcji. W naszym kontekście moneta jest reprezentowana przez wejście UTXO. Zakładając, że użytkownik Bitcoina U ma n dostępnych UTXO, cel oznacza wartość transakcji, która ma zostać dokonana. W procesie selekcji monet wielkość przestrzeni poszukiwań nie powinna być większa niż
aby zapobiec znacznemu zwiększeniu przestrzeni poszukiwań. Nasza praca skupia się na zwiększeniu dokładności dopasowania docelowej wartości każdej transakcji, utrzymaniu niewielkiej ilości kurzu w portfelu i zniechęceniu do wytwarzania kurzu.

Istnieje wiele technik optymalizacji wielocelowej, niektóre z najnowszych obejmują optymalizację roju cząstek [21] i głębokie uczenie się przez wzmacnianie [22]. Jednakże w porównaniu z klasycznymi algorytmami zachłannymi i genetycznymi, te najnowsze techniki optymalizacji mają odpowiednio wady, które sprawiają, że są mniej dopasowane w porównaniu z algorytmem zachłannym i genetycznym. W przypadku algorytmu roju cząstek łatwo wpada on w lokalne minimum przy pracy w przestrzeni o wyższych wymiarach i charakteryzuje się niskim współczynnikiem zbieżności. Z drugiej strony głębokie uczenie się przez wzmacnianie wymaga dużych obliczeń, dużej ilości czasu i braku danych do uczenia sieci. W tej sekcji przedstawimy proponowaną przez nas strategię selekcji monet w oparciu o algorytm zachłanny i genetyczny, a także zbadamy cechy tego nowego podejścia. Następnie szczegółowo zostaną opisane poszczególne kroki stosowania tych dwóch algorytmów do wyboru monety w transakcji, wraz z wyjaśnieniem zastosowania i znaczenia na każdym etapie.

Algorytm, o którym mowa
Aby zapobiec tworzeniu się kurzu i wykorzystać monety o niskiej wartości, zanim staną się niemożliwe do wydania, monety wybrane do transakcji powinny znajdować się jak najbliżej celu, włączając monety o niższej wartości, zachowując jednocześnie liczbę UTXO na poziomie, który będzie nie powodować niepotrzebnych opłat transakcyjnych. Algorytm zachłanny może uzyskać minimalną liczbę wejść transakcyjnych. Jednakże algorytm ten będzie rozróżniał wartości UTXO o niskiej wartości, a suma ilości kombinacji UTXO nie zawsze będzie rozwiązaniem najbliższym wartości docelowej. Zatem algorytm genetyczny znajduje kombinację UTXO z najmniejszą liczbą UTXO i kwotą najbliższą wartości docelowej.

(1) Algorytm zachłanny: Algorytm zachłanny to szybki i prosty algorytm rankingowy służący do rozwiązywania problemów optymalizacyjnych. Generuje rozwiązanie w drodze iteracji, a podczas każdej iteracji wybierane będzie rozwiązanie lokalnie optymalne w bieżącej sytuacji [23]. Po ustaleniu docelowej kwoty do zapłaty, za pomocą algorytmu zachłannego zostanie najpierw wybrany UTXO z największą kwotą z aktualnej puli UTXO płatnika. Następnie zostanie wybrany UTXO z drugą co do wielkości ilością i tak dalej, aż suma wybranych UTXO będzie większa lub równa wartości docelowej. Wybrane UTXO to rozwiązanie uzyskane przez algorytm zachłanny. Chociaż może to nie być rozwiązanie optymalne, może określić minimalną liczbę UTXO jako rozwiązanie.

(2) Algorytm genetyczny: Algorytm genetyczny (GA) został po raz pierwszy wprowadzony przez Hollanda w 1975 roku [24]. GA to rodzaj algorytmu ewolucyjnego, który służy do rozwiązywania poszukiwań optymalizacyjnych. Naśladuje proces ewolucji populacji, taki jak dobór naturalny, krzyżowanie i mutacje. W miarę kolejnych iteracji ewolucji populacji zostanie znalezione optymalne rozwiązanie. Główną ideą jest zakodowanie możliwych rozwiązań problemu w postaci ciągów binarnych o stałej długości [25]. Każdy ciąg binarny reprezentuje osobnika w populacji, który nazywany jest chromosomem, a każda liczba całkowita w chromosomie nazywana jest genem. W zależności od problemu konieczna jest funkcja celu i funkcja przystosowania. Dostosowanie służy do oceny chromosomów w celu określenia prawdopodobieństwa wybrania do następnego pokolenia. Trzy podstawowe operacje genetyczne w GA to selekcja proporcjonalna, krzyżowanie jednopunktowe i mutacja niezbędna.

Selekcja proporcjonalna: Wybierz kilka wybitnych osobników z obecnej populacji i skopiuj je następnemu pokoleniu. Prawdopodobieństwo, że dana osoba zostanie wybrana, jest proporcjonalne do jej sprawności.

Krzyżowanie jednopunktowe: podziel osoby na pary. Wybierz kolejne pary osobników z aktualnej populacji jako rodziców, określ pozycję skrzyżowania, a następnie skrzyżuj kody na odpowiednich pozycjach rodziców, aby wygenerować nowe osobniki.

Mutacja podstawowa: w przypadku genu, który wymaga zmutowania, jeśli pierwotna wartość genu wynosi 0, operacja mutacji zmienia ją na 1; w przeciwnym razie, jeśli pierwotna wartość genu wynosi 1, operacja mutacji zmienia ją na 0.

Podczas korzystania z algorytmu genetycznego należy wcześniej określić niektóre parametry, zwane zmiennymi decyzyjnymi, w tym wielkość populacji M, prawdopodobieństwo krzyżowania
, prawdopodobieństwo mutacji
i czas zakończenia T.

Konkretne kroki w celu wybrania UTXO za pomocą algorytmu zachłannego i algorytmu genetycznego
W tej podsekcji opisano metodę wybierania UTXO jako danych wejściowych transakcji podczas generowania transakcji. Po pierwsze, algorytm zachłanny służy do określenia najmniejszej liczby UTXO jako danych wejściowych transakcji. Liczba z algorytmu zachłannego służy do określenia funkcji celu i funkcji przystosowania algorytmu genetycznego. Po drugie, algorytm genetyczny służy do poszukiwania optymalnego rozwiązania. Ponieważ waluta zawsze ma najmniejszą jednostkę, można uznać, że jednostką kwoty każdego UTXO jest najmniejsza jednostka waluty. Jeśli chodzi o Bitcoin, najmniejszą jednostką jest satoshi, gdzie 1 BTC
satoshi. Podczas korzystania z algorytmów do przedstawienia UTXO potrzebna jest tylko ilość UTXO, a ilość ta jest liczbami nieujemnymi. Aby uprościć wyjaśnienie, w dalszej części artykułu zastosowano symbole matematyczne do wskazania ilości UTXO lub związanych z nią wyników.

Dane wyjściowe algorytmu to kombinacja UTXO z najmniejszą liczbą i sumą najbliższą wartości docelowej, ta wartość docelowa reprezentuje kwotę do zapłaty, a opłaty transakcyjne nie są uwzględnione. Schemat działania algorytmu przedstawiono na rys. 5. Etapy rozwiązywania problemu są następujące:

S1: Ustaw wynik na zero. Rozważmy użytkownika U z dostępnymi N UTXO, który chce komuś zapłacić cel. Pozwalać
oznaczają wartość i-tego UTXO. Niech UTXOS oznacza listę
posortowane rosnąco, a rozmiar oznacza liczbę elementów UTXOS;

S2: Przejdź przez UTXOS i oblicz bieżące saldo tego użytkownika U jako całkowite;

S3: Jeśli
, oznacza to, że saldo jest niewystarczające, przejdź do kroku S8, w przeciwnym razie przejdź do kroku S4;

S4: Jeśli
, to znaczy UTXOS to dane wejściowe transakcji
, przejdź do kroku S8, w przeciwnym razie przejdź do kroku S5;

S5: Jeśli
i istnieje UTXO w UTXOS, który jest większy niż cel, następnie użyj UTXO, który jest większy niż cel, ale najbliżej celu, jako wynik selekcji, przejdź do kroku S8, w przeciwnym razie przejdź do kroku S6;

S6: Używając algorytmu zachłannego, dodawaj liczby w UTXOS w kolejności od dużej do małej, aż suma wybranych UTXO będzie większa lub równa wartości docelowej, przestań dodawać, zapisz liczbę wybranych UTXO jako num i kombinację pozycji UTXO w UTXOS jako jeden osobnik z populacji początkowej i wartość początkowa best, best oznacza rozwiązanie optymalne w bieżącej populacji, a następnie losowo wygeneruj inne
osobniki tworzące populację początkową;

S7: Używając GA, zaczynając od populacji początkowej, populacja jest dziedziczona, krzyżowana i mutowana z pokolenia na pokolenie, a najlepszy osobnik w poprzednim pokoleniu jest rejestrowany jako najlepszy, aż pokolenie populacji będzie równe pokoleniu końcowemu T lub najlepsze to zatem najlepszy wynik
. Schemat blokowy GA opisano na ryc. 6, a poszczególne kroki S7 pokazano w następujący sposób:

S70: Każda osoba w tym algorytmie reprezentuje możliwe rozwiązanie tego problemu i jest kodowana jako ciąg binarny o rozmiarze Długość jako gen. Jeśli u tej osoby wybrane zostanie UTXO w UTXOS, odpowiednia pozycja zostanie zakodowana jako 1. Jeśli nie, zostanie zakodowana jako 0. Proces kodowania można zilustrować jak pokazano na rys. 7.

S71: Ponieważ początkową wartość najlepszego uzyskano z S6, należy wybrać najlepszą osobę z populacji początkowej i losowo wygenerować inne
osobniki w celu utworzenia pokolenia początkowego i ustawić czas populacji na 0;

S72: Określ, czy czas zapełniania t jest krótszy niż czas zakończenia T. Jeśli jest krótszy niż T, przejdź do kroku S73. W przeciwnym razie,
, przejdź do S8.

S73: Określ funkcję celu i funkcję przystosowania pokazane w funkcji 2 i oblicz przystosowanie każdego osobnika w bieżącej populacji zgodnie z funkcją 2. Funkcja przystosowania:

gdzie jestem indywidualnością,
jest k-tą cyfrą binarną ciągu genowego I, oraz
jest wartością k-tego UTXO w UTXOS. Jeżeli k-ty UTXO jest zdefiniowany jako pył, to
w funkcji przystosowania przyjmuje się wartość 0.

S74: Najlepiej zaktualizuj. Jeśli
, a następnie zamień najlepsze na I.

S75: Jeśli
uważa się, że znaleziono najbardziej odpowiednią kombinację UTXO,
, przejdź do kroku S8, w przeciwnym razie przejdź do kroku S76;

S76: Skorzystaj z reguły gry w ruletkę, aby wybrać osoby, które odziedziczą następne pokolenie. Proces ten to selekcja proporcjonalna. Całkowitą sprawność aktualnej populacji oblicza się w następujący sposób:

(3)
Gdzie
to jednostki obecnego pokolenia. I indywidualne przystosowanie do
współczynnik oblicza się w następujący sposób:

(4)
Gdzie
, mam na myśli
osobnik w obecnej populacji. Jeśli korzystasz z reguły gry w ruletkę, konieczne jest zapisanie sumy współczynnika, czyli:

(5)
gdzie i ma takie samo znaczenie jak funkcja 4 i
. Cały proces gry w ruletkę polega na dokonaniu M selekcji w celu wybrania M osób dla następnego pokolenia. Konkretny proces selekcji jest przedstawiony w następujący sposób:

*:
Wygeneruj losową liczbę Rand pomiędzy [0, 1) ;

*:
;

*:
Oblicz
, Jeśli
, przejdź do kroku 5, w przeciwnym razie przejdź do kroku 4;

*:
, Jeśli
, przejdź do kroku 5, w przeciwnym razie przejdź do kroku 3;

*:
Wybierz osobnika odpowiadającego k populacji następnego pokolenia;

S77: Przejście jednopunktowe. W nowych osobnikach M uzyskanych w kroku S76 co dwa osobniki są wykorzystywane jako rodzice, następnie losowo określają pozycję krzyżowania i krzyżują geny w odpowiednich pozycjach rodziców. Najpierw generujemy losową liczbę r pomiędzy [0, 1) . A następnie, jeśli
, losowo znajdujemy pozycję pomiędzy [0, len] i krzyżujemy te dwa geny, aby wygenerować dwa nowe osobniki. Proces krzyżowania pokazano na ryc. 8:

S78: Podstawowa mutacja. Każdy osobnik uzyskany w kroku S77 generuje losową liczbę r z zakresu [0, 1) . Jeśli
uważa się, że u danego osobnika występuje mutacja. Losowo wybierz pozycję mutacji, a następnie odwróć cyfrę binarną w pozycji mutacji. Następnie zaktualizuj
przez
. Proces mutacji przedstawiono w sposób pokazany na ryc. 9:

S79:
, przejdź do S72;

S8: Wynik wyjściowy jako dane wejściowe transakcji.

Wprowadzono pewne ulepszenia, dzięki którym GA działa lepiej.

(1)
Zakoduj UTXO w odpowiadającej mu pozycji w genie jako 0 lub 1. Ma to dwa powody.

Długość kodowania wzrośnie, jeśli UTXO zostanie zakodowany w binarnej reprezentacji jego ilości i ma UTXO o dużej wartości. Poza tym, jeśli dystrybucja UTXOS jest rzadka, tym łatwiej jest wygenerować niedostępne jednostki.

Ponieważ każdego UTXO można użyć tylko raz podczas generowania jednostki, każdy zawiera różne części, a dziesiętna reprezentacja każdej części musi być mniejsza lub równa size. Nowe osoby należy sprawdzić, czy nie występują duplikaty części i czy każda część odnosi się do dostępnego stanowiska. Jeśli nastąpi duplikacja, nowy osobnik jest niedostępny, należy zregenerować nowego lub pozostać jego rodzicami. Jednak za każdym razem, gdy generowany jest nowy osobnik, należy sprawdzić jego dostępność, co obniży efektywność algorytmu. Dlatego też, gdy rozmiar jest mały, do UTXO można dodać 0, aby uzyskać potęgę 2. W ten sposób po uzyskaniu nowego osobnika konieczne jest jedynie sprawdzenie, czy w osobniku znajdują się duplikaty.

(2)
Wynik uzyskany za pomocą algorytmu zachłannego wykorzystuje się jako osobnik w populacji początkowej i początkową wartość najlepszego. Ponieważ algorytm genetyczny w kolejnych iteracjach wyszukuje osobniki o wysokim przystosowaniu, a wynik uzyskany przez algorytm zachłanny może być wynikiem najlepszym.

Algorytm zachłanny będzie wybierał UTXO z rosnącej listy, aż suma UTXO będzie większa niż wartość docelowa. W tym przypadku liczba UTXO wybranych przez zachłanny algorytm będzie zawsze minimalna. W najgorszym przypadku zachłanny algorytm wybiera wszystkie UTXO z listy. Jeśli chodzi o algorytm genetyczny, krok S74 przejdzie przez wszystkie osoby i porówna go z najlepszymi. Jeśli
, najlepsi zostaną zastąpieni przez tę osobę. Z kolei w S75 algorytm genetyczny sprawdzi, czy aktualnie najlepsze rozwiązanie jest odpowiednim rozwiązaniem. Jeśli
, zostanie znalezione ostateczne rozwiązanie, a następnie wygenerowane zostanie najlepsze. Nawet jeśli algorytm genetyczny nie znajdzie żadnego osobnika lepszego od wyniku podanego przez algorytm zachłanny, ostatecznym wynikiem będzie wynik z minimalną liczbą UTXO podaną przez algorytm zachłanny.

Metoda selekcji Bitcoin UTXO obejmuje do 2000 prób (każda próba nazywana jest „rundą”), aby znaleźć niemal optymalną kombinację wejściowych UTXO. Chociaż złożoność czasowa metody Bitcoin wynosi O(n), nie może to zagwarantować, że metoda znajdzie rozwiązanie wystarczająco bliskie rozwiązania optymalnego. W miarę jak n będzie większe, znalezienie rozwiązania metodą Bitcoin stanie się trudniejsze. Nawet jeśli rozwiązanie zostanie znalezione, odległość od celu jest niepewna.

Zaproponowana przez nas metoda łączy w sobie prosty algorytm zachłanny i algorytm genetyczny. Algorytm genetyczny jest rodzajem algorytmu heurystycznego, który jest często używany do rozwiązywania problemów o znacznie dużej przestrzeni poszukiwań. Złożoność czasowa algorytmu genetycznego jest zwykle trudna do obliczenia, ale nadal możemy przeprowadzić analizę złożoności czasowej zaproponowanej przez nas metody. Po pierwsze, złożoność czasowa algorytmu zachłannego jest sumą procesu sortowania i procesu wyszukiwania. Do sortowania używamy algorytmu szybkiego sortowania ze złożonością czasową O(nlogn). Proces wyszukiwania w naszej metodzie polega po prostu na dodaniu wartości UTXO i porównaniu jej z wartością docelową. Złożoność czasowa procesu wyszukiwania powinna wynosić O(1) , a całkowita złożoność czasowa algorytmu zachłannego wynosi O(nlogn). Niech g oznacza wielkość pokolenia. W każdej generacji algorytmu genetycznego realizowane będą trzy procesy: (1) selekcja indywidualna, (2) krzyżowanie, (3) mutacja. Możemy omówić je osobno.

Selekcja indywidualna: proces ten składa się z dwóch etapów: (1) obliczenie sprawności każdej osoby, (2) wybranie osób. Ponieważ liczba osobników w każdym pokoleniu jest taka sama, niech m oznacza liczbę osobników w jednym pokoleniu. Złożoność czasowa pierwszego kroku powinna wynosić O(mn), a drugiego etapu O(m). Zatem całkowita złożoność czasowa tego procesu wynosi O(mn) ;

Krzyżowanie: W najgorszym przypadku proces krzyżowania musi przebiegać przez gen wszystkich osobników. Złożoność czasowa procesu krzyżowania wynosi O(mn).

Mutacja: W tym procesie używamy prostego jednopunktowego skrzyżowania. W najgorszym przypadku będziemy musieli przeprowadzić proces mutacji u wszystkich osobników. Zatem złożoność czasowa tego procesu wynosi O(m).

Podsumowując, złożoność czasowa naszej metody wynosi

Analiza i dyskusja wyników
Podczas pierwszego eksperymentu przeprowadziliśmy 8 serii symulacji, z których każda trwała 100 lub 1000 strzałów. Dla pierwszych 6 zestawów symulacji wygenerowaliśmy losowo n dodatnich liczb całkowitych z pewnego zakresu pokazanego w pierwszej kolumnie Tabeli 1 i 2 jako dostępne UTXO dla każdej symulacji. Dla ostatnich trzech zestawów uzyskaliśmy UTXO trzech prawdziwych kont Bitcoin jako dostępne UTXO. W każdej rundzie losowy wybór UTXO jest sumowany i ustalany jako kwota docelowa. Aby zbadać skuteczność naszej metody w porównaniu z innymi strategiami, każdy eksperyment obejmował symulacje Branch’n’Bound (BnB), bieżącego algorytmu, którego używa Bitcoin (BTC) oraz proponowaną przez nas metodę w celu porównania pionowego (
,GA).

W sumie wykonaliśmy 1800 rund doświadczalnych. Zestawy UTXO użyte w każdym zestawie symulacji pokazano w kolumnie 1 zarówno w Tabeli 1, jak i 2, a rundy eksperymentalne m w każdym zestawie pokazano w kolumnie 2. Dla każdej rundy losowo wybraliśmy zestaw UTXO i ustaliliśmy cel jako suma ich wartości. W idealnym przypadku odległość pomiędzy UTXO wybranymi przez algorytm a celem wynosi 0.

Do drugiego eksperymentu wykorzystaliśmy próbkę zestawu UTXO pobraną 1 października 2019 roku dostępną na GitHubie [19], przeprowadziliśmy 1000 rund symulacji. Stworzyliśmy trzy identyczne portfele, z 2000 UTXO i 10% pyłu, gdzie stawka opłaty za bajt wynosi 22. W każdej rundzie zestaw UTXO jest sumowany w celu przypisania wartości docelowej, której potrzebuje nasz proponowany algorytm i metoda Bitcoina aby pobrać pasujące UTXO. Następnie, jeśli to konieczne, wynik zmiany jest dodawany z powrotem do portfeli, a następnie do wszystkich portfeli dodawane są odpowiednio trzy identyczne zestawy 200 UTXO zawierające 10% pyłu. Jest to powtarzane przez 1000 rund, przy czym po każdej rundzie rejestrowana jest liczba kurzu pozostałego w każdym portfelu.

W kolumnach 3, 4 i 5 pokazaliśmy średnią odległość między celem a wynikiem metody Bitcoin, metody Branch’n’Bound i metody, którą zaproponowaliśmy. Kolumny 6, 7 i 8 pokazują odchylenie od celu każdej metody, przedstawia stabilność znalezienia rozwiązania najbliższego celowi. Tabela 2 porównuje średnią i wariancję ilości UTXO wybranej metodą dla trzech metod. Na rysunkach 10 i 11 przedstawiono porównanie wyników uzyskanych dla rachunku rzeczywistego 1 i rachunku rzeczywistego 3.
to wynik selekcji uzyskany metodą selekcji monet stosowaną w Bitcoinie
wynik uzyskany metodą Branch’n’Bound, oraz
jest wynikiem selekcji uzyskanym naszym podejściem. Tabela 3 pokazuje minimalną, maksymalną i średnią ilość kurzu w trzech portfelach na każde 100 nabojów. Rycina 12 ilustruje wahania ilości kurzu w każdym portfelu na przestrzeni 300 rund.

Zgodnie z wynikami tabel 1, 2, ryc. 10 i 11, zaproponowana przez nas metoda oferuje rozwiązanie, którego wynik jest bliższy wartości docelowej i wykorzystuje mniej UTXO. W prawie każdej symulacji odległość do celu UTXO wybranych naszą metodą jest znacznie mniejsza niż w przypadku innych metod, przy zachowaniu podobnej średniej liczby wybranych UTXO. W pierwszych 6 zestawach symulacji algorytmy zachłanne i genetyczne okazały się wysoce skuteczne pod względem dokładności dopasowywania celu, ponieważ średnia odległość była przez cały czas niska. Dodatkowo znakomity wynik metody wariancji odległości świadczy o jej stabilności. Trend ten przekłada się na symulacje z wykorzystaniem rachunków rzeczywistych. Dwa porównania odległości od wykresów docelowych na ryc. 10 i 11 wizualizują działanie wszystkich trzech metod i przedstawiają wybitną wydajność proponowanej przez nas metody w porównaniu pionowym.

Z tabeli 2 można zaobserwować, że proponowana przez nas metoda nie zawodzi w zakresie kontroli ilości UTXO. W związku z tym, choć osiągamy cel dokładniej, nasza metoda nie będzie tworzyć transakcji wymagających nadmiernych opłat transakcyjnych, jest to stabilna zasada. Wydajność tę można wyraźnie dostrzec na wykresach przedstawiających porównanie wielkości UTXO wybranych wszystkimi trzema metodami na ryc. 10 i 11.

Dla każdych 100 rund porównaliśmy minimalną, maksymalną i średnią ilość kurzu w każdym portfelu, aby wykazać skuteczność odpowiednich metod selekcji monet. Chociaż metoda Bitcoina ma najniższą minimalną ilość pyłu, to jednak średnia ilość pyłu w portfelu metody Bitcoina wynosi około 100. Wynik Branch’n’Bound pokazuje największy zakres pomiędzy minimum a maksimum, ma też najwyższą średnią ilość pyłowy. Zaproponowana przez nas metoda stabilnie utrzymuje ilość kurzu w portfelu na stosunkowo niskim poziomie. Dlatego zademonstrowanie naszej metody selekcji monet powoduje wykorzystanie większej ilości kurzu przy wyborze zestawu UTXO używanych w każdej transakcji bez uszczerbku dla niskich opłat transakcyjnych. Rysunek 12 ilustruje wynik pierwszych 300 rund. Z wykresu widać, że wyniki metod BTC i BnB podlegają dużym wahaniom, natomiast metoda GA utrzymuje stały trend w przypadku małej ilości pyłu.

Po uruchomieniu algorytmu zachłannego każdy wybrany UTXO ma dużą liczbę, ponieważ wykluczono małe UTXO, co ogranicza użyteczność UTXO o niskiej wartości. Jednakże algorytm genetyczny wykorzystuje UTXO o niższej wartości, zwracając stłumione małe UTXO z algorytmu zachłannego. Poza tym, ponieważ początkową wartością best jest ustawiony wynik uzyskany przez algorytm zachłanny, wynik końcowy musi być wynikiem algorytmu zachłannego lub lepszym wynikiem niż algorytm zachłanny. Chociaż zaproponowana przez nas metoda jest lepsza od metody Bitcoin zarówno pod względem odległości, jak i liczby UTXO, algorytm ten wymaga więcej czasu na rozwiązanie problemu, jak omówiliśmy w sekcji 4.

Integracja algorytmu zachłannego i algorytmu genetycznego pozwala sformułować rozwiązanie, które skutecznie selekcjonuje monety na podstawie ich indywidualnych wartości w taki sposób, aby przy jak najmniejszej liczbie monet zbliżyć się jak najbliżej celu. Zgodnie z tym założeniem metoda zapobiega również tworzeniu się pyłu, ponieważ priorytetowo wykorzystuje kombinację monet o określonej docelowej wartości, eliminując w ten sposób nadmierną „resztę”.

Conclusion

The method described in this paper uses Bitcoin as the main subject and environment of experimentation. However, the proposed method is applicable to all blockchain applications that employs the UTXO transaction model and includes an amount field in the transaction. Although, transactions generated using this method cannot guarantee the lowest possible transaction fees, it does not produce excessively high transaction fees. The algorithm described in this paper is mature and has established accountability and hence why it is essential to illustrate the feasibility of this method. In genetic algorithm, due to the setting of the initial population and the initial value of best, the algorithm can guarantee the quality of the solution even when the termination time T is relatively small, and the improvement of the encoding method speeds up the process of solution searching.

As greedy algorithm and genetic algorithm are used, the time taken to search for the solution will be extended. If this time prove to be inconveniently long, then improvement on the selection, crossover, and mutation process is in need. Since�� and �� can affect the algorithm and its convergence, they can be changed automatically adaptively, that is, adaptive genetic algorithm [26]. In Bitcoin, the user’s UTXO is stored in the UTXO pool. Selecting fewer UTXO as transaction input means that a larger number of UTXO will accumulate in the UTXO pool, which is not conducive to UTXO management or adds complexity to subsequent UTXO searches [27]. While this was not a complication in a controlled experimental environment, it could pose to be a hindrance in realising the benefits of this strategy in a real-world situation. Further research on improving the speed and time of this coin selection method will be relevant for the near future.

https://link.springer.com/article/10.1007/s40747-022-00799-2