package tezos-protocol-alpha

  1. Overview
  2. Docs
package tezos-protocol-alpha
Legend:
Library
Module
Module type
Parameter
Class
Class type

This module provides an abstract data structure (type History.t) that represents a skip list used to store successive DAL slots confirmed/attested on L1. There is one slot per cell in the skip list. The slots are sorted in increasing order by level, and by slot index, for the slots of the same level.

This module also defines a bounded history cache (type History.History_cache.t) that allows to remember recent values of a skip list of type History.t (indexed by the skip lists' hashes). This structure is meant to be maintained and used by the rollup node to produce refutation proofs involving DAL slot inputs.

Note on terminology: "confirmed slot" is another name for "attested slot".

type t

Abstract representation of a skip list specialized for confirmed slot headers.

type hash = Pointer_hash.t

Type of hashes of history.

Encoding of the datatype.

val genesis : t

The genesis skip list that contains one dummy cell. This cell has Raw_level_repr.root as published level and no attested slots. Since Dal is not necessarily activated in the genesis block (e.g. this will be the case on mainnet), the skip list is reset at the first call to add_confirmed_slot_headers to enforce the invariant that there are no gaps in the levels of the cells of the skip list.

So, a skip list is initialized with this genesis cell. It's then replaced with a growing (non-dummy) skip list as soon as a call to add_confirmed_slot_headers with a level bigger than Raw_level_repr.root is performed. This allows to activate Dal at any level and having a contiguous skip list (w.r.t. L1 levels). This representation allows to produce simpler proofs with a bounded history cache.

val hash : t -> hash

Returns the hash of an history.

module History_cache : Bounded_history_repr.S with type key = hash and type value = t

The History_cache.t structure is basically a bounded lookup table of t skip lists. (See Bounded_history_repr.S). In the L1 layer, the capacity (bound) is set to zero (nothing is remembered). By contrast, the rollup node uses a history cache with a (sufficiently) large capacity to participate in all potential refutation games occurring during the challenge period. Indeed, the successive recent skip-lists stored in the cache are needed to produce proofs involving slots' pages.

val add_confirmed_slot_headers : t -> History_cache.t -> Raw_level_repr.t -> number_of_slots:int -> Header.t list -> (t * History_cache.t) Tezos_protocol_environment_alpha.Error_monad.tzresult

add_confirmed_slots hist cache published_level ~number_of_slots slot_headers updates the given structure hist with the list of slot_headers. The given cache is also updated to add successive values of cell to it.

This function checks the following pre-conditions before updating the list:

  • The given published_level should match all the levels of the slots in slot_headers, if any;
  • published_level is the successor the last inserted cell's level.
  • slot_headers is sorted in increasing order w.r.t. slots indices.
val add_confirmed_slot_headers_no_cache : t -> Raw_level_repr.t -> number_of_slots:int -> Header.t list -> t Tezos_protocol_environment_alpha.Error_monad.tzresult

Similiar to add_confirmed_slot_headers, but no cache is provided or updated.

val equal : t -> t -> bool

equal a b returns true iff a is equal to b.

Dal slots/pages proofs

type proof

When a SCORU kernel's inputs come from the DAL, they are provided as pages' content for confirmed slots, or None in case the slot doesn't exist or is not confirmed.

In a refutation game involving an import tick of a Dal page input, a honest user should be able to provide:

  • When the PVM is requesting a page of a confirmed slot: a proof that the slot is confirmed, in addition to needed information to check that the page (whose id and content are given) is part of the slot;
  • When the opponent pretends that the PVM is requesting a page of some unconfirmed slot, but that slot is not published or not confirmed on L1: a proof that the slot (whose id is given via the page's id) cannot be confirmed on L1.

See the documentation in the ml file for more technical details.

Encoding for proof.

val pp_proof : serialized:bool -> Tezos_protocol_environment_alpha.Format.formatter -> proof -> unit

Pretty-printer for proof. If serialized is false it will print the abstracted proof representation, otherwise if it's true it will print the serialized version of the proof (i.e. a sequence of bytes).

produce_proof dal_parameters page_id page_info ~get_history slots_hist produces a proof that either:

  • there exists a confirmed slot in the skip list that contains the page identified by page_id whose data and slot inclusion proof are given by page_info, or
  • there cannot exist a confirmed slot in the skip list (whose head is given by slots_hist) containing the page identified by page_id.

In the first case above, page_info should contain the page's content and the proof that the page is part of the (confirmed) slot whose id is given in page_id. In the second case, no page content or proof should be provided, as they are not needed to construct a non-confirmation proof.

The function returns an error in case the slot is not confirmed but the page's content and proof are given. It also fails if the slot is confirmed but no or bad information about the page are provided.

Note that, in case the level of the page is far in the past (the Dal skip list was not populated yet or the slots of the associated level are not valid anymore) should be handled by the caller.

dal_parameters is used when verifying that/if the page is part of the candidate slot (if any).

verify_proof dal_params page_id snapshot proof verifies that the given proof is a valid proof to show that either:

  • the page identified by page_id belongs to a confirmed slot stored in the skip list whose head is snapshot, or
  • there is not confirmed slot in the skip list (whose head is) snapshot that could contain the page identified by page_id.

dal_parameters is used when verifying that/if the page is part of the candidate slot (if any).

type Tezos_protocol_environment_alpha.Error_monad.error +=
  1. | Add_element_in_slots_skip_list_violates_ordering
type Tezos_protocol_environment_alpha.Error_monad.error +=
  1. | Dal_proof_error of string
  2. | Unexpected_page_size of {
    1. expected_size : int;
    2. page_size : int;
    }
module Internal_for_tests : sig ... end
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct