From 4b8c215f20f76ba553ae43a6a2d546ab9a5e752d Mon Sep 17 00:00:00 2001 From: Yann Regis-Gianas Date: Thu, 1 Dec 2022 10:53:35 +0100 Subject: [PATCH 1/3] Proto,SCORU: Add a cost model for playing a refutation move Signed-off-by: Yann Regis-Gianas --- .../lib_protocol/sc_rollup_game_repr.ml | 45 +++++++++++++++++-- .../lib_protocol/sc_rollup_game_repr.mli | 8 ++-- 2 files changed, 46 insertions(+), 7 deletions(-) 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 4a59aa1c40ad..d498dc652ea1 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_game_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_game_repr.ml @@ -808,8 +808,6 @@ let loser_of_results ~alice_result ~bob_result = | false, true -> Some Alice | true, false -> Some Bob -(* TODO: https://gitlab.com/tezos/tezos/-/issues/2926 - This function is incomplete and needs to account for additional gas. *) let cost_play _game refutation = match refutation.step with | Dissection states -> @@ -820,7 +818,48 @@ let cost_play _game refutation = ~number_of_states ~tick_size ~hash_size - | Proof _proof -> Gas_limit_repr.free + | Proof _proof -> + (* + + Proof verification is complex. We choose to follow a very + rough overaproximation based on the idea that proof + verification for both the inbox and the execution step is + dominated by hash computation. + + Assuming that the worst case is a proof of the maximal + operation data length, we consider the cost of hashing a + balanced binary tree of this size (with a maximal size of + leaves since the hashing of internal nodes can be neglected. + + We also consider the largest tick known. At the time writing + this comment, the largest tick is the origination tick of the + PVM. If we assume that the origination has been done with a + kernel of maximum size, and we also assume that most of the + computation cost to import this kernel in the PVM, we simply + consider, again, that the cost of hashing dominates + everything else. + + We multiply this number by 10 by security. + + At the time of writing this comment, this leads to 372940 + mgas for the proof wellformedness verification and 372940 + mgas for the cost of executing a tick. + + *) + let open Saturation_repr in + (* model N_IBlake2b *) + (* Approximating 1.120804 x term *) + let cost_N_IBlake2b size = + let open Syntax in + let v0 = safe_int size in + safe_int 430 + v0 + (v0 lsr 3) + in + let overapproximated_hashing_size = + 2 * Constants_repr.max_operation_data_length + in + let scale10 x = Saturation_repr.(mul (safe_int 10) x) in + scale10 @@ Gas_limit_repr.atomic_step_cost + @@ cost_N_IBlake2b overapproximated_hashing_size let play kind dal_parameters ~dal_attestation_lag ~stakers metadata game refutation = diff --git a/src/proto_alpha/lib_protocol/sc_rollup_game_repr.mli b/src/proto_alpha/lib_protocol/sc_rollup_game_repr.mli index 8cd384a2492d..ac183ecd7f58 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_game_repr.mli +++ b/src/proto_alpha/lib_protocol/sc_rollup_game_repr.mli @@ -388,6 +388,10 @@ val play : refutation -> (game_result, t) Either.t tzresult Lwt.t +(** [cost_play game refutation] returns the gas cost of [play] applied with [game] + and [refutation]. *) +val cost_play : t -> refutation -> Gas_limit_repr.cost + (** A type that represents the number of blocks left for players to play. Each player has her timeout value. `timeout` is expressed in the number of blocks. @@ -406,10 +410,6 @@ type timeout = { val timeout_encoding : timeout Data_encoding.t -(** [cost_play game refutation] returns the gas cost of [play] applied with [game] - and [refutation]. *) -val cost_play : t -> refutation -> Gas_limit_repr.cost - module Internal_for_tests : sig (** Checks that the tick count chosen by the current move is one of the ones in the current dissection. Returns a tuple containing -- GitLab From 3ef5f7ee6c9c7540da01a9cbfd54b038418c1d67 Mon Sep 17 00:00:00 2001 From: Joel Bjornson Date: Mon, 5 Dec 2022 14:58:52 +0000 Subject: [PATCH 2/3] Proto,SCORU: Fix typos --- src/proto_alpha/lib_protocol/sc_rollup_game_repr.ml | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) 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 d498dc652ea1..dd4258005051 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_game_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_game_repr.ml @@ -831,7 +831,7 @@ let cost_play _game refutation = balanced binary tree of this size (with a maximal size of leaves since the hashing of internal nodes can be neglected. - We also consider the largest tick known. At the time writing + We also consider the largest tick known. At the time of writing this comment, the largest tick is the origination tick of the PVM. If we assume that the origination has been done with a kernel of maximum size, and we also assume that most of the @@ -839,7 +839,7 @@ let cost_play _game refutation = consider, again, that the cost of hashing dominates everything else. - We multiply this number by 10 by security. + We multiply this number by 10 for extra safety. At the time of writing this comment, this leads to 372940 mgas for the proof wellformedness verification and 372940 -- GitLab From 370fed1847b1f7e886298c79cf202b8b0778554e Mon Sep 17 00:00:00 2001 From: Yann Regis-Gianas Date: Tue, 6 Dec 2022 09:34:09 +0100 Subject: [PATCH 3/3] Proto,SCORU: Improve doc about gas model for step verification Signed-off-by: Yann Regis-Gianas --- .../lib_protocol/sc_rollup_game_repr.ml | 14 +++++++++----- 1 file changed, 9 insertions(+), 5 deletions(-) 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 dd4258005051..b3c049969710 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_game_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_game_repr.ml @@ -833,11 +833,15 @@ let cost_play _game refutation = We also consider the largest tick known. At the time of writing this comment, the largest tick is the origination tick of the - PVM. If we assume that the origination has been done with a - kernel of maximum size, and we also assume that most of the - computation cost to import this kernel in the PVM, we simply - consider, again, that the cost of hashing dominates - everything else. + PVM. + + If we assume the following worst-case for origination tick: + - the origination has been done with a kernel of maximum size, and + - most of the computation cost is consumed by importing this kernel + in the PVM, + + We can simply consider, again, that the cost of hashing the imported + kernel dominates everything else. We multiply this number by 10 for extra safety. -- GitLab