Tezos context hashes

Status	Stable
Version	2021-03-22
Permalink	https://hackmd.io/@samoht/tezos-context-hash
Contact	https://github.com/tarides/tezos-context-hash/issues

This document provides a specification for computing the encoding of each kind of objects present in the Tezos context. Tezos then applies 32-bytes BLAKE2B-256 to compute context hashes from these encodings. Moreover, hashes are displayed using a base 58 representation and are prefixed by Co and suffixed by a 4-byte checksum. For instance, CoVGWKM7Ufu6dk74CEQz3MgffhUPFyeaMCD6eS3Q8o7mDis8n1Vi is a valid context hash for Tezos.

Notations:

• blake2b(s) is the BLAKE2B-256 hash of the string s.
• encode(v) is the raw sequence of bytes representing the encoding of v.
• hash(v) = blake2b(encode(v)) is the cryptographic hash of the object v.
• len(s) is the length of the string s (in bytes).

This documents uses a graphical notation to represent encodings:

• Let s an encoding and n = len(s) be its size in byte. This is represented as:

  n
  s

• Let s and t be 2 encodings and n = len(s) and m = len(t) be their respective sizes (in bytes). The concatenations and t is represented as:

  n	m
  s	t

Integers

The Tezos context has two modes for encoding integers:

• Fixed-length mode: the integer is encoded using 8 bytes, with big-endian conventions.
• Variable length mode: the integer is encoded in a variable length string, using unsigned LEB128 encoding. This encoding has the following good property: positive integers smaller than 128 have the same binary representation using both variable-size and fixed-size encoding.

Notations:

• we will denote the encoding of integers with 8 when fixed length encoding is used, and (LEB128) when the variable length encoding is used, and the size is not known in advance.
• We will write \x instead of the binary representation of the integer x, e.g. \32 instead of \000\000\000\000\000\000\000\032 for fixed-length encoding or \032 for variable-length encoding.

Example: encoding the integer 1298532.

• In fixed-length mode:

  8
  \000\000\000\000\000\019\208\100

• In variable-length mode:

  (LEB128)
  \228\160\079

Contents

Contents are raw sequences of bytes. Encoding contents is done by concatenating their length, encoded on 8 bytes, along with their value:

8	len(v)
\len(v)	v

Example: encoding the contents "delphi_007".

8	10
\000\000\000\000\000\000\000\010	delphi_007

Commits

Commits are immutable objects that contain metadata about changes done to the context, as well as pointers to previous commits and to the current Merkle trees root. These objects allow Tezos to track the history of all the changes done to the context.

Commits metadata are triplet: date

$\times$ author

$\times$ message. Date values are expressed in seconds and are stored as an int64. Author is usually the string "Tezos" but could change in the future. Message is a string containing information about the corresponding Tezos block such as its level, fit, priority and number of operations.

A commit metadata is encoded as follows:

8	8	len(author)	8	len(message)
\date	\len(author)	author	\len(message)	message

Example: encoding the commit metadata with date 1612521119 and message "msg".

8	8	5	8	3
\000\000\000\000\039\029\030\159	\000\000\000\000\000\000\000\005	Tezos	\000\000\000\000\000\000\000\03	msg

Commits are triplet: tree

$\times$ parents

$\times$ metadata. Tree is a hash pointing to the Merkle tree root. Parents is a lexicographically sorted list of commit hashes which are immediate predecessors of the current commit. A commit with

$k$ parent hashes

$p_1$, …,

$p_k$ is encoded as follows:

8	32	8	8	32	…	8	32	m
\32	tree	\k	\32	$p_1$	…	\32	$p_k$	encode(metadata)

where m = len(encode(metadata)).

Example: encoding the commit with tree hash <tree>, one parent <parent> and the metadata encoded by <m>.

8	32	8	8	32	len(m)
\000\000\000\000\000\000\000\032	<tree>	\000\000\000\000\000\000\001	\000\000\000\000\000\000\000\032	<parent>	<m>

Trees

The Tezos context contains Merkle trees. Contents encoding has already been explained in a previous section. This section presents the encoding for internal nodes of the tree. In Tezos, tree nodes are equivalent to a list of entries, pointing to the immediate children of the node.

A tree entry is a triplet: name

$\times$ kind

$\times$ hash. Names are strings, similar to file or directory names. Kind distinguishes between tree and contents and hash points to other data present in the context. Its encoding will depend on the internal representation of nodes.

The complexity of verifying (and computing) the hash of tree nodes depends on the number of its entries. To reduce that cost on large nodes, Tezos distinguishes between tree nodes holding at most 256 entries and tree nodes with more than 256 ones. The small nodes are represented as a list of entries and have a linear complexity, while large nodes are using an optimised representation – similar to inode tables implemented by filesystems – to handle large directories with a logarithmic complexity.

Until now in Tezos (i.e. Edo), all the directories have at most 256 entries and so do not use this optimised representation. This might change with sappling.

Tree nodes representations

The encoding of a tree node depends on the number n of entries present in that tree node.

• when n <= 256, Tezos encodes the entries as a list of bindings. See below for encoding of nodes.
• when n > 256, Tezos encodes the entries as an optimised tree of inodes. See below for encoding of inodes.

Nodes

Directories with at most 256 entries are encoded as a flat list of entries.

As already described above, a tree entry is a triplet: name

$\times$ kind

$\times$ hash. An entry is encoded as follow:

8	(LEB128)	len(name)	8	32
kind	\len(name)	name	\32	hash

kind is either:

• the string "\255\000\000\000\000\000\000\000" if the entry is pointing to a contents.
• the string "\000\000\000\000\000\000\000\000" if the entry is pointing to a node.

Example: encoding an entry whose name is "protocol", pointing to some contents with hash <hash>.

8	1	8	8	32
\255\000\000\000\000\000\000\000	\008	protocol	\000\000\000\000\000\000\000\032	<hash>

A node is a list of at most 256 entries, sorted by lexicographic order of names. A node with

$n$ entries,

$e_1$,

$e_2$, …

$e_n$ is encoded as follow when

$n\le 256$:

8	$n_1$	…	$n_n$
\n	encode(e_1)	…	encode(e_n)

where

$n_i$ = len(encode(

$e_i$)) and name(

$e_1$)

$<$ …

$<$ name(

$e_n$). Hence all names must be different.

Inodes

Because of storage optimisations implemented in Tezos, the encoding of directories with more than 256 entries is computed in a different way, and requires some transformations prior to its computation. In fact, inodes are themselves represented as trees. There are two kinds of inode objects: values (leafs) and trees.

Inode values

An inode value contains a flat list of tree entries.

As already described, a tree entry is a triplet: name

$\times$ kind

$\times$ hash. The encoding for inode entries is more compact than for node entries. For inodes, entries are encoded as follows:

(LEB128)	len(name)	1	32
\len(name)	name	kind	hash

where kind is \000 for nodes, and \001 for contents.

Example: encoding an entry whose name is "protocol" and pointing to some contents with hash <hash>.

1	8	1	32
\008	protocol	\001	<hash>

An inode value is a list of at most 32 entries, sorted by lexicographic order of names. A value with

$n$ entries

$e_1$,

$e_2$, …

$e_n$ is encoded as follows when

$n\le 32$:

1	1	$n_1$	…	$n_k$
\000	\n	encode(_1)	…	encode(e_k)

where

$n_i$ = len(encode

$e_i$)) and name(

$e_1$)

$\le$ …

$\le$ name(

$e_n$). Hence all names must be different.

Inode trees

Inode trees contain a list of inode pointers

An inode pointer is a pair: index

$\times$ hash. index is always less than 32. A pointer is encoded as follows:

1	32
index	hash

An inode tree is a triplet: depth

$\times$ len(entries)

$\times$ pointers. The number of pointers is always less than or equal to 32.

$pointers$ is a sparse list of pointers: every pointer in the list has a distinct index and the list is ordered by increasing indices, but some indices might be missing. Moreover, len(entries) aggregates the total number of entries that are reachable via the pointers. This information can for instance be used to decide whenever an inode value has to be converted into a inode tree (or the reverse) when a new entry is added (or removed) from the tree.

An inode tree with k pointers

$p_1$,

$p_2$, …

$p_k$ is encoded as follow:

1	(LEB128)	(LEB128)	1	33	..	33
\001	depth	len(children)	\k	$s_1$	…	$s_k$

where

$s_i$ = encode(

$p_i$).

Example: encoding an inode tree of depth 0, length 50000 and a list of pointers encoded by

$s_1$, …

$s_{32}$.

1	1	3	1	33	..	33
\001	\000	\160\194\030	\032	$s_1$	…	$s_{32}$

Constructing the internal tree

So far we have described only how to encode inodes but not how to construct them. This section explain how to do this and turn a list of entries into tree-like structure of inode trees and values.

The goal is thus to partition a list of entries of size greater than 256 into disjoint groups of entries of at most 32 elements, corresponding to inode values described above; and to create intermediate inode trees to efficiently dispatch names to the right leaf value using inode pointers.

Index function

The crux of the algorithm is to compute indices. Given an entry with name n, its index at depth d is defined as:

index(d, n) =
    ocaml_hash(d, n) mod 32

where ocaml_hash is a custom, non-crypto hash function defined by the the OCaml's runtime and based on MurmurHash3 and defined as follows:

mix(h: <uint32>, w: <uint32>) {
    w *= 0xcc9e2d51;
    w = w << 15 | w >> 17;
    w *= 0x1b873593;
    h ^= w;
    h = h << 13 | h >> 19;
    h = h * 5 + 0xe6546b64;
}

uint32 ocaml_hash(seed: <uint32>, s: <string>) {
    uint32 h = seed;
    for (i = 0; i < len(s); i = i + 4) {
        uint32 w;
        if big_endian_machine
            w = rev(s[i:i+4])
        else
            w = s[i:i+4];
        mix(h, w);
    }
    // At this point there might be up to 3 bytes left to read.
    if i <> len {
        // Bytes that are out of range should be set to \000.
        uint32 w = rev(s[i:i+4]);
        mix(h, w);
    }
    h ^= (uint32) len(s);
    h ^= h >> 16;
    h *= 0x85ebca6b;
    h ^= h >> 13;
    h *= 0xc2b2ae35;
    h ^= h >> 16;
    return h & 0x3FFFFFFFU;
}

Inode decomposition

First, let us define a few notations. Let

$\mathbf{\text{Value}}(X)$ denotes the inode value with entries

$X$. Let

$\mathbf{\text{Empty}}$ be the empty inode value, i.e.

$\mathbf{\text{Value}}(\{\})$. Let

$\mathbf{\text{Pointer}}(i\times h)$ be the inode pointer with index

$i$ and hash

$h$. And let

$\mathbf{\text{Tree}}(d\times n\times P)$ the inode tree with depth

$d$, number of children

$n$ and containing the list of pointers

$P$.

Let

$X$ be a set of inode entries

$e_1$,

$e_2$, …

$e_n$. Let's define the subset

$X_{d,j}$ of

$X$ as the set of elements with the same index

$j$ at depth

$d$:

$$X_{d,j}=\{e_i\in X|\mathbf{\text{index}}(d,\text{name}(e_i))=j\}$$

The following function partitions recursively a list of entries

$X$ into a collection of inode trees and values, starting at depth

$d$:

$$\begin{array}{rl}& \mathbf{\text{partition }}(d,X)=\\ & \text{if }len(X)=0\text{ then }\mathbf{\text{Empty}}\\ & \text{elif }len(X)\le 32\text{ then }\mathbf{\text{Value}}(X)\\ & \text{else }\\ & \text{ for }j=0..31\text{ do }\\ & t_j=\mathbf{\text{partition}}(d+1,X_{d,j})\\ & p_j=\mathbf{\text{Pointer}}(j\times hash(t_j))\\ & \text{ done }\\ & P=\{p_i|t_i\ne \mathbf{\text{Empty}}{\}}_{i\le 31}\\ & \mathbf{\text{Tree}}(depth\times len(X)\times P)\end{array}$$

$\mathbf{\text{Empty}}$ will never appear in the Tezos context directly, as the storage layer always automatically remove empty directories. But it is an useful concept to manipulate sparse lists of pointers.

The encoding of a tree node with

$n$ entries

$X$, when

$n>256$, is the encoding of the result of

$\mathbf{\text{partition}}(0,X)$:

• The encoding of
  $\mathbf{\text{Value}}(X)$ is defined in section about inode values.
• The encoding of
  $\mathbf{\text{Tree}}(d\times l\times P)$ is defined in section about inode trees.
• The encoding of
  $\mathbf{\text{Empty}}$ is the encoding of
  $\mathbf{\text{Value []}}$.

Inode search

$$\begin{array}{rl}& \mathbf{\text{find }}(n,\mathbf{\text{Value}}(X))=\\ & \text{ if }e\in X|name(e)=n\text{ then }\mathbf{\text{Some }}e\\ & \text{ else }\mathbf{\text{None}}\\ & \mathbf{\text{find }}(n,\mathbf{\text{Tree }}(depth\times \mathrm{\_}\times \bigcup p_i))=\\ & j=\mathbf{\text{index}}(depth,n)\\ & t_j=\mathbf{\text{read}}(p_j)\\ & \mathbf{\text{find }}(n,t_j)\end{array}$$

Inode add

$$\begin{array}{rl}& \mathbf{\text{add }}(d,e,\mathbf{\text{Value}}(X))=\\ & \text{ if }len(X)<32\text{ then }\mathbf{\text{Value}}(X\cup \{e\})\\ & \text{ else }\mathbf{\text{partition}}(d,X\cup \{e\})\\ & \mathbf{\text{add }}(d,e,\mathbf{\text{Tree }}(\mathrm{\_}\times len\times \bigcup p_i))=\\ & j=\mathbf{\text{index}}(d,name(e))\\ & t_j=\mathbf{\text{read}}(p_j)\\ & t_j^{\prime }=\mathbf{\text{add }}(d+1,e,t_j)\\ & p_j^{\prime }=\mathbf{\text{Pointer }}(j\times hash(t_j^{\prime }))\\ & P^{\prime }=\bigcup p_i\cup \{p_j^{\prime }\}-\{p_j\}\\ & \mathbf{\text{Tree }}(d\times (len+1)\times P^{\prime })\end{array}$$