Proof-of-Stake: взгляд изнутри07.03.2019 03:19

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

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

Ужасаемся под катом.

Крупица истории

На просторах интернета прослеживается зарождение Proof-of-Stake (PoS) в Peercoin после дискуссии на одном из форумов в 2011 году, последующее использование в Novaсoin и дальнейшее распространение в PIVX и прочих форках Bitcoin. Достаточно примитивную PoS-логику вынесли в модуль kernel.h/kernel.cpp, которая и кочует по пространствам форков в виде различных франкенштейнов.

Алгоритм PoS прошёл несколько стадий развития, кто-то даёт им версии. Сейчас варианты PoS разделились по естественным причинам, появился DPoS. Одним из самых передовых решений является протокол Casper в Ethereum.

Любому блокчейну требуется генерация блоков и за кем-то должно быть право построить новый блок. Если в таком блокчейне как система контроля версий Git это делает автор без особой конкуренции, то в криптовалютах идёт ожесточённая борьба за награду блока в рамках Proof-of-Work (PoW) — нахождение такой комбинации переменных входных параметров путём подбора, которая даёт результат, соответствующий детерминировано заданной цели (добыча, майнинг).

PoS заменяет Proof-of-Work (PoW) с целью избежать бесполезной траты ресурсов на майнинг. Вместо этого все входные параметры строго заданы с константной характеристикой на основе существующих сбережений держателей монет. Поэтому PoW требуется как стартовый этап для PoS, если не прибегать к различным вариантам изначального заложенного обогащения создателей монеты.

Зачем?

Экономия электроэнергии примерно так же важна разработчикам и держателям монет как ограничение выбросов парниковых газов для производителей и потребителей. Жестокая правда в другом:

1. проекты на основе PoW подвержены т.н. «атакам 51 процента»: атакующие могут накинуть большие мощности, создать паралелльную цепь, а потом внезапно опубликовать её с иным движением монет по счетам (т.е. двойная трата),
2. майнерам PoW необходимо покрывать свои затраты и вкладываться в наращивание мощностей — это прямой отток капитала из проектов,
3. владельцы сбережений желают поддерживать её покупательную способность путём самонаращивания капитала, а не смотреть на естественную инфляцию.

На живом примере: в ноябре-декабре 2018 были попытки атак; потом в декабре-феврале был ажиотаж как на самую доходную монету для майнинга на видеокартах; курс просел с 2+ до 0.5 USD; после перехода на PoS, курс поднялся до 1 USD уже через неделю и приток инвестиций усилился.

Технические моменты

Внимание: в данном разрезе речь идёт именно о «традиционном» PoS в том виде, как он есть в Peercoin, PIVX и их форках.

Надо понимать, что отсутствует какая-либо централизация и учёт «очков». В данном варианте работает всё тот же принцип удачи как и в PoW.

1. Терминология

Терминология относительно общая, но в различных реализация свои нюансы:

• PoW target — цель = базовая цель, обычно 2^240 (0×0000ffff…), делённая на сложность блока (увеличивает количество нулей спереди).
• Block difficulty — сложность блока относительно базовой цели, детерминировано устанавливаемая на основе текущего темпа роста цепи.
• UTXO — Unspent Transaction Output, пара из хеша транзакции и номер выхода.
• CoinBase — специальная транзакция с индексом 0 в блоке, где содержится вознаграждение.
• Stake или CoinStake — специальная транзакция с индексом 1 в блоке.
• Stake Input — UTXO, который соответствует требованиям для ставки по размеру и возрасту.
• Stake Modifier — специальный детерминировано вычисляемый параметр для каждого Stake Input.
• Stake Hash — результат хеширования, который должен быть арифметически меньше Stake Target.
• Stake Target — то же, что и PoW target, но пропорционально увеличенная суммой Stake Input относительно минимальной ставки.
• Block Signature — подпись блока.
• Fork — разветвление цепи.
• Split — разделение сети.
• Orphan — отброшенные блоки из-за выбора другой альтернативы.

2. Анатомия

Процесс генерации:

1. Находим все UTXO, которые соответствуют требования Stake Input
2. Находим Stake Modifier.
3. Умножаем PoW Target на сумму Stake Input
   
   • в миллионных долях по факту — поэтому 1 MH PoW хешрейта экспериментально выходит равным одной монете.
4. Получаем Stake Hash = H(Stake Modifier, Stake Block Time, UTXO output index, UTXO txid, Current Block Time).
   
   • переменный параметр только Current Block Time
5. Если Stake Hash >= Stake Target, то пытаемся подобрать Current Block Time в допустимом промежутке.
   
   • нужно учитывать возможность переполнения Stake Target при умножении на сумму Stake Input в зависимости от реализации.
6. Запихиваем Coinbase в tx[0], а CoinStake в tx[1].
   
   • бенефициар'ом Coinbase является тот же скрипт (адрес), что и у Stake Input.
7. Подписываем блок.

2.1. Время блока:

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

Нижним всегда задаётся среднее время блоков за последние N блоков, обычно за 11. Это допуск на неточность времени на генерирующих узлах.

Исторический верхний предел был задан для PoW пальцем в небо в 2 часа. Увеличение интервалов уменьшает сложность и делает ветку менее привлекательной — поэтому нет смысла. Зато для PoS смысл есть.

PIVX и другие ограничивают время в будущем в максимум 3 минуты. Некоторые ставят более жёсткое ограничение, но это создаёт проблемы у пользователей. Некоторые реализации PoS решили изменить минимальные интервалы Current Block Time с одной секунды до 15–16 секунд.

2.2. Stake Modifier:

Stake Modifier задумывался как средство для затруднения предсказания и строительства цепи наперёд, но что-то пошло не так…

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

В оригинале берётся промежуток в 64 интервала. Этот промежуток прогрессивно делится на 64 неравные части. Границы округляются к минутам. По границам выбираются существующие блоки и с них берётся по одному последнему биту. Так получается число в 64-бита, чем-то похожее на Nonce.

Интервал в Peercon 20 минут, но ребята из PIVX решили что интервал в 1 минуту, округлённый до минуты — это то, что доктор прописал.

В общем, в некоторых реализациях типа Blackcoin V2+ всё исправлено и Stake Modifier считается от головы, а в Peercoin V03, PIVX, Blackcoin V1 и других от блока Stake Input. Последнее почти полностью уничтожает смысл. Есть предположение что путаница пошла из-за банальной проблемы именования переменных, дальнейших метаморфоз и бездумной копипасты. И сам автор достаточно поздно обнаружил проблему пока всё внимание было сконцентрировано на защите от DoS. Не попадитесь!

2.3. Подпись блока

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

2.4. Скрипт выхода CoinBase и CoinStake

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

2.5 Что и куда?

Есть разные вариации как распоряжаются с суммами в CoinBase и CoinStake. Логика и мотивация в конкретном случае:

1. Суммы должны быть раздельны чтобы избежать даже малейшего варианта потери средств пользователя из-за ошибки обработки.
2. CoinBase сохраняет свои 100 подтверждений, а вот CoinStake может быть потрачен сразу, что конечно оставляет риск двойной траты.
   
   • привязывание к глубине блоков ещё и противоречит цензу по возрасту для использования в качестве Stake Input.
3. CoinBase и CoinStake никогда не должны попадать в mempool, а все основанные на них транзакции должны удаляться при перестройке цепи.

3. Полные блоки против заголовков

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

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

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

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

К слову, стандартный клиент Bitcoin и его форки достаточно долго набирают минимальное стандартное количество исходящих соединений в 8 штук, если какие-то из них срываются по различным причинам. Это было решено асинхронными исходящими соединениями.

4. Форки, сплиты и орфаны

При конкуренции создания блоков, альтернативные цепи в 1–2 звена являются относительно обычным явлением. Более длинные форки в развитых сетях естественным путём происходят только при эпичных сбоях в консенсусе из-за ошибки программирования или глобального разрыва интернета.

Даже при наличии разделения, обычно нет угрозы целостности обработки транзакций, т.к. при отсоединении блоков все транзакции попадают обратно в mempool и включаются уже в другие блоки. Mempool — это временное хранилище транзакций после их создания. Сам mempool сохраняется на диск в последних версиях. Награда же за блок уничтожается. Именно поэтому для наград устанавливается минимальное количество подтверждений (глубина).

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

Главная атака 51% для PoW уже описана выше — она крайне ресурсоёмка, а вот для PoS она становится относительно доступна. По этой причине становится технически возможным плодить множество ветвей из различных звеньев цепи. Одно из классических решений — это запрещать форки ниже определённой глубины.

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

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

При целевом интервале блоков в 1 минуту, критерий старого форк был выбран в 1 час, что примерно соответствует 60% подтверждений CoinBase, а критерий молодости макушки в 15 минут — в 3+ раза выше максимального статистического запаздывания блока.

5. Хеш блока и сплиты

В PoW хеш блока полностью покрывает все данные. Он же используется для проверки относительно цели. В PoS, Stake Hash является отдельным значением, т.к. необходимо исключить возможность его подбора. Это открывает основную угрозу — возможность плодить неограниченное количество различных версий блока на основе одного и того же совпавшего Stake, которыми легко зафлудить и положить сеть или её отдельные узлы.

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

Ещё более фатально возможно это усугубить DoS-баном, что разделит не только цепи, но и саму сеть на разные сегменты.

Возникают и другие проблемы — невозможность использовать Stake из отброшенного блока.

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

Всё равно остаются некоторые моменты, при которых узлы уязвимы к умеренному флуду до момента полной синхронизации.

6. Минимальный возраст

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

Как было упомянуто ранее, локальный узел должен обработать все блоки до временной границы возраста чтобы иметь возможность проверить что Stake Input а) имеет место быть b) действительно является UTXO и не был потрачен.

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

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

Слишком большая планка для возрастного ценза UTXO негативно сказывается на пользователях, которые хотят потратить или объединить часть своих монет.

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

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

7. Что лучше N UTXO по минимальной сумме или один UTXO с N суммой?

Здесь сама напрашивается аналогия: что лучше одна пушка с точностью 0.9 или три пушки с точностью 0.3, но при вероятностях порядка ½^20 результаты таких расчётов казалось бы нивелируются. Немного карты спутывает ценз зрелости.

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

В данный момент на основе практических экспериментов и теоретических расчётов, сгруппированные в большие UTXO суммы приносят больше блоков. Вдобавок, меньшее количество UTXO требует меньше работы CPU. Кто-то утверждает и обратное.

Поэтому думайте сами.

8. Забегание блоков вперёд

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

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

Таким путём сеть защищается и от гипотетических преждевременно отосланных блоков, Stake Input которых невозможно использовать в ближайшие 60 секунд с таким же Stake Modifier’ом из-за DoS-защиты. Как бы двойное наказание за жульничество со временем.

9. Небольшой чеклист

1. Stake Input должен быть действительным UTXO до fork point:
   
   • в случае главной цепи fork point — это tip,
   • в случае альтернативной цепи — UTXO после fork point может привести к само-DoS при переключении,
   • само собой подразумевается, что UTXO не должен быть в mempool’е.
2. Не принимать CoinStake в mempool при перестройке основной цепи:
   
   • такое же происходит с CoinBase,
   • это может уничтожить цепь транзакций (маловероятно).
3. Не принимать форки от старых блоков, если верхушка вполне себе живая.
4. Возрастной ценз в абсолютных единицах времени для Stake Input необходим для стабильности и безопасности.
5. Stake Hash должен изменяться только от времени блока.
6. Stake Modifier не должен быть привязан к блоку Stake Input.
7. Работа с заголовками блоков требует особой обработки в сети и при переиндексировании.
8. CoinStake записываются в локальном кошельке и требуют некоторых изменений для корректного отображения орфанов.
9. PoS майнеры скорее всего имеют достаточно косяков и требуют доработки напильником.
10. Re-index требует доработки, т.к. работает по аналогии с заголовками — сначала грузит и проверяет только индекс блоков, а потом только пытается обработать блоки.
11. Если переход на PoS не жёстко задан, а через spork, то его нужно ловить на загрузке, т.к. sporks не сохраняются.
12. Checkpoints в Dash и Bitcoin практически бутафория и требует очень серьёзной доработки.
13. Если форк Dash до версии 0.13, то есть проблемы с обработкой данных мастернод в режиме использования простого пользователя.
    
    • При частом перезапуске клиента, представление сети искажается.
    • Лучше просто игнорировать кеш, если запущен в графическом режиме.
14. Изменить выбор лучшего блока с учётом времени блока.
15. В некоторых операциях Bitcoin присутствует неоправданная проверка уже проверенных блоков при чтении с диска.
16. Кошелёк может пытаться отсылать в сеть и в mempool CoinStake из орфанов.

Внедрение в жизнь

Теперь немного о реальной истории. Первые полгода mainnet прекрасно работал на PoW и давление от майнеров не сильно ощущалось, не смотря на то, что маркетинг изначально пытался продавить PoS, предвидя возможные проблемы по своему опыту. PoS был запланирован при переходе на платформу Ethereum после внедрения Casper’а.

Официальный GPU майнер был доведён до ума и даже чем-то превосходил своего донора — ethminer’а. Был сделан официальный пул и несколько сторонних с общим хешрейтом 150–200 GH (ethash). В какой-то момент цена стремительна пошла вверх давление от майнеров стало ощутимым и вопрос досрочного перехода на PoS встал ребром.

В качестве донора была установка взять PoS ядро из PIVX 2.x как «проверенного временем и стабильного». Отсутствие каких-либо автоматических тестов в PIVX должно было насторожить автора сразу, но не тем менее основная головная боль заключалась в необходимости прикрутить всё остальное, описанное выше. Лишь потом автор узнал о всей той боли разработчиков, которые по неосмотрительности брали PIVX 2.x за основу своих проектов. Благо сам проект основывался на Dash и был благополучно обновлён до последней версии ветки 0.12 с множеством изменений из основного Bitcoin’а.

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

Подготовительные работы

Документация

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

Первое приближение

В изначальном варианте были перенесены все изменения PoS из PIVX с учётом более новой базовой версии Bitcoin/Dash. Некоторые изменения вроде индикатора CoinStake и сохранения последнего бита хеша в отдельном поле показались чрезмерными. Поэтому было решено максимально сузить PoS логику до отдельного модуля.

В этом процессе был упущен нюанс, что в индексе блока сохраняется Stake Modifier не для Stake Hash текущего блока, а для использования связанных с ним Stake Input в последующих блоках. Из-за этого вышел небольшой каламбур с логикой, но из-за другой упомянутой проблемы PIVX это практически не проявляется.

Динамичные чекпойнты

Первое и главное что вы захотите в своих проектах — это чтобы действительно надёжно работали чекпойнты. Лишь некоторые из проблем:

1. Они не работают в принципе и могут легко привести к нерабочей базе.
2. Они не интегрированы на этапе загрузки и соответственно бесполезны.
3. Отмеченные как некорректные блоки не восстанавливаются — т.е. если старый клиент сломает, то даже новый уже не сможет работать.
4. При выборе наилучшего блока не учитывается, что где-то в истории может быть некорректный предок, что в лучшем случае приведёт к отказу в работе.

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

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

Переход на PoS не должен быть жёстко зашит

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

Новая версия протокола

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

Публичное тестирование

Более одной недели добровольцы мучили testnet, но благо проблем консенсуса не было выявлено.

Для testnet был установлен ценз возраста в 3 минуты вместо 1 часа для mainnet, что подтвердило предположение о необходимости достаточно большого значения.

Калькулятор доходности

В отличии от PoW хешрейта, с PoS казалось бы сложно сделать какую-то аппроксимацию, но использование миллионных долей монеты как бы само намекает на делитель 1e6 для стандартных приближений по методологии для PoW.

На основе этих данных возможно вычислить среднее время между нахождением блоков. По опыту mainnet оказалось что к нему следует добавить возрастной ценз для Stake Input.

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

Переход на PoS в жизни

За сутки до часа X был установлен spork с номером первого PoS блока. Из-за ухода майнеров и нестабильности в сложности сети, блок пришёл на два часа раньше.

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

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

Ложка дёгтя

Обнаруженный после запуска недосмотр в Stake Modifier немного огорчил. Вышла ещё более кривая калька с кривой кальки. С другой стороны PIVX ведь как-то живёт… Безусловно, это необходимо было бы исправить, если бы не переход на кодовую базу Ethereum, чего и всем желается.

Заключение

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

Примечание: в статье намерено убрано название и какие-то прямые отсылки на ресурсы проекта чтобы избежать ложных обвинений в рекламе.

Зеркало на GitHub со всей кодовой базой как она есть: https://github.com/energicryptocurrency/energi

© Habrahabr.ru