diff --git a/payload_consumer/payload_constants.cc b/payload_consumer/payload_constants.cc
index ad193a0..29daddc 100644
--- a/payload_consumer/payload_constants.cc
+++ b/payload_consumer/payload_constants.cc
@@ -25,7 +25,8 @@
 const uint32_t kInPlaceMinorPayloadVersion = 1;
 const uint32_t kSourceMinorPayloadVersion = 2;
 const uint32_t kOpSrcHashMinorPayloadVersion = 3;
-const uint32_t kPuffdiffMinorPayloadVersion = 4;
+const uint32_t kBrotliBsdiffMinorPayloadVersion = 4;
+const uint32_t kPuffdiffMinorPayloadVersion = 5;
 
 const char kLegacyPartitionNameKernel[] = "boot";
 const char kLegacyPartitionNameRoot[] = "system";
diff --git a/payload_consumer/payload_constants.h b/payload_consumer/payload_constants.h
index 1e2e810..9d29afd 100644
--- a/payload_consumer/payload_constants.h
+++ b/payload_consumer/payload_constants.h
@@ -43,6 +43,9 @@
 // The minor version that allows per-operation source hash.
 extern const uint32_t kOpSrcHashMinorPayloadVersion;
 
+// The minor version that allows BROTLI_BSDIFF, ZERO and DISCARD operation.
+extern const uint32_t kBrotliBsdiffMinorPayloadVersion;
+
 // The minor version that allows PUFFDIFF operation.
 extern const uint32_t kPuffdiffMinorPayloadVersion;
 
diff --git a/payload_generator/payload_generation_config.cc b/payload_generator/payload_generation_config.cc
index 2c5d6d6..15d4ab5 100644
--- a/payload_generator/payload_generation_config.cc
+++ b/payload_generator/payload_generation_config.cc
@@ -128,6 +128,7 @@
                         minor == kInPlaceMinorPayloadVersion ||
                         minor == kSourceMinorPayloadVersion ||
                         minor == kOpSrcHashMinorPayloadVersion ||
+                        minor == kBrotliBsdiffMinorPayloadVersion ||
                         minor == kPuffdiffMinorPayloadVersion);
   return true;
 }
@@ -151,7 +152,7 @@
       // The implementation of these operations had a bug in earlier versions
       // that prevents them from being used in any payload. We will enable
       // them for delta payloads for now.
-      return minor >= kPuffdiffMinorPayloadVersion;
+      return minor >= kBrotliBsdiffMinorPayloadVersion;
 
     // Delta operations:
     case InstallOperation::MOVE:
@@ -166,10 +167,10 @@
       return minor >= kSourceMinorPayloadVersion;
 
     case InstallOperation::BROTLI_BSDIFF:
-      return minor >= kPuffdiffMinorPayloadVersion;
-    // TODO(*) Revert the disablement of puffdiff after we fix b/72815313.
+      return minor >= kBrotliBsdiffMinorPayloadVersion;
+
     case InstallOperation::PUFFDIFF:
-      return false;
+      return minor >= kPuffdiffMinorPayloadVersion;
   }
   return false;
 }
diff --git a/scripts/update_payload/applier.py b/scripts/update_payload/applier.py
index d91a833..9582b3d 100644
--- a/scripts/update_payload/applier.py
+++ b/scripts/update_payload/applier.py
@@ -588,6 +588,7 @@
         shutil.copyfile(old_part_file_name, new_part_file_name)
       elif (self.minor_version == common.SOURCE_MINOR_PAYLOAD_VERSION or
             self.minor_version == common.OPSRCHASH_MINOR_PAYLOAD_VERSION or
+            self.minor_version == common.BROTLI_BSDIFF_MINOR_PAYLOAD_VERSION or
             self.minor_version == common.PUFFDIFF_MINOR_PAYLOAD_VERSION):
         # In minor version >= 2, we don't want to copy the partitions, so
         # instead just make the new partition file.
diff --git a/scripts/update_payload/checker.py b/scripts/update_payload/checker.py
index db17011..e241b0b 100644
--- a/scripts/update_payload/checker.py
+++ b/scripts/update_payload/checker.py
@@ -69,6 +69,7 @@
     2: (_TYPE_DELTA,),
     3: (_TYPE_DELTA,),
     4: (_TYPE_DELTA,),
+    5: (_TYPE_DELTA,),
 }
 
 _OLD_DELTA_USABLE_PART_SIZE = 2 * 1024 * 1024 * 1024
@@ -1029,8 +1030,10 @@
     elif op.type == common.OpType.SOURCE_BSDIFF and self.minor_version >= 2:
       self._CheckAnyDiffOperation(op, data_length, total_dst_blocks, op_name)
       self._CheckAnySourceOperation(op, total_src_blocks, op_name)
-    elif (op.type in (common.OpType.PUFFDIFF, common.OpType.BROTLI_BSDIFF) and
-          self.minor_version >= 4):
+    elif op.type == common.OpType.BROTLI_BSDIFF and self.minor_version >= 4:
+      self._CheckAnyDiffOperation(op, data_length, total_dst_blocks, op_name)
+      self._CheckAnySourceOperation(op, total_src_blocks, op_name)
+    elif op.type == common.OpType.PUFFDIFF and self.minor_version >= 5:
       self._CheckAnyDiffOperation(op, data_length, total_dst_blocks, op_name)
       self._CheckAnySourceOperation(op, total_src_blocks, op_name)
     else:
diff --git a/scripts/update_payload/checker_unittest.py b/scripts/update_payload/checker_unittest.py
index 394ed0b..f718234 100755
--- a/scripts/update_payload/checker_unittest.py
+++ b/scripts/update_payload/checker_unittest.py
@@ -897,8 +897,10 @@
     if op_type == common.OpType.REPLACE_XZ:
       payload_checker.minor_version = 2 if fail_bad_minor_version else 3
     elif op_type in (common.OpType.ZERO, common.OpType.DISCARD,
-                     common.OpType.PUFFDIFF, common.OpType.BROTLI_BSDIFF):
+                     common.OpType.BROTLI_BSDIFF):
       payload_checker.minor_version = 3 if fail_bad_minor_version else 4
+    elif op_type == common.OpType.PUFFDIFF:
+      payload_checker.minor_version = 4 if fail_bad_minor_version else 5
 
     if op_type not in (common.OpType.MOVE, common.OpType.SOURCE_COPY):
       if not fail_mismatched_data_offset_length:
@@ -1113,7 +1115,8 @@
         (minor_version == 1 and payload_type == checker._TYPE_DELTA) or
         (minor_version == 2 and payload_type == checker._TYPE_DELTA) or
         (minor_version == 3 and payload_type == checker._TYPE_DELTA) or
-        (minor_version == 4 and payload_type == checker._TYPE_DELTA))
+        (minor_version == 4 and payload_type == checker._TYPE_DELTA) or
+        (minor_version == 5 and payload_type == checker._TYPE_DELTA))
     args = (report,)
 
     if should_succeed:
@@ -1340,7 +1343,7 @@
 
   # Add all _CheckManifestMinorVersion() test cases.
   AddParametricTests('CheckManifestMinorVersion',
-                     {'minor_version': (None, 0, 1, 2, 3, 4, 555),
+                     {'minor_version': (None, 0, 1, 2, 3, 4, 5, 555),
                       'payload_type': (checker._TYPE_FULL,
                                        checker._TYPE_DELTA)})
 
diff --git a/scripts/update_payload/common.py b/scripts/update_payload/common.py
index 42c91c2..4e7b2e3 100644
--- a/scripts/update_payload/common.py
+++ b/scripts/update_payload/common.py
@@ -39,7 +39,8 @@
 INPLACE_MINOR_PAYLOAD_VERSION = 1
 SOURCE_MINOR_PAYLOAD_VERSION = 2
 OPSRCHASH_MINOR_PAYLOAD_VERSION = 3
-PUFFDIFF_MINOR_PAYLOAD_VERSION = 4
+BROTLI_BSDIFF_MINOR_PAYLOAD_VERSION = 4
+PUFFDIFF_MINOR_PAYLOAD_VERSION = 5
 
 #
 # Payload operation types.
diff --git a/update_metadata.proto b/update_metadata.proto
index ad377c7..7ff032a 100644
--- a/update_metadata.proto
+++ b/update_metadata.proto
@@ -169,8 +169,10 @@
     // On minor version 4 or newer, these operations are supported:
     ZERO = 6;  // Write zeros in the destination.
     DISCARD = 7;  // Discard the destination blocks, reading as undefined.
-    PUFFDIFF = 9;  // The data is in puffdiff format.
     BROTLI_BSDIFF = 10;  // Like SOURCE_BSDIFF, but compressed with brotli.
+
+    // On minor version 5 or newer, these operations are supported:
+    PUFFDIFF = 9;  // The data is in puffdiff format.
   }
   required Type type = 1;
   // The offset into the delta file (after the protobuf)