Checking an inclusion proof
Certificate transparency logs store issued certificates in a Merkle tree and on request send a proof that a certificate is in the log: the leaf number, the tree size and the hashes of the neighbours on the path from the leaf to the root. A browser that receives such a proof checks it itself. Write this check.
The tree is built as in RFC 6962. The hash of a leaf with data d is SHA-256(0x00 ‖ d). The tree over a range of one leaf is the leaf itself. If there are more leaves, the left subtree takes the first k leaves, where k is the largest power of two less than their number, the right one the rest, and the hash of the node is SHA-256(0x01 ‖ left ‖ right). The proof for leaf number m in a tree of n leaves is the hashes of the neighbouring subtrees on the path from the leaf to the root, from the bottom up: at each level the neighbour is the subtree with which the subtree containing our leaf joins into a node.
A proof is correct if it has exactly as many hashes as there are levels on the path from leaf m to the root in a tree of n leaves, and if, climbing this path and attaching the neighbours on the proper side, we get the given root. A number outside the tree makes the proof incorrect.
Input
The first line holds the number of queries q (1 ≤ q ≤ 400). Each query is four lines: n, m and the number of hashes k (1 ≤ n ≤ 1018, 1 ≤ m ≤ 1018, 0 ≤ k ≤ 64, leaves numbered from one); the leaf data in hexadecimal; k hashes separated by spaces (64 hexadecimal digits each), or “-” when k = 0; the root.
Output
For each query, YES if the proof is correct, NO otherwise.
Examples
Example 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
Example 2
2 1 1 0 6f6e6c79 - 48823b3c6133664ce7b6219a005ad5ed7b5a91a69a0aa800cc51ce1cd4086955 1 1 0 6f74686572 - 48823b3c6133664ce7b6219a005ad5ed7b5a91a69a0aa800cc51ce1cd4086955
YES NO
Limits
- Time · Python
- 3000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
In a tree whose number of leaves is exactly a power of two, the leaf number decides everything: the lowest bit tells whether it is a left or a right child, then the next bit. What changes when there are, say, five leaves?
2Hint 2
In a tree of five leaves the fifth leaf on its own is the right subtree of the root, and its proof has one hash. By the bits of its index 4 = 1002 it is a left child three times. Which levels are “skipped” for it?
3The idea
Keep two numbers: fn, the place of our subtree on the current level, and sn, the place of the last subtree on this level. At the bottom these are the leaf index and n − 1 (from zero). If fn is odd, we are a right child: the neighbour is on the left. If fn is even and fn < sn, we are a left child: the neighbour is on the right. And if fn = sn and it is even, we have no neighbour on the right: this is the last subtree of an incomplete level, and it rises higher unchanged until it becomes someone’s right child. This is how the check in RFC 9162 works: when fn = sn the neighbour is on the left, and then fn and sn are shifted until fn becomes odd.
4Walkthrough
A step of the check: if sn is already 0, there are more hashes than levels, so the proof is wrong. If fn is odd or fn = sn: r ← SHA-256(0x01 ‖ neighbour ‖ r), and while fn is even and not zero, fn and sn are halved. Otherwise r ← SHA-256(0x01 ‖ r ‖ neighbour). At the end of the step fn and sn are halved once more. The proof is correct if the hashes ran out exactly when sn became zero, and r matched the root.
In the first example, the fifth leaf: fn = 4, sn = 4. They match, so the neighbour is on the left; it is the hash of the first four leaves, and the root comes at once. A check “by the bits” would take the leaf for a left child, attach the neighbour on the right and get a different hash. The third query of the same example is the same path but for the fourth leaf: its proof should have three hashes, and one is given, so the check rejects it, because sn did not reach zero.
The tree size is no formality here. It determines both the side of each neighbour and the length of the path. A check that forgot about n will accept a proof built for a different tree, and on incomplete trees reject an honest one. Why a leaf and a node are hashed with different prefixes, 0x00 and 0x01, is in the article on the Merkle tree: without them an internal node can be passed off as a leaf.
4+Solution
5Complexity
O(k) hashings per query: k ≤ 64, and for a tree of 1018 leaves the path is at most 60 levels long.
6Common mistakes
- Only the bits of the index. Correct for a tree of 2t leaves, but on an incomplete tree it mixes up sides for the last subtrees of a level: the first example.
- Not checking that the hashes ran out on time. A proof with an extra or missing hash sometimes assembles someone else’s root, but must be rejected on length.
- Numbering. In the statement leaves are numbered from one, and in the formulas of the check from zero.
- A number outside the tree. m > n is NO at once.