diff --git a/filesystem_verifier_action.cc b/filesystem_verifier_action.cc
index df54f80..d28526f 100644
--- a/filesystem_verifier_action.cc
+++ b/filesystem_verifier_action.cc
@@ -29,6 +29,7 @@
 #include <chromeos/streams/file_stream.h>
 
 #include "update_engine/boot_control_interface.h"
+#include "update_engine/payload_constants.h"
 #include "update_engine/system_state.h"
 #include "update_engine/utils.h"
 
diff --git a/install_plan.cc b/install_plan.cc
index 382eb4e..ec2ee93 100644
--- a/install_plan.cc
+++ b/install_plan.cc
@@ -18,15 +18,13 @@
 
 #include <base/logging.h>
 
+#include "update_engine/payload_constants.h"
 #include "update_engine/utils.h"
 
 using std::string;
 
 namespace chromeos_update_engine {
 
-const char* kLegacyPartitionNameKernel = "boot";
-const char* kLegacyPartitionNameRoot = "system";
-
 InstallPlan::InstallPlan(bool is_resume,
                          bool is_full_update,
                          const string& url,
diff --git a/install_plan.h b/install_plan.h
index 5e50626..6eb52fc 100644
--- a/install_plan.h
+++ b/install_plan.h
@@ -31,14 +31,6 @@
 // parts of the update system about the install that should happen.
 namespace chromeos_update_engine {
 
-// The kernel and rootfs partition names used by the BootControlInterface when
-// handling update payloads with a major version 1. The names of the updated
-// partitions are include in the payload itself for major version 2.
-// TODO(deymo): Remove these constants from this interface once the InstallPlan
-// doesn't list the partitions explicitly.
-extern const char* kLegacyPartitionNameKernel;
-extern const char* kLegacyPartitionNameRoot;
-
 struct InstallPlan {
   InstallPlan(bool is_resume,
               bool is_full_update,
diff --git a/omaha_response_handler_action_unittest.cc b/omaha_response_handler_action_unittest.cc
index 5e14511..65dbf0f 100644
--- a/omaha_response_handler_action_unittest.cc
+++ b/omaha_response_handler_action_unittest.cc
@@ -23,6 +23,7 @@
 #include "update_engine/constants.h"
 #include "update_engine/fake_system_state.h"
 #include "update_engine/mock_payload_state.h"
+#include "update_engine/payload_constants.h"
 #include "update_engine/platform_constants.h"
 #include "update_engine/test_utils.h"
 #include "update_engine/utils.h"
diff --git a/payload_constants.cc b/payload_constants.cc
index 05f114d..9d6fb3d 100644
--- a/payload_constants.cc
+++ b/payload_constants.cc
@@ -18,6 +18,9 @@
 
 namespace chromeos_update_engine {
 
+const char kLegacyPartitionNameKernel[] = "boot";
+const char kLegacyPartitionNameRoot[] = "system";
+
 const char kDeltaMagic[] = "CrAU";
 const char kBspatchPath[] = "bspatch";
 
diff --git a/payload_constants.h b/payload_constants.h
index 55a82d3..188ea84 100644
--- a/payload_constants.h
+++ b/payload_constants.h
@@ -23,6 +23,12 @@
 
 namespace chromeos_update_engine {
 
+// The kernel and rootfs partition names used by the BootControlInterface when
+// handling update payloads with a major version 1. The names of the updated
+// partitions are include in the payload itself for major version 2.
+extern const char kLegacyPartitionNameKernel[];
+extern const char kLegacyPartitionNameRoot[];
+
 extern const char kBspatchPath[];
 extern const char kDeltaMagic[];
 
diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
index c653433..2f76796 100644
--- a/payload_generator/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -149,10 +149,12 @@
   diff_utils::FilterNoopOperations(&kernel_ops);
 
   // Write payload file to disk.
-  payload.AddPartitionOperations(PartitionName::kRootfs, rootfs_ops);
-  payload.AddPartitionOperations(PartitionName::kKernel, kernel_ops);
-  payload.WritePayload(output_path, temp_file_path, private_key_path,
-                       metadata_size);
+  TEST_AND_RETURN_FALSE(payload.AddPartitionOperations(
+      kLegacyPartitionNameRoot, rootfs_ops));
+  TEST_AND_RETURN_FALSE(payload.AddPartitionOperations(
+      kLegacyPartitionNameKernel, kernel_ops));
+  TEST_AND_RETURN_FALSE(payload.WritePayload(output_path, temp_file_path,
+                                             private_key_path, metadata_size));
   temp_file_unlinker.reset();
 
   LOG(INFO) << "All done. Successfully created delta file with "
diff --git a/payload_generator/payload_file.cc b/payload_generator/payload_file.cc
index 6185f6c..2e0b22c 100644
--- a/payload_generator/payload_file.cc
+++ b/payload_generator/payload_file.cc
@@ -68,11 +68,6 @@
 
 }  // namespace
 
-const vector<PartitionName> PayloadFile::partition_disk_order_ = {
-  PartitionName::kRootfs,
-  PartitionName::kKernel,
-};
-
 bool PayloadFile::Init(const PayloadGenerationConfig& config) {
   major_version_ = config.major_version;
   TEST_AND_RETURN_FALSE(major_version_ == kChromeOSMajorPayloadVersion ||
@@ -107,10 +102,18 @@
   return true;
 }
 
-void PayloadFile::AddPartitionOperations(
-    PartitionName name,
+bool PayloadFile::AddPartitionOperations(
+    const std::string& partition_name,
     const vector<AnnotatedOperation>& aops) {
-  aops_map_[name].insert(aops_map_[name].end(), aops.begin(), aops.end());
+  // Check partitions order for Chrome OS
+  if (major_version_ == kChromeOSMajorPayloadVersion) {
+    const vector<const char*> part_order = { kLegacyPartitionNameRoot,
+                                             kLegacyPartitionNameKernel };
+    TEST_AND_RETURN_FALSE(aops_vec_.size() < part_order.size());
+    TEST_AND_RETURN_FALSE(partition_name == part_order[aops_vec_.size()]);
+  }
+  aops_vec_.emplace_back(partition_name, aops);
+  return true;
 }
 
 bool PayloadFile::WritePayload(const string& payload_file,
@@ -126,34 +129,38 @@
   ScopedPathUnlinker ordered_blobs_unlinker(ordered_blobs_path);
   TEST_AND_RETURN_FALSE(ReorderDataBlobs(data_blobs_path, ordered_blobs_path));
 
-  // Copy the operations from the aops_map_ to the manifest.
-  manifest_.clear_install_operations();
-  manifest_.clear_kernel_install_operations();
-  for (PartitionName name : partition_disk_order_) {
-    for (const AnnotatedOperation& aop : aops_map_[name]) {
-      if (name == PartitionName::kKernel) {
-        *manifest_.add_kernel_install_operations() = aop.op;
-      } else {
-        *manifest_.add_install_operations() = aop.op;
+  // Check that install op blobs are in order.
+  uint64_t next_blob_offset = 0;
+  for (const auto& part_name_aops_pair : aops_vec_) {
+    for (const auto& aop : part_name_aops_pair.second) {
+      if (!aop.op.has_data_offset())
+        continue;
+      if (aop.op.data_offset() != next_blob_offset) {
+        LOG(FATAL) << "bad blob offset! " << aop.op.data_offset() << " != "
+                   << next_blob_offset;
       }
+      next_blob_offset += aop.op.data_length();
     }
   }
 
-  // Check that install op blobs are in order.
-  uint64_t next_blob_offset = 0;
-  {
-    for (int i = 0; i < (manifest_.install_operations_size() +
-                         manifest_.kernel_install_operations_size()); i++) {
-      InstallOperation* op = i < manifest_.install_operations_size()
-                                 ? manifest_.mutable_install_operations(i)
-                                 : manifest_.mutable_kernel_install_operations(
-                                       i - manifest_.install_operations_size());
-      if (op->has_data_offset()) {
-        if (op->data_offset() != next_blob_offset) {
-          LOG(FATAL) << "bad blob offset! " << op->data_offset() << " != "
-                     << next_blob_offset;
+  // Copy the operations from the aops_vec_ to the manifest.
+  manifest_.clear_install_operations();
+  manifest_.clear_kernel_install_operations();
+  manifest_.clear_partitions();
+  for (const auto& part_name_aops_pair : aops_vec_) {
+    if (major_version_ == kBrilloMajorPayloadVersion) {
+      PartitionUpdate* partition = manifest_.add_partitions();
+      partition->set_partition_name(part_name_aops_pair.first);
+      for (const AnnotatedOperation& aop : part_name_aops_pair.second) {
+        *partition->add_operations() = aop.op;
+      }
+    } else {
+      for (const AnnotatedOperation& aop : part_name_aops_pair.second) {
+        if (part_name_aops_pair.first == kLegacyPartitionNameKernel) {
+          *manifest_.add_kernel_install_operations() = aop.op;
+        } else {
+          *manifest_.add_install_operations() = aop.op;
         }
-        next_blob_offset += op->data_length();
       }
     }
   }
@@ -168,7 +175,7 @@
     AddSignatureOp(next_blob_offset, signature_blob_length, &manifest_);
   }
 
-    // Serialize protobuf
+  // Serialize protobuf
   string serialized_manifest;
   TEST_AND_RETURN_FALSE(manifest_.AppendToString(&serialized_manifest));
 
@@ -244,8 +251,8 @@
   ScopedFileWriterCloser writer_closer(&writer);
   uint64_t out_file_size = 0;
 
-  for (PartitionName name : partition_disk_order_) {
-    for (AnnotatedOperation& aop : aops_map_[name]) {
+  for (auto& part_name_aops_pair : aops_vec_) {
+    for (AnnotatedOperation& aop : part_name_aops_pair.second) {
       if (!aop.op.has_data_offset())
         continue;
       CHECK(aop.op.has_data_length());
@@ -278,11 +285,8 @@
   vector<DeltaObject> objects;
   off_t total_size = 0;
 
-  for (PartitionName name : partition_disk_order_) {
-    const auto& partition_aops = aops_map_.find(name);
-    if (partition_aops == aops_map_.end())
-      continue;
-    for (const AnnotatedOperation& aop : partition_aops->second) {
+  for (const auto& part_name_aops_pair : aops_vec_) {
+    for (const AnnotatedOperation& aop : part_name_aops_pair.second) {
       objects.push_back(DeltaObject(aop.name,
                                     aop.op.type(),
                                     aop.op.data_length()));
diff --git a/payload_generator/payload_file.h b/payload_generator/payload_file.h
index 6e0776c..7cf9160 100644
--- a/payload_generator/payload_file.h
+++ b/payload_generator/payload_file.h
@@ -17,9 +17,9 @@
 #ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_PAYLOAD_FILE_H_
 #define UPDATE_ENGINE_PAYLOAD_GENERATOR_PAYLOAD_FILE_H_
 
-#include <map>
 #include <string>
 #include <vector>
+#include <utility>
 
 #include <chromeos/secure_blob.h>
 #include <gtest/gtest_prod.h>  // for FRIEND_TEST
@@ -41,7 +41,7 @@
 
   // Sets the list of operations to the payload manifest. The operations
   // reference a blob stored in the file provided to WritePayload().
-  void AddPartitionOperations(PartitionName name,
+  bool AddPartitionOperations(const std::string& partition_name,
                               const std::vector<AnnotatedOperation>& aops);
 
   // Write the payload to the |payload_file| file. The operations reference
@@ -77,16 +77,13 @@
   // Print in stderr the Payload usage report.
   void ReportPayloadUsage(uint64_t metadata_size) const;
 
-  // The list of partitions in the order their blobs should appear in the
-  // payload file.
-  static const std::vector<PartitionName> partition_disk_order_;
-
   // The major_version of the requested payload.
   uint64_t major_version_;
 
   DeltaArchiveManifest manifest_;
 
-  std::map<PartitionName, std::vector<AnnotatedOperation>> aops_map_;
+  std::vector<std::pair<std::string,
+                        std::vector<AnnotatedOperation>>> aops_vec_;
 };
 
 // Adds a dummy operation that points to a signature blob located at the
diff --git a/payload_generator/payload_file_unittest.cc b/payload_generator/payload_file_unittest.cc
index 2206d27..ff8c8a4 100644
--- a/payload_generator/payload_file_unittest.cc
+++ b/payload_generator/payload_file_unittest.cc
@@ -22,7 +22,6 @@
 
 #include <gtest/gtest.h>
 
-#include "update_engine/payload_constants.h"
 #include "update_engine/payload_generator/extent_ranges.h"
 #include "update_engine/test_utils.h"
 
@@ -64,33 +63,31 @@
   aop.op.set_data_offset(7);
   aop.op.set_data_length(1);
   aops.push_back(aop);
-  payload_.AddPartitionOperations(PartitionName::kRootfs, aops);
+  payload_.AddPartitionOperations("part0", aops);
 
   aop.op.set_data_offset(0);
   aop.op.set_data_length(6);
   aops = {aop};
-  payload_.AddPartitionOperations(PartitionName::kKernel, aops);
+  payload_.AddPartitionOperations("part1", aops);
 
   EXPECT_TRUE(payload_.ReorderDataBlobs(orig_blobs, new_blobs));
 
-  const vector<AnnotatedOperation>& rootfs_aops =
-      payload_.aops_map_[PartitionName::kRootfs];
-  const vector<AnnotatedOperation>& kernel_aops =
-      payload_.aops_map_[PartitionName::kKernel];
+  const vector<AnnotatedOperation>& part0_aops = payload_.aops_vec_[0].second;
+  const vector<AnnotatedOperation>& part1_aops = payload_.aops_vec_[1].second;
   string new_data;
   EXPECT_TRUE(utils::ReadFile(new_blobs, &new_data));
   // Kernel blobs should appear at the end.
   EXPECT_EQ("bcdakernel", new_data);
 
-  EXPECT_EQ(2, rootfs_aops.size());
-  EXPECT_EQ(0, rootfs_aops[0].op.data_offset());
-  EXPECT_EQ(3, rootfs_aops[0].op.data_length());
-  EXPECT_EQ(3, rootfs_aops[1].op.data_offset());
-  EXPECT_EQ(1, rootfs_aops[1].op.data_length());
+  EXPECT_EQ(2, part0_aops.size());
+  EXPECT_EQ(0, part0_aops[0].op.data_offset());
+  EXPECT_EQ(3, part0_aops[0].op.data_length());
+  EXPECT_EQ(3, part0_aops[1].op.data_offset());
+  EXPECT_EQ(1, part0_aops[1].op.data_length());
 
-  EXPECT_EQ(1, kernel_aops.size());
-  EXPECT_EQ(4, kernel_aops[0].op.data_offset());
-  EXPECT_EQ(6, kernel_aops[0].op.data_length());
+  EXPECT_EQ(1, part1_aops.size());
+  EXPECT_EQ(4, part1_aops[0].op.data_offset());
+  EXPECT_EQ(6, part1_aops[0].op.data_length());
 }
 
 }  // namespace chromeos_update_engine
diff --git a/update_attempter_unittest.cc b/update_attempter_unittest.cc
index 7d7b796..749ad3b 100644
--- a/update_attempter_unittest.cc
+++ b/update_attempter_unittest.cc
@@ -47,6 +47,7 @@
 #include "update_engine/mock_p2p_manager.h"
 #include "update_engine/mock_payload_state.h"
 #include "update_engine/mock_prefs.h"
+#include "update_engine/payload_constants.h"
 #include "update_engine/platform_constants.h"
 #include "update_engine/postinstall_runner_action.h"
 #include "update_engine/prefs.h"