Объяснение Proof-of-History из документации Solana

От переводчика

Перевод Solana whitepaper осуществлён в рамках прикладного курса “Веб3-разработчик”, где мы рассматриваем и обсуждаем архитектуры различных блокчейн платформ и разработку смарт-контрактов под эти платформы. 

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

В этой Белой Книге описывается основная концепция Solana - доказательство истори (Proof-of-History, PoH), кроме PoH в Solana есть другие концепции, которые полагаются на PoH. Про другие архитектурные решения будет рассказано в других статьях.

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

Вопросы принимаются в комментарии или личном сообщении.

Юридическая оговорка. Ничто в этой статье не является предложением о продаже или предложением о покупке каких-либо токенов. Solana публикует эту "Белую книгу" исключительно для получения отзывов и комментариев от общественности. Ничто в этой Белой книге не должно рассматриваться или считаться как гарантия или обещание того, как будет развиваться Solana. В данной Белой Книге изложены текущие планы, которые могут быть изменены по собственному усмотрению команды Solana, и успех которых будет зависеть от многих факторов, находящихся вне контроля Solana, включая рыночные факторы. 

Аннотация  

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

В данной работе также предлагаются два алгоритма, использующие свойства сохранения времени в блокчейне на основе PoH: 

• алгоритм PoS, который может восстанавливаться после разделения сети;

• эффективное потоковое доказательство репликации (PoRep).

Комбинация PoRep и PoH обеспечивает защиту от подделки блокчейна в отношении времени (упорядочивания) и хранения.

Протокол изучен на сети со скоростью 1 гбит/с, достигнута пропускная способность до 710,000 транзакций в секунду.

Введение 

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

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

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

Участники сети 

Как показано на рисунке 1, в любой момент времени один из узлов системы является Лидером, который создаёт PoH-последовательность, обеспечивая в сети глобальную согласованность чтения и проверяемый ход времени. 

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

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

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

Доказательства истории 

Доказательство истории (PoH) - это последовательность вычислений, которая может криптографически подтвердить факт прохождения некоторого количества времени между двумя событиями. Для этого используется криптографически защищенная функция (Функция проверяемой задержки, ФПЗ), написанная таким образом, что:

• выход не может быть предсказан по входу;

• эта функция должна быть полностью выполнена, чтобы создать выход. 

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

Данные могут быть занесены в эту последовательность путем добавления данных (или хеша некоторых данных) в состояние функции. 

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

Описание

С помощью криптографической хеш-функции, выход которой невозможно предсказать без запуска функции (например, stribog, sha256, ripemd и т.д.). Пример:

1. запустите функцию от некоторого случайного начального значения - первый вход;

2. возьмите выход этой функции;

3. снова передайте его в качестве входа в ту же функцию;

4. запишите количество вызовов функции и её выход при каждом вызове. 

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

Например: 

Где hashN представляет собой выход (выходное значение) хеш-функции.

Необходимо публиковать только подмножество хешей и их порядком в определенном интервале. Например:

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

Таким образом, из структуры данных можно сделать вывод, что между индексом 0 и индексом 300 прошло реальное время. 

На Рисунке 2 хеш 62f51643c1 был получен при счетчике 510144806912, а хеш c43d862d88 - при счетчике 510146904064. Следуя ранее рассмотренным свойствам алгоритма PoH, мы можем считать, что между счётчиком 510144806912 и счётчиком 510146904064 прошло реальное время.

Временная метка для событий 

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

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

Пример. 

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

2. Происходит какое-то внешнее событие, например, была сделана фотография или созданы произвольные цифровые данные: 

hash336 вычисляется из добавленных двоичных данных hash335 и photo_streebog. Порядок и photo_streebog записываются как часть выхода (выходных данных) последовательности. Таким образом, любой, кто проверяет эту последовательность, может воссоздать это изменение в последовательности. 

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

Таблица 1. PoH-последовательность с 2-мя событиями

В последовательности, представленной в Таблице 1, photo2_streebog была создана до hash600, а photo1_streebog - до hash336. Вставка данных в последовательность хешей приводит к изменению всех последующих значений в последовательности. До тех пор, пока используемая хеш-функция устойчива к коллизиям, а данные были добавлены, должно быть вычислительно невозможно предварительно вычислить любые будущие хеши-последовательности на основе предварительного знания о том, какие данные будут включены в последовательность.  

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

В примере на Рисунке 3 вход cfd40df8... был вставлен в PoH-последовательность. Счетчик, в который он был вставлен, равен 510145855488, а состояние, в которое он был вставлен равно 3d039eef3. Все будущие создаваемые хеши модифицируются этим изменением последовательности, это изменение обозначено изменением цвета на рисунке. 

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

Проверка 

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

Например:

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

Общее количество хешей / Количество хешей в секунду для 1 ядра.

Ожидаемое время проверки правильности последовательности будет: 

Общее количество хешей / (Количество хешей в секунду на ядро * Количество ядер, доступных для проверки)  

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

Горизонтальное масштабирование 

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

Выходы обоих создателей необходимы для восстановления полного порядка событий в системе.

Здесь Создатель A получает пакет данных (hash1b) от Создателя Б, пакет содержит последнее состояние Создателя Б и последнее состояние, которое Создатель Б наблюдал от Создателя А. 

Так как следующий хеш Создателя А зависит от хеша Создателя Б, мы можем вывести, что hash1b произошел за некоторое время до hash3a. Это свойство может быть транзитивным, поэтому если три создателя синхронизированы через одного общего создателя A ↔ Б ↔ В, то мы можем проследить зависимость между A и В, даже если они не были синхронизированы напрямую.

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

На Рисунке 5 два создателя используют хеши друг друга как входные значения для функции и записывают эту операцию. Изменение цвета указывает на то, что полученные от другого создателя данные изменили последовательность. Созданные хеши, которые смешиваются в каждом потоке, выделены жирным шрифтом.

Синхронизация является транзитивной A ↔ Б ↔ В. Существует доказуемый порядок событий между A и В через Б. 

Масштабирование таким образом происходит за счет доступности. 10 × 1 гбит/с соединений с доступностью 0,999 будут иметь доступность 0,999^10 = 0,99.  

Согласованность  

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

Вредоносный PoH-создатель может создать вторую скрытую последовательность с событиями в обратном порядке, если он имеет доступ ко всем событиям сразу или способен создать более быструю скрытую последовательность.

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

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

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

Проверка этих данных требует проверки подписи и поиска хеша в последовательности хешей, предшествующих этому. Порядок проверки: 

1. (Подпись, Открытый_ключ, hash30a, Данные_События_3) = Событие_3

2. Проверка(Подпись, Открытый_ключ, Событие_3) 

3. Найти(hash30a, PoH-последовательность) 

На Рисунке 6 входы предоставленные пользователем, зависят от хеша 0xdeadbeef..., существующего в созданной последовательности за некоторое время до его вставки. 

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

Накладные расходы 

4000 хешей в секунду создают дополнительные 160 килобайт данных и потребуют доступа к GPU с 4000 ядрами и примерно 0,25-0,75 миллисекунд времени для проверки.

Атаки 

Обратный ход 

Создание обратного порядка потребует от злоумышленника начать вредоносную последовательность после второго события. Эта задержка должна позволить любым не злонамеренным одноранговым узлам сообщить о первоначальном порядке.

Скорость 

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

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

Атаки на основе старых ключей 

Атаки на основе старых ключ (или long-range attacks) включают в себя получение старых выброшенных закрытых ключей пользователей блокчейна и создание фальсифицированной версии блокчейна. PoH обеспечивает некоторую защиту от таких атак. Злонамеренный пользователь, получивший доступ к старым закрытым ключам, должен будет воссоздать историческую запись, которая займет столько же времени, сколько и оригинальная запись, которую он пытается подделать. Для этого потребуется доступ к более быстрому процессору, чем тот, который используется в сети в настоящее время, иначе злоумышленник никогда не сможет догнать его по длине истории.

Кроме того, единый источник времени позволяет построить более простое доказательство репликации (Proof of Replication, PoRe). Поскольку сеть спроектирована таким образом, что все участники сети будут полагаться на единую историчность запись событий.

PoRep и PoH вместе должны обеспечить защиту хранения данных и времени от подделки блокчейна. 

Консенсус

Описание 

Proof of Stake в Solana предназначен для:

• быстрого подтверждения текущей последовательности, созданной PoH-создателем;

• для голосования и выбора следующего PoH-создателя;

• для наказания любых недобросовестных Подтверждающих.

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

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

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

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

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

Обязательства 

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

Голосование 

Предполагается, что PoH-создатель может публиковать подпись состояния в заранее определенный период времени. Каждая личность (разместившая обязательство)  должна подтвердить эту подпись, опубликовав свою собственную подпись состояния. Голосование - это простое голосование "за", без "против".

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

Закрытие обязательств

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

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

Выборы 

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

Для выбора новой последовательности (нового лидера) требуется супербольшинство подтверждений. Если новый лидер терпит неудачу до получения супербольшинства подтверждений, выбирается следующий по силе Подтверждающий, и требуется новый набор подтверждений.

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

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

Причины выборов 

Разветвление PoH-создателя

PoH-создатели содержат идентификатор, который подписывает созданную PoH-последовательность. Если идентификатор скомпрометирован, то может произойти Разветвление. Разветвление обнаруживается, когда две разные PoH-записи были размещены одним и тем же PoH-идентификатором.

Исключения во время выполнения 

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

Сетевые задержки времени

Сетевая задержка вызовет выборы. 

Штрафование 

Если Подтверждающий голосует по двум отдельным PoH-последовательностями, то происходит штрафование. Доказательство злонамеренного голосования изымает из обращения монеты Обязательства и добавляет их в майнинговый пул. 

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

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

Выборы Вторичного

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

Доступность  

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

Проверяющие в Proof of Stake блокируют некоторое количество монет в стейк, что позволяет им голосовать за определенный набор транзакций. Транзакция с блокировкой монет вводится в PoH-последовательность, как и любая другая транзакция. Чтобы проголосовать, PoS-проверяющий должен подписать хеш состояния, поскольку он был вычислен после обработки всех транзакций до определенной позиции в PoH-реестре. Это голосование также вводится в PoH-последовательность как транзакция. Просматривая PoH-реестр, мы можем сделать вывод о том, сколько времени прошло между каждым голосованием, а если произошло Разделение, то как долго каждый Проверяющий был недоступен.

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

Восстановление

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

Окончательность 

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

Атаки 

Трагедия общин  

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

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

Сговор с PoH-создателем 

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

Цензурирование

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

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

Атаки на основе старых ключей

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

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

ASIC-атаки  

В этом протоколе существуют две возможности для ASIC-атак - во время разделения и обман срока при Окончательности.

Для ASIC-атак во время Разделения, скорость, с которой снимаются обязательства, нелинеен, и для сетей с большими Разделением скорость на порядки медленнее, чем ожидаемая прибыль от ASIC-атаки.

Для ASIC-атак во время Окончательности уязвимость позволяет византийским Подтверждающим, имеющим ставку обязательства, дождаться подтверждений от других узлов и передать свои голоса сотрудничающему PoH-создателю. Затем PoH-создатель может использовать свой более быстрый ASIC для создания хешей за 500 мс за меньшее время и обеспечить сетевое взаимодействие между PoH-создателем и сотрудничающими узлами. Но если PoH-создатель также является византийским, нет причин, по которым византийский создатель не сообщил бы точный счетчик, когда он ожидает вставить сбой. Этот сценарий ничем не отличается от того, что PoH-создатель и все сотрудничающие узлы разделяют одну и ту же личность, имеют один общий пакет акций и используют только один набор оборудования.

Потоковое доказательство репликации 

Описание 

Filecoin предложил консенсус Proof of Replication (далее – PoRep). Целью PoRep в Solana является быстрая и потоковая проверка Доказательства репликации данных, которая осуществляется благодаря отслеживанию времени в последовательности создаваемых PoH. PoRep не используется в качестве алгоритма консенсуса, но является полезным инструментом для учета затрат на хранение истории или состояния блокчейна для повышения доступности данных.

Алгоритм

Как показано на Рисунке 7, CBC-шифрование шифрует каждый блок данных последовательно, используя ранее зашифрованный блок для XOR входных данных.  

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

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

Вычисляется хеш дерева Меркла с выбранным PoH-хешем, добавляемым к каждому фрагменту.

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

После периода из N доказательств данные повторно шифруются с помощью нового ключа CBC.   

Проверка 

При наличии N ядер каждое ядро может осуществлять потоковое шифрование для каждого идентификатора. Всего требуется 2_блока ∗ N_ядер, так как предыдущий зашифрованный блок необходим для создания следующего. Затем каждое ядро может быть использовано для создания всех доказательств, вытекающих из текущего зашифрованного блока.

Ожидается, что общее время проверки доказательств будет равно времени, затрачиваемому на шифрование. Сами доказательства потребляют мало случайных байт из блока, поэтому объем данных для хеширования значительно меньше размера зашифрованного блока. Количество идентификаторов репликации, которые могут быть проверены одновременно, равно количеству доступных ядер. Современные графические процессоры имеют в своем распоряжении 3500+ ядер, хотя и с тактовой частотой на ½-⅓ меньше, чем у CPU.  

Ротация ключа 

Без ротации ключей одна и та же зашифрованная репликация может создавать дешевые доказательства для нескольких PoH-последовательностей. Ключи периодически меняются, и каждая репликация заново шифруется новым ключом, который привязан к уникальной PoH-последовательности. Обращение должно быть достаточно медленным, чтобы можно было проверять доказательства репликации на аппаратном обеспечении GPU, которое работает медленнее, чем CPU, на каждое ядро.

Выбор хеша 

PoH-создатель публикует хеш, который будет использоваться всей сетью для шифрования доказательств репликации и для использования в качестве создателя псевдослучайных чисел для выбора байтов в быстрых доказательствах. 

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

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

Подтверждение доказательств 

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

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

Атаки 

Спам  

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

PoRep, разработанное в данной работе, позволяет дешево проверять любые дополнительные доказательства, поскольку они не занимают дополнительного места. Но каждое доказательство будет потреблять 1 ядро времени шифрования. Цель репликации должна быть установлена на максимальный размер легкодоступных ядер. Современные графические процессоры поставляются с 3500+ ядрами. 

Частичное стирание 

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

Например, пользователь, хранящий 1 терабайт данных, стирает один байт из каждого 1-мегабайтного блока. Одно доказательство, которое выбирает 1 байт из каждого мегабайта, будет иметь вероятность столкновения с любым стертым байтом 1 - (1 - 1/1, 000, 0000)1,000,000 = 0.63. После 5 доказательств вероятность равна 0,99. 

Сговор с PoH-создателем 

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

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

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

Отказ в обслуживании 

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

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

Трагедия общин 

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

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

Архитектура системы

Компоненты 

Лидер, PoH-создатель 

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

Состояние 

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

Таблица транзакций содержит: 

В общей сложности 32 байта.

Таблица PoS-обязательств содержит:

В общей сложности 64 байта.

Проверяющий, репликация состояний 

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

Сеть может быть сконфигурирована с минимальным размером PoS обязательства и требованием к одному идентификатору репликатору на обязательство.

Подтверждающие

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

Ограничения сети 

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

Формат входящего пакета: 

Размер 20 + 8 + 16 + 8 + 32 + 3232 = 148 байт. 

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

С полезной нагрузкой:

С полезной нагрузкой минимальный размер: 176 байт 

Пакет PoH-последовательности содержит:

• текущий хеш, 

• счетчик, 

• хеш всех новых сообщений, добавленных к PoH-последовательности, 

• хеш-состояния после обработки всех сообщений. 

Этот пакет отправляется раз в N сообщений. PoH-пакет:  

Минимальный размер выходного пакета составляет: 132 байта 

При сетевом соединении 1 Гбит/с максимальное количество транзакций: 1 гигабит в секунду / 176 байт = 710,000 ТвС максимум. Ожидается некоторая потеря 1-4% из-за кадрирования Ethernet. Резервная емкость, превышающая целевой объем для сети, может быть использована для повышения доступности путем кодирования выходного сигнала кодами Рида-Соломона и его отправки на доступные нижележащие Проверяющих. 

Вычислительные пределы 

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

Серверы проверки ECDSA на базе GPU показали экспериментальные результаты в 900,000 операций в секунду. 

Пределы памяти  

Наивная реализация состояния в виде заполненной на 50% хеш-таблицы с 32-байтовыми записями для каждого аккаунта теоретически позволит уместить 10 миллиардов аккаунтов в 640 ГБ.  Случайный доступ к этой таблице в стабильном состоянии измеряется на уровне 1,1 ∗ 10^7 записей или чтений в секунду. Исходя из расчета 2 чтения и 2 записи на транзакцию, пропускная способность памяти позволяет обрабатывать 2,75 млн транзакций в секунду. Данные измерения проводились на экземпляре AWS 1 Tb x 1.16x. 

Высокоэффективные смарт-контракты 

Смарт-контракты - это обобщенная форма транзакций. Это программы, которые выполняются на каждом узле и изменяют состояние. Solana использует расширенный байткод Berkeley Packet Filter как быстрый и простой для анализа и JIT-байткод для создания и выполнения смарт-контрактов.

Одним из его основных преимуществ является интерфейс внешних функций (FFI) с “нулевой стоимостью”. Встроенные функции (встройки), которые реализуются напрямую на платформе, могут вызываться программами. Вызов встройки приостанавливает работу этой программы и планируется выполнение этой встроенной функции на высокопроизводительном сервере. Встройки объединяются в группы для параллельного выполнения на GPU.

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

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

Бэкенд eBPF включен в LLVM с 2015 года, поэтому любой язык LLVM может быть использован для написания смарт-контрактов. В ядре Linux он присутствует с 2015 года, а первые итерации байткода существуют с 1992 года. За один проход можно проверить корректность eBPF, определить его требования к времени выполнения и памяти и преобразовать его в инструкции x86.

Выводы

Если вы прочитали Белую бумагу полностью, то поняли, что на многие вопросы не дано формальных ответов. Например: описания атак, ответы на которые не имеют формального обоснования.

В других хабр статьях обсудим другие концепции Solana (TowerBFT, Turbine, Sealevel, Gulf Stream), а также разработку смарт-контратков для Solana. А также сравним Solana с другими блокчейн платформами.

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

Все, кто интересуется платформами отличными от Ethereum и прочими вопросами, которые редко обсуждаются, приглашаются на курс “Веб3-разработчик” (старт потока в декабре, доп.инфа тут @druzhcom "или в личных сообщениях @didexBot). Где мы обсуждаем особые, узкие, специализированные темы в рамках блокчейн технологий. И конечно разрабатываем смарт-контракты для различных блокчейнов. Итоговым результатом обучающихся является создание проекта на актуальную рыночную тему и написание совместной Хабр-статьи по проблематике создаваемого проекта.

Вопрос для ответа в комментарии: про какую платформу вы хотели бы почитать хабр-статью?

UPD: после многих негативных (крайне "конструктивных" по содержательной части) комментариев о неправильном использовании перевода слова whitepaper, во втором абзаце исправлено с "Белая бумага" на "Белая книга". В других местах было и остаётся "Белая книга". Других претензий и возражений у страждущей аудитории нет.