diff --git a/manifest/main.ml b/manifest/main.ml
index ebaf2d2b1e5692f63bcf37410806dcd5dc23b5d5..a4b817f36afd66ab00e56eb634c51054711a39ed 100644
--- a/manifest/main.ml
+++ b/manifest/main.ml
@@ -5604,7 +5604,7 @@ let _octez_shell_tests =
       "test_shell";
       "test_synchronisation_heuristic_fuzzy";
       "test_shell_operation";
-      "test_prevalidation_t";
+      "test_prevalidation";
       "test_prevalidator_classification";
       "test_prevalidator_classification_operations";
       "test_prevalidator_pending_operations";
diff --git a/src/lib_shell/prevalidation.ml b/src/lib_shell/prevalidation.ml
index 0d9183b35290b27b1122903fd5fada2cbafca00e..5cc4c5b31c5d967364a6f5148bcce4990e308e53 100644
--- a/src/lib_shell/prevalidation.ml
+++ b/src/lib_shell/prevalidation.ml
@@ -27,53 +27,6 @@
 
 open Shell_operation
 
-type error +=
-  | Operation_replacement of {
-      old_hash : Operation_hash.t;
-      new_hash : Operation_hash.t;
-    }
-  | Operation_conflict of {new_hash : Operation_hash.t}
-
-let () =
-  register_error_kind
-    `Temporary
-    ~id:"prevalidation.operation_replacement"
-    ~title:"Operation replacement"
-    ~description:"The operation has been replaced."
-    ~pp:(fun ppf (old_hash, new_hash) ->
-      Format.fprintf
-        ppf
-        "The operation %a has been replaced with %a."
-        Operation_hash.pp
-        old_hash
-        Operation_hash.pp
-        new_hash)
-    (Data_encoding.obj2
-       (Data_encoding.req "old_hash" Operation_hash.encoding)
-       (Data_encoding.req "new_hash" Operation_hash.encoding))
-    (function
-      | Operation_replacement {old_hash; new_hash} -> Some (old_hash, new_hash)
-      | _ -> None)
-    (fun (old_hash, new_hash) -> Operation_replacement {old_hash; new_hash}) ;
-  register_error_kind
-    `Temporary
-    ~id:"prevalidation.operation_conflict"
-    ~title:"Operation conflict"
-    ~description:
-      "The operation cannot be added because the mempool already contains a \
-       conflicting operation."
-    ~pp:(fun ppf new_hash ->
-      Format.fprintf
-        ppf
-        "The operation %a cannot be added because the mempool already contains \
-         a conflicting operation that should not be replaced (e.g. an \
-         operation from the same manager with better fees)."
-        Operation_hash.pp
-        new_hash)
-    (Data_encoding.obj1 (Data_encoding.req "new_hash" Operation_hash.encoding))
-    (function Operation_conflict {new_hash} -> Some new_hash | _ -> None)
-    (fun new_hash -> Operation_conflict {new_hash})
-
 module type CHAIN_STORE = sig
   type chain_store
 
@@ -119,14 +72,14 @@ module type T = sig
     | Prevalidator_classification.error_classification ]
     Lwt.t
 
-  type replacement =
-    (Operation_hash.t * Prevalidator_classification.error_classification) option
+  type replacements =
+    (Operation_hash.t * Prevalidator_classification.error_classification) list
 
   type add_result =
     t
     * protocol_operation operation
     * Prevalidator_classification.classification
-    * replacement
+    * replacements
 
   val add_operation :
     t -> filter_config -> protocol_operation operation -> add_result Lwt.t
@@ -225,7 +178,9 @@ module MakeAbstract (Chain_store : CHAIN_STORE) (Filter : Shell_plugin.FILTER) :
 
   type replacement = (Operation_hash.t * error_classification) option
 
-  type add_result = t * operation * classification * replacement
+  type replacements = (Operation_hash.t * error_classification) list
+
+  type add_result = t * operation * classification * replacements
 
   let classification_of_trace trace =
     match classify_trace trace with
@@ -237,7 +192,7 @@ module MakeAbstract (Chain_store : CHAIN_STORE) (Filter : Shell_plugin.FILTER) :
   let proto_add_operation ~conflict_handler state op :
       (Proto.Mempool.t * Proto.Mempool.add_result) tzresult Lwt.t =
     Proto.Mempool.add_operation
-      ~check_signature:Compare.Int.(op.count_successful_prechecks <= 0)
+      ~check_signature:(not op.signature_checked)
       ~conflict_handler
       state.validation_info
       state.mempool
@@ -254,6 +209,7 @@ module MakeAbstract (Chain_store : CHAIN_STORE) (Filter : Shell_plugin.FILTER) :
   let translate_proto_add_result (proto_add_result : Proto.Mempool.add_result)
       op : (replacement, error_classification) result =
     let open Result in
+    let open Validation_errors in
     match proto_add_result with
     | Added -> return_none
     | Replaced {removed} ->
@@ -279,7 +235,7 @@ module MakeAbstract (Chain_store : CHAIN_STORE) (Filter : Shell_plugin.FILTER) :
       protocol's abstract [mempool].
 
       Return the updated [state] (containing the updated protocol
-      [mempool]) and [filter_state], and the final [replacement], which
+      [mempool]) and [filter_state], and the final [replacements], which
       may have been mandated either by the protocol's [add_operation]
       or by [Filter.Mempool.add_operation_and_enforce_mempool_bound]
       (but not both: if the protocol already causes a replacement, then
@@ -287,7 +243,7 @@ module MakeAbstract (Chain_store : CHAIN_STORE) (Filter : Shell_plugin.FILTER) :
       [full_mempool_replacement]. *)
   let enforce_mempool_bound_and_update_states state filter_config
       (mempool, proto_add_result) op :
-      (t * replacement, error_classification) result Lwt.t =
+      (t * replacements, error_classification) result Lwt.t =
     let open Lwt_result_syntax in
     let*? proto_replacement = translate_proto_add_result proto_add_result op in
     let* filter_state, full_mempool_replacement =
@@ -303,19 +259,19 @@ module MakeAbstract (Chain_store : CHAIN_STORE) (Filter : Shell_plugin.FILTER) :
       | `Replace (replace_oph, _) ->
           Proto.Mempool.remove_operation mempool replace_oph
     in
-    let replacement =
+    let replacements =
       match (proto_replacement, full_mempool_replacement) with
-      | _, `No_replace -> proto_replacement
-      | None, `Replace repl -> Some repl
+      | _, `No_replace -> Option.to_list proto_replacement
+      | None, `Replace repl -> [repl]
       | Some _, `Replace _ ->
           (* If there is a [proto_replacement], it gets removed from the
              mempool before adding [op] so the mempool cannot be full. *)
           assert false
     in
-    return ({state with mempool; filter_state}, replacement)
+    return ({state with mempool; filter_state}, replacements)
 
   let add_operation_result state filter_config op :
-      (t * operation * classification * replacement) tzresult Lwt.t =
+      (t * operation * classification * replacements) tzresult Lwt.t =
     let open Lwt_result_syntax in
     let conflict_handler = Filter.Mempool.conflict_handler filter_config in
     let* proto_output = proto_add_operation ~conflict_handler state op in
@@ -324,10 +280,9 @@ module MakeAbstract (Chain_store : CHAIN_STORE) (Filter : Shell_plugin.FILTER) :
        full and the operation does not have enough fees. Nevertheless,
        the successful call to [Proto.Mempool.add_operation] guarantees
        that the operation is individually valid, in particular its
-       signature is correct. Therefore we increment its successful
-       precheck counter, so that any future signature check can be
-       skipped. *)
-    let op = increment_successful_precheck op in
+       signature is correct. We record this so that any future
+       signature check can be skipped. *)
+    let op = record_successful_signature_check op in
     let*! res =
       enforce_mempool_bound_and_update_states
         state
@@ -337,7 +292,7 @@ module MakeAbstract (Chain_store : CHAIN_STORE) (Filter : Shell_plugin.FILTER) :
     in
     match res with
     | Ok (state, replacement) -> return (state, op, `Prechecked, replacement)
-    | Error err_class -> return (state, op, (err_class :> classification), None)
+    | Error err_class -> return (state, op, (err_class :> classification), [])
 
   let add_operation state filter_config op : add_result Lwt.t =
     let open Lwt_syntax in
@@ -346,7 +301,7 @@ module MakeAbstract (Chain_store : CHAIN_STORE) (Filter : Shell_plugin.FILTER) :
     in
     match res with
     | Ok add_result -> return add_result
-    | Error trace -> return (state, op, classification_of_trace trace, None)
+    | Error trace -> return (state, op, classification_of_trace trace, [])
 
   let remove_operation state oph =
     let mempool = Proto.Mempool.remove_operation state.mempool oph in
diff --git a/src/lib_shell/prevalidation.mli b/src/lib_shell/prevalidation.mli
index bc830ebf3f094f79584e7cbe98b9345bf5d0088e..d90d52e91ac75d4ee843fb9368a273611e377e84 100644
--- a/src/lib_shell/prevalidation.mli
+++ b/src/lib_shell/prevalidation.mli
@@ -89,26 +89,26 @@ module type T = sig
     | Prevalidator_classification.error_classification ]
     Lwt.t
 
-  (** If an old operation has been replaced by a newly added
-      operation, then this type contains its hash and its new
-      classification. If there is no replaced operation, this is [None]. *)
-  type replacement =
-    (Operation_hash.t * Prevalidator_classification.error_classification) option
+  (** Contain the hash and new classification of any operations that
+      had to be removed to make room for the newly validated
+      operation. *)
+  type replacements =
+    (Operation_hash.t * Prevalidator_classification.error_classification) list
 
   (** Result of {!add_operation}.
 
       Contain the updated (or unchanged) state {!t},
       the operation (in which [count_successful_prechecks]
       has been incremented if appropriate), its classification,
-      and the potential {!replacement}.
+      and the potential {!replacements}.
 
-      Invariant: [replacement] can only be [Some _] when the
+      Invariant: [replacements] can only be non-empty when the
       classification is [`Prechecked]. *)
   type add_result =
     t
     * protocol_operation Shell_operation.operation
     * Prevalidator_classification.classification
-    * replacement
+    * replacements
 
   (** Call the protocol [Mempool.add_operation] function, providing it
       with the [conflict_handler] from the plugin.
diff --git a/src/lib_shell/prevalidator_internal.ml b/src/lib_shell/prevalidator_internal.ml
index a9c538a8ab10881edc385e4150c36a9763a79101..03e255d1213cdea0d13c13f8745d6f40902786cc 100644
--- a/src/lib_shell/prevalidator_internal.ml
+++ b/src/lib_shell/prevalidator_internal.ml
@@ -366,20 +366,19 @@ module Make_s
       remove_from_advertisement old_hash shell.advertisement ;
     match Classification.remove old_hash shell.classification with
     | Some (op, _class) ->
-        [(op, (replacement_classification :> Classification.classification))]
+        Some (op, (replacement_classification :> Classification.classification))
     | None ->
         (* This case should not happen. *)
         shell.parameters.tools.chain_tools.clear_or_cancel old_hash ;
-        []
+        None
 
   (* Determine the classification of a given operation in the current
-     filter/validation states, i.e. whether it could be included in a
+     validation state, i.e. whether it could be included in a
      block on top of the current head, and if not, why. If yes, the
      operation is accumulated in the given [mempool].
 
      The function returns a tuple
-     [(filter_state, validation_state, mempool, to_handle)], where:
-     - [filter_state] is the (possibly) updated filter_state,
+     [(validation_state, mempool, to_handle)], where:
      - [validation_state] is the (possibly) updated validation_state,
      - [mempool] is the (possibly) updated mempool,
      - [to_handle] contains the given operation and its classification, and all
@@ -392,17 +391,14 @@ module Make_s
       * (protocol_operation operation * Classification.classification) trace)
       Lwt.t =
     let open Lwt_syntax in
-    let* v_state, op, classification, replacement =
+    let* v_state, op, classification, replacements =
       Prevalidation_t.add_operation validation_state filter_config op
     in
     let to_replace =
-      match replacement with
-      | None -> []
-      | Some (old_oph, replacement_classification) ->
-          reclassify_replaced_manager_op
-            old_oph
-            shell
-            replacement_classification
+      List.filter_map
+        (fun (replaced_oph, new_classification) ->
+          reclassify_replaced_manager_op replaced_oph shell new_classification)
+        replacements
     in
     let to_handle = (op, classification) :: to_replace in
     let mempool =
diff --git a/src/lib_shell/shell_operation.ml b/src/lib_shell/shell_operation.ml
index 03bab55f3477e5a61770cb2ad6e03a543952ca9d..330f155077d180b48371d321eb331dea2ce65794 100644
--- a/src/lib_shell/shell_operation.ml
+++ b/src/lib_shell/shell_operation.ml
@@ -29,18 +29,10 @@ type 'protocol_operation operation = {
   hash : Operation_hash.t;
   raw : Operation.t;
   protocol : 'protocol_operation;
-  count_successful_prechecks : int;
+  signature_checked : bool;
 }
 
-let increment_successful_precheck op =
-  (* We avoid {op with ...} to get feedback from the compiler if the record
-     type is extended/modified in the future. *)
-  {
-    hash = op.hash;
-    raw = op.raw;
-    protocol = op.protocol;
-    count_successful_prechecks = op.count_successful_prechecks + 1;
-  }
+let record_successful_signature_check op = {op with signature_checked = true}
 
 (** Doesn't depend on heavy [Registered_protocol.T] for testability. *)
 let safe_binary_of_bytes (encoding : 'a Data_encoding.t) (bytes : bytes) :
@@ -77,9 +69,7 @@ module MakeParser (Proto : Tezos_protocol_environment.PROTOCOL) :
         hash;
         raw;
         protocol = {Proto.shell = raw.Operation.shell; protocol_data};
-        (* When an operation is parsed, we assume that it has never been
-           successfully prechecked. *)
-        count_successful_prechecks = 0;
+        signature_checked = false;
       }
 end
 
@@ -89,9 +79,7 @@ module Internal_for_tests = struct
   let hash_of {hash; _} = hash
 
   let make_operation op oph data =
-    (* When we build an operation, we assume that it has never been
-       successfully prechecked. *)
-    {hash = oph; raw = op; protocol = data; count_successful_prechecks = 0}
+    {hash = oph; raw = op; protocol = data; signature_checked = false}
 
   let safe_binary_of_bytes = safe_binary_of_bytes
 end
diff --git a/src/lib_shell/shell_operation.mli b/src/lib_shell/shell_operation.mli
index 9fbea1aded360599cc11ec35303d53e56266a7c3..defb30d8dd72626cb065453bb5a9a3bc384a92dd 100644
--- a/src/lib_shell/shell_operation.mli
+++ b/src/lib_shell/shell_operation.mli
@@ -40,20 +40,17 @@ type 'protocol_operation operation = private {
           unserialized representation of [raw.protocol_data]. For
           convenience, the type associated to this type may be [unit] if we
           do not have deserialized the operation yet. *)
-  count_successful_prechecks : int;
-      (** This field provides an under-approximation for the number of times
-          the operation has been successfully prechecked. It is an
-          under-approximation because if the operation is e.g., parsed more than
-          once, or is prechecked in other modes, this flag is not globally
-          updated. *)
+  signature_checked : bool;
+      (** This field is initially [false]. It is set to [true] when the
+          operation is successfully validated in any context. While this does
+          not guarantee that the operation will still be valid in another
+          validation context, it notably means that the signature is
+          correct. Therefore, when this field is [true], we can tell the
+          protocol to skip signature checks. *)
 }
 
-(** [increment_successful_precheck op] increments the field
-    [count_successful_prechecks] of the given operation [op]. It is supposed
-    to be called after each successful precheck of a given operation [op],
-    and nowhere else. Overflow is unlikely to occur in practice, as the
-    counter grows very slowly and the number of prechecks is bounded. *)
-val increment_successful_precheck :
+(** Return the operation with the {!signature_checked} field set to [true]. *)
+val record_successful_signature_check :
   'protocol_operation operation -> 'protocol_operation operation
 
 (** The purpose of this module type is to provide the [parse]
diff --git a/src/lib_shell/test/dune b/src/lib_shell/test/dune
index 6950d02b145c41f4e6697e991d750550e3a27caf..6bf2e9f5f9cdfacc1494a3b61c94c7bf83afd3b8 100644
--- a/src/lib_shell/test/dune
+++ b/src/lib_shell/test/dune
@@ -6,7 +6,7 @@
   test_shell
   test_synchronisation_heuristic_fuzzy
   test_shell_operation
-  test_prevalidation_t
+  test_prevalidation
   test_prevalidator_classification
   test_prevalidator_classification_operations
   test_prevalidator_pending_operations
@@ -68,7 +68,7 @@
 (rule
  (alias runtest)
  (package tezos-shell)
- (action (run %{dep:./test_prevalidation_t.exe})))
+ (action (run %{dep:./test_prevalidation.exe})))
 
 (rule
  (alias runtest)
diff --git a/src/lib_shell/test/test_prevalidation_t.ml b/src/lib_shell/test/test_prevalidation.ml
similarity index 98%
rename from src/lib_shell/test/test_prevalidation_t.ml
rename to src/lib_shell/test/test_prevalidation.ml
index db035ce781f3c31cec8da09fd1c3f040ca2f55c5..979eb289805fbe665d1c3094d55fd71e2bf0bcf5 100644
--- a/src/lib_shell/test/test_prevalidation_t.ml
+++ b/src/lib_shell/test/test_prevalidation.ml
@@ -26,7 +26,7 @@
 (** Testing
     -------
     Component:    Prevalidation
-    Invocation:   dune exec src/lib_shell/test/test_prevalidation_t.exe
+    Invocation:   dune exec src/lib_shell/test/test_prevalidation.exe
     Subject:      Unit tests for {!Prevalidation.T}
 *)
 
@@ -486,7 +486,7 @@ let test_add_operation ctxt =
     let*! ( state,
             (_op : Mock_protocol.operation Shell_operation.operation),
             classification,
-            replacement ) =
+            replacements ) =
       P.add_operation state filter_outcome op
     in
     (* Check the classification. *)
@@ -511,13 +511,13 @@ let test_add_operation ctxt =
     | Proto_added, F_no_replace ->
         assert (Operation_hash.Map.mem op.hash valid_ops) ;
         assert (Operation_hash.Set.mem op.hash filter_state) ;
-        assert (Option.is_none replacement)
+        assert (List.is_empty replacements)
     | Proto_added, F_replace | Proto_replaced, F_no_replace -> (
         assert (Operation_hash.Map.mem op.hash valid_ops) ;
         assert (Operation_hash.Set.mem op.hash filter_state) ;
-        match replacement with
-        | None -> assert false
-        | Some (removed, _) ->
+        match replacements with
+        | [] | _ :: _ :: _ -> assert false
+        | [(removed, _)] ->
             assert (Operation_hash.Map.mem removed valid_ops_before) ;
             assert (Operation_hash.Set.mem removed filter_state_before) ;
             assert (not (Operation_hash.Map.mem removed valid_ops)) ;
@@ -527,7 +527,7 @@ let test_add_operation ctxt =
     | _ ->
         assert (not (Operation_hash.Map.mem op.hash valid_ops)) ;
         assert (not (Operation_hash.Set.mem op.hash filter_state)) ;
-        assert (Option.is_none replacement)) ;
+        assert (List.is_empty replacements)) ;
     Lwt.return state
   in
   let timestamp : Time.Protocol.t = now () in
@@ -659,10 +659,10 @@ let () =
     "mempool-prevalidation"
     [
       (* Run only those tests with:
-         dune exec src/lib_shell/test/test_prevalidation_t.exe -- test create '0' *)
+         dune exec src/lib_shell/test/test_prevalidation.exe -- test create '0' *)
       ("create", [register_test "[create] succeeds" test_create]);
       (* Run only those tests with:
-         dune exec src/lib_shell/test/test_prevalidation_t.exe -- test add_operation '0' *)
+         dune exec src/lib_shell/test/test_prevalidation.exe -- test add_operation '0' *)
       ( "add_operation",
         [
           register_test
@@ -670,7 +670,7 @@ let () =
             test_add_operation;
         ] );
       (* Run only those tests with:
-         dune exec src/lib_shell/test/test_prevalidation_t.exe -- test remove_operation '0' *)
+         dune exec src/lib_shell/test/test_prevalidation.exe -- test remove_operation '0' *)
       ( "remove_operation",
         [register_test "Test remove_operation" test_remove_operation] );
     ]
diff --git a/src/lib_shell_services/validation_errors.ml b/src/lib_shell_services/validation_errors.ml
index 86b4c95a87d6350283e35c2be8e2a9ba8a5b960f..374c1fccd3986ae31f70c797187c32039398f402 100644
--- a/src/lib_shell_services/validation_errors.ml
+++ b/src/lib_shell_services/validation_errors.ml
@@ -28,6 +28,13 @@
 
 type error += Parse_error
 
+type error +=
+  | Operation_conflict of {new_hash : Operation_hash.t}
+  | Operation_replacement of {
+      old_hash : Operation_hash.t;
+      new_hash : Operation_hash.t;
+    }
+
 type error += Too_many_operations
 
 type error += Oversized_operation of {size : int; max : int}
@@ -55,6 +62,46 @@ let () =
     Data_encoding.empty
     (function Parse_error -> Some () | _ -> None)
     (fun () -> Parse_error) ;
+  (* Operation conflict *)
+  register_error_kind
+    `Temporary
+    ~id:"prevalidation.operation_conflict"
+    ~title:"Operation conflict"
+    ~description:
+      "The operation cannot be added because the mempool already contains a \
+       conflicting operation."
+    ~pp:(fun ppf new_hash ->
+      Format.fprintf
+        ppf
+        "The operation %a cannot be added because the mempool already contains \
+         a conflicting operation that should not be replaced (e.g. an \
+         operation from the same manager with better fees)."
+        Operation_hash.pp
+        new_hash)
+    (Data_encoding.obj1 (Data_encoding.req "new_hash" Operation_hash.encoding))
+    (function Operation_conflict {new_hash} -> Some new_hash | _ -> None)
+    (fun new_hash -> Operation_conflict {new_hash}) ;
+  (* Operation replacement *)
+  register_error_kind
+    `Temporary
+    ~id:"prevalidation.operation_replacement"
+    ~title:"Operation replacement"
+    ~description:"The operation has been replaced."
+    ~pp:(fun ppf (old_hash, new_hash) ->
+      Format.fprintf
+        ppf
+        "The operation %a has been replaced with %a."
+        Operation_hash.pp
+        old_hash
+        Operation_hash.pp
+        new_hash)
+    (Data_encoding.obj2
+       (Data_encoding.req "old_hash" Operation_hash.encoding)
+       (Data_encoding.req "new_hash" Operation_hash.encoding))
+    (function
+      | Operation_replacement {old_hash; new_hash} -> Some (old_hash, new_hash)
+      | _ -> None)
+    (fun (old_hash, new_hash) -> Operation_replacement {old_hash; new_hash}) ;
   (* Too many operations *)
   register_error_kind
     `Temporary
diff --git a/src/lib_shell_services/validation_errors.mli b/src/lib_shell_services/validation_errors.mli
index b182a73cce9c9bebf928e4c9aa0ed279fe335cce..906477663a5100f3236fc7f8dbcb84b46145369e 100644
--- a/src/lib_shell_services/validation_errors.mli
+++ b/src/lib_shell_services/validation_errors.mli
@@ -28,6 +28,13 @@
 
 type error += Parse_error
 
+type error +=
+  | Operation_conflict of {new_hash : Operation_hash.t}
+  | Operation_replacement of {
+      old_hash : Operation_hash.t;
+      new_hash : Operation_hash.t;
+    }
+
 type error += Too_many_operations
 
 type error += Oversized_operation of {size : int; max : int}