Masz kolegę. Obaj pracujecie w tej samej firmie. Macie takie same stanowiska, wykonujecie identyczną pracę, przyszliście do firmy w tym samym momencie.
Ale czy zarabiacie tyle samo?
Chcielibyście to sprawdzić. Jest to jednak mocno problematyczne. Teoretycznie moglibyście się umówić, że obaj zapisujecie na kartce swoje pensje i pokazujecie je na „trzy cztery”.
Tylko co, jeśli jednak nie zarabiacie tyle samo, a co więcej - różnica w waszych zarobkach jest bardzo duża? Na pewno nie będzie to komfortowe dla żadnej ze stron. Jak rozwiązać ten problem? O tym w dzisiejszym materiale.
Nie jestem ekspertem od kryptografii ani matematyki. Ten tekst to luźne tłumaczenie materiału z serwisu Twisted Oak (opublikowane za zgodą autora). Jest to uproszczone rozwiązanie problemu. Więcej informacji znajdziesz tutaj.
Dla uproszczenia załóżmy, że Tomek oraz Kacper mogą zarabiać siedem, osiem albo dziewięć tysięcy.
Kacper idzie do sklepu i kupuje trzy skarbonki. Są one nieprzeźroczyste – nie widać co jest w ich wnętrzu. Każdą z nich odpowiednio opisuje, tak aby było wiadomo, która z nich oznacza jakie zarobki.
Skarbonki są zamykane na kluczyk. Można do nich wrzucić pieniądze – ale aby można je było wyjąć, należy posiadać odpowiedni klucz. Jeden klucz pasuje tylko do jednej skarbonki. Klucz ze skarbonki A nie pasuje do skarbonki B.
Kacper wybiera teraz tą skarbonkę, która opisana jest kwotą jaką zarabia. Klucze do innych skarbonek wyrzuca – tak aby nie mógł ich otworzyć.
Wychodzi z pokoju, a na jego miejsce wchodzi Tomek.
Nie posiada on żadnego klucza – więc nie może otworzyć żadnej skarbonki. Nie wie też jaki klucz posiada Kacper – bo nie był w pokoju w momencie wyrzucania kluczy.
Tomek ma trzy kartki – jedną z napisem TAK oraz dwie z napisem NIE.
Teraz, do każdej skarbonki wrzuca jedną kartkę przez otwór na monety. Do skarbonki oznaczonej kwotą, którą zarabia wrzuca tą z napisem TAK. Do reszty – te z napisem NIE.
Wychodzi z pokoju i ponownie woła Kacpra. Kacper w samotności otwiera skarbonkę do której posiada klucz i wyjmuję kartkę, która się tam znajduje.
- Jeżeli wyciągnął tą z napisem
TAK– wie, że zarabiają tyle samo.
- Jeżeli tą z napisem
NIE– ich zarobki różnią się.
Ponieważ wcześniej wyrzucił klucze do innych skarbonek – nie może ich sprawdzić, zatem nie dowie się ile zarabia Tomek.
Zamyka teraz skarbonkę i woła Tomka do pokoju. Pokazuje mu kartkę z napisem TAK/NIE, którą przed chwilą wyciągnął. Na tej podstawie Tomek dowiaduje się, czy zarabiają tyle samo.
- Jeżeli zobaczy kartkę z napisem
TAK– zarabiają tyle samo. - Jeżeli odpowiedź brzmi
NIE– obaj dalej nie wiedzą ile zarabia każdy z nich. Wiedzą tylko, że nie zarabiają tyle samo.
Oczywiście zakładamy tutaj, że każdy z nich nie kłamie. Bo przecież nic nie stoi na przeszkodzie, aby Kacper wybrał klucz do innej skarbonki (albo nie wyrzucił innych kluczy).
Tak samo Tomek – może przecież skłamać i do wszystkich skarbonek wrzucić kartkę z napisem TAK.
Alternatywny opis problemu tutaj. Więcej informacji o "Zero Knowledge" w przestępnej formie – tutaj.