Проверка доказательств Меркла для блоков iOS на облачном Mac

При поблочной загрузке офлайн-ресурсов iOS даже успешная проверка каждого блока не гарантирует, что в итоге будет собрана нужная версия. Клиент мог принять блоки из другого манифеста, а генератор и верификатор — по-разному обработать нечётное число узлов. Если разместить верификатор на облачном Mac с фиксированной средой Swift, сначала проверить протокол на небольших деревьях и лишь затем подключить его к реальному процессу загрузки, искать причины ошибок будет проще, чем при единственном сравнении общего хеша после скачивания.

Фиксируем правила дерева и доверенные входные данные

В этой статье используется SHA-256. Лист вычисляется как H(0x00 || исходные байты блока), внутренний узел — как H(0x01 || левый хеш || правый хеш); префиксы разделяют эти два типа входных данных. Хеши конкатенируются как исходные последовательности по 32 байта, а не как шестнадцатеричные строки.

Если на уровне остаётся один узел без пары, он переносится на следующий уровень без дублирования. Доказательство упорядочено от листа к корню и содержит только реально существующие соседние узлы. Расположение слева или справа определяется по индексу листа и ширине текущего уровня.

Манифест должен связывать версию ресурса, размер блока, общее число байтов, количество листьев и корень. Последний блок может быть короче стандартного размера. Поведение для пустого ресурса нужно определить отдельно, а не угадывать в верификаторе.

Доказательство Меркла отвечает на вопрос «принадлежит ли этот блок заданному корню», но не на вопрос «кто опубликовал этот корень». Корень и количество листьев должны поступать из доверенного канала либо из манифеста с проверенной подписью.

Реализуем строгий верификатор доказательств

Сохраните следующий код на облачном Mac в файл MerkleCheck.swift. Сначала выполните xcrun swift --version, чтобы зафиксировать версию инструментальной цепочки, затем запустите xcrun swift MerkleCheck.swift. Код использует только системные фреймворки; загружать сторонние пакеты не требуется.

import Foundation
import CryptoKit

func leaf(_ bytes: Data) -> Data {
    Data(SHA256.hash(data: Data([0]) + bytes))
}

func parent(_ left: Data, _ right: Data) -> Data {
    Data(SHA256.hash(data: Data([1]) + left + right))
}

func verify(
    chunk: Data,
    index: Int,
    count: Int,
    siblings: [Data],
    root: Data
) -> Bool {
    guard count > 0, index >= 0, index < count,
          root.count == 32,
          siblings.allSatisfy({ $0.count == 32 })
    else { return false }

    var value = leaf(chunk)
    var position = index
    var width = count
    var consumed = 0

    while width > 1 {
        let hasSibling = position % 2 == 1 || position < width - 1
        if hasSibling {
            guard consumed < siblings.count else { return false }
            let sibling = siblings[consumed]
            value = position % 2 == 0
                ? parent(value, sibling)
                : parent(sibling, value)
            consumed += 1
        }
        position /= 2
        width = width / 2 + width % 2
    }

    return consumed == siblings.count && value == root
}

func require(_ condition: Bool, _ name: String) {
    guard condition else {
        fatalError("Check failed: \(name)")
    }
}

let a = Data("A".utf8)
let b = Data("B".utf8)
let c = Data("C".utf8)
let ab = parent(leaf(a), leaf(b))
let root = parent(ab, leaf(c))

require(verify(chunk: c, index: 2, count: 3,
               siblings: [ab], root: root), "odd promotion")
require(verify(chunk: a, index: 0, count: 3,
               siblings: [leaf(b), leaf(c)], root: root), "left branch")
require(!verify(chunk: Data("X".utf8), index: 2, count: 3,
                siblings: [ab], root: root), "tampered chunk")
require(!verify(chunk: c, index: 2, count: 3,
                siblings: [ab, ab], root: root), "excess proof")
require(!verify(chunk: c, index: 3, count: 3,
                siblings: [ab], root: root), "invalid index")

При успехе скрипт завершается без вывода, при ошибке — с ненулевым кодом возврата. Сохраняйте результат выполнения; не подменяйте проверку кода возврата поиском определённой строки об успехе.

Проверяем граничные формы на небольших деревьях

В дереве из трёх листьев третий лист на первом уровне переносится выше без пары, поэтому для него нужен только один хеш соседнего узла. Если генератор дублирует последний узел, корень получится другим. Это не сетевая ошибка, и повторные попытки загрузки её не исправят.

После переноса скрипта в тестовый таргет добавьте как минимум следующие проверки:

• Дерево с одним листом: пустое доказательство принимается, добавление любого узла приводит к отказу.
• Дерево с двумя листьями: левый и правый листья проходят проверку каждый на своей позиции; при перестановке позиций проверка не проходит.
• Деревья с тремя и пятью листьями: последний лист корректно переносится выше; доказательство с одним недостающим или лишним узлом отклоняется.
• Недопустимые входные данные: отрицательный индекс, нулевое количество листьев, укороченные хеши и индекс за пределами диапазона отклоняются.

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

Проверяем блоки до записи

Слой загрузки сначала сверяет размер и индекс блока с манифестом, затем проверяет доказательство. После успешной проверки блок записывается во временный каталог соответствующей версии ресурса. Когда все блоки собраны, нужно проверить общую длину и создать маркер завершения. Интерфейс не должен трактовать «файл существует» как «ресурс доступен».

Доказательство — недоверенные входные данные. До разбора ограничьте размер тела ответа, количество узлов и длину хешей. Максимальный размер корректного доказательства растёт с числом уровней дерева; принимать массив неограниченной длины нельзя. Ограничьте также размер исходного блока, чтобы загрузка блока целиком в память не исчерпала её ещё до начала проверки.

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

Получаем интерпретируемые результаты регрессионных тестов

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

В завершение выполните сквозной тест с внесением ошибки: измените один байт блока во временном каталоге и убедитесь, что блок отклонён, а маркер завершения не создан. Затем восстановите правильный блок и проверьте, что задача может продолжиться. Критерий приёмки — не «код хеширования отработал», а невозможность попадания любых данных, не прошедших проверку доказательства, в набор ресурсов, доступных для чтения.

Часто задаваемые вопросы