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

First cell of this skip list.

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.

add_confirmed_slots hist cache 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.

val add_confirmed_slot_headers_no_cache : t -> Header.t list -> t Tezos_protocol_environment_alpha.Error_monad.tzresult

add_confirmed_slot_headers_no_cache cell slot_headers same as add_confirmed_slot_headers, but no cache is 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.

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