diff --git a/src/proto_alpha/bin_sc_rollup_node/wasm_2_0_0_pvm.ml b/src/proto_alpha/bin_sc_rollup_node/wasm_2_0_0_pvm.ml index dc32c2bdd5a56761e0d2515622c931e026614dd5..681fedc48109a816ea79051e43df10e567585324 100644 --- a/src/proto_alpha/bin_sc_rollup_node/wasm_2_0_0_pvm.ml +++ b/src/proto_alpha/bin_sc_rollup_node/wasm_2_0_0_pvm.ml @@ -70,7 +70,7 @@ module Impl : Pvm.S = struct let kind = Sc_rollup.Kind.of_pvm (module PVM) - let new_dissection = Game_helpers.default_new_dissection + let new_dissection = Game_helpers.Wasm.new_dissection module State = Context.PVMState diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index 78a9a8503c847d89deb8ae380b8b382206527d77..3509c29afeb653dd8ce9cbe70103851805174f62 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.mli +++ b/src/proto_alpha/lib_protocol/alpha_context.mli @@ -3141,6 +3141,10 @@ module Sc_rollup : sig val to_int : t -> int option + val of_z : Z.t -> t + + val to_z : t -> Z.t + val encoding : t Data_encoding.t val pp : Format.formatter -> t -> unit @@ -3495,7 +3499,7 @@ module Sc_rollup : sig chunk_stop_tick : Tick.t; } | Dissection_ticks_not_increasing - | Dissection_invalid_distribution + | Dissection_invalid_distribution of Z.t | Dissection_invalid_successive_states_shape end diff --git a/src/proto_alpha/lib_protocol/sc_rollup_arith.ml b/src/proto_alpha/lib_protocol/sc_rollup_arith.ml index 7682ab3f10e3506db8809c934f46eb295b38f4d7..fd6b788d3fde847a3f5570f06725827eecd61efd 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_arith.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_arith.ml @@ -213,9 +213,17 @@ module Make (Context : P) : | IAdd -> Format.fprintf fmt "add" | IStore x -> Format.fprintf fmt "store(%s)" x - let check_dissection = + let check_dissection ~default_number_of_sections ~start_chunk ~stop_chunk = + let open Sc_rollup_dissection_chunk_repr in + let dist = Sc_rollup_tick_repr.distance start_chunk.tick stop_chunk.tick in + let section_maximum_size = Z.div dist (Z.of_int 2) in Sc_rollup_dissection_chunk_repr.( - default_check ~check_sections_number:default_check_sections_number) + default_check + ~section_maximum_size + ~check_sections_number:default_check_sections_number + ~default_number_of_sections + ~start_chunk + ~stop_chunk) (* diff --git a/src/proto_alpha/lib_protocol/sc_rollup_dissection_chunk_repr.ml b/src/proto_alpha/lib_protocol/sc_rollup_dissection_chunk_repr.ml index c363d6e75eba58ef38ba99ef95008bd947477a69..178433092f1377c7c013a82d97e0203f756cc260 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_dissection_chunk_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_dissection_chunk_repr.ml @@ -64,7 +64,7 @@ type error += chunk_stop_tick : Sc_rollup_tick_repr.t; } | (* `Permanent *) Dissection_ticks_not_increasing - | (* `Permanent *) Dissection_invalid_distribution + | (* `Permanent *) Dissection_invalid_distribution of Z.t | (* `Permanent *) Dissection_invalid_successive_states_shape let pp_state_hash = @@ -85,32 +85,30 @@ let pp ppf {state_hash; tick} = Sc_rollup_tick_repr.pp tick -let default_check_sections_number ~default_number_of_sections ~start_chunk - ~stop_chunk dissection = +let default_check_sections_number ~default_number_of_sections + ~number_of_sections ~dist = let open Result_syntax in - let len = Z.of_int @@ List.length dissection in - let dist = Sc_rollup_tick_repr.distance start_chunk.tick stop_chunk.tick in + let number_of_sections = Z.of_int number_of_sections in + let default_number_of_sections = Z.of_int default_number_of_sections in let should_be_equal_to expected = - Dissection_number_of_sections_mismatch {expected; given = len} + Dissection_number_of_sections_mismatch + {expected; given = number_of_sections} in - let num_sections = Z.of_int @@ default_number_of_sections in - if Z.geq dist num_sections then - error_unless Z.(equal len num_sections) (should_be_equal_to num_sections) - else if Z.(gt dist one) then - error_unless Z.(equal len (succ dist)) (should_be_equal_to Z.(succ dist)) - else tzfail (Dissection_invalid_number_of_sections len) + if Compare.Z.(default_number_of_sections <= dist) then + error_unless + Compare.Z.(number_of_sections = default_number_of_sections) + (should_be_equal_to default_number_of_sections) + else if Compare.Z.(dist > Z.one) then + error_unless Compare.Z.(number_of_sections = dist) (should_be_equal_to dist) + else tzfail (Dissection_invalid_number_of_sections number_of_sections) -let default_check ~check_sections_number ~default_number_of_sections - ~start_chunk ~stop_chunk dissection = +let default_check ~section_maximum_size ~check_sections_number + ~default_number_of_sections ~start_chunk ~stop_chunk dissection = let open Result_syntax in - let len = Z.of_int @@ List.length dissection in + let number_of_sections = Compare.Int.max 0 (List.length dissection - 1) in let dist = Sc_rollup_tick_repr.distance start_chunk.tick stop_chunk.tick in let* () = - check_sections_number - ~default_number_of_sections - ~start_chunk - ~stop_chunk - dissection + check_sections_number ~default_number_of_sections ~number_of_sections ~dist in let* () = match (List.hd dissection, List.last_opt dissection) with @@ -145,9 +143,9 @@ let default_check ~check_sections_number ~default_number_of_sections | _ -> (* This case is probably already handled by the [Dissection_invalid_number_of_sections] returned above *) - tzfail (Dissection_invalid_number_of_sections len) + tzfail + (Dissection_invalid_number_of_sections (Z.of_int number_of_sections)) in - let half_dist = Z.(div dist (of_int 2) |> succ) in let rec traverse states = match states with | {state_hash = None; _} :: {state_hash = Some _; _} :: _ -> @@ -155,8 +153,8 @@ let default_check ~check_sections_number ~default_number_of_sections | {tick; _} :: ({tick = next_tick; state_hash = _} as next) :: others -> if Sc_rollup_tick_repr.(tick < next_tick) then let incr = Sc_rollup_tick_repr.distance tick next_tick in - if Z.(leq incr half_dist) then traverse (next :: others) - else tzfail Dissection_invalid_distribution + if Z.(leq incr section_maximum_size) then traverse (next :: others) + else tzfail (Dissection_invalid_distribution section_maximum_size) else tzfail Dissection_ticks_not_increasing | _ -> return () in @@ -297,19 +295,20 @@ let () = Data_encoding.empty (function Dissection_ticks_not_increasing -> Some () | _ -> None) (fun () -> Dissection_ticks_not_increasing) ; - let description = - "Maximum tick increment in a section cannot be more than half total \ - dissection length" - in register_error_kind `Permanent ~id:"Dissection_invalid_distribution" ~title:description ~description - ~pp:(fun ppf () -> Format.pp_print_string ppf description) - Data_encoding.empty - (function Dissection_invalid_distribution -> Some () | _ -> None) - (fun () -> Dissection_invalid_distribution) ; + ~pp:(fun ppf max -> + Format.fprintf + ppf + "Maximum tick increment in a section cannot be more than %a ticks" + Z.pp_print + max) + Data_encoding.(obj1 (req "section_max_size" n)) + (function Dissection_invalid_distribution max -> Some max | _ -> None) + (fun max -> Dissection_invalid_distribution max) ; let description = "Cannot recover from a blocked state in a dissection" in register_error_kind `Permanent diff --git a/src/proto_alpha/lib_protocol/sc_rollup_dissection_chunk_repr.mli b/src/proto_alpha/lib_protocol/sc_rollup_dissection_chunk_repr.mli index 8f3d14279ed11c4b80e3d6504801e229371ff786..d81adbe90c9fd5d8de24473d3cb76cc87e05291e 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_dissection_chunk_repr.mli +++ b/src/proto_alpha/lib_protocol/sc_rollup_dissection_chunk_repr.mli @@ -37,9 +37,8 @@ val encoding : t Data_encoding.t val default_check_sections_number : default_number_of_sections:int -> - start_chunk:t -> - stop_chunk:t -> - t list -> + number_of_sections:int -> + dist:Z.t -> unit tzresult (** We check firstly that [dissection] is the correct length. It must @@ -62,11 +61,11 @@ val default_check_sections_number : game' attack) will mean that sometimes the honest play is a dissection with multiple [None] states. *) val default_check : + section_maximum_size:Z.t -> check_sections_number: (default_number_of_sections:int -> - start_chunk:t -> - stop_chunk:t -> - t list -> + number_of_sections:int -> + dist:Z.t -> unit tzresult) -> default_number_of_sections:int -> start_chunk:t -> @@ -101,7 +100,7 @@ type error += | Dissection_ticks_not_increasing (** Invalid provided dissection because ticks are not increasing between two successive sections. *) - | Dissection_invalid_distribution + | Dissection_invalid_distribution of Z.t (** Invalid provided dissection because ticks split is not well balanced across sections *) | Dissection_invalid_successive_states_shape diff --git a/src/proto_alpha/lib_protocol/sc_rollup_game_repr.ml b/src/proto_alpha/lib_protocol/sc_rollup_game_repr.ml index dc5c1f512a3d00ab912100677e544b091efb8542..c9b8a31782c63fb1ed7b7d1d94428091188a00cd 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_game_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_game_repr.ml @@ -920,9 +920,17 @@ let play dal_parameters ~dal_attestation_lag ~stakers metadata game refutation = module Internal_for_tests = struct let find_choice = find_choice - let check_dissection = + let check_dissection ~default_number_of_sections ~start_chunk ~stop_chunk = + let open Sc_rollup_dissection_chunk_repr in + let dist = Sc_rollup_tick_repr.distance start_chunk.tick stop_chunk.tick in + let section_maximum_size = Z.div dist (Z.of_int 2) in Sc_rollup_dissection_chunk_repr.( - default_check ~check_sections_number:default_check_sections_number) + default_check + ~section_maximum_size + ~check_sections_number:default_check_sections_number + ~default_number_of_sections + ~start_chunk + ~stop_chunk) end type timeout = {alice : int; bob : int; last_turn_level : Raw_level_repr.t} diff --git a/src/proto_alpha/lib_protocol/sc_rollup_tick_repr.ml b/src/proto_alpha/lib_protocol/sc_rollup_tick_repr.ml index 9e19e92abac11f0949f46f6c3cf005f1c5f03ccd..3c90af0b6b17da1fcb7819f8e1d9b0c516027ea2 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_tick_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_tick_repr.ml @@ -44,6 +44,8 @@ let to_int x = if Z.fits_int x then Some (Z.to_int x) else None let of_z x = x +let to_z x = x + let of_number_of_ticks x = Z.of_int64 (Sc_rollup_repr.Number_of_ticks.to_value x) diff --git a/src/proto_alpha/lib_protocol/sc_rollup_tick_repr.mli b/src/proto_alpha/lib_protocol/sc_rollup_tick_repr.mli index 19d8d34c74c67da22fad35f2cabed38ba6559337..e3a584b5da2108b32bd7f628a0733b81c669b921 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_tick_repr.mli +++ b/src/proto_alpha/lib_protocol/sc_rollup_tick_repr.mli @@ -59,6 +59,8 @@ val of_number_of_ticks : Sc_rollup_repr.Number_of_ticks.t -> t val of_z : Z.t -> t +val to_z : t -> Z.t + val encoding : t Data_encoding.t val pp : Format.formatter -> t -> unit diff --git a/src/proto_alpha/lib_protocol/sc_rollup_wasm.ml b/src/proto_alpha/lib_protocol/sc_rollup_wasm.ml index 5d42b790629f3d7b70bde2830c839c67ce7a0e75..30ed9608c2a021209f0d10d219f059b2ea9231c1 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_wasm.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_wasm.ml @@ -32,6 +32,8 @@ type error += WASM_output_proof_production_failed type error += WASM_invalid_claim_about_outbox +type error += WASM_invalid_dissection_distribution + let () = let open Data_encoding in let msg = "Invalid claim about outbox" in @@ -63,7 +65,20 @@ let () = ~description:msg unit (function WASM_proof_production_failed -> Some () | _ -> None) - (fun () -> WASM_proof_production_failed) + (fun () -> WASM_proof_production_failed) ; + let msg = + "Invalid dissection distribution: not all ticks are a multiplier of the \ + maximum number of ticks of a snapshot" + in + register_error_kind + `Permanent + ~id:"sc_rollup_wasm_invalid_dissection_distribution" + ~title:msg + ~pp:(fun fmt () -> Format.fprintf fmt "%s" msg) + ~description:msg + unit + (function WASM_invalid_dissection_distribution -> Some () | _ -> None) + (fun () -> WASM_invalid_dissection_distribution) module V2_0_0 = struct let ticks_per_snapshot = Z.of_int64 11_000_000_000L @@ -522,9 +537,123 @@ module V2_0_0 = struct | Some (_, false) -> fail WASM_invalid_claim_about_outbox | None -> fail WASM_output_proof_production_failed - let check_dissection = - Sc_rollup_dissection_chunk_repr.( - default_check ~check_sections_number:default_check_sections_number) + let check_sections_number ~default_number_of_sections ~number_of_sections + ~dist = + let open Sc_rollup_dissection_chunk_repr in + let is_stop_chunk_aligned = + Compare.Z.(Z.rem dist ticks_per_snapshot = Z.zero) + in + let max_number_of_sections = Z.(div dist ticks_per_snapshot) in + let expected = + Compare.Z.min + (Z.of_int default_number_of_sections) + (if is_stop_chunk_aligned then max_number_of_sections + else Z.succ max_number_of_sections) + in + let given = Z.of_int number_of_sections in + error_unless + Compare.Z.(given = expected) + (Dissection_number_of_sections_mismatch {given; expected}) + + let check_dissection ~default_number_of_sections ~start_chunk ~stop_chunk + dissection = + let open Result_syntax in + let open Sc_rollup_dissection_chunk_repr in + let dist = + Sc_rollup_tick_repr.distance start_chunk.tick stop_chunk.tick + in + (* + We fall back to the default dissection check when the + [kernel_run] culprit has been found and is being dissected. + + This condition will also be met if the PVM is stuck (because + it is unlikely that [ticks_per_snapshot] messages can be + posted in a commitment period), which is OKay because the Fast + Execution cannot be leveraged in that case, which means the + ad-hoc dissection predicate would not provide any speed up. + *) + if Compare.Z.(dist <= ticks_per_snapshot) then + default_check + ~section_maximum_size:Z.(div dist (Z.of_int 2)) + ~check_sections_number:default_check_sections_number + ~default_number_of_sections + ~start_chunk + ~stop_chunk + dissection + else + (* + There are enough ticks to consider that at least one call + to [kernel_run] is involved. + + We now need to consider two cases: either [stop_chunk] is a + multiple of [ticks_per_snapshot] (the PVM is not stuck), or + it is not (the PVM has been stuck during the processing + of one of the ticks of the dissection). + + For the latter case, we want to validate a dissection if + + 1. Every complete [kernel_run] invocations are dissected + as normal in the n-1 first chunks, and + 2. The final section contains all the ticks of the + interrupted [kernel_run]. + *) + let is_stop_chunk_aligned = + Compare.Z.(Z.rem dist ticks_per_snapshot = Z.zero) + in + (* + We keep the same dissection predicate as the default + dissection that a given section cannot be more than half of + the “full distance”, but we only consider the complete + calls to [kernel_run] in the “full distance”. The remainder + ticks will be put in the very last section. + *) + let considered_dist = + if is_stop_chunk_aligned then dist + else + let last_valid_stop_tick = + Sc_rollup_tick_repr.of_z + Z.( + mul + (div + (Sc_rollup_tick_repr.to_z stop_chunk.tick) + ticks_per_snapshot) + ticks_per_snapshot) + in + Sc_rollup_tick_repr.(distance start_chunk.tick last_valid_stop_tick) + in + (* + There is one last corner case to consider: if the stuck + state happens in the second [kernel_run] of the period. + + In this case, the considered distance is equal to the + snapshot size, and divided this value by two means the + maximum size of a section becomes 0. + + So we keep that a section length is at least + [ticks_per_snapshot]. + *) + let section_maximum_size = + Z.max ticks_per_snapshot (Z.div considered_dist (Z.of_int 2)) + in + let* () = + default_check + ~section_maximum_size + ~check_sections_number + ~default_number_of_sections + ~start_chunk + ~stop_chunk + dissection + in + error_unless + (List.for_all + (fun chunk -> + let open Sc_rollup_tick_repr in + Z.( + equal (rem (to_z chunk.tick) ticks_per_snapshot) zero + || Sc_rollup_tick_repr.equal start_chunk.tick chunk.tick + || Sc_rollup_tick_repr.equal stop_chunk.tick chunk.tick)) + dissection) + WASM_invalid_dissection_distribution module Internal_for_tests = struct let insert_failure state = diff --git a/src/proto_alpha/lib_protocol/test/pbt/test_refutation_game.ml b/src/proto_alpha/lib_protocol/test/pbt/test_refutation_game.ml index 3de5ac7fc7575d9dfe0d386c837115825b0f43c1..365c8e2b986cd505f070b8254c51724e46c03454 100644 --- a/src/proto_alpha/lib_protocol/test/pbt/test_refutation_game.ml +++ b/src/proto_alpha/lib_protocol/test/pbt/test_refutation_game.ml @@ -279,6 +279,43 @@ let gen_tick ?(lower_bound = 0) ?(upper_bound = 10_000) () = let+ tick = lower_bound -- upper_bound in tick_of_int_exn ~__LOC__ tick +(** Generate two chunks consisting in valid boundaries for a dissection *) +let gen_wasm_pvm_dissection_boundaries kind = + let open QCheck2.Gen in + let open Alpha_context in + let* broken = bool in + let* state_hash = gen_random_hash in + let* base = Z.of_int <$> 0 -- 10_000 in + let* len = + Z.of_int + <$> + match kind with + | `Kernel_run -> pure 1 + | `Short -> 2 -- 32 + | `Large -> 1_000 -- 10_000 + in + let+ offset = + if broken then 1 -- Z.to_int Sc_rollup.Wasm_2_0_0PVM.ticks_per_snapshot + else pure 0 + in + let start_tick = + Sc_rollup.Tick.of_z @@ Z.(base * Sc_rollup.Wasm_2_0_0PVM.ticks_per_snapshot) + in + let stop_tick = + Sc_rollup.Tick.of_z + @@ Z.( + ((base + len) * Sc_rollup.Wasm_2_0_0PVM.ticks_per_snapshot) + + Z.of_int offset) + in + let start_chunk = + Sc_rollup.Dissection_chunk. + {tick = start_tick; state_hash = Some State_hash.zero} + in + let stop_chunk = + Sc_rollup.Dissection_chunk.{tick = stop_tick; state_hash = Some state_hash} + in + (start_chunk, stop_chunk) + (** [gen_arith_pvm_messages ~gen_size] is a `correct list` generator. It generates a list of strings that are either integers or `+` to be consumed by the arithmetic PVM. @@ -519,7 +556,7 @@ module Dissection = struct stop_chunk, default_number_of_sections, distance ) -> - let expected_len = succ distance in + let expected_len = distance in truncate_and_check_error dissection start_chunk @@ -747,7 +784,7 @@ module Dissection = struct Z.succ @@ Tick.distance start_chunk.tick stop_chunk.tick in let max_section_length = - Z.(succ @@ (distance - of_int default_number_of_sections)) + Z.(distance - of_int default_number_of_sections) in let section_length = Z.one in @@ -770,6 +807,8 @@ module Dissection = struct let invalid_dissection = replace_distances start_chunk.tick picked_section dissection in + let dist = Tick.distance start_chunk.tick stop_chunk.tick in + let half_dist = Z.div dist (Z.of_int 2) in assert_fails_with ~__LOC__ (Game.Internal_for_tests.check_dissection @@ -777,7 +816,7 @@ module Dissection = struct ~start_chunk ~stop_chunk invalid_dissection) - Dissection_chunk.Dissection_invalid_distribution) + (Dissection_chunk.Dissection_invalid_distribution half_dist)) let tests = ( "Dissection", @@ -1577,6 +1616,70 @@ let prepare_game ~p1_start block rollup lcc commitment_level p1_client p2_client ~refuter_commitment:p2_commitment (p2_client, p1_client) +let check_distribution = function + | fst :: snd :: rst -> + let open Dissection_chunk in + let dist = Tick.distance fst.tick snd.tick in + let _, min_len, max_len = + List.fold_left + (fun (previous_tick, min_len, max_len) chunk -> + let dist = Tick.distance previous_tick chunk.tick in + (* We only consider length that are greater or equal than + the snapshot size. The last one may not be as big, if + the PVM was stuck. *) + if Compare.Z.(dist < Sc_rollup.Wasm_2_0_0PVM.ticks_per_snapshot) + then (chunk.tick, min_len, max_len) + else (chunk.tick, Z.min min_len dist, Z.max max_len dist)) + (snd.tick, dist, dist) + rst + in + Z.(max_len - min_len <= Sc_rollup.Wasm_2_0_0PVM.ticks_per_snapshot) + | _ -> true + +let test_wasm_dissection name kind = + qcheck_make_lwt_res + ~count:1_000_000 + ~name + ~print:(fun (start_chunk, stop_chunk) -> + Format.asprintf + "dissection from %a to %a" + Dissection_chunk.pp + start_chunk + Dissection_chunk.pp + stop_chunk) + ~gen:(gen_wasm_pvm_dissection_boundaries kind) + (fun (start_chunk, stop_chunk) -> + let open Lwt_result_syntax in + let+ dissection = + Game_helpers.( + make_dissection + ~state_hash_from_tick:(fun _ -> + return_some Sc_rollup.State_hash.zero) + ~start_chunk + ~our_stop_chunk:stop_chunk + @@ Wasm.new_dissection + ~start_chunk + ~our_stop_chunk:stop_chunk + ~default_number_of_sections:32) + in + if kind <> `Kernel_run then assert (check_distribution dissection) ; + match + Wasm_2_0_0PVM.Protocol_implementation.check_dissection + ~default_number_of_sections:32 + ~start_chunk + ~stop_chunk:{stop_chunk with state_hash = Some State_hash.zero} + dissection + with + | Ok () -> true + | Error e -> + Format.printf + "dissection %a caused errors %a\n" + Game.pp_dissection + dissection + Environment.Error_monad.pp_trace + e ; + false) + (** Create a test of [p1_strategy] against [p2_strategy]. One of them must be a {!Perfect} player, otherwise, we do not care about which cheater wins. *) @@ -1685,6 +1788,9 @@ let tests = ( "Refutation", qcheck_wrap [ + test_wasm_dissection "dissection is one kernel_run" `Kernel_run; + test_wasm_dissection "dissection shorter than 32 kernel_run" `Short; + test_wasm_dissection "dissection larger than 32 kernel_run" `Large; test_perfect_against_random; test_perfect_against_lazy; test_perfect_against_keen; diff --git a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_game.ml b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_game.ml index 82b77426f8f9f96b504337b6def27851de3826e4..edaf177d754b7e589ed82162c59c1f86aa8bb957 100644 --- a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_game.ml +++ b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_game.ml @@ -46,6 +46,10 @@ let assert_fails_with ~__LOC__ k expected_err = let*! res = k in Assert.proto_error ~loc:__LOC__ res (( = ) expected_err) +let assert_fails_with_f ~__LOC__ k f = + let*! res = k in + Assert.proto_error ~loc:__LOC__ res f + let tick_of_int_exn n = match Tick.of_int n with None -> assert false | Some t -> t @@ -73,7 +77,7 @@ let init_dissection ~size ?init_tick start_hash = ~some:(fun init_tick -> init_tick size) init_tick in - Stdlib.List.init size init_tick + Stdlib.List.init (size + 1) init_tick let init_refutation ~size ?init_tick start_hash = G. @@ -144,7 +148,7 @@ let test_poorly_distributed_dissection () = let init_tick size i = mk_dissection_chunk @@ - if i = size - 1 then (None, tick_of_int_exn 10000) + if i = size then (None, tick_of_int_exn 10000) else (Some (if i = 0 then start_hash else hash_int i), tick_of_int_exn i) in let* ctxt = @@ -154,10 +158,10 @@ let test_poorly_distributed_dissection () = Constants_storage.sc_rollup_number_of_sections_in_dissection ctxt in let move = init_refutation ~size ~init_tick start_hash in - assert_fails_with + assert_fails_with_f ~__LOC__ (T.lift @@ R.game_move ctxt rollup ~player:refuter ~opponent:defender move) - D.Dissection_invalid_distribution + (function D.Dissection_invalid_distribution _ -> true | _ -> false) let test_single_valid_game_move () = let* ctxt, rollup, refuter, defender = two_stakers_in_conflict () in @@ -167,11 +171,11 @@ let test_single_valid_game_move () = in let tick_per_state = 10_000 / size in let dissection = - Stdlib.List.init size (fun i -> + Stdlib.List.init (size + 1) (fun i -> mk_dissection_chunk @@ if i = 0 then (Some start_hash, tick_of_int_exn 0) - else if i = size - 1 then (None, tick_of_int_exn 10000) + else if i = size then (None, tick_of_int_exn 10000) else (Some (hash_int i), tick_of_int_exn (i * tick_per_state))) in let* ctxt = diff --git a/src/proto_alpha/lib_sc_rollup/game_helpers.ml b/src/proto_alpha/lib_sc_rollup/game_helpers.ml index 1e23b59a5072e54f6d6bc8cf357e6419f5dd8eef..7ae2e54fda1195690d11c3d2c0cfe9611d5e1d93 100644 --- a/src/proto_alpha/lib_sc_rollup/game_helpers.ml +++ b/src/proto_alpha/lib_sc_rollup/game_helpers.ml @@ -29,13 +29,11 @@ let default_new_dissection ~default_number_of_sections ~(start_chunk : Game.dissection_chunk) ~(our_stop_chunk : Game.dissection_chunk) = let max_number_of_sections = Z.of_int default_number_of_sections in - let trace_length = - Z.succ (Tick.distance our_stop_chunk.tick start_chunk.tick) - in + let trace_length = Tick.distance our_stop_chunk.tick start_chunk.tick in let number_of_sections = Z.min max_number_of_sections trace_length in let rem = Z.(rem trace_length number_of_sections) in let first_section_length, section_length = - if Compare.Z.(trace_length < max_number_of_sections) then + if Compare.Z.(trace_length <= max_number_of_sections) then (* In this case, every section is of length one. *) Z.(one, one) else @@ -48,7 +46,7 @@ let default_new_dissection ~default_number_of_sections in (* [k] is the number of sections in [rev_dissection]. *) let rec make rev_dissection k tick = - if Z.(equal k (pred number_of_sections)) then List.rev rev_dissection + if Z.(equal k number_of_sections) then List.rev rev_dissection else let next_tick = Tick.jump tick section_length in make (tick :: rev_dissection) (Z.succ k) next_tick @@ -66,3 +64,113 @@ let make_dissection ~state_hash_from_tick ~start_chunk ~our_stop_chunk ticks = | [] -> return @@ List.rev (our_stop_chunk :: acc) in make_dissection_aux ticks [start_chunk] + +module Wasm = struct + let new_dissection ~default_number_of_sections ~start_chunk ~our_stop_chunk = + let open Dissection_chunk in + let dist = Tick.distance start_chunk.tick our_stop_chunk.tick in + let ticks_per_snapshot = Wasm_2_0_0PVM.ticks_per_snapshot in + if Compare.Z.(dist <= ticks_per_snapshot) then + (* + There are two cases that require us to fall back to the + default behavior. Either [start_chunk] is not aligned on the + size of a snapshot (meaning the PVM is stuck) or the distance + between the start and stop chunk is lesser than a snapshot, + meaning we have already found the kernel_run invocation we + were looking for. + *) + default_new_dissection + ~default_number_of_sections + ~start_chunk + ~our_stop_chunk + else + let is_stop_chunk_aligned = + Compare.Z.( + Z.rem (Tick.to_z our_stop_chunk.tick) ticks_per_snapshot = Z.zero) + in + let final_tick = + Tick.of_z + Z.( + div (Tick.to_z our_stop_chunk.tick) ticks_per_snapshot + * ticks_per_snapshot) + in + let dist = Tick.distance start_chunk.tick final_tick in + let max_number_of_sections = Z.(div dist ticks_per_snapshot) in + let number_of_sections = + Z.min + (Z.of_int + (* If [is_stop_chunk_aligned] is false, we allocate one + sections for the surplus. *) + (if is_stop_chunk_aligned then default_number_of_sections + else default_number_of_sections - 1)) + max_number_of_sections + in + + (* [go remaining_sections last_tick dist] tries to compute + [remaining_sections] sections as evenly as possible, starting + from [last_tick] and covering [dist] ticks. *) + let rec go remaining_sections last_tick dist rev_acc = + (* The last section is created by [make_dissection] when it + adds the [stop_chunk]. *) + if Z.(remaining_sections <= one) then + let rev_acc = + (* If [is_stop_chunk_aligned] is false, we insert the + last snapshot point. *) + if is_stop_chunk_aligned then rev_acc else final_tick :: rev_acc + in + List.rev rev_acc + else + (* + We compute the length of the next section of the + dissection as the maximum size such that if we would give + this number to all remaining sections, we would not + consume more than [dist] ticks. This is ensured by + [Z.div], which computes a lower rounding. + *) + let section_len = + Z.( + dist + / (ticks_per_snapshot * remaining_sections) + * ticks_per_snapshot) + in + let next_tick = Tick.jump last_tick section_len in + let next_dist = Z.(dist - section_len) in + (* + There are two cases to consider here. + + 1. Either [dist] was a multiple of + [ticks_per_snapshot]. In that case, the same + [section_len] will be computed in all subsequent + calls of [go]. + 2. Or [dist] was not a multiple of + [ticks_per_snapshot]. In that case, the next + [section_len] in float will be slightly higher than + the previous one, because it will benefit from the + unconsumed reminder of the previous computation, + until enough is left that [dist] becomes a + multiplier of [ticks_per_snapshot]. In that case, we + will fall back to case 1. + + Take case of dividing 60 into 32 chunks. + + - [remaining_sections = 60], [remaining_sections = 32], and + [section_len = 1] (60 / 32 ~= 1.87) + - [remaining_sections = 59], [remaining_sections = 31], and + [section_len = 1] (59 / 31 ~= 1.90) + - [remaining_sections = 58], [remaining_sections = 30], and + [section_len = 1] (58 / 30 ~= 1.93) + - [remaining_sections = 57], [remaining_sections = 29], and + [section_len = 1] (57 / 29 ~= 1.97) + - [remaining_sections = 56], [remaining_sections = 28], and + [section_len = 2] (56 / 28 = 2) + + All remaining sections will be of length 2. + *) + go + Z.(pred remaining_sections) + next_tick + next_dist + (next_tick :: rev_acc) + in + go number_of_sections start_chunk.tick dist [] +end diff --git a/src/proto_alpha/lib_sc_rollup/game_helpers.mli b/src/proto_alpha/lib_sc_rollup/game_helpers.mli index b9a8ddca1d57f9ed80a893b3623cba96fb97ecd7..eb59b3bc9512e71ed9ea878893fe2621566d9363 100644 --- a/src/proto_alpha/lib_sc_rollup/game_helpers.mli +++ b/src/proto_alpha/lib_sc_rollup/game_helpers.mli @@ -50,3 +50,21 @@ val make_dissection : our_stop_chunk:Dissection_chunk.t -> Tick.t trace -> Dissection_chunk.t list tzresult Lwt.t + +module Wasm : sig + (** [new_dissection ~default_number_of_sections ~start_chunk + ~our_stop_chunk] computes a dissection that satisfies the + dissection predicate of the WASM PVM, that is all the ticks in + the dissection are aligned with the size of a snapshot. + + If [start_chunk] is not a multiple of the size of a snapshot or + if the distance between [start_chunk] and [stop_chunk] is not + greater than the size of a snapshot, then + {!default_new_dissection} is called, because it means the WASM + PVM is stuck. *) + val new_dissection : + default_number_of_sections:int -> + start_chunk:Game.dissection_chunk -> + our_stop_chunk:Game.dissection_chunk -> + Tick.t list +end