Proof-Of-Stake изнутри

7 min readDec 12, 2018

Часть 1 — Базовая структура.

Введение

Алгоритм консенсуса является важной частью любого блокчейна. Proof-of-Work, используемый в Bitcoin, Ethereum и прочих криптовалютах, является одним из первых таких алгоритмов. Однако все меньше и меньше создается криптовалют, использующих Proof-of-Work. На это есть свои причины, одна из них — это, конечно же, огромные затраты на электроэнергию и использование мощности железа “в никуда”. В связи с этим был придуман новый протокол, который основывается не на вычислительной мощности участника сети, а на количестве монет, находящихся у него на счету, и имя ему Proof-of-Stake (далее PoS).

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

На данный момент в интернете не так много статей, описывающих реализации PoS, в основном отражающие лишь их преимущества и недостатки. Однако, я дам несколько ссылок на такие статьи, чтобы было проще понять смысл протокола: Обзор альтернатив Proof of Work. Часть 1. Proof of Stake, Proof-of-stake (bitcoinwiki), A primer on Proof-of-Stake and why it matters…

Прежде чем начать

Я надеюсь, что у вас уже есть базовое понимание того, как работает Bitcoin и proof-of-work майнинг. Также большим плюсом будет наличие базовых навыков программирования, чтобы понимать представленный мной код. Все примеры кода написаны на Node.js.

Класс Transaction

Перед тем, как перейти к структуре транзакций, определим класс Account:

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

Перейдем к транзакциям:

Хочу заметить, что структура транзакций сильно упрощена. К примеру, нет полей inputs и outputs (используемых, например, в Bitcoin), а есть лишь recipient (получатель) и amount (кол-во монет). Хотя и они нам в рамках данной статьи не нужны.

Класс Block

В отличие от транзакции, где структура может быть одинаковой в любом алгоритме консенсуса, структура блоков разная. NXT для реализации PoS, помимо всего прочего, добавили поля, предназначенные конкретно для forging’а (генерации блоков):

С index, hash, transactions и timestamp, я думаю, все понятно из названия. Пройдемся по неизвестным:

• generator содержит публичный ключ аккаунта, сгенерировавшего данный блок

• baseTarget и generationSignature помогают выбрать forger’а, то есть создателя нового блока, и используются для генерации hit и target, о которых мы поговорим чуть позже.

Класс Mempool

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

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

Класс Blockchain

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

Эффективный баланс

Как вы уже знаете, в PoS вероятность выбора forger’а зависит от баланса аккаунта. В основном используется не просто баланс аккаунта, а так называемый эффективный баланс. В случае того же NXT это баланс 1440 блоков назад, и если он меньше 1000 NXT, то приравнивается к 0, то есть форжинг становится недоступным. Это, если говорить простыми словами, на деле же все чуточку сложнее. Кому интересно, можете заглянуть в их исходный код. Для большего понимания самого процесса forging’а, упростим и будем использовать обычный баланс пользователя.

Часть 2 — Forging.

Итак, после знакомства с основной структурой элементов можно перейти к объяснению алгоритма работы PoS.

Как я уже говорил ранее, для forging’а используется hit и target. Hit и target являются числами, сгенерированными на основе данных блока и forger’а, они необходимы для выбора участника сети, претендующего на forging нового блока. Рассмотрим подробнее это на схеме:

На схеме выше представлены 3 узла сети. Допустим, что все они являются forger’ами. Как видно, у каждого из них разное количество монет на счету. Стрелкой с пунктирной линией показан процесс синхронизации нод (узлов). Прямоугольником с пунктирной линией обозначен блокчейн участника сети. На 1-ом этапе, все узлы синхронизированы, то есть их блокчейны совпадают. На этапе 2 появляется потребность создать новый блок и все forger’ы начинают соревноваться в небольшой игре. Суть её состоит в том, чтобы сгенерировать число target, превышающее число hit. Шанс сделать это быстрее других у forger’а с наибольшим количеством монет. И наконец на 3-ем этапе в этой нелегкой борьбе побеждает фиолетовый forger. Он генерирует новый блок, а остальные участники в свою очередь проверяют, чтобы не было читерства со стороны победителя.

Если получилась ситуация, когда никому не удалось выиграть, участники пробуют снова, повторяя генерацию target каждую единицу времени, например, каждую секунду, пока не достигнут выполнения условия hit < target. Рассмотрим генерацию hit и target поподробнее.

Hit

Число hit вычисляется на основе данных предыдущего блока. Найти его очень просто, но перед этим необходимо определить значение generationSignature (да-да, того самого поля в структуре блока).

Файл Blockchain.js:

1. Берем generationSignature предыдущего блока;

2. Присоединяем к нему publicKey forger’a, планирующего получить право на создание нового блока;

3. И находим hash полученной строки при помощи алгоритма хэширования (в данном случае использован sha256);

Далее, при помощи generationSignature, вычисляем hit:

Файл Blockchain.js:

Тут все тоже очень примитивно. Берем первые 8 байт строки generationSignature и преобразовываем их в число. Таким образом, для каждого участника генерируется псевдослучайное число hit.

Target

После того, как hit сгенерирован, необходимо сгенерировать еще одно число под названием target. Как я уже говорил, если forger’у не удается достичь условия hit < target, через секунду он снова генерирует target для выполнения условия. Несложно предположить, что в таком случае target зависит от времени и вычисляется он по следующей формуле:

target = prevBaseTarget * effectiveBalance * elapsedTime

• prevBaseTarget — значение baseTarget (см. структуру блока) предыдущего блока

• effectiveBalance — эффективный баланс forger’а (в нашем случае просто баланс)

• elapsedTime — время, прошедшее с момента создания последнего блока

Напишем на основе этого функцию computeTarget, вычисляющую значение target в определенный момент времени:

Файл Blockchain.js:

Все, что нам осталось сделать, это связать hit и target для проверки выполнения условия “победы”. Реализуем это в функции verifyHit:

Файл Blockchain.js:

Удобство функции verifyHit заключается в том, что её можно использовать как при forging’е, когда forger пытается получить право на создание нового блока, так и при проверке очередного блока на выполнение условия.

Вы можете сказать: “Ну как же так? Ведь в таком случае получается, что forger’ы буду стараться копить как можно больше монет у себя на счету, тем самым генерировать новые блоки будут всегда одни и те же узлы, разве это правильно?”. И будете правы, это не есть хорошо и является одним из недостатков PoS. Данную проблему неплохо решает, например, DPoS (Delegated Proof of Stake), деля участников на голосующих и валидирующих, тем самым позволяя пользователям самим решать, кто будет forger’ом, а кто нет. Но вернемся к PoS.

Формирование блока

После того, как forger спустя какое-то время достигает выполнения условия hit < target, он начинает формировать новый блок. Для этого нам понадобится функция generateBlock:

Файл Block.js:

Функция довольно простая, однако стоит более подробно рассмотреть вычисление baseTarget. Формула для его вычисления:

baseTarget = prevBaseTarget * elapsedTime

Она очень похожа на формулу для вычисления обычного target, за тем лишь исключением, что не зависит теперь от баланса forger’а. К тому же на baseTarget накладываются определенные ограничения:

baseTarget должен быть не больше, чем предыдущий baseTarget*2 и не больше, чем maxBaseTarget. maxBaseTarget же вычисляется следующим образом:

maxBaseTarget = initialCoinAmount * initialBaseTarget

Где initialCoinAmount — это начальное кол-во монет в сети, initialBaseTarget — начальный baseTarget (в NXT он равен 153722867, так как в таком случае следующий блок после генезисного, при начальном кол-ве монет в 1 млрд, создастся за 60 сек.);

Файл Block.js:

2. baseTarget должен быть не меньше, чем предыдущий baseTarget/2 и не меньше 1;

В строке, помеченной номером 3, производится непосредственно вычисление baseTarget по формуле выше, но в дополнение к этому еще делится на 60 (1 минута). Таким образом, baseTarget увеличивается или уменьшается в зависимости от того, быстрее или медленнее минуты создался очередной блок.

Сложность

Еще одна вещь, которая присутствует в NXT — это cumulativeDifficulty. Она позволяет выбрать, так называемый, каноничный блокчейн. Каноничным считается тот, у которого значение cumulativeDifficulty максимально. Считается по формуле:

currCumulativeDiff = prevCumulativeDiff + 2^64/baseTarget

Однако данная тема уже относится к процессу синхронизации, что не входит в рамки данной статьи.

Соединяем все вместе

Теперь, когда у нас есть все необходимое для генерации новых блоков, объединим все в функции forge:

Файл Blockchain.js:

На мой взгляд, не стоит подробно объяснять код выше, так как тут все тривиально: проверяем выполнение условия hit < target, если выполняется, берем транзакции из мемпула, генерируем и добавляем новый блок в блокчейн, после чего через секунду повторно запускаем функцию. Кроме этого созданы функции startForging и stopForging для непосредственного управления forging’ом.

Заключение

Итак, в данной статье мы рассмотрели реализацию протокола Proof-of-Stake от NXT. Я надеюсь, что после прочтения у вас сложилось более полное представление о PoS майнинге. Конечно, данная реализация не является идеальной и имеет свои недостатки. Однако, на мой взгляд, она отлично иллюстрирует процесс forging’а.