diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli
index 3ce5eb1aee43a379864fea4e16bbc3fccf2eb7e0..811099bf760cf2099812821f9b336b146c1fcbf1 100644
--- a/src/proto_alpha/lib_protocol/alpha_context.mli
+++ b/src/proto_alpha/lib_protocol/alpha_context.mli
@@ -3733,6 +3733,13 @@ module Sc_rollup : sig
 
     val last_cemented_commitment_hash_with_level :
       context -> rollup -> (Hash.t * Raw_level.t * context) tzresult Lwt.t
+
+    val check_if_commitments_are_related :
+      context ->
+      rollup ->
+      descendant:Hash.t ->
+      ancestor:Hash.t ->
+      (bool * context) tzresult Lwt.t
   end
 
   module Storage : sig
diff --git a/src/proto_alpha/lib_protocol/sc_rollup_commitment_storage.ml b/src/proto_alpha/lib_protocol/sc_rollup_commitment_storage.ml
index e027c9525c6fdbac74bab76b28c2f7cbfae2e426..1a3d957089b3080a3278d348ffcdeb0c3bbf8ff6 100644
--- a/src/proto_alpha/lib_protocol/sc_rollup_commitment_storage.ml
+++ b/src/proto_alpha/lib_protocol/sc_rollup_commitment_storage.ml
@@ -85,6 +85,21 @@ let get_predecessor_unsafe ctxt rollup node =
   let* commitment, ctxt = get_commitment_unsafe ctxt rollup node in
   return (commitment.predecessor, ctxt)
 
+let check_if_commitments_are_related ctxt rollup ~descendant ~ancestor =
+  let open Lwt_result_syntax in
+  let rec aux ctxt current_commitment_hash =
+    if Commitment_hash.(current_commitment_hash = ancestor) then
+      return (true, ctxt)
+    else
+      let* predecessor_commitment_opt, ctxt =
+        get_predecessor_opt_unsafe ctxt rollup current_commitment_hash
+      in
+      match predecessor_commitment_opt with
+      | None -> return (false, ctxt)
+      | Some cch -> (aux [@ocaml.tailcall]) ctxt cch
+  in
+  aux ctxt descendant
+
 let hash ctxt commitment =
   let open Result_syntax in
   let* ctxt =
diff --git a/src/proto_alpha/lib_protocol/sc_rollup_commitment_storage.mli b/src/proto_alpha/lib_protocol/sc_rollup_commitment_storage.mli
index b126d0b2ab2f1f22399e9eccc3bfcbdeb1d2ae91..71d1769f777b674926db308281bb64d399226d21 100644
--- a/src/proto_alpha/lib_protocol/sc_rollup_commitment_storage.mli
+++ b/src/proto_alpha/lib_protocol/sc_rollup_commitment_storage.mli
@@ -221,6 +221,16 @@ val get_predecessor_unsafe :
   Commitment_hash.t ->
   (Commitment_hash.t * Raw_context.t) tzresult Lwt.t
 
+(** [check_if_commitments_are_related ~descendant ~ancestor] checks whether a
+    commitment with hash [~ancestor] exists as a predecessor of [~descendant],
+    among the list of commitments stored for [rollup] in [ctxt]. *)
+val check_if_commitments_are_related :
+  Raw_context.t ->
+  Sc_rollup_repr.t ->
+  descendant:Commitment_hash.t ->
+  ancestor:Commitment_hash.t ->
+  (bool * Raw_context.t) tzresult Lwt.t
+
 (** Hash a commitment and account for gas spent. *)
 val hash :
   Raw_context.t -> Commitment.t -> (Raw_context.t * Commitment_hash.t) tzresult
diff --git a/src/proto_alpha/lib_protocol/sc_rollup_operations.ml b/src/proto_alpha/lib_protocol/sc_rollup_operations.ml
index e234e8c51057d5d8c2c70e93be2a28ba510b3243..4742efb2c0f0077832141dab7202f2c819c27514 100644
--- a/src/proto_alpha/lib_protocol/sc_rollup_operations.ml
+++ b/src/proto_alpha/lib_protocol/sc_rollup_operations.ml
@@ -408,26 +408,32 @@ let validate_outbox_level ctxt ~outbox_level ~lcc_level =
 let execute_outbox_message ctxt ~validate_and_decode_output_proof rollup
     ~cemented_commitment ~source ~output_proof =
   let open Lwt_result_syntax in
-  (* TODO: #3211
-     Allow older cemented commits as well.
-     This has the benefits of eliminating any race condition where new commits
-     are cemented and makes inclusion proofs obsolete. *)
+  (* Get inbox level of last cemented commitment, needed to validate that the
+     outbox message is active. This call also implicitly checks that the rollup
+     exists. *)
   let* lcc_hash, lcc_level, ctxt =
     Sc_rollup.Commitment.last_cemented_commitment_hash_with_level ctxt rollup
   in
-  (* Check that the last-cemented-commitment matches the one for the given
-     rollup. This is important in order to guarantee that the inclusion-proof
-     is for the correct state-hash. *)
+  (* Check that the commitment is a cemented commitment still stored in the
+     context. We start from the [lcc_hash] of the rollup, which we know to be
+     stored in context. *)
+  let* is_cemented_commitment_in_context, ctxt =
+    Sc_rollup.Commitment.check_if_commitments_are_related
+      ctxt
+      rollup
+      ~descendant:lcc_hash
+      ~ancestor:cemented_commitment
+  in
   let* () =
     fail_unless
-      Sc_rollup.Commitment.Hash.(lcc_hash = cemented_commitment)
+      is_cemented_commitment_in_context
       Sc_rollup_invalid_last_cemented_commitment
   in
   (* Validate and decode the output proofs. *)
   let* Sc_rollup.{outbox_level; message_index; message}, ctxt =
     validate_and_decode_output_proof
       ctxt
-      ~cemented_commitment:lcc_hash
+      ~cemented_commitment
       rollup
       ~output_proof
   in
diff --git a/src/proto_alpha/lib_protocol/test/integration/operations/test_sc_rollup.ml b/src/proto_alpha/lib_protocol/test/integration/operations/test_sc_rollup.ml
index 6df28f288c4156894acb98ccdc0647a8b4ce5586..549057105ec15edaf18f429325def34649c52284 100644
--- a/src/proto_alpha/lib_protocol/test/integration/operations/test_sc_rollup.ml
+++ b/src/proto_alpha/lib_protocol/test/integration/operations/test_sc_rollup.ml
@@ -236,7 +236,7 @@ let dummy_commitment ?predecessor ?compressed_state ?(number_of_ticks = 3000L)
     match compressed_state with
     | None ->
         let* {compressed_state; _} =
-          Context.Sc_rollup.commitment ctxt rollup genesis_info.commitment_hash
+          Context.Sc_rollup.commitment ctxt rollup predecessor
         in
         return compressed_state
     | Some compressed_state -> return compressed_state
@@ -615,6 +615,23 @@ let check_balances_evolution bal_before {liquid; frozen} ~action =
   let* () = Assert.equal_tez ~loc:__LOC__ expected_frozen frozen in
   return ()
 
+(* Generates a list of cemented dummy commitments. *)
+let gen_commitments incr ~baker ~originator rollup ~predecessor_hash
+    ~num_commitments =
+  let rec aux incr predecessor_hash n acc =
+    if n <= 0 then return (List.rev acc, incr)
+    else
+      let* predecessor =
+        Context.Sc_rollup.commitment (I incr) rollup predecessor_hash
+      in
+      let* commitment = dummy_commitment ~predecessor (I incr) rollup in
+      let* commitment_hash, incr =
+        publish_and_cement_commitment incr ~baker ~originator rollup commitment
+      in
+      aux incr commitment_hash (n - 1) (predecessor_hash :: acc)
+  in
+  aux incr predecessor_hash num_commitments []
+
 let attempt_to_recover_bond i contract rollup =
   let* recover_bond_op = Op.sc_rollup_recover_bond (I i) contract rollup in
   let* i = Incremental.add_operation i recover_bond_op in
@@ -1055,6 +1072,114 @@ let test_single_transaction_batch () =
     (Destination.Contract (Originated ticket_receiver))
     (Some 1)
 
+(** Test that checks that an outbox message can be executed against all stored
+    cemented commitments but not against an outdated one. *)
+let test_older_cemented_commitment () =
+  let* block, (baker, originator) = context_init Context.T2 in
+  let source = Context.Contract.pkh originator in
+  let baker = Context.Contract.pkh baker in
+  (* Originate a rollup that accepts a list of string tickets as input. *)
+  let* block, rollup = sc_originate block originator "list (ticket string)" in
+  let* incr = Incremental.begin_construction block in
+  (* Originate a contract that accepts a pair of nat and ticket string input.  *)
+  let* ticket_receiver, incr =
+    originate_contract
+      incr
+      ~script:ticket_receiver
+      ~storage:"{}"
+      ~source_contract:originator
+      ~baker
+  in
+  (* Ticket-token with content "red". *)
+  let* red_token =
+    string_ticket_token "KT1ThEdxfUcWUwqsdergy3QnbCWGHSUHeHJq" "red"
+  in
+  let verify_outbox_message_execution incr cemented_commitment =
+    (* Set up the balance so that the self contract owns one ticket. *)
+    let* _ticket_hash, incr =
+      adjust_ticket_token_balance_of_rollup
+        (I incr)
+        rollup
+        red_token
+        ~delta:Z.one
+    in
+    (* Create an atomic batch message. *)
+    let transactions =
+      [
+        ( ticket_receiver,
+          Entrypoint.default,
+          {|Pair 42 (Pair "KT1ThEdxfUcWUwqsdergy3QnbCWGHSUHeHJq" "red" 1)|} );
+      ]
+    in
+    let output = make_output ~outbox_level:0 ~message_index:0 transactions in
+    let* Sc_rollup_operations.{operations; _}, incr =
+      execute_outbox_message_without_proof_validation
+        incr
+        rollup
+        ~cemented_commitment
+        ~source
+        output
+    in
+    (* Confirm that each transaction maps to one operation. *)
+    let* () =
+      verify_execute_outbox_message_operations
+        ~loc:__LOC__
+        incr
+        ~source
+        ~operations
+        ~expected_transactions:transactions
+    in
+    (* Verify that the balance has moved to ticket-receiver. *)
+    let* () =
+      assert_ticket_token_balance
+        ~loc:__LOC__
+        incr
+        red_token
+        (Destination.Sc_rollup rollup)
+        None
+    in
+    assert_ticket_token_balance
+      ~loc:__LOC__
+      incr
+      red_token
+      (Destination.Contract (Originated ticket_receiver))
+      (Some 1)
+  in
+  let* max_num_stored_cemented_commitments =
+    let* ctxt = Context.to_alpha_ctxt (I incr) in
+    return
+    @@ Alpha_context.Constants.max_number_of_stored_cemented_commitments ctxt
+  in
+  (* Publish and cement a commitment. *)
+  let* first_commitment_hash, incr =
+    publish_and_cement_dummy_commitment incr ~baker ~originator rollup
+  in
+  (* Generate a list of commitments that exceed the maximum number of stored
+     ones by one. *)
+  let* commitment_hashes, incr =
+    gen_commitments
+      incr
+      ~baker
+      ~originator
+      rollup
+      ~predecessor_hash:first_commitment_hash
+      ~num_commitments:(max_num_stored_cemented_commitments + 1)
+  in
+  match commitment_hashes with
+  | too_old_commitment :: stored_hashes ->
+      (* Executing outbox message for the old non-stored commitment should fail. *)
+      let* () =
+        assert_fails
+          ~loc:__LOC__
+          ~error:Sc_rollup_operations.Sc_rollup_invalid_last_cemented_commitment
+          (verify_outbox_message_execution incr too_old_commitment)
+      in
+      (* Executing outbox message for the recent ones should succeed. *)
+      List.iteri_es
+        (fun _ix commitment -> verify_outbox_message_execution incr commitment)
+        stored_hashes
+  | _ -> failwith "Expected non-empty list of commitment hashes."
+
 let test_multi_transaction_batch () =
   let* block, (baker, originator) = context_init Context.T2 in
   let baker = Context.Contract.pkh baker in
@@ -1233,6 +1358,67 @@ let test_execute_message_twice () =
        ~source
        output)
 
+(** Verifies that it is not possible to execute the same message twice from
+    different commitments. *)
+let test_execute_message_twice_different_cemented_commitments () =
+  let* block, (baker, originator) = context_init Context.T2 in
+  let baker = Context.Contract.pkh baker in
+  let source = Context.Contract.pkh originator in
+  (* Originate a rollup that accepts a list of string tickets as input. *)
+  let* block, rollup = sc_originate block originator "list (ticket string)" in
+  let* incr = Incremental.begin_construction block in
+  (* Originate a contract that accepts a pair of nat and ticket string input.  *)
+  let* string_receiver, incr =
+    originate_contract
+      incr
+      ~script:string_receiver
+      ~storage:{|""|}
+      ~source_contract:originator
+      ~baker
+  in
+  (* Publish and cement a commitment. *)
+  let* first_cemented_commitment, incr =
+    publish_and_cement_dummy_commitment incr ~baker ~originator rollup
+  in
+  let* predecessor =
+    Context.Sc_rollup.commitment (I incr) rollup first_cemented_commitment
+  in
+  let* commitment = dummy_commitment ~predecessor (I incr) rollup in
+  let* second_cemented_commitment, incr =
+    publish_and_cement_commitment incr ~baker ~originator rollup commitment
+  in
+  (* Create an atomic batch message. *)
+  let transactions = [(string_receiver, Entrypoint.default, {|"Hello"|})] in
+  let output = make_output ~outbox_level:0 ~message_index:1 transactions in
+  (* Execute the message once - should succeed. *)
+  let* Sc_rollup_operations.{operations; _}, incr =
+    execute_outbox_message_without_proof_validation
+      incr
+      rollup
+      ~cemented_commitment:first_cemented_commitment
+      ~source
+      output
+  in
+  (* Confirm that each transaction maps to one operation. *)
+  let* () =
+    verify_execute_outbox_message_operations
+      ~loc:__LOC__
+      incr
+      ~source
+      ~operations
+      ~expected_transactions:transactions
+  in
+  (* Execute the same message again should fail. *)
+  assert_fails
+    ~loc:__LOC__
+    ~error:Sc_rollup_errors.Sc_rollup_outbox_message_already_applied
+    (execute_outbox_message_without_proof_validation
+       incr
+       rollup
+       ~cemented_commitment:second_cemented_commitment
+       ~source
+       output)
+
 let test_zero_amount_ticket () =
   let* block, (baker, originator) = context_init Context.T2 in
   let baker = Context.Contract.pkh baker in
@@ -2463,6 +2649,10 @@ let tests =
       "single transaction atomic batch"
       `Quick
       test_single_transaction_batch;
+    Tztest.tztest
+      "execute outbox message against older cemented commitment"
+      `Quick
+      test_older_cemented_commitment;
     Tztest.tztest
       "multi-transaction atomic batch"
       `Quick
@@ -2472,6 +2662,10 @@ let tests =
       `Quick
       test_transaction_with_invalid_type;
     Tztest.tztest "execute same message twice" `Quick test_execute_message_twice;
+    Tztest.tztest
+      "execute same message twice against different cemented commitments"
+      `Quick
+      test_execute_message_twice_different_cemented_commitments;
     Tztest.tztest
       "transaction with zero amount ticket"
       `Quick
diff --git a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_storage.ml b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_storage.ml
index 53e9529c7929ab77c5a069dbb4e165f0922b21c1..61f50455d5d7a29785ab3779023d4ae5e0970a2a 100644
--- a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_storage.ml
+++ b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_storage.ml
@@ -2578,6 +2578,104 @@ let test_get_cemented_commitments_with_levels () =
     cemented_commitments_with_levels
     expected_commitments_with_levels
 
+(* Produces [max_num_stored_cemented_commitments] number of commitments and
+   verifies that each of them is an ancestor of the last cemented commitment. *)
+let test_are_commitments_related_when_related () =
+  let* ctxt, rollup, c0, staker =
+    originate_rollup_and_deposit_with_one_staker ()
+  in
+  let challenge_window =
+    Constants_storage.sc_rollup_challenge_window_in_blocks ctxt
+  in
+  (* Produce and stake on n commitments, each on top of the other. *)
+  (* Fetch number of stored commitments in context. *)
+  let max_num_stored_cemented_commitments =
+    (Raw_context.constants ctxt).sc_rollup
+      .max_number_of_stored_cemented_commitments
+  in
+  (* Produce and store a number of commitments equal to the maximum number of
+     cemented commitments that can be stored. *)
+  let number_of_commitments = max_num_stored_cemented_commitments in
+  let* commitments, ctxt =
+    lift
+    @@ produce_and_refine
+         ~number_of_commitments
+         ~predecessor:c0
+         ctxt
+         staker
+         rollup
+  in
+  let ctxt = Raw_context.Internal_for_tests.add_level ctxt challenge_window in
+  (* Cement all commitments that have been produced. *)
+  let* ctxt = lift @@ cement_commitments ctxt commitments rollup in
+  (* Check that check_if_commitments_are_related detects that each
+     cemented commitment is an ancestor of the last cemented commitment. *)
+  let* lcc, ctxt =
+    lift @@ Sc_rollup_commitment_storage.last_cemented_commitment ctxt rollup
+  in
+  commitments
+  |> List.iter_es (fun commitment ->
+         let* is_commitment_cemented, _ctxt =
+           lift
+           @@ Sc_rollup_commitment_storage.check_if_commitments_are_related
+                ctxt
+                rollup
+                ~descendant:lcc
+                ~ancestor:commitment
+         in
+         Assert.equal_bool ~loc:__LOC__ is_commitment_cemented true)
+
+(** Tests that [check_if_commitments_are_related] returns false for two
+    unrelated commitments. *)
+let test_unrelated_commitments () =
+  let* ctxt, rollup, genesis_hash, staker1, staker2 =
+    originate_rollup_and_deposit_with_two_stakers ()
+  in
+  let level = valid_inbox_level ctxt in
+  let commitment1 =
+    Commitment_repr.
+      {
+        predecessor = genesis_hash;
+        inbox_level = level 1l;
+        number_of_ticks = number_of_ticks_exn 1232909L;
+        compressed_state = Sc_rollup_repr.State_hash.zero;
+      }
+  in
+  let* c1, _level, ctxt =
+    lift
+    @@ Sc_rollup_stake_storage.Internal_for_tests.refine_stake
+         ctxt
+         rollup
+         staker1
+         commitment1
+  in
+  let commitment2 =
+    Commitment_repr.
+      {
+        predecessor = genesis_hash;
+        inbox_level = level 1l;
+        number_of_ticks = number_of_ticks_exn 44L;
+        compressed_state = Sc_rollup_repr.State_hash.zero;
+      }
+  in
+  let* c2, _level, ctxt =
+    lift
+    @@ Sc_rollup_stake_storage.Internal_for_tests.refine_stake
+         ctxt
+         rollup
+         staker2
+         commitment2
+  in
+  let* are_commitments_related, _ctxt =
+    lift
+    @@ Sc_rollup_commitment_storage.check_if_commitments_are_related
+         ctxt
+         rollup
+         ~descendant:c1
+         ~ancestor:c2
+  in
+  Assert.equal_bool ~loc:__LOC__ are_commitments_related false
+
 let tests =
   [
     Tztest.tztest
@@ -2810,6 +2908,14 @@ let tests =
       "Getting cemented commitments returns multiple cemented commitments"
       `Quick
       test_get_cemented_commitments_with_levels;
+    Tztest.tztest
+      "All cemented commitments are ancestors of last cemented commitment"
+      `Quick
+      test_are_commitments_related_when_related;
+    Tztest.tztest
+      "Unrelated commitments are classified as such"
+      `Quick
+      test_unrelated_commitments;
   ]
 
 (* FIXME: https://gitlab.com/tezos/tezos/-/issues/2460