Podpisy Progowe (ang. Threshold Signatures)
Strona Główna
Artykuły
Podpisy Progowe (ang. Threshold Signatures)

Podpisy Progowe (ang. Threshold Signatures)

Zaawansowany
Opublikowane Jul 21, 2019Zaktualizowane Apr 29, 2021
12m
Schemat Podpisów Progowych (TSS), to nic innego jak algorytm kryptograficzny niskiego poziomu, który dedykowany jest tworzeniu (generowaniu) kluczy i wykorzystywaniu ich do podpisywania cyfrowych danych. TSS znajduje szczególne zastosowanie w sieciach blockchain, a wykorzystywany jest szczególnie w zakresie zwiększenia bezpieczeństwa sieci. W szerszym znaczeniu, TSS ma możliwość wywarcia znaczącego wpływu w systemach służących do zarządzania kluczami (takich jak np. portfele do przechowywania kryptowalut). TSS jednocześnie stoi u podstaw dziedziny DeFi. Mimo to, TSS należy w dalszym ciągu postrzegać jako nowa technologa, dlatego też warto wziąć pod uwagę wynikające z jej użycia ryzyka i ograniczenia.

W tym artykule omówimy w szczegółach czym jest TSS, jakie potencjalne korzyści wnosi do przestrzeni blockchain, gdzie rozpocząć w kwestii jego implementacji do własnego projektu oraz jak wygląda na tle ona algorytmów Shamir Secret Sharing czy Multisig. Na samym końcu artykułu omówimy również różne sposoby wykorzystania TSS do zarządzania kluczami rozproszonymi oraz omówimy zagrożenia i ograniczenia wynikające z użycia tego algorytmu.

Siła drzemiąca w kryptografii

Aby móc zrozumieć algorytm TSS, to w pierwszej kolejności koniecznie musimy zrozumieć i posiadać podstawową wiedzę na temat kryptografii. Począwszy od lat 70. XX wieku u coraz większej ilości systemów internetowych (takich jak TLS i PGP ) zaczęto stosować kryptografię asymetryczną, znaną również jako kryptografię klucza publicznego (Public Key Cryptography). PKC opiera się na wykorzystaniu dwóch kluczy: publicznego i prywatnego. O ile klucz publiczny nie musi być trzymany w tajemnicy można go bez obaw publicznie zakomunikować, może być też wykorzystany przez dosłownie każdego, o tyle klucz prywatny jest fragmentem dającym dostęp do tajnych informacji niedostępnych publicznie (przy użyciu klucza publicznego).
Szyfrowanie (ang. encryption) oraz podpisy cyfrowe (ang. digital signatures) są dwoma najczęściej wymienianymi przykładami w których stosuje się PKC. Zarówno algorytmy szyfrujące jak i podpisy cyfrowych opierają się na zestawach trzech algorytmów. Pierwszy z nich odpowiada za generowanie pary kluczy prywatnych i publicznych, drugi za generowanie tekstu zaszyfrowanego/podpisu, a trzeci, odpowiada za proces deszyfrowania/weryfikacji dostarczonych danych. W odniesieniu do podpisów cyfrowych, to w ich przypadku algorytm służący do podpisu w celu uzyskania unikalnego podpisu wymaga podania klucza prywatnego, który znany jest jedynie jego właścicielowi. Tak wygenerowany podpis (ang. signature) dołączany jest później do danej wiadomości propagowanej w sieci przez właściciela klucza prywatnego w taki sposób, że każdy, kto posiada odpowiedni klucz publiczny, będzie mógł zweryfikować autentyczność i poprawność takiej wiadomości.


Blockchain

Nikt nie powinien mieć żadnych wątpliwości, że blockchain jest bardzo potężną technologią. Sieci blockchain zapewniają odpowiednią przestrzeń, która działa wedle zasad zapisanych w konsensusie, w której w odpowiedni sposób zapisywane i organizowane są wpisy (rekordy). Dzięki temu my, użytkownicy, zyskujemy potencjalną moc do tworzenia zdecentralizowanych gospodarek, a nawet rządów. Co zaskakujące, lista algorytmów kryptograficznych potrzebnych do uruchomienia podstawowej sieci blockchain może zamknąć się na podpisach cyfrowych. W kontekście sieci blockchain, klucze prywatne reprezentują tożsamość (osobę, byt), podczas gdy podpisy są publicznym oświadczeniem lub roszczeniem stworzonym/opublikowanym przez daną tożsamość. Blockchain z kolei porządkuje i weryfikuje takie oświadczenia zgodnie z przyjętym w konsensusie sieci zestawem reguł, który między innymi dba o to, aby podpisy były unikalne oraz poprawne.
Algorytmy kryptograficzne wykorzystywane na początku formowania się pierwszych sieci blockchain znacząco różnią się od tych dostępnych dzisiaj. Do najbardziej niesamowitych algorytmów należą obecnie: dowody zerowej wiedzy (ang. zero-knowledge proofs), algorytm szyfrowania homomorficznego, algorytmy do wielopodmiotowych obliczeń - jednak jest ich zdecydowanie więcej. Ostatnia dekada w dziedzinie technologii blockchain spowodowała ogromny wzrost zastosowań kryptografii i pojawienie się wielu innowacyjnych algorytmów - które stosowane są już nie tylko w świecie łańcuchów bloków. 

W artykule skupimy się na jednej z innowacyjnych technologii: Schemacie Podpisów Progowych (TSS).


MPC oraz Threshold Signature Scheme (TSS)

Multi-party computation (pol. dosł. wielopodmiotowe obliczenia - MPC) to gałąź kryptografii, którą zapoczątkowała przełomowa dla tej dziedziny praca Andrewa C. Yao, której publikacja miała miejsce prawie 40 lat temu. MPC polega na tym, iż uczestnicy takiego systemu, którzy nie ufają sobie nawzajem, próbują wspólnie obliczyć funkcję na podstawie posiadanych przez siebie danych wejściowych, zachowując jednak dane wyjściowe dla siebie - w formie prywatnej.

Jako przykład powiedzmy, że "x" pracowników firmy chce wiedzieć, kto otrzymuje największą wypłatę ale nie przy okazji nie chcą ujawniać sobie nawzajem swojej rzeczywistej płacy. Tutaj prywatnymi danymi wejściowymi są pensje, a daną wyjściową, którą poznają wszyscy będzie nazwisko pracownika o najwyższym wynagrodzeniu. Wykonując obliczenia za pomocą MPC, możemy być pewni, że żadno z wynagrodzeń oraz danych pracowników nie zostało ujawnione innym uczestnikom procesu obliczania.

Dwiema głównymi właściwościami MPC są poprawność (prawidłowość) i prywatność:

  • Poprawność: dane wyjściowe wygenerowane przez algorytm są poprawne (zgodnie z oczekiwaniami).

  • Prywatność: prywatne dane wejściowe przechowywane przez jedną ze stron nie są przekazywane innym stronom procesu.

Aby lepiej zrozumieć zasadę działania MPC posłużmy się przykładem. W przykładzie w rozproszony sposób wygenerujemy cyfrowy podpis (sygnaturę). Zobaczmy, jak powyższe właściwości można zastosować do podpisów. Przypomnijmy, że w przypadku podpisów konieczne jest wykonanie następujących trzech kroków:

  • Generacja klucza: pierwszy krok jest również najbardziej złożony. Musimy wygenerować klucz, który będzie jednocześnie publiczny i będzie służył do weryfikacji przyszłych podpisów Przy okazji musimy też wygenerować tzw. individual secret dla każdej ze stron, który nazwiemy secret share. Jeśli chodzi o poprawność danych i prywatność w procesie MPC, to w wyniku obliczeń możemy być pewni, iż wygenerowany zostanie ten sam klucz publiczny dla wszystkich stron oraz inny secret share dla każdej z nich. Tym samym: (1) prywatność: żadne dane secret share nie wyciekły między stronami, oraz (2) poprawność: klucz publiczny jest funkcją secret shares.

  • Podpisywanie: ten krok obejmuje funkcję generowania podpisu. Danymi wejściowymi każdej ze stron będzie ich secret share, utworzony jako wynik poprzedniego kroku (rozproszona generacja klucza). Na tym etapie powstaje również tzw. public input (publiczne dane wejściowe), który jest po prostu wiadomością do podpisania. Wynikiem tej operacji będzie podpis cyfrowy. Właściwość MPC, którą jest prywatność gwarantuje, że na żadnym z etapów obliczeń nie doszło do wycieku secret shares.

  • Weryfikacja: algorytm weryfikacji pozostaje taki sam, jak w ustawieniu klasycznym. Aby zachować zgodność jedno-kluczowymi podpisamy, każdy, kto zna klucz publiczny, powinien mieć możliwość weryfikacji i walidacji podpisów. To właśnie taką pracę wykonują węzły walidujące dane w sieci blockchain.

Threshold signature scheme (TSS) to nazwa, którą nadajemy procesowi generowania klucza rozproszonego (DKG) i rozproszonego schematu podpisywania sygnatur progowych.


Implementacja TSS w blockchain

TSS w naturalny sposób można wykorzystać w blockchain w celu generowania kluczy i podpisów cyfrowych. W tym kontekście będzie to zestaw poleceń wykonywanych przez pełny węzeł (ang. full node). W praktyce technologia TSS pozwala nam zastąpić wszystkie polecenia związane z kluczem prywatnym rozproszonymi obliczeniami.

Aby lepiej wyjaśnić to zagadnienie, zacznijmy od krótkiego wyjaśnienia w jaki sposób tworzone są nowe adresy w klasycznej sieci blockchain. Krótko mówiąc, utworzenie nowego adresu jest możliwe poprzez wygenerowanie klucza prywatnego, a następnie obliczenie klucza publicznego z klucza prywatnego. Tym samym zauważymy, że adres blockchain pochodzi formalnie z klucza publicznego.

Implementując TSS do blockchain mamy do czynienia z "x" stronami, które wspólnie obliczają klucz publiczny, a każda z nich posiada secret share klucza prywatnego (poszczególne share nie są ujawniane innym stronom). Z klucza publicznego możemy uzyskać adres w taki sam sposób, jak w tradycyjnym systemie, dzięki czemu blockchain pozostaje niezależny od sposobu generowania adresu. Zaletą takiego rozwiązania jest to, iż klucz prywatny przestaje być pojedynczym punktem, który może zawieść (tzw. ang. single point of failure) ponieważ każda ze stron posiada tylko wybraną część tego klucza.

To samo można zrobić przy podpisywaniu transakcji. W tym kontekście transakcja nie jest podpisywana kluczem prywatnym tylko przez jedną stronę. Zamiast tego do jej podpisania wykorzystywany jest proces rozproszonej generacji podpisu w którym bierze udział wiele stron. Tym samym każda ze stron uczestnicząca w procesie jest w stanie wyprodukować (dosłownie) prawidłowy podpis tak długo, jak wystarczająca ilość uczestników procesu działa uczciwie. Ponownie, dzięki TSS obliczenia lokalne (pojedynczy punkt awarii) zamieniane są na obliczenia rozproszone.

Należy również wspomnieć, że proces rozproszonego generowania klucza można wykonać na wiele sposobów, gdzie każdy z nich charakteryzuje się inną strukturą dostępu do danych: najczęściej spotykane ustawienia procesu polegają na zabezpieczeniu procesu przed "t" błędami w obliczaniu klucza prywatnego, bez zmniejszania bezpieczeństwa całego procesu.


TSS vs. Multisig

Niektóre sieci blockchain oferują funkcjonalność TSS jako wbudowaną lub programowalną część swojej sieci. Funkcjonalność ta zazwyczaj nazywana jest multisig lub multi-signature. Aby lepiej zrozumieć różnice, najprościej jest spojrzeć na multisig jako TSS w warstwie aplikacji blockchain.

Innymi słowy, zarówno multisig, jak i TSS zasadniczo próbują osiągnąć podobne cele, ale TSS korzysta z kryptografii poza siecią blockchain, podczas gdy procesy inicjowane przez multisig odbywają się w łańcuchu bloków (w sieci). Co jednak istotne, to fakt, iż sieć blockchain potrzebuje sposobu na zakodowanie multisig, co może zaszkodzić prywatności, ponieważ struktura dostępu (liczba stron uczestniczących w procesie podpisywania) zostaje zapisana i publicznie ujawniona w blockchain. Co więcej, koszt transakcji multisig jest wyższy, ponieważ w sieci muszą również zostać zapisane informacje o wszystkich stronach uczestniczących w procesie podpisywania.

W przypadku TSS dane sygnatariuszy są łączone i zapisywane w formie zwykłej transakcji, co zmniejsza koszty i zapewnia prywatność. Z drugiej strony proces multisig może pozostać nie-interaktywny, co może (ale nie musi) oszczędzić kłopotów z uruchomieniem złożonej warstwy komunikacyjnej między różnymi sygnatariuszami.

Główną różnicą między TSS a Multisig jest to, że multisig jest unikalne dla każdej sieci blockchain i należy go ponownie wdrożyć dla każdej kolejnej sieci. W niektórych przypadkach nie jest też w ogóle obsługiwany. TSS natomiast zbudowany jest na bazie uniwersalnych algorytmów kryptograficznych, dzięki czemu jego obecność w danej sieci jest zawsze możliwa. Świetny artykuł objaśniający różnicę pomięzy TSS i Multisig znajdziesz tutaj.


TSS vs. algorytm Shamir secret sharing scheme

Schemat SSSS (Shamir Secret Sharing Scheme) daje możliwość przechowywania klucza prywatnego w sposób rozproszony - przy czym odnosi się to do sytuacji, kiedy w danym momencie nie jest on używany. Pomiędzy TSS i SSSS występują dwie główne różnice:

  • Generowanie klucza: w przypadku SSSS, za wygenerowanie secret shares dla danego klucza prywatnego odpowiada jedna strona, którą nazwano “the dealer”. Tym samym, w chwili zainicjowania procesu generacji klucza, klucz prywatny generowany jest w jednej lokalizacji, a następnie dystrybuowany do pozostałych lokacji. W przypadku TSS, w rolę dealera wchodzą wszystkie strony zaangażowane w proces generowania klucza - dzięki czemu tworzony jest on w sposób rozproszony - i nigdy nie znajduje się w całości w jednej lokalizacji.

  • Podpisywanie: w przypadku SSSS, każda ze stron musi samodzielnie odtworzyć klucz prywatny, aby móc podpisać jakąkolwiek partię danych, co ponownie powoduje powstanie tzw. pojedynczego punktu awarii za każdym razem, gdy potrzebne jest uzyskanie/wygenerowanie podpisu. W przypadku TSS, proces podpisywania partii danych odbywa się w rozproszony sposób bez konieczności odtwarzania secret shares klucza prywatnego.

Jak więc widać, w TSS klucz prywatny (który generalnie reprezentuje poziom bezpieczeństwa danego systemu) nigdy nie znajduje się w jednym miejscu przez cały okres jego użytkowania.


Portfele Threshold

Portfele wykorzystujące technologię TSS w pewnych aspektach różnią się od tradycyjnych portfeli do przechowywania kryptowalut. W przypadku tradycyjnych portfeli, te na podstawie wygenerowanej seedphrase deterministycznie uzyskują adres do przechowywania środków przez użytkownika. Użytkownik może następnie wykorzystać tę strukturę deterministyczną, aby 1) dotrzeć do kluczy prywatnych, które odpowiadają adresom portfeli i podpisać nimi transakcje w tych portfelach, oraz 2), odzyskać wszystkie klucze dające dostęp do środków w portfelu przy użyciu seedphrase.

W przypadku portfeli typu threshold, nie jest to już tak proste. O ile możliwe jest wygenerowanie struktury HD, jej wygenerowanie musi odbyć się w sposób rozproszony, jako kolejny protokół MPC. Każda ze stron uczestnicząca w tym procesie musi wspólnie z innymi stronami zdecydować, który z kluczy zostanie wykorzystany w następnej kolejności. Innymi słowy, każda ze stron będzie posiadać swój własny seed phrase. Seed phrases są generowane osobno i nigdy nie są ze sobą łączone, dzięki czemu każda ze stron jest w stanie uzyskać klucz prywatny z własnego seeda.

Portfele oparte na TSS charakteryzują się również dodatkową warstwą bezpieczeństwa, która umożliwia zmianę algorytmu generowania klucza prywatnego (ang. public key rotation), bez konieczności całkowitej zmiany klucza publicznego i adresu blockchain do niego przypisanego. Funkcja Private key rotation znana również pod nazwą Proactive Secret Sharing, to nic innego jak kolejny protokół MPC, który na bazie jednej porcji secret shares (w postaci danych wejściowych), generuje nowy zestaw secret shares. Dzięki temu starych (nieaktualnych) secret shares można się pozbyć i bez żadnych problemów korzystać z nowych.

Taka struktura sprawia, że atakujący musi znajdować się w wielu lokalizacjach jednocześnie, aby móc z sukcesem zaatakować portfel typu threshold. Połączenie ze sobą secret shares przed ich "rotacją" z ich odpowiednikami po rotacji nie da atakującemu żadnej dodatkowej korzyści, jeśli będzie on próbował sfałszować podpis.

Minusem tego rodzaju portfeli jest to, że bez posiadania frazy „seed”, Twój portfel staje się niezgodny z portfelami, które wykorzystują system jednokluczowy. Dlatego ważne jest, aby rozważyć, które strony będą w posiadaniu secret shares.

Portfele Threshold mogą występować w kilku różnych rodzajach:

  • Outsoure'ujące TSS: w których użytkownik portfela daje “n” wskazanym serwerom możliwość wykonywania obliczeń w jego imieniu. Dzięki temu proces generowania, zarządzania i podpisywania kluczy jest skutecznie outsource'owany do dostawców usług, którzy nie są właścicielami aktywów, ale zapewniają warstwę bezpieczeństwa w zamian za pewne korzyści.

  • Wykorzystujące wiele urządzeń: w których użytkownik końcowy wykonuje TSS między urządzeniami, których je właścicielem. Dla przykładu - jedna strona będzie jakimś urządzeniem IoT w domu użytkownika, inna strona będzie użytkownikiem mobilnym, kolejna ze stron będzie jego laptopem i tak dalej.

  • Hybrydowym: TSS funkcjonuje w taki sposób, iż niektóre strony są kontrolowane przez zewnętrznych dostawców usług, a niektóre strony działają na urządzeniach należących do użytkowników.

Pierwsza metoda odciąża klienta użytkownika od konieczności wykonywania najcięższych obliczeń. Z drugiej strony dostawcy usług mogą specjalnie się zmawiać, aby wspólnie wykradać aktywa swoich użytkowników (chociaż ciężko wyobrazić sobie scenariusz w którym wystarczająca liczba użytkowników zostanie zaatakowana w tym samym czasie, to w praktyce jest to możliwe).

Druga z metod daje użytkownikowi pełną kontrolę, ale sprawia, że przeprowadzanie transakcji jest uciążliwe, ponieważ potrzeba wielu urządzeń, przejścia do trybu online i zaangażowania się w obliczenia TSS.

Trzecia opcja jest uważana za najlepszą mieszankę plusów i minusów z obu światów, ponieważ zapewnia użytkownikowi łatwy i szybki sposób przeprowadzania transakcji, ale dalej bez możliwości przeprowadzania transakcji bez autoryzacji użytkownika.


TSS i smart kontrakty 

Badacze z dziedziny kryptografii przez wiele lat istnienia TSS znaleźli wiele zastosowań dla podpisów cyfrowych. Niektóre z nich są zaskakująco nietrywialne. Jak już wspomnieliśmy wcześniej, TSS jest algorytmem kryptograficznym niskiego poziomu, który jest w stanie znacząco zwiększyć bezpieczeństwo systemu w którym zostanie zaimplementowany. W przypadku sieci blockchain, można pokusić się o stwierdzenie, iż wiele funkcji dostępnych w tych sieciach można zastąpić kryptografią opartą na TSS. Zdecentralizowane aplikacje, rozwiązania skalujące w ramach tzw. 2 warstwy, atomic swapy, miksowanie środków, inheritance i wiele innych można odtworzyć wykorzystując do tego celu jedynie TSS. Pozwoliłoby to ostatecznie na zastąpienie kosztownych i ryzykownych operacji wykonywanych przy użyciu inteligentnych kontraktów, tańszymi i bardziej niezawodnymi alternatywami.
Aby lepiej zrozumieć tę kwestię posłużmy się przykładami: Multi-Hop Locks, to rozwiązanie, które w sprytny sposób wykorzystuje podpisy-obustronne, co otwiera drogę do wykorzystania ich, jako alternatywy dla rozwiązania Lightning Network z sieci Bitcoin, jako bardziej bezpieczna i prywatna sieć kanałów płatności. ShareLock jest prawdopodobnie najtańszym rozwiązaniem pozwalającym na miksowanie on-chain środków w sieci Ethereum, a które oparte jest na weryfikacji pojedynczej sygnatury progowej.


Zagrożenia

Ostatnie kilka lat w świecie internetu i branży komputerowej zaowocowało znaczącym zwiększeniem ilości rozwiązań w których podjęto się implementacji TSS. Mimo wszystko, TSS jako stosunkowo nowa technologia wciąż ma pewne ograniczenia i niesie za sobą pewne ryzyka. W porównaniu z klasycznymi algorytmami kryptografii kluczy publicznych, protokoły TSS mogą być bardzo złożone i nie zostały jeszcze do końca sprawdzone w "walce". Co więcej, rozwiązania wykorzystujące TSS zazwyczaj wymagają dodatkowych oraz jednocześnie słabszych kryptograficznych założeń w porównaniu do prostych podpisów cyfrowych. W rezultacie co rusz odkrywane są kryptograficzne wektory ataku, które nie istnieją w tradycyjnych konfiguracjach (więcej na ten temat znajdziesz w tej prezentacji z konferencji Breaking Bitcoin 2019). Mimo wszystko odpowiednio wyszkoleni inżynierowie bezpieczeństwa i doświadczeni kryptografowie mogą pomóc w odpowiednio bezpiecznym wdrożeniu TSS do Twojego systemu.

Po pozytywnej stronie natomiast warto wspomnieć o tym, iż co rusz powstają nowe przykłady skutecznych implementacji TSS, co z kolei skutkuje pojawianiem się wielu audytów i propozycji ulepszeń na polu wydajności tego algorytmu.


Przemyślenia końcowe

W tym artykule przedstawiliśmy jedynie podstawy schematu podpisów progowych (TSS), który jest bardzo ciekawym przykładem algorytmu kryptograficznego niskiego poziomu, a który ma moc wprowadzenia istotnych zmian w sposobie w jaki wykorzystujemy technologię blockchain.

Ponieważ w artykule nie omówiliśmy Schematu ECDSA, z którego dobrodziejstw można skorzystać m.in w sieciach Binance Chain i Bitcoin, dla zainteresowanych czytelników podajemy listę dodatkowych źródeł, które mogą pomóc w lepszym zgłębieniu tej tematyki. Ponadto, jeśli zechciałbyś pobawić się kodem niektórych implementacji TSS, to m.in deweloperzy portfela Binance Chain opublikowali jego kod źródłowy który znajdziesz tutaj. Możesz też sprawdzić portfel ZenGo dla Binance Chain, który wykorzystuje metodę hybrydową o której wspominaliśmy wyżej.


Lista dodatkowych i sugerowanych źródeł do przeczytania (w języku angielskim):