diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index 8b36d8ae76742b7f2a4ada7e7069428fae9c3fce..e450eca62dc62031e44dd1828195c4f28b92b79b 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.mli +++ b/src/proto_alpha/lib_protocol/alpha_context.mli @@ -2807,6 +2807,8 @@ module Sc_rollup : sig type history_proof + type history + module Hash : sig include S.HASH @@ -2828,8 +2830,6 @@ module Sc_rollup : sig val new_level_tree : inbox_context -> Raw_level.t -> tree Lwt.t - type history - val history_encoding : history Data_encoding.t val pp_history : Format.formatter -> history -> unit @@ -3305,7 +3305,7 @@ module Sc_rollup : sig val inbox : Inbox.history_proof - val history : history + val history : Inbox.history end end diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml index b805cd02558a24a55be94bf95eeee3f5f4f80f95..ea922ce92a4c3f24aa37a7400f85861120e8f6d3 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml @@ -93,6 +93,8 @@ let () = (function Tried_to_add_zero_messages -> Some () | _ -> None) (fun () -> Tried_to_add_zero_messages) +module Int64_map = Map.Make (Int64) + (* 32 *) let hash_prefix = "\003\250\174\238\208" (* scib1(55) *) @@ -158,6 +160,27 @@ module V1 = struct (Skip_list.pp ~pp_content:Hash.pp ~pp_ptr:Hash.pp) history + type history = { + events : history_proof Hash.Map.t; + (** The history proofs stored in the history structure, indexed by + inboxes hashes. *) + sequence : Hash.t Int64_map.t; + (** An additional map from int64 indexes to inboxes hashes, to be able + to remove old entries when the structure is full. *) + capacity : int64; + (** The max number of the entries in the structure. Once the maximum size + is reached, older entries are deleted to free space for new ones. *) + next_index : int64; + (** The index to use for the next entry to add in the structure. *) + oldest_index : int64; + (** The oldest index of the (oldest) entry that has been added to the + data structure. If the history is empty, [oldest_index] is + equal to [next_index]. *) + size : int64; + (** Counts the number of entries that are stored in history. It + satisfies the invariant: `0 <= size <= capacity` *) + } + (* At a given level, an inbox is composed of metadata of type [t] and @@ -365,8 +388,6 @@ module type MerkelizedOperations = sig val new_level_tree : inbox_context -> Raw_level_repr.t -> tree Lwt.t - type history - val history_encoding : history Data_encoding.t val pp_history : Format.formatter -> history -> unit @@ -533,24 +554,6 @@ struct Sc_rollup_inbox_message_repr.unsafe_of_string (Bytes.to_string bs)) bytes - module Int64_map = Map.Make (Int64) - - type history = { - events : history_proof Hash.Map.t; - (** The of history proofs stored in the history structure, indexed by - inboxes hashes. *) - sequence : Hash.t Int64_map.t; - (** An additional map from int64 indexes to inboxes hashes, to be able - to remove old entries when the structure is full. *) - capacity : int64; - (** The max number of the entries in the structure. Once the maximum size - is reached, older entries are deleted to free space for new ones. *) - (* TODO: The current implementation likely needs a fix. - See: https://gitlab.com/tezos/tezos/-/issues/2981*) - next_index : int64; - (** The index to use for the next entry to add in the structure *) - } - let history_encoding : history Data_encoding.t = let open Data_encoding in let events_encoding = Hash.Map.encoding history_proof_encoding in @@ -561,15 +564,17 @@ struct (list (tup2 int64 Hash.encoding)) in conv - (fun {events; sequence; capacity; next_index} -> - (events, sequence, capacity, next_index)) - (fun (events, sequence, capacity, next_index) -> - {events; sequence; capacity; next_index}) - (obj4 + (fun {events; sequence; capacity; next_index; oldest_index; size} -> + (events, sequence, capacity, next_index, oldest_index, size)) + (fun (events, sequence, capacity, next_index, oldest_index, size) -> + {events; sequence; capacity; next_index; oldest_index; size}) + (obj6 (req "events" events_encoding) (req "sequence" sequence_encoding) (req "capacity" int64) - (req "next_index" int64)) + (req "next_index" int64) + (req "oldest_index" int64) + (req "size" int64)) let pp_history fmt history = Hash.Map.bindings history.events |> fun bindings -> @@ -590,10 +595,14 @@ struct fmt "@[History:@;\ \ { capacity: %Ld;@;\ + \ current size: %Ld;@;\ + \ oldest index: %Ld;@;\ \ next_index : %Ld;@;\ \ bindings: %a;@;\ \ sequence: %a; }@]" history.capacity + history.size + history.oldest_index history.next_index (Format.pp_print_list pp_binding) bindings @@ -601,11 +610,14 @@ struct sequence_bindings let history_at_genesis ~capacity = + let next_index = 0L in { events = Hash.Map.empty; sequence = Int64_map.empty; capacity; - next_index = 0L; + next_index; + oldest_index = next_index; + size = 0L; } (** [no_history] creates an empty history with [capacity] set to @@ -631,24 +643,34 @@ struct sequence = Int64_map.add current_index ptr history.sequence; capacity = history.capacity; next_index; + oldest_index = history.oldest_index; + size = Int64.succ history.size; } in - if Int64.(equal history.next_index history.capacity) then - match Int64_map.min_binding history.sequence with + (* A negative size means that [history.capacity] is set to [Int64.max_int] + and that the structure is full, so adding a new entry makes the size + overflows. In this case, we remove an element in the else branch to + keep the size of the history equal to [Int64.max_int] at most. *) + if Compare.Int64.(history.size > 0L && history.size <= history.capacity) + then history + else + let l = history.oldest_index in + match Int64_map.find l history.sequence with | None -> - (* This case is impossible as the map [history.sequence] was - added to a few lines earlier. *) + (* If history.size > history.capacity > 0, there is necessarily + an entry whose index is history.oldest_index in [sequence]. *) assert false - | Some (l, h) -> + | Some h -> let sequence = Int64_map.remove l history.sequence in let events = Hash.Map.remove h events in { - next_index = Int64.pred history.next_index; + next_index = history.next_index; capacity = history.capacity; + size = history.capacity; + oldest_index = Int64.succ history.oldest_index; sequence; events; } - else history let take_snapshot inbox = let prev_cell = inbox.old_levels_messages in diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli index 3eae7243fb4032e6e2876c0744812bfc79dbb662..856444ac0e9ec069d0d66d072762ffb80212a587 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli @@ -162,6 +162,23 @@ module V1 : sig *) type history_proof + (** A [history] is basically a lookup table of {!history_proof}s. We + need this if we want to produce inbox proofs because it allows us + to dereference the 'pointer' hashes in any of the + [history_proof]s. This [deref] function is passed to + [Skip_list.back_path] or [Skip_list.search] to allow these + functions to construct valid paths back through the skip list. + + A subtlety of this [history] type is that it is customizable + depending on how much of the inbox history you actually want to + remember, using the [capacity] parameter. In the L1 we use this with + [capacity] set to zero, which makes it immediately forget an old + level as soon as we move to the next. By contrast, the rollup node + uses a history that is sufficiently large to be able to take part + in all potential refutation games occurring during the challenge + period. *) + type history + val pp_history_proof : Format.formatter -> history_proof -> unit val history_proof_encoding : history_proof Data_encoding.t @@ -228,23 +245,6 @@ module type MerkelizedOperations = sig check that in proofs. *) val new_level_tree : inbox_context -> Raw_level_repr.t -> tree Lwt.t - (** A [history] is basically a lookup table of {!history_proof}s. We - need this if we want to produce inbox proofs because it allows us - to dereference the 'pointer' hashes in any of the - [history_proof]s. This [deref] function is passed to - [Skip_list.back_path] or [Skip_list.search] to allow these - functions to construct valid paths back through the skip list. - - A subtlety of this [history] type is that it is customizable - depending on how much of the inbox history you actually want to - remember, using the [capacity] parameter. In the L1 we use this with - [capacity] set to zero, which makes it immediately forget an old - level as soon as we move to the next. By contrast, the rollup node - uses a history that is sufficiently large to be able to take part - in all potential refutation games occurring during the challenge - period. *) - type history - val history_encoding : history Data_encoding.t val pp_history : Format.formatter -> history -> unit diff --git a/src/proto_alpha/lib_protocol/sc_rollup_proof_repr.ml b/src/proto_alpha/lib_protocol/sc_rollup_proof_repr.ml index 067176c20e3055f35dc608f5b402d2e88f9b9323..179105813c47b78b4a86f2d0e51cda7b08de3c22 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_proof_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_proof_repr.ml @@ -139,7 +139,7 @@ module type PVM_with_context_and_state = sig val inbox : Sc_rollup_inbox_repr.history_proof - val history : history + val history : Sc_rollup_inbox_repr.history end end diff --git a/src/proto_alpha/lib_protocol/sc_rollup_proof_repr.mli b/src/proto_alpha/lib_protocol/sc_rollup_proof_repr.mli index bf2ec6389f95d0bd8b32f855fc5c8c3b8f9516be..80c1e997409a7c87446a8916ed05b541064c27ec 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_proof_repr.mli +++ b/src/proto_alpha/lib_protocol/sc_rollup_proof_repr.mli @@ -114,7 +114,7 @@ module type PVM_with_context_and_state = sig val inbox : Sc_rollup_inbox_repr.history_proof - val history : history + val history : Sc_rollup_inbox_repr.history end end