26 lipca 2013

Problemem internetu jest to, że... jest zbyt tani



Temat brzmi dość absurdalnie. Ktoś złośliwy dla ekipy rządzącej pewnie zasugerowałby, że to kolejny pomysł ministra gospodarki. Jednak w tym zaskakującym stwierdzeniu nie kryje się wcale sposób zwiększenia wpływów do budżetu państwa, lecz możliwość rozwiązania wielu problemów światowej sieci. Problemy te związane są z sieciowym bałaganem, który zostawiają po sobie wszelkie boty, a którego symbolem stał się spam. Autorowi wcale nie chodzi o zwiększenie opłaty abonamentowej, która spowodowałaby, że Internet stałby się mniej powszechny. Wysłanie wiadomości mailowej jest dziś w praktyce bezkosztowe, płacimy tylko ryczałt za dostęp do Internetu. Zanim nadeszła era globalnej wioski, różnica w koszcie wysłania jednej, a tysiąca tradycyjnej wiadomości była olbrzymia. Koszt znaczka pocztowego i koperty był dowodem na to, że przy wysłaniu listu ponieśliśmy jakiś trud (w tym przypadku finansowy). Dziś wysłanie większej ilości wiadomości drogą elektroniczną nie stanowi żadnej różnicy w stosunku do wysłania pojedynczego egzemplarza. Czy to jest właśnie jedna z przyczyn tworzenia się śmietnika w globalnej pajęczynie?


Myślisz pewnie, że zaraz zasugeruję, że należałoby opodatkować wysyłanie wiadomości. Oj nie! Wystarczy abyśmy za każdym razem przy wysyłaniu wiadomości musieli udowodnić, że poświęciliśmy temu działaniu jakiś wysiłek. Wysiłek większy niż użycie metody copy&paste, dzięki której wysłalibyśmy maila w ciągu sekundy. Ściślej rzecz ujmując komputer musi udowodnić, że wykonał jakąś trudną pracę (trwającą dłuższą chwilę - ściślej wykonaną w czasie wykładniczym od rozmiaru danych) przy tej całej operacji. Do wiadomości załączana jest pieczęć, która jest "dowodem pracy". Następnie odbiorca naszej wiadomości mając ten dowód pracy sprawdza szybko (błyskawicznie - ściślej w czasie wielomianowym), czy dowód jest poprawny. Jeżeli tak jest nasza wiadomość staje się wiarygodna. W przeciwnym przypadku mamy dość duże prawdopodobieństwo, że padliśmy ofiarą spamu.

Prekursorami dowodów pracy są autorzy publikacji "On Memory-Bound Functions for Fighting Spam" , czyli Dwork, Naor i Goldberg (1992). Ważnym praktycznym osiągnięciem w tej dziedzinie jest hashcash wykorzystywany między innymi przez serwis BitCoin służący do anonimowego transferu pieniądza. Hashcash jest swego rodzaju elektronicznym znaczkiem pocztowym. Generowanie dowodu tego typu (nie skupiam się tutaj na standardzie, ale ilustracji metody tego typu) polega na tym, że musimy znaleźć taką liczbę k, dla której hash na pierwszych N najbardziej znaczących bitach będzie zawierał same zera. Skrót generowany jest z wejścia, które jest złączeniem treści wiadomości, jej odbiorcy, czasu wysłania i wylosowanej liczby, którą dołączamy jako dowód. Taką wartość k znajdujemy w średniej liczbie prób 2^(N-1).  Skąd się bierze taka liczba prób? Korzystamy z jednej z własności funkcji hashującej, czyli jej pseudolosowości. Zgodnie z nią hash ma przypominać wylosowaną wartość. W naszym przypadku używamy jednostronnej funkcji hashującej SHA-1 (funkcja 160 bitowa).

Przykład. Załóżmy, że N określiliśmy jako 40 najbardziej znaczących bitów. Nasza funkcja hashująca wygląda następująco SHA-1(message + recipient + time + k). Dla wiadomości "Testowa", odbiorcy "imie.nazwisko@gmail.com" i daty "2013-07-26 00:00" losujemy wartość k, dla której 40 najbardziej znaczących bitów będzie wyzerowanych. 

Jedną z takich wartości k jest 1053786903041250420403443923384887918684823022029. Wysyłamy wiadomość o podanych parametrach załączając taki dowód liczbowy. Przy policzeniu SHA-1 otrzymujemy "000008682c554f02a7f4ebc8d7acdb3adb8ef735". Pierwsze 5 znaków liczby szesnastkowej hasha ma wartość 0, a więc wiemy, że pierwsze 20 bitów w rzeczywistości są bitami 0, więc k jest prawidłowe. 

Bardzo prostą implementację tego "pseudo hashcasha", którą wykonałem na potrzeby tego wpisu, możesz znaleźć tutaj. Dla przyśpieszenia generowania dowodu w interpreterze Pythona zamiast N najbardziej znaczących bitów wykorzystałem N najbardziej znaczących bajtów. Jeżeli to wprowadzenie do tematu "dowodów pracy" sprawiło, że poczułeś się zainteresowany tym zagadnieniem poniżej znajdziesz kilka ciekawych odniesień. Czy uważasz, że wysyłanie wiadomości powinno stać się bardziej kosztowne?

Ciekawe odniesienia:

Pliki cookies

Uwaga! Strona wykorzystuje do działania pliki cookies, które są zbierane między innymi w celach reklamowych oraz statystycznych, a także dla poprawy wygody korzystania z serwisu. Jeżeli nie zgadzasz się z tym wyłącz opcję w przeglądarce. Więcej informacji