Reed Specification or Better Prefix Authentication (2023)

# Reed Specification Source: [https://worm-blossom.github.io/reed/](https://worm-blossom.github.io/reed/) [Prefix authentication schemes\(Meyer, 2023bb\)](https://worm-blossom.github.io/reed/assets/references/meyer2023sok.pdf)— 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](https://worm-blossom.github.io/reed/#name)is a lightweigh specification for implementing the[scheme\(Meyer, 2023aa\)](https://worm-blossom.github.io/reed/assets/references/meyer2023better.pdf), a scheme that produces shorter proofs than the traditional[certificate transparency logs\(Laurieet al\., 2021\)](https://www.rfc-editor.org/info/rfc9162)\. [Reed](https://worm-blossom.github.io/reed/#name)supersedes the earlier[Bamboo](https://github.com/AljoschaMeyer/bamboo)specification\.[Reed](https://worm-blossom.github.io/reed/#name)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](https://willowprotocol.org/), so[Reed](https://worm-blossom.github.io/reed/#name)sheds its data replication origins\. There will be graphs\. ## [Overview](https://worm-blossom.github.io/reed/#overview) How about a dense one\-paragraph summary, followed by a step\-by\-step explanation with pictures? [Reed](https://worm-blossom.github.io/reed/#name)is a[transitive prefix authentication scheme\(Meyer, 2023bb\)](https://worm-blossom.github.io/reed/assets/references/meyer2023sok.pdf): 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 acommitment vertexwhich 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](https://worm-blossom.github.io/reed/#name)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](https://worm-blossom.github.io/reed/#fig_events) 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](https://worm-blossom.github.io/reed/#fig_vertices) 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 itsout\-neighbors11This is a slight oversimplification,[Reed](https://worm-blossom.github.io/reed/#name)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](https://worm-blossom.github.io/reed/#fig_edges) 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](https://worm-blossom.github.io/reed/#fig_commitments) 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](https://worm-blossom.github.io/reed/#fig_path) The shortest path between the commitment vertices of eventsand\. 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 eventsand\. `1let label\_2\_0 := hash\(concat\(label\(\), label\(\)\)\)2let label\_3\_0 := hash\(concat\(label\_2\_0, label\(\)\)\)3let label\_3\_1 := hash\(concat\(label\(\), label\_3\_0\)\)4let label\_6\_1 := hash\(concat\(label\_3\_1, label\(\)\)\)5let label\_7\_0 := hash\(concat\(label\_6\_1, label\(\)\)\)6let 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, eventmust have happened before event\. Neat\! ## [Specification](https://worm-blossom.github.io/reed/#spec) We assume[hash](https://worm-blossom.github.io/reed/#hash)to be a secure hash function that maps arbitrary bytestrings to fixed\-width bytestrings\. We call an output of[hash](https://worm-blossom.github.io/reed/#hash)a[digest](https://worm-blossom.github.io/reed/#digest)\. WeCompare[Figure 1](https://worm-blossom.github.io/reed/#fig_events)\.define everything in terms of a sequence[events](https://worm-blossom.github.io/reed/#events)of[events](https://worm-blossom.github.io/reed/#event), where an[event](https://worm-blossom.github.io/reed/#event)is an arbitrary bytestring\. The sequence[events](https://worm-blossom.github.io/reed/#events)must have a[length](https://worm-blossom.github.io/reed/#length)between one andboth inclusive\. We number[events](https://worm-blossom.github.io/reed/#event)starting atbecause the math ends up much nicer that way\. TheCompare[Figure 2](https://worm-blossom.github.io/reed/#fig_vertices)\.set[InnerVertices](https://worm-blossom.github.io/reed/#InnerVertices)is the set of all pairssuch thatanddivideswithout remainder\. We callthe[commitment vertex](https://worm-blossom.github.io/reed/#commitment)Compare[Figure 4](https://worm-blossom.github.io/reed/#fig_commitments)\.of[event](https://worm-blossom.github.io/reed/#event)\. Letbe in[InnerVertices](https://worm-blossom.github.io/reed/#InnerVertices)\. The[predecessor vertex](https://worm-blossom.github.io/reed/#predecessor)Compare[Figure 3](https://worm-blossom.github.io/reed/#fig_edges)\(light edges\)\.ofis the[event](https://worm-blossom.github.io/reed/#event)if, or the inner vertex, otherwise\. Letbe in[InnerVertices](https://worm-blossom.github.io/reed/#InnerVertices)such thatis*not*in[InnerVertices](https://worm-blossom.github.io/reed/#InnerVertices)\. Then we callthe[topmost vertex](https://worm-blossom.github.io/reed/#topmost)of[event](https://worm-blossom.github.io/reed/#event)\. Letbe in[InnerVertices](https://worm-blossom.github.io/reed/#InnerVertices), withThe[jump vertex](https://worm-blossom.github.io/reed/#jump)Compare[Figure 3](https://worm-blossom.github.io/reed/#fig_edges)\(dark edges\)\.ofis the[topmost vertex](https://worm-blossom.github.io/reed/#topmost)of[event](https://worm-blossom.github.io/reed/#event) [Figure 6](https://worm-blossom.github.io/reed/#fig_slls) A graph depicting the first few vertices for a long sequence of[events](https://worm-blossom.github.io/reed/#events)\. The light, vertical edges connect each vertex to its[predecessor vertex](https://worm-blossom.github.io/reed/#predecessor), the darker edges connect each vertex to its[jump vertex](https://worm-blossom.github.io/reed/#jump)\. The[label](https://worm-blossom.github.io/reed/#label)of an[event](https://worm-blossom.github.io/reed/#event)[e](https://worm-blossom.github.io/reed/#label_event)is the[hash](https://worm-blossom.github.io/reed/#hash)of the concatenation of - the byte`0x00`, and - [e](https://worm-blossom.github.io/reed/#label_event)\. The[label](https://worm-blossom.github.io/reed/#label)of an inner vertexis the[hash](https://worm-blossom.github.io/reed/#hash)of the concatenation of - the byte`0x01`, - the[label](https://worm-blossom.github.io/reed/#label)of the[predecessor vertex](https://worm-blossom.github.io/reed/#predecessor)of, - the[label](https://worm-blossom.github.io/reed/#label)of the[jump vertex](https://worm-blossom.github.io/reed/#jump)of— or the[hash](https://worm-blossom.github.io/reed/#hash)of the empty string, if - the big\-endian encoding ofIncorporatingandin 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](https://worm-blossom.github.io/reed/#predecessor)and[jump vertex](https://worm-blossom.github.io/reed/#jump)\.as an unsigned 64\-bit integer, and - the encoding ofas 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](https://worm-blossom.github.io/reed/#jump)\. If that overshoots, go to its[predecessor vertex](https://worm-blossom.github.io/reed/#predecessor)instead\. Iterate until you reached the target vertex\. Formally: Letandbe in[InnerVertices](https://worm-blossom.github.io/reed/#InnerVertices), withThe[shortest path](https://worm-blossom.github.io/reed/#shortest)fromtois the unique sequencesuch that - and - for eachwe have that- if the x\-coordinate of the[jump vertex](https://worm-blossom.github.io/reed/#jump)ofis strictly less than, thenis the[predecessor vertex](https://worm-blossom.github.io/reed/#predecessor)ofelse - is the[jump vertex](https://worm-blossom.github.io/reed/#jump)of [Figure 7](https://worm-blossom.github.io/reed/#fig_large_path): An Example Path The[shortest path](https://worm-blossom.github.io/reed/#shortest)fromtois the sequence The labels of the closed out\-neighborhood of the[shortest path](https://worm-blossom.github.io/reed/#shortest)between two[commitment vertices](https://worm-blossom.github.io/reed/#commitment)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](https://worm-blossom.github.io/reed/#commitment)of the greater event to the[commitment vertex](https://worm-blossom.github.io/reed/#commitment)of the lesser event, adding theone22For the final vertex, both out\-neighbors are outside the path — add the[predecessor vertex](https://worm-blossom.github.io/reed/#predecessor)first and the[jump vertex](https://worm-blossom.github.io/reed/#jump)second\.out\-neighbor at each step that is not itself part of the path, and reversing the obtained sequence at the end\. Formally: Letandbe in[InnerVertices](https://worm-blossom.github.io/reed/#InnerVertices), withThe[prefix certificate](https://worm-blossom.github.io/reed/#certificate)ofandis the sequence that - starts with the[label](https://worm-blossom.github.io/reed/#label)of the[jump vertex](https://worm-blossom.github.io/reed/#jump)of— or the[hash](https://worm-blossom.github.io/reed/#hash)of the empty string, ifand which then - continues with exactly one[digest](https://worm-blossom.github.io/reed/#digest)for each of the elements of the[shortest path](https://worm-blossom.github.io/reed/#shortest)fromtoin reverse order: either the[digest](https://worm-blossom.github.io/reed/#digest)of the[jump vertex](https://worm-blossom.github.io/reed/#jump)or the[digest](https://worm-blossom.github.io/reed/#digest)of the[predecessor vertex](https://worm-blossom.github.io/reed/#predecessor), whichever vertex is*not*the preceding vertex in the reversed[shortest path](https://worm-blossom.github.io/reed/#shortest)\(for the first vertex, always use the[digest](https://worm-blossom.github.io/reed/#digest)of the[predecessor vertex](https://worm-blossom.github.io/reed/#predecessor)\)\. ContinuingNote how the same[digest](https://worm-blossom.github.io/reed/#digest)may appear multiple times in a[prefix certificate](https://worm-blossom.github.io/reed/#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 thecoordinate of a[jump vertex](https://worm-blossom.github.io/reed/#jump)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](https://worm-blossom.github.io/reed/#fig_large_path): The[prefix certificate](https://worm-blossom.github.io/reed/#certificate)ofandis the sequence of the[digests](https://worm-blossom.github.io/reed/#digest)of Given a sequenceof[digests](https://worm-blossom.github.io/reed/#digest)and a claim thatis the[prefix certificate](https://worm-blossom.github.io/reed/#certificate)of two[commitment vertices](https://worm-blossom.github.io/reed/#commitment)with[label](https://worm-blossom.github.io/reed/#label)andwith[label](https://worm-blossom.github.io/reed/#label)you can iteratively verify that claim\. To verify, use the information into compute the labels of the[shortest path](https://worm-blossom.github.io/reed/#shortest)fromto— successively and in reverse order\. If the labels that you compute this way forandmatchandrespectively, then you have successfully verified the[prefix certificate](https://worm-blossom.github.io/reed/#certificate)\. Assuming abscence of hash collisions, this proves that the sequence of all events up to[event](https://worm-blossom.github.io/reed/#event)is a prefix of the sequence of all events up to[event](https://worm-blossom.github.io/reed/#event)\. Hence, in particular,[event](https://worm-blossom.github.io/reed/#event)happened before[event](https://worm-blossom.github.io/reed/#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](https://worm-blossom.github.io/reed/#commitment)\. Signed[commitment vertices](https://worm-blossom.github.io/reed/#commitment)would take on the role of[signed tree heads](https://www.rfc-editor.org/rfc/rfc9162.html#name-signed-tree-head-sth)in that scenario\. For a detailed complexity analysis of the linking scheme that[Reed](https://worm-blossom.github.io/reed/#name)employs, see the[paper\(Meyer, 2023aa\)](https://worm-blossom.github.io/reed/assets/references/meyer2023better.pdf)\. ## [References](https://worm-blossom.github.io/reed/#bibliography)