Matematyka tworząca blockchain i bitcoin – poradnik

Wstęp

W poprzednim poście rozpocząłem implementację własnego blockchain. http://blog.patys.pl/2017/09/29/wlasny-blockchain-implementacja-poradnik/ Teraz przejdziemy do kopania. Postanowiłem rozbić to na 3 posty.

Wstęp do matematyki blockchain

Kryptografia w matematyce

Implementacja kopania

Te 3 posty pokryją Proof of Work, czyli udowodnienie prawidłowości transakcji na podstawie czasu i zużytej mocy obliczeniowej. Również ten wstęp do kryptografii pozwoli nam na implementację kolejnych rozwiązań. Nie tylko związanych z blockchain, lecz też na przykład z szyfrowaniem czy kluczami prywatnymi i publicznymi.

Ciało skończone

Zaczniemy od wyjaśnienia sobie czym jest ciało skończone. Na Wikipedii jest okropna, książkowa definicja, z której nie da się nic zrozumieć, a przypisy zajmują połowę treści. https://pl.wikipedia.org/wiki/Cia%C5%82o_sko%C5%84czone

Tak więc, ciało skończone jest określone pewną liczbą elementów. Coś w stylu tablicy w programowaniu. Mamy na przykład ciało skończone F19 = {0,1, …, 18}, czyli zamyka się ono w elementach od 0 do 18. Aby nie przekraczać tego zakresu używane jest modulo (mod), czyli reszta z dzielenia. Każda liczba na której wykonamy modulo zamknie się w wartości przez jaką dzielimy.

Czyli:

17 % 19 = 17 // reszta wynosi 17

11 % 19 = 11 // reszta wynosi 11

22 % 19 = 3 // reszta wynosi 3, zaczęliśmy od 0 i szliśmy do 19, tam nastąpił powrót do początku gdzie jeszcze wykonały się 3 kroki, % przerwał liczenie gdy osiągnęliśmy wartość po lewej i kazał od początku liczyć

Wrzucam zdjęcie z większą liczbą przykładów, które przygotowałem na jednym z wykładów.

Funkcje

Mamy wstęp za sobą. Teraz czas przejść do funkcji.

W kryptowalutach używa się krzywych eliptycznych. Nie jest to ciężka funkcja w zapisie. Zobaczcie:

Funkcja liniowa: y = ax + b

Funkcja kwadratowa: y = ax2 + bx + c

Funkcja sześcienna: y = ax3 + bx2 + cx + d

Funkcja eliptyczna: y2 = x3 + ax + b

Tak więc funkcja eliptyczna niewiele się różni pod względem zapisu w porównaniu do funkcji sześciennej. Jednak jej wygląd i właściwości idealnie nadają się do szyfrowania.

Bitcoin

Każdy kto zobaczy jaką funkcją opisany jest bitcoin może nie uwierzyć, że jest ona w stanie zapewnić bezpieczeństwo.

y2 = x3 + 7

A tak wygląda wykres tej funkcji:

Jednak za tą prostotą kryje się wspaniałe rozwiązanie. Dzięki własnościom takiej funkcji idealnie nadaje się do szyfrowania. Skupimy się na dwóch operacjach: dodaniu punktów i podwojeniu punktu.

Dodanie punktów

Zaczniemy od dodania dwóch punktów.

Oznaczymy sobie dwa punkty: P i Q. Linia która przetnie te 2 punkty wyznaczy nam R. To R należy jedynie odbić względem osi X i mamy sumę tych punktów. Najprościej wytłumaczyć to patrząc na rysunek:

Tak więc widzimy, że P jest liczbą ujemną. Q to liczba dodatnia, jednak ma małą wartość. Łatwo więc zauważyć, że wynik będzie ujemny. Tak więc linia łącząca te dwa punkty przetnie wykres w jeszcze jednym miejscu. Będzie to punkt R. Jeśli go odbijemy na drugą stronę, otrzymamy R’ = P + Q

Podwojenie punktu

Służy do wyznaczenia stycznej do punktu, który ma być podwojony. Czyli P + P = R (na rysunku zapomniałem dorysować styczną). Przechodzi ona przez punkt P i punkt R, czyli jedynie przez dwa punkty. W przypadku dodania punktów mieliśmy przecięcie w trzech miejscach.

Dodanie punktu i podwojenie punktu jest wykorzystywane w mnożeniu skalarnym: R=bP.

Tutaj posłużyło nam do uproszczenia zapisu i rozbicia go na cztery operacje. Dwie dodania punktu i dwie podwojenia punktu.

Podsumowanie

Jest to ciężki temat. Ja sam się nie czuję w nim zbyt swobodnie. To jest wstęp do drugiej części, którą postaram się niedługo wrzucić. Pokażę tam jak na podstawie wiedzy z tego posta, obliczyć klucz publiczny i prywatny. A w ostatniej części wyjaśnię jak działa kopanie i zrobimy implementację.

Zapraszam Was do komentowania i zadawania pytań. Postaram się odpowiedzieć jak najlepiej i wyjaśnić wszelkie niejasności.

Tutaj źródła na podstawie których zagłębiałem się w temat:

http://kryptopolonia.info/matematyka-kryjaca-sie-za-bitcoin/

https://eng.paxos.com/blockchain-101-foundational-math

Zapraszam również do subskrypcji email. Przygotuję materiały, które będę tam publikował. Pojawi się tam też cała seria przepisana do postaci książki w formie pdf.