Начиная работать над Vileo мы хотели создать механизм майнинга позволяющий использовать разные алгоритмы хэширования для построения блокчейна. Цель — дать возможность майнерам с любым оборудованием(ASIC, GPU, CPU) поддерживать сеть, охватывая всю возможную аудиторию участников сети. В статье я расскажу к каким результатам мы пришли, о майнинге в биткоине и некоторых других криптовалютах, использующих гибридный майнинг.

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

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

Мультигибридный майнинг неустоявшийся термин, в статье он используется для обозначения майнинга с доказательством работы(POW) на нескольких алгоритмах. В англоязычном и русскоязычном криптосообществах общепринятое название — Multi-PoW. Будет рассмотрен на примере криптовалюты Verge с пятью алгоритмами. Гибридный майнинг термин общепринятый, применяют к криптовалютам использующим POW и доказательство хранения средств/доли (POS). Его рассмотрим на примере одного из пионеров подобного решения — Novacoin.

Для понимания механизма майнинга нужно понимать следующие фундаментальные понятия в криптовалютах — работа и цель(target). Цель — числовое значение определяющие верхнюю границу хэшей, подходящих для создания блока в цепи. Работа — статистически среднее количество переборов необходимых для поиска хэша меньшего или равного цели.

Работа и цель на пальцах

Рассмотрим на примере броска 20-гранного кубика D&D. Раздадим кубики каждому игроку D&D на планете и попросим их бросить. Половина кубиков будут иметь значения от 1 до 10, вторая от 11 до 20. Допустим, что для нужного события в игре значение должно быть от 1 до 10. Пусть игроки продолжают бросать пока каждый не выкинет нужное значение. С каждым броском, количество оставшихся игроков уменьшается вдвое и окажется, что среднее количество бросков кубика на игрока будет рассчитываться согласно следующей формуле:

$\operatorname{кол-во\,бросков} = \frac{\operatorname{кол-во\,возможных\,значений}}{\operatorname{кол-во\,подходящих\,значений}}$

Если допустить, что на планете играет 500 миллионов, то самым “везучим” игрокам придется бросить кубик около 29 раз, но среднее количество бросков на игрока будет равно 2. Количество бросков в формуле идентично количеству актов генераций хэша и соответствует работе. Соответственно, количество подходящих значений хэша равно значению цели + 1. Полная формула для работы с 256 битными хэшами:

$work = \frac{2^{256}}{target + 1}$

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

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

$target_{new} = \frac{2^{256}}{work_{next}} - 1 =\frac{2^{256}}{{10min}\cdot{hashrate_{aver}}} - 1 = \frac{2^{256}}{\frac{{10min}\cdot{work_{2016}}}{time_{2016}}} - 1 =$

$= \frac{{2^{256}}\cdot{time_{2016}}}{{{10min}\cdot{2016}\cdot{\frac{2^{256}}{{target_{prev}} + 1}}}} - 1 =\frac{{time_{2016}}\cdot\left({{target_{prev}} + 1}\right)}{{{10min}\cdot{2016}}} - 1\approx\frac{{time_{2016}}\cdot{target_{prev}}}{{10min}\cdot{2016}}$

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

График бросков 12 гранного кубика игроком при хэшрейте 1 бросок/сек за время 100 секунд. Каждая точка — значение выпавшей грани, правая ось Y — количество значений попавших в таргет. Видно, что в таргет 2 попадают 20 бросков — подходят броски со значением 1 и 2. Оценка работы будет равна 20 * 12 / 2 = 120 броскам, при таргете 6 работа равна 53 * 12 / 2 = 106. Основное используемое свойство — при любом таргете в условии достаточной статистики получают близкое к точному значение работы и хэшрейта участника.

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

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

На первый взгляд расчет таргета в Novacoin не сильно отличается от расчета в биткоин. Novacoin правильно разделил расчет POS и POW. Итоговая приведенная формула для расчета таргета блоков POS в Novacoin имеет следующий вид

$target_{new} =target_{last}\cdot\frac{7day - 10min+2\cdot{time_{pos\_intrerval}}}{7day + 10min}$

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

Расчет POW почти такой же, за исключением того что в Novacoin заявлена разная частота для блоков POW и POS и он рассчитывается с интервалом от 10 мин до 30 в зависимости от положения в блокчейна. Можно заметить, если сеть резко потеряет хэшрейт POW или POS, то таргет будет сохранять свое значение вплоть до появления нового блока на потерявшем мощность механизме майнинга.

Расчет таргета в Verge использует механизм Dark Gravity Wave, который является развитием идей положенных Kimoto Gravity Well. Не вдаваясь в математику всех этих способов, цель у этих, без сомнения поэтично названных механизмов, одна — обеспечить пересчет таргета достаточно быстро реагирующий на изменение хэшрейта сети. Несмотря на некоторую мудреность кода, его математика сводится к достаточно простым формулам. Verge рассчитывает средний таргет 12 блоков выбранного алгоритма, в котором последний блок учитывается дважды:

$target_{aver} = \frac{2\cdot{target_{last}}+{target_{last-1}}+{...}+{target_{last-11}}}{13}$

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

$\frac{13\cdot({target_{aver} + 1)}}{2^{256}} = \frac{2\cdot({target_{last} + 1)}}{2^{256}}+ \frac{target_{last-1} + 1}{2^{256}} +{...}+\frac{target_{last-11} + 1}{2^{256}}$

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

$target_{new} \approx\frac{{time_{12}}\cdot{target_{aver}}}{{0,5min}\cdot{5}\cdot{12}}$

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

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

В Novacoin, несмотря на использование в комментариях и именовании переменных некого trust score, при детальном разборе логики это оказывается ничем иным как работой. Расчет для POS совпадает с формулой работы в точности, а расчет для POW можно рассматривать как работу с неким понижающим константным коэффициентом. Остальные дополнительные расчеты выглядят как добавочный к таргету механизм балансирующий очередность блоков. Надо заметить что это не лучшее решение. Как будет показано далее, для балансировки блоков достаточно только таргета. Кроме того блоки POS и POW c общим родителем могут оказаться неравными, хотя сам факт появления валидных блоков с общим родителем должен определяться как их равенство.

Прежде чем рассмотреть текущее состояние механизма консенсуса Verge будет познавательным заглянуть в его прошлое. Весной 2018 Verge пережил несколько атак. Не вдаваясь в подробности механики атак, код того времени, отвечающий за выбор форка, содержит сомнительную логику. Если допустить, что в криптовалюте POW функция IsProofOfStake() может вернуть истинное значение, то сложение работ разных алгоритмов будет, как было показано выше, приводить к доминированию алгоритма с более высоким хэшрейтом. В противном случае выбор делается просто по длине цепи, что при верно рассчитываемом таргете(цель которого — равномерное появление блоков) может привести к равенству ветвей с очень разными действительно проделанными работами.

В текущем коде Verge использует для сравнения константные коэффициенты. Если допустить, что эти коэффициенты учитывают некую актуальность мощностей оборудования для майнинга, явная слабость такого выбора — потеря актуальности при появлении нового оборудования.

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

Расчет таргета будет вычисляться из средних арифметических работы и времени на статистики последних 300 блоков. Итоговая формула расчета:

$target =\frac{2^{256}}{k\cdot{60}\cdot{hashrate_{aver}}} - 1$

где k — количество интервалов на которые должен приходиться один блок алгоритма для которого вычисляется таргет.

Сведем в таблице исходные и расчетные значения для 10 000 блоков.

algo	1	2	3	4
hashrate	40	80	index < 4000: 20 4000 > index < 6000: 150 index > 6000: 20	100
interval	60
blocks	3333	3333	1666	1666
work	24000000	48000000	27600000	60000000

Хочу обратить внимание, что расчетное значение работы цепи рассчитывается по формуле:

$work_{algo}=hashrate_{algo}\cdot{time_{all block}}$

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

algo	1	2	3	4
interval	59	59	57	59
blocks	3306	3320	1691	1683
work	23847014	47085487	27028272	60499076

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

^{График блоков 3850-4650}

^{График блоков 5599-6399}

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

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

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

$work_{equal}=\sqrt[k_1]{work_{algo_1}}\cdot\sqrt[k_2]{work_{algo_2}}\cdot ...\cdot\sqrt[k_n]{work_{algo_n}}$

Где k — количество интервалов, на которые должен приходиться один блок алгоритма, для которого вычисляется таргет.

Такая эквивалентная работа обладает следующими свойствами:

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

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

$work_{equal}=\sqrt[k_1]{{k_1}\cdot{t}\cdot{hashrate_{algo_1}}}\cdot \sqrt[k_2]{{k_2}\cdot{t}\cdot{hashrate_{algo_2}}}\cdot...\cdot\sqrt[k_n]{{k_n}\cdot{t}\cdot{hashrate_{algo_n}}}$

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

algo	1	2	3	4	equal
part	3	3	6	6
net hashrate	40	80	20	100	11862
attacker hashrate	160	40	10	50	11862

Для достижения равенства с сетью ему придется обладать хэшрейтом превосходящим хэшрейт сети по первому алгоритму в 4 раза.

На следующем графике показан результат эмуляции атаки на блокчейн.

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

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

Всем счастливого блокчейна и спасибо за внимание к теме.

Консенсус в криптовалютах с гибридным и Multi-PoW майнингом