Ralph Merkle

Chcesz wysłać zaszyfrowaną wiadomość. Odbiorca potrzebuje tajnego klucza, by ją odczytać. Jak go przekazać, jeśli ktoś obserwuje całą rozmowę? W artykule z 1978 roku Ralph Merkle opisał zaskakującą metodę: nadawca przygotowuje wiele zaszyfrowanych zagadek, odbiorca losuje jedną, rozwiązuje ją i publicznie odsyła ukryty w środku identyfikator. Obaj znają wtedy wspólny klucz. Podsłuchujący też widzi identyfikator, ale nie wie, która zagadka go zawierała. W opisanym modelu jego nakład pracy rośnie kwadratowo wraz z rozmiarem zadania, a praca uczestników liniowo. To przewaga kwadratowa, nie wykładnicza. Historyczny przełom nie jest dzisiejszym zaleceniem dotyczącym szyfrowania wiadomości. [1]

W artykule z 1978 roku ważne są możliwości przeciwnika. Wolno mu podsłuchiwać, ale zmiany i fałszerstwa nadal mają być wykrywalne. Wyobraź sobie kogoś, kto czyta listy, oraz kogoś, kto dodatkowo je przepisuje i podpisuje twoim nazwiskiem. Drugi przypadek wymaga dodatkowej ochrony: upewnienia się, z kim naprawdę rozmawiasz. Różnica w kosztach obliczeń tego nie rozstrzyga. Zagadki nie gwarantują więc bezpieczeństwa dowolnej komunikacji przez aktywnego pośrednika. Pokazują, że przy podanych założeniach można uzgodnić sekret bez wcześniej współdzielonego tajnego klucza. [1]

Merkle Tree rozwiązuje inny problem. To drzewo uwierzytelniające opisano w rozprawie Merkle’a z 1979 roku. Wyobraź sobie archiwum umów: chcesz sprawdzić konkretną umowę bez pobierania całego archiwum. Dla każdego elementu oblicza się hash, krótki cyfrowy odcisk. Odciski łączy się parami i ponownie hashuje, aż pozostanie wspólny korzeń. Hashowanie nie szyfruje treści; pozwala sprawdzić zgodność. Potrzebny jest wcześniej uwierzytelniony korzeń, czyli odcisk potwierdzony jako należący do właściwego archiwum. Jeśli oszust może dostarczyć zarówno dokument, jak i dowolny własny korzeń, ich zgodność niczego nie dowodzi o oryginalnym archiwum. [2]

Weźmy zrównoważone drzewo binarne z 8 elementami. Do sprawdzenia wybranego liścia potrzebujesz 3 sąsiednich hashy: po jednym odcisku sąsiedniej gałęzi na każdym poziomie. Z własnego liścia i tych odcisków obliczasz korzeń, a następnie porównujesz go z korzeniem uwierzytelnionym. Sam liść i korzeń nie wchodzą w liczbę pomocniczych hashy. Trzeba też znać budowę drzewa oraz kolejność łączenia: czy sąsiad znajduje się po lewej, czy po prawej. Oszczędność nie wynika ze sztuczki z ukrytymi danymi. Odległe części archiwum reprezentują ich odciski, więc pełne dokumenty nie są potrzebne do tego konkretnego sprawdzenia. [2]

Merkle Tree potwierdza związek elementu z określonym zbiorem danych. Nie sprawia jednak, że błędna informacja staje się prawdziwa. W naszym archiwum może znajdować się umowa z niewłaściwym nazwiskiem. Dowód poprawnie potwierdzi jej obecność, nie wykrywając błędu w nazwisku. Podobnie odcisk nie potwierdza uprawnień autora dokumentu. Warto rozdzielić pytania: czy element pasuje do tego korzenia, skąd znam korzeń i według jakich reguł przyjmuję treść? To rozróżnienie pomaga zrozumieć, co ta technika robi w Bitcoinie, a co muszą zapewnić inne części systemu. [2]

Bitcoin używa Merkle Tree do powiązania transakcji z nagłówkiem bloku, jego zwięzłym zapisem. Korzeń znajduje się w nagłówku; zmiana zawartych transakcji wpływa na ich wspólny odcisk. Satoshi Nakamoto opisuje tę konstrukcję w części 7 whitepaperu i wymienia pracę Merkle’a w źródłach. To dowód wpływu technicznego, nie autorstwa Bitcoina. Drzewo nie wybiera poprawnej historii ani nie sprawdza podpisów transakcji za węzły. Bitcoin łączy je z innymi regułami, w tym weryfikacją transakcji i Proof of Work, dowodem wykonanej pracy obliczeniowej. Lepiej zrozumieć pojedynczy element niż przypisywać mu możliwości całego systemu. [3]

Część 8 whitepaperu opisuje SPV, uproszczoną weryfikację płatności. Lekki klient korzysta z nagłówków bloków i gałęzi drzewa łączącej transakcję z wybranym blokiem. Oszczędza dane, ale opiera się na założeniach dotyczących łańcucha o największej skumulowanej pracy i zachowania górników. Sam dowód włączenia nie sprawdza wszystkich reguł transakcji tak jak Full Node, węzeł w pełni weryfikujący dane. Nie pokazuje też, czy wyjście zostało później wydane: do tego trzeba znać dalsze zdarzenia. Początkujący nie powinien utożsamiać zdania „ta płatność jest w tym bloku” z pełnym sprawdzeniem środków dostępnych teraz. [3]

Rozprawa z 1979 roku wykorzystuje drzewo uwierzytelniające także do skończonego zbioru jednorazowych podpisów cyfrowych. Podpis cyfrowy pozwala sprawdzić, czy wiadomość zatwierdził posiadacz określonego tajnego klucza; nie jest obrazkiem odręcznego podpisu. Drzewo może połączyć wiele wartości weryfikacyjnych z jednym znanym korzeniem. W tej konstrukcji liczba podpisów jest jednak ograniczona i korzeń trzeba po pewnym czasie odnowić. Nie wolno więc dowolnie powtarzać użycia tego samego jednorazowego klucza. Ten bardziej zaawansowany fragment pracy Merkle’a pokazuje wspólną ideę: sprawdzić potrzebną część małym dowodem, dokładnie rozumiejąc warunki takiego sprawdzenia. [2]