From 0141d841be385ac9f71ef055934b00adbd326fc9 Mon Sep 17 00:00:00 2001 From: Valentin Chaboche Date: Wed, 23 Nov 2022 11:43:35 +0100 Subject: [PATCH] Scoru,Proto: skip list index can be a Z.t --- .../lib_protocol/alpha_context.mli | 6 +-- ...p_inbox_merkelized_payload_hashes_repr.mli | 6 +-- .../lib_protocol/sc_rollup_inbox_repr.ml | 21 ++------- .../lib_protocol/skip_list_repr.ml | 47 ++++++++++--------- .../lib_protocol/skip_list_repr.mli | 6 +-- .../lib_protocol/test/helpers/assert.ml | 3 ++ .../test/unit/test_sc_rollup_inbox.ml | 16 +++---- .../test/unit/test_sc_rollup_inbox_legacy.ml | 3 +- .../test/unit/test_skip_list_repr.ml | 11 +++-- ...a refutation game are slashed-rewarded.out | 4 +- 10 files changed, 60 insertions(+), 63 deletions(-) diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index 17aae84fb411..ce4bffdb6ba5 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.mli +++ b/src/proto_alpha/lib_protocol/alpha_context.mli @@ -3200,7 +3200,7 @@ module Sc_rollup : sig val get_payload_hash : t -> Inbox_message.Hash.t - val get_index : t -> int + val get_index : t -> Z.t type merkelized_and_payload = { merkelized : t; @@ -3227,12 +3227,12 @@ module Sc_rollup : sig val proof_encoding : proof Data_encoding.t val produce_proof : - History.t -> index:int -> t -> (merkelized_and_payload * proof) option + History.t -> index:Z.t -> t -> (merkelized_and_payload * proof) option val verify_proof : proof -> (t * t) tzresult module Internal_for_tests : sig - val find_predecessor_payload : History.t -> index:int -> t -> t option + val find_predecessor_payload : History.t -> index:Z.t -> t -> t option end end diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_merkelized_payload_hashes_repr.mli b/src/proto_alpha/lib_protocol/sc_rollup_inbox_merkelized_payload_hashes_repr.mli index c204bf0f6f45..22e5121a491b 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_merkelized_payload_hashes_repr.mli +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_merkelized_payload_hashes_repr.mli @@ -96,7 +96,7 @@ val pp : Format.formatter -> t -> unit val get_payload_hash : t -> Sc_rollup_inbox_message_repr.Hash.t (** [get_index merkelized] returns the index of [merkelized]. *) -val get_index : t -> int +val get_index : t -> Z.t (** Given two t [(a, b)] and a {!Sc_rollup_inbox_message_repr.serialized} [payload], a [proof] guarantees that [payload] hash is equal to [a] and that @@ -112,7 +112,7 @@ val proof_encoding : proof Data_encoding.t [None] if no merkelized payload with [index] is found (either in the [history] or [index] is not inferior to [get_index into_]). *) val produce_proof : - History.t -> index:int -> t -> (merkelized_and_payload * proof) option + History.t -> index:Z.t -> t -> (merkelized_and_payload * proof) option (** [verify_proof proof] returns [(a, b)] where [proof] validates that [a] is an ancestor of [b]. Fails when [proof] is not a valid inclusion proof. *) @@ -121,5 +121,5 @@ val verify_proof : proof -> (t * t) tzresult module Internal_for_tests : sig (** [find_predecessor_payload history ~index latest_merkelized] looks for the {!t} with [index] that is an ancestor of [latest_merkelized]. *) - val find_predecessor_payload : History.t -> index:int -> t -> t option + val find_predecessor_payload : History.t -> index:Z.t -> t -> t option 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 8998b93dcf35..352bb6b8b321 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml @@ -655,7 +655,7 @@ let verify_level_tree_proof {proof; payload} head_cell_hash n label = in (* TODO: https://gitlab.com/tezos/tezos/-/issues/3975 We could check that index = snapshot_max_index + 1 *) - if Compare.Int.(Z.to_int n > max_index) then + if Compare.Z.(n > max_index) then (* [n] is superior to the index of [head_cell] then the provided [payload] must be empty (,and [payload_cell = head_cell]) *) let* () = @@ -702,12 +702,8 @@ let verify_level_tree_proof {proof; payload} head_cell_hash n label = Sc_rollup_inbox_merkelized_payload_hashes_repr.get_index payload_cell in let* () = - (* TODO: https://gitlab.com/tezos/tezos/-/issues/4259 - - replace the message counter by an int32 so we don't need this - conversion *) error_unless - (Compare.Int.equal (Z.to_int n) payload_index) + (Compare.Z.equal n payload_index) (Inbox_proof_error (Format.sprintf "found index in message_proof (%s) is incorrect" @@ -758,7 +754,7 @@ let produce_level_tree_proof get_level_tree_history head_cell_hash ~index = (* if [index <= level_tree_max_index] then the index belongs to this level, we prove its existence. Else the index is out of bounds, we prove its non-existence. *) - let target_index = Compare.Int.(min index head_cell_max_index) in + let target_index = Compare.Z.(min index head_cell_max_index) in (* We look for the cell at `target_index` starting from `head_cell`. If it exists, we return the payload held in this cell. Otherwise, we prove that [index] does not exist in this level. *) @@ -770,7 +766,7 @@ let produce_level_tree_proof get_level_tree_history head_cell_hash ~index = in match proof with | Some ({payload; merkelized = _}, proof) -> - if Compare.Int.(target_index = index) then + if Compare.Z.(target_index = index) then return {proof; payload = Some payload} else return {proof; payload = None} | None -> tzfail (Inbox_proof_error "could not produce a valid proof.") @@ -872,14 +868,7 @@ let produce_proof ~get_level_tree_history history inbox_snapshot (l, n) = in let level_proof = Skip_list.content history_proof in let* ({payload; proof = _} as message_proof) = - (* TODO: https://gitlab.com/tezos/tezos/-/issues/4259 - - replace the message counter by an int32 so we don't need this - conversion *) - produce_level_tree_proof - get_level_tree_history - level_proof.hash - ~index:(Z.to_int n) + produce_level_tree_proof get_level_tree_history level_proof.hash ~index:n in match payload with | Some payload -> diff --git a/src/proto_alpha/lib_protocol/skip_list_repr.ml b/src/proto_alpha/lib_protocol/skip_list_repr.ml index 7821e2034257..ae284a49ff59 100644 --- a/src/proto_alpha/lib_protocol/skip_list_repr.ml +++ b/src/proto_alpha/lib_protocol/skip_list_repr.ml @@ -45,7 +45,7 @@ module type S = sig 'content Data_encoding.t -> ('content, 'ptr) cell Data_encoding.t - val index : (_, _) cell -> int + val index : (_, _) cell -> Z.t val content : ('content, 'ptr) cell -> 'content @@ -64,13 +64,13 @@ module type S = sig val find : deref:('ptr -> ('content, 'ptr) cell option) -> cell_ptr:'ptr -> - target_index:int -> + target_index:Z.t -> ('content, 'ptr) cell option val back_path : deref:('ptr -> ('content, 'ptr) cell option) -> cell_ptr:'ptr -> - target_index:int -> + target_index:Z.t -> 'ptr list option val valid_back_path : @@ -145,7 +145,7 @@ end) : S = struct type ('content, 'ptr) cell = { content : 'content; back_pointers : 'ptr option FallbackArray.t; - index : int; + index : Z.t; } let equal equal_ptr equal_content cell1 cell2 = @@ -161,7 +161,7 @@ end) : S = struct in let {content; back_pointers; index} = cell1 in equal_content content cell2.content - && Compare.Int.equal index cell2.index + && Compare.Z.equal index cell2.index && equal_back_pointers back_pointers cell2.back_pointers let index cell = cell.index @@ -180,12 +180,12 @@ end) : S = struct fmt {| content = %a - index = %d + index = %s back_pointers = %a |} pp_content content - index + (Z.to_string index) (Format.pp_print_list pp_ptr) (back_pointers_to_list back_pointers) @@ -201,7 +201,7 @@ end) : S = struct (fun (index, content, back_pointers) -> {index; content; back_pointers = of_list back_pointers}) (obj3 - (req "index" int31) + (req "index" n) (req "content" content_encoding) (req "back_pointers" (list ptr_encoding))) @@ -210,7 +210,7 @@ end) : S = struct let back_pointers cell = back_pointers_to_list cell.back_pointers let genesis content = - {index = 0; content; back_pointers = FallbackArray.make 0 None} + {index = Z.zero; content; back_pointers = FallbackArray.make 0 None} let back_pointer cell i = FallbackArray.get cell.back_pointers i @@ -221,13 +221,13 @@ end) : S = struct | None -> (* By precondition and invariants of cells. *) assert false let next ~prev_cell ~prev_cell_ptr content = - let index = prev_cell.index + 1 in + let index = Z.succ prev_cell.index in let back_pointers = let rec aux power accu i = - if Compare.Int.(index < power) then List.rev accu + if Compare.Z.(index < power) then List.rev accu else let back_pointer_i = - if Compare.Int.(index mod power = 0) then prev_cell_ptr + if Compare.Z.(Z.rem index power = Z.zero) then prev_cell_ptr else (* The following call is valid because of - [i < List.length prev_cell.back_pointer] @@ -236,9 +236,9 @@ end) : S = struct back_pointer_unsafe prev_cell i in let accu = back_pointer_i :: accu in - aux (power * basis) accu (i + 1) + aux Z.(mul power (of_int basis)) accu (i + 1) in - aux 1 [] 0 + aux Z.one [] 0 in let back_pointers = FallbackArray.of_list ~fallback:None ~proj:Option.some back_pointers @@ -266,20 +266,23 @@ end) : S = struct *) let best_skip cell target_index powers = let open FallbackArray in - let pointed_cell_index i = cell.index - (cell.index mod get powers i) - 1 in + let pointed_cell_index i = + Z.(pred @@ sub cell.index (rem cell.index (of_int (get powers i)))) + in + (* cell.index - (cell.index mod get powers i) - 1 in *) let rec binary_search start_idx end_idx = if Compare.Int.(start_idx >= end_idx) then Some start_idx else let mid_idx = start_idx + ((end_idx - start_idx) / 2) in let mid_cell_index = pointed_cell_index mid_idx in - if Compare.Int.(mid_cell_index = target_index) then Some mid_idx - else if Compare.Int.(mid_cell_index < target_index) then + if Compare.Z.(mid_cell_index = target_index) then Some mid_idx + else if Compare.Z.(mid_cell_index < target_index) then binary_search start_idx (mid_idx - 1) else let prev_mid_cell_index = pointed_cell_index (mid_idx + 1) in - if Compare.Int.(prev_mid_cell_index = target_index) then + if Compare.Z.(prev_mid_cell_index = target_index) then Some (mid_idx + 1) - else if Compare.Int.(prev_mid_cell_index < target_index) then + else if Compare.Z.(prev_mid_cell_index < target_index) then (* If (mid_cell_index > target_index) && (prev_mid_cell_index < target_index) @@ -299,8 +302,8 @@ end) : S = struct let path = ptr :: path in let* cell = deref ptr in let index = cell.index in - if Compare.Int.(target_index = index) then return path - else if Compare.Int.(target_index > index) then fail + if Compare.Z.(target_index = index) then return path + else if Compare.Z.(target_index > index) then fail else let* best_idx = best_skip cell target_index powers in let* ptr = back_pointer cell best_idx in @@ -342,7 +345,7 @@ end) : S = struct let rec valid_path index cell_ptr path = match (cell_ptr, path) with | final_cell, [] -> - equal_ptr target_ptr final_cell && Compare.Int.(index = target_index) + equal_ptr target_ptr final_cell && Compare.Z.(index = target_index) | cell_ptr, cell_ptr' :: path -> assume_some (deref cell_ptr) @@ fun cell -> assume_some (deref cell_ptr') @@ fun cell' -> diff --git a/src/proto_alpha/lib_protocol/skip_list_repr.mli b/src/proto_alpha/lib_protocol/skip_list_repr.mli index 41270ed47435..ae8f07093b03 100644 --- a/src/proto_alpha/lib_protocol/skip_list_repr.mli +++ b/src/proto_alpha/lib_protocol/skip_list_repr.mli @@ -71,7 +71,7 @@ module type S = sig ('content, 'ptr) cell Data_encoding.t (** [index cell] returns the position of [cell] in the sequence. *) - val index : (_, _) cell -> int + val index : (_, _) cell -> Z.t (** [content cell] is the content carried by the [cell]. *) val content : ('content, 'ptr) cell -> 'content @@ -102,7 +102,7 @@ module type S = sig val find : deref:('ptr -> ('content, 'ptr) cell option) -> cell_ptr:'ptr -> - target_index:int -> + target_index:Z.t -> ('content, 'ptr) cell option (** [back_path ~deref ~cell_ptr ~target_index] returns [Some path] @@ -112,7 +112,7 @@ module type S = sig val back_path : deref:('ptr -> ('content, 'ptr) cell option) -> cell_ptr:'ptr -> - target_index:int -> + target_index:Z.t -> 'ptr list option (** [valid_back_path ~equal_ptr ~deref ~cell_ptr ~target_ptr path] diff --git a/src/proto_alpha/lib_protocol/test/helpers/assert.ml b/src/proto_alpha/lib_protocol/test/helpers/assert.ml index 31db55d5c35d..24d1953a35e3 100644 --- a/src/proto_alpha/lib_protocol/test/helpers/assert.ml +++ b/src/proto_alpha/lib_protocol/test/helpers/assert.ml @@ -136,6 +136,9 @@ let not_equal_int64 ~loc (a : int64) (b : int64) = let leq_int64 ~loc (a : int64) (b : int64) = leq ~loc Compare.Int64.compare "Int64 comparison" Int64.pp a b +let equal_z ~loc (a : Z.t) (b : Z.t) = + equal ~loc Compare.Z.( = ) "Z are not equal" Z.pp_print a b + (* bool *) let equal_bool ~loc (a : bool) (b : bool) = equal ~loc Bool.equal "Booleans aren't equal" Format.pp_print_bool a b 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 81113814d24d..4f2d6a6fda80 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 @@ -62,7 +62,7 @@ let assert_merkelized_payload ~__LOC__ ~payload_hash ~index found = let* () = assert_equal_payload_hash ~__LOC__ found_payload_hash payload_hash in - Assert.equal_int ~loc:__LOC__ found_index index + Assert.equal_z ~loc:__LOC__ found_index index let assert_equal_merkelized_payload ~__LOC__ ~found ~expected = let payload_hash = Merkelized_payload_hashes.get_payload_hash expected in @@ -83,8 +83,8 @@ let gen_payloads = let gen_index payloads = let open QCheck2.Gen in let max_index = List.length payloads - 1 in - let* index = 0 -- max_index in - return index + let+ index = 0 -- max_index in + Z.of_int index let gen_payloads_and_index = let open QCheck2.Gen in @@ -125,10 +125,10 @@ let test_merkelized_payload_history payloads = let nb_payloads = List.length payloads in let* history, merkelized_payloads = construct_merkelized_payload payloads in let* () = - Assert.equal_int + Assert.equal_z ~loc:__LOC__ - nb_payloads - (Merkelized_payload_hashes.get_index merkelized_payloads + 1) + (Z.of_int nb_payloads) + (Z.succ (Merkelized_payload_hashes.get_index merkelized_payloads)) in List.iteri_es (fun index (expected_payload : Message.serialized) -> @@ -139,7 +139,7 @@ let test_merkelized_payload_history payloads = WithExceptions.Option.get ~loc:__LOC__ @@ Merkelized_payload_hashes.Internal_for_tests.find_predecessor_payload history - ~index + ~index:(Z.of_int index) merkelized_payloads in let found_payload_hash = @@ -161,7 +161,7 @@ let test_merkelized_payload_proof (payloads, index) = @@ Merkelized_payload_hashes.produce_proof history ~index merkelized_payload in let payload : Message.serialized = - WithExceptions.Option.get ~loc:__LOC__ @@ List.nth payloads index + WithExceptions.Option.get ~loc:__LOC__ @@ List.nth payloads (Z.to_int index) in let payload_hash = Message.hash_serialized_message payload in let* () = assert_equal_payload ~__LOC__ proof_payload payload in diff --git a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox_legacy.ml b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox_legacy.ml index 2bd242a90ca0..6cc5752a111e 100644 --- a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox_legacy.ml +++ b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox_legacy.ml @@ -186,7 +186,8 @@ let test_get_message_payload messages = List.iteri_es (fun i message -> let expected_payload = encode_external_message message in - get_message_payload level_tree_histories level_tree i |> function + get_message_payload level_tree_histories level_tree (Z.of_int i) + |> function | Some payload -> let payload = Sc_rollup_inbox_message_repr.unsafe_to_string payload in fail_unless diff --git a/src/proto_alpha/lib_protocol/test/unit/test_skip_list_repr.ml b/src/proto_alpha/lib_protocol/test/unit/test_skip_list_repr.ml index 3db8327f5eff..b1ab593a7c2f 100644 --- a/src/proto_alpha/lib_protocol/test/unit/test_skip_list_repr.ml +++ b/src/proto_alpha/lib_protocol/test/unit/test_skip_list_repr.ml @@ -94,10 +94,10 @@ struct {size = list.size + 1; cells = (list.size, cell) :: list.cells} let back_path list start stop = - back_path ~deref:(deref list) ~cell_ptr:start ~target_index:stop + back_path ~deref:(deref list) ~cell_ptr:start ~target_index:(Z.of_int stop) let find list start stop = - find ~deref:(deref list) ~cell_ptr:start ~target_index:stop + find ~deref:(deref list) ~cell_ptr:start ~target_index:(Z.of_int stop) let search list start target_content = search @@ -122,12 +122,13 @@ struct match find l i j with | None -> error (err (Printf.sprintf "There must be a cell (%d)" i)) | Some cell -> + let index = Z.to_int (index cell) in error_unless - (index cell = j) + (index = j) (err (Printf.sprintf "Found cell is not the correct one (found %d, expected %d)" - (index cell) + index j)) in let*? path = @@ -248,7 +249,7 @@ struct invariant we want to check is in the opposite direction. *) match rev_path with | cell_x :: cell_z :: _ -> ( - let i = index cell_x in + let i = Z.to_int (index cell_x) in let next_index = i + 1 in match List.nth history.cells (List.length history.cells - next_index - 1) diff --git a/tezt/tests/expected/sc_rollup.ml/Alpha- arith - participant of a refutation game are slashed-rewarded.out b/tezt/tests/expected/sc_rollup.ml/Alpha- arith - participant of a refutation game are slashed-rewarded.out index d2a801bd2daf..b24f7477cb14 100644 --- a/tezt/tests/expected/sc_rollup.ml/Alpha- arith - participant of a refutation game are slashed-rewarded.out +++ b/tezt/tests/expected/sc_rollup.ml/Alpha- arith - participant of a refutation game are slashed-rewarded.out @@ -107,7 +107,7 @@ This sequence of operations was run: ./octez-client --wait none timeout dispute on sc rollup '[SC_ROLLUP_HASH]' with '[PUBLIC_KEY_HASH]' from bootstrap1 Node is bootstrapped. -Estimated gas: 6460.956 units (will add 100 for safety) +Estimated gas: 6460.944 units (will add 100 for safety) Estimated storage: no bytes added Operation successfully injected in the node. Operation hash is '[OPERATION_HASH]' @@ -130,7 +130,7 @@ This sequence of operations was run: First staker (Alice): [PUBLIC_KEY_HASH] Second staker (Bob): [PUBLIC_KEY_HASH] This smart contract rollup refutation timeout was successfully applied - Consumed gas: 6460.956 + Consumed gas: 6460.944 Refutation game status: Game ended: [PUBLIC_KEY_HASH] lost because: timeout Balance updates: Frozen_bonds([PUBLIC_KEY_HASH],[SC_ROLLUP_HASH]) ... -ęś©10000 -- GitLab