[bwesterb]

You only need to send one treehead per MTCA. From that one treehead the server can infer it must also have the previous few. If that's still too much, we can compress it even further by only sending "I trust the standard CAs of Mozilla plus/minus some CAs and the stalest treehead I have has this timestamp". That'll be just a few bytes.

[cryptonector]

Yes, a timestamp and a code for which set of trust anchors it trusts should be enough. Or even just a timestamp. The server is not going to have lots of certs chaining to many roots, so the client's trust anchor set is really not that relevant. The timestamp can be in coarse increments.