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 commitments to arbitrary data blobs called slots. 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 shards, allowing retrieval of the slot with any subset of {!recfield:parameters.number_of_shards}/{!recfield:parameters.redundancy_factor} out of {!recfield: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 {!recfield:parameters.slot_size}/{!recfield:parameters.page_size} segments called Verifier.pages 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_proofs 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).

type parameters = {

redundancy_factor : int;
page_size : int;
slot_size : int;
number_of_shards : int;

}

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

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.

type commitment

type commitment_proof

type page_proof

type ('a, 'b) error_container = {

given : 'a;
expected : 'b;

}

type Tezos_error_monad.Error_monad.error +=

| Dal_initialisation_twice

Dal_initialisation_twice, thrown by Config.init_dal.

type Tezos_error_monad.Error_monad.error +=

| Failed_to_load_trusted_setup of string

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 parameters = 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

include Cryptobox_intf.VERIFIER
  with type t := t
   and type parameters := 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 : parameters Data_encoding.t

An encoding for values of type parameters.

val make : parameters -> (t, [> `Fail of string ]) Stdlib.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 -> parameters

parameters t returns the parameters given when t was initialised with the function make

module Commitment_proof : 
  Cryptobox_intf.COMMITMENT_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.

type page = bytes

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 : 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 ])
    Stdlib.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.

type initialisation_parameters

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

type slot = bytes

A slot is a byte sequence corresponding to some data.

type scalar

The finited field used by the polynomial.

type polynomial

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

val pp_commit_error : 
  Stdlib.Format.formatter ->
  [< `Invalid_degree_strictly_less_than_expected of (int, int) error_container ] ->
  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 ] ->
  string

string_of_commit_error error returns an error string message for error.

type share

A portion of the data represented by a polynomial.

val share_encoding : share Data_encoding.t

Encoding of a share.

type shard = {

index : int;
share : share;

}

A shard is share with its index (see shards_from_polynomial).

val shard_encoding : shard Data_encoding.t

An encoding of a share.

val encoded_share_size : t -> int

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

val polynomial_from_shards : 
  t ->
  shard Stdlib.Seq.t ->
  (polynomial,
    [> `Not_enough_shards of string
    | `Shard_index_out_of_range of string
    | `Invalid_shard_length of string ])
    Stdlib.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 Stdlib.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.

type shard_proof

A proof that a shard belongs to some commitment.

val verify_shard : 
  t ->
  commitment ->
  shard ->
  shard_proof ->
  (unit,
    [> `Invalid_degree_strictly_less_than_expected of
         (int, int) error_container
    | `Invalid_shard
    | `Shard_index_out_of_range of string ])
    Stdlib.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_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 prove_commitment : 
  t ->
  polynomial ->
  (commitment_proof,
    [> `Invalid_degree_strictly_less_than_expected of
         (int, int) error_container ])
    Stdlib.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

val prove_page : 
  t ->
  polynomial ->
  int ->
  (page_proof,
    [> `Invalid_degree_strictly_less_than_expected of
         (int, int) error_container
    | `Page_index_out_of_range ])
    Stdlib.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).

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.

type shards_proofs_precomputation

The precomputation used to produce shard proofs.

val shards_proofs_precomputation_encoding : 
  shards_proofs_precomputation Data_encoding.t

val precompute_shards_proofs : t -> shards_proofs_precomputation

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.

raises a
Data_encoding.Binary.Write_error if precomputation can't be serialized to a value shards_proofs_precomputation_encoding.

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.

package tezos-crypto-dal

Cryptography for the Data Availability Layer