diff --git a/CHANGES.rst b/CHANGES.rst
index 4b1106edd3de6495e2b328e9951de5d536397f94..e84b9dd15d7cd6369c750b743d61987da9a90df3 100644
--- a/CHANGES.rst
+++ b/CHANGES.rst
@@ -231,6 +231,9 @@ Node
 
 - Removed Mumbai mempool plugin. (MR :gl:`!9696`)
 
+- Operations posting invalid WASM proofs are now discarded earlier by the
+  Nairobi mempool plugin. (MR :gl:`!`)
+
 Client
 ------
 - Adding client commands to generate, open and verify a time-lock.
diff --git a/src/lib_shell/prevalidation.ml b/src/lib_shell/prevalidation.ml
index 661deb70bd62a44a48c84af87e8cb88804a3f78f..8081b3aef73c144b83df934c2d47fbf72d5265bb 100644
--- a/src/lib_shell/prevalidation.ml
+++ b/src/lib_shell/prevalidation.ml
@@ -176,7 +176,9 @@ module MakeAbstract
     create_aux ~old_state chain_store head timestamp
 
   let pre_filter state (filter_config, (_ : Prevalidator_bounding.config)) op =
-    match Proto.Plugin.syntactic_check op.protocol with
+    let open Lwt_syntax in
+    let* status = Proto.Plugin.syntactic_check op.protocol in
+    match status with
     | `Ill_formed ->
         Lwt.return
           (`Refused
diff --git a/src/lib_validation/block_validation.ml b/src/lib_validation/block_validation.ml
index 9e582d916ccfcfeebee636dcd73a39d943d3d1e8..c1c1fa1e7ade2b8f1f278543415799f735ca25a5 100644
--- a/src/lib_validation/block_validation.ml
+++ b/src/lib_validation/block_validation.ml
@@ -896,8 +896,9 @@ module Make (Proto : Protocol_plugin.T) = struct
               {shell = op.raw.shell; protocol_data = op.protocol_data}
             in
             let open Lwt_result_syntax in
+            let*! status = Proto.Plugin.syntactic_check operation in
             let* validation_state =
-              match Proto.Plugin.syntactic_check operation with
+              match status with
               | `Ill_formed -> failwith "Ill-formed operation filtered"
               | `Well_formed ->
                   Proto.validate_operation
@@ -1285,7 +1286,8 @@ module Make (Proto : Protocol_plugin.T) = struct
         (fun state ops ->
           List.fold_left_es
             (fun state (oph, op, check_signature) ->
-              match Proto.Plugin.syntactic_check op with
+              let*! status = Proto.Plugin.syntactic_check op in
+              match status with
               | `Ill_formed -> failwith "Ill-formed operation filtered"
               | `Well_formed ->
                   Proto.validate_operation ~check_signature state oph op)
diff --git a/src/lib_validation/protocol_plugin.ml b/src/lib_validation/protocol_plugin.ml
index acfd9960af07b3f3ad0efd9982b9d436c347bbd4..28d763c6d7c137d603c96ace683108ec560bd395 100644
--- a/src/lib_validation/protocol_plugin.ml
+++ b/src/lib_validation/protocol_plugin.ml
@@ -44,7 +44,7 @@ module type T = sig
     val flush :
       info -> head:Tezos_base.Block_header.shell_header -> info tzresult Lwt.t
 
-    val syntactic_check : operation -> [`Well_formed | `Ill_formed]
+    val syntactic_check : operation -> [`Well_formed | `Ill_formed] Lwt.t
 
     val pre_filter :
       info ->
@@ -104,7 +104,7 @@ module No_plugin (Proto : Registered_protocol.T) :
 
     let flush _ ~head:_ = Lwt_result_syntax.return_unit
 
-    let syntactic_check _ = `Well_formed
+    let syntactic_check _ = Lwt.return `Well_formed
 
     let pre_filter _ _ _ = Lwt.return @@ `Passed_prefilter (`Low [])
 
diff --git a/src/lib_validation/protocol_plugin.mli b/src/lib_validation/protocol_plugin.mli
index 6d47a4614a9e02c4b17bbdf275aaf17ec8c3cf8a..73177d9b3d821e4f0845db5f2df199809c48afc3 100644
--- a/src/lib_validation/protocol_plugin.mli
+++ b/src/lib_validation/protocol_plugin.mli
@@ -69,7 +69,7 @@ module type T = sig
         ill-formed operations to block block application.
 
         Should be called before the {!pre_filter}, does not need a context. *)
-    val syntactic_check : operation -> [`Well_formed | `Ill_formed]
+    val syntactic_check : operation -> [`Well_formed | `Ill_formed] Lwt.t
 
     (** Perform some light preliminary checks on the operation.
 
diff --git a/src/proto_017_PtNairob/lib_plugin/mempool.ml b/src/proto_017_PtNairob/lib_plugin/mempool.ml
index 631a8dfb610ac8569b12e6b0136edb8a963e3cda..f7737b7bcbd006a6392001e8b43cc49f48f5c6d8 100644
--- a/src/proto_017_PtNairob/lib_plugin/mempool.ml
+++ b/src/proto_017_PtNairob/lib_plugin/mempool.ml
@@ -266,43 +266,99 @@ let weight_and_resources_manager_operation ~hard_gas_limit_per_block ?size ~fee
   let resources = Q.max size_ratio gas_ratio in
   (Q.(fee_f / resources), resources)
 
+let output_encoding =
+  let open Data_encoding in
+  obj3
+    (req "outbox_level" Environment.Bounded.Non_negative_int32.encoding)
+    (req "message_index" n)
+    (req "message" Variable.string)
+
 let output_proof_encoding =
   let open Data_encoding in
   obj3
     (req
        "output_proof"
-       Sc_rollup_wasm.V2_0_0.Protocol_implementation.proof_encoding)
+       Tezos_context_helpers.Context.Proof_encoding.Merkle_proof_encoding.V2
+       .Tree2
+       .tree_proof_encoding)
     (req "output_proof_state" Sc_rollup.State_hash.encoding)
-    (req "output_proof_output" Variable.bytes)
+    (req "output_proof_output" output_encoding)
+
+module Tree = struct
+  open Environment
+  include Context.Tree
+
+  type tree = Context.tree
+
+  type t = Context.t
+
+  type key = string list
+
+  type value = bytes
+end
+
+module Wasm_machine = Environment.Wasm_2_0_0.Make (Tree)
+
+let discard_wasm_output_proof_early output_proof outbox_level message_index
+    output =
+  let open Lwt_syntax in
+  let+ result =
+    Environment.Context.verify_tree_proof output_proof (fun tree ->
+        let* output =
+          Wasm_machine.get_output {outbox_level; message_index} tree
+        in
+        return (tree, output))
+  in
+  match result with
+  | Ok (_, Some expected_output) -> not (expected_output = output)
+  | _ -> false
 
 let kinded_hash_to_state_hash = function
   | `Value hash | `Node hash ->
       Sc_rollup.State_hash.context_hash_to_state_hash hash
 
-let is_invalid_op : type t. t manager_operation -> bool = function
+let is_invalid_op : type t. t manager_operation -> bool Lwt.t =
+  let open Lwt_syntax in
+  function
   | Sc_rollup_execute_outbox_message
       {rollup = _; cemented_commitment = _; output_proof} -> (
       match
         Data_encoding.Binary.of_string_opt output_proof_encoding output_proof
       with
-      | None -> true
-      | Some (output_proof, output_proof_state, _) ->
-          not
-            (Sc_rollup.State_hash.equal
-               output_proof_state
-               (kinded_hash_to_state_hash
-                  output_proof.Environment.Context.Proof.before)))
-  | _ -> false
+      | None -> return_true
+      | Some
+          ( output_proof,
+            output_proof_state,
+            (outbox_level, message_index, output) ) ->
+          let* discard_wasm_proof =
+            discard_wasm_output_proof_early
+              output_proof
+              outbox_level
+              message_index
+              output
+          in
+          let state_is_correct =
+            Sc_rollup.State_hash.equal
+              output_proof_state
+              (kinded_hash_to_state_hash
+                 output_proof.Environment.Context.Proof.before)
+          in
+          let is_invalid = (not state_is_correct) || discard_wasm_proof in
+          return is_invalid)
+  | _ -> return_false
 
-let rec contains_invalid_op : type t. t Kind.manager contents_list -> bool =
-  function
+let rec contains_invalid_op : type t. t Kind.manager contents_list -> bool Lwt.t
+    = function
   | Single (Manager_operation {operation; _}) -> is_invalid_op operation
   | Cons (Manager_operation {operation; _}, rest) ->
-      is_invalid_op operation || contains_invalid_op rest
+      let open Lwt_syntax in
+      let* is_invalid = is_invalid_op operation in
+      if not is_invalid then contains_invalid_op rest else return_true
 
 let syntactic_check
     ({shell = _; protocol_data = Operation_data {contents; _}} : Main.operation)
     =
+  let open Lwt_syntax in
   match contents with
   | Single (Failing_noop _)
   | Single (Preendorsement _)
@@ -317,11 +373,13 @@ let syntactic_check
   | Single (Vdf_revelation _)
   | Single (Drain_delegate _)
   | Single (Ballot _) ->
-      `Well_formed
+      Lwt.return `Well_formed
   | Single (Manager_operation _) as op ->
-      if contains_invalid_op op then `Ill_formed else `Well_formed
+      let* is_invalid = contains_invalid_op op in
+      if is_invalid then return `Ill_formed else return `Well_formed
   | Cons (Manager_operation _, _) as op ->
-      if contains_invalid_op op then `Ill_formed else `Well_formed
+      let* is_invalid = contains_invalid_op op in
+      if is_invalid then return `Ill_formed else return `Well_formed
 
 let pre_filter_manager :
     type t.
diff --git a/src/proto_017_PtNairob/lib_plugin/mempool.mli b/src/proto_017_PtNairob/lib_plugin/mempool.mli
index 954cb5190b51b0e6f25a82bdcd228cca10ae62a9..8157d174f705be09abb0f8c4f8c577b63e8c37bd 100644
--- a/src/proto_017_PtNairob/lib_plugin/mempool.mli
+++ b/src/proto_017_PtNairob/lib_plugin/mempool.mli
@@ -72,7 +72,7 @@ val flush : info -> head:Block_header.shell_header -> info tzresult Lwt.t
 
     Should be called before the {!pre_filter}, does not need a context. *)
 val syntactic_check :
-  Protocol.Alpha_context.packed_operation -> [`Well_formed | `Ill_formed]
+  Protocol.Alpha_context.packed_operation -> [`Well_formed | `Ill_formed] Lwt.t
 
 (** Perform some preliminary checks on an operation.
 
diff --git a/src/proto_018_Proxford/lib_plugin/mempool.ml b/src/proto_018_Proxford/lib_plugin/mempool.ml
index e107df24db3ff36b533e5533510d4a5953f12e7f..5b9cf6f28efddfeae1efe64c6f50a48e4e892868 100644
--- a/src/proto_018_Proxford/lib_plugin/mempool.ml
+++ b/src/proto_018_Proxford/lib_plugin/mempool.ml
@@ -554,7 +554,7 @@ let pre_filter info config
   | Single (Manager_operation _) as op -> prefilter_manager_op op
   | Cons (Manager_operation _, _) as op -> prefilter_manager_op op
 
-let syntactic_check _ = `Well_formed
+let syntactic_check _ = Lwt.return `Well_formed
 
 let is_manager_operation op =
   match Operation.acceptable_pass op with
diff --git a/src/proto_018_Proxford/lib_plugin/mempool.mli b/src/proto_018_Proxford/lib_plugin/mempool.mli
index 954cb5190b51b0e6f25a82bdcd228cca10ae62a9..8157d174f705be09abb0f8c4f8c577b63e8c37bd 100644
--- a/src/proto_018_Proxford/lib_plugin/mempool.mli
+++ b/src/proto_018_Proxford/lib_plugin/mempool.mli
@@ -72,7 +72,7 @@ val flush : info -> head:Block_header.shell_header -> info tzresult Lwt.t
 
     Should be called before the {!pre_filter}, does not need a context. *)
 val syntactic_check :
-  Protocol.Alpha_context.packed_operation -> [`Well_formed | `Ill_formed]
+  Protocol.Alpha_context.packed_operation -> [`Well_formed | `Ill_formed] Lwt.t
 
 (** Perform some preliminary checks on an operation.
 
diff --git a/src/proto_alpha/lib_plugin/mempool.ml b/src/proto_alpha/lib_plugin/mempool.ml
index edef73395f8578d2e0213d8ee73ec91cf3a101ea..b672a841d4b7b48b37304052a28f5ea83f2d4e96 100644
--- a/src/proto_alpha/lib_plugin/mempool.ml
+++ b/src/proto_alpha/lib_plugin/mempool.ml
@@ -561,7 +561,7 @@ let pre_filter info config
   | Single (Manager_operation _) as op -> prefilter_manager_op op
   | Cons (Manager_operation _, _) as op -> prefilter_manager_op op
 
-let syntactic_check _ = `Well_formed
+let syntactic_check _ = Lwt.return `Well_formed
 
 let is_manager_operation op =
   match Operation.acceptable_pass op with
diff --git a/src/proto_alpha/lib_plugin/mempool.mli b/src/proto_alpha/lib_plugin/mempool.mli
index 954cb5190b51b0e6f25a82bdcd228cca10ae62a9..8157d174f705be09abb0f8c4f8c577b63e8c37bd 100644
--- a/src/proto_alpha/lib_plugin/mempool.mli
+++ b/src/proto_alpha/lib_plugin/mempool.mli
@@ -72,7 +72,7 @@ val flush : info -> head:Block_header.shell_header -> info tzresult Lwt.t
 
     Should be called before the {!pre_filter}, does not need a context. *)
 val syntactic_check :
-  Protocol.Alpha_context.packed_operation -> [`Well_formed | `Ill_formed]
+  Protocol.Alpha_context.packed_operation -> [`Well_formed | `Ill_formed] Lwt.t
 
 (** Perform some preliminary checks on an operation.