From 856dfc4d91f40fa33211bde0020ad4cfb214096d Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Tue, 19 Jul 2022 18:19:21 +0200 Subject: [PATCH 1/2] Proto/Scoru: re-design the way the proof sliding window is handled --- .../lib_protocol/sc_rollup_inbox_repr.ml | 56 +++++++++++++------ 1 file changed, 40 insertions(+), 16 deletions(-) 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 b805cd02558a..2e67602e147f 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml @@ -545,10 +545,15 @@ struct 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 *) + 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` *) } let history_encoding : history Data_encoding.t = @@ -561,15 +566,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 +597,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 +612,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 +645,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 -- GitLab From 8e9c2797d65dcb3e3989628ad2e28dd846dec4a7 Mon Sep 17 00:00:00 2001 From: Alain Mebsout Date: Mon, 25 Jul 2022 11:27:02 +0200 Subject: [PATCH 2/2] Proto,SCORU: move history type out of functor --- .../lib_protocol/alpha_context.mli | 6 +-- .../lib_protocol/sc_rollup_inbox_repr.ml | 48 +++++++++---------- .../lib_protocol/sc_rollup_inbox_repr.mli | 34 ++++++------- .../lib_protocol/sc_rollup_proof_repr.ml | 2 +- .../lib_protocol/sc_rollup_proof_repr.mli | 2 +- 5 files changed, 45 insertions(+), 47 deletions(-) diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index 8b36d8ae7674..e450eca62dc6 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 2e67602e147f..ea922ce92a4c 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,29 +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. *) - 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` *) - } - let history_encoding : history Data_encoding.t = let open Data_encoding in let events_encoding = Hash.Map.encoding history_proof_encoding 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 3eae7243fb40..856444ac0e9e 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 067176c20e30..179105813c47 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 bf2ec6389f95..80c1e997409a 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 -- GitLab