# package octez-libs

`include module type of struct include Proof_types end`

Tezos-specific proof types, as opposed to proofs provided by Irmin. These types are used only by the light mode and it is recommended to avoid extending their usage: only the light mode should use them.

Whether an RPC caller requests an entirely shallow Merkle tree (`Hole`

) or whether the returned tree should contain data at the given key (`Raw_context`

)

`type raw_context = Proof_types.raw_context = `

`| Key of Tezos_base.TzPervasives.Bytes.t`

(*A leaf, containing a value

*)`| Dir of raw_context Tezos_base.TzPervasives.String.Map.t`

(*A directory, mapping keys to nested

*)`raw_context`

s`| Cut`

(*An omitted piece, because it is too deep compared to the maximum depth requested in the /chains/<chain_id>/blocks/<block_id/context/raw/bytes RPC

*)

The low-level storage exposed as a tree

`type merkle_hash_kind = Proof_types.merkle_hash_kind = `

The kind of a `merkle_node`

`type merkle_node = Proof_types.merkle_node = `

`| Hash of merkle_hash_kind * string`

(*A shallow node: just a hash

*)`| Data of raw_context`

(*A full-fledged node containing actual data

*)`| Continue of merkle_tree`

(*An edge to a more nested tree

*)

A node in a `merkle_tree`

`and merkle_tree = merkle_node Tezos_base.TzPervasives.String.Map.t`

The type of Merkle tree used by the light mode

`val pp_raw_context : Format.formatter -> raw_context -> unit`

Proofs are compact representations of trees which can be shared between peers.

This is expected to be used as follows:

- A first peer runs a function
`f`

over a tree`t`

. While performing this computation, it records: the hash of`t`

(called`before`

below), the hash of`f t`

(called`after`

below) and a subset of`t`

which is needed to replay`f`

without any access to the first peer's storage. Once done, all these informations are packed into a proof of type`t`

that is sent to the second peer.

- The second peer generates an initial tree
`t'`

from`p`

and computes`f t'`

. Once done, it compares`t'`

's hash and`f t'`

's hash to`before`

and`after`

. If they match, they know that the result state`f t'`

is a valid context state, without having to have access to the full storage of the first peer.

`type hash = Tezos_base.TzPervasives.Context_hash.t`

The type for hashes.

The type for (internal) inode proofs.

These proofs encode large directories into a tree-like structure. This reflects irmin-pack's way of representing nodes and computing hashes (tree-like representations for nodes scales better than flat representations).

`length`

is the total number of entries in the children of the inode. It's the size of the "flattened" version of that inode. `length`

can be used to prove the correctness of operations such `Tree.length`

and `Tree.list ~offset ~length`

in an efficient way.

In proofs with `version.is_binary = false`

, an inode at depth 0 has a `length`

of at least `257`

. Below that threshold a `Node`

tag is used in `tree`

. That threshold is `3`

when `version.is_binary = true`

.

`proofs`

contains the children proofs. It is a sparse list of `'a`

values. These values are associated to their index in the list, and the list is kept sorted in increasing order of indices. `'a`

can be a concrete proof or a hash of that proof.

In proofs with `version.is_binary = true`

, inodes have at most 2 proofs (indexed 0 or 1).

In proofs with `version.is_binary = false`

, inodes have at most 32 proofs (indexed from 0 to 31).

`type 'a inode_extender = 'a Proof_types.inode_extender = {`

`length : int;`

`segment : index list;`

`proof : 'a;`

`}`

The type for inode extenders.

An extender is a compact representation of a sequence of `inode`

which contain only one child. As for inodes, The `'a`

parameter can be a concrete proof or a hash of that proof.

If an inode proof contains singleton children `i_0, ..., i_n`

such as: `{length=l; proofs = [ (i_0, {proofs = ... { proofs = [ (i_n, p) ] }})]}`

, then it is compressed into the inode extender `{length=l; segment = [i_0;..;i_n]; proof=p}`

sharing the same lenght `l`

and final proof `p`

.

`type tree = Proof_types.tree = `

`| Value of value`

`| Blinded_value of hash`

`| Node of (step * tree) list`

`| Blinded_node of hash`

`| Inode of inode_tree inode`

`| Extender of inode_tree inode_extender`

The type for compressed and partial Merkle tree proofs.

Tree proofs do not provide any guarantee with the ordering of computations. For instance, if two effects commute, they won't be distinguishable by this kind of proofs.

`Value v`

proves that a value `v`

exists in the store.

`Blinded_value h`

proves a value with hash `h`

exists in the store.

`Node ls`

proves that a a "flat" node containing the list of files `ls`

exists in the store.

In proofs with `version.is_binary = true`

, the length of `ls`

is at most 2.

In proofs with `version.is_binary = false`

, the length of `ls`

is at most 256.

`Blinded_node h`

proves that a node with hash `h`

exists in the store.

`Inode i`

proves that an inode `i`

exists in the store.

`Extender e`

proves that an inode extender `e`

exist in the store.

`and inode_tree = Proof_types.inode_tree = `

`| Blinded_inode of hash`

`| Inode_values of (step * tree) list`

`| Inode_tree of inode_tree inode`

`| Inode_extender of inode_tree inode_extender`

The type for inode trees. It is a subset of `tree`

, limited to nodes.

`Blinded_inode h`

proves that an inode with hash `h`

exists in the store.

`Inode_values ls`

is similar to trees' `Node`

.

`Inode_tree i`

is similar to tree's `Inode`

.

`Inode_extender e`

is similar to trees' `Extender`

.

`module Stream = Proof_types.Stream`

`type stream = Stream.t`

The type for proofs of kind `'a`

.

A proof `p`

proves that the state advanced from `before p`

to `after p`

. `state p`

's hash is `before p`

, and `state p`

contains the minimal information for the computation to reach `after p`

.

`version p`

is the proof version, it packs several informations.

`is_stream`

discriminates between the stream proofs and the tree proofs.

`is_binary`

discriminates between proofs emitted from `Tezos_context(_memory).Context_binary`

and `Tezos_context(_memory).Context`

.

It will also help discriminate between the data encoding techniques used.

The version is meant to be decoded and encoded using the `Tezos_context_helpers.Context.decode_proof_version`

and `Tezos_context_helpers.Context.encode_proof_version`

.

`module Internal_for_tests = Proof_types.Internal_for_tests`