# package octez-libs

## Cryptography for the Data Availability Layer

The Data Availability Layer (DAL) reduces the storage strain on the blockchain by only storing on-chain constant-size cryptographic `commitment`

s to arbitrary data blobs called `slot`

s. The slots themselves are stored off-chain and are made available by the DAL.

A slot is encoded with some redundancy using a so-called MDS (Maximum Distance Separable) code. The resulting encoded slot is partitioned into `shard`

s, allowing retrieval of the slot with any subset of `{!field:parameters.number_of_shards}/{!field:parameters.redundancy_factor}`

out of `{!field:parameters.number_of_shards}`

shards. By doing so, we can guarantee high data availability provided a certain fraction of the DAL nodes is storing and supplying the data. This fraction can be made as small as desired at the expense of a higher data redundancy `parameters.redundancy_factor`

. MDS codes have no unnecessary redundancy.

One can verify in constant time that the correct shard was retrieved using a constant-sized KZG proof `shard_proof`

(see function `verifyEval`

in section 3.3) and the slot commitment.

A `slot`

is partioned into `{!field:parameters.slot_size}/{!field:parameters.page_size}`

segments called `Verifier.page`

s of size `parameters.page_size`

. One can also verify in constant time that the correct page was retrieved using a KZG proof `page_proof`

and the slot commitment.

A challenge is to keep the proving time for the `shard_proof`

s almost proportional to the length `n`

of the slot encoded with the MDS code: we've chosen and implemented a technique to produce the proofs in time `O(n log n)`

(see Fast amortized KZG proofs).

Initial values for the parameters of the DAL cryptographic primitives. It used to build a value of type `t`

.

Encapsulates parameters required to use the cryptographic primitives exported by this module. A value of type `t`

contains both initial `parameters`

and computed values depending on it.

Because of the shell/protocol separation, cryptographic primitives need to be splitted. An interface, called the `Verifier`

aims to be provided for the economic protocol. The other interface, called the `Builder`

is for the shell.

A `Verifier`

, as hinted by the name, mainly needs to check proofs:

1. A proof that a commitment is valid

2. A proof that a page is valid

A technicality is that the economic protocol is able to configure those cryptographic primitives via several constants. Also, an SRS (aka trusted setup) is required.

It is the responsibility of the shell and the protocol to ensure that both the `Verifier`

and the `Builder`

are instantiated with the same parameters and use the same trusted setup.

`Failed_to_load_trusted_setup`

, thrown by `Config.init_dal`

.

`type Tezos_error_monad.Error_monad.error += `

`| Invalid_precomputation_hash of (string, string) error_container`

`Invalid_precomputation_hash`

, thrown by `load_precompute_shards_proofs`

.

```
module Verifier :
Cryptobox_intf.VERIFIER
with type t = t
and type commitment = commitment
and type commitment_proof = commitment_proof
and type page_proof = page_proof
and type ('a, 'b) error_container = ('a, 'b) error_container
```

```
include Cryptobox_intf.VERIFIER
with type t := t
and type parameters :=
Tezos_crypto_dal_octez_dal_config.Dal_config.parameters
and type commitment := commitment
and type commitment_proof := commitment_proof
and type page_proof := page_proof
and type ('a, 'b) error_container := ('a, 'b) error_container
```

```
val parameters_encoding :
Tezos_crypto_dal_octez_dal_config.Dal_config.parameters Data_encoding.t
```

An encoding for values of type `parameters`

.

```
val make :
Tezos_crypto_dal_octez_dal_config.Dal_config.parameters ->
(t, [> `Fail of string ]) result
```

`make`

precomputes the set of values needed by the cryptographic primitives defined in this module and stores them in a value of type `t`

`val parameters : t -> Tezos_crypto_dal_octez_dal_config.Dal_config.parameters`

`parameters t`

returns the parameters given when `t`

was initialised with the function `make`

```
module Commitment_proof :
Kzg.Interfaces.DegreeCheck_proof with type t := commitment_proof
```

`val verify_commitment : t -> commitment -> commitment_proof -> bool`

`verify_commitment t commitment proof`

returns `true`

if and only if the size of the data committed via `commitment`

does not exceed the `slot_size`

declared in `t`

.

The verification time is constant.

The original slot can be split into a list of pages of fixed size. This size is given by the parameter `page_size`

given to the function `make`

.

`val page_proof_encoding : page_proof Data_encoding.t`

An encoding for the proof of a page.

```
val pages_per_slot :
Tezos_crypto_dal_octez_dal_config.Dal_config.parameters ->
int
```

`pages_per_slot t`

returns the number of expected pages per slot.

```
val verify_page :
t ->
commitment ->
page_index:int ->
page ->
page_proof ->
(unit,
[> `Invalid_degree_strictly_less_than_expected of
(int, int) error_container
| `Invalid_page
| `Page_length_mismatch
| `Page_index_out_of_range ])
Result.t
```

`verify_page t commitment ~page_index page proof`

returns `Ok ()`

if the `proof`

certifies that the `page`

is the `page_index`

-th page of the slot with the given `commitment`

.

Fails with:

`Error `Invalid_page`

if the verification Fails`Error `Invalid_degree_strictly_less_than_expected _`

if the SRS contained in`t`

is too small to proceed with the verification`Error `Page_length_mismatch`

if the page is not of the expected length`page_size`

given for the initialisation of`t`

`Error `Page_index_out_of_range`

if`page_index`

is out of the range`0, slot_size/page_size - 1`

where`slot_size`

and`page_size`

are given for the initialisation of`t`

Ensures:

`verify_page t commitment ~page_index page proof = Ok ()`

if and only if`page = Bytes.sub slot (page_index * t.page_size) t.page_size`

),`proof = prove_page t polynomial page_index`

,`p = polynomial_from_slot t slot`

, and`commitment = commit t p`

.

The primitives exposed in this modules require some preprocessing. This preprocessing generates data from an unknown secret. For the security of those primitives, it is important that the secret is unknown.

`module Commitment : sig ... end`

A polynomial is another representation for a slot. One advantage of this representation is that a commitment can be computed from a polynomial. A commitment has nice properties:

1. A commitment ensures that the size of the `slot`

has a bounded size (typically `slot_size`

).

2. A commitment can be used to verify that a page of fixed size (typically `page_size`

) is part of the original slot.

`val polynomial_degree : polynomial -> int`

`polynomial_degree polynomial`

returns the degree of the polynomial.

`val polynomial_evaluate : polynomial -> scalar -> scalar`

`polynomial_evaluate polynomial x`

evaluates `polynomial(x)`

.

```
val polynomial_from_slot :
t ->
slot ->
(polynomial, [> `Slot_wrong_size of string ]) Result.t
```

`polynomial_from_slot t slot`

returns a polynomial from the a slot `slot`

.

Requires:

`Bytes.length slot`

is the slot size declared in`t`

.

Ensures:

- For any
`slot`

satisfying`Bytes.length slot`

is equal to the declared slot size of`t`

,`polynomial_to_slot (polynomial_from_slot slot) = slot`

.

Fails with ``Slot_wrong_size`

when the slot size is not equal to the value slot size declared in `t`

.

Note:

`polynomial_from_slot`

is injective.

`val polynomial_to_slot : t -> polynomial -> slot`

`polynomial_to_slot t polynomial`

returns a slot from a `polynomial`

.

Ensures:

- For any
`slot`

satisfying`Bytes.length slot = parameters.slot_size`

,`polynomial_to_slot (polynomial_from_slot slot) = slot`

.

```
val commit :
t ->
polynomial ->
(commitment,
[> `Invalid_degree_strictly_less_than_expected of
(int, int) error_container
| `Prover_SRS_not_loaded ])
Result.t
```

`commit t polynomial`

returns the commitment associated to a polynomial `p`

.

Fails with ``Invalid_degree_strictly_less_than_expected _`

if the degree of `p`

exceeds the SRS size.

Fails with ``Prover_SRS_not_loaded`

if the prover’s SRS is not loaded (ie: `init_dal_verifier`

has been used to load the SRS).

```
val pp_commit_error :
Format.formatter ->
[< `Invalid_degree_strictly_less_than_expected of (int, int) error_container
| `Prover_SRS_not_loaded ] ->
unit
```

`pp_commit_error fmt error`

pretty-prints the error returned by `commit`

.

```
val string_of_commit_error :
[< `Invalid_degree_strictly_less_than_expected of (int, int) error_container
| `Prover_SRS_not_loaded ] ->
string
```

`string_of_commit_error error`

returns an error string message for `error`

.

A portion of the data represented by a polynomial.

Encoding of a share.

A shard is share with its index (see `shards_from_polynomial`

).

`val shard_encoding : shard Data_encoding.t`

An encoding of a share.

`encoded_share_size t`

returns the size of a share in byte depending on `t`

```
val polynomial_from_shards :
t ->
shard Seq.t ->
(polynomial,
[> `Not_enough_shards of string
| `Shard_index_out_of_range of string
| `Invalid_shard_length of string ])
result
```

`polynomial_from_shards t shards`

computes the original polynomial from `shards`

. The proportion of shards needed is `1`

over `redundancy_factor`

the total number of shards declared in `t`

.

Requires:

`Seq.length shards >= number_of_shards / redundancy_factor`

(where`number_of_shards`

and`redundancy_factor`

are found in`t`

) .

Ensures:

- For any
`p`

, let`shards = shards_from_polynomial p`

, for any subset S of shards of`polynomial_length / shard_length`

elements,`polynomial_from_shards S = p`

. Here,`polynomial_length`

and`shard_length`

are parameters declared in`t`

.

Fails with:

`Error (`Not_enough_shards msg)`

if there aren't at least`number_of_shards / redundancy_factor`

shards (where these two parameters are found in`t`

)`Error (`Shard_index_out_of_range msg)`

if one shard index is not within the range`0, number_of_shards - 1`

(where`number_of_shards`

is declared in`t`

).`Error (`Invalid_shard_length msg)`

if one shard is not of the expected length.

`val shards_from_polynomial : t -> polynomial -> shard Seq.t`

`shards_from_polynomial t polynomial`

computes all the shards encoding the original `polynomial`

.

Ensures:

- For any
`p`

, let`shards = shards_from_polynomial p`

, for any subset S of shards of`polynomial_length / shard_length`

elements,`polynomial_from_shards S = p`

. Here,`polynomial_length`

and`shard_length`

are parameters declared in`t`

. The shards in the returned sequence have increasing indexes.

`val shard_proof_encoding : shard_proof Data_encoding.t`

An encoding of a shard proof.

```
val verify_shard :
t ->
commitment ->
shard ->
shard_proof ->
(unit,
[> `Invalid_degree_strictly_less_than_expected of
(int, int) error_container
| `Invalid_shard
| `Shard_length_mismatch
| `Shard_index_out_of_range of string ])
Result.t
```

`verify_shard t commitment shard proof`

returns `Ok ()`

if `shard`

is an element of `shards_from_polynomial p`

where `commitment = commit t p`

for some polynomial `p`

.

The verification time is constant.

Requires:

- The SRS (structured reference string) contained in
`t`

should be the same as the one used to produce the`commitment`

and`proof`

.

Fails with:

`Error `Invalid_shard`

if the verification fails`Error `Invalid_degree_strictly_less_than_expected _`

if the SRS contained in`t`

is too small to proceed with the verification`Error `Shard_length_mismatch`

if the shard is not of the expected length`shard_length`

given for the initialisation of`t`

`Error (`Shard_index_out_of_range msg)`

if the shard index is not within the range`0, number_of_shards - 1`

(where`number_of_shards`

is found in`t`

).

Ensures:

`verify_shard t commitment shard proof = Ok ()`

if and only if`Array.mem shard (shards_from_polynomial t polynomial`

),`precomputation = precompute_shards_proofs t`

,`proof = (prove_shards t ~precomputation ~polynomial).(shard.index)`

, and`commitment = commit t p`

.

```
val verify_shard_multi :
t ->
commitment ->
shard list ->
shard_proof list ->
(unit,
[> `Invalid_degree_strictly_less_than_expected of
(int, int) error_container
| `Invalid_shard
| `Shard_length_mismatch
| `Shard_index_out_of_range of string ])
Result.t
```

Batched version of verify_shard, for better verifier performance. `verify_shard_multi t commitment shard_list proof_list`

returns `Ok ()`

if for all i List.nth i `shard`

is an element of `shards_from_polynomial p`

where `commitment = commit t p`

for some polynomial `p`

, and the proofs are correctly generated.

The verification time smaller than calling List.lenght shard_list times the verify_shard function.

Requires:

- The SRS (structured reference string) contained in
`t`

should be the same as the one used to produce the`commitment`

and`proof`

.

Fails with:

`Error `Invalid_shard`

if the verification fails`Error `Invalid_degree_strictly_less_than_expected _`

if the SRS contained in`t`

is too small to proceed with the verification`Error `Shard_length_mismatch`

if one of the shard is not of the expected length`shard_length`

given for the initialisation of`t`

`Error (`Shard_index_out_of_range msg)`

if one of the shard index is not within the range`0, number_of_shards - 1`

(where`number_of_shards`

is found in`t`

).

Ensures:

`verify_shard_multi t commitment shard_list proof_list = Ok ()`

if and only if`Array.mem (List.nth i shard_list) (shards_from_polynomial t polynomial`

),`precomputation = precompute_shards_proofs t`

,`List.nth i proof_list = (prove_shards t ~precomputation ~polynomial). (List. nth i (shard_list.index))`

, for all i and`commitment = commit t p`

.

```
val prove_commitment :
t ->
polynomial ->
(commitment_proof,
[> `Invalid_degree_strictly_less_than_expected of
(int, int) error_container
| `Prover_SRS_not_loaded ])
Result.t
```

`prove_commitment t polynomial`

produces a proof that the slot represented by `polynomial`

has its size bounded by `slot_size`

declared in `t`

.

Fails with:

`Error `Invalid_degree_strictly_less_than_expected _`

if the SRS contained in`t`

is too small to produce the proof`Error `Prover_SRS_not_loaded`

if the prover’s SRS is not loaded (ie:`init_dal_verifier`

has been used to load the SRS).

```
val prove_page :
t ->
polynomial ->
int ->
(page_proof,
[> `Invalid_degree_strictly_less_than_expected of
(int, int) error_container
| `Page_index_out_of_range
| `Prover_SRS_not_loaded ])
Result.t
```

`prove_page t polynomial n`

produces a proof for the `n`

-th page of the `slot`

such that `polynomial = polynomial_from_slot t slot`

. This proof can be used to verify given a commitment to a slot that a byte sequence is indeed the `n`

-th page of the slot (see Ensures section below).

Fails with:

`Error `Invalid_degree_strictly_less_than_expected _`

if the SRS contained in`t`

is too small to produce the proof`Error (`Page_index_out_of_range msg)`

if the page index is not within the range`0, slot_size/page_size - 1`

(where`slot_size`

and`page_size`

are found in`t`

).`Error `Prover_SRS_not_loaded`

if the SRS has been loaded with`init_dal_verifier`

.

Ensures:

`verify_page t commitment ~page_index page page_proof = Ok ()`

if and only if`page = Bytes.sub slot (page_index * t.page_size) t.page_size`

),`page_proof = prove_page t polynomial page_index`

,`p = polynomial_from_slot t slot`

, and`commitment = commit t p`

.

```
val shards_proofs_precomputation_encoding :
shards_proofs_precomputation Data_encoding.t
```

```
val precompute_shards_proofs :
t ->
(shards_proofs_precomputation,
[> `Invalid_degree_strictly_less_than_expected of
(int, int) error_container ])
Result.t
```

`precomputation_shard_proofs t`

returns the precomputation used to produce shard proofs.

```
val save_precompute_shards_proofs :
shards_proofs_precomputation ->
filename:string ->
unit Tezos_error_monad.Error_monad.tzresult Lwt.t
```

`save_precompute_shards_proofs precomputation ~filename`

saves the given `precomputation`

to disk with the given `filename`

.

```
val load_precompute_shards_proofs :
hash:Tezos_crypto.Blake2B.t option ->
filename:string ->
unit ->
shards_proofs_precomputation Tezos_error_monad.Error_monad.tzresult Lwt.t
```

`load_precompute_shards_proofs ~hash ~filename ()`

loads the precomputation from disk from the given `filename`

. If `hash`

is not `None`

, an integrity check of the retrieved precomputation is performed.

Returns the error `Invalid_precomputation_hash`

if the integrity check fails.

```
val hash_precomputation :
shards_proofs_precomputation ->
Tezos_crypto.Blake2B.t
```

`hash_precomputation precomputation`

returns the `Tezos_crypto.Blake2B.t`

hash of the `Data_encoding.t`

value of `precomputation`

.

```
val prove_shards :
t ->
precomputation:shards_proofs_precomputation ->
polynomial:polynomial ->
shard_proof array
```

`prove_shards t ~precomputation ~polynomial`

produces `number_of_shards`

proofs `(π_0, ..., π_{number_of_shards - 1})`

for the elements of `polynomial_from_shards polynomial`

(where `number_of_shards`

is declared in `t`

) using the `precomputation`

.

Requires:

`polynomial = polynomial_from_slot t s`

for some slot`s`

and the same value`t`

used in`prove_shards`

. Since the caller of`prove_shards`

knows`polynomial`

, it is its responsibility to enforce this requirement.`precomputation = precompute_shards_proofs t`

with the same value`t`

used in`prove_shards`

. There is no way for this function to check that the`precomputation`

is correct since it doesn't compute it.

Ensures:

`verify_shard t commitment shard proof = Ok ()`

if and only if`Array.mem shard (shards_from_polynomial t polynomial`

)`proof = (prove_shards t polynomial).(shard.index)`

, and`commitment = commit t polynomial`

.

`module Internal_for_tests : sig ... end`

`module Config : sig ... end`

node parameters for the DAL.