HTML Subresource Integrity

Posted Jul 7, 2016 8:59 UTC (Thu) by hkario (subscriber, #94864)
In reply to: HTML Subresource Integrity by nybble41
Parent article: HTML Subresource Integrity

the suggestion was so that the browser can do partial rendering as soon as the data is read, that means you need all the leaf nodes as the browser will want to update the rendering each time a new chunk is downloaded and checksummed

By writing 8KiB I meant exactly 8192 bytes of data i.e. only the leaf nodes.

In general yes, if getting parts of the tree requires less time (latency) than downloading the data, you don't need the full Merkle tree, but that doesn't assume that the whole point of using it is to reduce latency.

to post comments

HTML Subresource Integrity

Posted Jul 7, 2016 16:57 UTC (Thu) by nybble41 (subscriber, #55106) [Link]

> the suggestion was so that the browser can do partial rendering as soon as the data is read

Sorry, I wasn't looking at the bigger picture, just the statement that one needs the full Merkle tree to verify part of a file. If you want to download the full file while verifying each part as its received then you will need (almost) the full Merkle tree.

Still, it isn't necessary to download the Merkle tree in full before you can start verifying the data. You could stream the hashes from the Merkle tree in the order that they'll be needed to verify each block, e.g.:

(the root hash is already known from the SRI attribute)
Fetch A1, B1, C1, D1, E1, H(Block 1), and Block 0
Compute H(Block 0)
Compute E0 = H(H(Block 0)|H(Block 1))
Compute D0 = H(E0|E1)
Compute C0 = H(D0|D1)
Compute B0 = H(C0|C1)
Compute A0 = H(B0|B1)
Verify H(A0|A1) = root hash
Fetch Block 1
Verify H(Block 1)
Fetch H(Block 3) and Block 2
Compute H(Block 2)
Verify H(H(Block 2)|H(Block 3)) = E1
Fetch Block 3
Verify H(Block 3)
Fetch E3, H(Block 5), and Block 4
Compute H(Block 4)
Compute E2 = H(H(Block 4)|H(Block 5))
Verify H(E2|E3) = D1
Fetch Block 5
Verify H(Block 5)
etc.

The expectation is that the hashes would be provided in this order in a separate file alongside the content. With this approach you can verify each block as it's downloaded. Even better, to do so you only need to download the hashes for the odd-numbered blocks and intermediate nodes; the even-numbered hashes can be computed from the content under the assumption that the even-numbered nodes are downloaded and verified first within each subtree. For larger files this should cut the number of downloaded hashes almost in half.