It feels like merkle trees[1] could help here. We could split each transparency log into blocks, issuing a new block every 24 hours. Every block header would c

It feels like merkle trees[1] could help here. We could split each transparency log into blocks, issuing a new block every 24 hours. Every block header would contain a hash of the root node of it's Merkle tree, the hash of the previous header and a digital signature. Storing 1000 latest headers for 5 transparency logs would take less than a megabyte, so most browsers would be fine with this. When sending a certificate, the server would also send the header hashes for the block the certificate appears in, as well as the contents of any intermediate merkle tree nodes. In the rare case where we encounter a certificate issued in the latest 24 hours, we would directly ask the transparency log for a hash list of all certificates issued in a given 1 minute period (taken from the issuance date in the certificate).