Kriptográfiai rendezés a blokkláncokban: a VRF-ek fontossága

Ha a kriptográfia lehet a rendszergazda

A Witnetben folytatott kutatói munkám részeként egyre inkább elolvastam és megértem a blockchain technológiákat, és rájöttem, hogy a kriptográfiai protokollok és sémák fontosak a tervükön. Elképesztő, hogy egy kis tervezési döntés hogyan befolyásolhatja a felhasználók interakcióját a rendszerrel, és potenciálisan kihasználhatják azt.

Ebben a bejegyzésben szeretnék megosztani néhány belső kutatást, amelyet a Witnetnél végeztünk, és arról, hogy rájöttünk, hogy a kriptográfiai feltevések nem voltak elég erősek kezdeti céljainkhoz.

A PoE a Blockchain Protocols részeként

Az alkalmazhatóság igazolása (PoE) egyre népszerűbbé válik a Blockchain technológiában. Valójában a PoE-k lehetőséget adnak nekünk annak eldöntésére, hogy ki felel egy akció végrehajtásáért. Amikor az alkalmasságot az egyes társak külön-külön fedezik fel, általában kriptográfiai válogatási sémaként nevezzük, vagyis arra a képességre, hogy felfedezzük, vajon Ön egy „lottó” nyertese.

Számos olyan tulajdonság létezik, amelyeknek a kriptográfiai osztályozásnak teljesnek kell lennie. Először, a csomópontoknak külön-külön meg kell tudniuk határozni, hogy alkalmasak-e egy adott művelet végrehajtására. Másodszor, a jogosultságot kriptográfiailag ellenőrizni kell más társak által. Harmadszor, a kriptográfiai osztályozás egyetlen azonosítóval van társítva, azaz a társaknak biztosnak kell lenniük abban, hogy a bizonyítékot az azt igénylő társ generálta. Ezenkívül azt is szeretnénk, ha a bizonyítás megkülönböztethetetlen a véletlenszerűtől.

Megfigyeltük, hogy a kriptográfiai osztályozási sémákat a blokklánc-tervezés részeként javasolják, a jól ismert Proof of Work a Bitcoin-től az új javaslatokig, például: Algorand, Filecoin vagy Witnet. Ebben a bejegyzésben a Witnet-ben leírt kriptográfiai osztályozásra és annak lehetséges fejlesztéseire fogom összpontosítani. Remélem, hogy az itt közzétett információk hasznosak más azonos célú blokkláncok számára.

Kriptográfiai rendezés digitális aláírások alapján

Általában a kriptográfiai osztályozási sémák jogosultságukat azon a szerencsén alapítják, hogy véletlenszerű számot kapnak, amely egy adott célérték alá esik. A nehézség nyilvánvalóan a célértéktől függ; minél magasabb az érték, annál több esély van arra, hogy társaik jogosultak legyenek. A célérték valószínűleg eltérő lehet a különböző társaik között, attól függően, hogy mennyire viselkedtek jól az előző feladatok során. Pontosan ezt a megközelítést írta le Witnet. A kriptográfiai osztályozást a Witnet-ben a következőképpen határozza meg:

Kriptográfiai rendezés a Witnet-ben

Ahol <> az M kulcson keresztüli aláírást jelöli, és I az i társaknak a t időtartamra gyakorolt ​​hatására utal. A befolyás a csomópont jó hírnevére utal, azaz hogy mennyire viselkedett jól a korábbi feladatok során. Alapvetõen, ha a társ által elvégzendõ feladat aláírásának kivonása a célérték alá esik, akkor jogosult lesz a feladat végrehajtására. Megfigyeltük, hogy az egyes társak hogyan tudják külön-külön kitalálni a rendezettségüket anélkül, hogy kölcsönhatásba lépnének a hálózat többi társával. A véletlenszerű érték minden társra jellemző (valószínűleg az előző blokk kivonása).

A csomópont alkalmasságának ellenőrzése érdekében a csomópontok többi része először ellenőrizze, hogy az aláírást a megfelelő paraméterekkel generálták-e (az aktuális korszakhoz és a csomópont által kiválasztott feladathoz tartozó véletlenszerű érték). Ezután kivonják az aláírást, hogy kiderítsék, nem esik-e a célérték alá. Ha igen, akkor ellenőrzik a szakértő alkalmasságát a feladatra.

A digitális aláírásokon alapuló kriptográfiai osztályozások (azaz egy adott üzenet aláírása) kitöltik a fenti meghatározásokat: egy adott társ által generáltak, a nyilvános kulcson keresztül ellenőrizhetők, és kimenetük véletlenszerűen jelenik meg a nyilvános kulcs nélkül.

De a digitális aláíráson alapuló kriptográfiai osztályozási rendszerek általában teljesítik (mint a Witnet esetében) egy másik követelményt, amelyet nem említettem: minden egyes társnak egyetlen bejövő üzenethez való jogosultsági felvétellel kell rendelkeznie. Ellenkező esetben a kortársak csak annyiszor futtathatják a lottót, amennyit csak akartak, amíg nem válnak támogathatóvá. A Witnetben feltett kérdésünk az volt, hogy a digitális aláírások tele vannak-e ezzel a tulajdonsággal?

A probléma: az ECDSA nem egyedi kimenete

Mielőtt megválaszolnám az előző kérdést, hadd röviden ismertessem az elliptikus görbe kriptográfia működését.

Dióhéjban az elliptikus görbe kriptográfia (ECC) egy nyilvános kulcsú kriptográfia, amelyben minden társ magán-nyilvános kulcspárt tart. A privát kulcsot csak a tulajdonos ismeri, míg a nyilvános kulcsot minden társ ismeri. A kommunikációs társaiknak először meg kell egyezniük az ECC görbében
fogják felhasználni. A görbe csak egy egyenlet által meghatározott pontok halmaza,
például y ^ 2 = x ^ 3 + ax + b. A görbét egyebek mellett egy generátorpont határozza meg, amelynek köszönhetően a görbe bármely más pontját elérhetjük. Egy ilyen rendszer felépítéséhez az ECC a következő aritmetikát állítja elő:

  • ha P egy pont a görbén, -P a reflexiója az x tengelyen
  • ha két P és Q pont különbözik egymástól, akkor P és Q összeadásának eredménye a következő
    úgy számolva, hogy egy P és Q kereszteződésű vonalat rajzol, amely metszi az a pontot
    harmadik pont - R a görbén. R kiszámításához az −R tükröt vesszük
    az x tengelyhez viszonyítva.
  • A P + P kiszámításához úgy kell megérinteni egy érintő vonalat a P görbenél, amely
    ismét keresztezni fogja a –2P görbe harmadik pontját. A 2P csak a
    visszaverődés az x tengely felett
Elliptikus görbe hozzáadási példa

Vegye figyelembe, hogy ezzel a számtani módszerrel már pontokat is hozzáadhatunk, és ennek következtében szorozzuk meg a pontokat eskalarákkal (az 5P csak 2P + 2P + P). A magán-nyilvános kulcspárt úgy állítjuk elő, hogy először egy véletlenszerű egész számot választunk, amely kiszolgálja nekünk a privát kulcsot. A nyilvános kulcs az egész szám szorzása a generátorponttal. A rendszer biztonsága a nyilvános kulcspontból származó egész szám nehézségein vagy beolvasásán alapul. Ez, figyelembe véve a Q nyilvános kulcsot, az a k egész szám megtalálásának problémája, amely megsokszorozta a generátort, hogy elérje a Q értéket, egyenértékű a diszkrét logaritmus problémával.

Egy ilyen rendszerrel már több kriptográfiai megközelítést is végrehajthat. Az egyik a digitális aláírások generálásának képessége. Az ECDSA szigantura generációjának átfogó képe a következő képen látható

ECDSA aláírás generálása

Lényegében az m bemeneti üzenet először hash. Később az u véletlen számot úgy választják meg, hogy ha megszorozzuk a G generációs ponttal, a görbe egy pontjához térjen el, amelynek x-koordinátája 0. Ha ez a feltétel nem teljesül, akkor az u értéket újra megválasztjuk. Ha igen, akkor az u inverzét megszorozzuk (e + dr) -ig, amíg az érték nem nulla. Az aláírás a gomb (r, s).

Valójában nem kell teljesen megértenünk az algoritmust, hogy felismerjük, hogy az aláírás (r, s) nagymértékben függ az 5. sorban kiválasztott u véletlenszerű értéktől. Ez azt jelenti, hogy az aláírás értéke egy véletlenszerű értéktől függ, ezért egy adott üzenet több különféle aláírásra leképezhető.

Ez már ellentétes azzal, amit ideálisan írtunk le egy kriptográfiai osztályozáshoz. Ha egy társ elfogadhatósága az aláírás hash-jától függ, amely eltérő értékeket vehet igénybe a kiválasztott u véletlenszerű értéktől függően, akkor számíthatunk arra, hogy a társak folyamatosan kiszámítják az aláírásokat, amíg meg nem találják az aláírást, amelyen a hash elegendően alacsony, és így jogosultak lesznek. Érdekes, hogy a felhasznált kriptográfia lehetőséget ad a társaknak a rendszer játékra.

Megoldás: VRF-ek kriptográfiai osztályozásként

Az említett probléma ellenére nem szeretnénk lemondni az összes olyan előnyeről, amelyet a digitális aláírások nyújtanak rendszerünknek. Ezért hozzá kell adnunk az egyediség tulajdonságot a kriptográfiai osztályozásunkhoz, mintha ez egy „kulcsos HMAC nyilvános kulcsú verziója” lenne. Úgy tűnik, hogy az ellenőrizhető véletlenszerű funkciók (VRF) teszik a trükköt (és valójában Algorandban használják őket). A VRF-eket először Silvio Micali vezette be [1]. A VRF-k két kimenetet generálnak: az úgynevezett „egyedi aláírás” β és a π igazolás. A nyilvános kulcsú kriptoszisztéma mellett a következő tulajdonságokkal is rendelkeznek:

  • Ütközésállóság, azaz nehéz két bemenetet megtalálni, amelyek azonos kimenetet képeznek.
  • A pszeudo-véletlenszerűség, azaz a kimenet nem különböztethető meg véletlenszerűen azok közül, akik nem ismerik a titkos kulcsot.
  • Megbízható egyediség, amely megköveteli, hogy adott nyilvános kulcs esetén az m VRF bemenet megfeleljen egy egyedi β kimenetnek.

Az utolsó állítás nagyon fontos. Ez azt jelenti, hogy a β mindig egyedi lesz egy adott bemeneti üzenetnél és egy nyilvános kulcsnál, míg a bizonyítás véletlenszerű lehet. Így a társak nem hozhatnak létre több aláírást, amíg el nem érik a kellően alacsony értéket, mivel ugyanazon bemenet esetén mindig ugyanazt az értéket kapják. Vagyis csak a beérkezett üzenetekenként egyszer futtatják a lottót.

VRF példa

A kérdés természetesen az, hogy ezeket a sémákat hogyan kell felépíteni. Követjük a [2] -ben javasolt sémát, amely leírja a VRF-konstrukciókat mind az RSA, mind az ECC számára. A rövidség kedvéért kihagyjuk az RSA felépítésének leírását. Valójában az ECC titkosítási rendszereknek kínál előnyöket a kulcs és az aláírás méretében az RSA-hoz képest, hogy ugyanazt a biztonságot érjék el.

Az ECC-VRF aláírás-ellenőrző algoritmus az alábbiakban látható. ECVRF_hash_to_curve olyan függvény, amely egész számot mutat a görbe egy pontjához. Éppen ellenkezőleg, az ECVRF_hash_points olyan függvény, amely a görbén több pontot egészre mutat. Ezzel a két kiegészítő funkcióval felépíthetjük a következő aláírás-generációs sémát:

ECC-VRF bizonyíték generáció

A β kimenetet később megismételjük annak ellenőrzésére, hogy a kivonat nem éri-e el a célértéket, míg a π bizonyítékot a hitelesítő használja annak ellenőrzésére, hogy a kimenetet valóban kiszámították-e a társított nyilvános kulcsmal és az adott üzenetre a következő módon:

ECC-VRF-igazolás

Ha megnézzük az algoritmust, akkor és csak akkor, ha c 'egyenlő c értékkel, akkor a bizonyítékot ellenőrizzük. Összevetve a hitelesítés 15. lépését és az aláírás generációjának 4. lépését, láthatjuk, hogy az egyenlőség mindaddig fennmarad, amíg u = Gt és v = Ht. Hitelesítheti-e ezt a hiteles titkos kulcs ismerete nélkül? Az alábbiakban bemutatjuk az egyenlőség helyességét:

  • Az u = Qc + Gs = Qc + G (t-kc) = Qc + Gt-Gkc = Qc + Gt -Qc = Gt érték
  • V = βc + Hs = βc + H (t-kc) = βc + Ht-Hkc = βc + Ht-βc = Ht

Megállapítható, hogy az egyenlőség fennáll-e anélkül, hogy tudnunk kellene a k titkos értéket.

Következtetések

Ebben a bejegyzésben megosztottam azzal, hogy a digitális aláírás alapú kriptográfiai osztályozási rendszerek miért ösztönözhetik egymást a rendszer játékra, különösen akkor, ha tőlük függ a feladatra való alkalmasság. A Witnet esetében mind a bányászat, mind az adatkérés feladatai a rendezés eredményétől függenek, így nem tudunk ilyen ösztönzést nyújtani társaink számára. Elérhetjük azt a helyzetet, amikor az adatkérés jutalma elég magas ahhoz, hogy ösztönözze a társakat arra, hogy folyamatosan alírásokat generálhassanak ahhoz, amíg a hash elegendő nem lesz, így az adatkéréseknél alátámaszthatatlanul befejezhetetlen munkajellemzőt lehet végrehajtani. Valójában, ha a csomópontok minden erőforrást nagylelkű adatkérésre tesznek, akkor a többit elfelejtik, és a rendszer teljesítményét súlyosan érinti.

Az ellenőrizhető véletlenszerű funkciók a fent leírt kérdést megoldják. Valójában megtartják a digitális aláírások összes előnyeit, egy további ténygel: az „aláírás” egy adott nyilvános kulcs és üzenet esetében egyedi. Ezenkívül a VRF-ek előállítják a bizonyítékot, amelynek köszönhetően a hitelesítő ellenőrizheti a tranzakció érvényességét. Így a VRF-ek a megfelelő megközelítésnek tűnnek a Witnethez hasonló rendszerek számára.

Irodalom

  • https://people.csail.mit.edu/nickolai/papers/gilad-algorand-eprint.pdf
  • https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Pseudo%20Randomness/Verifiable_Random_Functions.pdf
  • https://filecoin.io/filecoin.pdf
  • https://witnet.io/static/witnet-whitepaper.pdf
  • https://eprint.iacr.org/2017/099.pdf
  • https://tools.ietf.org/html/draft-irtf-cfrg-vrf-03