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 $SLLS_{3}$ 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:

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.

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.

Each event has an associated commitment vertex.

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

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 $2$ and $8$.

`let label_2_0 := hash(concat(label($(1,0)$), label($2$)))let label_3_0 := hash(concat(label_2_0, label($3$)))let label_3_1 := hash(concat(label($(1,0)$), label_3_0))let label_6_1 := hash(concat(label_3_1, label($(6,0)$)))let label_7_0 := hash(concat(label_6_1, label($7$)))let label_8_0 := hash(concat(label_7_0, label($8$)))`

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 $2$ must have happened before event $8$. 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 $2_{64}−1,$ both inclusive. We number events starting at $1,$ because the math ends up much nicer that way.

TheCompare Figure 2. set InnerVertices is the set of all pairs $(x,y)$ such that $1≤x≤length,$ $y∈N_{0},$ and $3_{y}$ divides $x$ without remainder. We call $(x,0)$ the commitment vertexCompare Figure 4. of event $x$.

Let $(x,y)$ be in InnerVertices. The predecessor vertexCompare Figure 3 (light edges). of $(x,y)$ is the event $x$ if $y=0$, or the inner vertex $(x,y−1)$, otherwise.

Let $(x,y)$ be in InnerVertices such that $(x,y+1)$ is *not* in InnerVertices. Then we call $(x,y)$ the topmost vertex of event $x$.

Let $(x,y)$ be in InnerVertices, with $x≥2.$ The jump vertexCompare Figure 3 (dark edges). of $(x,y)$ is the topmost vertex of event $x−3_{y}.$

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

- the byte
`0x00`

, and - e.

The label of an inner vertex $v:=(x,y)$ is the hash of the concatenation of

- the byte
`0x01`

, - the label of the predecessor vertex of $v$,
- the label of the jump vertex of $v$ — or the hash of the empty string, if $v=(1,0),$
- the big-endian encoding of $x$Incorporating $x$ and $y$ 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 $y$ 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 $(x1 ,y1 )$ and $(x2 ,y2 )$ be in InnerVertices, with $x1 <x2 .$ The shortest path from $(x2 ,y2 )$ to $(x1 ,y1 )$ is the unique sequence $(v_{0},…,v_{k})$ such that

- $v_{0}=(x2 ,y1 ),$
- $v_{k}=(x1 ,y1 ),$ and
- for each $0≤i<k,$ we have that
- if the x-coordinate of the jump vertex of $v_{i}$ is strictly less than $x1 $, then $v_{i+1}$ is the predecessor vertex of $v_{i},$ else
- $v_{i+1}$ is the jump vertex of $v_{i}.$

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 $(x1 ,0)$ and $(x2 ,0)$ be in InnerVertices, with $x1 <x2 .$ The prefix certificate of $(x1 ,0)$ and $(x2 ,0)$ is the sequence that

- starts with the label of the jump vertex of $(x1 ,0)$ — or the hash of the empty string, if $x1 =1,$ and which then
- continues with exactly one digest for each of the elements of the shortest path from $(x2 ,0)$ to $(x1 ,0)$ in reverse order: either the digest of the jump vertex or the digest of the predecessor vertex, whichever vertex is
*not*the preceding vertex in the reversed shortest path (for the first vertex, always use the digest of the predecessor vertex).

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 $y$ 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 $(6,0)$ and $(20,0)$ is the sequence of the digests of $((5,0),6,(3,1),(9,0),(3,1),(18,1),19,20).$

Given a sequence $cert=(d_{0},d_{1},…,l_{k})$ of digests and a claim that $cert$ is the prefix certificate of two commitment vertices $(x1 ,0)$ with label $label1 $ and $(x2 ,0)$ with label $label2 ,$ you can iteratively verify that claim. To verify, use the information in $cert$ to compute the labels of the shortest path from $(x2 ,0)$ to $(x1 ,0)$ — successively and in reverse order. If the labels that you compute this way for $(x1 ,0)$ and $(x2 ,0)$ match $label1 $ and $label2 $ 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 $x1 $ is a prefix of the sequence of all events up to event $x2 $. Hence, in particular, event $x1 $ happened before event $x2 $.

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).