Bitcoin dla opornych: Hash

[mainframe]

Hash - Wyobraźmy sobie książkę "Pan Tadeusz" Adama Mickiewicza.

"Pan Tadeusz, czyli Ostatni zajazd na Litwie. Historia szlachecka z roku 1811 i 1812 we dwunastu księgach wierszem – poemat Adama Mickiewicza wydany w 1834 w Paryżu. (...) Epopeja narodowa z elementami gawędy szlacheckiej powstała w latach 1832-34 w Paryżu. Składa się z dwunastu ksiąg pisanych wierszem, trzynastozgłoskowym aleksandrynem polskim.
Rękopis poematu znajduje się w Ossolineum we Wrocławiu wraz ze specjalną ozdobną szkatułką do jego przechowywania, z mahoniu i kości słoniowej, zamówioną przez Stanisława Tarnowskiego i wykonaną w 1873 przez lwowskiego artystę Józefa Brzostowskiego.


Widzimy przed oczami wyobraźni tę książkę?
Otóż gdybyśmy stworzyli dla niej podpis cyfrowy - tzw. hash tego poematu (przy użyciu algorytmu o nazwie SHA-256) wyglądałby on mniej więcej tak:

b58ba29045baf1ee36ee9c53a4dbefbf256ab83479ee68e519dea1fcddee18d5

Powyższy ciąg znaków w sposób jednoznaczny stwierdza autentyczność iż mamy do czynienia z oryginałem napisanym przez Adama Mickiewicza właśnie w 1834 r. w Paryżu. Nie inaczej. Gdybyśmy przestawili jedną kropkę, zamienili jedna literkę czy choćby dodali jedną spację więcej pomiędzy dwoma z tysięcy słów - hash poematu drastycznie by się zmienił. Usuniecie wprowadzonej zmiany i obliczenie podpisu ponownie - przywróci hash oryginału.
Tego konkretnego ciągu znaczków w identyfikatorze dla "Pana Tadeusza" nie sposób osiągnąć w inny sposób niż przeliczając cały tekst stosując matematyczny algorytm szyfrowania (w tym wypadku właśnie SHA-256).
Żaden inny tekst, żaden inny ciąg milionów przypadkowych kombinacji znaków, liczb, kropek, przecinków czy znaków specjalnych nie będzie posiadał identycznego podpisu przy zastosowaniu tego samego algorytmu szyfrowania.
Choćbyśmy mieli próbować setki milionów innych układów tekstów czy ciągów znaków. Gdybyśmy mogli sprawdzić 183 miliony takich "tekstów" na sekundę, gdybyśmy mieli zacząć od początku istnienia wszechświata (czyli ok. 14 mld lat temu) a skończyli dziś - nie podrobimy tego identyfikatora;) Jest tak unikalny.
Co ciekawe można "zamienić" tekst(lub plik z danymi) w ciąg znaków identyfikatora hash, ale w drugą stronę już się nie da.
Aby zweryfikować czy dany hash jest zgodny ze źródłem należy ponownie obliczyć hash źródła by porównać dwa hash'e.

Dla przykładu identyfikator słowa dupa w formacie szyfrowania SHA-256 to:
60a5d3e4100fe8afa5ee0103739a45711d50d7f3ba7280d8a95b51f5d04aa4b8

Trudno odróżnić geniusz Mickiewicza od zwykłej głupoty jeśli porównujemy podpisy w formacie hash. Ale jedno trzeba im oddać - podrobić się skubańców nie da.
Polecam pobawić się przez chwilę bardzo fajnym kalkulatorem SHA256 aby przyswoić czym jest hash dla ciągu znaków:
http://www.xorbin.com/tools/sha256-hash-calculator
Należy pamiętać że istnieje wiele sposobów kodowania: SHA-1; MD5; SHA-256, SHA-384; SHA-512 etc.

Hash to niepowtarzalny cyfrowy podpis. Służy do weryfikowania dowolnie długich "tekstów" za pomocą jednego krótkiego identyfikatora.
Tworzenie unikalnego identyfikatora (hasha) polega na przetworzeniu danych za pomocą skomplikowanych algorytmów matematycznych.
W wyniku przetwarzania powstanie relatywnie krótki ciąg literek i cyferek.

Tworzenie hash'a zajęło by nam ręcznie baaardzo dużo czasu, komputer a dokładnie jego procesor robi to błyskawicznie ale co ciekawe w komputerze istnieje inny komponent który potrafi wykonać obliczenia o wiele szybciej niż procesor. Tym elementem jest karta graficzna - podzespół bazowy komputera przetwarzający dane aby wyświetlać je na ekranie monitora. Karta graficzna to bardzo skomplikowany układ elektroniczny posiadający odrębny procesor graficzny GPU czasami kilka GPU na jednej karcie. Układy graficzne w "operacjach kodowania cyfrowego podpisu" nie mają sobie równych.

Przodują w tym karty firmy ATI (system OpenCL) w odróżnieniu do kart firmy Nvidia (system Cuda).
Stare modele kart graficznych nie potrafią wykonywać obliczeń wcale.
Listę kart i ich wydajność mierzoną w Mhash/s obejrzeć i porównać można pod adresem:
https://en.bitcoin.it/wiki/Mining_hardware_comparison

Karta graficzna potrafi wykonać miliony!! operacji w ciągu jednej sekundy.
1 Mhash/s - oznacza milon operacji hash na sekundę.


DODATEK:
Bardzo prostą funkcją haszującą może być na przykład reszta z dzielenia danej liczby przez 17
h (1000) = 14
h (2345) = 16
h (54321) = 6


oznacza to w praktyce że każdej liczbie możemy przyporządkować inną liczbę według jakieś przyjętej zasady:
reszta z dzielenia 1000 przez 17 to:
1000/17 = 58,823529411764705882352941176471
17*58 = 986
1000 - 986 = 14
Przykład:
Do przewiezienia 1000 osób w autobusach 17 osobowych, potrzebujemy 58 autobusów - w 59 autobusie pojedzie 14 osób.
Mając firmę przewozową i autobusy 17 osobowe - nasza funkcja hashująca mówi nam ile osób pojedzie w ostatnim autobusie.
Jeśli liczba jest podzielna przez 17 - reszta z dzielenia wyniesie 0.
14 to hash naszej funkcji mod 17 z h (1000)
Źrodło:
http://www.zgapa.pl/zgapedia/Funkcja_ha ... %85ca.html


DLA DOCIEKLIWYCH:
Cryptographic hash function [Wikipedia ENG]
http://en.wikipedia.org/wiki/Cryptograp ... h_function
File Hash Generator Shell Extension - porównywanie pliku i jego hasha
http://www.codeproject.com/KB/shell/Fil ... nsion.aspx
Pan Tadeusz
http://pl.wikipedia.org/wiki/Pan_Tadeusz


źródło artykułu:
http://forum.polmine.pl/index.php?topic=791.0

[severson]

Nie jest prawdą, że żaden inny ciąg znaków nie posiada takiego samego hasha.
Nie ma funkcji różnowartościowych przeprowadzających większy zbiór w mniejszy

[Kazik]

Nie jest prawdą, że żaden inny ciąg znaków nie posiada takiego samego hasha.
Nie ma funkcji różnowartościowych przeprowadzających większy zbiór w mniejszy

Powiem więcej, isnieje nieskończenie wiele tekstów które dają taki sam hash jak "Pan Tadeusz".
Tak samo, raczej nie chodziło o to, że starsze karty nie potfafiły robić obliczeń, chodziło raczej o to, że nie było takie api udostępnionego, bo jednak dalej to są operacje na macierzach itd.

Ale ogólnie, w ciekawy sposób napisane.

Możliwe natomiast jest by istniał hash o nieskończenie wielkiej ilości bitów różny dla dowolnego ciągu znaków

Tak i to ma nazwę...szyfrowanie

[Bitmar]

Nie jest prawdą, że żaden inny ciąg znaków nie posiada takiego samego hasha.
Nie ma funkcji różnowartościowych przeprowadzających większy zbiór w mniejszy

Zgadza się, to niemożliwe by hash czyli ciąg znaków o skończonej ilości kombinacji był różny dla każdego ciągu o dowolnej długości. Możliwe natomiast jest by istniał hash o nieskończenie wielkiej ilości bitów różny dla dowolnego ciągu znaków

[mainframe]

Fajnie że w kategorii teksty dla opornych, błąd merytoryczny dotyczy zagadnienia bardziej szczególnego.
W końcu nie jest moją intencją tłumaczenie ilości możliwych kombinacji hashy dla szyfrowania SHA-256 oraz czy jest to zbiór skończony czy też nie osobie zielonej w temacie a w szczególności mojej babci.

Chociaż błąd jest bezdyskusyjny muszę się zastanowić w jaki sposób ubrać porównanie "obliczeń od początku powstania wszechświata" tak aby mogło ono pozostać.
Ekstremalne porównania to coś co specjalista od mnemotechnik pamięciowych Harry Lorane używał aby jego słowa utkwiły w pamięci słuchaczy na długo:) Chciałem aby w tekście było ich sporo.

Taka koncepcję artykułu obrałem i to jego ciężar. Być może nie będzie on publikowany w Times ^^ ale ważna jest jego nośność. To aby "przedszkolacy miningu" zrozumieli o co w nim chodzi, pokłosi ich zrozumienia to opisane ich własnymi słowami zagadnienia swoim kolegom i koleżankom w przyszłości.

Głupio gdy nowy narybek kopaczy wie tylko że coś tam się liczy i niby jest z tego jakaś tam dziwna kasa ale zawsze można ją zamienić na złotówki i kupić piwo.

To może inaczej, a ile jest tych kombinacji może ktoś wie ?
Zakładam że liczba jest tak duża że da się z tego sklecić coś od początku wszechświata heh

Stare modele kart graficznych nie potrafią wykonywać obliczeń wcale.

Fakt przegiąłem. Podanie nieprawdziwej informacji nie jest dobre. Przemyślę ten wątek i jakoś go poprawię. Choć z pozytywów w tym wypadku moja dezinformacja ucina wiele pytań typu: czy mogę liczyć na moim procesorze w laptopie?

Prawdopodobnie będzie to coś w rodzaju:
Stare modele kart graficznych nie nadają się do wykonywania obliczeń wcale, ich prędkość byłaby znikoma.

[Kazik]

To może inaczej, a ile jest tych kombinacji może ktoś wie ?
Zakładam że liczba jest tak duża że da się z tego sklecić coś od początku wszechświata heh

Jak nazwa wskazuje jest to 2^256, czyli 77 zer . I gdyby tak liczyc te 200 milionów na sekundę to wyjdzie.. blisko dwójki i 61 zer (w latach) a wiek wrzechświata ma chyba 10 zer.

Swoja drogą znalezienie danego hasha to największy stopień trudności w BTC. Czyli przy obecnej ilości TH/s dalej czasów wszechświatów brakuje (56 zer do 10 zer) czyli nawet jak moc sieci zwiększy się miliard razy dalej będzie daleko powyżej wszechświata(tzn. dla pewności rzędu 100%)