5 июля 2022

PoS vs. PoW: Proof of Memory (PoM)

[Menaskop: данная заметка представлена мне в качестве ver 0.1 от 29.04.2022  автором progr76@gmail.com]. 

Цель PoM-консенсуса — ускорить обработку транзакций и блоков до уровня POS/DPOS консенсусов, но при этом сохранить уровень надёжности и децентрализации на уровне POW консенсуса. Как известно недостатком POS является зависимость цепочки от внутренних переменных блокчейна, следствием чего является дешевизна переписывания истории транзакций. В то же время в POW цепочка зависит от потраченной энергии, а значит изменение истории стоит дорого. Дополнительным бонусом консенсуса PoM является уравниванием между собой оборудования майнинга, основанного на  GPU и ASIC, а также неограниченно масштабируемый шардинг.

Для этого предлагаем помимо вычисления хэшей еще использовать память, но в отличие от других похожих алгоритмов (например Ethash), в нашем алгоритме память не ограничивает, а улучшает работу целевого оборудования. Это можно осуществить за счет того, что при подборе хеша будет использоваться не целочисленный nonce, а определенное значение, трудоемкое для вычисления — например, вычисленное по алгоритму SHA-3, и будет допущено повторное применение этого значения в течении некоторого времени для подбора лучшего хэша блока. Таким образом будет выгоднее сохранять эти значения в памяти, чем вычислять заново. 

Схема накачки памяти хэшами и поиска лучшего значения для нового блока:

Схема 00

  1. Ядра CPU/GPU выполняют постоянную накачку памяти “свежими” хэшами.
  2. Периодически в параллельном потоке производится поиск “лучшего” хэша для нового блока цепочки.
  3. Если конфигурация ядра + память не сбалансирована, например памяти мало, то после заполнения всего пула памяти вычислительные ядра могут быть остановлены, что может приводить к экономии электроэнергии.

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

Определение блока лидера

Формула расчёта NonceHash для накачки пулов в памяти:

NonceHash = sha3(Time, PubKey , Nonce), где:

  • Time  — время расчета нанс хэша из валидного диапазона
  • PubKey — публичный ключ майнера
  • Nonce — произвольное число

Для расчёта текущего хэша майнер использует NonceHash из пула и формула выглядит следующим образом: 

PowHash= XOR(sha3(BlockNum,PrevPowHash), NonceHash), где:

  • NonceHash- валидный nonce хэш из пула
  • PrevPowHash- хэш мощности из предыдущего блока
  • BlockNum — номера текущего блока

ОсобенностиПрименение XOR говорит о том, что для высокой мощности хэша (т.е. количество первых нулей) нужно найти наиболее близкое значение к друг другу, что позволяет при отсортированном пуле хэшей выполнять поиск за одно обращение к памяти (т.к. время алгоритма поиска порядка O(1)), а значит снизить расход электроэнергии.

В сеть отправляются параметры: BlockNum,PrevPowHash, Time, PubKey, Nonce являющиеся доказательством выполненной работы. Каждая нода проверяет валидность времени и восстанавливает хэш мощности по формуле:

NonceHash = sha3(Time, PubKey, Nonce)

PowHash = XOR(sha3(BlockNum,PrevPowHash), NonceHash)

Схема цепочки блоков (PoW chain):

Схема 01

Привязка данных блока

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

Формула расчета текущего хэша блока с данными:

BlockHash = hash(BlockNum,PowHash,PrevBlockHash,DataHash), где:

  • BlockNum — номер текущего блока
  • PowHash — хэш мощности текущего блока
  • PrevBlockHash — хэш предыдущего блока
  • DataHash- хэш транзакций текущего блока =hash(TxArr)

Формула расчета подписи:

Sign = sign(BlockHash , MinerAcc), где:

  • BlockHash  — хэш блока
  • MinerAcc- аккаунт майнера для награды за блок

В сеть отправляются те же параметры что и выше: BlockNum,PrevPowHash, Time, PubKey, Nonce, а также дополнительно: PrevBlockHash,DataHash, MinerAcc,Sign. 

Где параметры MinerAcc,Sign — являются опциональными (в этом случае майнер не получает награды, а цепочка подтверждается следующими майнерами).

Порядок выполнения проверок:

  1. Вычисляется публичный ключ майнера из параметра Sign
  2. Определяется корректность цифровой подписи
  3. Вычисляется хэш мощности
  4. Определяется кандидат в блок-лидер

Общая схема цепочки блоков:

Схема 02
Примечания:

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

Определение лидер-цепочки

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

Та цепочка которая имеет максимальную сумму числа ведущих нулей хэшей (PowHash) будет являться лидером.

Шардинг

Здесь под шардингом понимается возможность соединения блокчейнов на основе PoM консенсуса с друг другом для создания единого информационного пространства по обмену транзакциями.

Merged mining

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

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

Кросс-блокчейновые транзакции (сообщения)

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

Схема доставки кросс-сообщений:

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

Учитывая что в такой схеме шардинга не требуется централизованной цепочки, то значит нет “бутылочного” горлышка и шардинг не ограничен по масштабируемости.

Быстрое создания блоков

В данном алгоритме можно задавать очень низкое время формирования блоков, например 1 секунда или даже меньше.

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

В предложенном консенсусе PoM поиск хэша блока происходит практически мгновенно — O(1), что позволяет перестраивать блоки (хвосты цепочек) для нахождения оптимальной цепочки (выполняется максимизация суммы мощностей всех блоков).

Кроме того цепочку лидер можно строить заранее, что позволяет заранее находить майнера-лидера и отправлять ему транзакции текущего блока, таким образом скорость создания и подтверждения блока будет очень высокой — не хуже чем в частично централизованных консенсусах на основе POS/DPOS.

Безопасность

Изменение состава транзакций (данных блоков)

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

Таким образом схема требует на единицу больше подтверждений в отличие от классической схемы PoW.

Атака 51%

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

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

Изменения цепочек может использоваться при атаках вида “двойная трата”.

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

[Продолжение следует…]

Обсудить в Discord!