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

12 2.1. Блокчейн TON как структура, состоящая из 2D-блокчейнов должны быть собраны две трети голосов валидаторов и более половины голосов всех других участников, которые захотят принять участие в процессе голосования.
2.2. Общие сведения о блокчейнах
2.2.1. Общее определение блокчейна. В целом, любой (настоящий) блокчейн представляет собой последовательность блоков, причем каждый блок B содержит ссылку BLK-PREV(B) на предыдущий блок (обычно хэш предыдущего блока включается в заголовок текущего блока) и список транзакций. Каждая транзакция описывает некоторую трансформацию состояния глобального блокчейна.
Транзакции, перечисленные в блоке, применяются последовательно для вычисления нового состояния, начиная со старого состояния, которое является результирующим состоянием после оценки предыдущего блока.
2.2.2. Применимость к блокчейну TON. Напомним, что блокчейн TON - это не настоящий блокчейн, а система из 2 блокчейнов (т. е. это цепочка блокчейнов; см.
2.1.1), поэтому вышесказанное не применимо напрямую к блокчейну TON. Однако мы начнем с общего определения настоящего блокчейна, чтобы использовать его в качестве строительных блоков для наших более сложных конструкций.
2.2.3. Фактический блокчейн и тип блокчейна. Слово «блокчейн» часто используется для обозначения как общего типа блокчейна, так и конкретных экземпляров блокчейна, определяемых как последовательности блоков, удовлетворяющих определенным условиям. Например, в п. 2.2.1 приведено описание экземпляра блокчейна.
Таким образом, тип блокчейна обычно является «подтипом» типа Block* списков (т. е. конечных последовательностей) блоков, состоящих из тех последовательностей блоков, которые удовлетворяют определенным условиям совместимости и действительности:
Лучшим способом определения блокчейна было бы сказать, что блокчейн - это тип зависимой пары, состоящий из пар (B, v), где первый компонент B: Block* имеет тип
Block* (т. е. список блоков), а второй компонент v: isValidBc(B) является доказательством или свидетельством действительности B. Таким образом,
Здесь мы используем обозначения зависимых сумм типов, взятые из [16].
2.2.4. Теория зависимых типов, Coq и TL. Обратите внимание, что здесь мы используем теорию зависимых типов (теория Мартина-Лёфа), аналогичную теории, которая используется для автоматического доказательства Coq
3
. Упрощенная версия теории зависимых типов также используется в языке TL (Type Language)
4
, который будет использоваться в формальной спецификации блокчейна TON для описания сериализации всех структур данных и расположения блоков, транзакций и т.п.
Фактически, теория зависимых типов предоставляет необходимую формализацию того, что такое доказательство, а такие формальные доказательства (или их сериализации) могут оказаться полезными, когда, например, нужно предоставить доказательство невалидности для определенного блока.

13 2.2. Общие сведения о блокчейнах
TL - это язык, подходящий для описания зависимых алгебраических типов, которым разрешено иметь числовые (натуральные) и типовые параметры. Каждый тип описывается с помощью нескольких конструкторов. У каждого конструктора имеется
(человекочитаемый) идентификатор и имя, которое представляет собой битовую строку (по умолчанию 32-битное целое число). Кроме того, определение конструктора содержит список полей с их типами.
Набор определений конструкторов и типов называется TL-схемой. Обычно он хранится в одном или нескольких файлах с расширением .tl.
Важной особенностью TL-схем является то, что они определяют однозначный способ сериализации и десериализации значений (или объектов) определенных алгебраических типов. А именно, когда необходимо выполнить сериализацию значения в поток байтов, сначала выполняется сериализация имени конструктора, используемого для этого значения. Далее следуют рекурсивно вычисляемые сериализации каждого поля.
Описание предыдущей версии TL, подходящей для сериализации произвольных объектов в последовательности 32-битных целых чисел, доступно по адресу
https://core.telegram.org/mtproto/TL. Новая версия языка TL, названная TL-B, разрабатывается с целью описания сериализации объектов, используемых платформой TON. Эта новая версия может выполнять сериализацию объектов в потоки байтов и даже битов (а не только в 32-битные целые числа) и обеспечивает поддержку сериализации в дерево ячеек TVM (см. 2.3.14). Описание TL-B будет частью формальной спецификации блокчейна TON.
2.2.6. Блоки и транзакции как операторы преобразования состояний. Обычно в любом блокчейне с оператором (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, которое является истинным состоянием или специальным значением
, указывающим, что следующее состояние не может быть вычислено (т. е. что блок является невалидным при оценке из заданного начального состояния - например, блок включает транзакцию, которая свидетельствует о попытке списать средства с пустого счета).
2.2.7. Порядковые номера блоков. Ссылка на каждый блок B в блокчейне может осуществляться по его порядковому номеру BLK-SEQNO (B), начиная с нуля для

14 2.2. Общие сведения о блокчейнах самого первого блока и в порядке увеличения на единицу при переходе к следующему блоку. Более формально это выглядит следующим образом:
Обратите внимание, что порядковый номер не обеспечивает однозначную идентификацию блока при наличии форков.
2.2.8. Блокировка хэшей. Другой способ обращения к блоку B - это его хэш BLK-
HASH (B), который на самом деле является хэшем заголовка блока B (однако заголовок блока обычно содержит хэши, которые зависят от всего содержимого блока
B). Предполагая, что для используемой хэш-функции нет хэш-конфликтов (либо они как минимум очень маловероятны), блок однозначно идентифицируется по его хэш- функции.
2.2.9. Допущение хэша. Во время формального анализа алгоритмов блокчейна мы предполагаем отсутствие хэш-конфликтов для используемой k-битной хэш-функции
HASH: Bytes * → 2
k
:
Здесь Bytes = {0 ... 255} = 2 8
- это тип байтов или набор всех байтовых значений, а
Bytes * - тип или набор произвольных (конечных) списков байтов; в то время как 2 =
{0,1} - это битовый тип, а 2
k
- это набор (или фактически тип) всех k-битовых последовательностей (т. е. k-битных чисел).
Конечно, формула (7) невозможна с математической точки зрения, потому что отображение бесконечного множества в конечное множество не может быть инъективным. Более строгое предположение было бы следующим:
Однако для доказательств это не так удобно. Если (8) используется не более N раз в доказательстве с 2
-k
N <
∈ для некоторого малого ∈ (скажем, ∈ = 10
-18
), мы можем предположить, что (7) является истинным, при условии, что мы принимаем вероятность отказа ∈ (т. е. окончательные выводы будут верными с вероятностью не менее 1 - ∈).
Заключительное замечание: для того, чтобы утверждение о вероятности (8) было действительно строгим, необходимо ввести распределение вероятностей на множестве Bytes* всех последовательностей байтов. Один из способов сделать это - предположить, что все последовательности байтов одинаковой длины l равновероятны, и установить вероятность наблюдения за последовательностью длины l равной p l
– p l+1
для некоторого p → 1–. Тогда (8) следует понимать как
2.2. Общие сведения о блокчейнах предел условной вероятности P(HASH (S) = HASH(S') | s
≠
s'), когда p стремится к единице снизу.
2.2.10. Хэш, используемый для блокчейна TON. В настоящее время мы используем
256-битный хэш SHA256 для блокчейна TON. Если он окажется слабее, чем ожидалось, в будущем его можно заменить другой хэш-функцией. Выбор хэш- функции - это настраиваемый параметр протокола, поэтому его можно изменить без необходимости создания хард-форков, как описано в 2.1.21.
3
https://coq.inria.fr
4
https://core.telegram.org/mtproto/T

15 2.2. Общие сведения о блокчейнах
2.3. Состояние блокчейна, учетные записи и хэш-карты
Выше мы отметили, что любой блокчейн определяет заданное глобальное состояние, а каждый блок и каждая транзакция определяют преобразование этого глобального состояния. Ниже описывается глобальное состояние, используемое блокчейнами
TON.
2.3.1. Идентификаторы аккаунтов. Базовые идентификаторы учетных записей, используемые блокчейнами TON (или как минимум его мастерчейном и исходным воркчейном) представляют собой 256-битные целые числа, которые считаются открытыми ключами для 256-битного шифрования на основе эллиптических кривых
(ECC) для конкретной эллиптической кривой. Таким образом,
Где Account - это тип учетной записи, а account_id: Account - это конкретная переменная типа Account.
Другие воркчейны могут использовать другие форматы идентификаторов учетных записей (256-битные или другие). Например, можно использовать подобные биткоину идентификаторы учетной записи, равные SHA256 открытого ключа ECC.
Однако длина l в битах идентификатора учетной записи должна быть зафиксирована во время создания воркчейна (в мастерчейне), и она должна быть не менее 64, поскольку первые 64 бита идентификатора account_id используются для сегментирования и маршрутизации сообщений.
2.3.2. Основной компонент: хэш-карты. Главный компонент состояния блокчейна
TON - это хэш-карта. В некоторых случаях мы рассматриваем (частично определенные) «карты» h: 2
n
-→ + 2
m
. В более общем плане нас могут заинтересовать хэш-карты h: 2
n
-→ X для составного типа X. Однако тип источника (или индекса) почти всегда 2
n
. Иногда «значение по умолчанию» является пустым: X, а хэш-карта h:
2
n
→ X «инициализируется» своим пустым «значением по умолчанию» i →.
2.3.3. Пример: остатки на счетах TON. Важный пример - остатки на счетах TON.
Это хэш-карта, которая сопоставляет Account = 2 256
с балансом монет TON типа uint
128
= 2 128
. Эта хэш- карта имеет значение по умолчанию, равное нулю, то есть изначально (до обработки первого блока) баланс всех учетных записей равен нулю.
2.3.4. Пример: постоянное хранилище смарт-контракта. Другой пример - постоянное хранилище смарт-контрактов, которое можно (очень приблизительно) представить в виде хэш-карты.
Эта хэш-карта также имеет значение по умолчанию, равное нулю, то есть неинициализированные ячейки постоянного хранилища считаются равными нулю.
2.3.5. Пример: постоянное хранилище всех смарт-контрактов. Поскольку у нас есть несколько смарт-контрактов, различающихся идентификатором account_ id, каждый из которых имеет отдельное постоянное хранилище, у нас должна быть фактическая хэш-карта,

16 2.3. Состояние блокчейна, учетные записи и хэш-карты которая соотносит идентификатор account_id смарт-контракта с его постоянным хранилищем.
2.3.6. Тип хэш-карты. Хэш-карта - это не просто абстрактная (частично определенная) функция 2
n
--→ X; у нее есть конкретное представление. Поэтому мы предполагаем, что у нас есть специальный тип хэш-карты, соответствующий структуре данных, кодирующей (частичное) отображение 2
n
-→ X.
Мы также можем записать или
Мы всегда можем преобразовать h: Hashmap (n, X) в карту hget (h): 2
n
→X
?
, С этого момента мы обычно пишем h[i] вместо hget(h)(i):
2.3.7. Определение типа хэш-карты как дерева Patricia. Логически можно определить Hashmap(n, X) как (неполное) двоичное дерево глубины n с метками ребер
0 и 1 и со значениями типа X в листьях. Другим способом описания той же структуры было бы (побитовое) префиксное дерево для двоичных строк длиной, равной n.
На практике мы предпочитаем использовать компактное представление этого дерева, сжимая каждую вершину, имеющую только один дочерний элемент со своим родителем. Результирующее представление известно как дерево Patricia или двоичное основание системы счисления. Каждая промежуточная вершина теперь имеет ровно два дочерних элемента, помеченных двумя непустыми двоичными строками, начиная с нуля для левого дочернего элемента и с одного для правого дочернего элемента.
Другими словами, в дереве Patricia имеется два типа (некорневых) узлов:
• LEAF(x), содержащий значение x типа X.
• NODE (д, s l
, r, s r
), где l - (ссылка на) левый дочерний элемент или поддерево, s l
- это цепочка битов, обозначающая ребро, соединяющее эту вершину с ее левым дочерним элементом (всегда начинается с 0), r - правое поддерево, а sr - это цепочка битов, обозначающая край правого дочернего элемента (всегда начинается с 1).
Также необходим третий тип узла, который будет использоваться только один раз в корне дерева Patricia:
• ROOT (n, s
0
, t), где n - общая длина индексных битовых строк Hashmap (n, X), s
0
- общий префикс всех индексных битовых строк, а t - ссылка на LEAF или NODE .
Если мы хотим, чтобы дерево Patricia было пустым, необходимо использовать четвертый тип (корневого) узла:
• EMPTYROOT (n), где n - общая длина всех битовых строк индекса.
Мы определяем высоту дерева Patricia следующим образом:
Последние два выражения в каждой из двух последних формул должны быть равны.
Мы используем деревья Patricia высоты n для представления значений типа
Hashmap(n, X),