Проверка доказательства
Журналы прозрачности сертификатов хранят выданные сертификаты в дереве Меркла и по запросу присылают доказательство, что сертификат в журнале есть: номер листа, размер дерева и хеши соседей на пути от листа к корню. Браузер, получивший такое доказательство, проверяет его сам. Напишите эту проверку.
Дерево устроено как в RFC 6962. Хеш листа с данными d — SHA-256(0x00 ‖ d). Дерево над отрезком из одного листа — сам лист. Если листов больше, левое поддерево берёт первые k листов, где k — наибольшая степень двойки, меньшая их числа, правое — остальные, а хеш узла — SHA-256(0x01 ‖ левый ‖ правый). Доказательство для листа номер m в дереве из n листов — хеши соседних поддеревьев на пути от листа к корню, снизу вверх: на каждом уровне соседом служит то поддерево, с которым поддерево с нашим листом объединяется в узел.
Доказательство верное, если в нём ровно столько хешей, сколько уровней на пути от листа m к корню в дереве из n листов, и если, поднимаясь по этому пути и присоединяя соседей с нужной стороны, мы получаем данный корень. Номер вне дерева делает доказательство неверным.
Вход
В первой строке число запросов q (1 ≤ q ≤ 400). Каждый запрос — четыре строки: n, m и число хешей k (1 ≤ n ≤ 1018, 1 ≤ m ≤ 1018, 0 ≤ k ≤ 64, листы нумеруются с единицы); данные листа в шестнадцатеричной записи; k хешей через пробел (64 шестнадцатеричные цифры каждый) или «-» при k = 0; корень.
Выход
На каждый запрос — YES, если доказательство верное, иначе NO.
Примеры
Пример 1
3 5 5 1 65676773 0b494e91f09cdb81c273351afd08b15ee0d1b1b8c3546c6dfc9e460fe09896ef 2b659aa3c653f5c538c9e0235b731acb6d24a5e780e3fba2c698e580f175f274 5 1 3 6170706c65 1217f011afaa2ad828ec98b9bc3052a0d4e9084464b9f0609e765fc75e7e373e 50207330825485c343f7618e15b4d2b9548ae428373675b5e09988c794153db1 92913e67c1ef879838ce06e74ec2e259481593db1da01938ce5bacc23bd3c55b 2b659aa3c653f5c538c9e0235b731acb6d24a5e780e3fba2c698e580f175f274 5 4 1 65676773 0b494e91f09cdb81c273351afd08b15ee0d1b1b8c3546c6dfc9e460fe09896ef 2b659aa3c653f5c538c9e0235b731acb6d24a5e780e3fba2c698e580f175f274
YES YES NO
Пример 2
2 1 1 0 6f6e6c79 - 48823b3c6133664ce7b6219a005ad5ed7b5a91a69a0aa800cc51ce1cd4086955 1 1 0 6f74686572 - 48823b3c6133664ce7b6219a005ad5ed7b5a91a69a0aa800cc51ce1cd4086955
YES NO
Ограничения
- Время · Python
- 3000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
В дереве, где листов ровно степень двойки, всё решает номер листа: младший бит говорит, левый он ребёнок или правый, дальше — следующий бит. Что меняется, когда листов, например, пять?
2Подсказка 2
В дереве из пяти листов пятый лист сам по себе — правое поддерево корня, и в доказательстве у него один хеш. По битам номера 4 = 1002 он трижды левый ребёнок. Какие уровни для него «пропускаются»?
3Идея
Будем вести два числа: fn — место нашего поддерева на текущем уровне и sn — место последнего поддерева на этом уровне. Внизу это номер листа и n − 1 (с нуля). Если fn нечётно, мы правый ребёнок: сосед слева. Если fn чётно и fn < sn, мы левый: сосед справа. А если fn = sn и чётно, у нас нет соседа справа — это последнее поддерево неполного уровня, и оно поднимается выше без изменений, пока не станет чьим-то правым ребёнком. Так устроена проверка в RFC 9162: при fn = sn сосед слева, а потом fn и sn сдвигаются, пока fn не станет нечётным.
4Разбор
Шаг проверки: если sn уже 0, хешей больше, чем уровней, — неверно. Если fn нечётно или fn = sn: r ← SHA-256(0x01 ‖ сосед ‖ r), и пока fn чётно и не ноль, fn и sn делятся пополам. Иначе r ← SHA-256(0x01 ‖ r ‖ сосед). В конце шага fn и sn ещё раз делятся пополам. Доказательство верно, если хеши кончились ровно тогда, когда sn стал нулём, и r совпал с корнем.
В первом примере пятый лист: fn = 4, sn = 4. Совпали — сосед слева, это хеш первых четырёх листов, и сразу корень. Проверка «по битам» сочла бы лист левым ребёнком, приклеила соседа справа и получила бы другой хеш. Третий запрос того же примера — тот же путь, но для четвёртого листа: у него в доказательстве должно быть три хеша, а дан один, и проверка отвергает его, потому что sn не дошёл до нуля.
Размер дерева здесь не формальность. Он определяет и сторону каждого соседа, и длину пути. Проверка, которая про n забыла, примет доказательство, построенное для другого дерева, а на неполных деревьях отвергнет честное. Зачем лист и узел хешируются с разными префиксами, 0x00 и 0x01, — в статье о дереве Меркла: без них внутренний узел можно выдать за лист.
4+Решение
5Сложность
O(k) хеширований на запрос: k ≤ 64, и для дерева из 1018 листов путь не длиннее 60 уровней.
6Типичные ошибки
- Только биты номера. Верно для дерева из 2t листов, но на неполном дереве путает стороны у последних поддеревьев уровня: первый пример.
- Не проверять, что хеши кончились вовремя. Доказательство с лишним или недостающим хешем иногда собирает чужой корень, но должно быть отвергнуто по длине.
- Нумерация. В условии листы нумеруются с единицы, а в формулах проверки — с нуля.
- Номер вне дерева. m > n — сразу NO.