Vezetőválasztás a Randomness Beacons-ból és más stratégiákból

A vezetőválasztás blokklánc-beállításban annak a résztvevőnek a kiválasztása, aki meghatározza a következő blokkot, amelyet a blokklánchoz kell csatolni. Általában slotonként egy érvényesítőt választanak ki az érvényesítők készletéből, és megkapja a jogot a lánc meghosszabbítására egy új blokkkal az adott slotban. (Feltételezzük, hogy az érvényesítők pontos időt tartanak, és megegyeznek az aktuális résszámban.) Ebben a cikkben a stratégiákat vizsgáljuk meg véletlenszerű vezetőválasztás konszenzusos protokollokban. (A véletlenszerűségről általában lásd korábbi cikkünket, Nyilvános véletlenszerűség és véletlenszerűség jeladói, Ahol önálló protokollokat vizsgáltunk a nyilvánosan ellenőrizhető és előre nem látható véletlenszerűségek generálására.) 

Miért fontos a vezetőválasztás?

A becsületes és aktív vezetők megválasztása kulcsfontosságú a lánc egészséges növekedéséhez. A rosszindulatú érvényesítők nem képesek torzítani a vezetőválasztási folyamatot, hogy gyakrabban váljanak vezetővé. Ellenkező esetben a blokkok gyártása olyan felek kezébe kerülhet, akik cenzúrázhatják a tranzakciókat, vagy teljesen leállíthatják a blokkláncot. A leghosszabb lánc típusú konszenzusos protokollokban az érvénytelen blokkot (vagy egyáltalán nem blokkot) létrehozó vezető a lánc ideiglenes elágazását okozhatja. A BFT-stílusú konszenzusos protokollokban a rossz vezető egy nézetmódosítási alprotokollt indít el, amely kommunikációs többletköltséggel jár. 

A bizottsági választási alternatíva

Ehhez kapcsolódó probléma a bizottságválasztás, ahol a cél a validátorok valamilyen fix méretű, egységesen véletlenszerű részhalmazának kiválasztása k. Ez a funkció önmagában is hasznos, mert a blokklánc-beállításokban gyakran szükség van albizottságokra, hogy csökkentsék az érvényesítő készlet méretét, hogy a konszenzus gyorsabban futhasson (többek között pl. Algorand rendezése és a Az Ethereum bizottságának kiválasztása). De a bizottsági választás a vezetőválasztásnál is hasznos, lehetővé téve az érvényesítőknek, hogy elkerüljék a vezetőválasztási jegyzőkönyv újrafuttatását, ha a megválasztott vezető nem jelenik meg. Ha a vezető helyett fix sorrendben választanak bizottságot, akkor a második bizottsági tag lehet vezető, ha az első nem áll rendelkezésre. 

A jó választási jegyzőkönyv tulajdonságai

A vezetőválasztási protokollban a vezetőknek kiszámíthatatlannak kell lenniük. Ha egy támadó megtudja, ki a következő vezető, szolgáltatásmegtagadási (DoS) támadást indíthat ellene, hogy megakadályozza, hogy blokkot tegyen közzé. A támadó ezután leszedheti a következő vezetőt, és így tovább, leállítva a blokkláncot. A kiszámíthatatlanság is erősíthető annak biztosítására, hogy maga az érvényesítő ne tanulja meg, mikor fog vezetni, ami fontos lehet a megvesztegetés megelőzése szempontjából.

A vezetőválasztási folyamatnak a következő három tulajdonsággal kell rendelkeznie:

• Méltányosság: minden becsületes érvényesítőnek 1/ a valószínűségeN halmazából kell megválasztani N validátorok (egy laza felfogás a játékelméleti tisztesség megengedi vezetőválasztás kiépítése még rosszindulatú többség jelenlétében is, bár a fordulók számának nem állandó alsó korlátja mellett).
• Kiszámíthatatlanság: az ellenfél csak egy ideig tanulja meg a következő vezetőt T mielőtt a vezető bejelenti a következő blokkot.
• egyediség: minden nyílásban pontosan egy vezető kerül kiválasztásra.

Titkos vezetőválasztás

A titkos vezetőválasztás egy kiszámíthatatlan választás T = 0. Ebben a folyamatban a vezetőt senki sem ismeri, amíg nem publikálja a blokkot. Ez teljesen kiküszöböli a DoS támadások ablakát: mielőtt a vezető felfedné magát, a támadó nem tudja, kit támadjon, így a legjobb stratégiája egy véletlenszerű találgatás. És miután a vezető közzétette a blokkját, már késő támadni, mert a vezető már teljesítette a protokoll iránti felelősségét. 

Az „miután a vezető közzéteszi a blokkját” fogalma azonban valójában leegyszerűsítés, mivel a való világban nincs azonnali adás. Előfordulhat, hogy egy erős hálózati pozícióval rendelkező támadó észrevesz egy vezetőt, aki először egy blokkot sugároz, és gyorsan megronthatja a vezetőt, létrehozhat egy másik blokkot, és előre futtathatja az eredeti adást. 

Bár ez egy nagyon erős támadómodell, védekezést javasoltak ellene. Algorand javasolta a törlési modell, amelyben a vezető valóban képes törölni a blokk aláírásához szükséges kulcsot a slotjában előtt közvetíteni, így már tényleg túl késő támadni, mire a vezető nyilvánosan intézkedik. Thaddeus Dryja, Quanquan C. Liu és Neha Narula, az MIT Media Lab három kutatója, javasolt hogy a vezető számítson ki egy VDF-et a blokkon a sugárzás előtt, biztosítva, hogy az adaptív támadó ne tudjon időben létrehozni egy alternatív érvényes blokkot ahhoz, hogy elfogadja azt a kívánt helyhez.

Egyéb választási módszerek 

A vezetőválasztás legegyszerűbb folyamata az kerek vörösbegy, ahol a vezetőket determinisztikus sorrendben választják meg. Annak ellenére, hogy ez a megközelítés kiszámítható, és így hajlamos a DoS támadásokra, alkalmas olyan engedélyezett rendszerekre, ahol az érvényesítők jó DoS védelemmel rendelkeznek.

Vezetőt külső személy kimenetelével is meg lehet választani véletlenszerűség jeladója, ha elérhető, és megbízható, hogy biztonságos. Sajnos a konszenzus résztvevői számára trükkös, hogy maguk futtassák le az elosztott véletlenszerűségi jeladó (DRB) protokollt, mivel ezek jellemzően a megbízható sugárzás vagy konszenzus fogalmát feltételezik, ami viszont ismét vezetőválasztást igényel, ami egy körkörös függőséget hoz létre.

Jelenlegi vezetőválasztás az Ethereumban egy jó esettanulmány. Minden új vezető kiszámítja a Verifiable Randomness Function (VRF) kimenetet (egy BLS aláírást az epocha számon), és XOR-beírja az értéket a keverékbe. A keverék értéke a korszak végén i meghatározza a vezetőket és az albizottságokat a korszak időtartamára i+2. A vezetők és ütemtervük egy korszakra előre megjósolható (jelenleg ~6.4 perc). A protokoll hajlamos a méltányossági támadásokra, mivel az utolsó vezető dönthet úgy, hogy közzéteszi vagy visszatartja hozzájárulását a keverékhez, és így egy kicsit befolyásolja a következő választások eredményét. Ha az utolsó  k a vezetők összejátszanak, bevezethetik k  elfogultság, és valószínűbbé teszi a rosszindulatú felhasználók megválasztását. Az Ethereum Alapítvány aktívan dolgozik a vezetőválasztás fejlettebb technikáin, amelyeket alább tárgyalunk.

VRF-alapú vezetőválasztás

Egy másik megközelítés, úttörője Algorand, Egy VRF-alapú vezetőválasztás, amely azt jelenti, hogy minden érvényesítő magántulajdonban számít ki egy VRF kimenetet, és ellenőrzi, hogy a kimenet egy küszöb alá esik-e. Ez az eljárás már kiszűri a legtöbb érvényesítőt, mivel a küszöböt úgy választják meg, hogy az alá esni nem valószínű. A fennmaradó néhány érvényesítő felfedi a VRF-kimeneteit, és a legalacsonyabb VRF-értékkel rendelkezőt választják. Ez a megközelítés tökéletes kiszámíthatatlanságot (vagy titkosságot) ér el, de nem garantálja az egyediséget. Előfordulhat, hogy egyes érvényesítők nem kapnak üzeneteket az összes potenciális vezetőtől, és feltételezhetik, hogy a rossz vezető nyerte meg a választást, aminek következtében ezek az érvényesítők kiszakadnak a főláncból. 

A VRF-kiértékelést időszakonként egy véletlenszerűségi jeladó kimenetével töltik be, hogy maguk az érvényesítők kevésbé tudják megjósolni, hogy melyik réseket vezetik. Ez a tulajdonság megakadályozza, hogy az érvényesítőt csendben kompromittáló támadó megtanulja a slotot, amikor az érvényesítő vezetővé válna, és támadást indítson, amikor az érvényesítő blokkot készül bejelenteni. Ez a megközelítés segít megelőzni a megvesztegetési támadásokat is, amikor a validátor bizonyítja külső feleknek, hogy vezető szerepet tölt be egy adott résben, és kenőpénzt szed azért cserébe, hogy vezetőként végrehajtson valamilyen feladatot (pl. tranzakció blokkolása).

Az ilyen megközelítéseket, ahol a megválasztott vezetők száma egy valószínűségi változó, nevezzük Valószínűségi vezérválasztás (PLE). A PLE azt eredményezheti, hogy egy adott helyre nem választanak vezetőt. Ez egyenértékű egy rosszindulatú vagy offline vezető megválasztásával, mivel a slotot végül kihagyják, csökkentve a konszenzusos protokoll hatékonyságát.

De a legnagyobb figyelmeztetés a PLE-vel kapcsolatban az, hogy több vezetőt is megválasztanak, ami szükségessé tesz valamiféle döntetlent. A kötelékek kockázatot jelentenek a konszenzus szempontjából, mivel egy győztes bemenettel rendelkező validátor csak a hálózat felének jelentheti azt, ami nézeteltérést okozhat a kiválasztott vezetőben. Ezenkívül a kapcsolatok megoldásának folyamatai több időt és kommunikációt igényelhetnek, ami rontja a hatékonyságot. Dfinitycímű fejezetben részletesebben tárgyaljuk az első poszt ebből a sorozatból VRF-alapú véletlenszerű jeladót használ egyetlen vezető megválasztásához; a kiszámíthatatlanságot azonban feláldozza azért. Ideális esetben minden vezetőválasztási folyamatnak teljesen kerülnie kell a kötelékeket, és továbbra is kiszámíthatatlannak kell lennie, ami elvezet bennünket e kutatási terület szent gráljához – az Egyetlen titkos vezetőválasztáshoz.

Egyetlen titkos vezető választás 

A cél Egyetlen titkos vezető választás (SSLE) célja, hogy egy egyedi vezetőt válasszunk ki az érvényesítők sorából, miközben megőrizzük a méltányosságot és a kiszámíthatatlanságot. A Protocol Labs az elképzelést a kutatási problémaés Dan Boneh, a stanfordi informatikus és a16z kriptográfiai kutatási tanácsadó, valamint Saba Eskandarian, Lucjan Hanzlik és Nicola Greco, később felajánlották az SSLE formális meghatározása. Ezzel az egyediségi tulajdonsággal elkerülhető a konszenzus kockázata és a hatékonysági költségek, amelyek a döntetlen eljárásokból erednek. Konkrétan Sarah Azouvi, a Protocol Labs és Danielle Cappelletti, Politecnico di Torino, előadás hogy ha SSLE-t használnak a PLE-hez képest egy leghosszabb láncú protokollban, a blokkok lényegesen gyorsabban véglegesíthetők (25 százalékkal gyorsabban, ha egy ellenfél a tét egyharmadát irányítja). Így egy praktikus SSLE protokoll kidolgozása fontos probléma.

A legelterjedtebb megközelítésben, amelyet úgy fogunk hívni keverés alapú (az eredeti SSLE papíron és a egy Ethereum SSLE javaslat), minden érvényesítő regisztrál a pápai követ véletlenszerűnek tűnik, de bebizonyíthatják, hogy hozzájuk tartozik. A nonces-ek ezután listába kerülnek. A listát úgy keverjük össze, hogy a nonces-ek elválasszanak az azokat benyújtó érvényesítőktől; vagyis a megkevert lista ismeretében egyetlen ellenfél sem tudja megmondani, hogy melyik érvényesítő melyik nonce-t nyújtotta be. Ezután egy lista indexet választanak ki a nyilvánosság szerint véletlenszerűség jeladója, és a vezető felfedi magát azzal, hogy bebizonyítja, hogy a kevert lista azon indexében lévő nonce hozzájuk tartozik. 

Mivel csak egy index van kiválasztva, a keverés alapú protokoll mindig a egyedi vezető. Mivel a véletlenszerű jeladó egyenletesen véletlenszerű értékeket ad ki, a protokoll is az igazságos: minden érvényesítőnek egyenlő esélye van a megválasztásra. Továbbá, ha a keverés megfelelően történik (azaz egyenletesen véletlenszerűen), és a nonces-ek összekapcsolhatatlanokká válnak az érvényesítő személyazonosságaival, ez a protokoll azt is eléri, kiszámíthatatlanság.

Keverésre azért van szükség, mert bár pusztán egy index kiválasztása a nem kevert listából véletlenszerű jeladó alapján már egyediséget és méltányosságot adna, a kiszámíthatatlanságot nehezebb elérni: Ha az ellenfél tudja, melyik érvényesítő melyik nonce-t nyújtotta be, akkor tudja, hogy ki küldte be a nonce-t a kiválasztottnál. index, és azonosítani tudja a vezetőt. 

A következő két megközelítés különböző módon keveri a listát. Az egyszerűbb a Ethereum SSLE javaslat, amiben n Az érvényesítők a Toron keresztül küldik el noncess-eiket, hogy szétválasztsák az érvényesítők identitását a nonces-ektől. Miután az összes érvényesítő regisztrált, a listát egy nyilvános véletlenszerű jeladó segítségével megkeverik, és az érvényesítők a megkevert lista sorrendjében vezetőkké válnak. Bár ez a rendszer praktikus, a választást csak egyszer kell lebonyolítani n slot – ez a Tor-ra támaszkodás nemkívánatos lehet (mint minden külső protokoll biztonságára való támaszkodás esetén). Ráadásul nem is tökéletesen kiszámíthatatlan: az első után n-1 vezető felfedi magát, a döntő nth vezető ismert.

A Tor használata helyett az eredeti SSLE papíron minden érvényesítő sorban szerepel a választáshoz úgy, hogy a nonce-t hozzáfűzi a listához, megkeveri a listát, és újra véletlenszerűvé tétele a nonces. Ez az újrarandomizálás azt jelenti, hogy minden nonce egy új, nem összekapcsolható karakterláncra van leképezve, így az érvényesítő, akihez tartozik, továbbra is igazolni tudja az újra véletlenszerűen kiválasztott nonce tulajdonjogát. Az újravéletlenszerűsítés lehetővé teszi, hogy az ellenfél ne tudja megmondani, melyik nonce melyik pozícióba került a keverés után, feltételezve, hogy legalább egy keverő őszinte.

Bár ez az eredeti SSLE-papírból származó szekvenciális keverési megközelítés elkerüli a Tor-ra támaszkodást, és eléri az SSLE formális tulajdonságait, költséges: valahányszor új érvényesítő regisztrál, a teljes kevert listát el kell küldenie a blokkláncra, újra véletlenszerűvé kell tennie az összes hiányosságot, és bizonyítja, hogy ezt őszintén tették, ami lineáris kommunikációt eredményez validátoronként. Változatlan érvényesítőkészlet mellett ezt választásonként egyszer kell megtenni (amortizálni), mivel a vezető újra regisztrál, miután felfedte a nonce bizonyítékát. A papír egy hangolható hatékonyság-jósolhatóság kompromisszumot ad: ehelyett a listának csak egy kisebb részhalmazát keverhetjük meg, csökkentve ezzel a költségeket, ha hajlandóak vagyunk egy kis kiszámíthatóságra. A hatékonyság és a biztonság közötti jó egyensúly megteremtése kihívást jelent, és ennek eredményeként az SSLE-protokollokat a gyakorlatban még széles körben alkalmazni kell. 

Kényelmes módon ez a szekvenciális keverési megközelítés a bizottsági választási probléma megoldására is használható, ha a véletlenszerű jeladó segítségével k különálló indexet választunk ki a listáról bizottsági tagként. Ez szép eredmény, mivel a problémát nem triviálisan oldják meg a VRF-alapú megközelítések, mivel egy valószínűségi VRF-alapú protokollt futtatnak. k alkalommal a véletlenszerűségtől függően eltérő méretű bizottságot választhatnak. 

Az SSLE egyéb megközelítései

Egy másik keverés alapú megközelítés az Adaptívan biztonságos SSLE a DDH-tól. Ez a konstrukció valamivel bonyolultabb, de a biztonság erősebb fogalmát éri el, védve az an alkalmazkodó ellenfél az Algorand-féle törlési modellben. Ez az ellenfél adaptív abban az értelemben, hogy kiválaszthatja, hogy mely érvényesítőket rontsa meg a protokoll alatt, nem pedig a protokoll indulása előtt. 

Az SSLE további kihívása az, hogy minden validátort a tétjükkel arányos valószínűséggel kell megválasztani, nem pedig egységesen véletlenszerűen. A keverés alapú protokollok ezt naivan úgy érhetik el, hogy lehetővé teszik minden érvényesítőnek, hogy több nonce-t regisztráljon: egy nonce-t minden egyes birtokolt tétegységhez. A keverés költsége azonban lineárisan növekszik a tétegységek számával S, még a reális tételosztások esetén is nagyon drágává válik. Egy elegáns MPC-alapú SSLE A megközelítés bonyolultsága csak a naplóval növekszik S, és elkerüli a megbízható beállítás vagy véletlenszerű jeladó szükségességét. A keverés alapú megközelítésekhez képest azonban több kommunikációs kört igényel (a résztvevők számában logaritmikus) választott vezetőnként.

***

Elemzésünket ebben a praktikus táblázatban foglaltuk össze.

	Méltányosság	Kiszámíthatatlanság/ Titoktartás*	egyediség
Körmérkőzés	✓	✗	✓
Ideális véletlenszerűség-jelző	✓	✗	✓
Az Ethereum vezetőválasztása (jelenlegi)	✗	✗	✓
VRF-alapú vezetőválasztás (Algorand)	✓	✓	✗
SSLE	✓	✓	✓

* A körbefutó jeladó teljesen kiszámítható, de a többi jelzőfényben ✗ azt jelenti, hogy a fogalom bizonyos korlátozott mértékig teljesül: az ideális véletlenszerűség jeladója megjósolhatatlan, de az ellenfél a megválasztott vezetővel egy időben tanulja meg a kimenetet, így a megválasztott vezetőt megtámadhatják, mielőtt blokkot jelentene be; Az Etherum jeladója ~6 percig kiszámíthatatlan, és enyhén torzíthat, hogy sértse az igazságosságot; Algorand kis valószínűséggel több vezetőt választ.

Az SSLE ígéretes irány, amely méltányosságot, kiszámíthatatlanságot és egyediséget biztosít. Az elfogadása előtt álló két szembetűnő kihívás a hatékonyság és a nem egységes tételosztások befogadásának képessége. Továbbá az általunk kiemelt keverés alapú SSLE megközelítések egy elfogulatlan véletlenszerű jeladó létezését feltételezik, ami a gyakorlatban nem egyszerű megvalósítani. Mivel az SSLE-t formálisan csak a közelmúltban határozták meg, valószínűleg a közeljövőben olyan továbbfejlesztett protokollokat fogunk látni, amelyek megfelelnek a kihívásoknak. 

***

Miranda Christ a Columbia Egyetem számítástudományi PhD hallgatója, ahol az elméleti csoport tagja és elnöki ösztöndíjas. Emellett kutatógyakornok az a16z crypto-nál.

Joseph Bonneau az a16z crypto kutatási partnere. Kutatásai az alkalmazott kriptográfiára és a blokklánc biztonságra összpontosítanak. Tanított kriptovaluta kurzusokat a Melbourne-i Egyetemen, a New York-i Egyetemen, a Stanfordon és a Princetonon, PhD fokozatot szerzett számítástechnikából a Cambridge-i Egyetemen és BS/MS fokozatot a Stanfordon.

Valeria Nikolaenko az a16z crypto kutatási partnere. Kutatásai a kriptográfiára és a blokklánc biztonságra összpontosítanak. Olyan témákkal is foglalkozott, mint a hosszú távú támadások a PoS konszenzus protokollokban, az aláírási sémák, a kvantum utáni biztonság és a többoldalú számítás. A Stanford Egyetemen szerzett PhD fokozatot kriptográfiából Dan Boneh professzor vezetésével, és a kutatócsoport tagjaként a Diem blokkláncon dolgozott.

***

Szerkesztő: Tim Sullivan

***

Az itt kifejtett nézetek az AH Capital Management, LLC („a16z”) egyes alkalmazottainak nézetei, és nem az a16z vagy leányvállalatai nézetei. Az itt található bizonyos információk harmadik féltől származnak, többek között az a16z által kezelt alapok portfólióvállalataitól. Noha megbízhatónak vélt forrásokból származnak, az a16z nem ellenőrizte önállóan ezeket az információkat, és nem nyilatkozik az információk tartós pontosságáról vagy adott helyzetre való megfelelőségéről. Ezenkívül ez a tartalom harmadik féltől származó hirdetéseket is tartalmazhat; az a16z nem vizsgálta át az ilyen hirdetéseket, és nem támogatja az abban található reklámtartalmat.

Ez a tartalom csak tájékoztatási célokat szolgál, és nem támaszkodhat rá jogi, üzleti, befektetési vagy adótanácsadásként. Ezekkel a kérdésekkel kapcsolatban konzultáljon saját tanácsadójával. Bármely értékpapírra vagy digitális eszközre történő hivatkozások csak illusztrációs célt szolgálnak, és nem minősülnek befektetési ajánlásnak vagy ajánlatnak befektetési tanácsadási szolgáltatások nyújtására. Ezen túlmenően ez a tartalom nem befektetőknek vagy leendő befektetőknek szól, és nem is szánható felhasználásra, és semmilyen körülmények között nem támaszkodhat rá az a16z által kezelt alapokba történő befektetésről szóló döntés meghozatalakor. (A16z alapba történő befektetésre vonatkozó ajánlatot csak az ilyen alap zártkörű kibocsátási memoranduma, jegyzési szerződése és egyéb vonatkozó dokumentációja tesz, és azokat teljes egészében el kell olvasni.) Minden említett, hivatkozott befektetés vagy portfóliótársaság, ill. A leírtak nem reprezentatívak az a16z által kezelt járművekbe történő összes befektetésre, és nem garantálható, hogy a befektetések nyereségesek lesznek, vagy a jövőben végrehajtott egyéb beruházások hasonló tulajdonságokkal vagy eredménnyel járnak. Az Andreessen Horowitz által kezelt alapok befektetéseinek listája (kivéve azokat a befektetéseket, amelyek esetében a kibocsátó nem adott engedélyt az a16z számára a nyilvánosságra hozatalra, valamint a nyilvánosan forgalmazott digitális eszközökbe történő be nem jelentett befektetéseket) a https://a16z.com/investments oldalon érhető el. /.

A benne található diagramok és grafikonok kizárólag tájékoztató jellegűek, és nem szabad rájuk hagyatkozni befektetési döntések meghozatalakor. A múltbeli teljesítmény nem jelzi a jövőbeli eredményeket. A tartalom csak a feltüntetett dátum szerint beszél. Az ezekben az anyagokban megfogalmazott előrejelzések, becslések, előrejelzések, célok, kilátások és/vagy vélemények előzetes értesítés nélkül változhatnak, és mások véleményétől eltérhetnek vagy ellentétesek lehetnek. További fontos információkért látogasson el a https://a16z.com/disclosures oldalra.