Verify consistency of server data

[juagargi]

While downloading the data from the CT log servers works, no actual verification is performed using their Signed Tree Heads (STHs). Modify the downloader/updater so:

• [ ] The inserted and committed data in the DB is verified with the STH of the server at its current size (after all batches are downloaded).
• [ ] Investigate if the RFC mandates servers to implement obtaining the correct STH for intermediate sizes.
• [ ] If the answer above is yes, do the following:
  • [ ] Each batch is consistent-proven (one request to server per batch) with the previous one.
  • [ ] The last batch brings the state to the current size of the server, at which point it can be queried for its STH. Verify the new STH with the new contents.
• [ ] If the answer is no, solve the issue either with transactions or local intermediate STH computations (without server collaboration).

[juagargi]

The following related comment by @cyrill-k came up during a code review:

Maybe I can reformulate it: Again, let N = old tree size, B = batch size and M (> N + B) = the current size. Ideally, we would like to do the verification per batch, which works as follows: (1) Request STH at N+B with MHT root value R (2) Add the certificates in the batch [N, N+B] and calculate the new MHT root value R' (2) Verify that adding these certificates results results in the correct MHT root value (R==R') (3) Accept batch certificates and add to the DB However, since we cannot fetch the STH at arbitrary tree sizes, your current proposal is to accumulate all batches between N and M and then verify that the root value is correct: (1) Request STH at M with MHT root value R (2) Start DB transaction (3) for all batches ([N,N+B], [N+B,N+2B],...[N+XB,M]): add certificates in batch and calculate the final root value R' at tree size M (4) Verify that adding all batches results in the correct MHT root value (R==R') (5) Commit DB transaction

However, I'm not sure how well this will work because we have to lock tables, have huge transactions, etc. My suggestion is the following: (1) Request STH at M with MHT root value R (2) for all batches except the last one ([N, N+B], [N+B, N+2B], ..., [N+(X-1)B, N+XB]), do the following: (3a) for the batch [S, S+B], add all certificates in the batch which results in a new MHT root value R' (3b) request consistency proof for [S+B, M] (as I said before, it is not clear from the RFC if this must be supported by a CT log servers) (3c) verify that the consistency proof is valid given the two tree roots R' at S+B and R at M (3d) if the consistency proof is valid, add the batch to the DB (4) Verify and add the last batch [N+XB, M] as described in the first approach

The idea is that due to the append-only property of the MHT, it is not a problem if the MHT tree root at R' in (3c) is not signed by an STH. Because if the attacker can fabricate a batch B_0 (resulting in the root value R_0') which is different from the actual batch B_1 (resulting in to root value R_1'), such that there exist consistency proofs for both root values (consistency [R_0', R] and consistency [R_1', R]), the append-only property of the MHT would be violated. Someone should properly verify this.