Файл: Аннотация Цель данной работы предоставить первое описание блокчейнплатформы ton (The Open Network) и связанных с ней технологий одноранговых сетей, распределенного хранилища и хостинга..pdf

17 2.3. Состояние блокчейна, учетные записи и хэш-карты
Если в дереве N листьев (т. е. наша хэш-карта содержит N значений), то имеется ровно
N - 1 промежуточных вершин. Вставка нового значения всегда включает в себя разделение существующего ребра путем вставки новой вершины в середину и добавления нового листа в качестве другого дочернего элемента этой новой вершины.
Удаление значения из хэш-карты приводит к обратному эффекту: лист и его родитель удаляются, а родитель родителя и другой его дочерний элемент становятся напрямую связанными.
2.3.8. Деревья Merkle Patricia. При работе с блокчейнами мы хотим иметь возможность сравнивать деревья Patricia (то есть хэш-карты) и их поддеревья, сводя их к одному хэш-значению. Классический способ достижения этой задачи – использование дерева Merkle. По сути, мы хотим описать способ хэширования объектов h типа Hashmap(n, X) с помощью хэш-функции HASH, определенной для двоичных строк, при условии, что мы знаем, как вычислять хэш-значения HASH(X) объектов x: X (например, путем применения хэш-функции HASH к двоичной сериализации объекта x).
Можно определить HASH(h) рекурсивно следующим образом:
Здесь s.t обозначает конкатенацию (битовых) строк s и t, а CODE (S) - это префиксный код для всех битовых строк s. Например, можно закодировать 0 на 10, 1 на 11 и конец строки на 0.
5
Позже мы увидим (см. 2.3.12 и 2.3.14), что это (слегка измененная) версия рекурсивно определенных хэшей для значений произвольных (зависимых) алгебраических типов.
2.3.9. Пересчет хэшей дерева Merkle. Этот способ рекурсивного разделения HASH
(h), называемый хэшем дерева Merkle, обладает следующим преимуществом: если один явно хранит HASH(h') вместе с каждым узлом h' (в результате получается структура, называемая деревом Merkle, или, в нашем случае, деревом Merkle Patricia), необходимо пересчитывать не более n хэшей при добавлении, удалении или изменении элемента в хэш-карте.
Таким образом, если кто-то представляет глобальное состояние блокчейна подходящим хэшем дерева Merkle, его можно легко пересчитывать после каждой транзакции.
2.3.10. Доказательства Меркла. На основании предположения (7) «инъективности» выбранной хэш-функции HASH, можно построить доказательство того, что для данного значения z HASH(h), h: Hashmap(n, X) имеет место hget(h)(i) = x для некоторых i: 2
n и x: X. Такое доказательство будет состоять из пути в дереве Merkle
Patricia от листа, соответствующего i, до корня, дополненного хэшами всех братьев и сестер всех встречающихся узлов на этом пути.
Таким образом, неполная нода
6
, знающая только значение HASH(h) для некоторой хэш-карты h (например, постоянное хранилище смарт-контракта или глобальное состояние блокчейна), может запросить у полной ноды
7
не только значение x = h[i] = hget(h)(i), но такое значение вместе с доказательством Меркла, начиная с уже известного значения HASH(h).
Затем, в предположении (7), неполная нода может сама проверить, что x действительно является правильным значением h [i].

18 2.3. Состояние блокчейна, учетные записи и хэш-карты
В некоторых случаях клиент может захотеть получить вместо этого значение y =
HASH(X) = HASH(h[i]) - например, в случае очень большого значения x (например, самой хэш-карты). Тогда вместо этого можно предоставить доказательство Меркла для (i, y). Если x также является хэш-картой, то второе доказательство Меркла, начиная с y = HASH(X), может быть получено из полной ноды, чтобы предоставить значение x[j] = h[i][j] или только его хэш.
2.3.11. Важность доказательств Меркла для многозвенной системы, такой как
TON. Обратите внимание, что нода обычно не может быть полной нодой для всех шардчейнов, существующих в среде TON. Обычно эта нода является полной только для некоторых шардчейнов – например, шардчейнов, которые содержат ее собственную учетную запись, смарт- контракт, с которым она работает, либо шардчейнов, для которых эта нода была назначена валидатором. Для других шардчейнов это должна быть неполная нода, иначе требования к хранилищу, вычислениям и пропускной способности сети будут непомерно высокими. Это означает, что такая нода не может напрямую проверять утверждения о состоянии других шардчейнов; она должна полагаться на доказательства Меркла, полученные из полных нод для этих шардчейнов. Этот процесс является таким же безопасным, как и собственно проверка, если только (7) он не завершится неудачей (т. е. не будет обнаружен хэш-конфликт).
2.3.12. Особенности виртуальной машины TON. Виртуальная машина TON или
TVM, используемая для запуска смарт-контрактов в мастерчейне и исходном воркчейне, значительно отличается от обычных систем, вдохновленных виртуальной машиной Ethereum (EVM). TVM работает не только с 256-битными целыми числами, но и фактически с (почти) произвольными «записями», «структурами» или «типами суммы-произведения», что делает ее более подходящей для выполнения кода, написанного на высокоуровневых языках программирования
(особенно функциональных языках). По сути, TVM использует тегированные типы данных, аналогичные тем, которые используются в реализациях Prolog или Erlang.
Сначала можно подумать, что состояние смарт-контракта TVM - это не просто хэш- карта 2 256
→ 2 256
, от Hashmap (256, 2 256
), но (в качестве первого шага) Hashmap (256,
X), где X - это тип с несколькими конструкторами, позволяющий хранить, помимо
256-битных целых чисел, другие структуры данных, включая, в частности, другие хэш-карты Hashmap (256, X). Это означало бы, что ячейка хранилища TVM
(постоянного или временного) - переменная или элемент массива в коде смарт- контракта TVM - может содержать не только целое число, но и целую новую хэш- карту. Конечно, это будет означать, что ячейка содержит не только 256 бит, но также, скажем, 8-битный тег, описывающий, как эти 256 бит должны интерпретироваться.
5
Можно показать, что это кодирование оптимально примерно для половины всех меток ребер дерева
Patricia со случайными или последовательными индексами. Остальные граничные метки, вероятно, будут длинными (т. е. длиной почти 256 бит). Следовательно, почти оптимальным кодированием для граничных меток является использование приведенного выше кода с префиксом 0 для «коротких» битовых строк и кодирование 1, а затем девять битов, содержащих длину l = |s| битовой строки s, а затем l битов s для «длинных» битовых строк (l ≤ 10).
6
Неполная нода - это узел, который не отслеживает полное состояние шардчейна; вместо этого он сохраняет минимальную информацию, такую как хэши нескольких самых последних блоков, и полагается на информацию, полученную от полных нод, когда возникает необходимость проверить некоторые части полного состояния.
7
Полная нода - это узел, отслеживающий полное актуальное состояние рассматриваемого шардчейна.

19 2.3. Состояние блокчейна, учетные записи и хэш-карты
Фактически, значения не обязательно должны быть точно 256-битными. Формат значения, используемый TVM, состоит из последовательности необработанных байтов и ссылок на другие структуры, смешанных в произвольном порядке, причем некоторые байты дескриптора вставлены в подходящие места, что дает возможность отличать указатели от необработанных данных (например, строки или целые числа)
(см. 2.3.14)
Этот формат необработанных значений может использоваться для реализации произвольных алгебраических типов суммы-произведения. В этом случае значение будет сначала содержать необработанный байт, описывающий используемый
«конструктор» (с точки зрения высокоуровневого языка программирования), а затем другие «поля» или «аргументы конструктора», состоящие из необработанных байтов и ссылок на другие структуры в зависимости от выбранного конструктора (см. 2.2.5).
Однако TVM ничего не знает о соответствии конструкторов и их аргументов; смесь байтов и ссылок явно описывается определенными байтами дескриптора
8
Хэширование дерева Merkle распространяется на произвольные структуры - для вычисления хэша такой структуры все ссылки рекурсивно заменяются хэшами объектов, на которые имеется ссылка, а затем вычисляется хэш результирующей байтовой строки (включая байты дескриптора).
Таким образом, хэширование дерева Merkle для хэш-карт, описанное в п. 2.3.8, представляет собой просто простой способ хэширования для произвольных
(зависимых) алгебраических типов данных, применяемый к типу Hashmap (n, X) с двумя конструкторами
9

20 2.3. Состояние блокчейна, учетные записи и хэш-карты ячеек, а каждая ячейка имеет четко определенный (рекурсивно вычисленный) хэш
Меркла, фактически зависящий от всего поддерева, имеющего корень в этой ячейке, мы можем предоставить «обобщенные доказательства Меркла» для (частей) значений произвольных алгебраических типов, предназначенные для доказательства того, что определенное поддерево дерева с известным хэшем Меркла принимает определенное значение или значение с определенным хэшем. Это обобщает подход в п. 2.3.10, где были рассмотрены только доказательства Меркла для x[i] = y.
2.3.16. Поддержка сегментирования в структурах данных TON VM. Только что мы в общих чертах обрисовали, как виртуальная машина TON, не будучи чрезмерно сложной, поддерживает произвольные (зависимые) алгебраические типы данных на высокоуровневых языках смарт-контрактов. Однако для шардинг крупных (или глобальных) смарт-контрактов требуется специальная поддержка на уровне ВМ TON.
С этой целью в систему была добавлена специальная версия типа hashmap, равная
«карте» Account -->X . Эта «карта» может показаться эквивалентной Hashmap (m, X), где Account = 2
m
, однако, когда шард разделяется на два шарда, либо два шарда объединяются, такие хэш-карты автоматически разделяются на две хэш-карты или объединяются обратно, что позволяет сохранить только те ключи, которые принадлежат соответствующему шарду.
2.3.17. Плата за постоянное хранилище. Примечательной особенностью блокчейна
TON является плата, взимаемая со смарт-контрактов за хранение их постоянных данных (то есть за увеличение состояния блокчейна в целом). Этот процесс выглядит следующим образом:
В каждом блоке декларируются два стейка, номинированные в основной валюте блокчейна (обычно это монета TON): цена за хранение одной ячейки в постоянном хранилище и цена за хранение одного необработанного байта в какой-либо ячейке постоянного хранилища. Статистика по общему количеству ячеек и байтов, используемых каждой учетной записью, сохраняется как часть ее состояния, поэтому, умножив эти числа на два стейка, указанные в заголовке блока, мы можем вычислить платеж, который будет вычтен из баланса счета для хранения его данных между предыдущим блоком и текущим.
Однако плата за использование постоянного хранилища взимается не для каждой учетной записи и смарт-контракта в каждом блоке. Вместо этого порядковый номер блока, в котором этот платеж был взыскан в последний раз, сохраняется в данных учетной записи, и когда с учетной записью выполняется какое-либо действие
(например, перенос стоимости, либо получение или обработка сообщения смарт- контрактом), то плата за использование хранилища для всех блоков с момента предыдущего такого платежа вычитается из баланса аккаунта перед выполнением каких-либо дальнейших действий. Если после этого баланс учетной записи станет отрицательным, учетная запись будет уничтожена.
8
Эти два байта дескриптора, присутствующие в любой ячейке TVM, описывают только общее количество ссылок и общее количество необработанных байтов; ссылки хранятся вместе либо до, либо после всех необработанных байтов.
9
Фактически LEAF и NODE являются конструкторами вспомогательного типа HashmapAux (n, X). Тип
Hashmap (n, X) имеет конструкторы ROOT и EMPTYROOT, причем ROOT содержит значение типа
HashmapAux(n, X).
10
Логически; представление «набор ячеек», описанное в 2.5.5, идентифицирует все повторяющиеся ячейки, преобразовывая это дерево в ориентированный ациклический граф при сериализации.

21 2.3. Состояние блокчейна, учетные записи и хэш-карты
Воркчейн может объявить некоторое количество байтов необработанных данных для каждой учетной записи «бесплатными» (т. е. не участвующими в платежах за постоянное хранилище) для создания «простых» учетных записей, которые сохраняют только свой баланс в одной или двух криптовалютах, освобожденных от этих постоянных платежей.
Обратите внимание: если никто не отправляет сообщения в учетную запись, плата за постоянное хранение не взимается, и учетная запись может существовать бесконечно.
Однако любой пользователь может отправить, например, пустое сообщение для уничтожения такой учетной записи. Отправителю такого сообщения может быть предоставлено небольшое вознаграждение, взимаемое с части первоначального баланса учетной записи, подлежащей уничтожению. Однако мы ожидаем, что валидаторы будут уничтожать такие неплатежеспособные учетные записи бесплатно, просто чтобы уменьшить размер состояния блокчейна и избежать хранения больших объемов данных без компенсации.
Платежи, собранные за хранение постоянных данных, распределяются между валидаторами шардчейна или мастерчейна (во втором случае пропорционально их стейкам).
2.3.18. Локальные и глобальные смарт-контракты; экземпляры смарт-
контрактов. Смарт-контракт обычно находится только в одном шарде, выбранном в соответствии с идентификатором account_ id смарт-контракта (аналогично «обычной» учетной записи). Обычно этого достаточно для большинства приложений. Однако для некоторых смарт-контрактов с высокой нагрузкой может потребоваться наличие
«экземпляра» в каждой шардчейне какого-либо воркчейна. Для этого они должны распространить свою создаваемую транзакцию на все шардчейны, например, зафиксировав эту транзакцию в «корневом» шардчейне (w, θ)
11
воркчейна w и установив большую комиссию
12
Это позволяет эффективно создавать экземпляры смарт-контракта в каждом шарде с отдельными балансами. Первоначально баланс, переданный в создаваемой транзакции, распределяется просто путем присвоения экземпляру в шарде (w, s) значений 2
-|s|
от части общего баланса. Когда шард разделяется на два дочерних шарда, балансы всех экземпляров глобальных смарт-контрактов делятся пополам; когда два шарда объединяются, балансы складываются.
В некоторых случаях разделение/объединение экземпляров глобальных смарт- контрактов может включать (отложенное) выполнение специальных методов этих смарт-контрактов. По умолчанию балансы разделяются и объединяются, как описано выше, а некоторые специальные хэш-карты, индексированные «по учетным записям», также автоматически разделяются и объединяются (см. 2.3.16).
2.3.19. Ограничение разделения смарт-контрактов. Глобальный смарт-контракт может ограничивать глубину разделения d при его создании, что позволяет сделать расходы на постоянное хранение более предсказуемыми. Это означает, что если шардчейн (w, s) вместе с |s| > d делится на две части, только один из двух новых сегментов наследует экземпляр смарт-контракта. Эта шардчейн выбирается детерминировано: каждый глобальный смарт-контракт имеет некоторый
«account_id», который по сути является хэшем создаваемой транзакции, а его экземпляры имеют тот же идентификатор account_id с заменой первых