Słówko perkele po fińsku oznacza „diabeł”. Ma też piękne brzmienie. Rzecz w tym, że w Finlandii, gdyby istniała, większość społeczeństwa to luteranie. Zatem słówko to jest traktowane jako taka nasza rodzima kurwa.

Po tym krótkim wstępie przejdźmy do dzisiejszego tematu.

Drzewa Merkle – wstęp

Drzewa Merkle nazywane drzewami hash W są strukturą danych, która ma ułatwiać pracę z dużymi danymi. Historia powstania jest banalna. Ralph Merkle potrzebował w jakiś sposób przechowywać i przesyłać drzewa podpisów jednorazowych Lamporta. Przechowywanie samo w sobie jest już problemem. Ilość danych rośnie wykładniczo ( efektywnie) wraz ze wzrostem liczby komunikatów. Nie ma jednak możliwości „naprawienia” tego elementu. Znacznie poważniejszym problemem jest jednak przesyłanie danych (podpisów) w celu weryfikacji. Wyobraźmy sobie, że musimy przesłać ciąg podpisów dla 1000 wiadomości. Będzie on miał około 20MB. Teraz dokładamy kolejny tysiąc wiadomości i nasz blob danych ma teraz… 200MB. Schemat Lamporta ma tę zaletę, że jest bezpieczny nawet w przypadku ataku z wykorzystaniem komputera kwantowego. Jednak trochę to waży.
Pytanie, czy musimy przesyłać wszystkie dane, by móc sprawdzić jakiś ich fragment?
Oczywiście nie! Ralph Merkle zaproponował proste rozwiązanie.

  • Podzielmy nasze dane na N bloków (nie ma znaczenia czy równych);
  • dla każdego bloku policzmy hash np. za pomocą SHA1;
  • pogrupujmy bloki (w pary dla zachowania prostoty);
  • dla każdej takiej grupy policzmy hash z hashy bloków;
  • jeżeli jest więcej niż jedna grupa, to pogrupujmy je tak jak bloki i wyliczmy hash;
  • jeżeli została jedna grupa, to jest ona korzeniem drzewa;

Ten algorytm produkuje nam drzewo. Liśćmi są bloki danych z hashem. Węzłami bloki zawierające skrót wyliczony ze skrótów liści albo skrótów węzłów potomnych.

Proces weryfikacji poprawności (prawdziwości) bloku jest prosty.

  • Na początek potrzebuję pobrać z zaufanego źródła hash korzenia;
  • pobieram blok n (losowy);
  • wyliczam hash bloku;
  • pobieram hash bloku, z którym mam wspólnego rodzica;
  • wyliczam hash rodzica i jeżeli to korzeń to porównuję z pobraną z zaufanego źródła wartością;
  • jeżeli to węzeł, to pobieram hash „rodzeństwa”, wyliczam hash rodzica i tak aż do korzenia.

Jeżeli hash korzenia, pobrany z zaufanego źródła, jest taki sam jak hash, który wyliczyłem, to pobrany blok jest poprawny.
Algorytm ten wykorzystują sieci p2p, mechanizmy weryfikacji spójności w bazach danych oraz algorytmy kompresji.

Kata

Kata (形) to z japońskiego forma – układ. W sztukach walki kata, to rodzaj ćwiczeń, polegających na powtórzeniu pewnej sekwencji ruchów. Pozwala to wyćwiczyć pamięć mięśniową (nawyków), a tym samym powtarzalność. Nauka wykorzystania wyćwiczonych nawyków, ich kompozycji, odbywa się w formie kumite, czyli ćwiczeń dowolnych.
W IT kata to ćwiczenie mające na celu poznanie pewnych technik i narzędzi. Przy czym, równocześnie dotykamy różnych aspektów pracy. W tym przypadku kata i kumite są znacznie bliżej siebie niż w sztukach walki.
Ponadto w IT przyjęło się, że kata jest bardzo mocno związane z TDD. Wynika to z faktu, że największym promotorem tej formy nauki jest Wujek Bob.

O czym będzie ten cykl?

Biorąc pod uwagę dotychczasowe wywody, można założyć, że kilka najbliższych wpisów będzie poświęcone wykonaniu jakiegoś kata TDD.
A tu niespodzianka. Otóż celem jest przeprowadzenie czytelnika, przez proces projektowania kata. Dzięki temu będzie on wiedział jak rozszerzyć swój katalog ćwiczeń i tym samym nie popaść w powtarzalność.