Открытая сеть. Открытая сеть по материалам работы дра Николая Дурова 26 июля 2021

• Название: Открытая сеть по материалам работы дра Николая Дурова 26 июля 2021
• Дата: 11.06.2022
• Размер: 0.79 Mb.
• Имя файла: Открытая сеть.pdf
• Тип: Реферат; #585329
• страница: 6 из 14

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

В этом случае тело сообщения не копируется дважды. Вместо этого исходящие и обрабатывающие транзакции ссылаются на общую копию сообщения.
2.5
Состояние глобальной цепочки шардов. Философия мешка клеток.
Теперь мы готовы описать глобальное состояние TON blockchain или, по крайней мере, shardchain базовой рабочей цепочки.
Начнем с высокоуровневого или логического описания, которое состоит в том, что глобальное состояние является значением алгебраического типа ShardchainState.
2.5.1. Состояние Shardchain как совокупность состояний цепочки учетных записей.
Согласно парадигме конечного шардинга (см. 2.1.2), любая цепочка шардов-это всего лишь (временная) коллекция виртуальных цепочек учетных записей , содержащих ровно по одной учетной записи каждая. Это означает, что, по сути, глобальное состояние shardchain должно быть хэш - картой
ShardchainState: = (Учетная запись
AccountState)
(23) где все account_id, появляющиеся в качестве индексов этой хэш-карты, должны начинаться с pre x s, если мы обсуждаем состояние shard (w, s) (ср. 2.1.8).
38 2.5. Состояние глобальной цепочки шардов. Философия мешка клеток.
На практике мы можем захотеть разделить AccountState на несколько частей
(например, сохранить очередь выходных сообщений учетной записи отдельно,чтобы упростить ее проверку соседними цепочками шардов) и иметь несколько хэш-карт (AccountStatePart i
) внутри ShardchainState. Мы также можем добавить небольшое количество глобальных или интегральных параметров в состояние ShardchainState
(например, общий баланс всех счетов, принадлежащих этому сегменту, или общее количество сообщений во всех выходных очередях).
Однако (23) является хорошим первым приближением того, как выглядит глобальное состояние shardchain, по крайней мере, с логической (высокоуровневой) точки зрения. Формальное описание алгебраических типов AccountState и ShardchainState может быть выполнено с помощью TL-схемы (см. 2.2.5), которая будет предоставлена в другом месте.
2.5.2. Разделение и слияние состояний шардчейна. Обратите внимание, что в парадигме конечного осколочного описания состояния цепочки осколков (23) показано, как это состояние должно обрабатываться при разделении или объединении осколков. На самом деле эти преобразования состояний оказываются очень простыми операциями с хэш-картами.

2.5.3. Состояние цепочки счетов. Состояние (виртуальной) цепочки учетных записей- это просто состояние одной учетной записи, описываемое типом AccountState. Обычно он имеет все или некоторые поля, перечисленные в 2.3.20, в зависимости от используемого конструктора.
2.5.4. Состояние глобальной рабочей цепи. Аналогично (23), мы можем определить состояние глобальной рабочей цепочки по той же формуле, но с account_id's разрешено принимать любые значения, а не только те, которые принадлежат одному шарду. Замечания, аналогичные замечаниям, сделанным в 2.5.1, применимы и в этом случае: мы можем разбить эту хэш- карту на несколько хэш-карт и добавить некоторые интегральные параметры
, такие как общий баланс.
По сути, глобальное состояние рабочей цепочки должно быть задано тем же типом
ShardchainState, что и состояние shardchain, потому что это состояние shardchain, которое мы получили бы, если бы все существующие осколки этой рабочей цепочки внезапно слились в одну.
2.5.5. Низкоуровневая перспектива: мешок клеток . Существует также низкоуровневое описание состояния цепочки учетных записей или шардчейна, дополняющее описание высокого уровня, приведенное выше. Это описание довольно важно, потому что оно оказывается довольно универсальным, обеспечивая общую основу для представления, хранения, сериализации и передачи по сети практически всех данных, используемых блокчейном TON (блоки, состояния shardchain, хранение смарт- контрактов
, доказательства Merkle и т. Д.). В то же время,такой универсальный низкоуровневый
39 2.5. Состояние глобальной цепочки шардов. Философия мешка клеток. описание, однажды понятое и реализованное, позволяет нам сосредоточить наше внимание только на соображениях высокого уровня.
Напомним, что TVM представляет значения произвольных алгебраических типов
(включая, например, ShardchainState of (23)) с помощью дерева ячеек TVM, или сокращенно ячеек (см. 2.3.14 и 2.2.5).
Любая такая ячейка состоит из двух байтов дескриптора, определяющих определенные ags и значения 0 ≤ b ≤ 128, количество необработанных байтов, и 0 ≤ c ≤ 4, количество ссылок на другие ячейки. Затем следуют необработанные байты b и ссылки на ячейки c.
18
Точный формат ссылок на ячейки зависит от реализации и от того, находится ли ячейка в ОЗУ, на диске, в сетевом пакете, в блоке и так далее. Полезная абстрактная модель состоит в том, чтобы представить, что все ячейки хранятся в адресуемой содержимому памяти, а адрес ячейки равен ее хэшу (sha256). Напомним, что (Merkle) хэш ячейки вычисляется точно путем замены ссылок на ее дочерние ячейки их (рекурсивно вычисленными) хэшами и хеширования результирующей байтовой строки.

Таким образом, если мы используем хэши ячеек для ссылок на ячейки (например, внутри описаний других ячеек), система несколько упрощается, и хэш ячейки начинает совпадать с хэшем байтовой строки, представляющей ее.
Теперь мы видим, что любой объект, представляемый TVM, включая глобальное состояние shardchain, может быть представлен в виде пакета ячеек, т.
Е. Набора ячеек вместе с корневой ссылкой на одну из них (например, хэшем). Обратите внимание, что дубликаты ячеек удаляются из этого описания (пакет ячеек-это набор ячеек, а не мультимножество ячеек), поэтому представление абстрактного дерева может фактически стать представлением ориентированного ациклического графа (dag).
Можно даже сохранить это состояние на диске в B-или B + -дереве, содержащем все рассматриваемые ячейки (возможно, с некоторыми дополнительными данными, такими как высота поддерева или счетчик ссылок), индексируемыми хэшем ячейки. Однако наивная реализация этой идеи приведет к тому, что состояние одного смарт-контракта будет разбросано по удаленным частям дискового файла, чего мы предпочли бы избежать.
19 18
Можно показать, что, если доказательства Меркла для всех данных, хранящихся в дереве ячеек, необходимы одинаково часто, следует использовать ячейки с b + ch ≈ 2(h + r), чтобы минимизировать средний размер доказательства Меркла, где h = 32-размер хэша в байтах, а r ≈ 4 -размер байта ссылки на ячейку.
Другими словами, ячейка должна содержать либо две ссылки и несколько необработанных байтов, либо одну ссылку и около 36 необработанных байтов, либо вообще никаких ссылок с 72 необработанными байтами.
19
Лучшей реализацией было бы сохранить состояние смарт-контракта в виде сериализованной строки, если она маленькая, или в отдельном B-дереве, если оно большое; тогда структура верхнего уровня
, представляющая состояние блокчейна, будет B-деревом, листья которого могутсодержат ссылки на другие B-деревья.
40 2.5. Состояние глобальной цепочки шардов. Философия мешка клеток.
Теперь мы подробно объясним , как почти все объекты, используемые блокчейном TON, могут быть представлены в виде мешков ячеек, демонстрируя тем самым универсальность этого подхода.
2.5.6. Блок Shardchain в виде мешка ячеек . Сам блок shardchain также может быть описан алгебраическим типом и сохранен в виде пакета ячеек .
Тогда наивное двоичное представление блока может быть получено просто путем конкатенации байтовых строк, представляющих каждую из ячеек в пакете ячеек, в произвольном порядке. Это представление может быть улучшено и оптимизировано, например, путем предоставления списка наборов o всех ячеек в начале блока и замены хэш-ссылок на другие ячейки 32-битными индексами в этом списке, когда это возможно. Однако следует представить, что блок
-это , по сути, мешок ячеек, а все остальные технические детали-это лишь незначительные проблемы оптимизации и реализации.
2.5.7. Обновление объекта в виде пакета ячеек . Представьте , что у нас есть старая версия некоторого объекта, представленная в виде мешка ячеек, и что мы хотим представить новую версию того же объекта, предположительно не слишком

отличающуюся от предыдущей. Можно просто представить новое состояние как еще один пакет ячеек с собственным корнем и удалить из него все ячейки, встречающиеся в старой версии. Оставшийся пакет ячеек-это, по сути, обновление объекта. Все, у кого есть старая версия этого объекта и обновление можно вычислить новую версию, просто объединив два пакета ячеек и удалив старый корень (уменьшив его счетчик ссылок и освободив ячейку, если счетчик ссылок станет нулевым).
2.5.8. Обновление состояния учетной записи. В частности, обновления состояния учетной записи, или глобального состояния цепочки шардов, или любой хэш-карты могут быть представлены с использованием идеи, описанной в 2.5.7. Это означает, что когда мы получаем новый блок цепочки шардов (который представляет собой мешок ячеек), мы интерпретируем этот мешок ячеек не так.просто сам по себе, но сначала объединив его с мешком ячеек, представляющих предыдущее состояние цепочки осколков. В этом смысле каждый блок может содержать все состояние блокчейна.
2.5.9. Обновления блока. Напомним ,что блок сам по себе является мешком ячеек, поэтому, если возникает необходимость отредактировать блок , можно аналогичным образом определить обновление блока как мешок ячеек, интерпретируемый в присутствии мешка ячеек
, который является предыдущей версией этого блока. Это примерно идея вертикальных блоков, обсуждаемая в 2.1.17.
41 2.5. Состояние глобальной цепочки шардов. Философия мешка клеток.
2.5.10. Доказательство Меркле как мешок клеток . Обратите внимание, что (обобщенное) доказательство Меркля, например, утверждающее, что x[i] = y, начиная с известного значения Hash(x) = h (см. 2.3.10 и 2.3.15), также может быть представлено в виде мешка ячеек . А именно, нужно просто предоставить подмножество ячеек
, соответствующее пути от корня x: Hashmap (n, X) до его нужного листа с индексом i :
2 n и значение y: X. Ссылки на дочерние элементы этих ячеек, не лежащие на этом пути, останутся неразрешенными в этом доказательстве, представленном хэшами ячеек. Можно также обеспечить одновременное доказательство Меркля, скажем, x[i] = y и x [i] = y , включив в мешок ячеек ячейки, лежащие на объединении двух путей от корня x до листьев, соответствующих индексам i и i .
2.5.11. Доказательства Меркля как ответы на запросы от полных узлов. По сути, полный узел с полной копией состояния shardchain (или account-chain) может предоставить Merkle proof по запросу легкого узла (например, сетевого узла, работающего с облегченной версией клиента TON Blockchain), позволяя получателю выполнять некоторые простые запросы без внешней помощи,использование только ячеек, представленных в этом доказательстве Меркла. Легкий узел может отправлять свои запросы

в сериализованном формате полному узлу и получать правильные ответы с
Доказательства Меркла или только доказательства Меркла, потому что запрашивающий должен иметь возможность вычислять ответы, используя только ячейки, включенные в доказательство
Меркла.
Это доказательство Merkle будет состоять просто из пакета ячеек , содержащих только те ячейки, принадлежащие к состоянию shardchain, которые были доступны полному узлу при выполнении запроса легкого узла. Этот подход может быть использован, в частности, для выполнения get-запросов смарт-контрактов (см. 4.3.12).
2.5.12. Дополненное обновление или обновление состояния с доказательством действительности Merkle. Напомним (см. 2.5.7), что мы можем описать изменения состояния объекта от старого значения x : X к новому значению x : X с помощью обновления , которое представляет собой просто пакет ячеек, содержащий те ячейки, которые лежат в поддереве
, представляющем новое значение x, но не вподдерево,представляющее старое значение x, поскольку предполагается, что получатель имеет копию старого значения x и всех его ячеек.
Однако, если получатель не имеет полной копии x, но знает только свой (Merkle) хэш h = Hash(x), он не сможет проверить достоверность обновления (т. Е. Что все висячие ссылки на ячейки в обновлении ссылаются на ячейки, присутствующие в деревеиз x). Хотелось бы иметь проверяемые обновления, дополненные доказательствами Меркле существования всех упомянутых клеток в старом состоянии.
Тогда любой, кто знает только h = Hash(x), сможет проверить достоверность обновления и вычислить новый h = Hash(x) сам по себе.
42 2.5. Состояние глобальной цепочки шардов. Философия мешка клеток.
Поскольку наши доказательства Меркля представляют собой мешки самих клеток (см.
2.5.10), можно построить такое дополненное обновление как мешок клеток , содержащий старый корень x, некоторые из его потомков вместе с путями от корня x к ним, а также новый корень x и все его потомкикоторые не являются частью x.
2.5.13. Обновление состояния учетной записи в блоке shardchain. В частности, обновления состояния учетной записи в блоке shardchain должны быть дополнены, как описано в 2.5.12. В противном случае кто-то может зафиксировать блок, содержащий недопустимое обновление состояния, ссылаясь на ячейку, отсутствующую в старом состоянии; доказать недействительность такого блока было бы проблематично (как претендент может доказать, что ячейка не является частью предыдущего состояния?).
Теперь, если все обновления состояний, включенные в блок, дополнены, их действительность легко проверяется, и их недействительность также легко показывается как нарушение рекурсивного свойства определения (обобщенных) хэшей Меркла.
2.5.14. Все - мешок философии клеток. Предыдущие соображения показывают, что все, что нам нужно хранить или передавать, либо в

блокчейне TON, либо в сети, представляется в виде мешка ячеек . Это важная часть философии дизайна блокчейна TON. После объяснения подхода bag of cells и определения некоторых низкоуровневых сериализаций bags of cells можно просто определить все (формат блока, shardchain и состояние учетной записи и т. Д.) На высоком уровне абстрактных (зависимых) алгебраических типов данных.
Объединяющий эффект философии everything is a bag of cells значительно упрощает реализацию, казалось бы, несвязанных услуг; см. 5.1.9 для примера с использованием платежных каналов.
2.5.15. Заголовки блоков для блокчейнов TON. Обычно блок в блокчейне начинается с небольшого заголовка, содержащего хэш предыдущего блока, время его создания, хеш Меркла дерева всех транзакций
, содержащихся в блоке, и так далее. Тогда хэш блока определяется как хэш этого небольшого заголовка блока. Поскольку заголовок блока в конечном счете зависит от всех данных, включенных в блок, невозможно изменить блок, не изменив его хэш.
В подходе bag of cells, используемом блоками блокчейнов TON, нет назначенного заголовка блока. Вместо этого хэш блока определяется как хэш
(Merkle) корневой ячейки блока. Поэтому верхнюю (корневую) ячейку блока можно считать небольшим заголовком этого блока.
43 2.6. Создание и проверка новых блоков
Однако корневая ячейка может содержать не все данные, обычно ожидаемые от такого заголовка. По сути, нужно, чтобы заголовок содержал некоторые поля, определенные в типе данных блока. Обычно эти поля будут содержаться в нескольких ячейках, включая корень. Это ячейки, которые вместе составляют доказательство Меркля для значений рассматриваемых полей. Можно было бы настаивать на том, что блок содержит эти ячейки заголовка в самом начале, перед любыми другими ячейками. Тогда нужно будет загрузить только первые несколько байтов сериализации блока , чтобы получить все ячейки заголовка и изучить все ожидаемые поля.
2.6
Создание и проверка новых блоков
Блокчейн TON в конечном итоге состоит из блоков shardchain и masterchain
. Эти блоки должны быть созданы, проверены и распространены по сети среди всех заинтересованных сторон, чтобы система функционировала плавно и правильно.
2.6.1. Валидаторы. Новые блоки создаются и проверяются специальными узлами, называемыми валидаторами. По сути, любой узел, желающий стать валидатором, может стать им при условии, что он сможет внести достаточно большую ставку
(в тонных монетах, т. е. В тонных монетах; см. Приложение А) в мастер-цепочку.

Валидаторы получают некоторые награды за хорошую работу, а именно транзакционные, складские и газовые сборы со всех транзакций (сообщений), зафиксированных во вновь сгенерированных блоках, и некоторые новоиспеченные монеты, отражающие благодарность всего сообщества валидаторам за поддержание работы блокчейна TON.
Этот доход распределяется между всеми участвующими валидаторами пропорционально их ставкам.
Однако быть валидатором - это большая ответственность. Если валидатор подписывает недействительный блок, он может быть наказан потерей части или всей своей ставки, а также временным или постоянным исключением из набора валидаторов. Если валидатор не участвует в создании блока, он не получает свою долю вознаграждения, связанного с этим блоком. Если валидатор воздерживается от создания новых блоков в течение длительного времени, он может потерять часть своей доли и быть приостановлен или навсегда исключен из набора валидаторов.
Все это означает, что валидатор не получает свои деньги даром .
Действительно, он должен отслеживать состояния всех или некоторых шардчейнов
(каждый валидатор отвечает за проверку и создание новых блоков в определенном подмножестве шардчейнов), выполнять все вычисления, запрошенные smart con-
44 2.6. Создание и проверка новых блоков тракты в этих шардчейнах, получать обновления о других шардчейнах и так далее. Эта деятельность требует значительного дискового пространства, вычислительной мощности и пропускной способности сети.
2.6.2. Валидаторы вместо майнеров. Напомним, что блокчейн TON использует подход Proof-of-Stake вместо подхода Proof-of-Work, принятого
Биткойном, текущей версией Ethereum и большинством других криптовалют.
Это означает, что нельзя добыть новый блок, представив некоторое доказательство работы (вычисление большого количества бесполезных хэшей) и получить в результате несколько новых монет. Вместо этого нужно стать валидатором и тратить свои вычислительные ресурсы на хранение и обработку запросов и данных TON Blockchain. Короче говоря, нужно быть валидатором, чтобы добывать новые монеты. В этом отношении валидаторы- это новые майнеры.
Однако есть и другие способы заработать монеты, кроме того, чтобы быть валидатором.
2.6.3. Номинаторы и майнинг-пулы . Чтобы стать валидатором, обычно нужно купить и установить несколько высокопроизводительных серверов и приобрести для них хорошее интернет-соединение. Это не так дорого, как оборудование ASIC, необходимое в настоящее время для добычи биткойнов. Тем не менее,

вы не можете добывать монеты new TON на домашнем компьютере, не говоря уже о смартфоне.
В сообществах майнинга криптовалют Bitcoin, Ethereum и других Proof-of-Work существует понятие майнинговых пулов, где множество узлов, обладающих недостаточной вычислительной мощностью для самостоятельной добычи новых блоков, объединяют свои ресурсы и впоследствии делятся вознаграждением.
Соответствующее понятие в мире Proof-of-Stake-это понятие номинатора.
По сути, это узел, предоставляющий свои деньги, чтобы помочь валидатору увеличить свою ставку; затем валидатор распределяет соответствующую долю своего вознаграждения
(или некоторую ранее согласованную часть, скажем, 50%) номинатору.
Таким образом, номинатор также может принять участие в майнинге и получить некоторое вознаграждение, пропорциональное сумме денег, которую он готов внести для этой цели. Он получает лишь часть соответствующей доли вознаграждения валидатора, поскольку предоставляет только капитал , но не нуждается в покупке вычислительной мощности, хранилища и пропускной способности сети.
Однако, если валидатор теряет свою долю из-за недопустимого поведения, номинатор также теряет свою долю доли. В этом смысле номинатор разделяет риск. Он должен выбрать назначенного валидатора с умом, иначе он может потерять деньги. В этом смысле номинаторы принимают взвешенное решение и голосуют за определенных валидаторов своими средствами.
45 2.6. Создание и проверка новых блоков
С другой стороны, эта система номинации или кредитования позволяет стать валидатором, не вкладывая сначала большую сумму денег в монеты TON. Другими словами, это мешает тем, кто держит большое количество монет TON, монополизировать поставку валидаторов.
2.6.4. Рыбаки: получение денег путем указания на чужие ошибки. Еще один способ получить некоторые награды, не будучи валидатором, - стать шерманом. По сути, любой узел может стать шерманом, сделав небольшой депозит в masterchain. Затем он может использовать специальные транзакции masterchain для публикации (Merkle) доказательств недействительности некоторых (обычно shardchain) блоков, ранее подписанных и опубликованных валидаторами. Если другие валидаторы согласны с этим доказательством недействительности, окончательные валидаторы o являются каламбуромвыигрывает (теряя часть своей ставки), а шерман получает некоторую награду
(часть монет, собранных с валидаторов o ending). После этого недопустимый блок (shardchain) должен быть исправлен, как описано в 2.1.17.
Исправление недопустимых блоков masterchain может включать создание вертикальных блоков поверх ранее зафиксированных блоков masterchain (см. 2.1.17); нет необходимости создавать форк masterchain.
Обычно шерман должен стать полным узлом хотя бы для некоторых шардчейнов и потратить некоторые вычислительные ресурсы, запустив код

хотя бы некоторых смарт-контрактов. Хотя шерману не нужно иметь столько вычислительной мощности, сколько валидатору, мы считаем, что естественным кандидатом на роль шермана является потенциальный валидатор, который готов обрабатывать новые блоки, но еще не был избран в качестве валидатора (например, из-за неспособности внести suдостаточно большая ставка).
2.6.5. Collators: получение денег путем предложения новых блоков валидаторам. Еще один способ получить некоторые награды, не будучи валидатором
, - стать collator. Это узел, который готовит и предлагает валидатору новые кандидаты на блок shardchain, дополненные (сопоставленные) данными, взятыми из состояния этого shardchain и из других (обычно соседних) shardchain, наряду с подходящими доказательствами Merkle. (Это необходимо, например, когда некоторые сообщения нужно переадресовывать из соседних шардчейнов.) Тогда валидатор может легко проверить предложенного кандидата блока на валидность, без необходимости загружать полное состояние этой или других шардчейнов.
Поскольку валидатору необходимо представить новых (сопоставленных) кандидатов на блок, чтобы получить некоторые награды ( майнинг), имеет смысл заплатить некоторую часть вознаграждения сборщику, готовому предоставить подходящих кандидатов на блок. Таким образом,
46 2.6. Создание и проверка новых блоков валидатор может освободиться от необходимости следить за состоянием соседних шардчейнов, передав его на аутсорсинг collator.
Однако мы ожидаем, что на начальном этапе развертывания системы не будет отдельных назначенных сопоставителей, поскольку все валидаторы смогут действовать как сопоставители для себя.
2.6.6. Collators или validators: получение денег для включения транзакций пользователя. Пользователи могут открывать каналы микроплатежей некоторым сборщикам или валидаторам и платить небольшие суммы монет в обмен на включение своих транзакций в shardchain.
2.6.7. Выборы набора глобальных валидаторов. Глобальный набор валидаторов избирается один раз в месяц (фактически каждые 2 19 masterchain блокирует). Этот набор определено и общеизвестно за месяц вперед.
Чтобы стать валидатором, узел должен перевести несколько монет TON в masterchain, а затем отправить их в специальный смарт-контракт в качестве предложенных ставок. Другим параметром, отправленным вместе с ставкой, является l ≥
1, максимальная проверяющая нагрузка, которую этот узел готов принять относительно минимально возможной. Существует также глобальная верхняя граница (еще один контролируемый параметр). L на l, равное, скажем, 10.
Затем глобальный набор валидаторов избирается этим смарт - контрактом, просто выбирая до T кандидатов с максимальными предложенными ставками и публикуя

их личности. Первоначально общее количество валидаторов равно T = 100; мы ожидаем, что оно вырастет до 1000 по мере увеличения нагрузки. Это контролируемый параметр
(см. 2.1.21).
Фактическая ставка каждого валидатора вычисляется следующим образом: предлагаемые ставки
1
≥ с
2
≥ * · · · s
T
, фактическая ставка i-го валидатора равна установить в s i
: = мин (с i
, л i
* s
T
)
. Таким образом, s i
/ с
T
≤ l i
, таким образом, i-й валидатор делает не более l i
≤ L - кратная нагрузка самого слабого валидатора (потому что нагрузка в конечном счете пропорциональна ставке).
Затем избранные валидаторы могут отозвать неиспользованную часть своей доли, s i
- с i
. Неудачные кандидаты-валидаторы могут отозвать все свои предложенные кандидатуры. кол.
Каждый валидатор публикует свой открытый ключ подписи, не обязательно равный открытый ключ учетной записи, с которой была сделана ставка.
20
Ставки валидаторов замораживаются до конца срока, на который они были избраны, и еще на один месяц, в случае новых споров
20
Имеет смысл генерировать и использовать новую пару ключей для каждого выбора валидатора.
47 2.6. Создание и проверка новых блоков возникает (т. е. обнаруживается недопустимый блок, подписанный одним из этих валидаторов). После этого возвращается ставка вместе с долей валидатора отчеканенных монет и комиссиями от транзакций, обработанных за это время.
2.6.8. Выборы рабочих групп валидаторов . Весь глобальный набор валидаторов (где каждый валидатор считается присутствующим с кратностью, равной его доле, иначе у валидатора может возникнуть соблазн принять несколько идентичностей и разделить свою долю между ними) используется только для проверки

новых блоков masterchain. Блоки shardchain проверяются только специально выбранными подмножествами валидаторов, взятыми из глобального набора валидаторов, выбранных, как описано в 2.6.7.
Эти подмножества валидаторов или группы задач, определенные для каждого осколка, вращается каждый час (на самом деле, каждые 2 10 блоки masterchain), и они известны за час вперед, так что каждый валидатор знает, какие осколки ему нужно будет проверить, и может подготовиться к этому (например, загрузив недостающие данные shardchain).
Алгоритм, используемый для выбора групп задач валидатора для каждого осколка (w, s)
, является детерминированным псевдослучайным. Он использует псевдослучайные числа, встроенные валидаторами в каждый блок masterchain (генерируемый консенсусом с использованием пороговых сигнатур), чтобы создать случайное семя, а затем вычисляет
, например, хэш(code(w). code(s).validator_id. rand_seed) для каждого валидатора.
Затем валидаторы сортируются по значению этого хэша, и выбираются первые несколько, чтобы иметь не менее 20 / T от общего количества ставок валидатора и состоять как минимум из 5 валидаторов.
Этот выбор может быть сделан с помощью специального смарт-контракта. В этом случае алгоритм выбора будет легко обновляться без хардфорков с помощью механизма голосования, упомянутого в 2.1.21. Все остальные константы, упомянутые до сих пор (например, 2 19
, 2 10
, T, 20 и 5) также являются контролируемыми параметрами.
2.6.9. Чередование приоритетов в каждой целевой группе. Существует определенный порядок приоритета, налагаемый на членов целевой группы shard, в зависимости от хэша предыдущего блока masterchain и порядкового номера блока (shardchain). Этот порядок определяется путем генерации и сортировки некоторых хэшей, как описано выше.
Когда необходимо создать новый блок shardchain, валидатор целевой группы shard
, выбранный для создания этого блока, обычно является первым по отношению к этому вращающемуся порядку приоритета. Если не удается создать блок, это может сделать второй или третий валидатор. По сути, все они могут предложить своих кандидатов в блок
, но кандидат, предложенный валидатором, имеет самый высокий
48 2.6. Создание и проверка новых блоков

приоритет должен выиграть в результате византийского отказоустойчивого (BFT) консенсусного протокола.
2.6.10. Распространение кандидатов в блоки shardchain. Поскольку членство в целевой группе shardchain известно за час вперед, их члены могут использовать это время для создания выделенной сети многоадресного наложения валидаторов осколков
, используя общие механизмы сети TON (см. 3.3). Когда новый блок shardchain должен быть сгенерирован обычно через одну или две секунды после распространения последнего блока masterchain, все знают, кто имеет наивысший приоритет для генерации следующего блока (см. 2.6.9).
Этот валидатор создаст новый сопоставленный блок-кандидат либо сам по себе, либо с помощью сопоставителя (см. 2.6.5). Валидатор должен проверить (валидировать) этот кандидат на блок (особенно если он был подготовлен каким-либо сборщиком) и подписать его своим закрытым ключом (валидатором). Затем кандидат на блок распространяется на остальную часть целевой группы с использованием заранее подготовленной многоадресной оверлейной сети (целевая группа создает свою собственную частную оверлейную сеть, как описано в 3.3, а затем использует версию протокола потоковой многоадресной рассылки, описанную в 3.3.15, для распространения кандидатов на блок).
По-настоящему BFT-способом сделать это было бы использовать византийский протокол многоадресной рассылки, такой как тот, который используется в Honey Badger
BFT [11]: закодировать кандидата блока кодом (N, 2N/3) - стирания, отправить 1/N результирующих данных непосредственно каждому члену блока
.группа и ожидайте, что они будут напрямую передавать свою часть данных всем другим членам группы.
Однако более быстрый и простой способ сделать это (см. также
3.3.15) состоит в том, чтобы разбить кандидата блока на последовательность подписанных блоков ( блоков) в один килобайт, увеличить их последовательность кодом Рида
Соломона или кодом фонтана (например, кодом RaptorQ [9] [14]).и начать передавать куски соседям в многоадресной сетке (т. Е. В оверлейной сети), ожидая, что они будут распространять эти куски дальше. Как только валидатор получает достаточное количество блоков
, чтобы восстановить из них кандидата в блок, он подписывает квитанцию подтверждения и распространяет ее через своих соседей на всю группу. Затем его соседи перестают посылать ему новые куски, но могут продолжать посылать
(исходные) подписи этих кусков, полагая, что этот узел может генерировать последующие куски, применяя код Рида Соломона или фонтана сам по себе
(имея все необходимые данные), объединять их с сигнатурами и распространять на своих соседейкоторые еще не готовы.
Если многоадресная сеть (overlay network) остается подключенной после удаления всех плохих узлов (напомним, что до одной трети узлов могут быть

49 2.6. Создание и проверка новых блоков плохо по-византийски, т. Е. Вести себя произвольно злонамеренно), этот алгоритм будет распространять кандидата на блок как можно быстрее.
Не только назначенный высокоприоритетный создатель блока может многоадресно передавать своего кандидата на блок всей группе. Второй и третий валидаторы по приоритету могут начать многоадресную рассылку своих кандидатов на блок либо сразу
, либо после того, как не получат кандидата на блок от валидатора с высшим приоритетом.
Однако обычно только кандидат на блок с максимальным приоритетом будет подписан всеми (фактически, по крайней мере, двумя третями целевой группы) валидаторами и зафиксирован как новый блок shardchain.
2.6.11. Валидация кандидатов в блоки. После того,как кандидат блока получен валидатором и проверена подпись его исходного валидатора, принимающий валидатор проверяет действительность этого кандидата блока, выполняя все транзакции в нем и проверяя, совпадает ли их результат с заявленным. Все сообщения, импортированные из других блокчейнов, должны быть подкреплены подходящими доказательствами Меркла в сопоставленных данных, в противном случае кандидат на блок считается недействительным (и, если доказательство этого зафиксировано в masterchain, валидаторы, уже подписавшие этого кандидата в блокчейн, могут быть наказаны). С другой стороны, если кандидат в блок признан действительным, принимающий валидатор подписывает его и распространяет свою подпись другим валидаторам в группе либо через многоадресную сеть mesh, либо с помощью прямых сетевых сообщений.
Мы хотели бы подчеркнуть, что валидатору не нужен доступ к состояниям этой или соседних шардчейнов, чтобы проверить валидность
(сопоставленного) кандидата на блок.
21
Это позволяет валидации проходить очень быстро (без доступа к диску) и облегчает вычислительную нагрузку и нагрузку на хранилище для валидаторов (особенно если они готовы принять услуги внешних сортировщиков для создания кандидатов на блоки).
2.6.12. Выборы следующего кандидата блока. Как только кандидат на блок собирает не менее двух третей (по доле) подписей валидаторов в целевой группе, он имеет право быть зафиксированным в качестве следующего блока shardchain.
Протокол BFT запускается для достижения консенсуса по выбранному кандидату на блок
(может быть предложено несколько),все хорошие валидаторы предпочитают кандидата с наивысшим приоритетом для этого раунда. В результате
21
Возможным исключением является состояние выходных очередей соседних шардчейнов, необходимых для обеспечения требований к порядку сообщений, описанных в 2.4.21, поскольку размер доказательств Merkle в этом случае может стать недопустимым.

50 2.6. Создание и проверка новых блоков при выполнении этого протокола блок дополняется подписями не менее двух третей валидаторов (по ставке). Эти подписи свидетельствуют не только о действительности рассматриваемого блока, но и о том, что он избран протоколом BFT
. После этого блок (без сопоставленных данных) объединяется с этими сигнатурами, сериализуется детерминированным образом и распространяется по сети всем заинтересованным сторонам.
2.6.13. Валидаторы должны сохранять подписанные ими блоки. Во время их членства в рабочей группе и не менее одного часа (а точнее
2 10 блоки) после этого валидаторы должны сохранить блоки, которые они подписали и зафиксировали. Непредоставление подписанного блока другим валидаторам может быть наказано.
2.6.14. Распространение заголовков и подписей новых блоков shardchain на все валидаторы. Валидаторы распространяют заголовки и подписи вновь созданных блоков shardchain в глобальный набор валидаторов, используя многоадресную ячеистую сеть, аналогичную той, которая создается для каждой группы задач.
2.6.15. Генерация новых блоков masterchain. После того, как все (или почти все) новые блоки shardchain были сгенерированы, может быть сгенерирован новый блок masterchain. Процедура по существу такая же, как и для блоков shardchain(см. 2.6.12), с той разницей, что в этом процессе должны участвовать все валидаторы (или, по крайней мере, две трети из них). Поскольку заголовки и подписи новых блоков shardchain распространяются на все валидаторы, хэши новейших блоков в каждой цепочке shardchain могут и должны быть включены в новый блок masterchain. Как только эти хэши зафиксированы в блоке masterchain, внешние наблюдатели и другие шардчейны могут считать новые блоки шардчейнов зафиксированными и неизменяемыми (см. 2.1.13).
2.6.16. Валидаторы должны сохранять состояние masterchain. Примечательное различие между masterchain и shardchains заключается в том, что все валидаторы должны отслеживать состояние masterchain, не полагаясь на сопоставленные данные. Это важно, потому что знание групп задач валидатора выводится из состояния мастер-цепочки.
2.6.17. Блоки Shardchain генерируются и распространяются параллельно.
Обычно каждый валидатор является членом нескольких групп задач shardchain; их количество (следовательно, нагрузка на валидатор) примерно пропорционально доле валидатора. Это означает, что валидатор параллельно запускает несколько экземпляров нового протокола генерации блоков shardchain.
51 2.6. Создание и проверка новых блоков
2.6.18. Смягчение атак удержания блоков. Поскольку полный набор валидаторов вставляет хэш нового блока shardchain в мастер-цепочку после

просмотра только его заголовка и подписей, существует небольшая вероятность того, что валидаторы, создавшие этот блок, сговорятся и попытаются избежать публикации нового блока полностью. Это приведет к невозможности валидаторов соседних шардчейнов создавать новые блоки, поскольку они должны знать, по крайней мере, очередь выходных сообщений нового блока, как только его хэш будет зафиксирован в мастер-цепочке.
Чтобы смягчить это, новый блок должен собрать подписи от некоторых других валидаторов (например, две трети объединения целевых групп соседних шардчейнов), свидетельствующие о том, что эти валидаторы действительно имеют копии этого блока и готовы отправить их любым другим валидаторам, если потребуется. Только после того, как эти подписи будут представлены, хэш нового блока может быть включен в мастер
-цепочку.
2.6.19. Блоки Masterchain генерируются позже блоков shardchain. Блоки Masterchain генерируются примерно раз в пять секунд, как и блоки shardchain. Однако, в то время как генерация новых блоков во всех шардчейнах выполняется по существу одновременно (обычно вызывается выпуском нового блока мастерчейна), генерация новых блоков мастерчейна намеренно задерживается, чтобы включить хэши вновь сгенерированных блоков шардчейна в мастерчейн.
2.6.20. Медленные валидаторы могут получать меньшие вознаграждения. Если валидатор работает медленно, он может не проверить кандидатов в новые блоки, и две трети подписей, необходимых для фиксации нового блока, могут быть собраны без его участия. В этом случае он получит меньшую долю вознаграждения
, связанного с этим блоком.
Это дает валидаторам стимул оптимизировать свое оборудование, программное обеспечение и сетевое соединение, чтобы обрабатывать транзакции пользователей как можно быстрее.
Однако, если валидатор не подписывает блок до его фиксации, его подпись может быть включена в один из следующих блоков, а затем в часть вознаграждения (экспоненциально уменьшающуюся в зависимости от того, сколько блоков было сгенерировано, например, с 0.9 k если валидатор опаздывает на k блоков) все равно будет передан этому валидатору.
2.6.21. Глубина подписей валидатора. Обычно, когда валидатор подписывает блок, подпись свидетельствует только об относительной валидности блока:
52 2.6. Создание и проверка новых блоков этот блок действителен при условии, что все предыдущие блоки в этой и других цепочках шардов

действительны. Валидатор не может быть наказан за то, что принял как должное неверные данные, зафиксированные в предыдущих блоках.
Однако сигнатура валидатора блока имеет целочисленный параметр
, называемый глубиной . Если он не равен нулю, это означает, что валидатор также утверждает
(относительную) достоверность указанного числа предыдущих блоков. Это способ для медленных или временно отключенных валидаторов догнать и подписать некоторые блоки, которые были зафиксированы без их подписей. Тогда какая
-то часть награды за блок все равно будет отдана им (см. 2.6.20).
2.6.22. Валидаторы несут ответственность за относительную валидность подписанных блоков shardchain; за абсолютной валидностью следует. Мы хотели бы еще раз подчеркнуть, что подпись валидатора на блоке B цепи шардов свидетельствует только об относительной валидности этого блока (или, может быть, и предыдущих блоков d
, если подпись имеет глубину d, см. 2.6.21; но это не сильно влияет на последующее обсуждение). Другими словами, валидатор утверждает, что следующее состояние s цепочки осколков получено из предыдущего состояния s путем применения функции оценки блока ev_block, описанной в 2.2.6: s = ev_block (B) (s)
(24)
Таким образом, валидатор, подписавший блок B, не может быть наказан, если исходное состояние s окажется неверным (например, из - за недействительности одного из предыдущих блоков). Шерман (см. 2.6.4) должен жаловаться только в том случае, если он находит блок, который относительно недействителен. Система PoS в целом стремится сделать каждый блок относительно валидным, а не рекурсивно (или абсолютно) валидным.
Обратите внимание, однако, что если все блоки в блокчейне относительно действительны, то все из них и блокчейн в целом абсолютно верны; это утверждение легко показать с помощью математической индукции по длине блокчейна.
Таким образом, легко проверяемые утверждения об относительной валидности блоков вместе демонстрируют гораздо более сильную абсолютную валидность всего блокчейна.
Обратите внимание, что, подписывая блок B, валидатор утверждает, что блок действителен с учетом исходного состояния s (т. Е. Что результат (24) не является значением⊥
, указывающим на то, что следующее состояние не может быть вычислено). Таким образом, валидатор должен выполнять минимальные формальные проверки ячеек исходного состояния, к которым осуществляется доступ во время вычисления (24).
Например, представьте, что ячейка, которая, как ожидается, будет содержать исходный

баланс счета, доступ к которому осуществляется из транзакции, зафиксированной в блоке
, оказывается нулевой необработанный байт вместо ожидаемых 8 или 16. Тогда оригинал
53 2.6. Создание и проверка новых блоков баланс просто не может быть извлечен из ячейки, и необработанное исключение происходит при попытке обработать блок. В этом случае валидатор не должен подписывать такой блок под страхом наказания.
2.6.23. Подписание блоков masterchain. Ситуация с блоками masterchain несколько иная: подписывая блок masterchain, валидатор подтверждает не только его относительную валидность, но и относительную валидность всех предыдущих блоков вплоть до самого первого блока, когда этот валидатор взял на себя ответственность (но не далее).
2.6.24. Общее количество валидаторов. Верхний предел T для общего числа валидаторов, подлежащих избранию (см. 2.6.7), не может стать в описанной до сих пор системе больше, скажем, нескольких сотен или тысячи, поскольку все валидаторы должны участвовать в консенсусном протоколе BFT для создания каждого нового блока masterchain, и этоне ясно, могут ли такие протоколы масштабироваться до тысяч участников. Что еще более важно, блоки masterchain должны собирать подписи не менее двух третей всех валидаторов
(по ставкам), и эти подписи должны быть включены в новый блок (другие- мудрые все остальные узлы в системе не будут иметь оснований доверять новому блоку, не проверяя его самостоятельно). Если бы,скажем, более тысячи подписей валидатора должно было быть включено в каждый блок masterchain, это означало бы больше данных в каждом блоке masterchain, которые должны храниться всеми полными узлами и распространяться по сети, и больше вычислительной мощности
, затрачиваемой на проверку этих подписей (в PoS-системе полные узлыне нужно проверять блоки сами по себе, но вместо этого они должны проверять подписи валидаторов).
Хотя ограничение T тысячей валидаторов кажется более чем достаточным для первого этапа развертывания блокчейна TON, необходимо предусмотреть будущий рост, когда общее количество шардчейнов станет настолько большим, что несколько сотен валидаторов не смогут обработать их все. С этой целью мы вводим дополнительный контролируемый параметр T ≤ T
(первоначально равный T), и только лучшие T избранных валидаторов (по доле) должны создавать и подписывать новые блоки masterchain.
2.6.25. Децентрализация системы. Можно заподозрить, что система Proof-of-Stake, такая как блокчейн TON , полагающаяся на валидаторы T � �
1000 для создания всех блоков shardchain и masterchain, неизбежно станет слишком централизованной, в отличие от обычных блокчейнов Proof-of-Work, таких как
Bitcoin или Ethereum, где каждый (в принципе) может добыватьновый блок,
54 2.6. Создание и проверка новых блоков

без явного верхнего предела на общее количество майнеров.
Однако популярные блокчейны Proof-of-Work, такие как биткойн и
Эфириум, в настоящее время требуют огромных вычислительных мощностей (высоких хэшрейтов) для добычи новых блоков с не пренебрежимо малой вероятностью успеха. Таким образом, добыча новых блоков, как правило, сосредоточена в руках нескольких крупных игроков, которые вкладывают огромные суммы денег в центры обработки данных, заполненные специально разработанным оборудованием, оптимизированным для майнинга; и в руках нескольких крупных майнинг-пулов, которые концентрируют и координируют действия больших групп людей, которые не в состоянииобеспечить достаточный хэшрейт самостоятельно.
Таким образом, по состоянию на 2017 год более 75% новых блоков Ethereum или
Bitcoin производятся менее чем десятью майнерами. Фактически, два крупнейших пула майнинга Ethereum производят вместе более половины всех новых блоков! Очевидно, что такая система гораздо более централизована, чем система, полагающаяся на T ≈ 1000 узлов для производства новых блоков.
Можно также отметить, что инвестиции, необходимые для того, чтобы стать валидатором TON
Blockchain, т. Е. Купить оборудование (скажем, несколько высокопроизводительных серверов) и долю (которая при необходимости может быть легко собрана через пул номинаторов; см. 2.6.3), намного ниже, чем для того, чтобы стать успешным блокчейном. автономный майнер Bitcoin или Ethereum. Фактически, параметр L 2.6.7 заставит номинаторов не присоединяться к крупнейшему майнинговому пулу
(т. е. К валидатору, накопившему наибольшую долю), а искать для небольших валидаторов, в настоящее время принимающих средства от номинаторов, или даже для создания новых валидаторов, потому что это позволило бы увеличить долю s i
/ с i доли валидатора и,как следствие, номинатора, которые будут использоваться, что приведет к увеличению вознаграждения от майнинга. Таким образом, система TON
Proof-ofStake фактически поощряет децентрализацию (создание и использование большего количества валидаторов) и наказывает централизацию.
2.6.26. Относительная надежность блока. (Относительная) надежность блока
-это просто общая доля всех валидаторов, подписавших этот блок. Другими словами, это сумма денег, которую некоторые актеры потеряют, если этот блок окажется недействительным. Если речь идет о транзакциях, передающих значение ниже надежности блока, можно считать их достаточно безопасными

. В этом смысле относительная надежность-это мера доверия, которое внешний наблюдатель может иметь к конкретному блоку.
Обратите внимание, что мы говорим об относительной надежности блока, потому что это гарантия того, что блок действителен при условии, что предыдущий блок и все другие упомянутые блоки shardchains действительны (см. 2.6.22).
55 2.6. Создание и проверка новых блоков
Относительная надежность блока может возрасти после его фиксации
, например, при добавлении сигнатур запоздалых валидаторов (см. 2.6.21). С другой стороны, если один из этих валидаторов теряет часть или всю свою долю из
-за неправильного поведения, связанного с некоторыми другими блоками, относительная надежность блока может снизиться.
2.6.27. Укрепление блокчейна. Важно обеспечить стимулы для валидаторов, чтобы максимально повысить относительную надежность блоков
. Один из способов сделать это-выделить небольшое вознаграждение валидаторам за добавление подписей к блокам других шардчейнов. Даже потенциальные валидаторы, внесшие ставку, достаточную для того, чтобы попасть в топ T валидаторов по ставке и быть включенными в глобальный набор валидаторов (см. 2.6.7), могут участвовать в этой деятельности (если они согласятся сохранить свою ставку замороженной, а не вывести ее после проигрыша).выборы). Такие потенциальные валидаторы могут удвоиться как shermen (см. 2.6.4): если им все равно нужно проверить действительность определенных блоков, они могут также сообщить о недействительных блоках и получить соответствующие награды.
2.6.28. Рекурсивная надежность блока. Можно также определить рекурсивную надежность блока как минимум его относительной надежности и рекурсивных надежностей всех блоков, на которые он ссылается (т. е. Блока masterchain, предыдущего блока shardchain и некоторых блоков соседних shardchain).
Другими словами, если блок окажется недействительным, либо потому, что он недействителен сам по себе, либо потому, что один из блоков, от которого он зависит, недействителен, то, по крайней мере, эта сумма денег будет кем-то потеряна. Если вы действительно не уверены
, доверять ли конкретной транзакции в блоке, вы должны вычислить рекурсивную надежность этого блока, а не только относительную.
Не имеет смысла заходить слишком далеко назад при вычислении рекурсивной надежности, потому что, если мы заглянем слишком далеко назад, мы увидим блоки, подписанные валидаторами, чьи ставки уже разморожены и сняты. В любом случае мы не разрешаем валидаторам автоматически пересматривать старые блоки
(т. е. созданные более двух месяцев назад, если используются текущие значения контролируемых параметров) и создавать форки,начиная с них, или

корректировать их с помощью вертикальных блокчейнов (см. 2.1.17),даже если они окажутся недействительными. Мы предполагаем, что период в два месяца предоставляет широкие возможности для обнаружения и сообщения о любых недействительных блоках, так что если блок не будет оспорен в течение этого периода, он вряд ли будет оспорен вообще.
56 2.7. Разделение и слияние шардчейнов
2.6.29. Следствие Proof-of-Stake для легких узлов. Важным следствием подхода Proof-of-Stake, используемого блокчейном TON, является то, что легкий узел (работающий с легким клиентским программным обеспечением) для блокчейна TON не должен загружать заголовки всех блоков shardchain или даже masterchain
, чтобы иметь возможность самостоятельно проверить достоверность предоставленных доказательств Merkleк нему полными узлами в качестве ответов на его запросы.
Действительно, поскольку самые последние хэши блоков shardchain включены в блоки masterchain, полный узел может легко предоставить доказательство Merkle, что данный блок shardchain действителен, начиная с известного хэша блока masterchain. Далее, легкий узел должен знать только самый первый блок masterchain (где объявляется самый первый набор валидаторов), который (или
, по крайней мере, хэш которого) может быть встроен в клиентское программное обеспечение, и только один блок masterchain примерно каждый месяц после этого, где объявляются вновь избранные наборы валидаторов, поскольку этот блок будет подписан предыдущим набором валидаторов. Начиная с этого, он может получить несколько последних блоков masterchain или, по крайней мере, их заголовки и подписи валидатора и использовать их в качестве базы для проверки доказательств
Merkle, предоставляемых полными узлами.
2.7
Разделение и слияние шардчейнов
Одной из наиболее характерных и уникальных особенностей блокчейна TON является его способность автоматически разделять цепочку шардов на две части, когда нагрузка становится слишком высокой, и объединять их обратно, если нагрузка спадает (см. 2.1.10). Мы должны обсудить его более подробно из - за его уникальности и важности для масштабируемости всего проекта.
2.7.1. Конфигурация осколка. Напомним, что в любой момент времени каждая рабочая цепочка w разбивается на одну или несколько шардчейнов (w, s) (см.
2.1.8).
Эти шардчейны могут быть представлены листьями бинарного дерева с корнем
(w,∅).
, и каждый нелистовой узел (w, s), имеющий потомков (w, s.0) и (w, s.1).
Таким образом, каждая учетная запись, принадлежащая рабочей цепочке w, назначается

ровно одному сегменту, и каждый, кто знает текущую конфигурацию цепочки сегментов, может определить этот сегмент (w, s), содержащий account account_id
: это единственный осколок с двоичной строкой s, являющейся pre x account_id .
Конфигурация осколка, т. е. это бинарное дерево осколков, или совокупность всех активных (w, s) для данного w (соответствующих листьям бинарного дерева осколков), является частью состояния мастер-цепи и доступна всем
57 2.7. Разделение и слияние шардчейнов кто следит за мастерчейном.
22 2.7.2. Самая последняя конфигурация и состояние осколка. Напомним, что хэши самых последних блоков shardchain включены в каждый блок masterchain.
Эти хэши организованы в двоичное дерево shard (фактически, набор деревьев, по одному для каждой рабочей цепочки). Таким образом, каждый блок masterchain содержит самую последнюю конфигурацию shard.
2.7.3. Объявление и выполнение изменений в конфигурации осколка. Конфигурация осколка может быть изменена двумя способами: либо осколок
(w, s) может быть разделен на два осколка (w, s.0) и (w, s. 1), или два родственных осколка
(w, s. 0) и (w, s. 1) можно объединить в один осколок (w, s).
Эти операции разделения / слияния объявляются несколькими (например, 2 6
; это настраиваемый параметр) блоки заранее, сначала в заголовках соответствующих блоков shardchain, а затем в блоке masterchain, который ссылается на эти блоки shardchain. Это предварительное объявление необходимо для всех заинтересованных сторон, чтобы подготовиться к запланированным изменениям
(например, построить наложенную многоадресную сеть для распространения новых блоков вновь созданных шардчейнов, как описано в 3.3). Затем изменение фиксируется сначала в (заголовок блок) shardchain (в случае разделения; для слияния блоки обеих shardchain должны зафиксировать изменение), а затем распространяться на блок masterchain
. Таким образом, блок masterchain определяет не только самую последнюю конфигурацию осколка до его создания, но и следующую непосредственную конфигурацию осколка.
2.7.4. Группы задач валидатора для новых шардчейнов. Напомним, что каждому сегменту, т. е. каждой цепочке сегментов, обычно назначается подмножество валидаторов
( целевая группа валидаторов), предназначенных для создания и проверки новых блоков в соответствующей цепочке сегментов (см. 2.6.8). Эти целевые группы избираются на определенный

период времени (примерно один час) и известны заранее
(также примерно один час), и являются неизменными в течение этого периода.
23
Однако фактическая конфигурация осколков может измениться в течение этого периода из-за операций разделения / слияния. Вновь созданным осколкам необходимо назначить группы задач
. Это делается следующим образом:
22
На самом деле конфигурация осколка полностью определяется последней мастер-цепью блок; это упрощает получение доступа к конфигурации осколка.
23
Если только некоторые валидаторы не будут временно или постоянно заблокированы из-за подписи недопустимые блоки автоматически исключаются из всех групп задач.
58 2.7. Разделение и слияние шардчейнов
Обратите внимание, что любой активный осколок (w, s) будет либо потомком некоторого однозначно определенного исходного осколка (w, s ), что означает,что s является pre x из s, либо корнем поддерева исходных осколков (w, s), где s будетpre x каждого s . В первом случае мы просто берем группу задач исходного осколка (w, s), чтобы удвоить ее как группу задач нового осколка (w, s). В последнем случае группа задач нового осколка (w, s) будет объединением групп задач всех исходных осколков (w, s), которые являются потомками (w, s) в дереве осколков.
Таким образом, каждому активному осколку (w, s) назначается четко определенное подмножество валидаторов (целевая группа). При разделении осколка оба дочерних элемента наследуют всю группу задач от исходного осколка. Когда два осколка объединяются, их группы задач также объединяются.
Любой, кто отслеживает состояние masterchain, может вычислить группы задач валидатора для каждого из активных осколков.
2.7.5. Ограничение на операции разделения / слияния в период ответственности исходных целевых групп. В конечном итоге будет учтена новая конфигурация осколка, и каждому осколку автоматически будут назначены новые выделенные подмножества валидаторов (группы задач)
. Прежде чем это произойдет, необходимо наложить определенное ограничение на операции разделения / слияния; в противном случае исходная группа задач может в конечном итоге проверить 2 k shardchains для большого k в то же время, если исходный осколок быстро распадается на 2 k новые осколки.
Это достигается путем наложения ограничений на то, как далеко активная конфигурация осколка может быть удалена от исходной конфигурации осколка (той, которая используется для выбора групп задач валидатора, отвечающих в настоящее время). Например, можно

потребовать, чтобы расстояние в дереве осколков от активного осколка (w, s) до исходного осколка (w, s) не превышало 3, если s является предшественником s (т. Е. s является предшественником x двоичной строки s) и не должно превышатьпревышение 2, если s является преемником s (т. Е. s является pre x из s). В противном случае операция разделения или слияния не допускается.
Грубо говоря, накладывается ограничение на количество раз
, когда осколок может быть разделен (например, три) или объединен (например, два) в течение периода ответственности данной коллекции групп задач валидатора. Кроме того, после того, как осколок был создан путем слияния или разделения, он не может быть восстановлен в течение некоторого периода времени (некоторое количество блоков).
2.7.6. Определение необходимости операций разделения. Операция разделения для цепочки осколков запускается определенными формальными условиями (например, если для
64 последовательных блоков блоки цепочки осколков заполнены не менее чем на
90%). Эти условия контролируются целевой группой shardchain. Если они будут выполнены,
59 2.7. Разделение и слияние шардчейнов сначала разделенная подготовка ag включается в заголовок нового блока shardchain (и распространяется на блок masterchain, ссылающийся на этот блок shardchain). Затем, спустя несколько блоков, разделенный коммит ag включается в заголовок блока shardchain (и распространяется на следующий блок masterchain).
2.7.7. Выполнение операций разделения. После того, как разделенный коммит ag включен в блок B shardchain (w, s), не может быть последующего блока
B в этой цепочке осколков. Вместо этого два блока B
0 и B
1 из shardchains (w, s.0) и (w, s. 1), соответственно, будут созданы, оба ссылающиеся на блок B как на их предыдущий блок (и оба они будут указывать ag в заголовке, что осколок был только что разделен). Следующий блок masterchain будет содержать хэши блоков B
0 и B
1 новых шардчейнов; не разрешается содержать хэш нового блока B шардчейна (w, s), поскольку событие split commit уже было зафиксировано в предыдущем блоке мастерчейна.
Обратите внимание, что обе новые цепочки шардов будут проверены той же целевой группой валидатора, что и старая, поэтому они автоматически получат копию своего

состояния. Сама операция расщепления состояний довольно проста с точки зрения парадигмы конечного осколка (см. 2.5.2).
2.7.8. Определение необходимости операций слияния. Необходимость операций слияния осколков определяется также определенными формальными условиями
(например, если для 64 последовательных блоков сумма размеров двух блоков родственных шардчейнов не превышает 60% от максимального размера блока). Эти формальные условия также должны учитывать общее количество газа, израсходованного этими блоками, и сравнивать его с текущим лимитом газа блока, в противном случае блоки могут оказаться небольшими, поскольку существуют некоторые транзакции, требующие больших вычислений, которые препятствуют включению большего количества транзакций.
Эти условия контролируются группами задач валидатора обоих родственных сегментов (w, s.0) и (w, s. 1). Обратите внимание, что братья и сестры обязательно являются соседями по отношению к маршрутизации гиперкуба (см. 2.4.19), поэтому валидаторы из целевой группы любого осколка будут в какой-то степени контролировать родной осколок
При выполнении этих условий одна из подгрупп валидатора может предложить другой объединить их, отправив специальное сообщение. Затем они объединяются во временную объединенную целевую группу с объединенным членством , способную запускать алгоритмы консенсуса BFT и распространять обновления блоков и кандидатов в блоки, если это необходимо.
60 2.8. Классификация блокчейн - проектов
Если они достигают консенсуса о необходимости и готовности слияния, ags merge prepare фиксируются в заголовках некоторых блоков каждой цепочки шардов вместе с подписями не менее двух третей валидаторов целевой группы брата (и распространяются на следующие блоки masterchain, чтобы каждый могприготовьтесь к предстоящей разведке).
Тем не менее, они продолжают создавать отдельные блоки shardchain для некоторого заданного количества блоков.
2.7.9. Выполнение операций слияния. После этого, когда валидаторы из объединения двух исходных групп задач готовы стать валидаторами для объединенной цепочки осколков (это может включать передачу состояния из родной цепочки осколков и операцию слияния состояний), они совершают коммит слияния ag в заголовках блоков своей цепочки осколков (это событие называетсяраспространяется на следующие блоки masterchain), и прекратить создание новых блоков в отдельных шардчейнах (после появления коммита слияния ag создание блоков в отдельных шардчейнах запрещено). Вместо этого создается объединенный блок shardchain (путем объединения двух исходных групп задач), ссылающийся на оба предыдущих блока в своем заголовке . Это отражается в следующем блоке masterchain, который будет содержать хэш вновь созданного блока объединенного shardchain.

После этого объединенная целевая группа продолжает создавать блоки в объединенной цепочке шардов.
2.8
Классификация блокчейн проектов
Мы завершим наше краткое обсуждение блокчейна TON сравнением его с существующими и предлагаемыми блокчейн - проектами. Однако прежде чем сделать это, мы должны ввести достаточно общую классификацию блокчейн-проектов.
Сравнение конкретных блокчейн-проектов на основе этой классификации откладывается до 2.9.
2.8.1. Классификация блокчейн - проектов. В качестве первого шага мы предлагаем некоторые критерии классификации блокчейнов (т. е. блокчейн-проектов). Любая такая классификация является несколько неполной и поверхностной, поскольку она должна игнорировать некоторые из наиболее специфических и уникальных особенностей рассматриваемых проектов
. Тем не менее, мы считаем, что это необходимый первый шаг в предоставлении хотя бы очень приблизительной и приблизительной карты территории блокчейн-проектов
Список критериев, которые мы рассматриваем, выглядит следующим образом:
61 2.8. Классификация блокчейн - проектов
ˆ
Архитектура с одним блокчейном и несколькими блокчейнами (см. 2.8.2)
ˆ
Алгоритм консенсуса: Proof-of-Stake vs. Доказательство работы (см. 2.8.3)
ˆ
Для систем Proof-of-Stake используется точный алгоритм генерации блоков, валидации и консенсуса (два основных варианта-DPOS против BFT; см. 2.8.4)
ˆ
Поддержка произвольных (полных по Тьюрингу) смарт-контрактов (см. 2.8.6)
Мультиблоковые системы имеют дополнительные критерии классификации (см. 2.8.7).:
ˆ
Тип и правила членских блокчейнов: однородные, гетерогенные
(см. 2.8.8), смешанные (см. 2.8.9). Конфедерации (см. 2.8.10).
ˆ
Отсутствие или наличие мастер-цепи, внутренней или внешней (см. 2.8.11)
ˆ
Встроенная поддержка шардинга (см. 2.8.12). Статическое или динамическое шардирование
(см. 2.8.13).
ˆ
Взаимодействие между блокчейнами-членами: слабосвязанные и тесно связанные системы (см. 2.8.14)
2.8.2. Проекты с одним блокчейном и несколькими блокчейнами. Первым критерием классификации является количество блокчейнов в системе. Самые старые

и простые проекты состоят из одного блокчейна ( сокращенно singlechain projects); более сложные проекты используют (или, скорее, планируют использовать) несколько блокчейнов (multichain projects).
Одноцепочечные проекты, как правило, проще и лучше протестированы; они выдержали испытание временем. Их главный недостаток-низкая производительность, или, по крайней мере, пропускная способность транзакций, которая находится на уровне от десяти
(Биткоин) до менее чем ста
24
(Ethereum) транзакции в секунду для систем общего назначения. Некоторые специализированные системы (например,
Bitshares) способны обрабатывать десятки тысяч специализированных транзакций в секунду за счет необходимости сохранения состояния блокчейна в памяти и ограничения обработки заранее определенным специальным набором транзакций, которые затем выполняются высокооптимизированным кодом, написанным на таких языках, какC ++ (здесь нет виртуальных машин).
Мультицепные проекты обещают масштабируемость, которую все жаждут. Они могут поддерживать большие общие состояния и больше транзакций в секунду, за счет
24
Больше похоже на 15, на данный момент. Тем не менее, некоторые обновления планируется сделать
Пропускная способность транзакций Ethereum в несколько раз больше.
62 2.8. Классификация блокчейн - проектов сделать проект намного более сложным, а его реализацию-более сложной задачей. В результате уже запущено несколько мультицепочечных проектов, но большинство предлагаемых проектов являются мультицепочечными. Мы считаем, что будущее за мультицепными проектами.
2.8.3. Создание и проверка блоков: Proof-of-Work vs
.Proof-of -ake. Еще одним важным отличием является алгоритм и протокол, используемые для создания и распространения новых блоков, проверки их валидности и выбора одного из нескольких форков, если они появляются.
Двумя наиболее распространенными парадигмами являются Proof-of-Work (PoW) и
Proof-of-Stake (PoS). Подход Proof-of-Work обычно позволяет любому узлу создать
( добыть ) новый блок (и получить некоторое вознаграждение, связанное с добычей блока), если ему посчастливилось решить бесполезную вычислительную задачу (обычно включающую вычисление большого количества хэшей) до того, как это сделают другие конкурентыэто. В случае форков (например, если два узла публикуют два допустимых, но разных блока, следующих за предыдущим
) выигрывает самый длинный форк. Таким образом, гарантия неизменности блокчейна основана на количестве работы (вычислительных ресурсов), затраченных на генерацию блокчейна: любой, кто хотел бы создать форк этого

блокчейна, должен был бы повторно выполнить эту работу для создания альтернативных версий уже совершенных блоков. Для этого нужно было бы контролировать более
50% из общей вычислительной мощности, потраченной на создание новых блоков, в противном случае альтернативный форк будет иметь экспоненциально низкие шансы стать самым длинным.
Подход Proof-of-Stake основан на больших ставках (номинированных в криптовалюте), сделанных некоторыми специальными узлами (валидаторами), чтобы утверждать, что они проверили (валидировали) некоторые блоки и нашли их правильными. Валидаторы подписывают блоки и получают за это небольшие вознаграждения; однако, если валидатор когда-либо будет пойман на подписании неправильного блока и будет представлено доказательство этого, часть или вся его ставка будет аннулирована. Таким образом, гарантия валидности и неизменности блокчейна дается общим объемом ставок, сделанных валидаторами на валидность блокчейна.
Подход Proof-of-Stake более естественен в том отношении, что он стимулирует валидаторов (которые заменяют майнеров PoW) выполнять полезные вычисления (необходимые для проверки или создания новых блоков, в частности, путем выполнения всех транзакций, перечисленных в блоке) вместо вычисления бесполезных хэшей.
Таким образом, валидаторы будут приобретать оборудование, которое лучше приспособлено для обработки пользовательских транзакций, чтобы получать вознаграждения, связанные с этими транзакциями, что кажется довольно полезной инвестицией с точки зрения
63 2.8. Классификация блокчейн - проектов система в целом.
Однако системы Proof-of-Stake несколько сложнее реализовать, поскольку необходимо предусмотреть множество редких, но возможных условий.
Например, некоторые вредоносные валидаторы могут вступать в сговор с целью нарушения работы системы для извлечения некоторой прибыли (например, изменяя свои собственные балансы криптовалют).
Это приводит к некоторым нетривиальным теоретико-игровым проблемам.
Короче говоря, Proof-of-Stake более естественен и более перспективен, особенно для мультицепочечных проектов (потому что Proof-of-Work потребует непомерно больших вычислительных ресурсов при наличии большого количества блокчейнов), но должен быть более тщательно продуман и реализован. Большинство запущенных в настоящее время

блокчейн-проектов, особенно самые старые (такие как биткойн и, по крайней мере
, оригинальный Ethereum), используют Proof-of-Work.
2.8.4. Варианты Proof-of-Stake. DPOS против BFT. Хотя алгоритмы Proof-of-Work очень похожи друг на друга и отличаются в основном хэш
-функциями, которые должны быть вычислены для добычи новых блоков, существует больше возможностей для алгоритмов Proof-of-Stake. Они заслуживают собственной субклассификации
По существу, нужно ответить на следующие вопросы о доказательстве-
Алгоритм ставок:
ˆ
Кто может создать (добыть) новый блок любого полного узла или только члена (относительно) небольшого подмножества валидаторов? (Большинство PoS-систем требуют, чтобы новые блоки были сгенерированы и подписаны одним из нескольких назначенных валидаторов.)
ˆ
Гарантируют ли валидаторы действительность блоков своими подписями, или все полные узлы должны проверять все блоки самостоятельно?
(Масштабируемые PoS-системы должны полагаться на подписи валидаторов вместо того, чтобы требовать от всех узлов проверки всех блоков всех блокчейнов.)
ˆ
Есть ли назначенный производитель для следующего блока блокчейна, известный заранее, так что никто другой не может произвести этот блок вместо него?
ˆ
Является ли вновь созданный блок изначально подписанным только одним валидатором