diff --git a/src/proto_alpha/bin_sc_rollup_node/inbox.ml b/src/proto_alpha/bin_sc_rollup_node/inbox.ml index bd17c8ac8839c8b9aa8b690ed4a4d0f71c71c55a..e5b69d06b86c5f3769e3294d871024270bea938a 100644 --- a/src/proto_alpha/bin_sc_rollup_node/inbox.ml +++ b/src/proto_alpha/bin_sc_rollup_node/inbox.ml @@ -91,7 +91,8 @@ module State = struct let*! block_level = Layer1.level_of_hash store block_hash in let block_level = Raw_level.of_int32_exn block_level in if Raw_level.(block_level <= node_ctxt.genesis_info.level) then - return @@ Store.Inbox.history_at_genesis ~bound:(Int64.of_int 60000) + return + @@ Store.Inbox.history_at_genesis ~capacity:(Int64.of_int 60000) else failwith "The inbox history for hash %a is missing." diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index 0156ca1c0dc1ad20d12b00a3c5f2cf2abfbccc82..f0cc3a42c97dbea31f2236d3d962ff0b8849b18a 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.mli +++ b/src/proto_alpha/lib_protocol/alpha_context.mli @@ -2833,7 +2833,7 @@ module Sc_rollup : sig val pp_history : Format.formatter -> history -> unit - val history_at_genesis : bound:int64 -> history + val history_at_genesis : capacity:int64 -> history val add_messages : inbox_context -> 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 095c5937caa3964b67a385312f9b4c635b4d2e12..b805cd02558a24a55be94bf95eeee3f5f4f80f95 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml @@ -371,7 +371,7 @@ module type MerkelizedOperations = sig val pp_history : Format.formatter -> history -> unit - val history_at_genesis : bound:int64 -> history + val history_at_genesis : capacity:int64 -> history val add_messages : inbox_context -> @@ -537,9 +537,18 @@ struct 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; - bound : int64; - counter : int64; + (** 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 = @@ -552,15 +561,15 @@ struct (list (tup2 int64 Hash.encoding)) in conv - (fun {events; sequence; bound; counter} -> - (events, sequence, bound, counter)) - (fun (events, sequence, bound, counter) -> - {events; sequence; bound; counter}) + (fun {events; sequence; capacity; next_index} -> + (events, sequence, capacity, next_index)) + (fun (events, sequence, capacity, next_index) -> + {events; sequence; capacity; next_index}) (obj4 (req "events" events_encoding) (req "sequence" sequence_encoding) - (req "bound" int64) - (req "counter" int64)) + (req "capacity" int64) + (req "next_index" int64)) let pp_history fmt history = Hash.Map.bindings history.events |> fun bindings -> @@ -580,45 +589,51 @@ struct Format.fprintf fmt "@[History:@;\ - \ { bound: %Ld;@;\ - \ counter : %Ld;@;\ + \ { capacity: %Ld;@;\ + \ next_index : %Ld;@;\ \ bindings: %a;@;\ \ sequence: %a; }@]" - history.bound - history.counter + history.capacity + history.next_index (Format.pp_print_list pp_binding) bindings (Format.pp_print_list pp_sequence_binding) sequence_bindings - let history_at_genesis ~bound = - {events = Hash.Map.empty; sequence = Int64_map.empty; bound; counter = 0L} + let history_at_genesis ~capacity = + { + events = Hash.Map.empty; + sequence = Int64_map.empty; + capacity; + next_index = 0L; + } - (** [no_history] creates an empty history with [bound] set to + (** [no_history] creates an empty history with [capacity] set to zero---this makes the [remember] function a no-op. We want this behaviour in the protocol because we don't want to store previous levels of the inbox. *) - let no_history = history_at_genesis ~bound:0L + let no_history = history_at_genesis ~capacity:0L (** [remember ptr cell history] extends [history] with a new mapping from [ptr] to [cell]. If [history] is full, the - oldest mapping is removed. If the history bound is less + oldest mapping is removed. If the history capacity is less or equal to zero, then this function returns [history] untouched. *) let remember ptr cell history = - if Compare.Int64.(history.bound <= 0L) then history + if Compare.Int64.(history.capacity <= 0L) then history else let events = Hash.Map.add ptr cell history.events in - let counter = Int64.succ history.counter in + let current_index = history.next_index in + let next_index = Int64.succ current_index in let history = { events; - sequence = Int64_map.add history.counter ptr history.sequence; - bound = history.bound; - counter; + sequence = Int64_map.add current_index ptr history.sequence; + capacity = history.capacity; + next_index; } in - if Int64.(equal history.counter history.bound) then + if Int64.(equal history.next_index history.capacity) then match Int64_map.min_binding history.sequence with | None -> (* This case is impossible as the map [history.sequence] was @@ -628,8 +643,8 @@ struct let sequence = Int64_map.remove l history.sequence in let events = Hash.Map.remove h events in { - counter = Int64.pred history.counter; - bound = history.bound; + next_index = Int64.pred history.next_index; + capacity = history.capacity; sequence; events; } @@ -670,7 +685,7 @@ struct messages. If [new_level] is a higher level than the current inbox, we create a new inbox level tree at that level in which to start adding messages, and archive the earlier levels depending on the - [history] parameter's [bound]. If [level_tree] is [None] (this + [history] parameter's [capacity]. If [level_tree] is [None] (this happens when the inbox is first created) we similarly create a new empty level tree with the right [level] key. 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 c700a5f46e54f5ca8a647d4e667ae7577901bfba..3eae7243fb4032e6e2876c0744812bfc79dbb662 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli @@ -237,8 +237,8 @@ module type MerkelizedOperations = sig 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 [bound] parameter. In the L1 we use this with - [bound] set to zero, which makes it immediately forget an old + 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 @@ -249,10 +249,10 @@ module type MerkelizedOperations = sig val pp_history : Format.formatter -> history -> unit - (** Construct an empty initial [history] with a given [bound]. If you - are running a rollup node, [bound] needs to be large enough to + (** Construct an empty initial [history] with a given [capacity]. If you + are running a rollup node, [capacity] needs to be large enough to remember any levels for which you may need to produce proofs. *) - val history_at_genesis : bound:int64 -> history + val history_at_genesis : capacity:int64 -> history (** [add_messages ctxt history inbox level payloads level_tree] inserts a list of [payloads] as new messages in the [level_tree] of the diff --git a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox.ml b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox.ml index 7f68fba0bfd9b50869ba99ef6692c4626d7c3cc5..83e9f30b99b9c13c117d135c80a2a4ba5c475b19 100644 --- a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox.ml +++ b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox.ml @@ -58,7 +58,7 @@ let setup_inbox_with_messages list_of_payloads f = let open Lwt_syntax in create_context () >>=? fun ctxt -> let* inbox = empty ctxt rollup level in - let history = history_at_genesis ~bound:10000L in + let history = history_at_genesis ~capacity:10000L in let rec aux level history inbox inboxes level_tree = function | [] -> return (ok (level_tree, history, inbox, inboxes)) | [] :: ps -> @@ -266,7 +266,7 @@ let setup_node_inbox_with_messages list_of_payloads f = let* index = Tezos_context_memory.Context.init "foo" in let ctxt = Tezos_context_memory.Context.empty index in let* inbox = empty ctxt rollup level in - let history = history_at_genesis ~bound:10000L in + let history = history_at_genesis ~capacity:10000L in let rec aux level history inbox inboxes level_tree = function | [] -> return (ok (level_tree, history, inbox, inboxes)) | payloads :: ps -> ( @@ -398,7 +398,7 @@ let test_empty_inbox_proof (level, n) = let* index = Tezos_context_memory.Context.init "foo" in let ctxt = Tezos_context_memory.Context.empty index in let* inbox = Node.empty ctxt rollup level in - let history = Node.history_at_genesis ~bound:10000L in + let history = Node.history_at_genesis ~capacity:10000L in let* history, history_proof = Node.form_history_proof ctxt history inbox None in