Certificate Transparency Logs

Question

What is the actual advantage of using a Merkle tree for verifying?

In my understanding, the verifier needs to know at which "position" the certificate to check is in order to compute the hash and know which hashes are neighbors to the path to the root.

These neighbor hashes are then queried from the CT log.

If trust is the issue, what hinders the CT log provider to respond with arbitrary data?

Space efficiency cannot be the problem it solves as the merkle tree is larger than just a list of the hashes of the certificates.

If privacy is the issue, can't the CT log provider reconstruct the queried certificate from the neightbors along the path?

So my only argument for Merkle trees would be using it for the logarithmic-time checking if a hash is contained. Is this the actual reason?

Answer 1

Hi,

Great questions!

Merkle Trees are an append-only datastructure.
They are basically just trees that contain hashes in their nodes.
If we would use lists, we would need to use the hashes of all certificates in the list in order to compute the consistency proof.
This would make it much slower than just using a few node hashes, afaik.

The positions of certificates in the tree are fixed and the certificates get a leaf id.
The auditors know the amount of certificates in the tree and can thus determine the exact position of the certificate in the tree.
This way, they can easily determine which node hashes they need for the consistency proof.

We trust the CT logs to not respond with random data.
If they would do that, they would not be used as a CT log for long.

I am not sure if a Merkle Tree is strictly (or much) larger than just a list.
This really depends on how the tree is represented on a storage level.

Privacy is indeed an issue.

However, we did not cover CT logs this thoroughly in the lecture.
The exam will also not query such deep knowledge about them.

Cheers,
Sebastian