Что такое dag

Продвинутые структуры данных. Часть первая: Направленный ациклический граф

Всем привет! Уже на следующей неделе стартуют занятия в новой группе курса «Алгоритмы для разработчиков». В связи с этим, делимся с вами переводом совсем небольшого, но довольно интересного материала.

Я хотел начать эту серию статей со структуры данных, с которой все мы как разработчики, хорошо знакомы, но вполне возможно, что даже не представляем как она устроена.

«Направленный ациклический граф? Никогда об этом не слышал. Не думай, что все обо мне знаешь!», вы можете сказать, но именно этот граф делает возможным контроль версий. Да, Git представляет из себя ациклический граф. В этой статье я поделюсь с вами знаниями о направленных ациклических графах (Directed Acyclic Graphs, DAG), а затем покажу, как написать свой собственный.

Что такое DAG?

Так что это вообще значит? DAG – это однонаправленный граф, где ни один элемент не может считаться дочерним. Многие из нас знакомы со связными списками, деревьями и графами. DAG очень похож на первое и второе в реализации третьего.

Выглядит похоже на дерево, но не совсем

В самом минимальном виде у DAG есть 4 составляющих:

1. Узлы. В них хранятся данные.
2. Направленные ребра: стрелки, которые указывают в одном направлении (то, что делает эту структуру данных непохожей на другие).
3. Один «великий» узел-предок без родителей. (Забавный факт: большинство деревьев предков на самом деле являются направленными ациклическими графами, а не деревьями, поскольку порой «двоюродные братья и сестры женятся друг на друге»)
4. Листья. Или же узлы без дочерних узлов.

А теперь попишем код. Сначала создадим конструктор с двумя свойствами и назовем его DAG.

function DAG() < this.nodes = []; this.vertices = <>; >

Создадим метод для добавления узлов. Видите, что я здесь сделал?

DAG.prototype.add = function(node) < if (!node) < return; >if (this.vertices[node]) < return this.vertices[node]; >const vertex = < node: node, incoming: <>, incomingNodes: [], hasOutgoing: false, value: null >; this.vertices[node] = vertex; this.nodes.push(node); return vertex; >;

Как это работает? Объект vertex – это место, где происходит вся магия. Мы добавляем узел, объект с поступающими узлами и массив со всеми их именами, переменную типа Boolean, сигнализирующую о том, указывает ли узел на что-то или нет, и его значение. К этому мы перейдем попозже.

Теперь давайте добавим несколько ребер и соединим узлы друг с другом. Прежде чем мы сможем это сделать, мы должны создать вспомогательную функцию, которая проверяет, посещали мы этот узел или нет. Давайте назовем ее visit .

function visit(vertex, fn, visited, path) < const name = vertex.name, vertices = vertex.incoming, names = vertex.incomingNames, len = names.length, i; if (!visited) < visited = <>; > if (!path) < path = []; >if (visited.hasOwnProperty(name)) < return; >path.push(name); visited[name] = true; for (i = 0; i < len; i++) < visit(vertices[names[i]], fn, visited, path); >fn(vertex, path); path.pop(); >

DAG.prototype.addEdge = function(fromName, toName) < if (!fromName || !toName || fromName === toName) < return; >const from = this.add(fromName) const to = this.add(toName); if (to.incoming.hasOwnProperty(fromName)) < return; >function checkCycle(vertex, path) < if (vertex.name === toName) < throw new Error(“Theres a cycle foo. “)); >> visit(from, checkCycle); from.hasOutgoing = true; to.incoming[fromName] = from; to.incomingNames.push(fromName); >;

Пора отдать должное

Пока я изучал материалы для написания этой статьи, я прочел несколько замечательных сообщений от удивительно умных людей, и в итоге большая часть информации была получена от них. Часть теоретической информации я получил, изучив этот хорошо структурированный пост о DAG и контроле версий. Код, представленный здесь, вдохновлен исходниками emberjs и их авторами. А еще я многое почерпнул из других статей и сообщений о DAG в блогах множества великих людей.

Спасибо за то, что прочитали!

• JavaScript
• Programming
• Data Structures
• алгоритмы

• Блог компании OTUS
• JavaScript
• Алгоритмы

↗️ Что такое направленный ациклический граф (DAG) в криптовалюте

Многие уже знакомы с технологией блокчейн, где вся информация поэтапно записывается в распределительный реестр в строгом хронологическом порядке. В последнее время в криптосообществе набирает популярность технология иного распределительного реестра, который также позволяет создавать децентрализованные криптовалютные сети, но имеет совершенно иную асинхронную систему записи информации — DAG. Как это работает, разбираемся с ProstoCoin.

Что такое DAG

DAG — направленный ацикличный граф, который связывает информацию без циклов, используя топологическую сортировку. Технология ациклических графов часто используется при работе с разного рода информацией, поиске наиболее оптимального маршрута в навигационных системах или при сжатии данных.

В данной технологии нет блоков. Каждая новая транзакция добавляется в граф, состоящий из множества транзакций и записывается одновременно, а не последовательно. При этом каждый нод находится в определенном порядке, а сама конструкция такого распределительного реестра данных состоит из вершин, соединенных ребрами и направленных от более ранних к более поздним.

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

Немного позже исключительно на основе DAG были построены новые криптовалютные экосистемы. Сейчас концепция применения графа вместо блоков рассматривается как одно из перспективных направлений в развитии криптовалютной индустрии.

Особенности технологии DAG

В структуре DAG нет майнеров или мастренод. Пользователи сами обслуживают сеть. Прежде чем совершить транзакцию, следует подтвердить не менее одной, а чаще всего две предыдущие операции.

Направленный граф позволил создавать криптовалюты без блокчейна. По такой системе каждая транзакция подтверждает сохранение определенной последовательности операций в системе без необходимости хешировать ее в блоки.

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

Классический блокчейн vs. Directed Acyclic Graph (DAG)

Следует отметить, что обе технологии достаточно схожи и позволяют создавать децентрализованные системы с высокой степенью безопасности, но по разным принципам. Прежде всего, ориентированный граф точно так же, как классический блокчейн, является распределительным реестром данных, но, в отличие от блокчейна, информация в нем не записывается в строгой направленности.

Блокчейн — прямолинейный распределительный журнал, где вся информация хешируется и записывается в блоки в строгой хронологической последовательности. Каждый новый блок включает в себя информацию обо всех предыдущих и только после подтверждения подлинности майнерами включается в состав распределительного реестра. При этом новый блок уже должен включать информацию о только что добавленном. Такой алгоритм не позволяет создавать блоки параллельно, а, следовательно, существенно тормозит проверку транзакций.

В модели DAG нет блоков и проверка транзакций занимает значительно меньше времени. Нет и необходимости в майнерах, поскольку проверка транзакций происходит в самих транзакциях, а значит, сделки происходят практически мгновенно. Благодаря этому пользователи могут отправлять мгновенные платежи с минимальными издержками даже на незначительные суммы. Отсутствие майнеров также делает криптовалюту, основанную на ациклическом графе, еще более децентрализованной.

Отсутствие блоков решает проблемы с масштабируемостью, но в модели DAG появляется новая проблема — ширина сети. После того, как транзакция будет проверена, она должна быть связана с относительно более ранней отметкой в журнале реестра, но если новая информация будет связываться только с более новыми, то сеть может стать слишком обширной. Для того, чтобы удержать сеть в доступных для проверки размерах, транзакции связываются с существующими, но не самыми крайними транзакциями.

Криптовалюты, основанные на DAG, отличаются надежностью платежей, поскольку проверяются несколько раз разными узлами связи. Между транзакциями уже существует частичная упорядоченность, что позволяет выявлять проблемы двойной траты практически мгновенно.

В классическом блокчейне используется модель UTXO, по которой каждая не потраченная монета на кошельке может использоваться только один раз. Однако при проверке транзакций иногда возникают ситуации, граничащие с двойной тратой средств. И тогда майнеры признают подлинной только ту транзакцию, которая имеет более длинную цепочку подтверждений.

Криптовалюты, основанные на DAG

Несмотря на то, что технология является относительно новой, она уже считается жизнеспособной альтернативой блокчейна. На сегодняшний день направленный граф уже применен для построения сети нескольких криптовалют.

IOTA

IOTA — централизованная успешная криптовалюта, построенная без блокчейна. IOTA была разработана специально для индустрии Интернета вещей. В 2015 году разработчики провели успешное ICO, в рамках которого удалось привлечь 1337 ВТС инвестиций на развитие. Сейчас IOTA — один из топовых коинов, входящий в ТОП-20 криптовалют по капитализации.

В IOTA применение DAG привело к созданию журнала Tangle, который выглядит как ациклический граф в 3D. В сети каждая новая транзакция подтверждает две предыдущие, выбранные сетью случайным образом. Применение направленного графа позволило также создавать офлайновые сети, которые включаются в общие после подключения к Интернету.

Главная идея разработчиков – создать криптовалютную сеть, которая сможет обрабатывать миллиарды микротранзакций, которые помогут оплачивать любые, даже незначительные, автоматизированные процессы.

Byteball

Byteball — реализованный криптовалютный проект, построенный на технологии ациклического графа. Главной идеей разработчиков было желание создать криптовалютную экосистему со smart-контрактами и возможностью совершения мгновенных платежей и для хранения финансовых данных.

Проект был представлен в 2016 году и на сегодняшний день он успешно работает и выпустил свой удобный пользовательский кошелек Bytes. Децентрализованная система Byteball обеспечивает надежное хранение данных и защиту от подделки. Добавить в систему можно любую информацию, имеющую стоимость. Например, документы, подтверждающие право собственности, долговые расписки, акции и так далее.

Криптовалюта Bytes недоступна для майнинга и полностью конфиденциальна. Транзакции в ней невозможно отследить через распределительный реестр. Все монеты были выпущены в рамках первичной эмиссии. Количество монет в обороте остается постоянным, поскольку при оплате комиссии монеты возвращаются обратно в обиход. Интересной особенностью криптовалюты является и первичное размещение средств. Пользователю необходимо связать свой биткоин-кошелек с кошельком Byteball, после чего на счет будут начислены Bytes.

Dagcoin (Дагкоин)

На просторах Интернета еще с 2012 года можно найти упоминания о криптовалюте Dagcoin, которая теоретически должна была быть реализована через ориентированный граф. Фактически, коин так и не был разработан. Создатели перестали развивать техническую часть монеты и сделали упор на сбор средств.

Создателем монеты является Нильс Гроссберг, который известен как глава MLM –криптовалютного проекта OneCoin. На сегодняшний день Дагкоин не торгуется ни на одной бирже, а оплатив покупку криптовалюты, пользователи получают только обучающие материалы.

По всему можно сделать вывод, что Dagcoin — мошеннический проект. Их страница на GitHub закрыта за предупреждение о мошенничестве с пометкой, что это финансовая пирамида, которая продвигается известными мошенниками.

Преимущества и недостатки DAG

• более быстрая проверка транзакций внутри систем;
• минимизированные или полностью отсутствующие комиссии;
• более масштабируемые системы по сравнению с классическим блокчейном;
• позволяет создавать сети с высокой производительностью и минимальными издержками;
• двойная трата отсекается практически сразу;
• нет нужды в майнинге;
• транзакции проверяют сами пользователи.

• необходимо синхронизировать блокчейн каждый раз при добавлении транзакции;
• если участников в сети мало, то проверка транзакций может существенно затянуться.

DAG файл: создание и работа с ним

Для подготовки витрин данных SDP Analytics используется ETL оркестратор Airflow. Основным инструментом Airflow являются DAG файлы, расшифровывается как Directed Acyclic Graph — направленный ациклический граф.

По сути своей DAG является инструкцией с описанием последовательности операций над данными для Airflow. DAG пишется пользователем на Python в удобной для него IDE среде разработки.

Обычно DAG состоит из нескольких частей, рассмотрим их на примере простого DAGа по созданию таблицы.

1. Импортируем необходимые библиотеки и инструменты для подключения к БД

from airflow import DAG from datetime import datetime from airflow.operators.python import PythonOperator from airflow.providers.postgres.operators.postgres import PostgresOperator from airflow.hooks.postgres_hook import PostgresHook 

1. Задаем параметры запуска DAG’а подробнее

with DAG(  dag_id = "bootcamp4",  start_date = datetime.now(),  schedule_interval = None,  catchup = False,  tags = ['bootcamp'] ) as dag: 

1. Определяем параметры для подключения к БД, id конекта задается в подключениях Airflow

 src = PostgresHook(postgres_conn_id='admin_instance')  src_conn = src.get_conn() 

1. Далее идут блоки задач которые должен выполнять DAG

#Удалить таблицу таблицы  delete_table = PostgresOperator(  task_id ="delete_table",  postgres_conn_id = "admin_instance",  sql = """  DROP TABLE superset1_adb.test_b1  """ )  #Создаем таблицу в БД Analytics  create_new_table_1 = PostgresOperator(  task_id = "create_new_table_1",  trigger_rule = 'one_failed',  postgres_conn_id = "admin_instance",  sql = """  CREATE TABLE IF NOT EXISTS superset1_adb.test_b1 (  code int8 NULL  );  """ ) 

1. Задаем последовательность выполнения операторов в DAG’е,

delete_table >> create_new_table_1 

После того как DAG написан его необходимо загрузить в систему. Для этого необходимо авторизоваться на портале и пройти по ссылке в SDP Analytics. Далее открыть доступные области Airflow и у области куда необходимо добавить DAG нажать Список DAGs.

В открывшимся окне мы увидим список всех DAG файлов этой рабочей области, для добавление нового необходимо нажать кнопку Добавить сверху справа, перетащить файл в открывшуюся область и сохранить.

Изменение уже загруженного DAG файл происходит путем перезаписи текущего.

После загрузки DAGа он появляется в списке в Airflow, с наименованием, указанным в поле dag_id, в нашем примере это «bootcamp4»

При заходе в Airflow мы попадаем на стартовую страницу DAGs, на ней мы видим список всех загруженных сценариев, в том числе и наш и краткую информацию по ним.

Для запуска DAGа используется кнопка

колонки с действиями. На этом создание и запуск DAGа заканчивается.

Однако основная функция Airflow заключается не только в запуске, но и в мониторинге и управление работой DAGов, рассмотрим предназначенные для этого инструменты.

После того как сценарий запущен мы можем увидеть краткую статистику его работы, если пройти по имени DAGа, то можно получить доступ к более развернутой информации.

Каждая вкладка информационного окна DAGа позволяет посмотреть различные статистики и данные, их более подробное описание находится отдельно.

Через меню Browse — Dag Runs мы можем ознакомится с уже отработавшими сценариями.

Здесь мы видим результат запуска отдельных экземпляров DAG запущенных в конкретное время. По полю Dag Id мы можем перейти к DAG, по полю Run Id к конкретному экземпляру задачи для данного DAG. С помощью меню Actions можно массово изменить статус запуска DAG.

Для мониторинга выполнения большого количества заданий в разных DAG существует интерфейс Browse – Task Instance.

В нем представлен список задач из всех отработавших DAG с информацией по ним (подробнее).

ПАО Сбербанк использует cookie для персонализации сервисов и удобства пользователей.
Вы можете запретить сохранение cookie в настройках своего браузера.

Направленный ациклический граф (DAG)

Направленный ациклический граф (Directed acyclic graph, DAG) – это график, которые направлен и связывает остальные рёбра без циклов. Это значит, что невозможно преодолеть весь направленный граф, начав с одного ребра. Рёбра направленного графа идут только одним путём.

Направленный ациклический граф являет собой топологическую сортировку, где каждый нод находится в определённом порядке. Конструкция DAG состоит из вершин, соединяемых рёбрами. Основной алгоритм DAG называется топологическим распределением, это означает, что каждое ребро направлено от более раннего ребра к более позднему.

Что такое Направленный Ациклический Граф? [ править ]

Направленный ациклический граф (DAG) – Как это работает?

Поговорим о направленных ациклических графиках более подробно. Сейчас направленные ациклические графы – DAG очень популярны в криптосообществе. Прежде всего тем, что IOTA и другие проекты их используют. Вот как это работает.

Легко объяснить Directed Acyclic Graph поэтапно. На самом деле, всё так, как и у блокчейна. Когда вы разделяете это слово на «блок» и «чейн» (цепь), становится гораздо понятнее. Сделаем это и с DAG. Это график – да. Он ацикличен – то есть, ноды не связаны циклами. Следуя графику от нода к ноду, вы ни разу не перейдёте к одной и той же ноде дважды. Он также направленный – рёбра на направленном графике идут только в одну сторону.

Итак, Directed acyclic graph – это график, где рёбра идут в одном направлении, и он не имеет циклов – вы никогда не придёте к началу или к той же самой ноде.

• Далее — конструкция DAG, сделанная из нод и рёбер.
• Ноды – каждый нод представляет какой-то объект или фрагмент данных.
• Направленные рёбра. Направленное ребро (или «стрела») от одного узла к другому представляет собой определённый вид отношений между этими двумя нодами. В нашей ситуации, стрела означает «на её основе».
• Корневой нод. По крайней мере, один из нодов не будет иметь родителей. Это корень DAG.
• Листовые ноды. Один или несколько нодов не будет иметь детей. Они называются листьями или листовыми нодами.

Алгоритм направленного графа называется топологическим распределением. Каждое ребро всегда направлено от более раннего ребра к более позднему. DAG часто называют конкурентом блокчейна или даже следующим поколением блокчейна.

Блокчейн vs. Directed Acyclic Graph (DAG) [ править ]

На самом деле, блокчейн и DAG больше родственники, но в то же время и конкуренты. Дело в том, что оба эти понятия являются распределёнными реестрами. Блокчейн является линейным распределённым журналом, а направленные ациклические графики – без цепи блоков. В мире криптовалюты, блокчейн и распределённый реестр становятся синонимами, но это не совсем правильно – DAG – это реестры без блокчейна.

Преимущества DAG [ править ]

DAG имеют очевидные преимущества над блокчейном:

• DAG имеет хорошую масштабируемость, что означает высокую скорость транзакций. Только ноды являются контролёрами и валидаторами транзакций, а не блоки. Информация находится в транзакциях, что означает, что они очень быстрые. В теории, речь идет о миллионах транзакций в секунду. Это очень хорошая новость от DAG для криптовалют.
• Более высокая надёжность. Благодаря конструкции DAG, все транзакции всегда проверяются другими нодами, а иногда и неоднократно.
• PoW майнинг без энергозатрат. Нет никаких майнеров. Это также означает возможность большей децентрализации.
• Алгоритм DAG идеален для системы микроплатежей, потому что имеет «почти нулевые» комиссии.

Недостатки Направленных Ациклических Графов [ править ]

Конечно, Directed Acyclic Graph – это не панацея для блокчейна и криптовалюты и имеет свои ограничения. Прежде всего, несмотря на миллион возможных транзакций, у DAG всё же есть лимиты. Кто знает, может быть, в будущем мы будем говорить о проблеме масштабируемости DAG. Ещё одно сомнение в том, что нет информации о защите от взлома системы в её алгоритме или конструкции.

Криптовалюты с DAG [ править ]

IOTA [ править ]

Один из топовых коинов, использующих DAG — это IOTA. Этот проект находится в ТОП 10 на coinmarketcap.com с капитализацией около $5 млрд. Название IOTA составлено из «интернета вещей», а главной идеей этого криптовалютного проекта является создание экосистемы для миллиардов микроплатежей. Потому что в ближайшем будущем все наши устройства будут подключены к интернету и выполнять множество транзакций. Миллиарды платежей без комиссий – это идеальная экосистема для алгоритма DAG.

Сотрудничество IOTA и DAG привело к Tangle. Конструкция графика IOTA даже шире – согласно White Paper, он выглядит как направленный ациклический график в 3D. Каждой транзакции в Tangle нужно подтвердить любые две предыдущие транзакции, которые выбираются сетью случайно. Также, алгоритм данной криптовалюты, соединённый с DAG, сделал возможным создавать даже офлайн-части сети. При подключении к интернету эти блоки становятся частью общего «блокчейна». Также есть одно преимущество IOTA, не связанное с DAG – противодействие квантовых компьютеров из-за разных способов криптографии.

В конце мая IOTA Foundation представили кошелёк Trinity Mobile Wallet.

Byteball [ править ]

Криптовалютный проект Byteball пользуется преимуществами DAG, чтобы построить экосистему смарт-контрактов для быстрых платежей и хранения финансовых данный: валюты, права собственности, задолженности, акции и другое. Это не блокчейн-проект, основанный на конструкции DAG, уже работающий и имеющий хороший и удобный для пользователей кошелёк. Byteball хорош, когда речь заходит об одноранговых смарт-контрактов. Пользователи Byteball могут использовать безрисковые условные смарт-платежи: всё, что вам нужно – это установить условие, когда получатель получает деньги. Если это условие не выполнено, ваши деньги автоматически буду отправлены обратно вам – очень простой алгоритм, основанный на DAG. Например, Byteball позволяет купить или продать одноранговую страховку на своей платформе, используя смарт-контракты.

Учитывая потребности KYC/AML в сегодняшнем финансовом мире, хорошо, что Byteball даёт клиентам возможность присоединить свой адрес Byteball к их физическим лицам через сервис Jumio. Однако, в Byteball есть место и анонимности. Проект имеет две валюты – Bytes (GBYTE) и Blackbytes. Bytes – это широко используемая валюта на платформе Byteball, и все транзакции являются публичными. Blackbytes обеспечивают пользователям полную конфиденциальность, если это необходимо. Blackbytes – это наличная, неотслеживаемая валюта, чьи транзакции не видны в общественной базе данных. И последняя интересная вещь – Bytes доступны абсолютно бесплатно. Вам только нужно иметь биткоины (BTC) и привязать ваш биткоин-адрес к адресу Bytes!

Dagcoin (Дагкоин) [ править ]

Если вы уже провели собственное исследование о криптовалюте, использующей DAG, вы должны были найти что-нибудь о Dagcoin. Согласно фактам и информации из разных источников в интернете, (например, здесь, здесь и здесь), он выглядит как обман. Их страница на GitHub закрыта с предупреждением: «Dagcoin – это мошенническая финансовая пирамида, продвигаемая известными мошенниками» в заглавии. Вы также можете поискать дополнительную информацию о Dagcoin в сети самостоятельно.

Другими признаками обмана является использование множества сайтов для продвижения — dagcoin.org, dagcoin.group, dagcoin.club. Все интернет-источник полны фраз вроде «самая используемая криптовалюта во вселенной», но эта криптовалюта не торгуется ни на одной бирже, и её нельзя найти на coinmarketcap. Также нет информации о том, что делает Dagcoin. Вы просто платите какую-то сумму в долларах, чтобы получить Dagcoin, и получаете какие-то «обучающие материалы».

Основателем Dagcoin является Нильс Гроссберг – но этот человек был главой OneCoin, «успешного» MLM-криптовалютного проекта, где зарабатывают, приглашая новых членов. То же самое и у Dagcoin – можно зарабатывать монеты тем же способом, и вы получаете 10% от новичков, и даже «награду лидера» (информация из русскоязычного dagcoin.club). Вы также не можете получить все ваши дагкоины – как минимум 35% должны оставаться на счету (источник — dagcoin.club).

Согласно информации выше, Dagcoin имеет несколько очевидных признаков мошеннического проекта. Но информации о расследованиях против него или о закрытии этого проекта нет.

См. также на BitcoinWiki [ править ]

Источники [ править ]

1. https://www.techopedia.com/definition/5739/directed-acyclic-graph-dag
2. https://ericsink.com/vcbe/html/directed_acyclic_graphs.html
3. http://www.statisticshowto.com/directed-acyclic-graph/
4. https://en.wikipedia.org/wiki/Directed_acyclic_graph
5. https://en.wikipedia.org/wiki/Distributed_ledger
6. https://wikiq.ru/blockchain-vs-dag/
7. http://ins-money.net/dagcoin-team/
8. https://dagcoin.org
9. http://www.dagcoin.group
10. http://dagcoin.club
11. http://behindmlm.com/mlm-reviews/dagcoin-review-onecoin-affiliate-launches-ponzi-points-clone/
12. https://www.seospark.co.uk/dagcoin-review-good-opportunity-or-big-scam/