Delegated log verification

[adisbladis]

To fully verify that a Trustix log is 100% internally consistent & hasn't rewritten any old data is an expensive operation.
It requires replaying the entire log from scratch, meaning that it's not feasible to prove that logs are indeed append-only in normal operation.

To alleviate this we can create another log type which doesn't contain build results themselves, but instead contain observations about other build logs root hashes.
This will result in a relatively small "meta-log" that's comparably cheap to verify and decide on.

Consider this scenario:

We have these actors:

• Alice (client)
• Bob (build log)
• Carol (build log)
• Dave (build log)
• Erin (audit log)
• Faythe (audit log)

Alice want's to decide on an output hash for Nix store path "/nix/store/cg8a576pz2yfc1wbhxm1zy4x7lrk8pix-hello-2.12.1".
She will do that through cross-checking Bob, Carol & Dave's build results.

To do that she needs a Signed Tree Head (STH) for both Bob, Carol & Dave.
The STH contains two root hashes: One for the log (merkle hash) & one for the map (sparse merkle hash).

She also wants to verify that the logs are both operating correctly in an append-only fashion.
To meet this requirement she now has to walk every single entry from the start of their respective logs to verify append-only operation.

She could instead relies on Erin & Faythe's audit logs to verify root hashes for Bob, Carol & Dave.

An interesting side effect of this is a very significant performance boost as a read of the log now implies checking consistency with STH hashes for every read, but assuming a log is already audited we only need to verify the consistency with the map root hash for every read.

Additionally this is a protection mechanism against split view attacks, because Alice can verify that neither Bob, Carol or Dave has issued STHs that are inconsistent with what Erin & Faythe are observing.
This prevents targeted attacks where you might get build logs to collude against a particular client.