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

«Поговорим за DAG» или «Когда моя видеокарта перестанет майнить Эфир?»

Простой арифметический расчет. Никакой магии. Проходите, садитесь, посчитаем вместе.

Теория

DAG файл — блок данных, более 1 Гб в размере, используемый для нахождения решения блока в сети блокчейн на алгоритме Dagger Hashimoto (последняя версия алгоритма называется Ethash). Разумеется, основная монета Ethash — Эфириум (Ethereum), но помимо ETH есть также другие монеты на этом алгоритме: Ethereum Classic, Musicoin, Ubiq, Daxx, Whale, Pegas, Expanse, Dubaicoin, Soil и так далее. Если еще не читали, обязательно ознакомьтесь со статьей «Сложность и хешрейт сети Эфириум на пальцах». Именно DAG файл загружается в память видеокарт, когда запускается майнер. Рассмотрим на примере Claymore:

Размер DAG файла со временем увеличивается. Происходит это через каждые 30 000 блоков и называется сменой эпох, т.е. каждой эпохе соответствует свой размер DAG. Где узнать текущий размер DAG? Мы рекомендуем этот сервис: https://investoon.com/tools/dag_size. Он показывает текущий размер DAG файла для основных валют на алгоритме Ethash, а также позволяет определить размер DAG файла по номеру блока. Повторимся, каждому блоку соответствует своя эпоха, а у каждой эпохи свой размер DAG.

Рассчет DAG файла идет по определенному алгоритму, можете посмотреть его здесь и проверить, что он работает (мы проверили). Кстати, все значения DAG давно рассчитаны и табулированы, можно брать значения DAG из этого массива.

Каждую эпоху DAG файл увеличивается на 8 МБ.

Время нахождения блока у каждой монеты разное: ETH — 30 секунд, ETC — 15 секунд, EXP — 90 секунд. Соответственно в сети Ethereum Classic 30 000 блоков пройдут в 6 раз быстрее, чем в сети Expanse. Именно поэтому на текущий момент у ETC уже 151 эпоха (DAG = 2.18 ГБ), а у EXP всего лишь эпоха 25 (DAG = 1.2 ГБ). Надо признать, что сравнение не очень честное, т.к. Экспанс появился чуть позже, чем Эфир.

Практика

Давайте рассмотрим блокчейн Ethereum.

Время нахождения блока сейчас составляет 30 секунд.
30 секунд × 30 000 блоков = 900 000 секунд должно пройти для смены эпохи
(900 000 ÷ 60 ÷ 60 ÷ 24 = 10.4 дней)

На время написания статьи последний блок ETH — 4 322 994, идет эпоха 144 и размер DAG 2134 МБ.
На блоке 4 350 000 начнется эпоха 145 и размер DAG вырастет до 2142 МБ.
Это должно произойти через 27 000 блоков (грубо, 9 октября).

Когда видеокарты перестанут майнить Эфир?

Все зависит от размера памяти видеокарты.

Видеокарты с памятью 2 ГБ перестали работать в сети Эфириум в ноябре-декабре 2016. Умирание плавно происходило после эпохи 93 с размером DAG 1.73 ГБ. Дело в том, что часть памяти используется под буфер и невозможно использовать все 100% карты под DAG. Проверить это легко. Ниже данные загрузки памяти майнером Claymore на видеокарте ноутбука, эпоха 144:

Сейчас карта использует 2.3 ГБ, т.е. почти на 200 МБ больше, чем размер DAG (2.13 ГБ). Кстати, если к видеокарте подключен монитор, то на него расходуется еще 150-200 МБ места.

Если предположить, что время нахождения блока ETH скоро станет 14 секунд и не будет изменяться, то получается, что видеокарты с 3 ГБ памяти начнут отмирать, примерно, через 400 дней, в конце 2018 года. Расчет простой, можете проверить сами:

1. До полного заполнения карты остается, грубо, 650 МБ.
2. 650 МБ ÷ 8 МБ (рост DAG с одной эпохой) = 81 эпоха
3. Каждая эпоха 14 × 30000 ÷ 60 ÷ 60 ÷ 24 = 4.86 дней
4. 81 (эпох осталось) × 4.86 (дней на эпоху) = 394 дня

Картам с 4 ГБ памяти отведено намного больше, почти 3 года, их владельцам точно пока не о чем беспокоиться, технология блокчейн развивается так стремительно, что к этому времени все может уже 10 раз поменяться.

Обратите внимание! Не стоит отчаиваться, если ваша видеокарта не может майнить Ethereum или Ethereum Classic из-за малого размера памяти. Многие монеты на алгоритме Ethash до сих пор прекрасно работают с 2 ГБ видеокартами, потому что эпоха еще небольшая: Ubiq — эпоха 8, Expanse — эпоха 25, Musicoin — эпоха 37. DAG файл этих монет на данный момент чуть больше 1 ГБ. Более того, майнинг этих монет зачастую может быть выгоднее майнинга Эфира, см. Whattomine.

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

Направленный ациклический граф (Directed acyclic graph, 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 имеет несколько очевидных признаков мошеннического проекта. Но информации о расследованиях против него или о закрытии этого проекта нет.

От блокчейна к DAG: избавляемся от посредников

В этой статье я расскажу вам о DAG (Directed Acyclic Graph, направленный ациклический граф) и его применении в распределённых реестрах, и мы сравним его с блокчейном.

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

Также я покажу вам, что DAG на самом деле более устойчив к цензуре, и в нём отсутствуют посредники для доступа к реестру.

В привычных нам блокчейнах у пользователей нет прямого доступа к самому реестру. Когда вы хотите добавить транзакцию в реестр, вам приходится «просить» сделать это производителя блоков (блок-продюсера, он же «майнер»). Именно майнеры решают, какую транзакцию добавить в следующий блок, а какую — нет. Именно у майнеров есть эксклюзивный доступ к блокам и право решать, чью транзакцию принять для добавления в реестр.

Майнеры — это посредники, стоящие между вами и распределённым реестром.

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

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

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

Теперь каждый имеет прямой доступ к реестру, без посредников. Когда вы хотите добавить транзакцию в реестр – вы просто добавляете её. Выбираете несколько родительских транзакций, добавляете свои данные, подписываете и посылаете вашу транзакцию пирам в сети. Готово. Нет никого, кто бы мог помешать вам сделать это, поэтому ваша транзакция уже в реестре.

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

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

Теперь, когда у нас есть такая свобода, она не должна приводить к хаосу. Мы должны иметь согласие о состоянии реестра. И это согласие, или консенсус, обычно означает согласие о двух вещах:

1. Что произошло?
2. В каком порядке это произошло?

Если бы это был блокчейн, майнеры бы решали, что происходит. Всё, что майнер решает включить в блок – то и происходит. Всё, что он не включает в блок – не происходит.

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

Как же определить порядок транзакций в DAG?

Только лишь потому, что граф у нас направленный, мы уже имеем некоторый порядок. Каждая транзакция ссылается на одну или несколько предыдущих, родительских. Родители, в свою очередь, ссылаются на своих родителей, и так далее. Родители, очевидно, появляются раньше дочерних транзакций. Если какая-либо из транзакций может быть достигнута переходами по ссылкам «родитель-ребёнок», мы точно знаем порядок между транзакциями в этой цепочке транзакций.

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

Чтобы разрешить неоднозначность в таких случаях, мы полагаемся на так называемых провайдеров порядка. Мы также называем их «свидетелями». Это обычные пользователи, задачей которых является постоянная отправка транзакций в сеть с соблюдением порядка, т.е. так, что каждая их предыдущая транзакция может быть достигнута переходами по ссылкам «родитель-ребёнок». Провайдеры порядка – доверенные пользователи, и вся сеть полагается на то, что они не будут нарушать данное правило. Для того чтобы рационально доверять им, мы требуем, чтобы каждый провайдер порядка был известным (неанонимным) человеком или организаций и имел что-то, что может потерять в случае, если нарушит правила, например, репутацию или бизнес, основанный на доверии.

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

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

Теперь, когда у нас есть провайдеры порядка, мы можем выделить их транзакции в DAG и упорядочить все другие транзакции вокруг порядка, созданного ими. Возможность создания такого алгоритма есть (см. Obyte White Paper для технических деталей).

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

И, поскольку порядок определяется только позициями транзакций провайдеров в DAG, все ноды сети рано или поздно получат все транзакции и придут к одинаковому заключению относительно порядка транзакций.

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

Данный вариант консенсуса мы имеем в Obyte. Несмотря на то, что доступ в реестр Obyte полностью децентрализован, консенсус относительно порядка транзакций всё ещё централизован, т.к. 10 из 12 провайдеров контролируются создателем (Антон Чурюмов), и только два из них – независимые. Мы ищем кандидатов, желающих стать одним из независимых провайдеров порядка, чтобы помочь нам децентрализовать установление порядка в реестре.

Недавно появился третий независимый кандидат, желающий установить и поддерживать ноду провайдера порядка – Университет Никосии.

Теперь, как мы контролируем двойные траты (double-spends)?

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

В случае, если имеется возможность установить порядок между двумя транзакциями, тратящими одну монету (по связям родитель-ребёнок), то все ноды сразу отклоняют такую попытку двойной траты.

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

Хоть вторая транзакция и становится невалидной, она всё равно остаётся в реестре, потому как уже имеет последующие транзакции, ссылающиеся на неё, которые ничего не нарушали и не знали, что в будущем эта транзакция станет невалидной. Иначе нам пришлось бы удалять родителя у хороших последующих транзакций, что нарушило бы главный принцип сети – любая правильная транзакция принимается в реестр.

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

Давайте представим, что все провайдеры порядка вступают в сговор в попытке «зацензурить» одну конкретную транзакцию. Они могут игнорировать её и никогда не выбирать «родителем» для своих транзакций, но этого недостаточно, эта транзакция всё ещё может быть включена опосредованно как родитель какой-нибудь другой транзакции, выпущенной любым пользователем сети, который не участвует в сговоре. С течением времени, такая транзакция будет получать всё больше и больше детей, внуков и правнуков от обычных пользователей, разрастаясь как снежный ком, и всем договорившимся провайдерам порядка придётся игнорировать и эти транзакции тоже. В конце концов, им придётся зацензурить всю сеть, что равносильно саботажу.

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

Источник https://2bitcoins.ru/ethereum-dag-file-gpu-mining/

Источник https://ru.bitcoinwiki.org/wiki/%D0%9D%D0%B0%D0%BF%D1%80%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D1%86%D0%B8%D0%BA%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B3%D1%80%D0%B0%D1%84_(DAG)

Источник https://habr.com/ru/company/obyte/blog/477032/