Nowy pomysł proof of work oparty o ciągi Collatza

[Dasio11]

Od początku więc: dla dowolnego ciągu binarnego \(\displaystyle{ s \in \{ 0, 1 \}^n}\) przez \(\displaystyle{ C(s)}\) oznaczam zbiór takich liczb naturalnych \(\displaystyle{ x}\), na których pierwsze \(\displaystyle{ n}\) iteracji funkcji Collatza zachowuje się w sposób zakodowany w \(\displaystyle{ s}\). Na przykład: \(\displaystyle{ 9 \in C(1011)}\), bo:

\(\displaystyle{ 9 \xrightarrow{1} 14 \xrightarrow{0} 7 \xrightarrow{1} 11 \xrightarrow{1} 17}\),

z kolei \(\displaystyle{ 8 \in C(000)}\), gdyż

\(\displaystyle{ 8 \xrightarrow{0} 4 \xrightarrow{0} 2 \xrightarrow{0} 1}\).

Twierdzę, że dla każdego ciągu \(\displaystyle{ s \in \{ 0, 1 \}^n}\) istnieje dokładnie jedna taka liczba naturalna \(\displaystyle{ 0 \le r < 2^n}\), że ów zbiór powyżej to dokładnie zbiór takich liczb naturalnych, które przy dzieleniu przez \(\displaystyle{ 2^n}\) dają resztę równą \(\displaystyle{ r}\), czyli

\(\displaystyle{ C(s) = \{ x \in \NN : x \equiv r \pmod{2^n} \}}\).

A skoro każdemu \(\displaystyle{ s}\) odpowiada dokładnie jedna taka liczba \(\displaystyle{ r}\), to mogę tę liczbę zależącą od \(\displaystyle{ s}\) jakoś oznaczyć, zatem oznaczam ją przez \(\displaystyle{ r(s)}\). Jednocześnie owo \(\displaystyle{ r(s)}\) jest najmniejszą liczbą w zbiorze \(\displaystyle{ C(s)}\) (chyba że akurat \(\displaystyle{ r(s) = 0}\), to wtedy tą najmniejszą liczbą jest \(\displaystyle{ 2^n}\) gdzie \(\displaystyle{ s \in \{ 0, 1 \}^n}\)). Przykładowo \(\displaystyle{ r(1011) = 9}\), bo

\(\displaystyle{ C(1011) = \{ x \in \NN : x \equiv 9 \pmod{16} \} = \{ 9, 25, 41, 57, 73, \ldots \}}\)

i \(\displaystyle{ 9}\) jest jedyną liczbą w przedziale \(\displaystyle{ \{ 0, 1, 2, \ldots, 15 \}}\) o tej własności. Z podobnych powodów \(\displaystyle{ r(000) = 0}\). W ten sposób znajdowanie liczby \(\displaystyle{ x \in C(s)}\) dla zadanego \(\displaystyle{ s \in \{ 0, 1 \}^n}\) sprowadza się do znalezienia \(\displaystyle{ r(s)}\). Czynię to następująco: w oczywisty sposób

\(\displaystyle{ C(\left< \right>) = \NN = \{ x \in \NN : x \equiv 0 \pmod{1} \}}\),

gdzie \(\displaystyle{ \left< \right>}\) jest ciągiem długości zero (znanym też jako słowo puste), toteż zgodnie z definicją \(\displaystyle{ r(\left< \right>) = 0}\).

Jeśli teraz znam liczbę \(\displaystyle{ r(s)}\) dla jakiegoś ciągu \(\displaystyle{ s \in \{ 0, 1 \}^n}\), to mogę wyznaczyć szukane liczby mające z przodu o jedną cyfrę więcej, tj. \(\displaystyle{ r(0^{\frown}s)}\) i \(\displaystyle{ r(1^{\frown}s)}\), gdzie \(\displaystyle{ ^{\frown}}\) oznacza złączenie ciągów. Sposób wyznaczania tychże liczb podałem w jednym z poprzednich postów, używając dla wygody krótszych oznaczeń: \(\displaystyle{ r = r(s), r' = r(0^{\frown}s), r'' = r(1^{\frown}s)}\). W ten sposób można rekurencyjnie wyznaczyć \(\displaystyle{ r(s)}\) dla dowolnego skończonego ciągu \(\displaystyle{ s}\).


Na Twoim przykładzie kolejno:

\(\displaystyle{ r( \left< \right> ) = 0 \\[1ex]
r(1) = r(1^{\frown}\left< \right>) = \frac{1}{3} (2 \cdot r( \left< \right> ) - 1) \bmod{2} = 1 \\[1ex]
r(01) = r(0^{\frown}1) = 2 \cdot r(1) \bmod{4} = 2 \\[1ex]
r(101) = r(1^{\frown}01) = \frac{1}{3} (2 \cdot r(01) - 1) \bmod{8} = 1 \\[1ex]
r(1101) = r(1^{\frown}101) = \frac{1}{3} (2 \cdot r(101) - 1) \bmod{16} = \frac{1}{3} \bmod{16} = 11 \quad(\text{bo } 3 \cdot 11 \equiv 1 \pmod{16}) \\[1ex]
r(01101) = r(0^{\frown}1101) = 2 \cdot r(1101) \bmod{32} = 22 \\[1ex]
r(101101) = r(1^{\frown}01101) = \frac{1}{3} (2 \cdot r(01101) - 1) \bmod{64} = \frac{43}{3} \bmod{64} = 57 \quad(\text{bo } 3 \cdot 57 \equiv 43 \bmod{64})}\)

i tak dalej - znajdujemy wartości \(\displaystyle{ r}\) dla coraz dłuższych sufiksów wyjściowego ciągu, aż w końcu znajdziemy ją dla sufiksu maksymalnego, którym jest całe słowo.

I, o ile nie trzasnąłem się w kodzie, odpowiedzią jest liczba \(\displaystyle{ 36307}\).

[matemix]

Ok, już wszystko jasne. Nie wpadłem nigdy na ten dokładnie algorytm, posługuję się nieco innym, ale są one z grubsza podobne (też trzeba korzystać z algorytmu Euklidesa po drodze). Znaleziona liczba się zgadza. Koncepcyjnie ten Twój algorytm jest o wiele prostszy (dzięki rekurencji), niż to co ja obliczałem.

Nie uznałbym mimo wszystko tego algorytmu za taki zupełnie oczywisty, choć post factum jest. Tym gorzej dla blockchaina, który zaproponował autor. Ciekawym pytaniem wydaje się to, czy można tę jego koncepcję proof of work mimo wszystko jakoś naprawić? Ale to już pytanie chyba na inną dyskusję. Nie widzę na pierwszy rzut oka takiej możliwości.

[Dasio11]

Nie uznałbym mimo wszystko tego algorytmu za taki zupełnie oczywisty

Zgadzam się, z tym że ja nic takiego nie napisałem.