Reed Specification

Prefix authentication schemes (Meyer, 2023bb) — usually called append-only logs, or transparency logs — are cryptographic schemes to efficiently authenticate total ordering between events. For any two events from a single event stream, you can provide a short digest to certify that one happened before the other (as opposed to them happening concurrently). Reed is a lightweigh specification for implementing the scheme (Meyer, 2023aa), a scheme that produces shorter proofs than the traditional certificate transparency logs (Laurie et al., 2021).

Reed supersedes the earlier Bamboo specification. Reed is more efficient than Bamboo, more minimalistic in feature set, and generic over any particular cryptographic primitives. Bamboo was originally designed for efficient data replication, but I have since come to prefer more flexible replication technologies, so Reed sheds its data replication origins.

There will be graphs.


How about a dense one-paragraph summary, followed by a step-by-step explanation with pictures?

Reed is a transitive prefix authentication scheme (Meyer, 2023bb): given a sequence of events, we construct a directed acyclic graph (DAG), whose edges correspond to one object containing a secure hash of the other object (i.e., a Merkle-DAG). For each event, we assign a commitment vertex which has a path to the event, as well as paths to the commitment vertices of all earlier events. Given the commitment vertices of two events and the out-neighborhood of the path between them, we can reconstruct the hashes of all path vertices, thus proving that the first event did indeed happen before the other. Reed guarantees that the out-neighborhoods of these paths are small, i.e., verification is efficient.

Let’s break this down step by step. We start out with an ordered sequence of events, nine in the following example:

Figure 1

A sequence of nine events. Nothing interesting yet.

These events will form the basis of a graph. To ensure efficient prefix authentication, we first need to add some additional vertices. You do not yet need to care how we determine these, we are just getting a feel for the general concepts here.

Figure 2

We added some further vertices, according to rules we cover later.

Next, we add edges to turn these vertices into a useful graph. We are building a Merkle-DAG, which means that each vertex is labeled with a secure hash of the concatenation of the labels of its out-neighbors11This is a slight oversimplification, Reed proper also concatenates some metadata into the labels.. We need not visualize the labels, since they follow deterministically from the structure of the graph.

Figure 3

We add some edges. These follow a useful pattern, I promise. Can you smell the ternary almost-skip-list already?

Each event has an associated commitment vertex.

Figure 4

Events and their dedicated commitment vertices, grouped together. Note that each event is (trivially) reachable from its commitment vertex, and each commitment vertex is reachable from the commitment vertices of all later events.

To illustrate prefix authentication, we now arbitrarily select two events and highlight the path between their commitment vertices.

Figure 5

The shortest path between the commitment vertices of events and .

Given the (labels of the) out-neighborhood of that path, we can reconstruct the labels of the path vertices. In particular, we can reconstruct the labels of the commitment vertices of events and .

let label_2_0 := hash(concat(label(), label()))
let label_3_0 := hash(concat(label_2_0, label()))
let label_3_1 := hash(concat(label(), label_3_0))
let label_6_1 := hash(concat(label_3_1, label()))
let label_7_0 := hash(concat(label_6_1, label()))
let label_8_0 := hash(concat(label_7_0, label()))

If the hash function is secure, then it is computationally infeasible to fabricate labels that allow reconstructing a path between two vertices. Hence, the labels unforgeably certify that there is a path between the two vertices. In other words, event must have happened before event . Neat!


We assume hash to be a secure hash function that maps arbitrary bytestrings to fixed-width bytestrings. We call an output of hash a digest.

WeCompare Figure 1. define everything in terms of a sequence events of events, where an event is an arbitrary bytestring. The sequence events must have a length between one and both inclusive. We number events starting at because the math ends up much nicer that way.

TheCompare Figure 2. set InnerVertices is the set of all pairs such that and divides without remainder. We call the commitment vertexCompare Figure 4. of event .

Let be in InnerVertices. The predecessor vertexCompare Figure 3 (light edges). of is the event if , or the inner vertex , otherwise.

Let be in InnerVertices such that is not in InnerVertices. Then we call the topmost vertex of event .

Let be in InnerVertices, with The jump vertexCompare Figure 3 (dark edges). of is the topmost vertex of event

Figure 6

A graph depicting the first few vertices for a long sequence of events. The light, vertical edges connect each vertex to its predecessor vertex, the darker edges connect each vertex to its jump vertex.

The label of an event e is the hash of the concatenation of

  • the byte 0x00, and
  • e.

The label of an inner vertex is the hash of the concatenation of

  • the byte 0x01,
  • the label of the predecessor vertex of ,
  • the label of the jump vertex of — or the hash of the empty string, if
  • the big-endian encoding of Incorporating and in the labels is not needed for the security of the scheme, but it comes with a practical benefit: given any label of some inner vertex, you can prove its position in the graph by supplying the labels of its predecessor vertex and jump vertex. as an unsigned 64-bit integer, and
  • the encoding of as an unsigned 8-bit integer.

You can find the shortest path from one vertex to another with a greedy step-by-step algorithm. Starting at some vertex, go to its jump vertex. If that overshoots, go to its predecessor vertex instead. Iterate until you reached the target vertex. Formally:

Let and be in InnerVertices, with The shortest path from to is the unique sequence such that

Figure 7: An Example Path

The shortest path from to is the sequence

The labels of the closed out-neighborhood of the shortest path between two commitment vertices serve as a certificate that one event happened before the other. Slightly more precisely: the certificate is obtained by following the shortest path from the commitment vertex of the greater event to the commitment vertex of the lesser event, adding the one22For the final vertex, both out-neighbors are outside the path — add the predecessor vertex first and the jump vertex second. out-neighbor at each step that is not itself part of the path, and reversing the obtained sequence at the end. Formally:

Let and be in InnerVertices, with The prefix certificate of and is the sequence that

ContinuingNote how the same digest may appear multiple times in a prefix certificate. We could easily define a compressed version of prefix certificates that eliminates all but the first occurence of duplicate hashes, but verifying these becomes more difficult. Duplicates are rare enough (they only occur when the coordinate of a jump vertex decreases strictly, which only happens toward the “top-left of the graph”) that we opted for the simpler verification procedure over the slight, best-case certificate size reductions. the example from Figure 7:
The prefix certificate of and is the sequence of the digests of

Given a sequence of digests and a claim that is the prefix certificate of two commitment vertices with label and with label you can iteratively verify that claim. To verify, use the information in to compute the labels of the shortest path from to — successively and in reverse order. If the labels that you compute this way for and match and respectively, then you have successfully verified the prefix certificate. Assuming abscence of hash collisions, this proves that the sequence of all events up to event is a prefix of the sequence of all events up to event . Hence, in particular, event happened before event .

And that is how someone else can efficiently prove to you that some event happened before another. For the use-case of transparency logs, a logging authority would sign commitment vertices. Signed commitment vertices would take on the role of signed tree heads in that scenario.

For a detailed complexity analysis of the linking scheme that Reed employs, see the paper (Meyer, 2023aa).