Posortowane drzewo binarne, czyli dowód na to, że element nie należy do zbioru

Wygadany
Awatar użytkownika
Posty: 593
Rejestracja: 8 lutego 2020
Reputacja: 1114
Reputacja postu: 
20
Napiwki za post: 0 BTC
Lokalizacja: 7-bit secp256k1

Posortowane drzewo binarne, czyli dowód na to, że element nie należy do zbioru

Postautor: garlonicon » sobota, 14 maja 2022, 10:01

https://bitcoin.pl/manifest-satoshi-nakamoto pisze:Jedynym sposobem potwierdzenia nieobecności transakcji jest wgląd we wszystkie transakcje.
Czytając takie zdanie, wielu ludzi sądzi, że nie istnieje żaden inny sposób na potwierdzenie nieobecności danej transakcji. Stąd wielu wyciąga prosty wniosek, że należy podejść do tematu liniowo: zbieramy wszystkie transakcje, sprawdzamy każdą z nich po kolei, a następnie akceptujemy całość lub odrzucamy całość. Ludzie nie zdają sobie sprawy z tego, że za takim zdaniem kryje się głębszy sens, mianowicie: musimy zweryfikować wszystkie transakcje tylko wtedy, kiedy chcemy mieć TERAZ odpowiedź na pytanie o poprawność łańcucha. Czas jest tutaj kluczem, zaś kolejną wskazówkę stanowi drzewo merkle (ang. "merkle tree"). Przejdźmy zatem do szczegółów:

Drzewo merkle ułatwia wiele spraw. Można prościej dołączać i odrzucać transakcje, łatwiej przeszukiwać takie drzewo, portfele SPV również się na tym opierają. Aby uzyskać dowód na istnienie lub brak wybranego elementu, należy dodać do tego jeszcze jeden istotny element: sortowanie. Jeśli takie drzewo będzie posortowane zawsze i wszędzie, wtedy można logarytmicznie schodzić w głąb takiego drzewa, aż dotrzemy do poszukiwanych danych. Jeśli jednak tak się nie stanie, to nic straconego, możemy znaleźć dwa takie liście, których początek jest wspólny, co pozwoli na udowodnienie, że pomiędzy nimi nie istnieje szukany element.

Skąd nazwa "drzewo binarne" zamiast "drzewo merkle"? Otóż dalsze pójście tym tokiem rozumowania powoduje, że nie jest to typowe drzewo merkle. Różnice zaczynają być coraz łatwiejsze do zauważenia, co powoduje, że nazwa "drzewo binarne" zaczyna bardziej pasować do efektu końcowego. Sortowanie sprawia, że nie potrzebujemy już gałęzi w postaci typowych hashy. To już nie jest "merkle branch" jako sklejenie dwóch hashy i ponowne wywołanie funkcji skrótu na otrzymanym wyniku. Drzewo jest posortowane. Konsekwencje są takie, że lewa gałąź zaczyna się od zera, a prawa od jedynki. To wiele zmienia i wiele ułatwia.

Jak wygląda przykładowe drzewo? Wyobraźmy sobie, że chcemy mieć w nim liczby nieujemne zapisane dziesiętnie. Innymi słowy: mamy dowolny ciąg znaków od 0 do 9 o dowolnej dodatniej długości. Zakładamy, że zera wiodące są niedopuszczalne i traktujemy taki element jako nieprawidłowy. Wrzućmy sobie garść liczb pierwszych do takiego drzewa i zobaczmy, co się wówczas stanie:

primeTree
  [01234567]
    [0123]
      [01]
      [23]
        [2]
        [3]
          [3][01234567]
            SHA-256("29")=35135aaa6cc23891b40cb3f378c53a17a1127210ce60e125ccf03efcfdaec458
          [3][89abcdef]
            SHA-256("13")=3fdba35f04dc8c462986c992bcf875546257113072a909c162f7e470e581e278
    [4567]
      [45]
        [4]
          [4][01234567]
            SHA-256("17")=4523540f1504cd17100c4835e85b7eefd49911580f8efff0599a8f283be6b9e3
          [4][89abcdef]
            [4][89ab]
            [4][cdef]
              [4][cd]
              [4][ef]
                [4][e]
                  SHA-256("3")=4e07408562bedb8b60ce05c1decfe3ad16b72230967de01f640b7e4729b49fce
                [4][f]
                  SHA-256("11")=4fc82b26aecb47d2868c4efbe3581732a3e7cbcc6c2efb32062c08170a05eeb8
        [5]
          SHA-256("23")=535fa30d7e25dd8a49f1536779734ec8286108d115da5045d77f3b4185d8f790
      [67]
        [6]
        [7]
          SHA-256("7")=7902699be42c8a8e46fbbb4501726517e86b22c56a189f7625a6da49081b2451
  [89abcdef]
    [89ab]
      [89]
        [8]
        [9]
          SHA-256("19")=9400f1b21cb527d7fa3d3eabba93557a18ebe7a2ca4e471cfe5e4c5b4ca7f767
      [ab]
    [cdef]
      [cd]
        [c]
        [d]
          SHA-256("2")=d4735e3a265e16eee03f59718b9b5d03019c07d8b6c51f90da3a666eec13ab35
      [ef]
        [e]
          [e][01234567]
          [e][89abcdef]
            [e][89ab]
              SHA-256("31")=eb1e33e8a81b697b75855af6bfcdbcbf7cbbde9f94962ceaec1ed8af21f5a50f
            [e][cdef]
              SHA-256("5")=ef2d127de37b942baad06145e54b0c619a1f22327b2ebbcfbec78f5564afe39d
        [f]

Jak widać, całość ma złożoność logarytmiczną. Jeśli chcemy sprawdzić, czy dany element istnieje, wystarczy wykonać SHA-256 na tym elemencie i możemy z łatwością go znaleźć w takim drzewie, sprawdzając bit po bicie. W przypadku dokładania nowego elementu, wystarczy znaleźć miejsce podczas przeszukiwania i go tam utworzyć. Jedyną zmianę względem klasycznego drzewa binarnego stanowi sortowanie i jest to klucz do dowodu na brak danego elementu. Ustalenie standardowego formatu wyklucza możliwość podawania błędnych danych.

Jeśli chodzi o zastosowania praktyczne, to można użyć opisanego modelu przy zdecentralizowanym kopaniu, opartym na dowodach a'la SPV. Mianowicie: każdy górnik wykopuje swój własny nagłówek bloku i zgłasza 80 bajtów do sieci. Następnie taki element jest wkładany do wspomnianego drzewa binarnego i jest liczony jako share, czyli udział przy kopaniu, a także występuje zaalokowanie monet, proporcjonalnie do zgłoszonego hashu. W takim modelu aby wydać wspomniane monety, należy dostarczyć dowód na to, że blok jest poprawny. Tutaj również można użyć uproszczonej weryfikacji i poinformować sieć tylko o tych elementach, które są unikalne dla danego bloku, odnosząc się jedynie do różnic pomiędzy blokiem będącym częścią łańcucha, a blokiem wykopanym przez górnika.

Początkujący
Posty: 2365
Rejestracja: 4 kwietnia 2020
Reputacja: 386
Reputacja postu: 
2
Napiwki za post: 0 BTC
Napiwki: LaJyKiGrGR82QJH9NRU5N2XqDsGxsjfSuW

Posortowane drzewo binarne, czyli dowód na to, że element nie należy do zbioru

Postautor: zdzicho2000 » sobota, 14 maja 2022, 10:27

już dawno nie było na forum tak dzielącego się wiedzą fachowca

Wróć do „Bitcoin”

Kto jest online

Użytkownicy przeglądający to forum: Obecnie na forum nie ma żadnego zarejestrowanego użytkownika i 13 gości