diff --git a/src/proto_alpha/lib_benchmarks_proto/interpreter_workload.ml b/src/proto_alpha/lib_benchmarks_proto/interpreter_workload.ml
index 9b4410091b9f2956de7d6ed701c874ddd9f434de..2c2cefb4d936dc1f44fa7f22db2fdcf7556813b3 100644
--- a/src/proto_alpha/lib_benchmarks_proto/interpreter_workload.ml
+++ b/src/proto_alpha/lib_benchmarks_proto/interpreter_workload.ml
@@ -1174,11 +1174,11 @@ let extract_ir_sized_step :
   | (ISet_iter _, (set, _)) -> Instructions.set_iter (Size.set set)
   | (ISet_mem (_, _), (v, (set, _))) ->
       let (module S) = Script_set.get set in
-      let sz = Size.size_of_comparable_value S.elt_ty v in
+      let sz = S.OPS.elt_size v in
       Instructions.set_mem sz (Size.set set)
   | (ISet_update (_, _), (v, (_flag, (set, _)))) ->
       let (module S) = Script_set.get set in
-      let sz = Size.size_of_comparable_value S.elt_ty v in
+      let sz = S.OPS.elt_size v in
       Instructions.set_update sz (Size.set set)
   | (ISet_size (_, _), (set, _)) -> Instructions.set_size (Size.set set)
   | (IEmpty_map (_, _, _), _) -> Instructions.empty_map
@@ -1186,19 +1186,19 @@ let extract_ir_sized_step :
   | (IMap_iter _, (map, _)) -> Instructions.map_iter (Size.map map)
   | (IMap_mem (_, _), (v, (map, _))) ->
       let (module Map) = Script_map.get_module map in
-      let key_size = Size.size_of_comparable_value Map.key_ty v in
+      let key_size = Map.OPS.key_size v in
       Instructions.map_mem key_size (Size.map map)
   | (IMap_get (_, _), (v, (map, _))) ->
       let (module Map) = Script_map.get_module map in
-      let key_size = Size.size_of_comparable_value Map.key_ty v in
+      let key_size = Map.OPS.key_size v in
       Instructions.map_get key_size (Size.map map)
   | (IMap_update (_, _), (v, (_elt_opt, (map, _)))) ->
       let (module Map) = Script_map.get_module map in
-      let key_size = Size.size_of_comparable_value Map.key_ty v in
+      let key_size = Map.OPS.key_size v in
       Instructions.map_update key_size (Size.map map)
   | (IMap_get_and_update (_, _), (v, (_elt_opt, (map, _)))) ->
       let (module Map) = Script_map.get_module map in
-      let key_size = Size.size_of_comparable_value Map.key_ty v in
+      let key_size = Map.OPS.key_size v in
       Instructions.map_get_and_update key_size (Size.map map)
   | (IMap_size (_, _), (map, _)) -> Instructions.map_size (Size.map map)
   | (IEmpty_big_map (_, _, _, _), _) -> Instructions.empty_big_map
@@ -1439,7 +1439,7 @@ let extract_control_trace (type bef_top bef aft_top aft)
       Control.map_enter_body (Size.of_int (List.length xs))
   | KMap_exit_body (_, _, map, k, _) ->
       let (module Map) = Script_map.get_module map in
-      let key_size = Size.size_of_comparable_value Map.key_ty k in
+      let key_size = Map.OPS.key_size k in
       Control.map_exit_body key_size (Size.map map)
   | KView_exit _ -> Control.view_exit
   | KLog _ -> Control.log
diff --git a/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL b/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL
index bf0e7675ea25b2d7ef5c858be9a6369749b46b94..46bc20bd121a9fd356b59c4f45d54fdc1fb00c75 100644
--- a/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL
+++ b/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL
@@ -127,9 +127,10 @@
         "Script_ir_annot",
         "Script_typed_ir",
         "Script_comparable",
+        "Gas_comparable_input_size",
         "Script_set",
         "Script_map",
-	"Gas_input_size",
+        "Gas_input_size",
         "Script_typed_ir_size",
         "Script_typed_ir_size_costs",
         "Michelson_v1_gas",
diff --git a/src/proto_alpha/lib_protocol/dune.inc b/src/proto_alpha/lib_protocol/dune.inc
index 1adc8db32b9e5883c3fa0f0e5cc1cdceba41f9d9..f72940e104762978d5710f1a851ee4da6ac5f188 100644
--- a/src/proto_alpha/lib_protocol/dune.inc
+++ b/src/proto_alpha/lib_protocol/dune.inc
@@ -143,6 +143,7 @@ module CamlinternalFormatBasics = struct include CamlinternalFormatBasics end
    script_ir_annot.mli script_ir_annot.ml
    script_typed_ir.mli script_typed_ir.ml
    script_comparable.mli script_comparable.ml
+   gas_comparable_input_size.mli gas_comparable_input_size.ml
    script_set.mli script_set.ml
    script_map.mli script_map.ml
    gas_input_size.mli gas_input_size.ml
@@ -304,6 +305,7 @@ module CamlinternalFormatBasics = struct include CamlinternalFormatBasics end
    script_ir_annot.mli script_ir_annot.ml
    script_typed_ir.mli script_typed_ir.ml
    script_comparable.mli script_comparable.ml
+   gas_comparable_input_size.mli gas_comparable_input_size.ml
    script_set.mli script_set.ml
    script_map.mli script_map.ml
    gas_input_size.mli gas_input_size.ml
@@ -465,6 +467,7 @@ module CamlinternalFormatBasics = struct include CamlinternalFormatBasics end
    script_ir_annot.mli script_ir_annot.ml
    script_typed_ir.mli script_typed_ir.ml
    script_comparable.mli script_comparable.ml
+   gas_comparable_input_size.mli gas_comparable_input_size.ml
    script_set.mli script_set.ml
    script_map.mli script_map.ml
    gas_input_size.mli gas_input_size.ml
@@ -648,6 +651,7 @@ include Tezos_raw_protocol_alpha.Main
    Script_ir_annot
    Script_typed_ir
    Script_comparable
+   Gas_comparable_input_size
    Script_set
    Script_map
    Gas_input_size
@@ -850,6 +854,7 @@ include Tezos_raw_protocol_alpha.Main
    script_ir_annot.mli script_ir_annot.ml
    script_typed_ir.mli script_typed_ir.ml
    script_comparable.mli script_comparable.ml
+   gas_comparable_input_size.mli gas_comparable_input_size.ml
    script_set.mli script_set.ml
    script_map.mli script_map.ml
    gas_input_size.mli gas_input_size.ml
diff --git a/src/proto_alpha/lib_protocol/gas_comparable_input_size.ml b/src/proto_alpha/lib_protocol/gas_comparable_input_size.ml
new file mode 100644
index 0000000000000000000000000000000000000000..9cbda6412b3cd12e540c6921a7a441c5f89d8529
--- /dev/null
+++ b/src/proto_alpha/lib_protocol/gas_comparable_input_size.ml
@@ -0,0 +1,142 @@
+(*****************************************************************************)
+(*                                                                           *)
+(* Open Source License                                                       *)
+(* Copyright (c) 2021-2022 Nomadic Labs <contact@nomadic-labs.com>           *)
+(*                                                                           *)
+(* Permission is hereby granted, free of charge, to any person obtaining a   *)
+(* copy of this software and associated documentation files (the "Software"),*)
+(* to deal in the Software without restriction, including without limitation *)
+(* the rights to use, copy, modify, merge, publish, distribute, sublicense,  *)
+(* and/or sell copies of the Software, and to permit persons to whom the     *)
+(* Software is furnished to do so, subject to the following conditions:      *)
+(*                                                                           *)
+(* The above copyright notice and this permission notice shall be included   *)
+(* in all copies or substantial portions of the Software.                    *)
+(*                                                                           *)
+(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*)
+(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,  *)
+(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL   *)
+(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*)
+(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING   *)
+(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER       *)
+(* DEALINGS IN THE SOFTWARE.                                                 *)
+(*                                                                           *)
+(*****************************************************************************)
+
+type t = int
+
+type micheline_size = {traversal : t; int_bytes : t; string_bytes : t}
+
+(* ------------------------------------------------------------------------- *)
+(* encoding *)
+
+let encoding : t Data_encoding.encoding =
+  let open Data_encoding in
+  conv (fun i -> Int64.of_int i) (fun l -> Int64.to_int l) int64
+
+let micheline_size_encoding : micheline_size Data_encoding.encoding =
+  let open Data_encoding in
+  conv
+    (fun {traversal; int_bytes; string_bytes} ->
+      (traversal, int_bytes, string_bytes))
+    (fun (traversal, int_bytes, string_bytes) ->
+      {traversal; int_bytes; string_bytes})
+    (tup3 encoding encoding encoding)
+
+(* ------------------------------------------------------------------------- *)
+
+let zero = 0
+
+let add = ( + )
+
+let pp = Format.pp_print_int
+
+let pp_micheline_size fmtr {traversal; int_bytes; string_bytes} =
+  Format.fprintf
+    fmtr
+    "@[{ traversal = %a;@; int_bytes = %a;@; string_bytes = %a;@,}@]"
+    pp
+    traversal
+    pp
+    int_bytes
+    pp
+    string_bytes
+
+let to_int x = x
+
+let of_int x = x
+
+let unit : t = 1
+
+let integer (i : 'a Alpha_context.Script_int.num) : t =
+  Z.numbits (Alpha_context.Script_int.to_zint i) / 8
+
+let string = String.length
+
+let script_string = Alpha_context.Script_string.length
+
+let bytes (b : Bytes.t) : t = Bytes.length b
+
+let mutez (_tez : Alpha_context.Tez.tez) : t =
+  (* Up to now, mutez are stored on 8 bytes (int64). *)
+  8
+
+let bool (_ : bool) : t = 1
+
+let signature (_signature : Script_typed_ir.Script_signature.t) : t =
+  Script_typed_ir.Script_signature.size
+
+let key_hash (_keyhash : Signature.public_key_hash) : t =
+  Signature.Public_key_hash.size
+
+let public_key (public_key : Signature.public_key) : t =
+  Signature.Public_key.size public_key
+
+let chain_id (_chain_id : Script_typed_ir.Script_chain_id.t) : t =
+  Script_typed_ir.Script_chain_id.size
+
+let address (addr : Script_typed_ir.address) : t =
+  let entrypoint = addr.entrypoint in
+  Signature.Public_key_hash.size
+  + String.length (Alpha_context.Entrypoint.to_string entrypoint)
+
+let tx_rollup_l2_address x =
+  Tx_rollup_l2_address.Indexable.size @@ Indexable.forget x
+
+let timestamp (tstamp : Alpha_context.Script_timestamp.t) : t =
+  Z.numbits (Alpha_context.Script_timestamp.to_zint tstamp) / 8
+
+let rec size_of_comparable_value :
+    type a. a Script_typed_ir.comparable_ty -> a -> t =
+  fun (type a) (wit : a Script_typed_ir.comparable_ty) (v : a) ->
+   match wit with
+   | Never_key -> ( match v with _ -> .)
+   | Unit_key -> unit
+   | Int_key -> integer v
+   | Nat_key -> integer v
+   | String_key -> script_string v
+   | Bytes_key -> bytes v
+   | Mutez_key -> mutez v
+   | Bool_key -> bool v
+   | Key_hash_key -> key_hash v
+   | Timestamp_key -> timestamp v
+   | Address_key -> address v
+   | Tx_rollup_l2_address_key -> tx_rollup_l2_address v
+   | Pair_key (leaf, node, _) ->
+       let (lv, rv) = v in
+       let size =
+         size_of_comparable_value leaf lv + size_of_comparable_value node rv
+       in
+       size + 1
+   | Union_key (left, right, _) ->
+       let size =
+         match v with
+         | L v -> size_of_comparable_value left v
+         | R v -> size_of_comparable_value right v
+       in
+       size + 1
+   | Option_key (ty, _) -> (
+       match v with None -> 1 | Some x -> size_of_comparable_value ty x + 1)
+   | Signature_key -> signature v
+   | Key_key -> public_key v
+   | Chain_id_key -> chain_id v
diff --git a/src/proto_alpha/lib_protocol/gas_comparable_input_size.mli b/src/proto_alpha/lib_protocol/gas_comparable_input_size.mli
new file mode 100644
index 0000000000000000000000000000000000000000..7d697c720bd87024a309275f64562393e9a4d6ae
--- /dev/null
+++ b/src/proto_alpha/lib_protocol/gas_comparable_input_size.mli
@@ -0,0 +1,73 @@
+(*****************************************************************************)
+(*                                                                           *)
+(* Open Source License                                                       *)
+(* Copyright (c) 2022 Nomadic Labs <contact@nomadic-labs.com>                *)
+(*                                                                           *)
+(* Permission is hereby granted, free of charge, to any person obtaining a   *)
+(* copy of this software and associated documentation files (the "Software"),*)
+(* to deal in the Software without restriction, including without limitation *)
+(* the rights to use, copy, modify, merge, publish, distribute, sublicense,  *)
+(* and/or sell copies of the Software, and to permit persons to whom the     *)
+(* Software is furnished to do so, subject to the following conditions:      *)
+(*                                                                           *)
+(* The above copyright notice and this permission notice shall be included   *)
+(* in all copies or substantial portions of the Software.                    *)
+(*                                                                           *)
+(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*)
+(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,  *)
+(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL   *)
+(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*)
+(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING   *)
+(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER       *)
+(* DEALINGS IN THE SOFTWARE.                                                 *)
+(*                                                                           *)
+(*****************************************************************************)
+
+(** [Gas_input_size] includes the definitions for the different sizes used
+    in the gas models of the protocol. They do not always represent memory
+    sizes, but rather they can be seen as an information size. They are
+    tailored to the models that use them, and should not be used for anything
+    other than gas computation.
+
+    [Gas_comparable_input_size] is the restriction of [Gas_input_size] to
+    comparable types.
+ *)
+
+type t = int
+
+type micheline_size = {traversal : t; int_bytes : t; string_bytes : t}
+
+(* ------------------------------------------------------------------------- *)
+(* encoding *)
+
+val encoding : t Data_encoding.encoding
+
+val micheline_size_encoding : micheline_size Data_encoding.encoding
+
+(* ------------------------------------------------------------------------- *)
+
+val zero : t
+
+val add : t -> t -> t
+
+val pp : Format.formatter -> t -> unit
+
+val pp_micheline_size : Format.formatter -> micheline_size -> unit
+
+val to_int : t -> int
+
+val of_int : int -> t
+
+val integer : 'a Alpha_context.Script_int.num -> t
+
+val string : string -> t
+
+val script_string : Alpha_context.Script_string.t -> t
+
+val bytes : Bytes.t -> t
+
+val mutez : Alpha_context.Tez.tez -> t
+
+val timestamp : Alpha_context.Script_timestamp.t -> t
+
+val size_of_comparable_value : 'a Script_typed_ir.comparable_ty -> 'a -> t
diff --git a/src/proto_alpha/lib_protocol/gas_input_size.ml b/src/proto_alpha/lib_protocol/gas_input_size.ml
index fbe12aaa3b27af7368d56bf5cdfaaa78ff3ae0e1..fd3c7495850b975473a6672bff101fe7fc54a4f1 100644
--- a/src/proto_alpha/lib_protocol/gas_input_size.ml
+++ b/src/proto_alpha/lib_protocol/gas_input_size.ml
@@ -23,85 +23,7 @@
 (*                                                                           *)
 (*****************************************************************************)
 
-type t = int
-
-type micheline_size = {traversal : t; int_bytes : t; string_bytes : t}
-
-(* ------------------------------------------------------------------------- *)
-(* encoding *)
-
-let encoding : t Data_encoding.encoding =
-  let open Data_encoding in
-  conv (fun i -> Int64.of_int i) (fun l -> Int64.to_int l) int64
-
-let micheline_size_encoding : micheline_size Data_encoding.encoding =
-  let open Data_encoding in
-  conv
-    (fun {traversal; int_bytes; string_bytes} ->
-      (traversal, int_bytes, string_bytes))
-    (fun (traversal, int_bytes, string_bytes) ->
-      {traversal; int_bytes; string_bytes})
-    (tup3 encoding encoding encoding)
-
-(* ------------------------------------------------------------------------- *)
-
-let zero = 0
-
-let add = ( + )
-
-let pp = Format.pp_print_int
-
-let pp_micheline_size fmtr {traversal; int_bytes; string_bytes} =
-  Format.fprintf
-    fmtr
-    "@[{ traversal = %a;@; int_bytes = %a;@; string_bytes = %a;@,}@]"
-    pp
-    traversal
-    pp
-    int_bytes
-    pp
-    string_bytes
-
-let to_int x = x
-
-let of_int x = x
-
-let unit : t = 1
-
-let integer (i : 'a Alpha_context.Script_int.num) : t =
-  Z.numbits (Alpha_context.Script_int.to_zint i) / 8
-
-let string = String.length
-
-let script_string = Alpha_context.Script_string.length
-
-let bytes (b : Bytes.t) : t = Bytes.length b
-
-let mutez (_tez : Alpha_context.Tez.tez) : t =
-  (* Up to now, mutez are stored on 8 bytes (int64). *)
-  8
-
-let bool (_ : bool) : t = 1
-
-let signature (_signature : Script_typed_ir.Script_signature.t) : t =
-  Script_typed_ir.Script_signature.size
-
-let key_hash (_keyhash : Signature.public_key_hash) : t =
-  Signature.Public_key_hash.size
-
-let public_key (public_key : Signature.public_key) : t =
-  Signature.Public_key.size public_key
-
-let chain_id (_chain_id : Script_typed_ir.Script_chain_id.t) : t =
-  Script_typed_ir.Script_chain_id.size
-
-let address (addr : Script_typed_ir.address) : t =
-  let entrypoint = addr.entrypoint in
-  Signature.Public_key_hash.size
-  + String.length (Alpha_context.Entrypoint.to_string entrypoint)
-
-let tx_rollup_l2_address x =
-  Tx_rollup_l2_address.Indexable.size @@ Indexable.forget x
+include Gas_comparable_input_size
 
 let list (list : 'a Script_typed_ir.boxed_list) : t =
   list.Script_typed_ir.length
@@ -114,44 +36,6 @@ let map (map : ('a, 'b) Script_typed_ir.map) : t =
   let res = Alpha_context.Script_int.to_int (Script_map.size map) in
   match res with None -> assert false | Some x -> x
 
-let timestamp (tstamp : Alpha_context.Script_timestamp.t) : t =
-  Z.numbits (Alpha_context.Script_timestamp.to_zint tstamp) / 8
-
-let rec size_of_comparable_value :
-    type a. a Script_typed_ir.comparable_ty -> a -> t =
-  fun (type a) (wit : a Script_typed_ir.comparable_ty) (v : a) ->
-   match wit with
-   | Never_key -> ( match v with _ -> .)
-   | Unit_key -> unit
-   | Int_key -> integer v
-   | Nat_key -> integer v
-   | String_key -> script_string v
-   | Bytes_key -> bytes v
-   | Mutez_key -> mutez v
-   | Bool_key -> bool v
-   | Key_hash_key -> key_hash v
-   | Timestamp_key -> timestamp v
-   | Address_key -> address v
-   | Tx_rollup_l2_address_key -> tx_rollup_l2_address v
-   | Pair_key (leaf, node, _) ->
-       let (lv, rv) = v in
-       let size =
-         size_of_comparable_value leaf lv + size_of_comparable_value node rv
-       in
-       size + 1
-   | Union_key (left, right, _) ->
-       let size =
-         match v with
-         | L v -> size_of_comparable_value left v
-         | R v -> size_of_comparable_value right v
-       in
-       size + 1
-   | Option_key (ty, _) -> (
-       match v with None -> 1 | Some x -> size_of_comparable_value ty x + 1)
-   | Signature_key -> signature v
-   | Key_key -> public_key v
-   | Chain_id_key -> chain_id v
-
 (* ------------------------------------------------------------------------- *)
 (* Micheline/Michelson-related *)
 
diff --git a/src/proto_alpha/lib_protocol/gas_input_size.mli b/src/proto_alpha/lib_protocol/gas_input_size.mli
index 63faf7611006d2be72c82f262bbbcfe40c72203b..42f80a4c79b8d797c9d3098d345e945f41124b6f 100644
--- a/src/proto_alpha/lib_protocol/gas_input_size.mli
+++ b/src/proto_alpha/lib_protocol/gas_input_size.mli
@@ -30,51 +30,16 @@
     other than gas computation.
  *)
 
-type t = int
-
-type micheline_size = {traversal : t; int_bytes : t; string_bytes : t}
-
-(* ------------------------------------------------------------------------- *)
-(* encoding *)
-
-val encoding : t Data_encoding.encoding
-
-val micheline_size_encoding : micheline_size Data_encoding.encoding
+include module type of Gas_comparable_input_size
 
 (* ------------------------------------------------------------------------- *)
 
-val zero : t
-
-val add : t -> t -> t
-
-val pp : Format.formatter -> t -> unit
-
-val pp_micheline_size : Format.formatter -> micheline_size -> unit
-
-val to_int : t -> int
-
-val of_int : int -> t
-
-val integer : 'a Alpha_context.Script_int.num -> t
-
-val string : string -> t
-
-val script_string : Alpha_context.Script_string.t -> t
-
-val bytes : Bytes.t -> t
-
-val mutez : Alpha_context.Tez.tez -> t
-
 val list : 'a Script_typed_ir.boxed_list -> t
 
 val set : 'a Script_typed_ir.set -> t
 
 val map : ('a, 'b) Script_typed_ir.map -> t
 
-val timestamp : Alpha_context.Script_timestamp.t -> t
-
-val size_of_comparable_value : 'a Script_typed_ir.comparable_ty -> 'a -> t
-
 (* ------------------------------------------------------------------------- *)
 (* Micheline/Michelson-related *)
 
diff --git a/src/proto_alpha/lib_protocol/michelson_v1_gas.ml b/src/proto_alpha/lib_protocol/michelson_v1_gas.ml
index 40940cfcc6213fdcc488508257481ba220721491..62a6d6a16ffd53357df58f1edb253d4fa17d86aa 100644
--- a/src/proto_alpha/lib_protocol/michelson_v1_gas.ml
+++ b/src/proto_alpha/lib_protocol/michelson_v1_gas.ml
@@ -1454,10 +1454,7 @@ module Cost_of = struct
     let set_mem (type a) (elt : a) (set : a Script_typed_ir.set) =
       let open S_syntax in
       let (module Box) = Script_set.get set in
-      let per_elt_cost =
-        Size.size_of_comparable_value Box.elt_ty elt
-        |> Size.to_int |> S.safe_int
-      in
+      let per_elt_cost = Box.OPS.elt_size elt |> Size.to_int |> S.safe_int in
       let size = S.safe_int Box.size in
       let intercept = atomic_step_cost (S.safe_int 115) in
       Gas.(intercept +@ (log2 size *@ per_elt_cost))
@@ -1465,10 +1462,7 @@ module Cost_of = struct
     let set_update (type a) (elt : a) (set : a Script_typed_ir.set) =
       let open S_syntax in
       let (module Box) = Script_set.get set in
-      let per_elt_cost =
-        Size.size_of_comparable_value Box.elt_ty elt
-        |> Size.to_int |> S.safe_int
-      in
+      let per_elt_cost = Box.OPS.elt_size elt |> Size.to_int |> S.safe_int in
       let size = S.safe_int Box.size in
       let intercept = atomic_step_cost (S.safe_int 130) in
       (* The 2 factor reflects the update vs mem overhead as benchmarked
@@ -1478,10 +1472,7 @@ module Cost_of = struct
     let map_mem (type k v) (elt : k) (map : (k, v) Script_typed_ir.map) =
       let open S_syntax in
       let (module Box) = Script_map.get_module map in
-      let per_elt_cost =
-        Size.size_of_comparable_value Box.key_ty elt
-        |> Size.to_int |> S.safe_int
-      in
+      let per_elt_cost = Box.OPS.key_size elt |> Size.to_int |> S.safe_int in
       let size = S.safe_int Box.size in
       let intercept = atomic_step_cost (S.safe_int 80) in
       Gas.(intercept +@ (log2 size *@ per_elt_cost))
@@ -1491,10 +1482,7 @@ module Cost_of = struct
     let map_update (type k v) (elt : k) (map : (k, v) Script_typed_ir.map) =
       let open S_syntax in
       let (module Box) = Script_map.get_module map in
-      let per_elt_cost =
-        Size.size_of_comparable_value Box.key_ty elt
-        |> Size.to_int |> S.safe_int
-      in
+      let per_elt_cost = Box.OPS.key_size elt |> Size.to_int |> S.safe_int in
       let size = S.safe_int Box.size in
       let intercept = atomic_step_cost (S.safe_int 80) in
       (* The 2 factor reflects the update vs mem overhead as benchmarked
@@ -1505,10 +1493,7 @@ module Cost_of = struct
         (map : (k, v) Script_typed_ir.map) =
       let open S_syntax in
       let (module Box) = Script_map.get_module map in
-      let per_elt_cost =
-        Size.size_of_comparable_value Box.key_ty elt
-        |> Size.to_int |> S.safe_int
-      in
+      let per_elt_cost = Box.OPS.key_size elt |> Size.to_int |> S.safe_int in
       let size = S.safe_int Box.size in
       let intercept = atomic_step_cost (S.safe_int 80) in
       (* The 3 factor reflects the update vs mem overhead as benchmarked
diff --git a/src/proto_alpha/lib_protocol/script_interpreter.ml b/src/proto_alpha/lib_protocol/script_interpreter.ml
index 9dbd9c8ee05b1b47ff467d2a4e149c582cfba427..83670f16d3be5f9607f633e18d4d3fe1c04c1d52 100644
--- a/src/proto_alpha/lib_protocol/script_interpreter.ml
+++ b/src/proto_alpha/lib_protocol/script_interpreter.ml
@@ -400,7 +400,7 @@ and imap_map : type a b c d e f g h i. (a, b, c, d, e, f, g, h, i) imap_map_type
  fun log_if_needed g gas (body, k) ks accu stack ->
   let map = accu in
   let xs = List.rev (Script_map.fold (fun k v a -> (k, v) :: a) map []) in
-  let ys = Script_map.(empty @@ key_ty map) in
+  let ys = Script_map.empty_from map in
   let ks = log_if_needed (KMap_enter_body (body, xs, ys, KCons (k, ks))) in
   let (accu, stack) = stack in
   (next [@ocaml.tailcall]) g gas ks accu stack
diff --git a/src/proto_alpha/lib_protocol/script_ir_translator.ml b/src/proto_alpha/lib_protocol/script_ir_translator.ml
index a825b7d5760a77db2dcca26d9c4d81d0e397a3e7..5a0946b78f0aec850008a5fa4dd1ad94c369d65b 100644
--- a/src/proto_alpha/lib_protocol/script_ir_translator.ml
+++ b/src/proto_alpha/lib_protocol/script_ir_translator.ml
@@ -6179,8 +6179,6 @@ let[@coq_axiom_with_reason "gadt"] extract_lazy_storage_updates ctxt mode
 
           type value = M.value
 
-          let key_ty = M.key_ty
-
           let boxed = m
 
           let size = M.size
diff --git a/src/proto_alpha/lib_protocol/script_map.ml b/src/proto_alpha/lib_protocol/script_map.ml
index 91a123ab9bc29f1586ed0ca48053eb4d545f65e2..5a96396a518b5a4f0b6afc90225832ecd914fff9 100644
--- a/src/proto_alpha/lib_protocol/script_map.ml
+++ b/src/proto_alpha/lib_protocol/script_map.ml
@@ -32,31 +32,39 @@ let make x = Map_tag x
 
 let get_module (Map_tag x) = x
 
-let key_ty : type a b. (a, b) map -> a comparable_ty =
- fun (Map_tag (module Box)) -> Box.key_ty
+let empty_from : type a b c. (a, b) map -> (a, c) map =
+ fun (Map_tag (module Box)) ->
+  Map_tag
+    (module struct
+      type key = a
+
+      type value = c
+
+      module OPS = Box.OPS
+
+      let boxed = OPS.empty
+
+      let size = 0
+    end)
 
 let empty : type a b. a comparable_ty -> (a, b) map =
  fun ty ->
-  let module OPS = Map.Make (struct
-    type t = a
+  let module OPS = struct
+    let key_size = Gas_comparable_input_size.size_of_comparable_value ty
 
-    let compare = Script_comparable.compare_comparable ty
-  end) in
+    include Map.Make (struct
+      type t = a
+
+      let compare = Script_comparable.compare_comparable ty
+    end)
+  end in
   Map_tag
     (module struct
       type key = a
 
       type value = b
 
-      let key_ty = ty
-
-      module OPS = struct
-        type value = b
-
-        include OPS
-
-        type nonrec t = value t
-      end
+      module OPS = OPS
 
       let boxed = OPS.empty
 
@@ -82,8 +90,6 @@ let update : type a b. a -> b option -> (a, b) map -> (a, b) map =
 
       type value = b
 
-      let key_ty = Box.key_ty
-
       module OPS = Box.OPS
 
       let boxed = boxed
diff --git a/src/proto_alpha/lib_protocol/script_map.mli b/src/proto_alpha/lib_protocol/script_map.mli
index 6adfb78ed14cae7cb22dc2d4eed29621f98c4394..5a52c8b0b16f87d59562cacc1d243d8f0acffeae 100644
--- a/src/proto_alpha/lib_protocol/script_map.mli
+++ b/src/proto_alpha/lib_protocol/script_map.mli
@@ -37,6 +37,8 @@ val get_module :
 
 val empty : 'a comparable_ty -> ('a, 'b) map
 
+val empty_from : ('a, 'b) map -> ('a, 'c) map
+
 val fold :
   ('key -> 'value -> 'acc -> 'acc) -> ('key, 'value) map -> 'acc -> 'acc
 
@@ -52,6 +54,4 @@ val mem : 'key -> ('key, 'value) map -> bool
 
 val get : 'key -> ('key, 'value) map -> 'value option
 
-val key_ty : ('a, 'b) map -> 'a comparable_ty
-
 val size : ('a, 'b) map -> Script_int.n Script_int.num
diff --git a/src/proto_alpha/lib_protocol/script_set.ml b/src/proto_alpha/lib_protocol/script_set.ml
index eb54bb8cb2b993bf328ea24598c03231d9391df5..22a37d1cc10d763055a3322625c4fb8a739e916f 100644
--- a/src/proto_alpha/lib_protocol/script_set.ml
+++ b/src/proto_alpha/lib_protocol/script_set.ml
@@ -34,17 +34,19 @@ let get (Set_tag x) = x
 
 let empty : type a. a comparable_ty -> a set =
  fun ty ->
-  let module OPS : Boxed_set_OPS with type elt = a = Set.Make (struct
-    type t = a
+  let module OPS : Boxed_set_OPS with type elt = a = struct
+    let elt_size = Gas_comparable_input_size.size_of_comparable_value ty
 
-    let compare = Script_comparable.compare_comparable ty
-  end) in
+    include Set.Make (struct
+      type t = a
+
+      let compare = Script_comparable.compare_comparable ty
+    end)
+  end in
   Set_tag
     (module struct
       type elt = a
 
-      let elt_ty = ty
-
       module OPS = OPS
 
       let boxed = OPS.empty
@@ -58,8 +60,6 @@ let update : type a. a -> bool -> a set -> a set =
     (module struct
       type elt = a
 
-      let elt_ty = Box.elt_ty
-
       module OPS = Box.OPS
 
       let boxed =
diff --git a/src/proto_alpha/lib_protocol/script_typed_ir.ml b/src/proto_alpha/lib_protocol/script_typed_ir.ml
index 4c26d7f953ac68752fe27a9bbc344f8352ff2695..381135a95b444a7f2ab9f0789b76a87443d64178 100644
--- a/src/proto_alpha/lib_protocol/script_typed_ir.ml
+++ b/src/proto_alpha/lib_protocol/script_typed_ir.ml
@@ -416,6 +416,8 @@ module type Boxed_set_OPS = sig
 
   type elt
 
+  val elt_size : elt -> int (* Gas_input_size.t *)
+
   val empty : t
 
   val add : elt -> t -> t
@@ -430,8 +432,6 @@ end
 module type Boxed_set = sig
   type elt
 
-  val elt_ty : elt comparable_ty
-
   module OPS : Boxed_set_OPS with type elt = elt
 
   val boxed : OPS.t
@@ -448,24 +448,27 @@ type 'elt set = Set_tag of (module Boxed_set with type elt = 'elt)
 
 *)
 module type Boxed_map_OPS = sig
-  type t
+  type 'a t
 
   type key
 
-  type value
+  val key_size : key -> int (* Gas_input_size.t *)
 
-  val empty : t
+  val empty : 'value t
 
-  val add : key -> value -> t -> t
+  val add : key -> 'value -> 'value t -> 'value t
 
-  val remove : key -> t -> t
+  val remove : key -> 'value t -> 'value t
 
-  val find : key -> t -> value option
+  val find : key -> 'value t -> 'value option
 
-  val fold : (key -> value -> 'a -> 'a) -> t -> 'a -> 'a
+  val fold : (key -> 'value -> 'a -> 'a) -> 'value t -> 'a -> 'a
 
   val fold_es :
-    (key -> value -> 'a -> 'a tzresult Lwt.t) -> t -> 'a -> 'a tzresult Lwt.t
+    (key -> 'value -> 'a -> 'a tzresult Lwt.t) ->
+    'value t ->
+    'a ->
+    'a tzresult Lwt.t
 end
 
 module type Boxed_map = sig
@@ -473,11 +476,9 @@ module type Boxed_map = sig
 
   type value
 
-  val key_ty : key comparable_ty
+  module OPS : Boxed_map_OPS with type key = key
 
-  module OPS : Boxed_map_OPS with type key = key and type value = value
-
-  val boxed : OPS.t
+  val boxed : value OPS.t
 
   val size : int
 end
diff --git a/src/proto_alpha/lib_protocol/script_typed_ir.mli b/src/proto_alpha/lib_protocol/script_typed_ir.mli
index f26f085115afce36db47127796465ef93f14de1c..ad1280a530ed9f3868cb5e0eeaa440cb8eda8b72 100644
--- a/src/proto_alpha/lib_protocol/script_typed_ir.mli
+++ b/src/proto_alpha/lib_protocol/script_typed_ir.mli
@@ -274,6 +274,8 @@ module type Boxed_set_OPS = sig
 
   type elt
 
+  val elt_size : elt -> int (* Gas_input_size.t *)
+
   val empty : t
 
   val add : elt -> t -> t
@@ -288,8 +290,6 @@ end
 module type Boxed_set = sig
   type elt
 
-  val elt_ty : elt comparable_ty
-
   module OPS : Boxed_set_OPS with type elt = elt
 
   val boxed : OPS.t
@@ -303,24 +303,27 @@ type 'elt set = Set_tag of (module Boxed_set with type elt = 'elt)
 [@@ocaml.unboxed]
 
 module type Boxed_map_OPS = sig
-  type t
+  type 'a t
 
   type key
 
-  type value
+  val key_size : key -> int (* Gas_input_size.t *)
 
-  val empty : t
+  val empty : 'value t
 
-  val add : key -> value -> t -> t
+  val add : key -> 'value -> 'value t -> 'value t
 
-  val remove : key -> t -> t
+  val remove : key -> 'value t -> 'value t
 
-  val find : key -> t -> value option
+  val find : key -> 'value t -> 'value option
 
-  val fold : (key -> value -> 'a -> 'a) -> t -> 'a -> 'a
+  val fold : (key -> 'value -> 'a -> 'a) -> 'value t -> 'a -> 'a
 
   val fold_es :
-    (key -> value -> 'a -> 'a tzresult Lwt.t) -> t -> 'a -> 'a tzresult Lwt.t
+    (key -> 'value -> 'a -> 'a tzresult Lwt.t) ->
+    'value t ->
+    'a ->
+    'a tzresult Lwt.t
 end
 
 module type Boxed_map = sig
@@ -328,11 +331,9 @@ module type Boxed_map = sig
 
   type value
 
-  val key_ty : key comparable_ty
+  module OPS : Boxed_map_OPS with type key = key
 
-  module OPS : Boxed_map_OPS with type key = key and type value = value
-
-  val boxed : OPS.t
+  val boxed : value OPS.t
 
   val size : int
 end