Module Mavryk_base.Block_locator

A locator t is a data structure which roughly represents a list of block hashes in the chain. These hashes go from the top of the chain to the bottom. It is sparse in the sense that the distance between two hashes increases exponentially when we move away from the head.

The distance between two hashes of a locator is randomized to prevent attacks. The seed is determined uniquely from the peer_id of the sender and the receiver so that the distance between two hashes can be recomputed locally. This is the purpose of the function to_steps.

The step representation is mostly used by the peer_validator and the bootstrap_pipeline modules.

The last step of a locator may be truncated. It is the case when the last step hits the caboose. Thus, such a non-strict step can be terminated by:

type t = {
  1. head_hash : Mavryk_crypto.Hashed.Block_hash.t;
  2. head_header : Block_header.t;
  3. history : Mavryk_crypto.Hashed.Block_hash.t list;
}

Type for sparse block locators (/à la/ Bitcoin).

val pp : Stdlib.Format.formatter -> t -> unit
val pp_short : Stdlib.Format.formatter -> t -> unit
val encoding : t Data_encoding.t
val bounded_encoding : max_header_size:int -> max_length:int -> unit -> t Data_encoding.t
type seed = {
  1. sender_id : Mavryk_base.P2p_peer.Id.t;
  2. receiver_id : Mavryk_base.P2p_peer.Id.t;
}

Argument to the seed used to randomize the locator.

val estimated_length : seed -> t -> int

estimated_length seed locator estimates the length of the chain represented by locator using seed.

val compute : get_predecessor: (Mavryk_crypto.Hashed.Block_hash.t -> int -> Mavryk_crypto.Hashed.Block_hash.t option Lwt.t) -> caboose:Mavryk_crypto.Hashed.Block_hash.t -> size:int -> Mavryk_crypto.Hashed.Block_hash.t -> Block_header.t -> seed -> t Lwt.t

compute ~get_predecessor ~caboose ~size block_hash header seed returns a sparse block locator whose header is the given header and whose sparse block is computed using seed to compute random jumps from the block_hash, adding the caboose at the end of the sparse block. The sparse block locator contains at most size + 1 elements, including the caboose.

type step = {
  1. block : Mavryk_crypto.Hashed.Block_hash.t;
  2. predecessor : Mavryk_crypto.Hashed.Block_hash.t;
  3. step : int;
  4. strict_step : bool;
}

A 'step' in a locator is a couple of consecutive hashes in the locator, and the expected difference of level between the two blocks (or an upper bounds when strict_step = false).

val pp_step : Stdlib.Format.formatter -> step -> unit
val to_steps : seed -> t -> step list

to_steps seed t builds all the 'steps' composing the locator using the given seed, starting with the oldest one (typically the predecessor of the first step will be the `caboose`). All steps contains strict_step = true, except the oldest one.

val to_steps_truncate : limit:int -> save_point:Mavryk_crypto.Hashed.Block_hash.t -> seed -> t -> step list

to_steps_truncate ~limit ~save_point seed t behaves as to_steps except that when the sum of all the steps already done, and the steps to do in order to reach the next block is superior to limit, we return a truncated list of steps, setting the predecessor of the last step as save_point and its field strict to false.

type validity =
  1. | Unknown
  2. | Known_valid
  3. | Known_invalid

A block can either be known valid, invalid or unknown.

val unknown_prefix : is_known:(Mavryk_crypto.Hashed.Block_hash.t -> validity Lwt.t) -> t -> (validity * t) Lwt.t

unknown_prefix ~is_known t either returns :

  • (Known_valid, (h, hist)) when we find a known valid block in the locator history (w.r.t. is_known), where h is the given locator header and hist is the unknown prefix ending with the known valid block.
  • (Known_invalid, (h, hist)) when we find a known invalid block (w.r.t. is_known) in the locator history, where h is the given locator header and hist is the unknown prefix ending with the known invalid block.
  • (Unknown, (h, hist)) when no block is known valid nor invalid (w.r.t. is_known), where (h, hist) is the given locator.