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 4a59aa1c40ad0821639ff1ca530d266c39a92ca8..b3c049969710e618a62d3c52d005999c8786544b 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,52 @@ 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 of writing
+         this comment, the largest tick is the origination tick of the
+         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.
+
+         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 8cd384a2492df0473ba3a34b0bd8113a54d51d42..ac183ecd7f58ad54923e4fe73155ac07ff32d98b 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