Что такое DAG, или направленный ациклический граф? В этой статье речь пойдет в этом направлении. Во введении я объясню, что такое направленные ациклические графы и зачем их использовать? Затем я расскажу о структуре реестра Graphchain, который изначально основывался на STAG, о чем мы писали некоторое время назад. Здесь для наименования мы выбрали Graphchain. Затем мы поговорим о выборе дизайна, основных проблемах, а в конце сделаем вывод.
Это стенограмма презентации Кристофера Карра на мастер-классе «Layer 1 solutions», который состоялся в Primalbase AMS.
На всякий случай, если вам вдруг станет интересно, откуда все это взялось, сообщаю: изначально я написал эту статью под названием «Graphchain: масштабируемый децентрализованный реестр без блокчейна» с Ксавье Бойеном и Томасом Хейнсом в 2016 году. Мы поместили ее на ePrint; возможно, есть более читабельная версия в новостной статье ERCIM. Эта работа также опубликована и в других источниках. Но это, пожалуй, самый простой способ, чтобы найти ее.
Что такое направленные ациклические графы?
Во-первых, что мы имеем в виду под DAG? Мы имеем в виду направленный ациклический граф. Этот вид происходит от математического термина «граф», и, как правило, у вас эти множества состоят из вершин и ребер. Ребра – это просто упорядоченные пары вершин и они обычно представлены в виде стрелок, если у вас ориентированный граф. Граф ацикличен, если вы не можете начать с одной вершины и вернуться к другой, следуя стрелкам. Как вы понимаете, это не совсем математический термин.
Диаграмма (ниже) является примером DAG. Ребра – стрелки, а вершины – оранжевые блоки. Как вы можете видеть, здесь нет циклов. Вы не можете начать с одного из этих оранжевых блоков, проследовать по стрелкам и вернуться к оранжевому блоку. Это DAG. Вы также можете промаркировать эти графы.
Если вы промаркируете их, то получите так называемое Частично Упорядоченное Множество. В своей проделанной работе мы много говорим о частично упорядоченных множествах. Идея здесь состоит в том, чтобы получить частичное упорядочение. Так, если вы определяете стрелку, идущую к чему-то, выше той, из которой она выходит, то несложно заметить, что k выше всех остальных букв. Вы также можете заметить, что между f и h нет упорядочения. Все, что мы знаем о f и h, это то, что они выше d и что они ниже i.
Таким образом, мы получаем частичный порядок в отличие от другого вида графа, с которым мы все знакомы, а именно: блокчейном (ниже), который полностью упорядочен. На самом деле, прикольно, если задуматься над тем, как вы получаете эти «сиротские» блоки и сколько в итоге «сирот» вы можете иметь. Сейчас у меня нет на это времени, но это довольно весело, поверь мне. Вы получаете форки, но блокчейны – это, по сути, и есть ациклические графы, просто они гораздо более ограничены. Вы не можете иметь все эти дополнительные частичные упорядочения.
Зачем нам нужен DAG?
Какую задачу мы пытаемся решить? Главное, что мы здесь пытаемся сделать, - это децентрализация и масштабирование. У технологии блокчейн много проблем. Но эти две, пожалуй, одни из самых обсуждаемых; есть и другие, но больше всего меня интересует вопрос децентрализации, который по сути сводится к безопасности. Также важна и проблема масштабируемости, которая касается удобства использования. Но воз и ныне там. Откуда взялись эти проблемы? Судя по всему, они связаны с использованием блоков транзакций? Возможно.
Цель всего нашего проекта сводилась к следующему: можем ли мы создать систему, где вы будете вознаграждены за индивидуальные усилия? Основная проблема, и вы, вероятно, это знаете, заключается в том, что майнинговые пулы вызывают некоторую сложность. А сложность они вызывает потому, что у них по сути много власти: некоторые считают, что у них даже слишком много этой власти. Я в их числе. Это не значит, что майнеры – зло: есть много аргументов за и против их существования, и я на самом деле не хочу сейчас вдаваться в эту тему, но вы не думаете, что было бы хорошо, если бы в них не было надобности?
Можем ли мы отказаться от системы стимулирования за присоединение к майнинговым пулам? Это был один из вопросов. Помимо этого, возможно ли обеспечить более быструю обработку транзакций? Что, если бы мы могли просто транслировать транзакции с прилагаемым доказательством работы, сопоставлять эти транзакции и строить из них граф? Нам в таком случае вообще нужны блоки? Таково, по крайней мере, мышление на основе DAG.
Почему это важно? Потому что 51% честных пользователей достаточно? Нет! Мы знали об этом уже много лет. Так что же такое децентрализация? Этот вопрос гораздо сложнее. Он как бы связан с понятиями распределенного дизайна, поэтому вы можете резонно спросить, а что мы на самом деле подразумеваем под децентрализацией. Я действительно считаю, что ответить на этот вопрос довольно непросто. Есть и много тех, кто понимает, что мы реально подразумеваем под децентрализацией, особенно в части криптовалют. Грубо говоря, мы хотим, чтобы множество независимых машин по всему миру управляли одной и той же системой. Было бы также неплохо, если бы наши машины были эквивалентны с точки зрения вычислений. Как я уже сказал, ничего нового: все уже говорили об этом раньше.
Так о чем это мы? Мы вроде как говорим о майнинговых пулах и майнинговых фермах. В этой концепции «независимых машин по всему миру, управляющих одной и той же системой» — на самом деле машины работают под управлением одной системы майнинговых пулов. И в контексте машин, эквивалентных с точки зрения вычислений, у нас есть майнинговые фермы. Таким образом, у нас, по сути, есть только одна машина, у которой много вычислительной энергии. Вторая проблема не связана с тем, с чем, по моему мнению, обязательно столкнется DAG. Это зависит от функциональности.
Но и масштаб также является серьезной проблемой. Когда мы говорим о блокчейнах, почему мы обеспокоены масштабом? Ну, потому что блокчейн имеет этот линейный набор блоков, где одна транзакция относится к следующей. Проблема в том, что независимо от того, с каким блокчейном вы имеете дело, блоки содержат определенное количество транзакций. У них есть определенный период, в течение которого может поступить транзакция. Как мы только что услышали, мы знаем пределы для Эфириума и мы знаем пределы для Биткоина.
Часть проблемы заключается в том, что получая блоки, мы записываем их с чересчур большим количеством транзакций, т.е. у нас могут оказаться два разных блока, где один содержит транзакции от T1 до Tn, а другой от T1 до TN prime. Мы не знаем, одинаковы ли они — может быть, это один и тот же список транзакций, а может быть и нет.
Когда мы имеем дело с блокчейном, то получая разветвление, мы должны выбрать одну из веток. Это что-то типа вилки (т.н. «форк»). В этом случае мы будем ждать, пока одна из веток не будет продолжена, прежде чем мы сможем сказать, о каких транзакциях мы знаем. Если бы у меня были транзакции в T prime, мне теперь пришлось бы ждать, пока их не внесут в выбранную ветку. Мы не можем полагаться на транзакции, которые добавляются в форк.
Конечно, это очень обобщенный пример. Теперь представьте, что у вас тонны тонн блоков, которые производятся в одно и то же время. Когда мы имеем дело с блокчейнами, в число которых входит Эфириум с его протоколом GHOST, у вас есть «дяди» (потерянные блоки), которые могут быть включены в основную цепь. Это действительно умная идея, но вы при этом не добавляете транзакции. Таким образом, вы все еще можете вознаградить кого-то за их усилия, что является действительно умной идеей в создании этого дополнительного блока, потому что люди должны вознаграждаться за свои старания.
По сути, вся идея сводится к одному: можем ли мы создать систему, аналогичную этой, где вы создаете новый блок, но при этом также включаете транзакции как из T, так и из T prime, т.е. своего рода объединяете транзакции?
Это, по сути, Graphchain. Что у нас было и что значит - нет блоков? Транзакции просто относятся к предыдущим транзакциям, и их может быть столько, сколько вы хотите. Чтобы опубликовать транзакцию, вы просто собираете транзакции, с которыми согласны, и ссылаетесь на них, прикрепляя несколько доказательств работы к самой транзакции.
Как это работает?
Мы можем абстрактно определить функцию доказательства работы. Это довольно абстрактная идея, но она реализована на практике довольно легко: с помощью хэш-функций. Если говорить простым языком, функция доказательства работы S принимает задачу a и решение b. Мы можем сказать, что S (а,b) является истинной, если b – это решение a. Если брать блокчейн, например, то решением может быть одноразовый код (nonce), и ваша задача a – это ваш набор транзакций и ваша ссылка на предыдущий блок и все другие данные.
Все, что мы хотим, это количественно оценить работу, поэтому мы можем сказать, что работа этой функции доказательства работы = d. Это выполнимо, по крайней мере, большую часть времени. Если вы можете частично инвертировать хэш-функцию, то это вышло бы очень затратно в плане вычислительных усилий, ну или, по крайней мере, мы бы так могли предположить.
Итак, мы можем сделать это, и это уже происходит, потому что майнинговые пулы по сути делают то же самое. Если вы работаете в майнинговом пуле, вы не решаете блок и не передаете его в него, вы доказываете, что работаете на пул, показывая его участникам, что вы решили его в меньшей степени. Поэтому, если это, скажем, Биткоин, вы пытаетесь найти значение ниже определенного порога. Вы показываете участникам пула, что вы нашли решения, которые ниже более высокого порога: по крайней мере, это является доказательством того, что вы работаете на пул.
По сути, мы можем использовать тот же самый принцип. Идея состоит в том, чтобы количественно оценить, сколько работы было направлено на решение определенной головоломки. Абстрактная функция может быть чем угодно, где мы как-то количественно оцениваем, насколько трудно найти решение для головоломки. Нам даже не нужны хэш-функции: вы можете выбрать для этого что-нибудь другое. Опять же, мы попытались использовать это своего рода в качестве основы. Мы можем транслировать транзакции с соответствующим рабочим значением. Смысл этого всего сводится к тому, что мы можем сказать: вот блок, и он имеет значение работы, к примеру, 8.
Итак, вы снова берете свой ациклический граф, затем условно выбираете какие-нибудь цифры и говорите: ок, мы получили эти значения, и что это значит? Хороший вопрос. Наша задача - определить два понятия: вес и рост. Это очень похоже на блокчейн в том отношении, что у вас есть накопленный объем работы. После того, как мы отметили в графе рабочие значения, мы сможем отметить и остальные.
Для веса, например, у нас есть эта кумулятивная работа, связанная с транзакцией и всеми ее элементами-потомками (т.н. descendants). Высота – это совокупная работа, связанная с транзакцией и всеми ее элементами-предками (т.н. ancestors). Например, вы можете видеть, что по сути вес суммирует все значения доказательств работы для каждой из этих транзакций.
Таким образом, мы можем сказать (см. ниже), что вес транзакции составляет 61. Почему? Потому что это дает нам представление о том, как встраивается эта транзакция в систему. Для высоты (height) у вас есть система, в которой вы подсчитываете все транзакции-потомки. Интересно то, что вы также высчитываете саму транзакцию. Таким образом, для второй транзакции (также см. ниже, помечено ярко-красным цветом), мы можем сказать, что она имеет высоту 80. По сути, это всего лишь два примера, но с их помощью мы пытаемся показать, что в состоянии выяснить, насколько высокой в графе является транзакция, исходя из доказательства работы, на котором она построена.
Есть еще одна вещь, которую мы должны сделать в системе, основанной на DAG. Мы должны попытаться устранить транзакции, которые уходят дальше вниз. Причина, по которой мы должны сделать это, заключается в том, что если вам дан новый граф, то вы не видели каких-либо транзакций за последнее время и вам нужно сразу понять, насколько они высоки; и по мере того, как количество транзакций в системе возрастает, это очень быстро становится довольно затратным с точки зрения вычислений. Во избежание этого, вы в конечном счете должны начать избавляться от транзакций, которые уходят далеко назад. Это как бы отдельная тема для разговора.
Есть еще одна сложность в этом DAG-дизайне, и она довольно трудно разрешимая. Но вдруг у вас получится. В общем, мы бы хотели получить свойство сходимости. Если транзакции смогут ссылаться на любые другие предыдущие транзакции, что мешает пользователям создавать новые транзакции на очень старых узлах?
Вам нужны стимулы. Это тоже часть схемы. Нам нужны стимулы: мы хотим, чтобы пользователи строили блоки в верхней части графа, поэтому вознаграждение привязано к определенной функции высоты. Я это говорю очень простыми словами. Однако это не так просто, как кажется. Если бы функция была, скажем, обратной функцией, она бы не очень хорошо работала. Но вам нужна определенная функция высоты, чтобы создать этот стимул для работы с начального этапа. Смысл в том, что мы можем выполнять транзакции и поощрять людей работать в самом начале сделки. Мы оставляем это вопрос пока открытым, потому что, опять же, мы только пытаемся разработать схему.
Смысл в сходимости заключается в том, что вы в конечном итоге получаете зеленую транзакцию, которая по сути находится в верхней части списка. Это конвергентная транзакция, и каждая транзакция ниже нее является частью ее происхождения. И, основываясь на этой функции, каждый хочет дойти до этой новой зеленой транзакции: если вы собираетесь построить новую транзакцию, вы будете ссылаться на эту самую высокую. Такова идея.
Есть еще кое что, что требует нашего внимания. Мы должны решить проблему двойной траты. Рассмотрим сценарий такой двойной траты. У вас имеется следующий граф транзакций (см. ниже), и вдруг эти две помеченные красным транзакции начинают в двойном размере тратить деньги.
Итак, что с этим делать? Вы сравниваете значения. И в конечном итоге вы должны решить, какой из блоков вы хотите продолжить. Представьте, что вы в ситуации, которая называется «активный противник». Мы можем как-то генерализовать раскол в системах, но что, если противник захочет сохранить этот раскол в системах навсегда? Вы можете выполнить генерализацию таким образом, чтобы сделать невозможной надстройку транзакций на этих двух графах, поскольку вы не можете ссылаться на две конфликтующие ветки. Придется ли в этом случае удвоить расходы и сделать так, чтобы система никогда не сходилась?
Противник оказался в ситуации, когда ему нужно выстраивать цепочку на одной из этих двух транзакций. Ему также необходимо опередить остальную часть сети, которая попытается дальше строить блоки на одной из этих транзакций. Итак, представьте себе ситуацию, когда честные или, скорее, совместимые по стимулам узлы сначала создают транзакцию, которая должна быть достаточно высока, чтобы соответствовать «этому новому реалистичному графу». Тогда противник должен создать новую транзакцию на другой цепочке. Допустим, это это возможно. Затем это происходит снова и снова, и вы в конечном итоге сталкиваетесь с этой вероятной ситуацией (см. ниже).
Как видно, она очень быстро идет на уменьшение. Но это работает только при условии, что у противника нет достаточной вычислительной мощности. Это один из аргументов.
Просто для понимания работы [Graphchain]: вы создаете транзакции в своем собственном темпе и получаете вознаграждения за индивидуальные усилия. Вы способствуете дальнейшей эмиссии транзакций с помощью стимулов, и мы допускаем сходимость нескольких транзакций. Время создания доказательства работы приближено к реальному времени, так что есть надежда, что вы получите эти гораздо меньшие транзакции, которые создаются людьми, и доказательства работы будут выдаваться физическими лицами, совершающими сделки. И, наконец, что схема будет независима от функций доказательства работы или даже в какой-то степени от функций системы поощрения.
Отличия от существующих DAG-систем
Итак, есть другие системы DAG, о которых вы, возможно, слышали. Проект IOTA, пожалуй, самый известный: некоторое время назад он имел большую рыночную стоимость. Основные различия заключаются в том, что на самом деле нет никакого стимула (системы поощрения): есть своего рода майнинг, но нет по сути стимулов. И в настоящее время в этом проекте используются координаторы. Но они очень похожи с точки зрения схем и элементов, и на их веб-сайте изображены схемы, похожие на те, что я привел в этой статье. Вы можете ознакомиться с ними: они довольно интересны на самом деле.
Еще две реализации DAG – это Byteball и Nano. Казалось бы, обе реализации похожи, но они отличаются доверенными свидетелями. Nano использует распределенный протокол доказательства доли, и конфликтующие сделки устраняются путем голосования. Обе эти системы тоже классные – я бы рекомендовал присмотреться к ним. У них, очевидно, есть плюсы и минусы. Свою схему мы пытаемся сделать немного более независимой и децентрализованной.
Вывод
Я не только академически подошел к изучению этого вопроса, но и, как штатный сотрудник компании NTNU в Норвегии, занимаюсь разработкой этой схемы как рабочей версии криптовалюты. Я где-то полгода назад дал интервью норвежскому национальному телевидению, после чего я поговорил с TTO (офис по передаче технологий), и теперь я работаю над тем, чтобы превратить эту схему в рабочую криптовалюту. Удовольствия ради, но оно оказалось не очень-то и легкой задачей. Но мы все еще находимся на начальном этапе проекта. Только недавно мы получили финансирование и теперь ищем разработчиков.
Таким образом, мы пытаемся сохранить или даже расширить идею децентрализованной криптовалюты и мы также хотим получить систему, которая может масштабироваться. Это самое главное, что у нас есть. Возможно, масштабируемость будет ограничена в какой-то момент в практическом смысле — это то, что мы пытаемся выяснить, но, надеюсь, это привлекательно для многих пользователей. Спасибо за внимание.