package octez-libs

  1. Overview
  2. Docs
A package that contains multiple base libraries used by the Octez suite

Install 

dune-project
 Dependency

www.tezos.com Readme Edit opam file Versions (5)

Authors

  1. T
    Tezos devteam

Maintainers

  1. C
    contact@tezos.com

Sources

tezos-octez-v20.1.tag.bz2
sha256=ddfb5076eeb0b32ac21c1eed44e8fc86a6743ef18ab23fff02d36e365bb73d61
sha512=d22a827df5146e0aa274df48bc2150b098177ff7e5eab52c6109e867eb0a1f0ec63e6bfbb0e3645a6c2112de3877c91a17df32ccbff301891ce4ba630c997a65

doc/octez-libs.crypto-dal/Tezos_crypto_dal/Cryptobox/index.html

Module Tezos_crypto_dal.CryptoboxSource

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 {!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.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).

Sourcetype parameters = Tezos_crypto_dal_octez_dal_config.Dal_config.parameters = {
  1. redundancy_factor : int;
  2. page_size : int;
  3. slot_size : int;
  4. number_of_shards : int;
}

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

Sourcetype 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.

Sourcetype commitment
Sourcetype commitment_proof
Sourcetype page_proof
Sourcetype ('a, 'b) error_container = {
  1. given : 'a;
  2. expected : 'b;
}
Sourcetype Tezos_error_monad.Error_monad.error +=
  1. | Failed_to_load_trusted_setup of string

Failed_to_load_trusted_setup, thrown by Config.init_dal.

Sourcetype Tezos_error_monad.Error_monad.error +=
  1. | Invalid_precomputation_hash of (string, string) error_container

Invalid_precomputation_hash, thrown by load_precompute_shards_proofs.

Sourcemodule 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

An encoding for values of type parameters.

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

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

Sourceval 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.

Sourcetype 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.

Sourceval page_proof_encoding : page_proof Data_encoding.t

An encoding for the proof of a page.

pages_per_slot t returns the number of expected pages per slot.

Sourceval 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.
Sourcetype 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.

Sourcemodule Commitment : sig ... end
Sourcetype slot = bytes

A slot is a byte sequence corresponding to some data.

Sourcetype scalar

The finited field used by the polynomial.

Sourcetype 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.

Sourceval polynomial_degree : polynomial -> int

polynomial_degree polynomial returns the degree of the polynomial.

Sourceval polynomial_evaluate : polynomial -> scalar -> scalar

polynomial_evaluate polynomial x evaluates polynomial(x).

Sourceval 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.
Sourceval 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.
Sourceval 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).

Sourceval 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.

Sourceval 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.

Sourcetype share

A portion of the data represented by a polynomial.

Sourceval share_encoding : share Data_encoding.t

Encoding of a share.

Sourcetype shard = {
  1. index : int;
  2. share : share;
}

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

Sourceval shard_encoding : shard Data_encoding.t

An encoding of a share.

Sourceval encoded_share_size : t -> int

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

Sourceval 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.
Sourceval 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.
Sourcetype shard_proof

A proof that a shard belongs to some commitment.

Sourceval shard_proof_encoding : shard_proof Data_encoding.t

An encoding of a shard proof.

Sourceval 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.
Sourceval 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.
Sourceval 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).
Sourceval 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.
Sourcetype shards_proofs_precomputation

The precomputation used to produce shard proofs.

Sourceval shards_proofs_precomputation_encoding : shards_proofs_precomputation Data_encoding.t
Sourceval 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.

Sourceval 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.

Sourceval 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.

hash_precomputation precomputation returns the Tezos_crypto.Blake2B.t hash of the Data_encoding.t value of precomputation.

Sourceval 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.
Sourcemodule Internal_for_tests : sig ... end
Sourcemodule Config : sig ... end

node parameters for the DAL.