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

27 2.4. Сообщения между шардчейнами
Таким образом, все шардчейны составляют граф типа «гиперкуб», а сообщения перемещаются по краям этого гиперкуба.
Если сообщение отправляется на шард, отличный от текущего шарда, одна из детерминировано выбранных шестнадцатеричных цифр текущего идентификатора шарда заменяется соответствующей цифрой целевого шарда, а полученный идентификатор используется в качестве ближайшей цели для пересылки сообщения.
Основное преимущество маршрутизации в гиперкубе заключается в том, что условия допустимости блока подразумевают, что валидаторы, создающие блоки шардчейна, должны собирать и обрабатывать сообщения из выходных очередей «соседних» шардчейнов, опасаясь потери своих долей.
Таким образом, можно ожидать, что любое сообщение рано или поздно достигнет своего конечного пункта назначения; при этом сообщение не может быть потеряно в пути или доставлено дважды.
Обратите внимание, что маршрутизация в гиперкубе приводит к некоторым дополнительным задержкам и расходам из-за необходимости пересылать сообщения через несколько промежуточных шардчейнов. Однако количество этих промежуточных шардчейнов увеличивается очень медленно по мере роста логарифма log N (точнее, [log
16
N] - 1) от общего количества шардчейнов N. Например, если N =
250, то будет наблюдаться максимум один промежуточный переход; а для N = 4000 шардчейнов — максимум два. С четырьмя промежуточными переходами мы можем поддерживать до одного миллиона шардчейнов. Мы считаем, что это очень небольшая цена за практически неограниченную масштабируемость системы
(фактически, не обязательно платить даже ее).
2.4.20. Мгновенная маршрутизация в гиперкубе (Instant Hypercube Routing):
«быстрый путь» для сообщений. Новой особенностью блокчейна TON является то, что в нем используется «быстрый путь» для пересылки сообщений от одного шардчейна к любому другому шардчейну, что позволяет в большинстве случаев полностью обойти «медленную» маршрутизацию в гиперкубе (2.4.19) и доставлять сообщение в следующий блок конечного шардчейна.
Идея этой технологии заключается в следующем. Во время «медленной» маршрутизации в гиперкубе сообщение перемещается (в сети) по краям гиперкуба, но задерживается (примерно на пять секунд) в каждой промежуточной вершине и фиксируется в соответствующем шардчейне, прежде чем продолжить свой путь.
Чтобы избежать ненужных задержек, вместо этого можно передавать сообщение вместе с подходящим доказательством Меркла по краям гиперкуба, не дожидаясь его фиксации в промежуточных шардчейнах. Фактически, сетевое сообщение должно быть переадресовано от валидаторов «целевой группы» (см. 2.6.8) исходного шарда указанному создателю блоков (см. 2.6.9) «целевой группы» конечного шарда; это можно сделать напрямую, без остановок сообщения на краях гиперкуба.
Когда это сообщение с доказательством Меркла достигает валидаторов (точнее, сверщиков - см. 2.6.5) целевого шардчейна, они могут немедленно зафиксировать его в новом блоке, не дожидаясь, пока сообщение завершит продвижение по «медленному пути».
15
Это не обязательно окончательная версия алгоритма, используемого для вычисления следующего перехода при маршрутизации в гиперкубе. В частности, шестнадцатеричные цифры могут быть заменены r-битовыми группами с r конфигурируемым параметром, не обязательно равным четырем.
16
Однако у валидаторов есть некоторый стимул сделать это как можно скорее, потому что они смогут собрать все платежи за пересылку, связанные с сообщением, которое еще не было использовано на
«медленном» пути.
17
На самом деле, можно было временно или навсегда отключить механизм мгновенной доставки, и система продолжала бы работать, хотя и медленнее.

28 2.4. Сообщения между шардчейнами
Затем подтверждение доставки вместе с подходящим доказательством Меркла отправляется обратно по краям гиперкуба, и его можно использовать, чтобы остановить движение сообщения по «медленному пути» путем выполнения специальной транзакции.
Обратите внимание, что этот механизм «мгновенной доставки» не заменяет
«медленный», но отказоустойчивый механизм, описанный в 2.4.19. «Медленный путь» по-прежнему необходим, поскольку валидаторы не должны наказываться за потерю сообщения или просто решение не фиксировать сообщения в процессе
«быстрого пути» в новых блоках своих блокчейнов
16
Следовательно, оба метода пересылки сообщений выполняются параллельно, и
«медленный» механизм прерывается только в том случае, если доказательство успеха
«быстрого» механизма фиксируется в промежуточном шардчейне
17
2.4.21. Сбор входных сообщений из очередей вывода соседних шардчейнов. Когда предлагается создание нового блока в шардчейне, некоторые из выходных сообщений соседних (в смысле гиперкуба маршрутизации 2.4.19) шардчейнов включаются в новый блок как «входные» сообщения и немедленно доставляются (т. е. обрабатываются). Существуют определенные правила относительно порядка, в котором выходные сообщения этих соседних шардчейнов должны обрабатываться.
По сути, «старое» сообщение (исходящее из блока шардчейна, относящегося к более старому блоку мастерчейна) должно быть доставлено до любого «нового» сообщения; а для сообщений, поступающих из того же соседнего шардчейна, должен соблюдаться частичный порядок очереди вывода, описанный в 2.4.17.
2.4.22. Удаление сообщений из очередей вывода. После того, как сообщение очереди вывода помечается как доставленное соседним шардчейном сообщение, оно явно удаляется из очереди вывода специальной транзакцией.
2.4.23. Предотвращение двойной доставки сообщений. Чтобы предотвратить двойную доставку сообщений, взятых из очередей вывода соседних шардчейнов, каждый шардчейн (точнее, каждая цепочка учетных записей в шардчейне) сохраняет набор недавно доставленных сообщений (или только их хэшей) как часть своего состояния. Когда обнаруживается, что доставленное сообщение было удалено из очереди вывода соответствующим исходным соседним шардчейном (см.
2.4.22), оно также удаляется из набора недавно доставленных сообщений.
2.4.24. Пересылка сообщений, предназначенных для других шардчейнов.
Маршрутизация в гиперкубе (см. 2.4.19) означает, что иногда исходящие сообщения доставляются не в шардчейн, содержащий предполагаемого получателя, а в соседний шардчейн, находящийся в гиперкубе на пути к месту назначения. В этом случае
«доставка» заключается в перемещении входящего сообщения в очередь исходящих сообщений. Этот процесс явно отражается в блоке как специальная транзакция пересылки, содержащая само сообщение. По сути, это выглядит так, как если бы сообщение было получено кем-то внутри шардчейна, и в результате было сгенерировано одно идентичное сообщение.
2.4.25. Оплата пересылки и хранения сообщения. Транзакция пересылки фактически расходует некоторое количество газа (в зависимости от размера пересылаемого сообщения), поэтому оплата газа вычитается из стоимости сообщения, пересылаемого от имени валидаторов этого шардчейна. Этот платеж за пересылку обычно значительно меньше, чем платеж за газ, который взимается, когда сообщение окончательно доставляется получателю, даже если сообщение было переадресовано несколько раз в процессе маршрутизации в гиперкубе. Кроме того, пока сообщение

29 2.4. Сообщения между шардчейнами хранится в очереди вывода шардчейна, оно является частью глобального состояния шардчейна, поэтому за хранение глобальных данных в течение длительного времени также может взиматься плата с помощью специальных транзакций.
2.4.26. Сообщения, передаваемые в мастерчейн и из него. Сообщения могут быть отправлены напрямую из любого шардчейна в мастерчейн и наоборот. Однако оплата за газ для отправки и обработки сообщений в мастерчейне довольно высокая, поэтому эта возможность будет использоваться только в случае необходимости - например, валидаторами для внесения своих долей. В некоторых случаях может быть определен минимальный депозит (прикрепленное значение) для отправляемых в мастерчейн сообщений, который будет возвращаться только в том случае, если сообщение считается «действительным» принимающей стороной.
Автоматическая маршрутизация сообщений в мастерчейне отсутствует. Сообщение с идентификатором workchain_id
≠
—1 (—1 — специальный workchain_id, указывающий на мастерчейн) не может быть доставлено в мастерчейн.
В принципе, можно создать смарт-контракт для пересылки сообщений внутри мастерчейна, однако цена за его использование будет непомерно высокой.
2.4.27. Сообщения между учетными записями в одном шардчейне. В некоторых случаях учетной записью, принадлежащей определенному шардчейну, создается сообщение, предназначенное для другой учетной записи в том же шардчейне.
Например, это происходит в новом воркчейне, который еще не разделен на несколько шардчейнов благодаря нормальному уровню нагрузки.
Такие сообщения могут накапливаться в выходной очереди шардчейна, а затем обрабатываться как входящие сообщения в последующих блоках (для этой цели любой шард считается своим собственным соседним элементом). Однако в большинстве случаев эти сообщения можно доставить в самом исходном блоке.
Для этого для всех транзакций в блоке шардчейна вводится частичный порядок, а транзакции (каждая из которых заключается в доставке сообщения какой-либо учетной записи) обрабатываются с соблюдением этого частичного порядка. В частности, транзакции разрешено обрабатывать некоторое выходное сообщение предыдущей транзакции по отношению к этому частичному порядку.
В этом случае тело сообщения не копируется дважды. Вместо этого исходящая и обрабатывающая транзакции ссылаются на общую копию сообщения.
2.5. Глобальное состояние шардчейна. Философия «мешка ячеек».
Теперь мы готовы описать глобальное состояние блокчейна TON или как минимум шардчейна базового воркчейна.
Мы начинаем с «высокоуровневого» или «логического» описания, которое заключается в том, что глобальное состояние является значением алгебраического типа данных ShardchainState.
2.5.1. Состояние шардчейна как совокупность состояний цепочки учетных
записей. Согласно парадигме бесконечного шардинга (см. 2.1.2), любой шардчейн представляет собой (временную) совокупность виртуальных «цепочек учетных записей», каждая из которых содержит ровно одну учетную запись. Это означает, что, по сути, состояние глобальной шардчейна представлено в виде хэш-карты. где все идентификаторы account_ id, появляющиеся как индексы этой хэш-карты, должны начинаться с префикса s, если имеется в виду состояние шарда (w, s) (см.
2.1.8).

30 2.5. Глобальное состояние шардчейна. Философия «мешка ячеек».
На практике нам может потребоваться разделить AccountState на несколько частей
(например, сохранить отдельную очередь выходных сообщений учетной записи, чтобы упростить ее проверку соседними шардчейнами) и использовать несколько хэш-карт (Account --> * AccountStatePart i
) внутри ShardchainState. Мы также можем добавить небольшое количество «глобальных» или «интегральных» параметров в
ShardchainState (например, общий баланс всех учетных записей, принадлежащих этому шарду, или общее количество сообщений во всех очередях вывода).
Однако (23) – это наглядное приближение того, как выглядит глобальное состояние шардчейна, по крайней мере, с «логической» («высокоуровневой») точки зрения.
Формальное описание алгебраических типов Accountstate и ShardchainState может быть выполнено с помощью TL-схемы (см. 2.2.5), которая будет предоставлена где- либо еще.