Ячейки и пакеты ячеек (Cell & Bag of Cells (BoC))

warning

Эта страница переведена сообществом на русский язык, но нуждается в улучшениях. Если вы хотите принять участие в переводе свяжитесь с @alexgton.

Cell

Ячейка представляет собой структуру данных в блокчейне TON. Ячейки могут хранить до 1023 бит и иметь до 4 ссылок на другие ячейки.

Bag of Cells

Bag of Cells (BoC) - это формат для сериализации ячеек в массивы байтов, который более подробно описан в схеме TL-B.

В TON все состоит из ячеек, включая код контракта, хранимые данные, блоки, что обеспечивает упрощение и надежную гибкость процесса.

Сериализация ячеек

Давайте проанализируем наш первый пример Bag of Cells :

1[8_] -> {
  24[0AAAAA],
  7[FE] -> {
    24[0AAAAA]
  }
}

В этом примере у нас есть корневая ячейка размером 1 бит, которая имеет 2 ссылки: первая на 24-битную ячейку, а вторая на 7-битную ячейку, которая имеет 1 ссылку на 24-битную ячейку.

Чтобы эта структура работала так, как задумано, необходимо превратить ячейки в одну последовательность байтов. Для этого, во-первых, мы используем только уникальные типы ячеек, ниже представлены 3 из 4:

1[8_]
24[0AAAAA]
7[FE]

примечание

Чтобы оставить только уникальные ячейки, их необходимо сравнить. Чтобы сделать это, нам нужно сравнить [хэши] (#cell-хэш) ячеек.

1[8_]      -> index 0 (root cell)
7[FE]      -> index 1
24[0AAAAA] -> index 2

Теперь давайте вычислим описания для каждой из 3 ячеек, упомянутых выше. Эти описания состоят из 2 байт, в которых хранятся флаги, содержащие информацию о длине данных и количестве связей с данными.

Первый байт - дескриптор ссылок - вычисляется как r+8s+32l, где 0 ≤ r ≤ 4 - количество ссылок ячеек, 0 ≤ s ≤ 1 - 1 для экзотических ячеек и 0 для обычных, а 0 ≤ l ≤ 3 - уровней ячейки.

Второй - битовый дескриптор - равен floor(b / 8) + ceil (b / 8), где 0 <= b <= 1023 - количество бит в ячейке. Этот дескриптор представляет длину полных 4-битных групп данных ячейки (но не менее 1, если она не пустая).

Результат:

1[8_]      -> 0201 -> 2 refs, length 1
7[FE]      -> 0101 -> 1 ref, length 1
24[0AAAAA] -> 0006 -> 0 refs, length 6

Для данных с неполными 4-битными группами в конец последовательности добавляется 1 бит. Это означает, что он обозначает конечный бит группы и используется для определения истинного размера неполных групп. Давайте добавим биты ниже:

1[8_]      -> C0     -> 0b10000000->0b11000000
7[FE]      -> FF     -> 0b11111110->0b11111111
24[0AAAAA] -> 0AAAAA -> do not change (full groups)

Теперь давайте добавим индексы ссылок:

1[8_]      -> 0201 -> refers to 2 cells with such indexes
7[FE]      -> 02 -> refers to cells with index 2
24[0AAAAA] -> no refs

И соединим все вместе:

C0     0201
FF     02
0AAAAA

И объединим это, объединив соответствующие строки в один массив байтов: 0201c002010101ff0200060aaaaa, размером 14 байт.

Показать пример

func (c *Cell) descriptors() []byte {
  ceilBytes := c.bitsSz / 8
  if c.bitsSz%8 ! = 0 {
    ceilBytes++
  }

	// calc size
	ln := ceilBytes + c.bitsSz / 8

	specBit := byte(0)
	if c.special {
	  specBit = 8
	}

	return []byte{byte(len(c.refs)) + specBit + c.level*32, byte(ln)}
}

Источник

Упаковка Bag of Cells

Давайте упакуем ячейку из раздела выше. Мы уже сериализовали ее в плоский 14-байтовый массив.

Поэтому мы строим заголовок согласно его схеме.

b5ee9c72                      -> id tl-b of the BoC structure
01                            -> flags and size:(## 3), in our case the flags are all 0,
                                 and the number of bytes needed to store the number of cells is 1.
                                 we get - 0b0_0_0_00_001
01                            -> number of bytes to store the size of the serialized cells
03                            -> number of cells, 1 byte (defined by 3 bits size:(## 3), equal to 3.
01                            -> number of root cells - 1
00                            -> absent, always 0 (in current implementations)
0e                            -> size of serialized cells, 1 byte (size defined above), equal to 14
00                            -> root cell index, size 1 (determined by 3 size:(## 3) bits from header),
                                 always 0
0201c002010101ff0200060aaaaa  -> serialized cells

Далее мы объединяем все, что указано выше, в массив байтов в нашем окончательном BoC: b5ee9c7201010301000e000201c002010101ff0200060aaaaa

Примеры реализации Bag of Cells: Сериализация, Десериализация

Специальные (экзотические) ячейки

Как правило, ячейки, работающие на TON, делятся на два основных типа: обычные ячейки и специальные ячейки. Большинство ячеек, с которыми работают пользователи, являются обычными ячейками, отвечающими за перенос информации.

Тем не менее, для реализации внутренней функциональности сети иногда требуются специальные ячейки, которые используются для различных целей в зависимости от их подтипа.

Уровень ячейки

Каждая ячейка имеет атрибут, называемый Level, который представлен целым числом от 0 до 3.

Уровень обычных ячеек

Уровень обычной ячейки всегда равен максимальному из уровней всех ее ссылок:

Lvl(c) = max(Lvl(r_0), ..., Lvl(r_i), ..., Lvl(r_e))

Где i — это индекс ссылки c, e — это количество ссылок c.

Уровень обычной ячейки без ссылок равен нулю

Уровень экзотических ячеек

У экзотических ячеек есть разные правила установки их уровня, которые описаны в этой статье.

Хэш ячейки

В большинстве случаев пользователи работают с обычными ячейками с уровнем 0, которые имеют только один хэш, называемый хэшем представления (или бесконечным хэшем).

Ячейка c с уровнем Lvl(c) = l, где 1 ≤ l ≤ 3 имеет хэш представления, а l "более высокий" хэш.

Стандартный расчет хэша представления ячейки

Сначала нам нужно рассчитать представление ячейки (что похоже на сериализацию ячейки, описанную выше)

Вычислить байты дескрипторов
Добавить сериализованные данные ячейки
Для каждой ссылки ячейки добавить ее глубину
Для каждой ссылки ячейки добавить ее хэш представления
Вычислить хэш SHA256 результата

Давайте проанализируем следующие примеры:

Ячейка без ссылок

32[0000000F]

Вычисление дескрипторов

Дескриптор ссылки равен r+8s+32l = 0 + 0 + 0 = 0 = 00

Дескриптор бит равен floor(b / 8) + ceil (b / 8) = 8 = 08

Объединив эти байты, мы получим 0008

Сериализация данных ячейки

В этом случае у нас есть полные 4-битные группы, поэтому нам не нужно добавлять биты к данным ячейки. Результатом будет 0000000f

Глубина ссылок

Мы пропускаем эту часть, потому что у нашей ячейки нет ссылок

Хэши ссылок

Мы пропускаем эту часть, потому что у нашей ячейки нет ссылок

Вычисление SHA256

Объединяя байты из предыдущих шагов, мы получаем 00080000000f, а SHA256 из этой строки байтов равен 57b520dbcb9d135863fc33963cde9f6db2ded1430d88056810a2c9434a3860f9 — это хэш представления ячейки.

Ячейка со ссылками

24[00000B] -> {
	32[0000000F],
	32[0000000F]
}

Вычисление дескрипторов

Ссылочный дескриптор равен r+8s+32l = 2 + 0 + 0 = 0 = 02

Битовый дескриптор равен floor(b / 8) + ceil (b / 8) = 6 = 06

Объединяя эти байты, получаем 0206

Сериализация данных ячейки

В этом случае у нас есть полные 4-битные группы, поэтому нам не нужно добавлять биты к данным ячейки. Результатом будет 00000b

Глубина ссылок

Глубина представлена 2 байтами. Наша ячейка имеет 2 ссылки, и глубина каждой из них равна нулю, поэтому результатом этого шага будет 00000000.

Хэши ссылок

Для каждой ссылки мы добавляем ее хэш (мы вычислили выше), поэтому результат будет 57b520dbcb9d135863fc33963cde9f6db2ded1430d88056810a2c9434a3860f957b520dbcb9d135863fc33963cde9f6db2ded1430d88056810a2c9434a3860f9

Вычисление SHA256

Объединяя байты из предыдущих шагов, мы получаем 020600000b0000000057b520dbcb9d135863fc33963cde9f6db2ded1430d88056810a2c9434a3860f957b520dbcb9d135863fc33963cde9f6db2ded1430d88056810a2c9434a3860f9 а SHA256 из этой строки байтов равен f345277cc6cfa747f001367e1e873dcfa8a936b8492431248b7a3eeafa8030e7 - это хэш представления ячейки.

Вычисление более высоких хэшей

Более высокие хэши обычной ячейки c вычисляются аналогично хэшу ее представления, но с использованием более высоких хэшей ее ссылок вместо хэшей их представления.

Экзотические ячейки имеют свои собственные правила вычисления своих более высоких хэшей, которые описаны в этой статье.

Cell​

Bag of Cells​

Сериализация ячеек​

Упаковка Bag of Cells​

Специальные (экзотические) ячейки​

Уровень ячейки​

Уровень обычных ячеек​

Уровень экзотических ячеек​

Хэш ячейки​

Стандартный расчет хэша представления ячейки​

Ячейка без ссылок​

Ячейка со ссылками​

Вычисление более высоких хэшей​

См. также​