Альтернативы Proof of Work

В этой лекции будут рассмотрены альтернативы принятому в биткоине алгоритму защиты - доказательству выполненной работы (вычислительная задача proof of work, которая далее для краткости будет называться алгоритм, вычислительная задача или просто задача). Вычислительные задачи являются главной основой биткоина, потому что именно они применяются в системе поощрений. Майнеры получают вознаграждения за решение задач. Логично сделать предположение, что майнеры будут использовать любую возможность для ускорения нахождения правильного решения. И напротив, если существует свойство, помогающее экосистеме, но не способствующее непосредственному решению задач, оно не будет задействовано. Поэтому алгоритм вычислений играет очень важную роль в регулировании и направлении развития вычислительной сети.

Рассмотрим основные характеристики вычислительной задачи, основанной на криптографическом алгоритме SHA-2, которая в настоящее время используется в биткоин. Так, например, очень трудно найти полный набор решений для вычислительной задачи, что делает стоимость вычислительной мощности сети биткоина очень высокой или, другими словами, успешное решение задачи (нахождение блока) маловероятным. С другой стороны, скорость нахождения решений поддерживается на приемлемом уровне (около десяти минут). Это стимулирует майнеров, не имеющих больших вычислительных мощностей, участвовать в сети и позволяет им компенсировать затраты на ресурсы.

Если разрабатывать новый алгоритм вычислительных задач, какие особенности позволят ему завоевать популярность? Что будет помогать правильному развитию сети и препятствовать неверному?

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

Общие требования к алгоритмам PoW.

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

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

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

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

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

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

Алгоритмы с защитой от ASIC

Рассмотрим алгоритмы, устойчивые к использованию ASIC. Этот вид вычислительных задач в настоящее время является наиболее обсуждаемым. Тому есть несколько причин. В начале биткоины добывали, используя обычные ПК, позже для майнинга появились специальные интегральные схемы, сегодня почти весь майнинг идет на ASIC и использование ПК не окупает себя. Но это плохо для экосистемы, поскольку сейчас барьер для входа очень велик, а раньше новые пользователи активно включались в сеть. Для майнинга было достаточно оставить ПК включенным на ночь. Чтобы решить данную проблему, нужно придумать алгоритм, который свел бы к минимуму разницу между обычным ПК и специализированным оборудованием. Дополнительно можно выделить еще одну цель – снизить влияние производителей ASIC на сеть. Это важно, поскольку сейчас существует всего несколько крупных игроков на этом рынке. И они могут консолидировать в своих руках очень большую вычислительную мощность. У пользователей есть подозрения, что производители специально задерживают отправку ASIC устройств, добывая биткоины фактически за деньги покупателей. Еще одна возможная угроза – появление новой прорывной технологии для создания подобных устройств, которую производитель оставит в тайне и получит доминирующее положение в сети.

Наиболее популярный пример алгоритмов, устойчивых к ASIC, требует значительного объема памяти. Предпосылка довольно проста – в соответствии с законом Мура (см. Закон Мура) каждые 2 года количество транзисторов на кристалле ЦПУ должно удваиваться. Память и системы хранения данных так же развиваются, но скорость их развития намного ниже. И разрыв лишь увеличивается со временем. Из вышесказанного следует, что, если использовать алгоритм, требующий много памяти вместо просто вычислительной мощности, разница в производительности между специальным оборудованием и ПК будет меньше.

Самый известный алгоритм такого типа – scrypt. Вычисление SHA-256, используемого в биткоине, требует всего лишь 256 бит памяти. Такой объем легко разместить в регистрах процессора. Время на каждую операцию составляет порядка сотен миллисекунд. Значит, для полного перебора вариантов достаточно использовать много параллельных устройств. Scrypt же использует достаточно большое (по меркам однокристальных интегральных схем) количество памяти для хранения большого массива псевдослучайных чисел, которые генерируются на первом шаге алгоритма. Данные массива запрашиваются в случайном порядке и комбинируются с друг другом для создания ключа. Поскольку алгоритм генерации массива известен, то можно реализовать scrypt без использования памяти, но это потребует пересчета части элементов массива каждый раз заново, что достаточно сложно и занимает много времени. Таким образом, scrypt вносит баланс между количеством затрачиваемой памяти и временем.

Scrypt применяется во второй по популярности криптовалюте – Лайткоин (Litecoin). Кроме того, этот алгоритм используется для криптозащиты паролей, которая так же имеет целью защиту от ASIC. Это дает дополнительную уверенность в безопасности криптовалюты.

Рассмотрим шаги вычислений подробнее.

Пусть на входе строка символов Х. На первом шаге n ячеек памяти (n-количество шагов алгоритма) заполняются таким образом: в первую ячейку записывается V1 хэш от X, во вторую V2 хэш от первой ячейки, в третью V3– хэш от значения второй ячейки и так далее (рис 8.1).

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

Сначала рассчитывается значение-аккумулятор А, равное хэшу от последней ячейки. В цикле из n шагов с использованием текущего значения A высчитывается индекс ячейки i, из которой будут читаться данные. i находится как остаток от деления A на n. А на каждом шаге высчитывается как сложение по модулю 2 (XOR) А и Vi. После n шагов получаем итоговое A, которое и будет значением функции.

Если реализовывать алгоритм без буфера памяти, для вычисления A надо было каждый раз пересчитывать V_i . Общее количество пересчетов равно сумме арифметической прогрессии от 1 до n, то есть приблизительно n/2. Полное количество вычислений SHA-256 получится n*n/2=n²/2 против 2n вычислений в случае использования буфера. То есть быстрее в n/4 раз.

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

Так же вызывает сомнения, насколько он защищен от ASIC. Дело в том, что для выбранных в Litecoin параметров сложности (N) недостаточно для сглаживания разницы между ASIC и ПК. На рынке уже появились специальные устройства для майнинга, однако, стоит заметить, что их производительность в миллионы раз ниже, чем для биткоинов.

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

Рассмотрим другой пример алгоритма требующего использования памяти для работы. Он называется кукушкино хэширование. Для поиска решения на основании строки X строится неориентированный граф. Вершины графа выбираются по алгоритму

for i = 1 to n:
  i = X % N
  a = H0(X +i)
  b=N+ H1(X+1)

Ребра графа строятся так:

edge(a mod N, b mod N)

Теперь необходимо определить, есть ли в данном графе цикл длинной K (входной параметр функции). Если такой цикл найден, то ответом будет Х и индексы вершин.

Почему данный алгоритм требует много памяти? Дело в том, что нахождение циклов в графе хорошо изучено, но используемые для этого методы требовательны к объему ОЗУ. Зато проверить решение проще, чем в scrypt, нужно просто пересчитать вершины найденного цикла. И для этого не нужно много ресурсов.

Существуют и другие подходы к проблеме защиты от ASIC:

Алгоритмы, выполняющие реальную работу

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

Как уже отмечалось ранее, экосистема биткоина очень ресурсоемка. По разным оценкам вся сеть майнеров потребляет от 150 до 900 мегаватт энергии, что сравнимо с мощностью небольшой гидроэлектростанции. Но вся мощность используется только для высчитывания SHA-2 хэшей и не имеет какой-либо полезной функции.

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

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

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

Как пример воплощения полезного алгоритма можно рассмотреть Primecoin.

Для получения вознаграждения нужно найти последовательность простых чисел, называемых цепью Каннингема, которая вычисляется по формуле p_i=2ⁱa+1. Каждый член такой последовательности проверяется тестом простоты. Первое значение в последовательности делимо на хэш от цепочки блоков (предыдущего блока, mrkl_root и nonce ).

Алгоритм Primecoin действительно приносит результаты. Многие наибольшие цепи Каннингема были обнаружены в результате майнинга. Интересно, что существует проект распределённых вычислений, называемый PrimeGrid, который также нацелен на поиск простых чисел. Но действительно ли эта работа полезна? Цепи Каннингема используются в шифровании, однако, та форма, которая используется в Primecoin, практической пользы не несет.

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

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

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

Принцип работы алгоритма такой: представьте, что есть большой общеизвестный файл F. Для простоты предположим, что F выбирается избранным администратором.

Каждый пользователь собирается сохранить часть этого файла.

В Permacoin файл F разбивается на блоки. Из блоков строится дерево Меркла. Каждый майнер создает ключевую пару. Используя свой публичный ключ майнер псевдослучайно выбирает несколько сегментов файла F, которые он будет хранить. Чтобы получить награду за блок майнер должен выбрать случайно nonce и посчитать хеш h1, включающий хеш предыдущего блока, merkel_root, публичный ключ и выбранный nonce.

Теперь, вместо моментальной проверки на правильность (как в биткоине), исходя из полученного h1 выбираются несколько фрагментов из хранимых сегментов F и вычисляется хэш h2, содержащий всю информацию из h1 и, дополнительно, часть файла F. Полученный хэш h2 сравнивается с целевой сложностью, чтобы определить правильность найденного nonce. Таким образом, единственная возможность для успеха майнинга – сохранить себе часть блоков файла F.

Здесь стоит вспомнить об одном из спорных мест биткоина – честный майнер, то есть участник сети, который подтверждает все транзакции, включенные в блок, вынужден хранить на жестком диске информацию о всех непроведенных транзакциях. На данный момент - это около 200 Мб. Этот объем данных никак не помогает в майнинге и не приносит какого-либо дохода. В случае с Permacoin хранение данных оплачивается майнингом и быть честным майнером выгодно.

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

Алгоритмы, защищенные от распределения

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

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

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

Совсем недавно это проблема стала очень острой, поскольку крупнейший из существующих биткоин-пулов, Gigahash.IO, занял более 50% от общей мощности сети. Это вылилось в поток критики и обсуждений того, что подобная ситуация является огромной угрозой для биткоина и грозит ему гибелью. Пользователи требовали найти техническое решение для проблемы.

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

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

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

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

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

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

Рассмотрим подробнее, как должен работать алгоритм без возможности распределения.

Блок решения такой задачи будет содержать те же данные, что содержатся в блоке для биткоина: хэш предыдущего блока, merkle_root и произвольно выбранное nonce. Так же в блок включается публичный ключ, а майнер должен знать соответствующий приватный ключ. И две подписи, сделанные с помощью этой пары ключей s1 и s2.

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

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

Теперь после определения станет ли подобранный nonce корректным решением, вычисляется вторая подпись с использованием той же ключевой пары, но в нее включается так же и merkle_root.

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

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

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

Виртуальный майнинг, PoS

Рассмотрим алгоритм защиты, который называют доказательством доли владения (proof-of-stake, PoS). Всю группу подобных алгоритмов можно назвать виртуальным майнингом, поскольку они не предполагают вычислительной работы.

То есть мотивации для майнинга, подобной биткоину, нет.

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

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

Рассмотрим потенциальные плюсы данной распределенной системы. Первый – снижение стоимости вычислительной сети, не нужно ни производить, ни приобретать специальное оборудование. Второй плюс, как следствие из первого, – меньшее влияние на окружающую среду. В результате такого подхода каждый пользователь становится как бы вкладчиком в экосистему, а значит, он будет более заинтересован в поддержании ее нормальной работы и в ее развитии. Еще один плюс – защищённость от угрозы со стороны ASICs. Наконец, этот алгоритм защищен от атаки 51%, когда больше половины вычислительной мощности сети сконцентрировано в руках одного майнера.

Экономика биткоина намного меньше, чем мировая экономика. Значит, возможно, что человек, который очень богат вне системы биткоина, приобретет огромные вычислительные мощности, которые невозможно было бы приобрести, используя только средства из экосистемы. Такой человек или группа людей могли бы сделать атаку 51%. Если же представить, что майнинг основан только на монетах, существующих лишь внутри сети, то для атаки нужно будет купить 51% существующих монет. Во-первых, для этого нужно будет перевести часть внешних(реальных) средств в экосистему, например, через обменную биржу. Во-вторых, такой высокий спрос сильно поднимет стоимость криптовалюты и затруднит атаку. Конечно, это спорно, но считается, что намного дороже купить половину существующих биткоинов, чем создать ферму, превышающую половину мощности сети.

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

Другой вариант называют доказательством сжигания (proof-of-burn, PoB). В этом случае для майнинга нужно отправить монету на адрес, с которого гарантированно нельзя её потратить. Например, на адрес, который является хэшем случайного числа, – шансы подобрать к нему соответствующий публичный и приватный ключи ничтожно малы. С другой стороны, вы получаете шанс на получение вознаграждения.

Еще один возможный вариант – доказательство депозита (proof-of-deposit, PoD). Монеты вносятся на временно заблокированный аккаунт, они не уничтожаются, как в предыдущем случае, а вернутся обратно через время. То есть временно блокируется возможность тратить монеты.

Последний вариант– доказательство активности (proof-of-activity, PoA). В нем все владеющие монетами автоматически включаются в майнинг-лотерею. Если выбрана одна из монет конкретного пользователя, он должен за определенное время отправить подписанную своим ключом информацию о следующем блоке.

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

Терминологический словарь

доказательство выполнения работы (proof of work) - функция защиты распределенных систем от злоупотребления услугами (например, DoS-атак или рассылок спама), основанный на необходимости выполнения запрашивающей стороной некоторой достаточно сложной длительной работы (POW-задачи), результат которой легко и быстро проверяется обслуживающей стороной. В случае с криптовалютами доказательством решении задачи является правильно подобранный блок (точнее значение nonce для блока), хэш которого меньше определенного заданного числа, называемого целевым уровнем сложности.

майнер (miner) - программа, используемая для вычислений блоков. Так же человек, который занимается майнингом.

SHA-2 - группа криптографических алгоритмов, однонаправленная хэш-функция

ASIC (application-specific integrated circuit) – дословно интегральная схема специального назначения — интегральная схема, специализированная для решения конкретной задачи.

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

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

SHA-256 один из видов алгоритмов семейства SHA-2

хэш (hash) - результат вычисления хэш-функции для набора входных данных. Хэш-функция - преобразование входных данных произвольной длины в выходную строку (хэш) фиксированной длины, выполняемое определённым алгоритмом

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

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

x11 - алгоритм хэширования, который был впервые задействован в создании Darkcoin, использует 11 раундов хэширования с 11-ю различными хэш-функциями (blake, bmw, groestl, jh, keccak, skein, luffa, cubehash, shavite, simd, echo).

блок транзакций(блок) - специальная структура для записи группы транзакций в системе Биткоин и аналогичных ей. Блок состоит из хэша предыдущего блока, хеш-суммы всех включенных транзакций (merkle_root), и случайно перебираемого числа nonce.

merkle_root - дерево Меркла, древовидное хэширование. Хэш всех транзакций необходимых для блока данных

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