diff --git a/init/Android.bp b/init/Android.bp
index 672942e..0e580fc 100644
--- a/init/Android.bp
+++ b/init/Android.bp
@@ -73,6 +73,7 @@
         "log.cpp",
         "parser.cpp",
         "persistent_properties.cpp",
+        "persistent_properties.proto",
         "property_service.cpp",
         "security.cpp",
         "selinux.cpp",
@@ -90,11 +91,15 @@
         "liblog",
         "libprocessgroup",
         "libfs_mgr",
+        "libprotobuf-cpp-lite",
     ],
     include_dirs: [
         "system/core/mkbootimg",
     ],
-
+    proto: {
+        type: "lite",
+        export_proto_headers: true,
+    },
 }
 
 /*
@@ -179,6 +184,7 @@
         "libinit",
         "libselinux",
         "libcrypto",
+        "libprotobuf-cpp-lite",
     ],
 }
 
diff --git a/init/Android.mk b/init/Android.mk
index 6c28517..dd0f1bf 100644
--- a/init/Android.mk
+++ b/init/Android.mk
@@ -82,6 +82,7 @@
     libprocessgroup \
     libavb \
     libkeyutils \
+    libprotobuf-cpp-lite \
 
 LOCAL_REQUIRED_MODULES := \
     e2fsdroid \
diff --git a/init/persistent_properties.cpp b/init/persistent_properties.cpp
index 66fa011..71f2355 100644
--- a/init/persistent_properties.cpp
+++ b/init/persistent_properties.cpp
@@ -46,14 +46,21 @@
 constexpr const uint32_t kMagic = 0x8495E0B4;
 constexpr const char kLegacyPersistentPropertyDir[] = "/data/property";
 
-Result<std::vector<std::pair<std::string, std::string>>> LoadLegacyPersistentProperties() {
+void AddPersistentProperty(const std::string& name, const std::string& value,
+                           PersistentProperties* persistent_properties) {
+    auto persistent_property_record = persistent_properties->add_properties();
+    persistent_property_record->set_name(name);
+    persistent_property_record->set_value(value);
+}
+
+Result<PersistentProperties> LoadLegacyPersistentProperties() {
     std::unique_ptr<DIR, decltype(&closedir)> dir(opendir(kLegacyPersistentPropertyDir), closedir);
     if (!dir) {
         return ErrnoError() << "Unable to open persistent property directory \""
                             << kLegacyPersistentPropertyDir << "\"";
     }
 
-    std::vector<std::pair<std::string, std::string>> persistent_properties;
+    PersistentProperties persistent_properties;
     dirent* entry;
     while ((entry = readdir(dir.get())) != nullptr) {
         if (!StartsWith(entry->d_name, "persist.")) {
@@ -87,7 +94,7 @@
 
         std::string value;
         if (ReadFdToString(fd, &value)) {
-            persistent_properties.emplace_back(entry->d_name, value);
+            AddPersistentProperty(entry->d_name, value, &persistent_properties);
         } else {
             PLOG(ERROR) << "Unable to read persistent property file " << entry->d_name;
         }
@@ -115,30 +122,28 @@
     }
 }
 
-std::vector<std::pair<std::string, std::string>> LoadPersistentPropertiesFromMemory() {
-    std::vector<std::pair<std::string, std::string>> properties;
+PersistentProperties LoadPersistentPropertiesFromMemory() {
+    PersistentProperties persistent_properties;
     __system_property_foreach(
         [](const prop_info* pi, void* cookie) {
             __system_property_read_callback(
                 pi,
                 [](void* cookie, const char* name, const char* value, unsigned serial) {
                     if (StartsWith(name, "persist.")) {
-                        auto properties =
-                            reinterpret_cast<std::vector<std::pair<std::string, std::string>>*>(
-                                cookie);
-                        properties->emplace_back(name, value);
+                        auto properties = reinterpret_cast<PersistentProperties*>(cookie);
+                        AddPersistentProperty(name, value, properties);
                     }
                 },
                 cookie);
         },
-        &properties);
-    return properties;
+        &persistent_properties);
+    return persistent_properties;
 }
 
 class PersistentPropertyFileParser {
   public:
     PersistentPropertyFileParser(const std::string& contents) : contents_(contents), position_(0) {}
-    Result<std::vector<std::pair<std::string, std::string>>> Parse();
+    Result<PersistentProperties> Parse();
 
   private:
     Result<std::string> ReadString();
@@ -148,9 +153,7 @@
     size_t position_;
 };
 
-Result<std::vector<std::pair<std::string, std::string>>> PersistentPropertyFileParser::Parse() {
-    std::vector<std::pair<std::string, std::string>> result;
-
+Result<PersistentProperties> PersistentPropertyFileParser::Parse() {
     if (auto magic = ReadUint32(); magic) {
         if (*magic != kMagic) {
             return Error() << "Magic value '0x" << std::hex << *magic
@@ -174,24 +177,20 @@
         return Error() << "Could not read num_properties: " << num_properties.error();
     }
 
+    PersistentProperties result;
     while (position_ < contents_.size()) {
-        auto key = ReadString();
-        if (!key) {
-            return Error() << "Could not read key: " << key.error();
+        auto name = ReadString();
+        if (!name) {
+            return Error() << "Could not read name: " << name.error();
         }
-        if (!StartsWith(*key, "persist.")) {
-            return Error() << "Property '" << *key << "' does not starts with 'persist.'";
+        if (!StartsWith(*name, "persist.")) {
+            return Error() << "Property '" << *name << "' does not starts with 'persist.'";
         }
         auto value = ReadString();
         if (!value) {
             return Error() << "Could not read value: " << value.error();
         }
-        result.emplace_back(*key, *value);
-    }
-
-    if (result.size() != *num_properties) {
-        return Error() << "Mismatch of number of persistent properties read, " << result.size()
-                       << " and number of persistent properties expected, " << *num_properties;
+        AddPersistentProperty(*name, *value, &result);
     }
 
     return result;
@@ -220,9 +219,7 @@
     return result;
 }
 
-}  // namespace
-
-Result<std::vector<std::pair<std::string, std::string>>> LoadPersistentPropertyFile() {
+Result<std::string> ReadPersistentPropertyFile() {
     const std::string temp_filename = persistent_property_filename + ".tmp";
     if (access(temp_filename.c_str(), F_OK) == 0) {
         LOG(INFO)
@@ -234,51 +231,47 @@
     if (!file_contents) {
         return Error() << "Unable to read persistent property file: " << file_contents.error();
     }
+    return *file_contents;
+}
+
+}  // namespace
+
+Result<PersistentProperties> LoadPersistentPropertyFile() {
+    auto file_contents = ReadPersistentPropertyFile();
+    if (!file_contents) return file_contents.error();
+
+    // Check the intermediate "I should have used protobufs from the start" format.
+    // TODO: Remove this.
     auto parsed_contents = PersistentPropertyFileParser(*file_contents).Parse();
-    if (!parsed_contents) {
-        // If the file cannot be parsed, then we don't have any recovery mechanisms, so we delete
-        // it to allow for future writes to take place successfully.
-        unlink(persistent_property_filename.c_str());
-        return Error() << "Unable to parse persistent property file: " << parsed_contents.error();
+    if (parsed_contents) {
+        LOG(INFO) << "Intermediate format persistent property file found, converting to protobuf";
+
+        // Update to the protobuf format
+        WritePersistentPropertyFile(*parsed_contents);
+        return parsed_contents;
     }
-    return parsed_contents;
+
+    PersistentProperties persistent_properties;
+    if (persistent_properties.ParseFromString(*file_contents)) return persistent_properties;
+
+    // If the file cannot be parsed in either format, then we don't have any recovery
+    // mechanisms, so we delete it to allow for future writes to take place successfully.
+    unlink(persistent_property_filename.c_str());
+    return Error() << "Unable to parse persistent property file: " << parsed_contents.error();
 }
 
-std::string GenerateFileContents(
-    const std::vector<std::pair<std::string, std::string>>& persistent_properties) {
-    std::string result;
-
-    uint32_t magic = kMagic;
-    result.append(reinterpret_cast<char*>(&magic), sizeof(uint32_t));
-
-    uint32_t version = 1;
-    result.append(reinterpret_cast<char*>(&version), sizeof(uint32_t));
-
-    uint32_t num_properties = persistent_properties.size();
-    result.append(reinterpret_cast<char*>(&num_properties), sizeof(uint32_t));
-
-    for (const auto& [key, value] : persistent_properties) {
-        uint32_t key_length = key.length();
-        result.append(reinterpret_cast<char*>(&key_length), sizeof(uint32_t));
-        result.append(key);
-        uint32_t value_length = value.length();
-        result.append(reinterpret_cast<char*>(&value_length), sizeof(uint32_t));
-        result.append(value);
-    }
-    return result;
-}
-
-Result<Success> WritePersistentPropertyFile(
-    const std::vector<std::pair<std::string, std::string>>& persistent_properties) {
-    auto file_contents = GenerateFileContents(persistent_properties);
-
+Result<Success> WritePersistentPropertyFile(const PersistentProperties& persistent_properties) {
     const std::string temp_filename = persistent_property_filename + ".tmp";
     unique_fd fd(TEMP_FAILURE_RETRY(
         open(temp_filename.c_str(), O_WRONLY | O_CREAT | O_NOFOLLOW | O_TRUNC | O_CLOEXEC, 0600)));
     if (fd == -1) {
         return ErrnoError() << "Could not open temporary properties file";
     }
-    if (!WriteStringToFd(file_contents, fd)) {
+    std::string serialized_string;
+    if (!persistent_properties.SerializeToString(&serialized_string)) {
+        return Error() << "Unable to serialize properties";
+    }
+    if (!WriteStringToFd(serialized_string, fd)) {
         return ErrnoError() << "Unable to write file contents";
     }
     fsync(fd);
@@ -295,26 +288,30 @@
 // Persistent properties are not written often, so we rather not keep any data in memory and read
 // then rewrite the persistent property file for each update.
 void WritePersistentProperty(const std::string& name, const std::string& value) {
-    auto persistent_properties = LoadPersistentPropertyFile();
-    if (!persistent_properties) {
+    auto file_contents = ReadPersistentPropertyFile();
+    PersistentProperties persistent_properties;
+
+    if (!file_contents || !persistent_properties.ParseFromString(*file_contents)) {
         LOG(ERROR) << "Recovering persistent properties from memory: "
-                   << persistent_properties.error();
+                   << (!file_contents ? file_contents.error_string() : "Could not parse protobuf");
         persistent_properties = LoadPersistentPropertiesFromMemory();
     }
-    auto it = std::find_if(persistent_properties->begin(), persistent_properties->end(),
-                           [&name](const auto& entry) { return entry.first == name; });
-    if (it != persistent_properties->end()) {
-        *it = {name, value};
+    auto it = std::find_if(persistent_properties.mutable_properties()->begin(),
+                           persistent_properties.mutable_properties()->end(),
+                           [&name](const auto& record) { return record.name() == name; });
+    if (it != persistent_properties.mutable_properties()->end()) {
+        it->set_name(name);
+        it->set_value(value);
     } else {
-        persistent_properties->emplace_back(name, value);
+        AddPersistentProperty(name, value, &persistent_properties);
     }
 
-    if (auto result = WritePersistentPropertyFile(*persistent_properties); !result) {
+    if (auto result = WritePersistentPropertyFile(persistent_properties); !result) {
         LOG(ERROR) << "Could not store persistent property: " << result.error();
     }
 }
 
-std::vector<std::pair<std::string, std::string>> LoadPersistentProperties() {
+PersistentProperties LoadPersistentProperties() {
     auto persistent_properties = LoadPersistentPropertyFile();
 
     if (!persistent_properties) {
diff --git a/init/persistent_properties.h b/init/persistent_properties.h
index d84d9db..5f4df85 100644
--- a/init/persistent_properties.h
+++ b/init/persistent_properties.h
@@ -18,22 +18,19 @@
 #define _INIT_PERSISTENT_PROPERTIES_H
 
 #include <string>
-#include <vector>
 
 #include "result.h"
+#include "system/core/init/persistent_properties.pb.h"
 
 namespace android {
 namespace init {
 
-std::vector<std::pair<std::string, std::string>> LoadPersistentProperties();
+PersistentProperties LoadPersistentProperties();
 void WritePersistentProperty(const std::string& name, const std::string& value);
 
 // Exposed only for testing
-Result<std::vector<std::pair<std::string, std::string>>> LoadPersistentPropertyFile();
-std::string GenerateFileContents(
-    const std::vector<std::pair<std::string, std::string>>& persistent_properties);
-Result<Success> WritePersistentPropertyFile(
-    const std::vector<std::pair<std::string, std::string>>& persistent_properties);
+Result<PersistentProperties> LoadPersistentPropertyFile();
+Result<Success> WritePersistentPropertyFile(const PersistentProperties& persistent_properties);
 extern std::string persistent_property_filename;
 
 }  // namespace init
diff --git a/init/persistent_properties.proto b/init/persistent_properties.proto
new file mode 100644
index 0000000..c8d2e3a
--- /dev/null
+++ b/init/persistent_properties.proto
@@ -0,0 +1,27 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+syntax = "proto2";
+option optimize_for = LITE_RUNTIME;
+
+message PersistentProperties {
+    message PersistentPropertyRecord {
+        optional string name = 1;
+        optional string value = 2;
+    }
+
+    repeated PersistentPropertyRecord properties = 1;
+}
diff --git a/init/persistent_properties_test.cpp b/init/persistent_properties_test.cpp
index 9ab5b22..875a4f3 100644
--- a/init/persistent_properties_test.cpp
+++ b/init/persistent_properties_test.cpp
@@ -18,6 +18,8 @@
 
 #include <errno.h>
 
+#include <vector>
+
 #include <android-base/test_utils.h>
 #include <gtest/gtest.h>
 
@@ -28,34 +30,40 @@
 namespace android {
 namespace init {
 
-TEST(persistent_properties, GeneratedContents) {
-    const std::vector<std::pair<std::string, std::string>> persistent_properties = {
-        {"persist.abc", ""},
-        {"persist.def", "test_success"},
+PersistentProperties VectorToPersistentProperties(
+    const std::vector<std::pair<std::string, std::string>>& input_properties) {
+    PersistentProperties persistent_properties;
+
+    for (const auto& [name, value] : input_properties) {
+        auto persistent_property_record = persistent_properties.add_properties();
+        persistent_property_record->set_name(name);
+        persistent_property_record->set_value(value);
+    }
+
+    return persistent_properties;
+}
+
+void CheckPropertiesEqual(std::vector<std::pair<std::string, std::string>> expected,
+                          const PersistentProperties& persistent_properties) {
+    for (const auto& persistent_property_record : persistent_properties.properties()) {
+        auto it = std::find_if(expected.begin(), expected.end(),
+                               [persistent_property_record](const auto& entry) {
+                                   return entry.first == persistent_property_record.name() &&
+                                          entry.second == persistent_property_record.value();
+                               });
+        ASSERT_TRUE(it != expected.end())
+            << "Found unexpected proprety (" << persistent_property_record.name() << ", "
+            << persistent_property_record.value() << ")";
+        expected.erase(it);
+    }
+    auto joiner = [](const std::vector<std::pair<std::string, std::string>>& vector) {
+        std::string result;
+        for (const auto& [name, value] : vector) {
+            result += " (" + name + ", " + value + ")";
+        }
+        return result;
     };
-    auto generated_contents = GenerateFileContents(persistent_properties);
-
-    // Manually serialized contents below:
-    std::string file_contents;
-    // All values below are written and read as little endian.
-    // Add magic value: 0x8495E0B4
-    file_contents += "\xB4\xE0\x95\x84"s;
-    // Add version: 1
-    file_contents += "\x01\x00\x00\x00"s;
-    // Add number of properties: 2
-    file_contents += "\x02\x00\x00\x00"s;
-
-    // Add first key: persist.abc
-    file_contents += "\x0B\x00\x00\x00persist.abc"s;
-    // Add first value: (empty string)
-    file_contents += "\x00\x00\x00\x00"s;
-
-    // Add second key: persist.def
-    file_contents += "\x0B\x00\x00\x00persist.def"s;
-    // Add second value: test_success
-    file_contents += "\x0C\x00\x00\x00test_success"s;
-
-    EXPECT_EQ(file_contents, generated_contents);
+    EXPECT_TRUE(expected.empty()) << "Did not find expected properties:" << joiner(expected);
 }
 
 TEST(persistent_properties, EndToEnd) {
@@ -70,41 +78,15 @@
         {"persist.test.new.line", "abc\n\n\nabc"},
         {"persist.test.numbers", "1234567890"},
         {"persist.test.non.ascii", "\x00\x01\x02\xFF\xFE\xFD\x7F\x8F\x9F"},
-        // We don't currently allow for non-ascii keys for system properties, but this is a policy
+        // We don't currently allow for non-ascii names for system properties, but this is a policy
         // decision, not a technical limitation.
-        {"persist.\x00\x01\x02\xFF\xFE\xFD\x7F\x8F\x9F", "non-ascii-key"},
+        {"persist.\x00\x01\x02\xFF\xFE\xFD\x7F\x8F\x9F", "non-ascii-name"},
     };
 
-    ASSERT_TRUE(WritePersistentPropertyFile(persistent_properties));
+    ASSERT_TRUE(WritePersistentPropertyFile(VectorToPersistentProperties(persistent_properties)));
 
     auto read_back_properties = LoadPersistentProperties();
-    EXPECT_EQ(persistent_properties, read_back_properties);
-}
-
-TEST(persistent_properties, BadMagic) {
-    TemporaryFile tf;
-    ASSERT_TRUE(tf.fd != -1);
-    persistent_property_filename = tf.path;
-
-    ASSERT_TRUE(WriteFile(tf.path, "ab"));
-
-    auto read_back_properties = LoadPersistentPropertyFile();
-
-    ASSERT_FALSE(read_back_properties);
-    EXPECT_EQ(
-        "Unable to parse persistent property file: Could not read magic value: Input buffer not "
-        "large enough to read uint32_t",
-        read_back_properties.error_string());
-
-    ASSERT_TRUE(WriteFile(tf.path, "\xFF\xFF\xFF\xFF"));
-
-    read_back_properties = LoadPersistentPropertyFile();
-
-    ASSERT_FALSE(read_back_properties);
-    EXPECT_EQ(
-        "Unable to parse persistent property file: Magic value '0xffffffff' does not match "
-        "expected value '0x8495e0b4'",
-        read_back_properties.error_string());
+    CheckPropertiesEqual(persistent_properties, read_back_properties);
 }
 
 TEST(persistent_properties, AddProperty) {
@@ -115,7 +97,7 @@
     std::vector<std::pair<std::string, std::string>> persistent_properties = {
         {"persist.sys.timezone", "America/Los_Angeles"},
     };
-    ASSERT_TRUE(WritePersistentPropertyFile(persistent_properties));
+    ASSERT_TRUE(WritePersistentPropertyFile(VectorToPersistentProperties(persistent_properties)));
 
     WritePersistentProperty("persist.sys.locale", "pt-BR");
 
@@ -125,7 +107,7 @@
     };
 
     auto read_back_properties = LoadPersistentProperties();
-    EXPECT_EQ(persistent_properties_expected, read_back_properties);
+    CheckPropertiesEqual(persistent_properties_expected, read_back_properties);
 }
 
 TEST(persistent_properties, UpdateProperty) {
@@ -137,7 +119,7 @@
         {"persist.sys.locale", "en-US"},
         {"persist.sys.timezone", "America/Los_Angeles"},
     };
-    ASSERT_TRUE(WritePersistentPropertyFile(persistent_properties));
+    ASSERT_TRUE(WritePersistentPropertyFile(VectorToPersistentProperties(persistent_properties)));
 
     WritePersistentProperty("persist.sys.locale", "pt-BR");
 
@@ -147,7 +129,7 @@
     };
 
     auto read_back_properties = LoadPersistentProperties();
-    EXPECT_EQ(persistent_properties_expected, read_back_properties);
+    CheckPropertiesEqual(persistent_properties_expected, read_back_properties);
 }
 
 TEST(persistent_properties, UpdatePropertyBadParse) {
@@ -160,13 +142,14 @@
     WritePersistentProperty("persist.sys.locale", "pt-BR");
 
     auto read_back_properties = LoadPersistentProperties();
-    EXPECT_GT(read_back_properties.size(), 0U);
+    EXPECT_GT(read_back_properties.properties().size(), 0);
 
-    auto it = std::find_if(
-        read_back_properties.begin(), read_back_properties.end(), [](const auto& entry) {
-            return entry.first == "persist.sys.locale" && entry.second == "pt-BR";
-        });
-    EXPECT_FALSE(it == read_back_properties.end());
+    auto it =
+        std::find_if(read_back_properties.properties().begin(),
+                     read_back_properties.properties().end(), [](const auto& entry) {
+                         return entry.name() == "persist.sys.locale" && entry.value() == "pt-BR";
+                     });
+    EXPECT_FALSE(it == read_back_properties.properties().end());
 }
 
 }  // namespace init
diff --git a/init/property_service.cpp b/init/property_service.cpp
index 5f5ed40..db2d472 100644
--- a/init/property_service.cpp
+++ b/init/property_service.cpp
@@ -641,8 +641,8 @@
     load_override_properties();
     /* Read persistent properties after all default values have been loaded. */
     auto persistent_properties = LoadPersistentProperties();
-    for (const auto& [name, value] : persistent_properties) {
-        property_set(name, value);
+    for (const auto& persistent_property_record : persistent_properties.properties()) {
+        property_set(persistent_property_record.name(), persistent_property_record.value());
     }
     persistent_properties_loaded = true;
     property_set("ro.persistent_properties.ready", "true");