Начнем с описания блокчейна The Open Network (TON), который является ключевым компонентом проекта. Будет использоваться подход «сверху вниз» — сначала мы дадим общее описание всей структуры, а затем предоставим более подробную информацию о каждом компоненте.
Для простоты мы будем использовать термин «блокчейн TON», хотя в принципе несколько экземпляров этого протокола блокчейна могут работать независимо друг от друга (например, в результате хард-форков). Мы будем рассматривать только один блокчейн TON.
Блокчейн TON на самом деле представляет собой несколько блокчейнов (в нем используются два блокчейна — этот момент будет прояснен позже), потому что ни один блокчейн не способен достичь нашей цели по обработке миллионов транзакций в секунду, в отличие от текущего стандарта в несколько десятков транзакций в секунду.
Типы блокчейнов. Концепция блокчейна TON состоит из четырёх уровней:
Практически все решения по шардингу блокчейнов являются «нисходящими»: сначала представляется единый блокчейн, а затем обсуждаются способы его разделения на несколько взаимодействующих шардчейнов для повышения производительности и достижения масштабируемости.
«Восходящий» подход к шардингу в платформе 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, θ). Позже при необходимости он может быть разделен на несколько шардов.
Несмотря на то, что в системе может быть создано до 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 поддерживает до 232 различных «криптовалют», «монет» или «токенов», которые различаются 32-битным идентификатором currency_id. Новые криптовалюты добавляются с помощью специальных транзакций в мастерчейне. Каждый воркчейн имеет базовую криптовалюту и может иметь несколько дополнительных криптовалют.
Существует одна специальная криптовалюта с идентификатором currency_id = 0, а именно монета TON (см. Приложение A). Это основная криптовалюта исходного блокчейна. Она также используется в качестве комиссии за транзакции и для определения стейков валидаторов.
В принципе, другие воркчейны могут собирать комиссию за транзакции в других токенах. Для этого необходимо предоставить смарт-контракт для автоматического преобразования этих комиссий за транзакции в монеты TON.
Шардчейны, принадлежащие к одному воркчейну или разным воркчейнам, могут отправлять сообщения друг другу. Несмотря на то, что точная форма разрешенных сообщений зависит от принимающего воркчейна и принимающей учетной записи (смарт-контракт), существуют некоторые общие поля, которые делают возможным обмен сообщениями между воркчейнами. В частности, к каждому сообщению может быть прикреплена некоторая стоимость в виде определенного количества монет TON и/или других зарегистрированных криптовалют, при условии, что они объявлены принимающим воркчейном как приемлемые криптовалюты.
Самая простая форма такого обмена сообщениями — это перенос стоимости из одной учетной записи (обычно не смарт-контракта) в другую учетную запись.
Виртуальная машина TON, также сокращенно TON VM или TVM, — это виртуальная машина, используемая для выполнения кода смарт-контракта в мастерчейне и в исходном воркчейне. В других воркчейнах могут использоваться другие виртуальные машины вместе с TVM или вместо TVM.
В дополнение к «сборке 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. Если он окажется слабее, чем ожидалось, в будущем его можно заменить другой хэш-функцией. Выбор хэш-функции — это настраиваемый параметр протокола, поэтому его можно изменить без необходимости создания хард-форков.
https://coq.inria.fr
https://core.telegram.org/mtproto/T