Любой блокчейн определяет заданное глобальное состояние, а каждый блок и каждая транзакция определяют преобразование этого глобального состояния. Ниже описывается глобальное состояние, используемое блокчейнами TON.
Идентификаторы аккаунтов. Базовые идентификаторы учетных записей, используемые блокчейнами TON (или как минимум его мастерчейном и исходным воркчейном) представляют собой 256-битные целые числа, которые считаются открытыми ключами для 256-битного шифрования на основе эллиптических кривых (ECC) для конкретной эллиптической кривой. Таким образом,
Где Account — это тип учетной записи, а account_id: Account — это конкретная переменная типа Account.
Другие воркчейны могут использовать другие форматы идентификаторов учетных записей (256-битные или другие). Например, можно использовать подобные биткоину идентификаторы учетной записи, равные SHA256 открытого ключа ECC.
Однако длина l в битах идентификатора учетной записи должна быть зафиксирована во время создания воркчейна (в мастерчейне), и она должна быть не менее 64, поскольку первые 64 бита идентификатора account_id используются для сегментирования и маршрутизации сообщений.
Основной компонент: хэш-карты
Главный компонент состояния блокчейна TON — это хэш-карта. В некоторых случаях мы рассматриваем (частично определенные) «карты» h: 2n
-→ + 2m. В более общем плане нас могут заинтересовать хэш-карты h: 2n
-→ X для составного типа X. Однако тип источника (или индекса) почти всегда 2n
. Иногда «значение по умолчанию» является пустым: X, а хэш-карта h: 2
n → X «инициализируется» своим пустым «значением по умолчанию» i →.
Пример: остатки на счетах TON
Важный пример — остатки на счетах TON. Это хэш-карта, которая сопоставляет Account = 2256 с балансом монет TON типа uint128 = 2128. Эта хэш-карта имеет значение по умолчанию, равное нулю, то есть изначально (до обработки первого блока) баланс всех учетных записей равен нулю.
Пример: постоянное хранилище смарт-контракта
Другой пример — постоянное хранилище смарт-контрактов, которое можно (очень приблизительно) представить в виде хэш-карты.
Эта хэш-карта также имеет значение по умолчанию, равное нулю, то есть неинициализированные ячейки постоянного хранилища считаются равными нулю.
Пример: постоянное хранилище всех смарт-контрактов
Поскольку у нас есть несколько смарт-контрактов, различающихся идентификатором account_ id, каждый из которых имеет отдельное постоянное хранилище, у нас должна быть фактическая хэш-карта, которая соотносит идентификатор account_id смарт-контракта с его постоянным хранилищем.
Тип хэш-карты
Хэш-карта — это не просто абстрактная (частично определенная) функция 2n
—→ X; у нее есть конкретное представление. Поэтому мы предполагаем, что у нас есть специальный тип хэш-карты,
соответствующий структуре данных, кодирующей (частичное) отображение 2n
-→ X. Мы также можем записать или
Мы всегда можем преобразовать h: Hashmap (n, X) в карту hget (h): 2n →X?
, С этого момента мы обычно пишем h[i] вместо hget(h)(i):
Определение типа хэш-карты как дерева Patricia
Логически можно определить Hashmap(n, X) как (неполное) двоичное дерево глубины n с метками ребер 0 и 1 и со значениями типа X в листьях. Другим способом описания той же структуры было бы (побитовое) префиксное дерево для двоичных строк длиной, равной n.
На практике мы предпочитаем использовать компактное представление этого дерева, сжимая каждую вершину, имеющую только один дочерний элемент со своим родителем. Результирующее представление известно как дерево Patricia или двоичное основание системы счисления. Каждая промежуточная вершина теперь имеет ровно два дочерних элемента, помеченных двумя непустыми двоичными строками, начиная с нуля для левого дочернего элемента и с одного для правого дочернего элемента.
Другими словами, в дереве Patricia имеется два типа (некорневых) узлов:
• LEAF(x), содержащий значение x типа X.
• NODE (д, sl, r, sr), где l — (ссылка на) левый дочерний элемент или поддерево, sl — это цепочка битов, обозначающая ребро, соединяющее эту вершину с ее левым дочерним элементом (всегда начинается с 0), r — правое поддерево, а sr — это цепочка битов, обозначающая край правого дочернего элемента (всегда начинается с 1).
Также необходим третий тип узла, который будет использоваться только один раз в корне дерева Patricia:
• ROOT (n, s0, t), где n — общая длина индексных битовых строк Hashmap (n, X), s0 —
общий префикс всех индексных битовых строк, а t — ссылка на LEAF или NODE .
Если мы хотим, чтобы дерево Patricia было пустым, необходимо использовать четвертый тип (корневого) узла:
• EMPTYROOT (n), где n — общая длина всех битовых строк индекса.
Мы определяем высоту дерева Patricia следующим образом:
Последние два выражения в каждой из двух последних формул должны быть равны. Мы используем деревья Patricia высоты n для представления значений типа Hashmap(n, X), Если в дереве N листьев (т. е. наша хэш-карта содержит N значений), то имеется ровно N — 1 промежуточных вершин. Вставка нового значения всегда включает в себя разделение существующего ребра путем вставки новой вершины в середину и добавления нового листа в качестве другого дочернего элемента этой новой вершины. Удаление значения из хэш-карты приводит к обратному эффекту: лист и его родитель удаляются, а родитель родителя и другой его дочерний элемент становятся напрямую связанными.
Деревья 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), что это (слегка измененная) версия рекурсивно определенных хэшей для значений произвольных (зависимых) алгебраических типов.
Пересчет хэшей дерева Merkle
Этот способ рекурсивного разделения HASH (h), называемый хэшем дерева Merkle, обладает следующим преимуществом: если один явно хранит HASH(h’) вместе с каждым узлом h’ (в результате получается структура, называемая деревом Merkle, или, в нашем случае, деревом Merkle Patricia), необходимо пересчитывать не более n хэшей при добавлении, удалении или изменении элемента в хэш-карте.
Таким образом, если кто-то представляет глобальное состояние блокчейна подходящим хэшем дерева Merkle, его можно легко пересчитывать после каждой транзакции.
Доказательства Меркла
На основании предположения (7) «инъективности» выбранной хэш-функции HASH, можно построить доказательство того, что для данного значения z HASH(h), h: Hashmap(n, X) имеет место hget(h)(i) = x для некоторых i: 2n и x: X. Такое доказательство будет состоять из пути в дереве Merkle Patricia от листа, соответствующего i, до корня, дополненного хэшами всех братьев и сестер всех встречающихся узлов на этом пути.
Таким образом, неполная нода6, знающая только значение HASH(h) для некоторой хэш-карты h (например, постоянное хранилище смарт-контракта или глобальное состояние блокчейна), может запросить у полной ноды7 не только значение x = h[i] = hget(h)(i), но такое значение вместе с доказательством Меркла, начиная с уже известного значения HASH(h). Затем, в предположении (7), неполная нода может сама проверить, что x действительно является правильным значением h [i].
В некоторых случаях клиент может захотеть получить вместо этого значение y = HASH(X) = HASH(h[i]) — например, в случае очень большого значения x (например, самой хэш-карты). Тогда вместо этого можно предоставить доказательство Меркла для (i, y). Если x также является хэш-картой, то второе доказательство Меркла, начиная с y = HASH(X), может быть получено из полной ноды, чтобы предоставить значение x[j] = h[i][j] или только его хэш.
Важность доказательств Меркла для многозвенной системы, такой как TON
Обратите внимание, что нода обычно не может быть полной нодой для всех шардчейнов, существующих в среде TON. Обычно эта нода является полной только для некоторых шардчейнов – например, шардчейнов, которые содержат ее собственную учетную запись, смарт-контракт, с которым она работает, либо шардчейнов, для которых эта нода была назначена валидатором. Для других шардчейнов это должна быть неполная нода, иначе требования к хранилищу, вычислениям и пропускной способности сети будут непомерно высокими. Это означает, что такая нода не может напрямую проверять утверждения о состоянии других шардчейнов; она должна полагаться на доказательства Меркла, полученные из полных нод для этих шардчейнов. Этот процесс является таким же безопасным, как и собственно проверка, если только (7) он не завершится неудачей (т. е. не будет обнаружен хэш-конфликт).
Особенности виртуальной машины TON
Виртуальная машина TON или TVM, используемая для запуска смарт-контрактов в мастерчейне и исходном воркчейне, значительно отличается от обычных систем, вдохновленных виртуальной машиной Ethereum (EVM). TVM работает не только с 256-битными целыми числами, но и фактически с (почти) произвольными «записями», «структурами» или «типами суммы-произведения», что делает ее более подходящей для выполнения кода, написанного на высокоуровневых языках программирования (особенно функциональных языках). По сути, TVM использует тегированные типы данных, аналогичные тем, которые используются в реализациях Prolog или Erlang.
Сначала можно подумать, что состояние смарт-контракта TVM — это не просто хэш-карта 2256 → 2 256, от Hashmap (256, 2256), но (в качестве первого шага) Hashmap (256, X), где X — это тип с несколькими конструкторами, позволяющий хранить, помимо 256-битных целых чисел, другие структуры данных, включая, в частности, другие хэш-карты Hashmap (256, X). Это означало бы, что ячейка хранилища TVM (постоянного или временного) — переменная или элемент массива в коде смарт-контракта TVM — может содержать не только целое число, но и целую новую хэш-карту. Конечно, это будет означать, что ячейка содержит не только 256 бит, но также, скажем, 8-битный тег, описывающий, как эти 256 бит должны интерпретироваться.
Можно показать, что это кодирование оптимально примерно для половины всех меток ребер дерева Patricia со случайными или последовательными индексами. Остальные граничные метки, вероятно, будут длинными (т. е. длиной почти 256 бит).
Следовательно, почти оптимальным кодированием для граничных меток является использование приведенного выше кода с префиксом 0 для «коротких» битовых строк и кодирование 1, а затем девять битов, содержащих длину l = |s| битовой строки s, а затем l битов s для «длинных» битовых строк (l ≤ 10).
Неполная нода — это узел, который не отслеживает полное состояние шардчейна; вместо этого он сохраняет минимальную информацию, такую как хэши нескольких самых последних блоков, и полагается на информацию, полученную от полных нод, когда возникает необходимость проверить некоторые части полного состояния.
Полная нода — это узел, отслеживающий полное актуальное состояние рассматриваемого шардчейна. Фактически, значения не обязательно должны быть точно 256-битными. Формат значения, используемый TVM, состоит из последовательности необработанных байтов и ссылок на другие структуры, смешанных в произвольном порядке, причем некоторые байты дескриптора вставлены в подходящие места, что дает возможность отличать указатели от необработанных данных (например, строки или целые числа)
Этот формат необработанных значений может использоваться для реализации произвольных алгебраических типов суммы-произведения. В этом случае значение будет сначала содержать необработанный байт, описывающий используемый «конструктор» (с точки зрения высокоуровневого языка программирования), а затем другие «поля» или «аргументы конструктора», состоящие из необработанных байтов и ссылок на другие структуры в зависимости от выбранного конструктора. Однако TVM ничего не знает о соответствии конструкторов и их аргументов; смесь байтов и ссылок явно описывается определенными байтами дескриптора8.
Хэширование дерева Merkle распространяется на произвольные структуры — для вычисления хэша такой структуры все ссылки рекурсивно заменяются хэшами объектов, на которые имеется ссылка, а затем вычисляется хэш результирующей байтовой строки (включая байты дескриптора).
Таким образом, хэширование дерева Merkle для хэш-карт, представляет собой просто простой способ хэширования для произвольных (зависимых) алгебраических типов данных, применяемый к типу Hashmap (n, X) с двумя конструкторами.
Постоянное хранилище смарт-контрактов TON
Постоянное хранилище смарт-контрактов TON по существу состоит из его «глобальных переменных», сохраняемых между вызовами смарт-контракта. По сути, это просто тип «произведение», «кортеж» или «запись», состоящий из полей правильных типов, каждое из которых соответствует одной глобальной переменной. Если существует слишком много глобальных переменных, они не могут поместиться в одну ячейку TON из-за глобального ограничения на размер ячейки TON. Для простоты они разделены на несколько записей и организованы в дерево, по сути становясь типом «произведение произведений» или «произведение произведений произведений», а не просто типом-произведением.
Ячейки TVM
В конечном итоге виртуальная машина TON хранит все данные в виде набора ячеек (TVM). Каждая ячейка сначала содержит два байта дескриптора, указывающие, сколько байтов необработанных данных присутствует в этой ячейке (до 128) и сколько имеется ссылок на другие ячейки (до 4). Затем следуют байты необработанных данных и ссылки. На каждую ячейку имеется ровно одна ссылка, поэтому мы могли бы включить в каждую ячейку ссылку на ее «родительский элемент» (единственную ячейку, ссылающуюся на эту ячейку). Однако эта ссылка не обязательно должна быть явной.
Таким образом, ячейки постоянного хранилища смарт-контракта TON организованы в дерево со ссылкой на корень этого дерева, хранящейся в описании смарт-контракта. Если необходимо, рекурсивно вычисляется хэш дерева Merkle для всего этого постоянного хранилища, начиная с листьев, а затем просто заменяются все ссылки в ячейке рекурсивно вычисленными хэшами ячеек, на которые имеются ссылки, и впоследствии вычисляется хэш полученной таким образом строки байтов.
Обобщенные доказательства Меркла для значений произвольных алгебраических типов
Поскольку виртуальная машина TON представляет значение произвольного алгебраического типа посредством дерева, состоящего из ячеек, а каждая ячейка имеет четко определенный (рекурсивно вычисленный) хэш Меркла, фактически зависящий от всего поддерева, имеющего корень в этой ячейке, мы можем предоставить «обобщенные доказательства Меркла» для (частей) значений произвольных алгебраических типов, предназначенные для доказательства того, что определенное поддерево дерева с известным хэшем Меркла принимает определенное значение или значение с определенным хэшем. Это обобщает подход, где были рассмотрены только доказательства Меркла для x[i] = y.
Поддержка сегментирования в структурах данных TON VM
Только что мы в общих чертах обрисовали, как виртуальная машина TON, не будучи чрезмерно сложной, поддерживает произвольные (зависимые) алгебраические типы данных на высокоуровневых языках смарт-контрактов. Однако для шардинг крупных (или глобальных) смарт-контрактов требуется специальная поддержка на уровне ВМ TON. С этой целью в систему была добавлена специальная версия типа hashmap, равная «карте» Account —>X . Эта «карта» может показаться эквивалентной Hashmap (m, X), где Account = 2m, однако, когда шард разделяется на два шарда, либо два шарда объединяются, такие хэш-карты автоматически разделяются на две хэш-карты или объединяются обратно, что позволяет сохранить только те ключи, которые принадлежат соответствующему шарду.
Плата за постоянное хранилище
Примечательной особенностью блокчейна TON является плата, взимаемая со смарт-контрактов за хранение их постоянных данных (то есть за увеличение состояния блокчейна в целом). Этот процесс выглядит следующим образом:
В каждом блоке декларируются два стейка, номинированные в основной валюте блокчейна (обычно это монета TON): цена за хранение одной ячейки в постоянном хранилище и цена за хранение одного необработанного байта в какой-либо ячейке постоянного хранилища. Статистика по общему количеству ячеек и байтов, используемых каждой учетной записью, сохраняется как часть ее состояния, поэтому, умножив эти числа на два стейка, указанные в заголовке блока, мы можем вычислить платеж, который будет вычтен из баланса счета для хранения его данных между предыдущим блоком и текущим.
Однако плата за использование постоянного хранилища взимается не для каждой учетной записи и смарт-контракта в каждом блоке. Вместо этого порядковый номер блока, в котором этот платеж был взыскан в последний раз, сохраняется в данных учетной записи, и когда с учетной записью выполняется какое-либо действие (например, перенос стоимости, либо получение или обработка сообщения смарт-контрактом), то плата за использование хранилища для всех блоков с момента предыдущего такого платежа вычитается из баланса аккаунта перед выполнением каких-либо дальнейших действий. Если после этого баланс учетной записи станет отрицательным, учетная запись будет уничтожена.
Эти два байта дескриптора, присутствующие в любой ячейке TVM, описывают только общее количество ссылок и общее количество необработанных байтов; ссылки хранятся вместе либо до, либо после всех необработанных байтов.
Фактически LEAF и NODE являются конструкторами вспомогательного типа HashmapAux (n, X). Тип Hashmap (n, X) имеет конструкторы ROOT и EMPTYROOT, причем ROOT содержит значение типа HashmapAux(n, X).
Логически; представление «набор ячеек» идентифицирует все повторяющиеся ячейки, преобразовывая это дерево в ориентированный ациклический граф при сериализации.
Воркчейн может объявить некоторое количество байтов необработанных данных для каждой учетной записи «бесплатными» (т. е. не участвующими в платежах за постоянное хранилище) для создания «простых» учетных записей, которые сохраняют только свой баланс в одной или двух криптовалютах, освобожденных от этих постоянных платежей.
Обратите внимание: если никто не отправляет сообщения в учетную запись, плата за постоянное хранение не взимается, и учетная запись может существовать бесконечно. Однако любой пользователь может отправить, например, пустое сообщение для уничтожения такой учетной записи. Отправителю такого сообщения может быть предоставлено небольшое вознаграждение, взимаемое с части первоначального баланса учетной записи, подлежащей уничтожению. Однако мы ожидаем, что валидаторы будут уничтожать такие неплатежеспособные учетные записи бесплатно, просто чтобы уменьшить размер состояния блокчейна и избежать хранения больших объемов данных без компенсации.
Платежи, собранные за хранение постоянных данных, распределяются между валидаторами шардчейна или мастерчейна (во втором случае пропорционально их стейкам).
Локальные и глобальные смарт-контракты; экземпляры смарт-контрактов
Смарт-контракт обычно находится только в одном шарде, выбранном в соответствии с идентификатором account_ id смарт-контракта (аналогично «обычной» учетной записи). Обычно этого достаточно для большинства приложений. Однако для некоторых смарт-контрактов с высокой нагрузкой может потребоваться наличие «экземпляра» в каждой шардчейне какого-либо воркчейна. Для этого они должны распространить свою создаваемую транзакцию на все шардчейны, например, зафиксировав эту транзакцию в «корневом» шардчейне (w, θ)11 воркчейна w и установив большую комиссию. Это позволяет эффективно создавать экземпляры смарт-контракта в каждом шарде с отдельными балансами. Первоначально баланс, переданный в создаваемой транзакции, распределяется просто путем присвоения экземпляру в шарде (w, s) значений 2-|s| от части общего баланса. Когда шард разделяется на два дочерних шарда, балансы всех экземпляров глобальных смарт-контрактов делятся пополам; когда два шарда объединяются, балансы складываются.
В некоторых случаях разделение/объединение экземпляров глобальных смарт-контрактов может включать (отложенное) выполнение специальных методов этих смарт-контрактов. По умолчанию балансы разделяются и объединяются, как описано выше, а некоторые специальные хэш-карты, индексированные «по учетным записям», также автоматически разделяются и объединяются.
Ограничение разделения смарт-контрактов
Глобальный смарт-контракт может ограничивать глубину разделения d при его создании, что позволяет сделать расходы на постоянное хранение более предсказуемыми. Это означает, что если шардчейн (w, s) вместе с |s| > d делится на две части, только один из двух новых сегментов наследует экземпляр смарт-контракта. Эта шардчейн выбирается детерминировано: каждый глобальный смарт-контракт имеет некоторый «account_id», который по сути является хэшем создаваемой транзакции, а его экземпляры имеют тот же идентификатор account_id с заменой первых <d битов подходящими значениями, необходимыми для попадания в правильный шард. Этот идентификатор account_id выбирает, какой шард унаследует экземпляр смарт-контракта после разделения.
Состояние учетной записи/смарт-контракта
На основании всего вышесказанного мы можем сделать вывод, что состояние учетной записи или смарт-контракта включает следующее:
• Баланс в основной валюте блокчейна
• Баланс в других валютах блокчейна
• Код смарт-контракта (или его хэш)
• Постоянные данные смарт-контракта (или соответствующий хэш Меркла)
• Статистика количества используемых ячеек постоянного хранения и необработанных байтов
• Последний раз (собственно, номер блока мастерчейна), когда была получена оплата за постоянное хранение смарт-контракта
• Открытый ключ, необходимый для перевода валюты и отправки сообщений с этой учетной записи (необязательно; по умолчанию равен самому идентификатору account_id). В некоторых случаях здесь может быть расположен более сложный код проверки подписи, аналогично коду, который используется для выходных данных транзакции биткоина; тогда идентификатор account_id будет равен хэшу этого кода.
• Также в состоянии учетной записи или в какой-либо другой хэш-карте, индексированной учетной записью, необходимо хранить следующие данные:
• Очередь выходных сообщений учетной записи)
• Набор (хэшей) недавно доставленных сообщений
Не все эти функции действительно необходимы для каждой учетной записи; например, код смарт-контракта нужен только для смарт-контрактов, но не для «простых» учетных записей. Кроме того, хотя на любой учетной записи должен быть ненулевой баланс в основной валюте (например, монеты TON для мастерчейна и щардчейнов основного воркчейна), на ней могут быть нулевые балансы в других валютах. Чтобы избежать хранения неиспользуемых данных, (во время создания воркчейна) определяется тип суммы-произведения (в зависимости от воркчейна), который использует разные байты тегов (например, конструкторы TL), чтобы различать разные « конструкторы ». В конечном итоге, состояние учетной записи сохраняется как набор ячеек постоянного хранилища TVM.
