Zobowiązanie bitowe

Zobowiązanie bitowe – operacja kryptograficzna, w której:

• zobowiązujący decyduje się na jakąś wartość $X,$ jednego lub większej liczby bitów – coś co będzie chciał później udowodnić
• zobowiązujący ujawnia pewną wartość $Y,$ czyli swoje 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$ oblicza $Y=H(X,Z)$ i udostępnia innym wartość $Y$
• 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.$
• w odpowiednim momencie zobowiązujący ujawnia wartość $Z,$ w ten sposób każdy może samodzielnie obliczyć $Y=H(X,Z)$ i sprawdzić, czy zobowiązujący mówił prawdę
• jednak jeśli zobowiązujący potrafiłby wybrać takie liczby, że $H(X_{1},Z_{2})=H(X_{2},Z_{2}),$ dla $X_{1}\neq X_{2},$ 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.

Zastosowania

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 liczba 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 rozwiązań 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 suma 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.