Начнем с описания блокчейна The Open Network (TON), который является ключевым компонентом проекта. Будет использоваться подход «сверху вниз» — сначала мы дадим общее описание всей структуры, а затем предоставим более подробную информацию о каждом компоненте.
Для простоты мы будем использовать термин «блокчейн TON», хотя в принципе несколько экземпляров этого протокола блокчейна могут работать независимо друг от друга (например, в результате хард-форков). Мы будем рассматривать только один блокчейн TON.
Блокчейн TON на самом деле представляет собой несколько блокчейнов (в нем используются два блокчейна — этот момент будет прояснен позже), потому что ни один блокчейн не способен достичь нашей цели по обработке миллионов транзакций в секунду, в отличие от текущего стандарта в несколько десятков транзакций в секунду.
Типы блокчейнов. Концепция блокчейна TON состоит из четырёх уровней:
- Уникальная единая корневая цепь (или сокращенно мастерчейн), содержащая общую информацию о протоколе и текущих значениях его параметров, наборе валидаторов и их стейках, наборе текущих активных воркчейнов • (воркчейнов) и соответствующих «шардов», и, что наиболее важно, набор хэшей самых последних блоков всех воркчейнов и шардчейнов.
- Несколько (до 232) воркчейнов (или сокращенно воркчейнов), которые на самом деле являются «рабочими лошадками», содержащими транзакции стоимости и транзакции смарт-контрактов. Разные воркчейны могут иметь разные «правила», то есть разный формат адресов учетной записи, разный формат транзакций, разные криптовалюты, разные виртуальные машины для обработки кода смарт-контрактов и т.д. Однако все они должны удовлетворять определенным основным критериям совместимости, чтобы обеспечить взаимодействие между различными воркчейнами и сделать его относительно простым. В этом отношении воркчейны в TON аналогичны EOS и PolkaDot, где блокчейн также является гетерогенным.
- В свою очередь, каждый воркчейн подразделяется на шардчейны (которых максимум 2 в 60 степени), имеющие те же правила и формат блока, что и сам воркчейн, но отвечающие только за подмножество учетных записей, в зависимости от нескольких первых (наиболее значимых) битов адреса аккаунта. Другими словами, в систему встроена форма сегментирования. Поскольку во всех этих шардчейнах используется общий формат блоков и правила, блокчейн TON в этом отношении является гомогенным, аналогично к тому, что обсуждалось в одном из предложений по запечатыванию сети Ethereum1
- Каждый блок в шардчейне (и в мастерчейне) на самом деле является не просто блоком, а небольшим блокчейном. Обычно этот «блокчейн» или «вертикальный блокчейн» состоит ровно из одного блока, и тогда можно подумать, что это всего лишь соответствующий блок шардчейна (в этой ситуации также называемого «горизонтальной цепью»). Однако, если возникает необходимость исправить некорректные блоки шардчейна, новый блок фиксируется в «вертикальном блокчейне», содержащем либо замену недопустимого блока «горизонтального блокчейна», либо «характеристики различия блоков», содержащие только описание тех частей предыдущей версии этого блока, которые необходимо изменить. Это специфичный для TON механизм замены обнаруженных недопустимых блоков без создания истинного форка всех задействованных шардчейнов. На данный момент следует просто отметить, что каждый шардчейн (и мастерчейн) — это не обычный блокчейн, а цепь блокчейнов (2D-блокчейн или просто 2-блокчейн).
Парадигма бесконечного шардинга
Практически все решения по шардингу блокчейнов являются «нисходящими»: сначала представляется единый блокчейн, а затем обсуждаются способы его разделения на несколько взаимодействующих шардчейнов для повышения производительности и достижения масштабируемости.
«Восходящий» подход к шардингу в платформе TON объясняется следующим образом.
Представьте, что шардинг доведено до крайности, так что в каждом шардчейне остается ровно одна учетная запись или смарт-контракт. При этом имеется огромное количество «цепочек учетных записей», каждая из которых описывает состояние и переходы между состояниями только одной учетной записи и отправляет на другие цепи сообщения о переносе стоимости и информации.
Конечно, использовать сотни миллионов блокчейнов – это непрактично, причем обновления (т. е. новые блоки) в каждом блокчейне обычно довольно редко появляются. Чтобы обеспечить более высокую эффективность системы, мы группируем эти «цепочки учетных записей» в «шардчейны», так что каждый блок шардчейна по существу представляет собой набор блоков цепочек учетных записей, которые были назначены этому шарду. Таким образом, «цепочки учетных записей» существуют только исключительно виртуально или логически внутри «шардчейнов». Мы называем эту перспективу парадигмой бесконечного шардинга, которая объясняет многие проектные решения для блокчейна TON.
Сообщения
Мгновенная маршрутизация в гиперкубе (Instant Hypercube Routing). В парадигме бесконечного шардинга каждая учетная запись (или смарт-контракт) рассматривается так, как если бы она сама находилась в отдельном шардчейне. Тогда единственный способ, при помощи которого одна учетная запись может повлиять на состояние другой учетной записи, — это отправить ей сообщение (это особый случай так называемой модели акторов, причем в роли акторов выступают учетные записи). Следовательно, система передачи сообщений между учетными записями (и шардчейнами, поскольку исходная и конечная учетные записи, как правило, расположены в разных шардчейнах) имеет первостепенное значение для запечатываемой системы, такой как блокчейн TON. Фактически, новая функция блокчейна TON, называемая Instant Hypercube Routing, обеспечивает доставку и обработку сообщений, созданных в блоке одного шардчейна, в следующий блок целевого шардчейна, независимо от общего количества шардчейнов в системе.
Количество мастерчейнов, воркчейнов и шардчейнов. Блокчейн TON содержит ровно один мастерчейн. Однако система потенциально может вместить до 2 32 воркчейнов, каждый из которых будет разделен на 2 60 сегментов.
Воркчейны могут быть виртуальными, а не настоящими блокчейнами
Поскольку воркчейн обычно подразделяется на шардчейны, существование воркчейна является «виртуальным» — это не настоящий блокчейн в смысле общего определения, а просто набор шардчейнов. Если воркчейну соответствует только один шардчейн, этот уникальный шардчейн может быть идентифицирован с воркчейном, который в этом случае становится «настоящим» блокчейном (как минимум на некоторое время), таким образом, приобретая внешнее сходство с обычной структурой, в которой используется один блокчейн. Однако парадигма бесконечного шардинга говорит нам, что такое сходство является только внешним: это просто совпадение, что потенциально огромное количество «цепочек учетных записей» может быть временно сгруппировано в один блокчейн.
Идентификация воркчейнов
Каждый воркчейн идентифицируется на основании своего номера или идентификатора воркчейна (workchain_id : uint32), который представляет собой 32-битное целое число без знака. Воркчейны создаются специальными транзакциями в мастерчейне, определяющими ранее неиспользованный идентификатор воркчейна и формальное описание воркчейна, которое является достаточным для взаимодействия этой воркчейна с другими воркчейнами, а также для поверхностной проверки блоков этого воркчейна.
Создание и активация новых воркчейнов
Создание нового воркчейна может быть инициировано практически любым членом сообщества, готовым заплатить (высокие) комиссии за транзакции в мастерчейне, необходимые для публикации формальной спецификации нового воркчейна. Однако для того, чтобы новый воркчейн стал активным, требуется консенсус в две трети валидаторов, поскольку им необходимо будет обновить свое программное обеспечение для обработки блоков нового воркчейна и сигнализировать о своей готовности работать с новым воркчейном при помощи специальных транзакций в мастерчейне. Сторона, заинтересованная в активации нового воркчейна, может предоставить валидаторам некоторый стимул для поддержки нового воркчейна посредством вознаграждений, распределяемых при помощи смарт-контракта.
Идентификация шардчейнов
Каждый шардчейн идентифицируется парой (w, s) = (workchain_id, shard_prefix), где workchain_id: uint32 идентифицирует соответствующий воркчейн, а shard_prefix: 20…60 — это строка битов длиной не более 60, определяющая подмножество учетных записей, за которые отвечает этот шардчейн. А именно, все учетные записи с идентификатором account_id, начинающимся с префикса shard_prefix (т. е. имеющие префикс shard_prefix в качестве наиболее значимых битов), будут назначены этому шардчейну.
Идентификация цепочек учетных записей
Напомним, что цепочки учетных записей существуют только виртуально. Однако у них есть естественный идентификатор, а именно (workchain_id, account_id), поскольку любая цепочка учетных записей содержит информацию о состоянии и обновлениях ровно одной учетной записи (различие между обычной учетной записью или смарт-контрактом здесь не имеет значения).
Динамическое разделение и объединение шардчейнов
В менее сложной системе может использоваться статический шардинг — например, с использованием первых восьми битов идентификатора account_id для выбора одного из 256 предопределенных шардов.
Важной особенностью блокчейна TON является то, что в нем реализуется динамический шардинг – это означает, что количество шардов не является фиксированным. Вместо этого шард (w, s) можно автоматически разделить на несколько новых шардов (w,s.0) и (w, s.1), если выполняются некоторые формальные условия (по сути, если транзакционная нагрузка на исходный шард достаточно высока в течение продолжительного периода времени). И наоборот, если нагрузка остается слишком низкой в течение некоторого периода времени, шарды (w, s.0) и (w, s.1) могут быть автоматически объединены в исходный шард (w, s).
Изначально для воркчейна w создается только один шард (w, θ). Позже при необходимости он может быть разделен на несколько шардов.
Исходный воркчейн или Workchain Zero
Несмотря на то, что в системе может быть создано до 232 воркчейнов с соответствующими конкретными правилами и транзакциями, изначально задается только один воркчейн (workchain_ id = 0). Этот воркчейн, называемый Workchain Zero или исходный воркчейн, используется для работы со смарт-контрактами TON и перевода монет TON. Скорее всего, для большинства приложений потребуется только Workchain Zero. Шардчейны базового воркчейна будут называться исходными шардчейнами.
Интервалы генерации блоков
Ожидается, что новый блок будет генерироваться в каждом шардчейне и мастерчейне примерно раз в пять секунд. Это приведет к разумно малому времени подтверждения транзакции. Новые блоки всех шардчейнов будут генерироваться примерно одновременно; новый блок мастерчейна создается примерно на одну секунду позже, поскольку он должен содержать хэши последних блоков всех шардчейнов.
Использование мастерчейна для создания тесной взаимосвязи между воркчейнами и шардчейнами
После включения хэша блока шардчейна в блок мастерчейна этот блок шардчейна и все предшествующие ему блоки считаются «эталонными». Это означает, что все последующие блоки всех шардчейнов могут на них ссылаться как на нечто фиксированное и неизменяемое. Фактически, каждый новый блок шардчейна содержит хэш самого последнего блока мастерчейна, поэтому новый блок считает все блоки шардчейна, на которые ссылается этот блок мастерчейна, неизменяемыми.
По сути, это означает, что транзакция или сообщение, зафиксированное в блоке шардчейна, можно безопасно использовать в следующих блоках других шардчейнов без необходимости ожидания, к примеру, двадцати подтверждений (т. е. двадцать блоков, сгенерированных после исходного блока в том же блокчейне) передпересылкой сообщения или выполнением других действий на основе предыдущей транзакции, как это часто бывает в большинстве предлагаемых системах «со слабой связью», таких как EOS.
Эта способность использовать транзакции и сообщения в других сегментах сети всего через пять секунд после их фиксации является одной из причин, по которой мы считаем, что наша система «с сильной связью» первой в своем роде сможет обеспечить беспрецедентную производительность.
Хэш блока мастерчейна как глобальное состояние. Хэш последнего блока мастерчейна полностью определяет общее состояние системы с точки зрения внешнего наблюдателя. Поэтому нет необходимости следить за состоянием всех шардчейнов по отдельности.
Генерация новых блоков валидаторами
В блокчейне TON используется метод защиты Proof-of-Stake (подтверждение доли, PoS) для создания новых блоков в шардчейнах и мастерчейнах. Это означает, что существует, скажем, до нескольких сотен валидаторов — специальных узлов, которые внесли стейки (большие количества монет TON) с помощью специальной транзакции мастерчейна, чтобы иметь право на создание и проверку новых блоков.
Затем детерминированным псевдослучайным образом каждому сегменту (w, s) назначается меньшее подмножество валидаторов, которое изменяется примерно каждые 1024 блока. Это подмножество валидаторов предлагает и достигает консенсуса в отношении того, каким будет следующий блок шардчейна, путем сбора подходящих предлагаемых транзакций от клиентов в новые допустимые блоки-кандидаты. Для каждого блока существует псевдослучайно выбранный порядок валидаторов, который позволяет определить, чей блок-кандидат имеет наивысший приоритет для фиксации в каждой очереди.
Валидаторы и другие узлы проверяют действительность предложенных блоков-кандидатов; если валидатор подписывает недопустимый блок-кандидата, он может быть автоматически наказан потерей части своей стейка или всего стейка, либо лишением функций валидатора на некоторое время. После этого валидаторы должны прийти к консенсусу по выбору следующего блока. По сути, это достигается с помощью эффективного протокола консенсуса BFT (задача византийских генералов), подобного PBFT [4] или Honey Badger BFT [11]. При достижении консенсуса создается новый блок, после чего валидаторы делят между собой комиссию за транзакции, включенные в транзакцию, плюс некоторые вновь созданные («отчеканенные») монеты.
Каждый валидатор может быть избран для участия в нескольких подмножествах валидаторов; в этом случае предполагается, что все алгоритмы проверки и согласования будут выполняться параллельно.
После того, как все новые блоки гардчейна были сгенерированы, либо истекло время ожидания, создается новый блок мастерчейна, включая хэши последних блоков всех сегментов шардчейнов. Эта задача реализуется на основе консенсуса BFT всех валидаторов 2.
Форки мастерчейна
Сложность нашей предлагаемой системы «с сильной связью» заключается в том, что переключение на другой форк в мастерчейне почти обязательно потребует переключения на другой форк как минимум в некоторых из шардчейнов.
С другой стороны, до тех пор, пока в мастерчейне нет форков, форки в шардчейне невозможны, поскольку никакие блоки в альтернативных форках шардчейнов не могут стать «эталонными», если их хэши включены в блок мастерчейна.
Общее правило состоит в том, что если блок B’ мастерчейна является предшественником B, то B’ включает хэш HASH(B’w,s) из B’w,s блока шардчейна (w,s), а B включает хэш HASH(Bw,s), тогда B’w,s должен быть предшественником Bw,s. В противном случае блок B мастерчейна является невалидным.
Ожидается, что форки мастерчейна будут редким, практически невозможным явлением, поскольку в парадигме ВFT, принятой в блокчейне TON, они могут возникать только в случае некорректного поведения большинства валидаторов, что повлечет за собой значительную потерю нарушителями их стейков. Следовательно, не следует ожидать настоящих форков в шардчейнах. Вместо этого, в случае обнаружения недопустимого блока шардчейна, он будет исправлен с помощью механизма «вертикального блокчейна» (2-блокчейна), который может достичь этой цели без создания форков «горизонтального блокчейна» (т. е., шардчейна). Тот же механизм можно использовать и для исправления некритических ошибок в блоках мастерчейна.
Исправление неверных блоков шардчейна
Обычно фиксируются только действительные блоки шардчейна, потому что валидаторы, назначенные для шардчейна, должны достичь консенсуса в две трети при решении задачи византийских генералов, прежде чем может быть зафиксирован новый блок. Однако система должна обеспечивать обнаружение ранее зафиксированных недопустимых блоков и их исправление.
Конечно, при обнаружении невалидного блока шардчейна — либо валидатором (не обязательно назначенным для этого шардчейна), либо «фишерменом» (любым узлом системы, сделавшим определенный депозит, чтобы иметь возможность поднимать вопросы о валидности блока) -заявление о невалидности и соответствующие доказательства передаются в мастерчейн, а валидаторы, подписавшие невалидный блок, наказываются потерей части своего стейка и/или временно лишаются права выполнять функции валидатора (последняя мера важна в том случае, если злоумышленник украл закрытые ключи подписи надежного валидатора).
Однако этого недостаточно, потому что общее состояние системы (блокчейна TON) оказывается недопустимым из-за ранее зафиксированного недопустимого блока в шардчейне. Этот недопустимый блок необходимо заменить более новой действующей версией.
В большинстве систем эта задача достигается путем «отката» к последнему блоку перед недопустимым блоком в данном шардчейне и последним блокам, не затронутым сообщениями, передаваемыми из недопустимого блока в каждый из других блокчейнов, а также созданием нового форка из этих блоков. Недостатком этого подхода является то, что внезапно откатывается большое количество корректных и подтвержденных транзакций, и неясно, будут ли они вообще включены в систему позже.
Блокчейн TON решает эту проблему, превращая каждый «блок» каждого шардчейна и мастерчейна («горизонтальные блокчейны») в небольшой блокчейн («вертикальный блокчейн»), содержащий разные версии этого «блока» или их «различия». Обычно вертикальный блокчейн состоит ровно из одного блока, а шардчейн имеет вид классического блокчейна. Однако, как только невалидность блока будет подтверждена и зафиксирована в блоке мастерчейна, к «вертикальному блокчейну» недопустимого блока разрешается добавить новый блок в вертикальном направлении, после чего будет выполнена замена или изменение недопустимого блока. Новый блок генерируется текущим подмножеством валидаторов для рассматриваемого шардчейна.
Для нового «вертикального» блока действуют довольно строгие правила. В частности, если виртуальный «блок цепочки учетных записей», содержащийся в недопустимом блоке, действителен сам по себе, он должен быть оставлен без изменений со стороны нового вертикального блока.
Как только новый «вертикальный» блок фиксируется поверх недопустимого блока, его хэш публикуется в новом блоке мастерчейна (или, скорее, в новом «вертикальном» блоке, находящемся над исходным блоком мастерчейна, где был первоначально опубликован хэш недопустимого блока шардчейна), 2 На самом деле, двух третей голосов достаточно для достижения консенсуса, однако система старается собрать как можно больше подписей, а изменения распространяются дальше на любые блоки шардчейна, относящиеся к предыдущей версии этого блока (например, блоки, которые получили сообщения от некорректного блока).
Исправление этой проблемы достигается путем фиксации новых «вертикальных» блоков в вертикальных блокчейнах для всех блоков, ранее ссылающихся на «некорректный» блок. Новые вертикальные блоки будут ссылаться на самые последние (исправленные) версии. Опять же, строгие правила запрещают изменять цепочки учетных записей, которые не были фактически затронуты (т. е. получают те же сообщения, что и в предыдущей версии). Таким образом, исправление некорректного блока создаёт «волны», которые в конечном итоге распространяются к самым недавним блокам всех затронутых шардчейнов; эти изменения также отражены в новых «вертикальных» блока мастерчейна.
Когда «рябь перезаписи истории» достигает самых последних блоков, новые блоки шардчейна генерируются только в одной версии и становятся преемниками только новейших версий блоков. Это означает, что они с самого начала будут содержать ссылки на правильные (самые последние) вертикальные блоки.
Состояние мастерчейна неявно определяет карту, преобразующую хэш первого блока каждого «вертикального» блокчейна в хэш последней версии. Это позволяет клиенту идентифицировать и определять местонахождение любого вертикального блокчейна по хэшу самого первого (и обычно единственного) блока.
Монеты TON и мультивалютные воркчейны
Блокчейн TON поддерживает до 232 различных «криптовалют», «монет» или «токенов», которые различаются 32-битным идентификатором currency_id. Новые криптовалюты добавляются с помощью специальных транзакций в мастерчейне. Каждый воркчейн имеет базовую криптовалюту и может иметь несколько дополнительных криптовалют.
Существует одна специальная криптовалюта с идентификатором currency_id = 0, а именно монета TON (см. Приложение A). Это основная криптовалюта исходного блокчейна. Она также используется в качестве комиссии за транзакции и для определения стейков валидаторов.
В принципе, другие воркчейны могут собирать комиссию за транзакции в других токенах. Для этого необходимо предоставить смарт-контракт для автоматического преобразования этих комиссий за транзакции в монеты TON.
Обмен сообщениями и транзакции стоимости
Шардчейны, принадлежащие к одному воркчейну или разным воркчейнам, могут отправлять сообщения друг другу. Несмотря на то, что точная форма разрешенных сообщений зависит от принимающего воркчейна и принимающей учетной записи (смарт-контракт), существуют некоторые общие поля, которые делают возможным обмен сообщениями между воркчейнами. В частности, к каждому сообщению может быть прикреплена некоторая стоимость в виде определенного количества монет TON и/или других зарегистрированных криптовалют, при условии, что они объявлены принимающим воркчейном как приемлемые криптовалюты.
Самая простая форма такого обмена сообщениями — это перенос стоимости из одной учетной записи (обычно не смарт-контракта) в другую учетную запись.
Виртуальная машина TON
Виртуальная машина TON, также сокращенно TON VM или TVM, — это виртуальная машина, используемая для выполнения кода смарт-контракта в мастерчейне и в исходном воркчейне. В других воркчейнах могут использоваться другие виртуальные машины вместе с TVM или вместо TVM.
- TVM представляет все данные как набор ячеек (TVM). Каждая ячейка содержит до 128 байтов данных и до 4 ссылок на другие ячейки. Применение концепции «все есть мешок ячеек» позволяет TVM работать со всеми данными, относящимися к блокчейну TON, включая блоки и глобальное состояние блокчейна, если это необходимо. • TVM может работать со значениями произвольных алгебраических типов данных, представленными в виде деревьев или ориентированных ациклических графов из ячеек TVM. Однако виртуальная машина TON не зависит от существования алгебраических типов данных, она просто работает с ячейками.
- TVM имеет встроенную поддержку хэш-карт.
- TVM является стековой вычислительной машиной. В стеке TVM хранятся либо 64-битные целые числа, либо ссылки на ячейки.
- Поддерживаются 64-битные, 128-битные и 256-битные арифметические операции. Все n-битные арифметические операции бывают трех видов: для целых чисел без знака, для целых чисел со знаком и для целых чисел по модулю 2n (в последнем случае автоматический контроль переполнения отсутствует).
- TVM обеспечивает преобразование целых чисел без знака и со знаком из n-битн в m-бит для всех 0 ≤ m, n ≤ 256 с контролем переполнения.
- По умолчанию для всех арифметических операций выполняется контроль переполнения, что значительно упрощает разработку смарт-контрактов.
- TVM выполняет арифметические операции «умножить, затем сдвинуть» и «сдвинуть и разделить» с промежуточными значениями, вычисленными в большем целочисленном типе данных; это упрощает выполнение арифметических операций с фиксированной точкой.
- TVM предлагает поддержку строк битов и строк байтов.
- Присутствует поддержка 256-битное шифрование на основе эллиптических кривых (ECC) для некоторых предопределенных кривых, включая Curve25519.
- Также присутствует поддержка пар Вейля для некоторых эллиптических кривых, необходимая для быстрой реализации zk-SNARK.
- Присутствует поддержка популярных хэш-функций, в том числе SHA256.
- TVM может работать с доказательствами Меркла,
- TVM предлагает поддержку «больших» или «глобальных» смарт-контрактов. В таких смарт-контрактах должна быть информация о шардинге. В обычных (локальных) смарт-контрактах может отсутствовать информация о шардинге.
- TVM поддерживает замыкания.
- На TVM может быть легко реализована машина сокращения графов (spineless tagless G-machine).
В дополнение к «сборке TVM» могут быть разработаны несколько высокоуровневых языков программирования. Все эти языки будут статического типа и будут поддерживать алгебраические типы данных. Мы предполагаем следующие возможности:
• Императивный язык, подобный Java, в котором каждый смарт-контракт похож на отдельный класс.
• Функциональный язык для ленивых вычислений (Haskell).
• Функциональный язык для немедленных вычислений (ML).
Настраиваемые параметры
Важной особенностью блокчейна TON является то, что многие его параметры являются конфигурируемыми. Это означает, что они являются частью состояния мастерчейна и могут быть изменены с помощью определенных транзакций предложения/голосования/результатов в мастерчейне без необходимости форков. Для изменения таких параметров в пользу предложения должны быть собраны две трети голосов валидаторов и более половины голосов всех других участников, которые захотят принять участие в процессе голосования.
Общие сведения о блокчейнах
Общее определение блокчейна. В целом, любой (настоящий) блокчейн представляет собой последовательность блоков, причем каждый блок B содержит ссылку BLK-PREV(B) на предыдущий блок (обычно хэш предыдущего блока включается в заголовок текущего блока) и список транзакций. Каждая транзакция описывает некоторую трансформацию состояния глобального блокчейна. Транзакции, перечисленные в блоке, применяются последовательно для вычисления нового состояния, начиная со старого состояния, которое является результирующим состоянием после оценки предыдущего блока.
Применимость к блокчейну TON
Напомним, что блокчейн TON — это не настоящий блокчейн, а система из 2 блокчейнов (т. е. это цепочка блокчейнов), поэтому вышесказанное не применимо напрямую к блокчейну TON. Однако мы начнем с общего определения настоящего блокчейна, чтобы использовать его в качестве строительных блоков для наших более сложных конструкций.
Фактический блокчейн и тип блокчейна
Слово «блокчейн» часто используется для обозначения как общего типа блокчейна, так и конкретных экземпляров блокчейна, определяемых как последовательности блоков, удовлетворяющих определенным условиям.
Таким образом, тип блокчейна обычно является «подтипом» типа Block* списков (т. е. конечных последовательностей) блоков, состоящих из тех последовательностей блоков, которые удовлетворяют определенным условиям совместимости и действительности:
Лучшим способом определения блокчейна было бы сказать, что блокчейн — это тип зависимой пары, состоящий из пар (B, v), где первый компонент B: Block* имеет тип Block* (т. е. список блоков), а второй компонент v: isValidBc(B) является доказательством или свидетельством действительности B.
Теория зависимых типов, Coq и TL
Обратите внимание, что здесь мы используем теорию зависимых типов (теория Мартина-Лёфа), аналогичную теории, которая используется для автоматического доказательства Coq3. Упрощенная версия теории зависимых типов также используется в языке TL (Type Language)4, который будет использоваться в формальной спецификации блокчейна TON для описания сериализации всех структур данных и расположения блоков, транзакций и т.п. Фактически, теория зависимых типов предоставляет необходимую формализацию того, что такое доказательство, а такие формальные доказательства (или их сериализации) могут оказаться полезными, когда, например, нужно предоставить доказательство невалидности для определенного блока.
Язык TL (Type Language)
Поскольку язык TL (Type Language) будет использоваться в формальных спецификациях блоков TON, транзакций и сетевых датаграмм, необходимо краткое обсуждение особенностей этого языка.
TL — это язык, подходящий для описания зависимых алгебраических типов, которым разрешено иметь числовые (натуральные) и типовые параметры. Каждый тип описывается с помощью нескольких конструкторов. У каждого конструктора имеется (человекочитаемый) идентификатор и имя, которое представляет собой битовую строку (по умолчанию 32-битное целое число). Кроме того, определение конструктора содержит список полей с их типами.
Набор определений конструкторов и типов называется TL-схемой. Обычно он хранится в одном или нескольких файлах с расширением .tl. Важной особенностью TL-схем является то, что они определяют однозначный способ сериализации и десериализации значений (или объектов) определенных алгебраических типов. А именно, когда необходимо выполнить сериализацию значения в поток байтов, сначала выполняется сериализация имени конструктора, используемого для этого значения. Далее следуют рекурсивно вычисляемые сериализации каждого поля.
Описание предыдущей версии TL, подходящей для сериализации произвольных объектов в последовательности 32-битных целых чисел, доступно по адресу https://core.telegram.org/mtproto/TL. Новая версия языка TL, названная TL-B, разрабатывается с целью описания сериализации объектов, используемых платформой TON. Эта новая версия может выполнять сериализацию объектов в потоки байтов и даже битов (а не только в 32-битные целые числа) и обеспечивает поддержку сериализации в дерево ячеек TVM. Описание TL-B будет частью формальной спецификации блокчейна TON.
Блоки и транзакции как операторы преобразования состояний
Обычно в любом блокчейне с оператором (type) Blockchain связан оператор глобального состояния (type) State и транзакция (type) Transaction. Семантика блокчейна в значительной степени определяется функцией приложения транзакции:
Здесь Х? обозначает MAYBE X, результат применения монады MAYBE к типу X. Это похоже на использование X * для LiSTX. По существу, значение типа X? является либо значением типа X, либо специальным значением , указывающим на отсутствие фактического значения (вспомните о нулевом указателе). В нашем случае мы используем State? вместо State в качестве типа результата, потому что транзакция может быть недействительной, если вызывается из определенных исходных состояний (вспомните о попытке снять со счета больше денег, чем есть на самом деле).
Мы могли бы предпочесть чистую версию ev_trans’:
Поскольку блок — это, по сути, список транзакций, функция оценки блока может быть получена из ev_trans. Она принимает блок B: Block и предыдущее состояние блокчейна s: State (которое может включать хэш предыдущего блока) и вычисляет следующее состояние блокчейна s’ = ev_block(B)(s): State, которое является истинным состоянием или специальным значением , указывающим, что следующее состояние не может быть вычислено (т. е. что блок является невалидным при оценке из заданного начального состояния — например, блок включает транзакцию, которая свидетельствует о попытке списать средства с пустого счета).
Порядковые номера блоков
Ссылка на каждый блок B в блокчейне может осуществляться по его порядковому номеру BLK-SEQNO (B), начиная с нуля для самого первого блока и в порядке увеличения на единицу при переходе к следующему блоку. Более формально это выглядит следующим образом:
Обратите внимание, что порядковый номер не обеспечивает однозначную идентификацию блока при наличии форков.
Блокировка хэшей
Другой способ обращения к блоку B — это его хэш BLK-HASH (B), который на самом деле является хэшем заголовка блока B (однако заголовок блока обычно содержит хэши, которые зависят от всего содержимого блока B). Предполагая, что для используемой хэш-функции нет хэш-конфликтов (либо они как минимум очень маловероятны), блок однозначно идентифицируется по его хэш-функции.
Допущение хэша
Во время формального анализа алгоритмов блокчейна мы предполагаем отсутствие хэш-конфликтов для используемой k-битной хэш-функции HASH: Bytes * → 2 k :
Здесь Bytes = {0 … 255} = 28 — это тип байтов или набор всех байтовых значений, а Bytes * — тип или набор произвольных (конечных) списков байтов; в то время как 2 = {0,1} — это битовый тип, а 2k — это набор (или фактически тип) всех k-битовых последовательностей (т. е. k-битных чисел).
Конечно, формула (7) невозможна с математической точки зрения, потому что отображение бесконечного множества в конечное множество не может быть инъективным. Более строгое предположение было бы следующим:
Однако для доказательств это не так удобно. Если (8) используется не более N раз в доказательстве с 2-kN <∈ для некоторого малого ∈ (скажем, ∈ = 10-18), мы можем предположить, что (7) является истинным, при условии, что мы принимаем вероятность отказа ∈ (т. е. окончательные выводы будут верными с вероятностью не менее 1 — ∈).
Заключительное замечание: для того, чтобы утверждение о вероятности (8) было действительно строгим, необходимо ввести распределение вероятностей на множестве Bytes* всех последовательностей байтов. Один из способов сделать это —
предположить, что все последовательности байтов одинаковой длины l равновероятны, и установить вероятность наблюдения за последовательностью длины l равной pl – p
l+1 для некоторого p → 1–.
Общие сведения о блокчейнах предел условной вероятности P(HASH (S) = HASH(S’) | s ≠ s’), когда p стремится к единице снизу.
2.2.10. Хэш, используемый для блокчейна TON. В настоящее время мы используем 256-битный хэш SHA256 для блокчейна TON. Если он окажется слабее, чем ожидалось, в будущем его можно заменить другой хэш-функцией. Выбор хэш-функции — это настраиваемый параметр протокола, поэтому его можно изменить без необходимости создания хард-форков.
