Czy drzewo Merkle Bitcoina jest drzewem wyszukiwania binarnego?

Ten post pierwotnie pojawił się na stronie internetowej ZeMinga M. Gao i opublikowaliśmy go ponownie za zgodą autora. Przeczytaj cały artykuł tutaj.

Czy drzewo Merkle Bitcoina jest drzewem wyszukiwania binarnego?

Dr Craig Wright twierdzi, że drzewo Merkle Bitcoina jest drzewem wyszukiwania binarnego. Twórcy BTC nie zgadzają się i kwestionują jego kwalifikacje. Zadawanie pytań przez BTC i odpowiedzi doktora Wrighta pokazują typowy przykład doktora Wrighta mówiącego o tym na poziomie i dogłębnie, o jakim inni nie pomyśleli.

Jak na ironię, niektórzy kwestionują nawet zrozumienie technologii przez doktora Wrighta na poziomie licencjackim, nie pomimo tego, ale z tego powodu.

(I tego samego rodzaju przesłuchania trwające przez ostatnie osiem lat zdominowały temat Wrighta Satoshiego. Szczerze mówiąc, jest to haniebne i niesprawiedliwe. Często zmusza mnie to również do wyjaśniania innym.)

Każdy, kto mógł odnieść wrażenie, że dr Wright nie zna nawet podstawowych rzeczy, powinien ponownie przeanalizować swoje podstawowe nastawienie.

Nikt nie powinien ślepo ufać temu, co mówi druga osoba, ale znacznie częstszym błędem, jaki ludzie popełniają w stosunku do doktora Wrighta, jest domniemane odrzucenie go. Czas wyciągnąć wnioski z tego, co się wielokrotnie wydarzyło. Sądząc po powtarzających się doświadczeniach z przeszłości, podstawowe poczucie ostrożności wymagałoby bardziej przemyślanego i głębszego przemyślenia tego, co mówi dr Wright, aby uniknąć zawstydzenia.

Jeśli naprawdę chcesz zbadać prawdę o Bitcoinie, oprzyj się pokusie nadmiernego skupiania się na izolowanych szczegółach technicznych. To jest system. Mówiąc dokładniej, system istniejący w środowisku obliczeniowym, ekonomicznym i prawnym.

Twoje zrozumienie tych kwestii w dużej mierze zależy od tego, czy chcesz systemu techno-politycznego, który opiera się przede wszystkim na oporze przed cenzurą, czy systemu gospodarczego, który służy przede wszystkim produktywności. Każdy pogląd może mieć swoje własne, pełne szacunku uzasadnienie, ale należy zrozumieć różnicę, zanim dojdzie się do wniosku, że inni nic nie wiedzą.

Obydwa poglądy rozumiem bardzo dobrze. Tak się składa, że wolę skalowalny i produktywny system gospodarczy od techno-politycznego systemu oporu wobec prawa. W prawdziwym świecie może być miejsce na istnienie obu systemów. Moje preferencje mają związek z wartościami, w które wierzę i rozumiem, że inni mają swoje własne wartości i przekonania.

Proszę więc o wysłuchanie mnie w tej konkretnej kwestii dotyczącej drzewa wyszukiwania binarnego Bitcoina. Omawiam go nie tylko ze względu na wyjątkowe znaczenie techniczne, ale także dlatego, że jest to dobry przykład pokazujący, dlaczego należy zwracać uwagę na to, co mówi dr Wright.

Drzewo Merkle i drzewo binarne

Dr Wright powiedział, że struktura drzewa Merkle została pierwotnie zaprojektowana przez Satoshiego, a obecnie została zaimplementowana w BSV wraz z SPV (uproszczona weryfikacja płatności), która jest drzewem wyszukiwania binarnego.

Jego przeciwnicy sugerują, że jest to absurdalnie błędne, ponieważ każdy, kto ma podstawową wiedzę z zakresu informatyki, wiedziałby, że drzewo Merkle’a nie jest drzewem wyszukiwania binarnego.

Jego przeciwnik ma rację w tym sensie, że drzewo Merkle’a w swoim podstawowym zastosowaniu, którego uczy się w szkole, nie jest drzewem poszukiwań binarnych.

Ale nie wiedzą, że Satoshi zaprojektował drzewo Bitcoin Merkle w taki sposób, że chociaż jest to drzewo Merkle, jest także drzewem wyszukiwania, nawet drzewem wyszukiwania binarnego.

Doktor Wright po raz kolejny ma niewiarygodną rację.

Poniżej wyjaśnię szczegóły techniczne.

Po pierwsze, kluczowa koncepcja „drzewa binarnego” odnosi się do funkcji, która na każdym kroku przecina drzewo (razem zbiór danych) na dwie połowy (stąd „drzewo binarne”). Określa kierunek następnego kroku na podstawie dopasowania lub niedopasowania i odrzuca połowę w przeciwnym kierunku. Czynność powtarza się do momentu zlokalizowania elementu docelowego. Ten sposób binarny sprawia, że proces jest bardzo szybki i skalowalny. Ponieważ każdy krok jest binarny, postępuje wykładniczo, co daje logarytmiczną skalowalność.

Fakt, że połowę danych można natychmiast zignorować bez ryzyka utraty celu, tworzy ten niezwykły efekt. Wymaga to jednak, aby węzły i liście drzewa były uporządkowane i zrównoważone w określony sposób.

Dlatego nazwanie drzewa „binarnym” oznacza, że drzewo jest skonstruowane w taki sposób, że czynność (np. wyszukiwanie) może zostać wykonana w sposób binarny. Jeżeli struktura nie posiada tej cechy binarnej, nazwanie jej binarną byłoby niepoprawne. Jeśli jednak struktura faktycznie posiada tę cechę binarną, ale nikt inny takiej struktury nie zna i nigdy jej nie nazwał binarną, ten, kto pierwszy ją nazwie, będzie nie tylko poprawny, ale i innowacyjny.

Drzewo binarne można skonstruować tak, aby spełniało różne funkcje i osiągało różne cele. Jeśli struktura drzewa umożliwia wyszukiwanie binarne, jest to drzewo wyszukiwania binarnego. Jednak drzewa binarne można wykorzystać do innych celów, na przykład do zapewnienia integralności danych.

Pytanie brzmi więc: dlaczego dr Wright nazywa drzewo Merkle Bitcoina drzewem wyszukiwania binarnego?

Po pierwsze, jeśli drzewo Merkle Bitcoina jest skonstruowane w taki sposób, aby znaleźć lokalizację określonego fragmentu danych i potwierdzić jego istnienie, jest to drzewo wyszukiwania. To oczywiste, niezależnie od tego, co mówią inni.

Ale czy jest to drzewo „binarne”, a co za tym idzie, drzewo wyszukiwania binarnego? To bardziej szczegółowe rozważania.

Odpowiedź brzmi tak. Drzewo Merkle Bitcoina jest drzewem wyszukiwania binarnego, ponieważ dane Bitcoin są celowo ustrukturyzowane jako baza danych klucz-wartość, co oznacza, że każdy element (transakcja lub skrót) jest powiązany (oznaczony) kluczem. Klawisze są sekwencyjne. Istnieją różne sposoby tworzenia struktury kluczy. Zależy to od projektu struktury drzewa i algorytmu (przykład poniżej). Uwaga: tutaj słowo „klucz” jest standardową technologią bazy danych, podobnie jak etykieta przedmiotu i nie ma nic wspólnego z kluczami kryptograficznymi.

Ponieważ transakcje Bitcoin są znakowane czasem zgodnie z kolejnością otrzymania każdej transakcji, ta kolejność jest naturalna. Teraz, dzięki wbudowanym kluczom sekwencyjnym, z których każdy odpowiada sekwencyjnej transakcji ze znacznikiem czasu, masz uporządkowane i zrównoważone drzewo liści.

Rysunek 1 pokazuje przykład takiego drzewa Merkle’a, które jest jednocześnie drzewem wyszukiwania binarnego.

Transakcje są oznaczone Di. Transakcja Di odpowiada skrótowi (i, i), który jest szczególnym przypadkiem klucza (i, j), gdzie i=j.

Każdy węzeł jest oznaczony kluczem składającym się z pary liczb (i, j), np. (1, 4). Znaczenie liczb jest dość proste: węzeł z kluczem (i, j) oznacza, że dane w węźle i węzłach podrzędnych pod nim obejmują transakcje z zakresu od i do j. Na przykład (1, 4) oznacza, że węzeł i węzły podrzędne pod nim obejmują transakcje 1, 2, 3 i 4. W domyśle oznacza to również, że nie są one powiązane z transakcjami 5, 6, 7 i 8, co są objęte inną gałęzią zgodnie z (5,8).

Zgodnie z tą numeracją sekwencyjną (i, k) i (k+1, j) są dwoma sąsiadującymi ze sobą węzłami, jak wskazują k i k+1. Kiedy dwa sąsiednie skróty, H (i, k) i H(k+1, j), są łączone i mieszane, generuje nowy skrót H (i, j). Wynikowe klucze (i, j) są logiczne, ponieważ połączenie dwóch sąsiadujących skrótów powoduje połączenie dwóch zakresów, mianowicie i do k i k+1 do j, w celu utworzenia nowego zakresu i do j, stąd powstały skrót jest oznaczony jako H (i , J). Należy zwrócić uwagę, że w nowym kluczu (i, j) nie pojawiają się środkowe liczby k i k+1. Dzieje się tak, ponieważ zakres i do j oznacza rozszerzony zakres, który koniecznie obejmuje środkowe liczby k i k+1.

Rysunek 1 ilustruje prosty przypadek, w którym i=1, 2,…8. W rzeczywistości i=1, 2,…n, gdzie n jest całkowitą liczbą transakcji w bloku i może być dużą liczbą.

Drzewo Merkle powstaje w następujący sposób:

Zaszyfruj każdą transakcję Di, aby uzyskać H(i, i). Jest to pierwszy poziom drzewa Merkle, w którym elementy danych transakcji i ich skróty są ze sobą powiązane 1 do 1.
Zaszyfruj konkatenację każdej pary sąsiednich H(i, i) i H(i+1, i+1), aby otrzymać H(i, i+1). To dostaje drugi poziom. Drugi poziom będzie miał n/2 węzłów.
Powtarzaj ten sam proces w kroku 2 powyżej, aż osiągniemy końcowy poziom, na którym pozostanie tylko jeden węzeł. To jest korzeń Merkle’a.
Ponieważ liczba węzłów na każdym kolejnym poziomie jest zmniejszona o połowę, proces ten szybko dociera do korzenia (na górę). Całkowita liczba poziomów m=log2(n). Im więcej transakcji posiada blok, tym większą ma przewagę.

Na przykład, gdy n = 8, m = 3. Gdy n= 1 milion, m=20; gdy n=1 miliard, m=30; gdy n=1 bilion, m=40 i tak dalej. Widać, że od n=8 do n=1 miliarda całkowita liczba transakcji w bloku wzrosła ponad 100 milionów razy, a łączna liczba poziomów w drzewie wzrosła tylko 10 razy.

Powyżej przedstawiono podstawowe cechy drzewa Merkle. Ale będzie jasne, że etykietowanie węzłów za pomocą kluczy sekwencyjnych przekształca drzewo Merkle w drzewo wyszukiwania binarnego.

W przykładzie pokazanym na rysunku 1 załóżmy, że musimy wyszukać transakcję D5. co odpowiada klawiszowi (5, 5). Zaczynamy od góry (pierwiastka) H(1, 8), co oznacza, że w bloku znajduje się w sumie 8 transakcji od 1 do 8).

Najpierw porównujemy nasz cel (5, 5) z obecnym węzłem (1,8). Ponieważ 5 > 8/2, wiemy, że nasz cel znajduje się po prawej stronie. Idziemy w prawą stronę, aby dotrzeć do węzła H(5, 8) i pomijamy całą lewą gałąź, która stanowi połowę drzewa. Jeśli nie jest to oczywiste w tym małym przykładzie, wyobraź sobie, że jeśli blok zawiera 1 miliard transakcji, ten jeden krok pomija 500 milionów transakcji.

Następnie porównujemy nasz cel (5, 5) z obecnym węzłem (5, 8). Ponieważ 5=5, wiemy, że mamy już poprawną część klucza, czyli dolną granicę zakresu transakcji. Ale ponieważ 5<8, idziemy w lewo i docieramy do H(5,5), co odpowiada transakcji D5, czyli dokładnie tej transakcji, której szukamy.

Zatem powyższa struktura drzewa Merkle’a umożliwia wyszukiwanie binarne i dlatego jest drzewem wyszukiwania binarnego. Nie może być na ten temat dyskusji, ponieważ tak właśnie definiuje się drzewo wyszukiwania binarnego.

Takie drzewo wyszukiwania binarnego w połączeniu ze skomplikowanym projektem SPV sprawia, że Bitcoin zaimplementowany w BSV jest niezwykle potężny.

Drzewo wyszukiwania binarnego i SPV

Sama SPV to już inna sprawa. Chociaż zostało to ujawnione w białej księdze Bitcoin, SPV zostało właściwie rozumiane i dalej rozwijane jedynie w oparciu o Bitcoin SV (BSV). Pominę wyjaśnienie samego SPV, ale chciałbym podkreślić, że jest ono istotne dla drzewa wyszukiwania binarnego Bitcoin.

SPV stawia na skalowalność. Jeśli spojrzeć tylko na indywidualny przypadek działania SPV w przypadku podania przez użytkownika ścieżki Merkle jego transakcji, wydaje się, że nie ma to nic wspólnego z wyszukiwaniem, ponieważ użytkownik chętnie tworzy ścieżkę Merkle, która konkretnie lokalizuje nie tylko identyfikator transakcji, ale także jej lokalizację, nie pozostawiając nic więcej do przeszukiwania w blockchainie. Pozostaje tylko to, że odbiorca musi obliczyć dowód Merkle, aby zweryfikować istnienie transakcji przy użyciu ścieżki Merkle.

Pamiętaj jednak, że SPV stawia na skalowalność. Oznacza to, że będzie działać na blockchainie, który ma miliardy, a nawet biliony transakcji w jednym bloku. W tak skalowanym łańcuchu bloków skalowalne i wydajne wyszukiwanie staje się absolutnie niezbędne, w przeciwnym razie wszyscy, łącznie z nadawcą, odbiorcą i usługodawcami, poniosą straty.

Potrzebujemy więc skalowalnego wyszukiwania wraz z SPV. Ale co innego może zrobić to lepiej niż drzewo wyszukiwania binarnego?

W ten sposób drzewo wyszukiwania binarnego i SPV współpracują ze sobą jak ręka w rękę. To właśnie zrobiło BSV. Nadchodzące testy Teranode zaprezentują te funkcje. Jeśli nie zależy Ci na skalowalnym systemie, możesz nie być podekscytowany tą wiadomością. Nie oznacza to jednak, że powinieneś nadymać się i twierdzić, że dr Wright jest ignorantem, ponieważ twierdzi, że drzewo Bitcoin Merkle jest drzewem wyszukiwania binarnego. Wręcz przeciwnie, powinieneś odkryć swoją ignorancję w niezrozumieniu tego, co powiedział.

Obejrzyj: Bitcoin – elektroniczny system gotówkowy

Autor : BitcoinSV.pl

Źródło : Is Bitcoin’s Merkle tree a binary search tree? – CoinGeek

Author: BitcoinSV.pl
CEO