How much could we compress the list of trust anchors?

[bwesterb]

I do not think clients should send a lot of trust anchors. Nor do I think we should complicate the standard with a compression mechanism like this. It's good to think about though.

Coding subsets of integers

Theoretical limit

For the moment, let's simplify and assume trust anchors are numbers instead of OIDs. Say there are k=200 anchors with maximum value N=62,203 (number of PENs today). There are N choose k possible subsets of anchors to communicate. Thus, we cannot expect to code every subset with less than lg N choose k bits. We can approximate this well using Stirling's approximation: 243 bytes.

Rice coding

We can get quite close to this limit using a very simple method: Rice coding of differences. For each delta we compute q = floor(d / 2^b) and r = d mod 2^b, where b = round(-lg(-lg(1-k/N))) = 8. q is encoded in unary and r in binary, so 600 would be encoded as 0b11001011000. The 110 encodes q=2; the remainder is the remainder r. The average size using Rice coding for random subsets is about 244.3 bytes with a 95th percentile of 244.8 bytes.

Rice coding doesn't take advantage of big gaps. If we want to code {N-200, N-199, ..., N-1} that takes 255.25 bytes.

Huffman bitlength

A different approach is to write each delta in two parts: first code its bitlength, and then to write the delta (without its most significant bit). For the bitlengths we can use a Huffman code, which can be compressed efficiently using canonical trees and delta coding of the code lengths as in bzip2. (Here is an implementation.)

For random subsets this performs worse than Rice coding: 253 bytes on average with a 95th percentile of 255 bytes. However, it encodes {N-200, N-199, ..., N-1} in only 50 bytes, and there is room for improvement.

[davidben]

Another goofy encoding idea I had was just ranges. The old MTC scheme could be done with aliases on the issuance side ("if the client says batch 27, assume they also know batches 10 through 26"), but it could also be done by letting you efficiently encode things like 32473.123.{10-27} (32473.123 is the MTC CA prefix).

I could also imagine taking some of the goofy exclusion labels that TE had and instead recasting them as some kind of sequence of ranges. If we assume we don't need to punch too many holes, splitting ranges in two isn't horrible. And you could periodically rebalance by numbers by allocating new aliases higher up the number space, trusting that newer certs are aware of it. Not sure.

The DNS mechanism does handily remove the need for all these encoding tricks, but depends on DNS, so... 🤷

[bwesterb]

I wanted to add a few more remarks here.

Rule of thumb for size. It's not quite exact, but for N reasonably larger than k, the theoretical best average is approximately k * lg(N/k) bits to encode a random subset of k integers below N. So the number of bits per integer is directly related to the density: lg(N/k) = -lg(k/N).

Varying densities. Most compression mechanisms (including ncrlite) adapt to varying densities. If we assume the PENs used in MTC to be in the final quarter of the range, then it'd take only approximately 159 bytes to encode instead of 244.8 b.

Encoding actual TAIs instead of integers. A subset of integers can be seen as a list or as a bitmap. We can encode a set X of true TAIs as a subset of integers Enc(X) as follows. First we group the TAIs by their first component: write n, x_1, ..., x_n, X_1, ..., X_n, L such that X = x_1 . X_1 union x_2 . X_2 union ... union x_n . X_n cup L, where x_i are distinct (the components that appear), L is a set of integers (the components as is that appear as a TAI), and X_i are sets of relative OIDs.

Now, we can define

Bitmap(Enc(X)) = VarUint(n) 
      || Bitmap({x_1, ..., x_n})
      || Bitmap({i; 1 ≤ i ≤ n; x_i in L})
      || Bitmap(Enc(X_1)) || ... || Bitmap(Enc(X_n))

I guess in practice TAIs will be mostly <pen> or <pen>.<small number>. In that case I expect this to compress about bit worse but not that much worse than a simply a subset of pens. I can run some tests later.

Is the full hierarchical TAI worth it though? Isn't <pen>.<seqno> enough?

Tailored versus general purpose compression. ncrlite, Elias–Fano, and the like outperform general-purpose compression algorithms when compressing the subset represented as a list of numbers. If the subset is represented as a bitmap, then general-purpose compression algorithms are quite similar or outperform them in compressed size. The difference of course is that we don't want to deal with a huge uncompressed bit map. Further advantages of the former are simpler implementation and better decompression speed.

[davidben]

Is the full hierarchical TAI worth it though? Isn't . enough?

Eh the only thing we really get out of the hierarchy is a cute solution to the MTC batch naming problem. Beyond that, it was just a very convenient, pre-existing namespace of short identifiers that anyone can assign out of.