Reed Specification

Aljoscha Meyer

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 $S LL S_{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.

Overview

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

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

1
let label_2_0 := hash(concat(label( $(1, 0)$ ), label( $2$ )))
2
let label_3_0 := hash(concat(label_2_0, label( $3$ )))
3
let label_3_1 := hash(concat(label( $(1, 0)$ ), label_3_0))
4
let label_6_1 := hash(concat(label_3_1, label( $(6, 0)$ )))
5
let label_7_0 := hash(concat(label_6_1, label( $7$ )))
6
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!

Specification

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 \leq x \leq l e n g t h,$ $y \in 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 \geq 2 .$ The jump vertexCompare Figure 3 (dark edges). of $(x, y)$ is the topmost vertex of event $x - 3^{y} .$

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 $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 $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ be in InnerVertices, with $x_{1} < x_{2} .$ The shortest path from $(x_{2}, y_{2})$ to $(x_{1}, y_{1})$ is the unique sequence $(v_{0}, \dots, v_{k})$ such that

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

Figure 7: An Example Path
The shortest path from $(20, 0)$ to $(6, 0)$ is the sequence $((20, 0), (19, 0), (18, 2), (9, 2), (9, 1), (6, 1), (6, 0)) .$

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 $(x_{1}, 0)$ and $(x_{2}, 0)$ be in InnerVertices, with $x_{1} < x_{2} .$ The prefix certificate of $(x_{1}, 0)$ and $(x_{2}, 0)$ is the sequence that

starts with the label of the jump vertex of $(x_{1}, 0)$ — or the hash of the empty string, if $x_{1} = 1,$ and which then
continues with exactly one digest for each of the elements of the shortest path from $(x_{2}, 0)$ to $(x_{1}, 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 $cer t = (d_{0}, d_{1}, \dots, l_{k})$ of digests and a claim that $cer t$ is the prefix certificate of two commitment vertices $(x_{1}, 0)$ with label $l ab e l_{1}$ and $(x_{2}, 0)$ with label $l ab e l_{2},$ you can iteratively verify that claim. To verify, use the information in $cer t$ to compute the labels of the shortest path from $(x_{2}, 0)$ to $(x_{1}, 0)$ — successively and in reverse order. If the labels that you compute this way for $(x_{1}, 0)$ and $(x_{2}, 0)$ match $l ab e l_{1}$ and $l ab e l_{2}$ 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 $x_{1}$ is a prefix of the sequence of all events up to event $x_{2}$ . Hence, in particular, event $x_{1}$ happened before event $x_{2}$ .

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

References

Laurie, B ; Messeri, E ; Stradling, R: RFC 9162: Certificate Transparency Version 2.0.

Meyer, Aljoscha: Better Prefix Authentication. In: arXiv preprint arXiv:2308.15058 (2023a)

Meyer, Aljoscha: SoK: Authenticated Prefix Relations–A Unified Perspective On Relative Time-Stamping and Append-Only Logs. In: arXiv preprint arXiv:2308.13836 (2023b)