Szyfrowanie homomorficzne, czyli nowe funkcjonalności bez zmiany konsensusu

Wygadany
Awatar użytkownika
Posty: 593
Rejestracja: 8 lutego 2020
Reputacja: 1114
Reputacja postu: 
20
Napiwki za post: 0 BTC
Lokalizacja: 7-bit secp256k1

Szyfrowanie homomorficzne, czyli nowe funkcjonalności bez zmiany konsensusu

Postautor: garlonicon » sobota, 7 maja 2022, 08:25

Ludzie często myślą, że Bitcoin jest taki, jaki jest i że kompletnie nic z tym nie można zrobić bez zgody programistów. O ile jest to częściowo prawda, o tyle szyfrowanie homomorficzne stanowi potężną broń przeciwko stagnacji i pozwala na dołożenie kompletnie nowych reguł bez zmiany istniejących w taki sposób, aby nie można było tego łatwo powstrzymać. Jeśli chodzi o inspirację oraz podstawowe informacje na temat tego, co jest możliwe, to głównym źródłem jest ta strona: https://duo.com/labs/tech-notes/2p-ecdsa-explained. W dzisiejszym wpisie postaram się przekuć niektóre technikalia na bardziej ludzki język i wyjaśnić podstawowe mechanizmy za tym stojące w uproszczony sposób.

Zacznijmy od podstaw, czyli od samego słowa "szyfrowanie": każdy wie, że dane można przygotować, następnie zaszyfrować, przesłać dalej i na końcu odszyfrować. Jest to podstawowe zastosowanie, po prostu i zwyczajnie polegające na tym, żeby trzecia strona nie mogła tych danych podejrzeć w odszyfrowanej formie. Jednakże, na tym cała zabawa się nie kończy, jest to jedynie początek, niejako brama do znacznie ciekawszego świata.

Drugie słowo stanowi klucz do całej zagadki: "homomorficzne". Sama definicja z Wikipedii jest krótka i zawiera jedno zdanie, ale dobrze to wyjaśnia: "szyfrowanie, które pozwala na operowanie na zaszyfrowanym dokumencie bez jego deszyfrowania (bez znajomości klucza deszyfrującego)". I dokładnie o to w tym wszystkim chodzi! Kryje się za tym ogromny potencjał, na przykład można zrobić tak, aby obie strony najpierw zaszyfrowały swoje klucze prywatne, a następnie przygotowały transakcję, działając tylko i wyłącznie na zaszyfrowanych danych, które na samym końcu są wspólnie odszyfrowywane i rozgłaszane w sieci. Proste i genialne w swojej prostocie!

Co to oznacza w praktyce? Na przykład to, że jeśli na jakiejś monecie mamy działające klucze publiczne, to niczego więcej nie potrzeba do zrobienia transakcji typu multisig. Jeśli chcemy na przykład mieć 2-of-2 multisig, to możemy to zrobić nawet na P2PK. Co za tym idzie, możemy użyć dowolnych adresów, czy to Segwit, czy też Taproot, czy jeszcze coś, czego dzisiaj nie znamy. Podlinkowany przykład zawiera opis tego, jak można to zrobić w praktyce, wraz z technikaliami za tym stojącymi.

Kolejnym praktycznym zastosowaniem jest składanie transakcji. Skoro jesteśmy w stanie zrobić multisig na P2PK (czyli na każdym typie adresu), to może dałoby się wpakować tam całą transakcję? Otóż owszem, da się. Można zrobić to tak, jak w protokole MimbleWimble, ewentualnie tak, jak w Monero. Transakcje można łączyć, klucze publiczne da się dodawać, a to wszystko oznacza, że wiele transakcji off-chain można złożyć do jednej transakcji on-chain, co sprawia, że opłaty ponoszone przez każdą stronę drastycznie maleją (drastycznie, to znaczy, jeśli mamy opłatę wynoszącą 500 satoshi i mamy 500 osób, to każdy płaci jedynie jednego satoshiego od swojej transakcji).

Można byłoby się nadal rozwodzić nad tym, co jeszcze da się zrobić, gdyż (zgodnie z tytułem) jest to wytrych pozwalający na dołożenie "nowych funkcjonalności bez zmiany konsensusu". Przejdźmy jednak do strony praktycznej, czyli jak to technicznie wygląda i jak zrozumieć, że to jest w ogóle możliwe, jeśli ktoś nigdy o tym nie słyszał. Otóż: wielu programistów rozumie, w jaki sposób działa XOR. Wielu też zna najprostszy możliwy szyfr, polegający zwyczajnie na tym, że rozmiar klucza jest równy rozmiarom wiadomości, zaś dane są po prostu XORowane ze sobą, co przy losowym kluczu jest szyfrem nie do złamania (wraz z matematycznym dowodem na to, że brute force to jedyne wyjście, zakładając wystarczającą losowość klucza).

W praktyce, szyfrowanie homomorficzne wygląda nieco inaczej, ale przykład używający funkcji XOR jest wystarczający do przekonania się, że takie technikalia istnieją i że takie sztuczki są możliwe. Przykładowo, mamy wiadomość "HelloWorld(123)". Druga strona ma wiadomość "456", którą chce dodać. Jak to zrobić w naszym uproszczonym modelu? Funkcja XOR mogłaby nam tutaj zepsuć nieco dane, ale już samo dodawanie dużych liczb (z użyciem reszty z dzielenia) jest w stanie ładnie to ogarnąć. Choćby tak:

             message1=48656c6c6f576f726c642831323329
SHA-256("garlonicon")=272fc6644fedff1a897d6034bed23f61859e99440ee699033307976590316723
                 mask=ffffffffffffffffffffffffffffff0000000000000000000000000000000000
                 key1=272fc6644fedff1a897d6034bed23f
             message2=343536
     SHA-256("Alice")=3bc51062973c458d5a6f2d8d64a023246354ad7e064b1e4e009ec8a0699a3043
                 mask=ffffff0000000000000000000000000000000000000000000000000000000000
                 key2=3bc510
           encrypted1=6f9532d0bf456e8cf5e18865f10568
           encrypted2=6ffa46
     encrypted2_align=00000000000000000000006ffa4600
         encryptedSum=6f9532d0bf456e8cf5e188d5eb4b68

Teraz czas na odszyfrowanie tego. Ogólna zasada przekazywania danych wygląda następująco:

decryptBob(decryptAlice(encryptBob(encryptAlice(messageAlice))))=messageAlice

Innymi słowy: najpierw obie strony nakładają swoje szyfrowanie, a następnie zdejmują je w tej samej kolejności (kolejność jest istotna, ma być taka sama, a nie odwrócona!). Jeśli nie powoduje to zmian wiadomości ani ujawnienia klucza, to taki model jest bezpieczny. W powyższym przypadku samo dodawanie sprawia, że wiadomość jest nadal poprawna, ale powstaje problem z ujawnieniem klucza szyfrującego. Modele używane w praktyce, na przykład "Paillier Homomorphic Encryption" (dostępne w Pythonie jako "phe", podstawowy opis jest na stronie: https://coderzcolumn.com/tutorials/pyth ... yption-phe) są na to odporne. Wróćmy jednak do zdeszyfrowania naszej wiadomości:

         encryptedSum=6f9532d0bf456e8cf5e188d5eb4b68
                 key1=272fc6644fedff1a897d6034bed23f
        subtractedSum=48656c6c6f576f726c6428a12c7929
           key2_align=00000000000000000000003bc51000
               result=48656c6c6f576f726c642865676929

Jak łatwo zauważyć, otrzymaliśmy napis "HelloWorld(egi)". Wynika to z tego, że nie dodajemy "123" do "456", tylko dodajemy znaki ASCII. W praktycznych zastosowaniach, dane są przechowywane w formie binarnej, a nie tekstowej, więc ten problem nie występuje. Jeśli jednak odejmiemy kod znaku "zero", to uzyskamy właściwy napis:

               result=48656c6c6f576f726c642865676929
           zero_chars=000000000000000000000030303000
         final_result=48656c6c6f576f726c642835373929

Mamy to, uzyskaliśmy napis "HelloWorld(579)", czyli to, o co nam chodziło. Oczywiście, podane przykłady są obarczone wadami, ponieważ normalnie nie trzymamy liczb jako dziesiętnie zapisany tekst, tylko mamy je w formie binarnej. Niemniej jednak, myślę że przedstawione przykłady dobrze pokazują samą ideę i ułatwiają zrozumienie tego, co jest możliwe w praktycznych szyfrach, które są nieco bardziej złożone, gdyż muszą być odporne na tak proste ataki, jak ujawnienie klucza drugiej strony podczas deszyfrowania.

Wróć do „Bitcoin”

Kto jest online

Użytkownicy przeglądający to forum: Obecnie na forum nie ma żadnego zarejestrowanego użytkownika i 16 gości