У гэтым артыкуле я раскажу вам пра DAG (Directed Acyclic Graph, накіраваны ацыклічны граф) і яго прымяненні ў размеркаваных рэестрах, і мы параўнаем яго з блокчейном.
DAG не з'яўляецца чымсьці новым у свеце криптовалют. Магчыма вы чулі пра яго як аб рашэнні праблем маштабаванасці блокчейнов. Але сёння мы будзем казаць не пра маштабаванасць, а пра тое, што робіць крыптавалюты адрознымі ад усяго астатняга: дэцэнтралізацыя, адсутнасць пасрэднікаў і ўстойлівасць да цэнзуры.
Таксама я пакажу вам, што DAG насамрэч больш устойлівы да цэнзуры, і ў ім адсутнічаюць пасярэднікі для доступу да рэестру.
У звыклых нам блокчейнах у карыстачоў няма прамога доступу да самога рэестру. Калі вы хочаце дадаць транзакцыю ў рэестр, вам даводзіцца "прасіць" зрабіць гэта вытворцы блокаў (блок-прадзюсара, ён жа "майнер"). Менавіта майнеры вырашаюць, якую транзакцыю дадаць у наступны блок, а якую - не. Менавіта ў майнераў ёсць эксклюзіўны доступ да блокаў і права вырашаць, чыю транзакцыю прыняць для дадання ў рэестр.
Майнеры - гэта пасярэднікі, якія стаяць паміж вамі і размеркаваным рэестрам.
На практыцы ж, звычайна невялікая колькасць пулаў майнераў калектыўна кантралююць больш за палову вылічальных магутнасцяў сеткі. Для біткоіна гэта чатыры пулы, для Ethereum – два. У выпадку іх змовы яны могуць блакаваць любыя транзакцыі, якія захочуць.
За апошнія некалькі гадоў было прапанавана мноства варыяцый блокчейнов, якія адрозніваюцца ў прынцыпах выбару вытворцаў блока. Але самі вытворцы блокаў нікуды не сыходзяць, яны ўсё яшчэ "стаяць на шлагбаўме": кожная транзакцыя павінна прайсці праз вытворцу блокаў, і калі ён не прымае яе, то транзакцыі, па факце, не існуе.
Гэта непазбежная праблема ў выпадку з блокчэйнам. І калі мы жадаем яе вырашыць, мы павінны радыкальна змяніць дызайн і цалкам пазбавіцца ад блокаў і вытворцаў блокаў. І замест таго, каб выбудоўваць ланцужок блокаў, мы будзем злучаць самі транзакцыі, у тым ліку ў кожную транзакцыю хешы некалькіх папярэдніх. У выніку мы атрымаем структуру, вядомую ў матэматыцы як накіраваны ацыклічны граф - DAG.
Цяпер кожны мае прамы доступ да рэестру, без пасярэднікаў. Калі вы хочаце дадаць транзакцыю ў рэестр - вы проста дадаеце яе. Выбіраеце некалькі бацькоўскіх транзакцый, дадаеце свае дадзеныя, падпісваеце і пасылаеце вашу транзакцыю пірам у сетцы. Гатова. Няма нікога, хто мог бы перашкодзіць вам зрабіць гэта, таму ваша транзакцыя ўжо ў рэестры.
Гэта самы дэцэнтралізаваны, самы непаражальны перад цэнзурай спосаб дадання транзакцый у рэестр без пасярэднікаў. Таму што кожны жадаючы проста дадае свае транзакцыі ў рэестр, не пытаючыся дазволу ні ў кога.
DAG можна лічыць трэцяй стадыяй эвалюцыі рэестраў. Спачатку былі цэнтралізаваныя рэестры, дзе адзін бок кантраляваў доступ да іх. Потым прыйшлі блокчэйны, у якіх ужо было некалькі кантралёраў, якія запісвалі транзакцыі ў рэестр. І, нарэшце, у DAG наогул няма ніякіх кантралёраў, карыстачы дадаюць свае транзакцыі напроста.
Цяпер, калі ў нас ёсць такая свабода, яна не павінна прыводзіць да хаосу. Мы павінны мець згоду аб стане рэестра. І гэтая згода, ці кансэнсус, звычайна азначае згода пра дзве рэчы:
- Што адбылося?
- У якім парадку гэта адбылося?
На першае пытанне мы лёгка можам адказаць: як толькі правільна створаная транзакцыя была дададзена ў рэестр, яна адбылася. І кропка. Інфармацыя пра гэта можа даходзіць да ўсіх удзельнікаў у розны час, але ў рэшце рэшт усе ноды атрымаюць гэтую транзакцыю і даведаюцца, што яна адбылася.
Калі б гэта быў блокчэйн, майнеры б вырашалі, што адбываецца. Усё, што майнер вырашае ўключыць у блок - тое і адбываецца. Усё, што ён не ўключае ў блок - не адбываецца.
У блокчэйнах майнеры таксама вырашаюць другую праблему кансэнсусу: парадак. Ім дазволена парадкаваць транзакцыі ўнутры блока як заўгодна.
Як жа вызначыць парадак транзакцый у DAG?
Толькі таму, што граф у нас накіраваны, мы ўжо маем некаторы парадак. Кожная транзакцыя спасылаецца на адну ці некалькі папярэдніх, бацькоўскіх. Бацькі, у сваю чаргу, спасылаюцца на сваіх бацькоў, і так далей. Бацькі, відавочна, з'яўляюцца раней за даччыныя транзакцыі. Калі якая-небудзь з транзакцый можа быць дасягнута пераходамі па спасылках «бацька-дзіця», мы сапраўды ведаем парадак паміж транзакцыямі ў гэтым ланцужку транзакцый.
Але парадак паміж транзакцыямі не заўсёды можна вызначыць толькі з формы графа. Напрыклад, калі дзве транзакцыі ляжаць на паралельных галінах графа.
Каб дазволіць неадназначнасць у такіх выпадках, мы належым на так званых правайдэраў парадку. Мы таксама называем іх "сведкамі". Гэта звычайныя карыстачы, задачай якіх з'яўляецца сталая адпраўка транзакцый у сетку з захаваннем парадку, г.зн. так, што кожная іх папярэдняя транзакцыя можа быць дасягнута пераходамі па спасылках "бацька-дзіця". Правайдэры парадку - давераныя карыстальнікі, і ўся сетка належыць на тое, што яны не будуць парушаць дадзенае правіла. Для таго каб рацыянальна давяраць ім, мы патрабуем, каб кожны правайдэр парадку быў вядомым (неананімным) чалавекам ці арганізацый і меў нешта, што можа страціць у выпадку, калі парушыць правілы, напрыклад, рэпутацыю ці бізнэс, заснаваны на даверы.
Правайдэры парадку выбіраюцца карыстальнікамі, і кожны карыстальнік уключае спіс яго давераных правайдэраў у кожную транзакцыю, якую адпраўляе ў сетку. Гэты спіс складаецца з 12 правайдэраў. Гэта даволі маленькая лічба, каб чалавек мог праверыць асобы і рэпутацыю кожнага з іх, і дастатковую для таго, каб сетка працягвала працаваць у выпадку непазбежных праблем з меншасцю правайдэраў парадку.
Дадзены спіс правайдэраў вар'іруецца ад карыстальніка да карыстача, але спісы ў суседніх транзакцый могуць адрознівацца максімум на аднаго правайдэра.
Цяпер, калі ў нас ёсць правайдэры парадку, мы можам вылучыць іх транзакцыі ў DAG і упарадкаваць усе іншыя транзакцыі вакол парадку, створанага імі. Магчымасць стварэння такога алгарытму ёсць (гл. для тэхнічных дэталей).
Але парадак ва ўсёй сетцы не можа быць вызначаны маментальна, нам патрабуецца час на тое каб правайдэры парадку адправілі дастатковую колькасць сваіх транзакцый, каб пераканацца ў выніковым парадку мінулых транзакцый.
І, паколькі парадак вызначаецца толькі пазіцыямі транзакцый правайдэраў у DAG, усе ноды сеткі рана ці позна атрымаюць усе транзакцыі і прыйдуць да аднолькавага зняволення адносна парадку транзакцый.
Такім чынам, мы маем згоду адносна таго, што лічым тое, што здарылася: любая транзакцыя, якая трапіла ў DAG, здарылася. Таксама мы маем згоду аб парадку падзей: гэта альбо відаць зыходзячы з роднасных сувязяў транзакцый, альбо выводзіцца з парадку транзакцый, адпраўленых правайдэрамі парадку. Значыць мы маем кансэнсус.
Дадзены варыянт кансэнсусу мы маем у Obyte. Нягледзячы на тое, што доступ у рэестр Obyte цалкам дэцэнтралізаваны, кансэнсус адносна парадку транзакцый усё яшчэ цэнтралізаваны, т.я. 10 з 12 правайдэраў кантралююцца стваральнікам (Антон Чурумаў), і толькі два з іх - незалежныя. Мы шукаем кандыдатаў, якія жадаюць стаць адным з незалежных правайдэраў парадку, каб дапамагчы нам дэцэнтралізаваць устанаўленне парадку ў рэестры.
Нядаўна з'явіўся трэці незалежны кандыдат, які жадае ўсталяваць і падтрымліваць ноду правайдэра парадку - Універсітэт Нікасіі.
Цяпер, як мы кантралюем падвойныя марнаванні (double-spends)?
Па правілах, пры выяўленні дзвюх транзакцый, якія трацяць адну і тую ж манету, тая транзакцыя, якая аказалася раней у выніковым парадку ўсіх транзакцый, выйграе. Другая ж інвалідзуецца алгарытмам кансэнсусу.
У выпадку, калі маецца магчымасць усталяваць парадак паміж двума транзакцыямі, якія марнуюць адну манету (па сувязях бацька-дзіця), то ўсе ноды адразу адхіляюць такую спробу падвойнага марнавання.
У выпадку ж, калі парадак не бачны з бацькоўскіх сувязяў паміж дзвюма такімі транзакцыямі, яны абедзве прымаюцца ў рэестр, і нам спатрэбіцца дачакацца кансэнсусу і ўстанаўлення парадку паміж імі з дапамогай правайдэраў парадку. Тады выйграе больш ранняя транзакцыя, а другая стане неваліднай.
Хоць другая транзакцыя і становіцца неваліднай, яна ўсё роўна застаецца ў рэестры, бо ўжо мае наступныя транзакцыі, якія спасылаюцца на яе, якія нічога не парушалі і не ведалі, што ў будучыні гэтая транзакцыя стане неваліднай. Інакш нам прыйшлося б выдаляць аднаго з бацькоў у добрых наступных транзакцый, што парушыла б галоўны прынцып сеткі - любая правільная транзакцыя прымаецца ў рэестр.
Гэта вельмі важнае правіла, якое дазваляе ўсёй сістэме быць устойлівай да спробаў цэнзуры.
Давайце ўявім, што ўсе правайдэры парадку ўступаюць у змову ў спробе "зацэнзурыць" адну канкрэтную транзакцыю. Яны могуць ігнараваць яе і ніколі не выбіраць "бацькам" для сваіх транзакцый, але гэтага недастаткова, гэтая транзакцыя ўсё яшчэ можа быць уключана апасродкавана як бацька якой-небудзь іншай транзакцыі, выпушчанай любым карыстальнікам сеткі, які не ўдзельнічае ў змове. З цягам часу, такая транзакцыя будзе атрымліваць усё больш і больш дзяцей, унукаў і праўнукаў ад звычайных карыстальнікаў, разрастаючыся як снежны ком, і ўсім дамовіліся правайдэрам парадку давядзецца ігнараваць і гэтыя транзакцыі таксама. У рэшце рэшт, ім давядзецца зацэнзурыць усю сетку, што раўнасільна сабатажу.
Такім чынам, DAG застаецца цэнзура-ўстойлівым, нават калі мае месца змова правайдэраў парадку, тым самым пераўзыходзячы блокчэйн па ўстойлівасці да цэнзуры, у якім мы нічога не можам зрабіць, калі майнеры вырашаць не ўключаць якую-небудзь з транзакцый. І гэта вынікае з галоўнай уласцівасці DAG: удзел у рэестры абсалютна незалежна і без пасярэднікаў, а транзакцыі незваротныя.
Крыніца: habr.com