`Tezos_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:

- The genesis: it is the case in both
`Archive`

and`Full`

modes as the caboose is always located down to the genesis block, but it is also the case in a`Rolling`

mode early state (when caboose = genesis).

- Any block: it is the case in
`Rolling`

mode when the caboose is higher than the genesis. Indeed, the caboose can be located (almost) anywhere.

`type t = {`

`head_hash : Tezos_crypto.Hashed.Block_hash.t;` |

`head_header : Block_header.t;` |

`history : Tezos_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
```

Argument to the seed used to randomize the locator.

`estimated_length seed locator`

estimates the length of the chain represented by `locator`

using `seed`

.

```
val compute :
get_predecessor:
( Tezos_crypto.Hashed.Block_hash.t ->
int ->
Tezos_crypto.Hashed.Block_hash.t option Lwt.t ) ->
caboose:Tezos_crypto.Hashed.Block_hash.t ->
size:int ->
Tezos_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 = {`

`block : Tezos_crypto.Hashed.Block_hash.t;` |

`predecessor : Tezos_crypto.Hashed.Block_hash.t;` |

`step : int;` |

`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`

`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:Tezos_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`

.

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

```
val unknown_prefix :
is_known:( Tezos_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`

.