Теперь мы готовы описать глобальное состояние блокчейна TON или как минимум шардчейна базового воркчейна.
Мы начинаем с «высокоуровневого» или «логического» описания, которое заключается в том, что глобальное состояние является значением алгебраического типа данных ShardchainState.
Состояние шардчейна как совокупность состояний цепочки учетных записей
Согласно парадигме бесконечного шардинга, любой шардчейн представляет собой (временную) совокупность виртуальных «цепочек учетных записей», каждая из которых содержит ровно одну учетную запись. Это означает, что, по сути, состояние глобальной шардчейна представлено в виде хэш-карты. где все идентификаторы account_ id, появляющиеся как индексы этой хэш-карты, должны начинаться с префикса s, если имеется в виду состояние шарда (w, s).
На практике нам может потребоваться разделить AccountState на несколько частей (например, сохранить отдельную очередь выходных сообщений учетной записи, чтобы упростить ее проверку соседними шардчейнами) и использовать несколько хэш-карт (Account —> * AccountStateParti) внутри ShardchainState. Мы также можем добавить небольшое количество «глобальных» или «интегральных» параметров в ShardchainState (например, общий баланс всех учетных записей, принадлежащих этому шарду, или общее количество сообщений во всех очередях вывода).
Однако – это наглядное приближение того, как выглядит глобальное состояние шардчейна, по крайней мере, с «логической» («высокоуровневой») точки зрения. Формальное описание алгебраических типов Accountstate и ShardchainState может быть выполнено с помощью TL-схемы, которая будет предоставлена где-либо еще.
Разделение и объединение состояний шардчейна
Обратите внимание, что описание состояния шардчейна в парадигме бесконечного шардинга показывает, как это состояние должно обрабатываться при разделении или слиянии шардчейнов. Фактически, эти преобразования состояний являются очень простыми операциями с хэш-картами.
Состояние цепочки учетных записей
Состояние (виртуальной) цепочки учетных записей — это просто состояние одной учетной записи, описываемое типом AccountState. Обычно в нем есть все или некоторые из полей, в зависимости от конкретного используемого конструктора.
Состояние глобального воркчейна
Подобно, мы можем определить состояние глобального воркчейна по той же формуле, но с использованием идентификатора account_id, s, которому разрешено принимать любые значения, а не только значения, которые принадлежат одному шарду. В этом случае применимы замечания: мы можем разделить эту хэш-карту на несколько хэш-карт и добавить некоторые «интегральные» параметры, такие как общий баланс.
По сути, глобальное состояние воркчейна должно быть задано тем же типом ShardchainState, что и состояние шардчейна, потому что это состояние шардчейна, которое мы получили бы, если бы все существующие шардчейны данного воркчейна внезапно слились бы в один шардчейн.
Низкоуровневая перспектива: «мешок ячеек». Существует также «низкоуровневое» описание цепочки учетных записей или состояния шардчейна, дополняющее приведенное выше «высокоуровневое» описание. Это описание очень важно, потому что оно является довольно универсальным и обеспечивает общую основу для представления, хранения, сериализации и передачи по сети почти всех данных, используемых блокчейном TON (блоки, состояния шардчейна, хранилище смарт-контрактов, доказательства Меркла и т.д.). В то же время такое понятное универсальное «низкоуровневое» описание позволяет нам сосредоточить внимание только на соображениях «высокого уровня».
Напомним, что TVM представляет значения произвольных алгебраических типов (включая, например, ShardchainState) посредством дерева ячеек TVM, или для краткости «ячеек».
Любая такая ячейка состоит из двух байтов дескриптора, определяющих определенные флаги и значения 0 ≤ b ≤128, количество необработанных байтов, и 0 ≤ c ≤ 4 — количество ссылок на другие ячейки. Затем следуют b необработанных байтов и c ссылок на ячейки. Точный формат ссылок на ячейки зависит от реализации и от того, находится ли ячейка в ОЗУ, на диске, в сетевом пакете, в блоке и т. д. Полезная абстрактная модель заключается в том, что все ячейки хранятся в памяти с адресацией по содержимому с адресом ячейки, равным ее хэш-функции (SHA256). Напомним, что хеш (Меркла) ячейки вычисляется путем замены ссылок на ее дочерние ячейки их (рекурсивно вычисляемыми) хешами и хеширования полученной байтовой строки.
Таким образом, если мы используем хэши ячеек для ссылки на ячейки (например, внутри описаний других ячеек), система несколько упрощается, и хэш ячейки начинает совпадать с хешем представляющей ее байтовой строки.
Теперь мы видим, что любой представляемый TVM объект, включая глобальное состояние шардчейна, может быть представлен как «мешок ячеек» — т. е. набор ячеек вместе с «корневой» ссылкой на одну из них (например, хешем). Обратите внимание, что повторяющиеся ячейки отсутствуют в этом описании («набор ячеек» — это набор ячеек, а не мультимножество ячеек), поэтому представление абстрактного дерева фактически может стать представлением ориентированного ациклического графа (dag).
Это состояние можно сохранить на диске в дереве B- или B+-, содержащем все рассматриваемые ячейки (возможно, с некоторыми дополнительными данными, такими как высота поддерева или счетчик ссылок) и проиндексированном хэшем ячеек. Однако примитивная реализация этой идеи может привести к тому, что состояние одного смарт-контракта будет разбросано по удаленным частям файла на диске, чего мы предпочли бы избежать.
Теперь мы собираемся более подробно объяснить, как почти все объекты, используемые блокчейном TON, могут быть представлены в виде «мешков ячеек», демонстрируя тем самым универсальность этого подхода.
Блок шардчейна как «мешок ячеек»
Блок шардчейна может быть описан алгебраическим типом и храниться как «мешок ячеек». Тогда простое двоичное представление блока может быть получено простым объединением строк байтов, представляющих каждую из ячеек в «мешке ячеек», в произвольном порядке. Это представление может быть улучшено и оптимизировано, например, путем предоставления списка смещений всех ячеек в начале блока и замены хеш-ссылок на другие ячейки 32-битными индексами в этом списке, когда это возможно. Однако следует учитывать, что блок — это, по сути, «мешок ячеек», а все остальные технические детали — лишь мелкие компоненты оптимизации и реализации.
Обновление объекта как «мешка ячеек»
Представьте, что у нас есть старая версия некоторого объекта, представленного в виде «мешка ячеек», и мы хотим представить новую версию того же объекта, предположительно не слишком отличающуюся от предыдущей. Новое состояние может быть представлено просто как еще один «мешок ячеек» с собственным корнем, из которого будут удалены все ячейки, встречающиеся в старой версии. По сути, оставшийся «мешок ячеек» является обновлением объекта. Каждый пользователь, у которого есть старая версия этого объекта и обновление, может вычислить новую версию, просто объединив два пакета ячеек и удалив старый корень (уменьшив его счетчик ссылок и освободив ячейку, если счетчик ссылок становится равным нулю).
Можно показать, что если доказательства Меркла для всех данных, хранящихся в дереве ячеек, требуются одинаково часто, следует использовать ячейки с b+ch ≈ 2(h+r), чтобы минимизировать средний размер доказательства Меркла, где h = 32 — это размер хеша в байтах, а r ≈ 4 — размер ссылки на ячейку в байтах. Другими словами, ячейка должна содержать либо две ссылки и несколько необработанных байтов, либо одну ссылку и около 36 необработанных байтов, либо вообще не иметь ссылок с 72 необработанными байтами.
Наилучшей реализацией было бы сохранение состояния смарт-контракта в виде сериализированной строки, если оно маленькое, или в отдельном B-дереве, если оно большое. Тогда структура верхнего уровня, представляющая состояние блокчейна, будет B-деревом, листья которого могут содержать ссылки на другие B-деревья.
Обновления состояния учетной записи
В частности, обновления состояния учетной записи или глобального состояния шардчейна или любой хэш-карты могут быть представлены с использованием идеи. Это означает, что когда мы получаем новый блок шардчейна (который представляет собой «мешок ячеек»), мы интерпретируем не только собственно этот «мешок ячеек», но сначала объединяем его с «мешком ячеек», представляющим предыдущее состояние шардчейна. В этом смысле каждый блок может «содержать» все состояние блокчейна.
Обновления в блоке
Напомним, что сам блок представляет собой «мешок ячеек», поэтому, если возникает необходимость отредактировать блок, можно аналогичным образом определить «обновление блока» как «мешок ячеек», интерпретируемый при наличии «мешка ячеек», который является предыдущей версией этого блока. Этот процесс является примерной идеей «вертикальных блоков».
Доказательство Меркла как «мешок ячеек»
Обратите внимание, что (обобщенное) доказательство Меркла — например, утверждение, что x[i] = y, начиная с известного значения HASH(x) = h, — также может быть представлено как «мешок ячеек». А именно, нужно просто предоставить подмножество ячеек, соответствующее пути от корня x: Hashmap(n, X) к целевому листу с индексом i: 2n и значением y: X. Ссылки на дочерние элементы этих ячеек, которые не лежат на этом пути, останутся «нерешенными» в этом доказательстве, представленном хешами ячеек. Можно также обеспечить одновременное доказательство Меркла, скажем, x[i] = y и x[i’] = y’, включив в «мешок ячеек» ячейки, лежащие на пути объединения двух путей от корня x в листы, соответствующие индексам i и i’.
Доказательства Меркла в виде ответов на запросы от полных нод
По сути, полная нода с полной копией состояния шардчейна (или цепочки учетных записей) может предоставить доказательство Меркла по запросу неполного узла (например, сетевого узла, на котором запущена облегченная версия клиента блокчейна TON), что позволяет получателю выполнять некоторые простые запросы без внешней помощи, используя только ячейки в этом доказательстве Меркла. Неполная нода может отправлять свои запросы в сериализированном формате на полную ноду и получать правильные ответы с доказательствами Меркла (или просто доказательства Меркла), потому что запрашивающая сторона должна иметь возможность вычислять ответы, используя только ячейки, включенные в доказательство Меркла. Это доказательство Меркла будет состоять из «мешка ячеек», содержащего только ячейки, принадлежащие к состоянию шардчейна, к которым получила доступ полная нода при выполнении запроса неполной ноды. Такой подход может использоваться, в частности, для выполнения «запросов на получение» смарт-контрактов.
Дополненное обновление или обновление состояния с доказательством Меркла
Напомним, что мы можем описать изменения в состоянии объекта от старого значения x: X к новому значению x’: X с помощью «обновления», которое представляет собой просто «мешок ячеек» с ячейками, которые лежат в поддереве, представляющем новое значение x’, но не в поддереве, представляющем старое значение x, поскольку предполагается, что получатель имеет копию старого значения x и всех его ячеек.
Однако если получатель не имеет полной копии x, но знает только ее хэш (Меркла) h = HASH(X), он не сможет проверить правильность обновления (т. е. все «подвешенные» ссылки на ячейки в обновлении действительно относятся к ячейкам, присутствующим в дереве x). Хотелось бы иметь «проверяемые» обновления, дополненные доказательствами Меркла для существования всех упомянутых ячеек в старом состоянии. Тогда любой пользователь, который знает только h = HASH(X), сможет проверить правильность обновления и вычислить новый h’ = HASH (X’) самостоятельно.
Поскольку наши доказательства Меркла сами по себе являются «мешками ячеек» , можно построить такое расширенное обновление, как «мешок ячеек», содержащий старый корень x, некоторые из его потомков вместе с путями из корня x, а также новый корень x’ и всех его потомков, которые не являются частью x.
Обновление состояния учетной записи в блоке шардчейна
В частности, обновления состояния учетной записи в блоке шардчейна должны быть дополнены. В противном случае кто-то может зафиксировать блок, содержащий недопустимое обновление состояния, ссылаясь на ячейку, отсутствующую в старом состоянии; доказать невалидность такого блока будет проблематично (как претенденту доказать, что ячейка не является частью предыдущего состояния?).
Если дополняются все обновления состояния, включенные в блок, их достоверность можно легко проверить, а их невалидность также отображается как нарушение рекурсивного определяющего свойства (обобщенных) хэшей Меркла.
Философия «все есть мешок ячеек»
Предыдущие соображения показывают, что все данные, которые необходимо хранить или передавать, будь то в блокчейне TON или в сети, можно представить в виде «мешка ячеек». Это важная часть философии проектного решения блокчейна TON. После объяснения подхода «мешок ячеек» и определения некоторых «низкоуровневых» сериализаций «мешков ячеек» можно просто определить все (формат блока, шардчейн и состояние учетной записи и т. д.) с помощью высокого уровня абстрактных (зависимых) алгебраических типов данных.
Объединяющий эффект философии «все есть мешок ячеек» значительно упрощает реализацию, казалось бы, несвязанных сервисов.
«Заголовки» блоков для блокчейнов TON
Обычно блок в блокчейне начинается с небольшого заголовка, содержащего хэш предыдущего блока, время его создания, хэш Меркла дерева всех транзакций, содержащихся в блоке, и так далее. Затем хеш блока определяется как хеш этого небольшого заголовка блока. Поскольку заголовок блока в конечном итоге зависит от всех данных, включенных в блок, нельзя невозможно изменить блок, не изменив его хэш.
При использовании подхода «мешок ячеек», который используется блокчейнами TON, назначенный заголовок блока отсутствует. Вместо этого хеш блока определяется как хеш (Меркла) корневой ячейки блока. Следовательно, верхняя (корневая) ячейка блока может считаться небольшим «заголовком» этого блока.
Однако корневая ячейка может не содержать всех данных, обычно ожидаемых от такого заголовка. По сути, нужно, чтобы заголовок содержал некоторые поля, определенные в типе данных Block. Обычно эти поля содержатся в нескольких ячейках, включая корневую ячейку. Эти ячейки вместе составляют «доказательство Меркла» для значений рассматриваемых полей. Можно было бы настаивать на том, чтобы эти «ячейки заголовка» содержались в самом начале блока, перед любыми другими ячейками. Тогда нужно будет загрузить только первые несколько байтов сериализации блока, чтобы получить все «ячейки заголовка» и изучить все необходимые поля.
