Zobowiązanie bitowe
Z Wikipedii
Zobowiązanie bitowe to operacja kryptograficzna, w której:
- zobowiązujący decyduje się na jakąś wartość X, jednego lub większej ilości bitów
- zobowiązujący ujawnia pewną wartość Y, czyli zobowiązanie bitowe
- na podstawie Y nikt nie powinien móc dowiedzieć się jakie było X z prawdopodobieństwem istotnie różnym od 0
- kiedy przyjdzie na to pora, zobowiązujący ujawnia X oraz dowód Z tego, że Y rzeczywiście zobowiązywało go do X
Zobowiązania bitowe najprościej zaimplementować za pomocą funkcji haszującej:
- zobowiązujący losuje Z i wysyła Y = H(X,Z)
- jeśli funkcja jest trudna do odwrócenia (odporność na przeciwobraz, w tym każdy bit przeciwobrazu musi być odporny), nikt nie odczyta X na podstawie Y.
- jeśli zobowiązujący potrafiłby wybrać takie liczby, że H(X1,Z2) = H(X2,Z2), dla
, to potrafiłby generować kolizje funkcji haszującej. Jeśli więc funkcja jest odporna na kolizje, nie można złamać zobowiązania.
Istnieją też inne systemy zobowiązań bitowych, te oparte na funkcjach haszujących są jednak najczęściej stosowane.
Zobowiązania bitowe mają wiele zastosowań, m.in.:
- Możliwe jest przeprowadzenie uczciwego losowania algorytmem gry w marynarza – każda osoba wybiera jakąś liczbę, liczby te są jednocześnie odsłaniane, następnie dodaje się te liczby do siebie i bierze za rezultat ich resztę modulo ilość możliwych wyników. Żeby zapewnić jednoczesność, każdy najpierw wysyła zobowiązanie, a dopiero po otrzymaniu wszystkich zobowiązań wysyła swoją liczbę. Ponieważ każdy musi wybrać zanim zobaczy liczby innych graczy, nie można oszukiwać.
- Hazard internetowy. Żeby gracze mieli pewność, że kasyno nie oszukuje, kasyno publikuje najpierw zobowiązanie bitowe, następnie gracze obstawiają, a następnie kasyno publikuje wyniki.
- Konkursy z wieloma graczami. Np. w Perl golfie wygrywa ten kto wyśle najlepsze rozwiązanie najszybciej. Publiczne wysyłanie rozwiazań jest wadliwe, gdyż inni mogą zobaczyć rozwiązanie, poprawić je nieco, wysłać jako swoje i wygrać; wysyłanie jedynie wyników również (można twierdzić, że ma się program o danym wyniku, i czekać, aż ktoś taki nadeśle – wtedy kopiuje się jego program i twierdzi, że miało już wcześniej). Publikacja zobowiązań rozwiązuje ten problem – nikt nie widzi naszego rozwiązania, i nikt nie może też kłamać, że miał jakieś rozwiązanie jako pierwszy.
Zobowiązania bitowe nie zapewniają pełnej jednoczesności – o ile nie jest możliwe wysłanie innego wyniku, można nie wysłać żadnego. Np. grając w marynarza można (zakładając że wygrywamy jeśli jest nieparzysta):
- Wybrać 1 i wysłać odpowiednie zobowiązanie
- Odebrać zobowiązanie przeciwnika
- Czekać na odsłonięcie
- Jeśli przeciwnik odsłonił 0, odsłaniamy 1 (i wygrywamy)
- Jeśli przeciwnik odsłonił 1 rozłączamy się lub wysyłamy błędny pakiet
Jest to ważne w bezpiecznym podpisywaniu kontraktów, gdzie bezpieczeństwo zapewniałaby jedynie pełna jednoczesność składania podpisów.
