úvod
"Generování náhodných čísel je příliš důležité na to, aby bylo ponecháno náhodě."
Robert Cavue, 1970
Tento článek je věnován praktické aplikaci řešení pomocí hromadného generování náhodných čísel v nedůvěryhodném prostředí. Stručně řečeno, jak a proč se náhoda používá v blockchainech, a trochu o tom, jak rozlišit „dobré“ náhodné od „špatného“. Generování skutečně náhodného čísla je extrémně obtížný problém, a to i na jediném počítači, a kryptografové jej dlouho zkoumali. V decentralizovaných sítích je generování náhodných čísel ještě složitější a důležitější.
Právě v sítích, kde si účastníci navzájem nedůvěřují, nám schopnost generovat nezpochybnitelné náhodné číslo umožňuje efektivně vyřešit mnoho kritických problémů a výrazně zlepšit stávající schémata. Hazardní hry a loterie zde navíc nejsou cílem číslo jedna, jak se může nezkušenému čtenáři zprvu zdát.
Generování náhodných čísel
Počítače samy nemohou generovat náhodná čísla, k tomu potřebují pomoc zvenčí. Počítač může získat nějakou náhodnou hodnotu například z pohybu myši, množství použité paměti, bludných proudů na pinech procesoru a mnoha dalších zdrojů nazývaných zdroje entropie. Tyto hodnoty samy o sobě nejsou zcela náhodné, protože jsou v určitém rozmezí nebo mají předvídatelný vzorec změn. Aby se taková čísla změnila na skutečně náhodné číslo v daném rozsahu, jsou na ně aplikovány kryptotransformace, aby se vytvořily rovnoměrně rozložené pseudonáhodné hodnoty z nerovnoměrně rozložených hodnot zdroje entropie. Výsledné hodnoty se nazývají pseudonáhodné, protože nejsou skutečně náhodné, ale jsou deterministicky odvozeny z entropie. Jakýkoli dobrý kryptografický algoritmus při šifrování dat vytváří šifrové texty, které by měly být statisticky nerozeznatelné od náhodné sekvence, takže k vytvoření náhodnosti můžete použít zdroj entropie, který poskytuje pouze dobrou opakovatelnost a nepředvídatelnost hodnot i v malých rozsazích, zbytek práce je rozptýlení a míchání bitů v Výslednou hodnotu převezme šifrovací algoritmus.
Na doplnění stručného vzdělávacího programu dodám, že generování náhodných čísel i na jednom zařízení je jedním z pilířů zajištění bezpečnosti našich dat.Vygenerovaná pseudonáhodná čísla se používají při navazování bezpečných spojení v různých sítích, ke generování kryptografické klíče, pro vyvažování zátěže, monitorování integrity a pro mnoho dalších aplikací. Bezpečnost mnoha protokolů závisí na schopnosti vygenerovat spolehlivý, zvenčí nepředvídatelný náhodný soubor, uložit jej a neodhalit jej až do dalšího kroku protokolu, jinak bude bezpečnost ohrožena. Útok na generátor pseudonáhodných hodnot je extrémně nebezpečný a bezprostředně ohrožuje veškerý software, který generování náhodnosti využívá.
To vše byste měli vědět, pokud jste absolvovali základní kurz kryptografie, pojďme tedy pokračovat o decentralizovaných sítích.
Náhodné v blockchainech
Nejprve budu hovořit o blockchainech s podporou chytrých kontraktů, právě ty dokážou naplno využít příležitostí, které poskytuje kvalitní, nepopiratelná náhodnost. Dále, pro stručnost, budu tuto technologii nazývat „Veřejně ověřitelné náhodné majáky“ nebo PVRB. Vzhledem k tomu, že blockchainy jsou sítě, ve kterých může informace ověřit kterýkoli účastník, klíčová část názvu je „Veřejně ověřitelné“, tzn. Kdokoli může použít výpočty k získání důkazu, že výsledné číslo zveřejněné na blockchainu má následující vlastnosti:
- Výsledek musí mít prokazatelně rovnoměrné rozložení, tedy být založen na prokazatelně silné kryptografii.
- Není možné ovládat žádný z bitů výsledku. V důsledku toho nelze výsledek předem předvídat.
- Protokol generování nemůžete sabotovat tím, že se nebudete na protokolu podílet nebo že přetížíte síť útočnými zprávami
- Vše výše uvedené musí být odolné vůči tajné dohodě s přípustným počtem nepoctivých účastníků protokolu (například 1/3 účastníků).
Jakákoli možnost tajné dohody menší skupiny účastníků vytvořit i kontrolovanou sudou/lichou náhodu je bezpečnostní dírou. Jakákoli schopnost skupiny zastavit vydávání náhodných je bezpečnostní dírou. Obecně existuje mnoho problémů a tento úkol není snadný...
Zdá se, že nejdůležitější aplikací pro PVRB jsou různé hry, loterie a obecně jakýkoli typ hazardu na blockchainu. Ve skutečnosti je to důležitý směr, ale náhodnost v blockchainech má ještě důležitější aplikace. Pojďme se na ně podívat.
Konsensuální algoritmy
PVRB hraje obrovskou roli při organizování konsenzu sítě. Transakce v blockchainech jsou chráněny elektronickým podpisem, takže „útok na transakci“ je vždy zahrnutí/vyloučení transakce do bloku (nebo několika bloků). A hlavním úkolem konsensuálního algoritmu je dohodnout se na pořadí těchto transakcí a pořadí bloků, které tyto transakce zahrnují. Nezbytnou vlastností pro skutečné blockchainy je také finalita – schopnost sítě souhlasit s tím, že řetězec až po dokončený blok je konečný a nikdy nebude vyloučen kvůli vzhledu nového forku. Obvykle je pro odsouhlasení platnosti bloku, a hlavně konečného, nutné shromáždit podpisy od většiny výrobců bloků (dále jen BP - block-producers), což vyžaduje alespoň dodání blokového řetězce. všem BP a distribuci podpisů mezi všemi BP. S rostoucím počtem BP roste exponenciálně i počet potřebných zpráv v síti, proto konsenzuální algoritmy, které vyžadují konečnost, používané například v Hyperledger pBFT konsensu, nepracují požadovanou rychlostí, počínaje několika desítkami BP, které vyžadují obrovské množství spojení.
Pokud v síti existuje nepopiratelný a poctivý PVRB, pak i v nejjednodušším přiblížení lze na jeho základě vybrat jednoho z výrobců bloků a jmenovat jej „vedoucím“ během jednoho kola protokolu. Pokud máme N výrobců bloků, z toho M: M > 1/2 N jsou čestní, necenzurují transakce a nerozdvojují řetězec, aby provedl útok „dvojité útraty“, pak použití jednotně distribuovaného nenapadeného PVRB umožní s pravděpodobností vybrat čestného vůdce M / N (M / N > 1/2). Pokud je každému vůdci přidělen vlastní časový interval, během kterého může vytvořit blok a ověřit řetězec, a tyto intervaly jsou stejné v čase, pak bude blokový řetězec poctivých BP delší než řetězec tvořený zlomyslnými BP a konsensus Algoritmus spoléhá na délku řetězce. Jednoduše zahodí ten „špatný“. Tento princip přidělování stejných časových úseků každému BP byl poprvé aplikován v Graphene (předchůdce EOS) a umožňuje uzavřít většinu bloků jediným podpisem, což výrazně snižuje zatížení sítě a umožňuje, aby tento konsenzus fungoval extrémně rychle a stále. Síť EOS však nyní musí používat speciální bloky (Last Irreversible Block), které jsou potvrzeny podpisy 2/3 BP. Tyto bloky slouží k zajištění definitivnosti (nemožnost startu řetězové vidlice před posledním Posledním nevratným blokem).
Také v reálných implementacích je schéma protokolu složitější - hlasování o navrhovaných blocích se provádí v několika fázích, aby se síť udržela v případě chybějících bloků a problémů se sítí, ale i když to vezmeme v úvahu, konsensuální algoritmy využívající PVRB vyžadují výrazně méně zpráv mezi BP, což umožňuje jejich rychlejší provádění než tradiční PVFT, nebo jeho různé modifikace.
Nejvýznamnější představitel těchto algoritmů: z týmu Cardano, což je prý matematicky prokazatelné proti tajné dohodě BP.
V Ouroboros se PVRB používá k definování takzvaného „rozvrhu BP“ – rozvrhu, podle kterého je každému BP přidělen vlastní časový úsek pro publikování bloku. Velkou výhodou použití PVRB je naprostá „rovnost“ BP (podle velikosti jejich bilancí). Integrita PVRB zajišťuje, že zlomyslní BP nemohou kontrolovat plánování časových slotů, a proto nemohou manipulovat s řetězcem tím, že předem připraví a analyzují vidlice řetězce, a pro výběr vidlice se stačí spolehnout na délku řetěz, bez použití složitých způsobů výpočtu „užitečnosti“ BP a „hmotnosti“ jeho bloků.
Obecně platí, že ve všech případech, kdy je třeba v decentralizované síti vybrat náhodného účastníka, je téměř vždy nejlepší volbou PVRB, spíše než deterministická možnost založená například na blokovém hashe. Bez PVRB vede možnost ovlivnit volbu účastníka k útokům, ve kterých si útočník může vybrat z více futures, aby si vybral dalšího zkorumpovaného účastníka, nebo z několika najednou, aby si zajistil větší podíl na rozhodování. Použití PVRB tyto typy útoků diskredituje.
Škálování a vyvažování zátěže
PVRB může být také velkým přínosem v úkolech, jako je snižování zátěže a škálování plateb. Pro začátek má smysl se s tím seznámit Rivesta „Elektronické losy jako mikroplatby“. Obecná myšlenka je, že namísto provádění plateb 100 1c od plátce příjemci můžete hrát poctivou loterii s výhrou 1 $ = 100 c, kde plátce dává bance jeden ze 1 svých „losovacích tiketů“ za každého. 100c platba. Jeden z těchto tiketů vyhrává sklenici 1 dolaru a právě tento tiket může příjemce zaznamenat do blockchainu. Nejdůležitější je, že zbývajících 99 tiketů je převedeno mezi příjemcem a plátcem bez jakékoli vnější účasti, soukromým kanálem a libovolnou požadovanou rychlostí. Lze si přečíst dobrý popis protokolu založeného na tomto schématu na síti Emercoin .
Toto schéma má několik problémů, například příjemce může přestat obsluhovat plátce ihned po obdržení výherního tiketu, ale u mnoha speciálních aplikací, jako je minutová fakturace nebo elektronické předplatné služeb, mohou být tyto zanedbané. Hlavním požadavkem je samozřejmě férovost loterie a pro její realizaci je PVRB naprosto nezbytný.
Volba náhodného účastníka je také extrémně důležitá pro protokoly shardingu, jejichž účelem je horizontálně škálovat blokový řetězec, což umožňuje různým BP zpracovávat pouze jejich rozsah transakcí. Jedná se o extrémně obtížný úkol, zejména pokud jde o bezpečnostní problémy při slučování shardů. Úkolem PVRB je také spravedlivý výběr náhodného BP za účelem přiřazení osob odpovědných za konkrétní fragment, jako v konsensuálních algoritmech. V centralizovaných systémech přiděluje shardy balancer, ten hash jednoduše vypočítá z požadavku a odešle ho požadovanému exekutorovi. V blockchainech může možnost ovlivnit toto přiřazení vést k útoku na konsenzus. Například obsah transakcí může ovládat útočník, může kontrolovat, které transakce jdou do jím ovládaného shardu a manipulovat s řetězcem bloků v něm. Můžete si přečíst diskuzi o problému používání náhodných čísel pro shardovací úkoly v Ethereu
Sharding je jedním z nejambicióznějších a nejzávažnějších problémů v oblasti blockchainu, jeho řešení umožní budovat decentralizované sítě fantastického výkonu a objemu. PVRB je jen jedním z důležitých bloků k jeho řešení.
Hry, ekonomické protokoly, rozhodčí řízení
Role náhodných čísel v herním průmyslu je těžké přeceňovat. Explicitní použití v online kasinech a implicitní použití při výpočtu účinků hráčské akce, to všechno jsou extrémně složité problémy pro decentralizované sítě, kde neexistuje způsob, jak se spolehnout na centrální zdroj náhodnosti. Ale náhodný výběr může také vyřešit mnoho ekonomických problémů a pomoci vytvořit jednodušší a efektivnější protokoly. Předpokládejme, že v našem protokolu jsou spory o platbách za některé levné služby a tyto spory se vyskytují poměrně zřídka. V tomto případě, pokud existuje nesporný PVRB, se zákazníci a prodejci mohou dohodnout na řešení sporů náhodně, ale s danou pravděpodobností. Například s 60% pravděpodobností vyhraje klient a se 40% vyhraje prodejce. Tento na první pohled absurdní přístup umožňuje automaticky řešit spory s přesně předvídatelným podílem výher/proher, což vyhovuje oběma stranám bez jakékoli účasti třetí strany a zbytečné ztráty času. Kromě toho může být poměr pravděpodobnosti dynamický a závisí na některých globálních proměnných. Pokud se například firmě daří, má nízký počet sporů a vysokou ziskovost, může firma automaticky posunout pravděpodobnost vyřešení sporu směrem k orientaci na zákazníka, například 70/30 nebo 80/20 a naopak. pokud spory stojí hodně peněz a jsou podvodné nebo nedostatečné, můžete posunout pravděpodobnost opačným směrem.
Velké množství zajímavých decentralizovaných protokolů, jako jsou registry spravované tokeny, predikční trhy, spojovací křivky a mnoho dalších, jsou ekonomické hry, ve kterých je dobré chování odměňováno a špatné je penalizováno. Často obsahují bezpečnostní problémy, kvůli kterým jsou ochrany ve vzájemném konfliktu. To, co je chráněno před útokem „velryb“ s miliardami tokenů („velký podíl“), je zranitelné vůči útokům tisíců účtů s malými zůstatky („sybil stake“) a opatřením přijatým proti jedinému útoku, např. lineární poplatky vytvořené proto, aby byla práce s velkým podílem nerentabilní, jsou obvykle zdiskreditovány jiným útokem. Vzhledem k tomu, že mluvíme o ekonomické hře, lze předem vypočítat odpovídající statistické váhy a jednoduše nahradit provize náhodnými s příslušným rozdělením. Takové pravděpodobnostní provize jsou implementovány extrémně jednoduše, pokud má blockchain spolehlivý zdroj náhodnosti a nevyžadují žádné složité výpočty, což ztěžuje život jak velrybám, tak sybilám.
Zároveň je nutné mít stále na paměti, že kontrola nad jediným bitem v této náhodnosti umožňuje podvádět, snížit a zvýšit pravděpodobnosti na polovinu, takže poctivý PVRB je nejdůležitější složkou takových protokolů.
Kde najít tu správnou náhodu?
Teoreticky spravedlivý náhodný výběr v decentralizovaných sítích činí téměř každý protokol prokazatelně bezpečným proti tajné dohodě. Zdůvodnění je celkem jednoduché – pokud se síť shodne na jediném 0 nebo 1 bitu a méně než polovina účastníků je nepoctivá, pak je při dostatečném počtu opakování zaručeno, že síť dosáhne shody na tomto bitu s pevnou pravděpodobností. Jednoduše proto, že poctivý náhodný výběr vybere 51 ze 100 účastníků v 51 % případů. Ale to je teoreticky, protože... v reálných sítích je pro zajištění takové úrovně zabezpečení jako v článcích vyžadováno mnoho zpráv mezi hostiteli, komplexní víceprůchodová kryptografie a jakákoliv komplikace protokolu okamžitě přidává nové útočné vektory.
Proto zatím v blockchainech nevidíme osvědčený odolný PVRB, který by byl dostatečně dlouho používán na to, aby byl otestován reálnými aplikacemi, vícenásobnými audity, zátěžemi a samozřejmě reálnými útoky, bez kterých je těžké zavolat produkt skutečně bezpečný.
Slibných přístupů je však několik, liší se v mnoha detailech a jeden z nich problém určitě vyřeší. S moderními výpočetními prostředky lze kryptografickou teorii docela chytře převést do praktických aplikací. V budoucnu si rádi popovídáme o implementacích PVRB: nyní jich je několik, každá má svou vlastní sadu důležitých vlastností a implementačních vlastností a za každou se skrývá dobrý nápad. Týmů, které se účastní randomizace, není mnoho a zkušenost každého z nich je pro všechny ostatní nesmírně důležitá. Doufáme, že naše informace umožní ostatním týmům postupovat rychleji s přihlédnutím ke zkušenostem jejich předchůdců.
Zdroj: www.habr.com