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

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

2.2.5. TL или язык типов. Поскольку TL (Type Language) будет использоваться в формальных спецификациях блоков TON, транзакций и сетевых дейтаграмм, он заслуживает краткого обсуждения.
TL - это язык, пригодный для описания зависимых алгебраических типов, которым разрешено иметь числовые (натуральные) и типовые параметры. Каждый тип описывается с помощью нескольких конструкторов. Каждый конструктор имеет
(читаемый человеком) идентификатор и имя, которое представляет собой битовую строку
(32-битное целое число по умолчанию). Кроме того, определение конструктора содержит список полей и их типы.
3 https://coq.inria.fr
4 https://core.telegram.org/mtproto/TL
16 2.2. Общие положения о блокчейнах
Набор определений конструктора и типа называется TL-схемой. IT обычно хранится в одном или нескольких файлах с su x. 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. Блоки и транзакции как операторы преобразования состояний.
Блокчейн имеет ассоциированное глобальное состояние

(тип) Состояние и транзакция (тип) Сделка. Семантика блокчейна в значительной степени определяется прикладной функцией транзакции: ev_trans: Транзакция × Состояние → Состояние
?
(3)
Здесь X
? обозначает Maybe X, результат применения монады Maybe к тип X. Это похоже на наше использование X
∗ для списка X. По существу, значение типа X
?
- это либо значение типа X, либо специальное значение⊥, указывающее на отсутствие фактического значения (подумайте о нулевом указателе). В нашем случае мы используем
State
? вместо состояния в качестве типа результата, потому что транзакция может быть недействительной
, если она вызывается из определенных исходных состояний (подумайте о попытке снять со счета больше денег, чем на самом деле).
Мы могли бы предпочесть каррированную версию ev_trans : ev_trans: Транзакция → Состояние → Состояние
?
(4)
Поскольку блок-это, по сути, список транзакций, оценка блока функция ev_block: Блок → Состояние → Состояние
?
(5) может быть получен из ev_trans. Он принимает блок B: Блок и предыдущее состояние блокчейна s: Состояние (которое может включать хэш предыдущего
17 2.2. Общие положения о блокчейнах блок) и вычисляет следующее состояние блокчейна s = ev_block (B) (s): Состояние, которое является либо истинным состоянием, либо специальным значением⊥, указывающим, что следующее состояние не может быть вычислено (т. Е. Что блок недействителен, если вычисляется из начального состояния, заданного, например, блок включаеттранзакция пытается дебетовать пустой счет.)
2.2.7. Порядковые номера блоков. Каждый блок B в блокчейне может называться своим порядковым номером blk-seqno (B), начиная с нуля для самого первого блока и увеличиваясь на единицу при переходе к следующему блоку.
, blk-seqno (B)= blk-seqno blk-prev (B)+ 1
(6)
Обратите внимание, что порядковый номер не идентифицирует блок однозначно при наличии вилок.

2.2.8. Блокировать хэши. Другим способом ссылки на блок B является его хэш blk-hash(B), который на самом деле является хэшем заголовка блока B (однако заголовок блока обычно содержит хэши,которые зависят от всего содержимого блока B). Предполагая, что для используемой хэш-функции нет коллизий
(или, по крайней мере, что они очень маловероятны), блок однозначно идентифицируется по его хэшу.
2.2.9. Предположение о хешировании. При формальном анализе алгоритмов блокчейна мы предполагаем, что нет коллизий для k-битной хэш-функции Hash:
Bytes
∗
→
2 k используется:
Hash (s)= Hash (s) ⇒ s = s для любых s, s ∈ Байт
∗
(7)
Здесь байты = {0.. . 255} =
2 8 это тип байтов или набор всех байтов значения и байты
∗
- тип или набор произвольных ( конечных) списков байтов; в то время как
2
= {0, 1} это тип бита, и
2 k является ли набор (или фактически тип) всех k-бит последовательности (т. е. k-битные числа).
Конечно, (7) математически невозможно, потому что отображение из конечного множества в конечное множество не может быть инъективным. Более строгим предположением было бы
∀ s, s: s = s, P Hash (s)= Hash (s) = 2
- к
(8)
Однако это не так удобно для доказательств. Если (8) используется не более N раз в доказательстве с 2
- к
N < для некоторых небольших
(скажи,
= 10
−18
), мы можем
18 2.3. Состояние блокчейна, учетные записи и хэш-карты

рассуждайте так, как если бы (7) было истинно, при условии, что мы принимаем вероятность отказа (т. Е.
Окончательные выводы будут истинны с вероятностью не менее 1 -−.
Заключительное замечание: чтобы сделать вероятностное утверждение (8) действительно строго говоря, необходимо ввести распределение вероятностей на множестве байтов
∗ всех последовательностей байтов. Способ сделать это-предположить, что все байтовые последовательности одинаковой длины l равновероятны, и установить вероятность наблюдения последовательности длины l равной p l
- п l + 1 для некоторых p → 1 -. Тогда (8) следует понимать как предел условной вероятности P Hash (s)= Hash (s) /s = s когда p стремится к единице снизу.
2.2.10. Хэш используется для блокчейна TON. В настоящее время мы используем 256- битный хэш sha256 для блокчейна TON. Если он окажется слабее, чем ожидалось, он может быть заменен другой хэш-функцией в будущем. Выбор хэш-функции является контролируемым параметром протокола, поэтому он может быть изменен без хардфорков, как описано в 2.1.21.
2.3
Состояние блокчейна, учетные записи и хэш-карты
Выше мы отмечали, что любой блокчейн определяет определенное глобальное состояние, а каждый блок и каждая транзакция определяют трансформацию этого глобального состояния.
Здесь мы опишем глобальное состояние, используемое блокчейнами TON.
2.3.1. Идентификаторы учетных записей. Основные идентификаторы учетных записей,используемые блокчейнами TON или, по крайней мере, его masterchain и Workchain Zero, являются 256-битными целыми числами, которые считаются открытыми ключами для 256-битной криптографии с эллиптической кривой (ECC) для конкретной эллиптической кривой. Таким образом, account_id: Учетная запись = uint
256
=
2 256
(9)
Здесь Account-это тип учетной записи, а account_id : Account-это конкретная переменная типа Account.
Другие рабочие цепи могут использовать другие форматы идентификаторов учетных записей, 256-битные или иные.
Например, можно использовать идентификаторы учетных записей в биткойн-стиле,

равные sha256 открытого ключа ECC.
Однако длина бита l идентификатора учетной записи должна быть фиксирована при создании рабочей цепочки (в мастер-цепочке), и она должна быть не менее 64, поскольку первые 64 бита account_id используются для сегментирования и маршрутизации сообщений.
19 2.3. Состояние блокчейна, учетные записи и хэш-карты
2.3.2. Основной компонент: хэш-карты. Основным компонентом состояния блокчейна TON является хэш - карта. В некоторых случаях мы рассматриваем (частично определенные) отображения h :
2 n
2 m
В более общем плане нас могут заинтересовать hashmaps h :
2 n
X для составного типа X. Однако источник (или тип index) почти всегда
2 n
Иногда мы имеем пустое значение по умолчанию: X, а хэш - карта h :
2 n
→ X инициализируется значением по умолчанию i → empty.
2.3.3. Пример: Остатки на счетах TON. Важным примером являются остатки на счетах TON. Это хэш - карта баланс: Счет → uint
128
(10) картографическая учетная запись =
2 256 в ТОННУ монетного баланса типа uint
128
=
2 128
Эта хэш-карта имеет значение по умолчанию ноль, что означает, что изначально (до обработки первого блока) баланс всех счетов равен нулю.
2.3.4. Пример: постоянное хранилище смарт-контрактов. Другой пример приводится постоянным хранилищем смарт-контрактов, которое может быть (очень приблизительно) представлено в виде хэш-карты
Хранение :
2 256 2
256
(11)

Эта хэш - карта также имеет значение по умолчанию ноль, что означает, что неинициализированные ячейки постоянного хранилища считаются равными нулю.
2.3.5. Пример: постоянное хранение всех смарт - контрактов. Поскольку у нас есть более одного смарт-контракта, отличающегося account_id , каждый из которых имеет свое отдельное постоянное хранилище, у нас должна быть хэш-карта
Хранение: Учетная запись
(
2 256 2
256
)
(12) отображение account_id смарт-контракта в его постоянное хранилище.
2.3.6. Тип Hashmap. Hashmap-это не просто абстрактная (частично определенная) функция
2 n
X
; он имеет конкретное представление. Поэтому мы предположим, что у нас есть специальный тип hashmap
Hashmap (n, X): Тип
(13) соответствует структуре данных, кодирующей (частичную) карту
2 n
X
. Мы также можно написать
Hashmap (n: nat) (X: Type): Тип
(14)
20 2.3. Состояние блокчейна, учетные записи и хэш-карты или
Hashmap: nat → Тип → Тип
(15)
Мы всегда можем преобразовать h : Hashmap (n, X) в карту hget (h) :
2 n
→ Х
?
Отныне мы обычно пишем h [i] вместо hget (h) (i): h [i]: ≡ hget (h) (i): X
? для любого я :
2 n
, h: Hashmap (n, X)
(16)
2.3.7. Определение типа hashmap как дерева Патриций. Логически можно определить Hashmap (n, X) как (неполное) двоичное дерево глубины n с

метками ребер 0 и 1 и значениями типа X в листьях. Другим способом описания той же структуры было бы (побитовое) trie для двоичных строк длиной, равной n.
На практике мы предпочитаем использовать компактное представление этого trie, сжимая каждую вершину, имеющую только один дочерний элемент со своим родителем.
Полученное представление известно как дерево Патриций или двоичное дерево радиксов. Каждая промежуточная вершина теперь имеет ровно два дочерних элемента, помеченных двумя непустыми двоичными строками, начинающимися с нуля для левого дочернего элемента и с единицы для правого дочернего элемента.
Другими словами, в дереве Патриция существует два типа (некорневых) узлов:
ˆ
Лист (x), содержащий значение x типа X.
ˆ
Узел (l, s l
, r, s r
)
, где l - (ссылка на) левое дочернее или поддерево, s l является ли битовая строка меткой ребра, соединяющего эту вершину слева от нее ребенок (всегда начинающийся с 0), r-правильное поддерево, а s r это битовая строка, обозначающая край правого дочернего элемента (всегда начинающегося с
1).
Третий тип узла, который будет использоваться только один раз в корне дерева Патриции, также необходим:
ˆ
Корень (n, s
0
, т)
, где n - общая длина индексных битовых строк
Hashmap (n, X), s
0 является общим pre x всех индексных битовых строк, а t является ссылкой на Лист или узел.
Если мы хотим, чтобы дерево Patricia было пустым, будет использоваться четвертый тип
(корневого) узла:
ˆ
EmptyRoot (n), где n - общая длина всех битовых строк индекса.
21 2.3. Состояние блокчейна, учетные записи и хэш-карты
Мы определяем высоту дерева Патриции по высота (лист (x))= 0
(17) высота узла (l, s

l
, r, s r
) = высота (l)+ len (s l
) = высота (r)+ len (s r
)
(18) высота корня (n, s
0
, т) = лен (ы
0
) + высота (t)= n
(19)
Два последних выражения в каждой из двух последних формул должны быть равны. Мы используем деревья патриций высоты n для представления значений типа Hashmap (n, X).
Если в дереве N листьев (т. е. наша хэш − карта содержит N значений), то промежуточных вершин ровно N-1. Вставка нового значения всегда включает в себя разделение существующего ребра путем вставки новой вершины посередине и добавления нового листа в качестве другого дочернего элемента этой новой вершины. Удаление значения из хэш-карты приводит к обратному результату: лист и его родитель удаляются, а родитель родителя и другой его потомок становятся напрямую связанными.
2.3.8. Деревья Меркле-Патриции. При работе с блокчейнами мы хотим иметь возможность сравнивать деревья патриций (т. Е. хэш-карты) и их поддеревья, сводя их к одному хэш-значению. Классический способ достижения этого задается деревом Меркле. По сути, мы хотим описать способ хеширования объектов h типа Hashmap(n, X) с помощью хэш-функции
Hash, определенной для двоичных строк, при условии, что мы знаем, как вычислить хэши
Hash(x) объектов x : X (например, применяя хэш-функцию Hash кдвоичная сериализация объекта x).
Можно определить Hash (h) рекурсивно следующим образом:
Hash Leaf (x) := Hash(x)
(20)
Хэш-узел(l, s l
, r, s r
) :=
Hash Hash (l). Hash (r). code (s l
). код (ы r
)
(21)
Hash Root (n, s
0
, t): =

Хэш-код(n). код (ы
0
).
Хэш (t)
(22)
Здесь s. t обозначает конкатенацию (битовых) строк s и t, а code (s) является кодом pre x для всех битовых строк s. Например, можно закодировать 0 на 10, 1 на 11 и конец строки на 0.
5 5
Можно показать, что эта кодировка оптимальна примерно для половины всех краевых меток дерева Патриция со случайными или последовательными индексами. Оставшиеся метки ребер, скорее всего, будут длинными (т. Е. Почти 256 бит). Поэтому почти оптимальным кодированием для краевых меток является использование приведенного выше кода с pre x 0 для коротких битовых строк и кодирование 1, затем девяти битов
, содержащих длину l = |s| битовой строки s, а затем l битов s для длинных битовых строк (с l ≥ 10
).
22 2.3. Состояние блокчейна, учетные записи и хэш-карты
Позже мы увидим (см. 2.3.12 и 2.3.14), что это (слегка измененная) версия рекурсивно определенных хэшей для значений произвольных (зависимых) алгебраических типов.
2.3.9. Пересчет хэшей дерева Меркле. Этот способ рекурсивного определения Hash(h), называемый хэшем дерева Меркла, имеет то преимущество, что, если явно хранить Hash(h ) вместе с каждым узлом h (в результате чего получается структура, называемая деревом Меркла, или, в нашем случае, деревом Меркла Патриция), необходимопересчитайте не более n хэшей, когда элемент добавляется, удаляется или изменяется в хэш - карте.
Таким образом, если представить глобальное состояние блокчейна подходящим хэшем дерева Меркла, то легко пересчитать этот хэш состояния после каждой транзакции.
2.3.10. Доказательства Меркля. В предположении (7) об инъективности выбранной хеш-функции Hash можно построить доказательство того, что для заданного значения z
Hash (h), h: Hashmap(n, X) имеет hget (h) (i)= x для некоторого i :
2 n и x : X. Такое доказательство будет состоять из пути в дереве Merkle Patricia от листа, соответствующего i, до корня, дополненного хэшами всех братьев и сестер всех узлов, встречающихся на этом пути.
Таким образом, легкий узел
6 зная только значение Hash (h) для некоторого hashmap h (например, постоянное хранилище смарт-контракта или глобальное состояние

блокчейна)
, можно запросить запрос от полного узла
7 не только значение x = h [i]= hget (h) (i), но и такое значение вместе с доказательством Меркла, начиная с уже известного значения
Hash (h). Тогда, в предположении (7), узел света может проверить для себя
, что x действительно является правильным значением h [i].
В некоторых случаях клиент может захотеть получить значение y = Hash(x) =
Hash(h[i]) вместо этого, например, если сам x очень велик (например, сама хэш-карта). Тогда вместо этого может быть предоставлено доказательство Меркля для (i, y). Если x также является hashmap, то второе доказательство Меркла, начинающееся с y = Hash(x)
, может быть получено из полного узла, чтобы обеспечить значение x [j]= h [i] [j] или просто его хэш.
6
Легкий узел-это узел, который не отслеживает полное состояние цепочки осколков; вместо этого он хранит минимальную информацию,такую как хэши нескольких последних блоков, и полагается на информацию, полученную от полных узлов, когда возникает необходимость проверить некоторые части полного состояния.
7
Полный узел-это узел, отслеживающий полное актуальное состояние цепочки осколков под вопросом.
23 2.3. Состояние блокчейна, учетные записи и хэш-карты
2.3.11. Важность доказательств Меркля для многоцепочечной системы, такой как TON. Обратите внимание, что узел обычно не может быть полным узлом для всех шардчейнов, существующих в среде TON. Обычно это полный узел только для некоторых шардчейнов, например, тех, которые содержат его собственную учетную запись, смарт
-контракт, в котором он заинтересован, или тех, которым этот узел был назначен в качестве валидатора. Для других шардчейнов это должен быть легкий узел, иначе требования к хранению, вычислениям и пропускной способности сети будут непомерно высокими. Это означает, что такой узел не может напрямую проверять утверждения о состоянии других шардчейнов; он должен полагаться на доказательства Меркла, полученные от полных узлов для этих шардчейнов, что так же безопасно, как и проверка сама по себе, если
(7) не завершится неудачей (т. Е. Не будет найдено хэш-столкновение).
2.3.12. Особенности TON VM. Виртуальная машина TON или TVM (TON Virtual
Machine), используемая для запуска смарт-контрактов в masterchain и Workchain
Zero, значительно отличается от обычных конструкций, вдохновленных EVM
(Ethereum Virtual Machine): она работает не только с 256-битными целыми числами, но и с (почти) произвольными записями, структурами, или sum-типы продуктов , что делает его более подходящим для выполнения кода, написанного на высокоуровневых