У цій статті я розповім вам про 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