We might be able to get away with 16 byte hashes, by complicating the design significantly. I do not think that this is worthwhile for the first version, but I'll write the thoughts down in this issue for future reference.
If we truncate hashes to 16 bytes, then a CA (even with the CA chosen randomiser #45) can find two different batches with the same root in 2^64 work. This allows the CA to issue certificates for assertions that escape transparency.
We can prevent this, if the CA does not control the randomiser, and only learns it after having committed to the batch.
This can be done as follows. We have two CAs. The seconds mirrors the first with an offset, so batch n in the first is mirrored in batch n+offset of the second. The first uses 32 byte hashes, and the second truncates to 16 bytes. The second uses as randomiser, public randomness that's not known before say n+grace where 0 < grace ≤ offset. For this a post-quantum version of drand could do.
Before a TS would trust the truncated mirror, it must:
Fetch the nth batch from the original before n+grace. This is essential, because if the first CA can delay publication of the batch until n+grace, it can cheat in collusion with the mirror.
Check whether assertions of the mirror matches the original.
Compute the root of the mirror with the correct public randomness.
The mirror could be run by a TS.
This proposal will be much harder to run, as CAs wouldn't be allowed to issue batches late, and monitors need to watch closely for late issuance.
We might be able to get away with 16 byte hashes, by complicating the design significantly. I do not think that this is worthwhile for the first version, but I'll write the thoughts down in this issue for future reference.
If we truncate hashes to 16 bytes, then a CA (even with the CA chosen randomiser #45) can find two different batches with the same root in 2^64 work. This allows the CA to issue certificates for assertions that escape transparency.
We can prevent this, if the CA does not control the randomiser, and only learns it after having committed to the batch.
This can be done as follows. We have two CAs. The seconds mirrors the first with an offset, so batch
nin the first is mirrored in batchn+offsetof the second. The first uses 32 byte hashes, and the second truncates to 16 bytes. The second uses as randomiser, public randomness that's not known before sayn+gracewhere0 < grace ≤ offset. For this a post-quantum version of drand could do.Before a TS would trust the truncated mirror, it must:
nth batch from the original beforen+grace. This is essential, because if the first CA can delay publication of the batch untiln+grace, it can cheat in collusion with the mirror.The mirror could be run by a TS.
This proposal will be much harder to run, as CAs wouldn't be allowed to issue batches late, and monitors need to watch closely for late issuance.