Estä synkronointi 1.36 sekunnissa Harmonyn adaptiivisen IDA-protokollan kanssa

Tulokset ensimmäisestä verkottumistavoitteestamme ovat loppuneet! Eugene ja Chao, kaksi Amazonin veteraanistamme, jotka ovat kääntyneet Harmony-verkostoitumisen asiantuntijoiksi, ovat toimittaneet verkkokompleksiimme ydinosan, nimeltään Adaptive Information Dispersal Algorithm (IDA).

Adaptiivisella IDAllamme on haaste kaikille blockchain-protokollille - etenemällä lohkoille viallisessa, bysanttilaisessa verkossa - upealla nopeudella. Yhtä mielenkiintoista on, että avaamme lähdekoodin tämän komponentin osana suurempaa vertaisverkkoa, kokonaisvaltaista verkkokirjastoa ”libunison”.

Koodinpätkä adaptiivisen IDA-kirjaston ydinfunktiosta.

Hieman taustaa

Harmonyssa tavoitteemme on rakentaa tehokas blockchain-protokolla seuraavan sukupolven hajautettujen sovellusten käyttämiseksi. Lähestymistapamme skaalautuvuuden saavuttamiseksi on rakentaa terävöitetty ketju, joka on optimoitu kaikille teknologiapinokerroille konsensusmekanismeista järjestelmiin ja tärkein tähän viestiin, verkottuminen.

Verkkokerros ei ole tähän mennessä saanut ansaitsemaansa huomiota keskusteluissa blockchain-skaalauksen ympärillä. Tämä valvonta on valtava mahdollisuus parantaa nykyisiä protokollan toteutuksia. Siksi vanhempien insinööreidemme ryhmämme haluaa tuoda uusimmat tekniikat verkottumisteollisuudesta Harmonyen. Tämän viestin loppuosa keskittyy tiettyyn osaan verkkosuunnittelumme (IDA), mutta jos olet kiinnostunut oppimaan lisätietoja yleisestä verkottumisvisiostamme, sinua kehotetaan lukemaan edellinen viestimme ”Harmony's Networking Story”.

Mikä tekee verkottumisesta tärkeän estää ketjua?

Lohkoketju on pohjimmiltaan kopioitu tietokanta, jota koordinoidaan tietokoneverkon kautta Internetissä. Niin yksinkertainen kuin tämä kuulostaa, tämän tekeminen luvattomalla ja epäluotetulla tavalla on valtava haaste.

Ei riitä, että lähetetään kaikki ympärillä olevat tapahtumat kaikille verkon solmuille. Solmujen on myös päästävä yksimielisyyteen näiden tapahtumien järjestyksestä niin, että kaikki ovat samalla sivulla. Tämä viimeinen osa vaatii paljon viestintää, ja siinä verkostoituminen tulee.

Yksi konsensuksen saavuttamisen suurimmista pullonkauloista on uusimman tapahtumaryhmän levittäminen lohkoehdotuksesta kaikille verkon osallistujille. Olettaen, että lohkon koko on 1 Mt ja 500 osallistujaa, sinun on tehtävä lähettää yhteensä 500 Mt tietoa verkon ympärille, jotta jokaisella on kopio lohkosta. Tämä on tiedon leviämisen perusongelma, ja prosessi voi viedä kauan riippuen siitä, kuinka ratkaiset sen. Mitä kauemmin lohkon levittäminen vie, sitä pidempi lohkojen välinen viive tarkoittaa, mikä puolestaan ​​tarkoittaa hitaampaa tapahtuman viivettä ja vähemmän läpimenoaikaa.

Estä etenemistekniikat

Tutkitaan naiivimpaa lähestymistapaa, joka on nimeltään multcast. Monilähetyksessä lohko-ehdottaja lähettää 1MB-lohkon jokaiselle verkon solmulle yksi kerrallaan. Koska ehdottajan on lähetettävä kaikki 500 Mt itse, jos hänen keskimääräinen laajakaistan Internet-nopeus on 64 Mbit / s, tämä vie noin 62,5 sekuntia. Se on nopeampaa kuin Bitcoinin keskimääräinen 10 minuutin lohkojen välinen aika, mutta se ei silti ole tarpeeksi nopea Harmonyn kaltaiseen tehokkaaseen lohkoketjuun.

Kuten luultavasti voidaan arvata, manycast ei ole kovin käytännöllinen eikä sitä käytetä laajasti useista syistä. Suosituimpia lähestymistapoja ovat juoruttaminen ja monilähetyspuut. Niin juoruttavissa järjestelmissä, kun uudet solmut kuulevat lohkosta, ne välittävät sen muille verkon jäsenille. Tämä purkaa osan viestinnän taakasta ehdottajalta ikäisilleen ja vähentää pullonkaulaa. Monilähetysjärjestelmissä verkko on järjestetty haaroittuneeseen puurakenteeseen, joka on peräisin ehdottajalta. Kun jokainen solmu vastaanottaa lohkon, se välittää viestin lapsilleen, kunnes kaikki ovat vastaanottaneet sen.

Kun monilähetysten aika lohkojen etenemiseen on lineaarinen verkon solmujen lukumäärässä tai O (n), juoruttaminen ja ryhmälähetystavat vievät aikaa, joka on vain logaritminen verkon solmujen lukumäärässä tai O (log (n)).

Tämä on merkittävä parannus, mutta voimme tehdä vielä paremmin.

IDA: n alkuperä

Zamani, Movahedi ja Raykova julkaisivat vuoden 2018 lehdessä Rapidchain-ehdotuksen paremmasta lohkojen levitysjärjestelmästä [1]. Muiden terävöityjen lohkoketjuprotokollien parannusten lisäksi tekijät ehdottavat uutta tekniikkaa, nimeltään - arvasit sen - IDA, levittääkseen lohkon verkon sisällä, jossa käydään BFT-konsensusta. IDA: n ydinkonsepti on käyttää pyyhkimiskoodausta lohkon hajottamiseksi koodatuiksi palasiksi, jotta se voidaan levittää nopeasti ja turvallisesti koko verkkoon.

IDA: n toiminnan ymmärtämiseksi sinun on ensin tiedettävä vähän pyyhkimiskoodauksista. Pyyhkäisykoodauksen avulla voit ottaa osan tietoja ja laajentaa niitä suurempiin koodattuihin tiedostoihin. Vaikka koodatun tiedoston osat katoavat, alkuperäinen tiedosto voidaan silti palauttaa. Pyyhkäisykoodausjärjestelmillä on nopeudet, jotka määräävät koodatun tiedoston määrän, joka voidaan kadottaa menettämättä alkuperäistä. Nämä hinnat sanelevat myös ylimääräisen datan tai yleiskustannusten määrän, joka on koodattava alkuperäisen tiedoston koon mukaan.

IDA: ssa ehdottaja ottaa 1 Mt: n lohkon ja laajentaa sen poistomenetelmän koodattuun tiedostoon, jonka koko on 1,5 Mt. Ehdotuksen tekijä sitten pilkkoa tämän 1,5 Mt: n tiedoston 500 palasiksi, joiden paino on 3 kt. Seuraavaksi ehdottaja lähettää yhden 3 kt: n palasen jokaiselle verkon 500 solmulle. Lopuksi jokainen verkon solmu lähettää 3 kt: n kappaleensa kaikille muille. Sitten jokaisella solmulla on palat, jotka se on saanut ehdottajalta, samoin kuin muut 499 palat, jotka se on vastaanottanut ikäisensä. Heti, kun siinä on yli 1 Mt arvoja 3 kt palasia, tuo solmu voi purkaa nuo palat alkuperäiseen lohkoon ja voila, olemmeko valmis!

Ero monilähetysten ja IDA-lähetysten välillä pyyhkökoodausta käyttämällä.

Huomaa yllä olevassa esimerkissä, että lohkon ehdottaja lähettää vain 500 kappaleen 3 kt koko 1,5 Mt, mikä on paljon vähemmän kuin 500 Mt monilähetysesimerkissä. Kuitenkin kukin verkon toinen solmu lähettää myös 3 kb: n kimppunsa 500 kertaa yhteensä 1,5 Mt, jolloin siirretyn tiedon kokonaismäärä on 750 Mt. Pinnalla tämä saattaa näyttää huonommalta kuin monilähetys. IDA: n etuna on, että vaikka enemmän dataa lähetetään aggregoituna, datan lähettäminen on täysin rinnakkain kaikkien solmujen välillä. Tämä poistaa minkä tahansa yksittäisen solmun pullonkaulan, joka tarvitsee lähettää suurimman osan datasta, ja antaa meille mahdollisuuden hyödyntää parhaiten verkon jokaisen solmun yhdistettyä kaistanleveyttä.

Saatat kysyä, miksi emme voi vain jakaa alkuperäistä 1 Mt: n lohkoa koodamatta sitä? Hyvä kysymys! Vastaus on, että missään luvattomassa lohkoketjussa ei voida olettaa, että jokainen solmu toimii yhteistyössä. Poistamalla ensin lohko koodaamalla meitä varmistetaan vahingollisilta solmuilta, jotka haluavat olla jakamatta tietojaan. Itse asiassa yllä olevassa esimerkissä voimme sietää jopa 33% solmuista, jotka eivät jaa, ja loput solmut pystyvät kuitenkin palauttamaan alkuperäisen lohkon. Ilman koodausta vain yksi vahingollinen solmu estäisi jokaista muuta solmua palauttamasta koko lohkoa.

Adaptiivinen IDA

IDA: n edut ovat hämmästyttäviä. Suorittamalla tietoliikennekuormitus, IDA suorittaa ajan, joka kuluu yhden solmun lähettämiseen yhtä suuri datamäärä kuin lohko ja joitain yleiskustannuksia. Tämä edelleen vähentää ongelmaa logaritmisesta monimutkaisuudesta vakioksi monimutkaisuudeksi tai O: ksi (1).

IDA: n hyödyt lohkojen leviämisessä olivat meille heti selviä, mutta kun pohdimme edelleen ongelmaa, mieleemme tuli vielä parempi ratkaisu. Viettänyt 15 vuotta verkkoprotokollien parissa NTT: llä (Japanin suurin puhelin), Eugene on ajan tasalla viimeisimmästä ja parhaasta verkottumisesta. Idea tuli uudesta pyyhkäisykoodauksen sovelluksesta, nimeltään RaptorQ Forward Error Correction, jonka Eugene oli nimittänyt osaksi vertaisverkon, päästä päähän -verkkopinoa.

Harkittaessa IDA: ta ja RaptorQ FEC: tä rinnakkain, meille valutti, että voisimme käyttää RaptorQ-koodausta IDA: n parantamiseksi. RaptorQ-koodi on erityinen pyyhkimiskoodausjärjestelmä, jota kutsutaan suihkulähdekoodiksi. Suihkulähdekoodit ovat verrattomia, mikä tarkoittaa, että koodatulla tiedostolla ei ole kiinteää kokoa. Ne ovat hyödyllisiä, koska niiden avulla alkuperäisen tiedoston lähettäjä voi tuottaa uusia koodattuja paloja pyynnöstä toistaiseksi. Lähettäjä voi toimia uusien koodattujen palojen suihkulähteenä, tästä nimi.

Mitä tällä on tekemistä IDA: n kanssa? Normaalissa IDA: ssa koodinopeus on asetettava etukäteen. Joten olettaen 33%: n uhkamallin kuten PBFT: ssä, koodatun lohkon on oltava vähintään 1,5 Mt taata, että kaikki rehelliset solmut vastaanottavat alkuperäisen. Tämä tarkoittaa 50%: n kiinteää tietoliikennekustannusta riippumatta haitallisten solmujen todellisesta osuudesta verkossa. Kaikki alle 50 prosenttia ja lohkojen eteneminen voitaisiin pysäyttää, pakottaen ehdottajan aloittamaan alusta.

RaptorQ: n verrattoman koodauksen avulla voimme välttää tämän kiinteän yläpinnan ja mukauttaa sen sijaan koodinopeutemme todellisiin verkkoolosuhteisiin.

Katsotaanpa, kuinka tämä toimisi, kuvittelkaamme, että lohkon ehdottaja tunsi olleensa optimistinen suhteessa tovereihinsä ja teki vain 1,2 Mt: n suuruisia paloja. Tämä 1,2 Mt jaettiin 500 kappaleeksi ja lähetettiin verkon ympäri kuten normaalissa IDA: ssa. Jos yli viides kuudesosa verkosta on rehellisiä, niin jokainen rehellinen solmu saa riittävästi palasia muodostamaan 1 Mt ja palauttamaan alkuperäisen lohkon. Kaikki ovat kunnossa, ja itse asiassa ehdottaja on säästänyt 0,3 Mt ylimääräisiä yleiskustannuksia! Jos kuitenkin yli kuudesosa on haitallisia, yksikään rehellinen solmu ei pysty palauttamaan lohkoa.

Tällaisessa tilanteessa, jos olisimme käyttäneet normaalia pyyhkäisykoodausta, voisimme selvittää, mitkä palat eivät olleet vahingollisten solmujen levittämiä, ja lähettää ne uudelleen, mutta sen tekeminen olisi aikaa vievää. Tai voimme käynnistää koko prosessin uudelleen korkeammalla koodinopeudella suojautuaksemme pahoilta. Joka tapauksessa konsensus juuttuisi ja me menettäisimme arvokasta aikaa.

Rateleless-koodilla ratkaisu on paljon tyylikäs. Ehdottaja voi yksinkertaisesti aloittaa täysin uusien kappaleiden lähettämisen suihkulähteeltään, kunnes rehelliset solmut ovat saaneet tarpeeksi paloja alkuperäisen lohkon palauttamiseksi. Saatuaan tietää, että alkuperäinen koodinopeus oli liian matala, ehdottaja mukauttaa koodinopeuden korkeammaksi seuraavalle kierrokselle, tästä syystä nimi Adaptive IDA.

Eugenen kaavio adaptiivisesta IDA: sta työssä. Kun riittämättömiä paloja saavuttaa kaksi rehellistä osallistujaa, johtaja alkaa tuottaa ja lähettää uusia paloja, kunnes he ovat saaneet tarpeeksi palauttaakseen eston.

Joten Adaptive IDA suojaa itse asiassa enemmän kuin vain haitallisilta solmuilta - se suojaa myös viallisilta verkko-olosuhteilta. Internet on arvaamaton. Yhteydet putoavat ajoittain. Olet varmasti kokenut tämän turhautumisen itse. Mutta riippumatta siitä, kuinka epäluotettava Internet on, Harmonyn on oltava 100% luotettava. Adaptiivinen IDA käsittelee tilanteita, joissa yhteydet rehellisten solmujen välillä häviävät.

Siksi, toisin kuin normaalilla IDA: lla kiinteillä nopeuksilla, adaptiivinen IDA voi optimoida koodinopeuden annetulle haitalliselle suhteelle ja sen taustalla oleville verkko-olosuhteille. Tämä vähentää viestinnän yleiskustannuksia ja tarjoaa nopean palautumisen epäsuotuisista tilanteista, mikä tekee IDA-prosessista entistä nopeamman ja joustavamman.

Bonus: Niille verkon geeksille, joita voit katsoa, ​​Adaptive IDA voidaan estää TCP: n adaptiivisten ikkunayhteyksien lohkon etenemisanalogina.

Valkoinen paperi

Jos pidit tämän viestin mielenkiintoisena, sinun kannattaa tutustua äskettäin julkaistuamme tekniseen esitteeseen. Siinä on paljon uusia, kuten tämä lähestymistapoja konsensuksen skaalaamiseksi, kun pyrimme toimittamaan korkean suorituskyvyn lohkoketjuprotokolla seuraavan sukupolven hajautettujen sovellusten käyttämiseksi.

Avoin lähdekoodi

Olemme ylpeitä rakenteestamme ja Adaptive IDA -sovelluksen käyttöönotto on avoimen lähdekoodin kaikille. Suuntaa githubiin ja kaivaa koodia ympäri! Tämä on yksi osa laajempaa pyrkimystämme vapauttaa täysi P2P, E2E -verkkokirjasto, nimeltään libunison. Toivomme, että avoimen lähdekoodin verkko-ohjelmisto-panoksemme ajavat koko blockchain-ekosysteemin eteenpäin.

eripuraisuus

Jos haluat ottaa yhteyttä meihin, olemme erittäin aktiivisia Discordissa ja toivotamme sinut tervetulleeksi liittymään kanavaamme ja tuntemaan meidät. Voit seurata käynnissä olevaa avointa kehitystyötämme!

Tutkimusfoorumi

Jos olet löytänyt tämän mielenkiintoisen, tutustu tutkimusfoorumiimme, jossa puhumme monista muista ideoista, kuten nämä. Jos haluat matemaattisemman ja teknisen selityksen adaptiivisesta IDA: sta, tee uusi aihe foorumin verkostoitumisluokkaan. Tule keskustelemaan!

Erityiset kiitokset Picolo Labsin Arunesh Mishralle palautteestaan ​​tähän viestiin.

[1] M. Zamani, M. Movahedi ja M. Raykova, “RapidChain: nopea lohkoketjuprotokolla täydellisen varjostimen kautta.” Kryptologia ePrint-arkisto, raportti 2018/460, 2018. https://eprint.iacr.org/2018 / 460.