Just to give a concrete example of the additional work for making #bamboo (spec) private enough: With bamboo, you can request individual entries of a log, but you also get the metadata of a few other entries in order to be able to verify the integrity of the entry you requested. So all metadata is conceptually public. Suppose I gave you access to only log entry 2. If you requested it, you'd als get the metadata of entry 1. Since you shouldn't have access to entry 1, everything in its metadata that allows you to derive information about its payload is a data leak.

Bamboo signs (and thus puts into the metadata) a bunch of stuff (that does not pertain to the actual payload), a payload_hash and the payload_size. The payload_size is sensitive metadata, we should try to hide it. Solution: sign a secure hash of the size instead. But that leaves another problem: An attacker can confirm guesses about such hashes, both for the size and for the actual content. To stop that, we should add some random bits - 96 bits should be sufficiently paranoid. So the new signing algorithm could be sign(stuff | hash(96_random_bits | payload_size | payload_hash)), where | denotes concatenation.

This introduces one more hash computation, the random number generation, and it requires everyone who has access and wants to be able to replicate the entry to store and transmit an additional 96 bits per entry. And the whole thing got more complicated.

I guess the practical cost is actually not that bad. The randomness is awkward since it introduces nondeterminism, but you could always use a cryptographically secure prng to get around that if determinism is required or if gathering sufficient entropy is too expensive.

This doesn't change at all that a routing layer that needs to keep the things it routes upon private incurs some very real (even in practice) panelties. But a private log format could serve as a basis for a system where open data can be routed efficiently and access-controlled data can use a more privacy-aware routing system without that effort being negated by leaky log metadata.

So thanks @mixmix and @mikey, looks like I won't get to chicken out of the hard stuff...

CC @piet