Tezos_crypto_dal.CryptoboxSourceThe 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).
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.
Dal_initialisation_twice, thrown by Config.init_dal.
Failed_to_load_trusted_setup, thrown by Config.init_dal.
type Tezos_error_monad.Error_monad.error += | Invalid_precomputation_hash of (string, string) error_containerInvalid_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_containerinclude 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_containerAn 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
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.
An encoding for the proof of a page.
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.tverify_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 FailsError `Invalid_degree_strictly_less_than_expected _ if the SRS contained in t is too small to proceed with the verificationError `Page_length_mismatch if the page is not of the expected length page_size given for the initialisation of tError `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 tEnsures:
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.
A slot is a byte sequence corresponding to some data.
The finited field used by the 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.
polynomial_degree polynomial returns the degree of the polynomial.
polynomial_evaluate polynomial x evaluates polynomial(x).
val polynomial_from_slot :
t ->
slot ->
(polynomial, [> `Slot_wrong_size of string ]) Result.tpolynomial_from_slot t slot returns a polynomial from the a slot slot.
Requires:
Bytes.length slot is the slot size declared in t.Ensures:
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.polynomial_to_slot t polynomial returns a slot from a polynomial.
Ensures:
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 ])
Result.tcommit 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 :
Format.formatter ->
[< `Invalid_degree_strictly_less_than_expected of (int, int) error_container ] ->
unitpp_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 ] ->
stringstring_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).
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 ])
resultpolynomial_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:
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.shards_from_polynomial t polynomial computes all the shards encoding the original polynomial.
Ensures:
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.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 ])
Result.tverify_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:
t should be the same as the one used to produce the commitment and proof.Fails with:
Error `Invalid_shard if the verification failsError `Invalid_degree_strictly_less_than_expected _ if the SRS contained in t is too small to proceed with the verificationError (`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 ])
Result.tprove_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 proofval prove_page :
t ->
polynomial ->
int ->
(page_proof,
[> `Invalid_degree_strictly_less_than_expected of
(int, int) error_container
| `Page_index_out_of_range ])
Result.tprove_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 proofError (`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.The precomputation used to produce shard proofs.
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.tsave_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.tload_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.
val prove_shards :
t ->
precomputation:shards_proofs_precomputation ->
polynomial:polynomial ->
shard_proof arrayprove_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.