"Inflation propensity of Collatz orbits: a new proof-of-work for blockchain applications" - Fabian Bocart
Kod: Zaznacz cały
https://www.mdpi.com/1911-8074/11/4/83Więc zakładam wątek tutaj. W skrócie, autor w 4.1. Collatz-Based Proof-of-Work proponuje, żeby zadać kopiącym bloki znalezienie jakichś \(\displaystyle{ Q_{i}}\) dla liczb z przedziału \(\displaystyle{ B}\) do \(\displaystyle{ B*}\), gdzie \(\displaystyle{ B}\) jest jakąś liczbą 256-bitową, a \(\displaystyle{ B*=B+2^{64}}\). Czym jest \(\displaystyle{ Q_{i}}\)? Autor pisze:
the cardinality of the set of steps that lead to a number strictly larger than all previous numbers in the same sequence
Bierzemy jakąś liczbę i zaczynamy ją iterować w ciągu Collatza, aż to momentu, gdy osiągnie \(\displaystyle{ 1}\). Liczymy wszystkie liczby, które były w tym ciągu większe niż nasza liczba początkowa. Tę liczbę tych liczb autor definiuje jako \(\displaystyle{ \xi (x)}\), gdzie \(\displaystyle{ x}\) to nasza liczba startowa. Przykładowo x=3:
3, 5, 8, 4, 2, 1,...
Mamy 5 i 8 większe od 3, zatem \(\displaystyle{ \xi (3)=2}\). I autor chce zadawać znalezienie zbiorów jakichś \(\displaystyle{ Q_{i}}\) równych \(\displaystyle{ \xi (x)}\), gdzie liczby startowe \(\displaystyle{ x_{i}}\) będą z przedziału \(\displaystyle{ B}\) do \(\displaystyle{ B*}\). To proponuje autor, jeśli dobrze rozumiem. Czy dobrze to rozumiem?
I teraz pytania. Czy ktoś rozumie jak autor chce dobierać te \(\displaystyle{ Q_{i}}\), które zada kopaczom do znalezienia? Zada im konkretnie do znalezienia startowe \(\displaystyle{ x_{i}}\), które mają określone \(\displaystyle{ Q_{i}}\). Widzę tu taki problem, że w przedziale \(\displaystyle{ B}\) do \(\displaystyle{ B*}\) może nie być takiej liczby \(\displaystyle{ x_{i}}\), która da powiedzmy \(\displaystyle{ Q_{i}=\xi (x_{i})=3333}\), bo takie \(\displaystyle{ Q_{i}}\) sobie wymyśliliśmy. I co wtedy? Może w ogóle nie istnieć liczba w ciagu Collatza, która ma akurat \(\displaystyle{ \xi (x_{i})=3333}\). No chyba, że to jest gwarantowane w jakiś sposób? Skąd autor ma pewność, że znajdą się liczby \(\displaystyle{ x_{i}}\), które dadzą jakieś \(\displaystyle{ \xi (x_{i})=Q_{i}}\), które on sobie akurat wymyślił i to akurat w tym przedziale \(\displaystyle{ x_{i} \in (B,B*)}\)?
Niejasne jest też jak te \(\displaystyle{ Q_{i}}\) dobierać. Mają być one coraz większe, jak rozumiem (i nie mogą być sobie równe), ale one się szybko skończą w takim przypadku. Istnieje wzór (empiryczny, ale bardzo dobrze potwierdzony) zgodnie z którym długość ciągu Collatza (zanim osiągnie jedynkę i się zapętli) dla liczby startowej \(\displaystyle{ n}\) można oszacować na:
\(\displaystyle{ d(n)=\frac {2}{\ln(\frac {4}{3})} \cdot \ln(n)}\)
Jeśli mówimy o liczbach około 256-bitowych praktycznie wszystkie takie liczby będą miały długości ciągów wynoszące \(\displaystyle{ 1}\) do \(\displaystyle{ 1234}\). Znajdą się odstępstwa, niektóre odnotują dłuższe ciągi, ale procentowo będzie ich niewiele (prawdopodobnie dla coraz większych \(\displaystyle{ n}\) takie przypadki liczb mają gęstość zerową). Czyli każda liczba początkowa 256-bitowa może mieć maksymalnie \(\displaystyle{ 1234}\) liczb większych od niej. A realnie mniej, bo ciąg Collatza początkowo zwykle rośnie przez pewną liczbę iteracji, a później przez kolejne iteracje spada aż do \(\displaystyle{ 1}\), więc nie ma szans, żeby wszystkie iterowane liczby były większe od startowej. Ogólnie mamy więc do dyspozycji bardzo mały zbiór \(\displaystyle{ Q_{i}}\), w realnych zastosowaniach w kilka godzin pewnie będzie po wszystkim. Czy ja czegoś tu nie rozumiem?
Dodano po 18 godzinach 3 minutach 47 sekundach:
Ok, już rozumiem o co chodzi autorowi. Niestety wygląda na to, że blockchaina przez niego zaproponowanego można łatwo złamać, znając pewne twierdzenia.
Po pierwsze źle zrozumiałem czym jest \(\displaystyle{ \xi (x)}\). Jest to po prostu liczba kroków (iteracji) do maksimum w ciągu. Poprzednio pisałem, że to liczba liczb w ciągu, które są większe od liczby startowej - to nieprawda.
Po drugie jest już jasne jak autor chce zadawać \(\displaystyle{ Q_{i} = \xi (x_{i})}\) do znalezienia. Otóż okazuje się, że, jak to autor pokazał w Figure 3, istnieje pewna liczba takich startowych \(\displaystyle{ x_{i}}\), które mają \(\displaystyle{ \xi (x_{i})}\) równe \(\displaystyle{ 1}\), autor chce zadać ich poszukiwanie. Istnieje jeszcze mniejsza liczba takich startowych \(\displaystyle{ x_{i}}\), które mają \(\displaystyle{ \xi (x_{i})}\) równe \(\displaystyle{ 2}\), \(\displaystyle{ 3}\) itd. Im większe \(\displaystyle{ Q_{i}}\) tym mniej jest \(\displaystyle{ x_{i}}\), które będą osiągać maksima po tak wielu krokach. Autor twierdzi, że rozkład tych liczb jest quasi-geometric, zgadza się to ze znanym heurystycznym argumentem, postulującym, że trajektorie w ciągach Collatza realizują geometryczny proces Browna (dzielenia i mnożenia w kolejnych krokach następują w sposób pseudolosowy). Autor zresztą potwierdził to obliczeniowo (rozkład liczb o zadanych, coraz większych \(\displaystyle{ Q_{i}}\)) dla liczb do miliona, co pokazał w Figure 3. Jednocześnie nie ma w tym żadnego porządku, skoro mamy tu proces Browna, nie da się wytypować która dokładnie liczba osiągnie maksimum po zadanych \(\displaystyle{ n}\) krokach, bo każdy ciąg przypomina iterowanie losowo kolejnych operacji mnożenia z dodawaniem lub dzielenia.
A jednak... Niestety pomimo, że autor wydaje się, że odrobił lekcje i zrobił dobry research, prawdopodobnie nie zdaje sobie z pewnego twierdzenia, zwanego Terras’s bijection:
"CONSECUTIVE INTEGERS AND THE COLLATZ CONJECTURE", Marcus Elia
Patrz Theorem 4.1, tam jest odnośnik to oryginalnej pracy Terrasa (nie chce mi się jej cytować, jest do znalezienia), w której wyjaśnione jest twierdzenie. Problem polega na tym, że, jeśli znajdziemy jakiś ciąg, który ma powiedzmy \(\displaystyle{ \xi (x_{i}) = q}\), to na mocy tego twierdzenia wszystkie liczby postaci \(\displaystyle{ x_{i} + 2^{q} \cdot m}\) będą miały identyczny przebieg przez te \(\displaystyle{ q}\) kroków, co nasza liczba \(\displaystyle{ x_{i}}\). Część z nich również osiągnie maksimum po tych \(\displaystyle{ q}\) krokach. Ogólnie bardzo łatwo jest wyznaczyć wszelkie możliwe kombinacje przekształceń w ciągu Collatza (mnożenie z dodawaniem lub dzielenie), które będą powodowały wzrost trajektorii ciągu przez dowolne zadane z góry \(\displaystyle{ n}\) kroków. Istnieje też algorytm, który pozwala wszystkie te liczby, które realizują takie kombinacje przekształceń wyznaczyć. A nawet, gdyby nie istniał, to już samo znalezienie chociażby jednej liczby \(\displaystyle{ x_{i}}\) spełniającej \(\displaystyle{ \xi (x_{i}) = q}\), pozwala wygenerować ich nieskończenie wiele za pomocą wzoru \(\displaystyle{ x_{i} + 2^{q} \cdot m}\). Oznacza to, że nie musimy przeszukiwać wszystkich liczb z zadanego przedziału, a możemy skupić się tylko na tych, które są postaci \(\displaystyle{ x_{i} + 2^{q} \cdot m}\). Im większe \(\displaystyle{ Q_{i}}\), tym mniej liczb musimy przeszukać (gdy już znajdziemy chociaż jedną o właściwości \(\displaystyle{ \xi (x_{i}) = q}\)). Oznacza to, że trudność nie rośnie tutaj wykładniczo i kopacz, który posłuży się tym wzorem, a znajdzie tylko jedną liczbę \(\displaystyle{ x_{i}}\) o zadanym \(\displaystyle{ Q_{i}}\) bardzo łatwo będzie mógł sprawdzić pozostałe liczby-kandydatów, bez potrzeby przeszukiwania całego ogromnego zbioru wszystkich liczb i szybko wykopie istotną część bloków. A, jeśli by użyć algorytmu znajdowania wszystkich możliwych (w praktyce prawie wszystkich), najmniejszych liczb w ciągu Collatza, które rosną przez zadaną liczbę kroków, można wykopać prawie wszystkie bloki - bo będziemy kopać w tempie wykładniczo szybszym, niż zwykli kopacze. Oni będą przeszukiwać cały zbiór powiedzmy \(\displaystyle{ 2^{64}}\) liczb, a my tylko co \(\displaystyle{ 2^{q}}\)-tą liczbę z tego zbioru, czyli zbiór o wielkości \(\displaystyle{ \frac {2^{64}}{2^{q}}}\).
