Содержимое и хеширование

Утверждение записи — это хеш содержимого. Всё, что запись Label 309 говорит о существовании, вытекает из криптографического хеша байтов содержимого, закреплённого в блокчейне под меткой метаданных 309. На этой странице описано, как этот хеш переносится в записи, к чему именно он привязан и как один 32-байтовый корень способен заменить сколь угодно большую партию элементов.

Карта hashes

Каждый элемент записи несёт карту hashes — CBOR-карту, сопоставляющую идентификатор алгоритма с сырым 32-байтовым хешем.

hashes = {
  "sha2-256": h'…32 bytes…',      ; key = algorithm id, value = raw digest
}

Ключи — это текстовые идентификаторы из реестра хешей; значения — сырые байтовые строки, никогда не в hex-кодировке. Карта ДОЛЖНА содержать хотя бы одну запись, и каждый зарегистрированный алгоритм хеширования даёт ровно 32 байта:

Оба идентификатора обязательны к реализации для верификаторов, поэтому запись с единственным хешем под любым из них проходит проверку везде. Встретив нераспознанный идентификатор, верификатор отклоняет запись со стабильным кодом ошибки, а не молча пропускает эту запись. Полный реестр, включая зарезервированные постквантовые слоты, приведён на странице Реестры алгоритмов.

Применение CBOR-карты — вместо параллельных массивов или списка подобъектов {alg, digest} — даёт три следствия, которые входят в контракт формата. Дублирование алгоритмов исключено по построению, поскольку ключи CBOR-карты уникальны. Каноническая сортировка получается сама собой: канонический CBOR упорядочивает ключи по их закодированным байтам, поэтому два производителя, выражающие один и тот же набор хешей, выдают побайтово одинаковые карты, а любая подпись на уровне записи поверх них остаётся стабильной. Наконец, такая структура не требует поэлементной проверки: структурный валидатор лишь проверяет, что каждый ключ зарегистрирован, а длина каждого значения совпадает с длиной хеша соответствующего алгоритма.

К чему привязан хеш

Хеш привязан к байтам содержимого — той самой байтовой последовательности, для которой производитель фиксирует время существования. Каждая запись в карте hashes должна быть хешем именно этой байтовой последовательности под своим названным алгоритмом; запись, элементы которой описывают разные варианты открытого текста, не соответствует стандарту. Если байты содержимого доступны верификатору, он ДОЛЖЕН пересчитать каждый хеш и отклонить запись, если хотя бы один из них не совпадает.

Когда запись несёт конверт шифрования (enc), хеш привязан к открытому тексту, а не к шифртексту. Это сделано намеренно: подтверждение существования (PoE) существует для того, чтобы автор позднее мог раскрыть открытый текст и доказать, что тот существовал в заданный момент времени. Хеширование шифртекста доказывало бы лишь то, что существовал некий зашифрованный блок данных, а это ничего не говорит об исходном содержимом. Поэтому запечатанная запись по-прежнему точно доказывает, какой именно открытый текст получил отметку времени: получатель расшифровывает данные, заново вычисляет хеши открытого текста и сверяет их с ончейн-обязательством. Следовательно, элемент с полем enc должен нести хотя бы одну запись с хешем содержимого — без неё не было бы утверждения об открытом тексте, с которым можно сверяться.

Один хеш или несколько

Одного хеша содержимого достаточно для полного соответствия стандарту. Для всех 256-битных хешей в реестре лучшие из известных атак на нахождение второго прообраза лежат на уровне 2^256 или около него в классической модели — одного надёжного 256-битного хеша уже достаточно, чтобы покрыть реалистичную модель угроз на весь срок архивного хранения записи, и структурные валидаторы не выдают предупреждений для записей с единственным элементом в карте хешей.

Производитель МОЖЕТ добавить вторую запись из независимого семейства конструкций как дополнительный рубеж защиты по принципу эшелонирования — соединив sha2-256 (SHA-2: конструкция Merkle — Дамгора) с blake2b-256 (BLAKE2: конструкция HAIFA на основе перестановки, производной от ChaCha). Поскольку у этих двух семейств нет общей структурной родословной, запись, несущая оба хеша, становится уязвимой лишь в том случае, если оба семейства одновременно поддадутся криптоанализу. Цена — один дополнительный 32-байтовый хеш и его короткий идентификатор на каждый элемент; выбор остаётся за производителем и никогда не является обязательным.

Пакетные обязательства Merkle

Один хеш содержимого закрепляет одно содержимое. Чтобы закрепить сколь угодно большую совокупность — набор из 500 артефактов сборки CI, поток событий IoT, партию записей журнала аудита, — Label 309 определяет массив верхнего уровня merkle[]. Каждый его элемент привязан к упорядоченному списку 32-байтовых листьев, и в блокчейне публикуется один 32-байтовый корень; сами упорядоченные листья хранятся вне блокчейна.

merkle = [
  {
    "alg":        "rfc9162-sha256",
    "root":       h'…32 bytes…',   ; canonical root over the ordered leaves
    "leaf_count": 4,               ; binds the on-chain root to the leaf-list size
    "uris":       [ … ],           ; OPTIONAL — where the off-chain leaves list lives
  },
]

Зарегистрированный алгоритм обязательства — rfc9162-sha256: Merkle Tree Hash из RFC 9162 §2.1.1, где базовым хешем служит SHA-256. Это конструкция обязательства к списку, отличная от реестра хешей содержимого: корень Merkle привязан к структуре списка листьев, тогда как хеш sha2-256 привязан к байтам открытого текста, — поэтому он размещается в собственном массиве, а не внутри hashes. Ончейн-поле leaf_count связывает корень с размером внецепочечного списка, исключая подмену, при которой для некоторой позиции листа собиралось бы дерево другого размера с тем же корнем.

Построение дерева

В этой конструкции листья отличаются от внутренних узлов однобайтовым префиксом для разделения областей: 0x00 — для листьев, 0x01 — для внутренних узлов, — так что атакующий не может сконструировать внутренний узел, коллизирующий с листом. Для упорядоченного списка L = (d_0, …, d_{n-1}) из 32-байтовых значений при n ≥ 1 Merkle Tree Hash определяется рекурсивно:

MTH(L) = SHA-256(0x00 || d_0)                            when n == 1
MTH(L) = SHA-256(0x01 || MTH(L[0:k]) || MTH(L[k:n]))     when n > 1
         where k is the largest power of 2 strictly less than n

Важное следствие: одиночный лист хешируется как SHA-256(0x00 || d_0), а не как голый лист. Поэтому корень дерева с одним листом никогда не равен самому листу. Производители, желающие зафиксировать время для одного содержимого, ДОЛЖНЫ напрямую использовать обычную запись sha2-256 или blake2b-256, а не дерево Merkle с одним листом. Пустое дерево (n == 0) запрещено.

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

Внецепочечный список листьев

Корень бесполезен без списка листьев, поэтому производители сохраняют упорядоченные листья вне блокчейна. Канонический артефакт — это документ cardano-poe-merkle-leaves-v1, закодированный как канонический CBOR (RFC 8949): 32-байтовый корень, упорядоченный массив 32-байтовых листьев и количество листьев.

leaves-list = {
  "format":     "cardano-poe-merkle-leaves-v1",
  "tree_alg":   tstr,                   ; registered list-commitment algorithm id
  "root":       bytes .size 32,         ; raw 32 bytes, not hex
  "leaves":     [ + bytes .size 32 ],   ; ordered raw 32-byte leaves
  "leaf_count": 1..4294967295,          ; 1 .. 2^32-1; MUST equal the length of `leaves`
  ? "leaf_alg": tstr,                   ; informative; no verification semantics
}

Верификатор находит внецепочечный список, заново вычисляет корень из его поля leaves по приведённой выше конструкции и сверяет его с ончейн-полем merkle[i].root байт в байт; значение leaf_count в файле должно совпадать как с ончейн-полем leaf_count, так и с len(leaves). Этот контейнер канонического CBOR — единственная нормативная форма списка листьев: ни JSON-проекции, ни альтернативной сериализации не существует, так что две реализации, обменивающиеся списком листьев, всегда обмениваются побайтово сравнимыми документами.

Доказательства включения

Смысл объединения в партии — избирательное раскрытие: доказать, что один элемент входил в зафиксированный список, не публикуя заново — и даже не раскрывая — остальные. Доказательство включения для листа — это упорядоченный список хешей соседних узлов вдоль пути от этого листа к корню: путь соседних узлов сложностью O(log n). Верификатор сворачивает лист и его соседей вверх по дереву согласно RFC 9162 и принимает доказательство тогда и только тогда, когда восстановленный корень побайтово равен опубликованному.

Поскольку деревья RFC 9162 не дополняются до степени двойки, лист у правого края несбалансированного дерева может иметь более короткий путь, чем лист на полной стороне. Поэтому достоверной является алгоритмическая проверка — даёт ли свёртка тот же корень, — а не сравнение длины доказательства.