Блокиране на синхронизиране за 1.36s с адаптивния IDA протокол на Harmony

Резултатите от първата ни мрежа за сравнение са вън! Юджийн и Чао, двама от нашите ветерани от Амазонка, превърнали се в специалисти по хармонични мрежи, доставиха основен компонент от нашия мрежов стек, наречен Алгоритъм за адаптивно разсейване на информация (IDA).

Нашата адаптивна IDA се справя с предизвикателство, което е централно за всеки протокол на blockchain - разпространяването на блокове в дефектна византийска мрежа - със зашеметяваща скорост. Също толкова вълнуващо, ние ще отворим този компонент като част от нашата по-голяма колективна библиотека „libunison”.

Кодов фрагмент от основна функция в нашата библиотека за адаптивни IDA.

Малко предистория

В Harmony, нашата цел е да изградим високоефективен блокчейн протокол, който да захранва следващото поколение децентрализирани приложения. Нашият подход за постигане на мащабируемост е да изградим стриган блокчейн, който е оптимизиран за всички слоеве от технологичния стек, от консенсусни механизми до системи и най-важното за този пост, работата в мрежа.

Към днешна дата мрежовият слой не е получил вниманието, което заслужава в дискусиите около мащабирането на блокчейн. Този надзор представлява огромна възможност за подобрение в сравнение с текущите внедрявания на протоколи. Ето защо нашият екип от старши инженери е нетърпелив да внесе най-новите техники от мрежовата индустрия в Harmony. Останалата част от тази публикация ще се съсредоточи върху един конкретен компонент от нашия мрежов дизайн (IDA), но ако се интересувате да научите повече за нашата обща визия за работа в мрежа, ще Ви насърчим да прочетете предишната ни публикация „Мрежовата история на Хармония“.

Какво прави работата в мрежа важна за blockchain?

По същество блокчейнът е репликирана база данни, която се координира в мрежа от компютри през Интернет. Колкото и просто да звучи това, това да се прави по без разрешение и без доверие е огромно предизвикателство.

Не е достатъчно просто да изпратите всички транзакции наоколо до всички възли в мрежата, възлите също трябва да стигнат до консенсус относно реда на тези транзакции, така че всички да са на една и съща страница. Тази последна част изисква много комуникация и именно там влиза мрежата.

Едно от основните пречки за постигане на консенсус е разпространяването на последния блок от транзакции от предлагащия блок до всички участници в мрежата. Ако приемем размер на блока от 1MB и 500 участници, вие сте изправени пред задачата да изпратите общо 500MB данни в мрежата, така че всеки да има копие на блока. Това е основният проблем с разпространението на информация и в зависимост от начина, по който я решавате, този процес може да отнеме много време. Колкото по-дълго време е необходимо за разпространението на блока, толкова по-дълго забавянето между блоковете, което от своя страна означава по-бавна латентност на транзакциите и по-малка пропускателна способност.

Техники за размножаване на блокове

Нека проучим най-наивния подход за блокиране на разпространението, наречен Manycast. В много предавания, предлагащият блок изпраща блок 1MB до всеки възел в мрежата един по един. Тъй като вносителят трябва сам да изпрати всички 500MB, ако има средна широколентова интернет скорост от 64Mbps, това ще отнеме приблизително 62,5 секунди. Това е по-бързо от средното 10-минутно междублоково време на биткойн, но все още не е достатъчно бързо за високоефективна блокчейна като Harmony.

Както вероятно се досещате, Manycast не е много практичен и не се използва широко поради редица причини. По-популярните подходи включват клюки и многокачествени дървета. В схемите за клюки, тъй като новите възли чуват за блока, те го предават на други в мрежата. Това разтоварва част от комуникационната тежест от предложителя към неговите връстници и намалява затрудненията. В схемите за множествено предаване мрежата е подредена в разклонена дървовидна структура, произлизаща от предложителя. Когато всеки възел получи блока, той предава съобщението на децата си, докато всички не го получат.

Като има предвид, че времето за много разпространение на блокове е линейно в броя на възлите в мрежата или O (n), клюките и подхода за множествено предаване отнемат време, което е само логаритмично в броя на възлите в мрежата или O (log (n)).

Това е значително подобрение, но можем да направим още по-добре.

Произходът на ИДА

Предложение за по-добра схема за разпространение на блокове се появи в документ от 2018 г., озаглавен Rapidchain от Zamani, Movahedi и Raykova [1]. Наред с други подобрения на проточените блокчейн протоколи, авторите предлагат нова техника, наречена - познахте - IDA, за разпространение на блок сред мрежа с консенсус за BFT. Основната концепция, която стои зад IDA е да използва кодиране за изтриване, за да разбие блок на кодирани парчета, така че да може бързо и сигурно да се разпространи в цялата мрежа.

За да разберете как работи IDA, първо трябва да знаете малко за кодирането на изтриване. Кодирането за изтриване ви позволява да вземете парче данни и да го разширите в по-голям кодиран файл. Дори ако части от този кодиран файл са загубени, оригиналният файл все още може да бъде възстановен. Схемите за кодиране на изтриване имат скорости, които определят размера на кодирания файл, който може да бъде загубен без загуба на оригинала. Тези тарифи също диктуват количеството излишни данни или режийни разходи, които трябва да бъдат кодирани над размера на оригиналния файл.

В IDA, предлагащият взема блока от 1MB и го разширява в кодиран с изтриване файл от 1.5MB. След това вносителят нарязва този 1,5MB файл на 500 парчета от 3kB всеки. По-нататък предложителят изпраща по един 3kB парче на всеки от 500-те възла в мрежата. И накрая, всеки възел в мрежата изпраща парче от 3kB на всички останали. Тогава всеки възел има парчето, което е получил от предложителя, както и останалите 499 парчета, които е получил от своите връстници. Щом има повече от 1MB парчета от 3kB, този възел може да декодира тези парчета в оригиналния блок и воала, която сме готови!

Разликата между Manycast и IDA излъчване, използвайки кодиране за изтриване.

Забележете в горния пример, че предлагащият блок изпраща само 500 парчета от 3kB за общо 1.5MB, много по-малко от 500MB в многоканалния пример. Въпреки това, всеки друг възел в мрежата също изпраща своите 3kB парче 500 пъти за общо 1.5MB, което прави общите данни, предадени 750MB. На повърхността това може да изглежда по-лошо, отколкото при многото. Предимството на IDA е, че въпреки че повече данни се изпращат съвкупно, изпращането на данните е перфектно паралелно между всички възли. Това премахва пречките на всеки един възел, който трябва да изпрати по-голямата част от данните, и ни позволява да използваме най-добре общата честотна лента на всеки възел в мрежата.

Може да попитате защо не можем просто да разделим оригиналния 1MB блок без да го кодираме? Добър въпрос! Отговорът е, че във всеки без разрешен блокчейн контекст не можем да предположим, че всеки възел ще си сътрудничи. Чрез кодирането на изтриването на блока първо се осигуряваме срещу всички злонамерени възли, които решат да не споделят своите данни. Всъщност, в горния пример можем да толерираме до 33% от възлите, които не споделят и все пак останалите възли ще могат да възстановят оригиналния блок. Без кодиране само един злонамерен възел би спрял всеки друг възел да възстанови целия блок.

Адаптивен IDA

Предимствата на IDA са изумителни. Чрез паралелизиране на комуникационното натоварване, IDA завършва за времето, необходимо за един възел, за да изпрати количество данни, толкова големи, колкото блока плюс някои режийни разходи. Това допълнително намалява проблема от логаритмична сложност до постоянна сложност или O (1).

Ползите от IDA за разпространение на блока веднага ни бяха ясни, но докато продължихме да обмисляме проблема, на ум ни дойде още по-добро решение. След като прекара 15 години в работа в мрежови протоколи в NTT (най-големия телекомуникационен апарат в Япония), Юджийн е в течение на най-новите и най-добрите в областта на мрежите. Идеята дойде от ново приложение за кодиране на изтриване, наречено RaptorQ Forward Error Correction, което Евгений бе определил като част от нашия мрежов стек от peer-to-peer, от край до край.

Докато обмисляхме IDA и RaptorQ FEC един до друг, ни стана ясно, че можем да използваме кодирането на RaptorQ за подобряване на IDA. RaptorQ код е специален тип схема за кодиране на изтриване, наречена код на фонтана. Кодовете на фонтаните са безценни, което означава, че кодираният файл няма фиксиран размер. Те са полезни, тъй като дават възможност на лицето, изпращащо оригиналния файл, да запази нови кодирани парчета при поискване за неопределено време. Подателят може да действа като фонтан от нови кодирани парчета, оттук и името.

Какво общо има това с IDA? При нормален IDA скоростта на кода трябва да бъде предварително зададена. Така че, ако приемем 33% модел на заплаха, както е в PBFT, кодираният блок трябва да бъде поне 1.5MB, за да гарантира, че всички честни възли ще получат оригинала. Това предполага 50% фиксирана комуникация с режийни разходи, независимо от действителния дял на злонамерените възли в мрежата. Всичко, по-малко от 50% и размножаване на блока, може да бъде спряно, принуждавайки предложителя да започне отначало.

Безкрайното кодиране на RaptorQ ни позволява да преодолеем тази фиксирана режийна работа и вместо това да адаптираме скоростта на кода си към реалните условия в мрежата.

За да видите как това ще работи, нека си представим, че предлагащият блок се чувства оптимистично настроен към своите връстници и направи само парчета от 1,2 милиарда. Този 1.2MB беше разделен на 500 парчета и изпратен в мрежата, както в обичайния IDA. Ако повече от 5/6-та от мрежата е честна, тогава всеки от честните възли ще получи достатъчно парчета, за да състави 1MB и да възстанови първоначалния блок. Всички са наред и всъщност предложителят е спестил 0,3MB излишък от режийни разходи! Ако обаче повече от 1/6 са злонамерени, никой честен възел няма да може да възстанови блока.

В такава ситуация, ако бяхме използвали нормално кодиране за изтриване, бихме могли да разберем кои парчета не са били разпространявани от злонамерени възли и да ги препродават, но това да отнеме време. Или бихме могли да рестартираме целия процес с по-висока кодова честота, за да се предпазим от лошите. Така или иначе консенсусът ще се забие и ще загубим ценно време.

С безценен код решението е много по-елегантно. Предложителят може просто да започне да излъчва изцяло нови парчета от чешмата си, докато честните възли не получат достатъчно парчета, за да възстановят оригиналния блок. След като научих, че началната честота на кода е твърде ниска, предложителят ще адаптира честотата на кода, за да бъде по-висока за следващия кръг, оттук и името Adaptive IDA.

Диаграмата на Юджийн за адаптивни IDA на работа. Когато не достигнат достатъчно парчета до двама от честните участници, лидерът започва да генерира и изпраща нови парчета, докато не получат достатъчно, за да възстановят блока.

Така че, Adaptive IDA всъщност предпазва от не само злонамерени възли - освен това защитава от повредени мрежови условия. Интернет е непредсказуем. Връзките падат от време на време. Несъмнено сами сте изпитали това неудовлетворение. Но колкото и да е ненадежден основен Интернет, Хармонията трябва да бъде 100% надеждна. Адаптивният IDA обработва ситуации, при които връзките между честни възли са отпаднали.

Следователно, за разлика от нормалния IDA с кодове с фиксирана скорост, Адаптивният IDA може да оптимизира скоростта на кода за даденото злонамерено съотношение и основните мрежови условия. Това намалява режима на комуникация и осигурява бързо възстановяване от неблагоприятни ситуации, което прави процеса на IDA още по-бърз и устойчив.

Бонус: За тези мрежови отрепки там, бихте могли да разгледате Adaptive IDA като аналог на размножаване на блока на адаптивните прозоречни връзки в TCP.

Бяла хартия

Ако сте намерили тази публикация за интересна, трябва да разгледате наскоро пуснатия ни технически документ. В него ще намерите много нови подходи като този за постигане на мащаб на консенсус, тъй като ние се стремим да предоставим високоефективен блокчейн протокол, който да захранва следващото поколение децентрализирани приложения.

Отворен код

Гордеем се с това, което сме изградили и прилагането на Adaptive IDA е отворен код за всеки, който може да използва. Моля, отидете до нашия github и разкопайте в кода! Това е част от нашите по-големи усилия да освободим пълна P2P, E2E мрежова библиотека, наречена libunison. Надяваме се, че приносът ни за софтуер с мрежи с отворен код ще задвижва цялата блокчейна екосистема напред.

раздор

Ако искате да се свържете с нас, ние сме много активни в Discord и ви приветстваме да се присъедините към нашия канал и да ни опознаете. Можете да наблюдавате нашето отворено развитие в ход!

Изследователски форум

Ако ви се стори интересно, моля, разгледайте нашия изследователски форум, където говорим за още много идеи като тези. Ако искате по-математическо и техническо обяснение на адаптивен IDA, направете нова тема в категорията на мрежите на форума. Елате да обсъдим!

Специални благодарности на Arunesh Mishra от Picolo Labs за отзивите му по този пост.

[1] М. Замани, М. Мовахеди и М. Райкова, „RapidChain: Бърз блокчейн протокол чрез пълно заточване.“ Архив на криптологията на ePrint, отчет 2018/460, 2018. https://eprint.iacr.org/2018 / 460.