diff --git a/Checkpoint.cpp b/Checkpoint.cpp
index e238acf..ce0d00c 100644
--- a/Checkpoint.cpp
+++ b/Checkpoint.cpp
@@ -26,6 +26,7 @@
 #include <android-base/file.h>
 #include <android-base/logging.h>
 #include <android-base/parseint.h>
+#include <android-base/properties.h>
 #include <android-base/unique_fd.h>
 #include <android/hardware/boot/1.0/IBootControl.h>
 #include <cutils/android_reboot.h>
@@ -36,6 +37,7 @@
 #include <sys/mount.h>
 #include <sys/stat.h>
 
+using android::base::SetProperty;
 using android::binder::Status;
 using android::hardware::hidl_string;
 using android::hardware::boot::V1_0::BoolResult;
@@ -81,8 +83,15 @@
     return Status::ok();
 }
 
+namespace {
+
+bool isCheckpointing = false;
+}
+
 Status cp_commitChanges() {
-    if (!cp_needsCheckpoint()) return Status::ok();
+    if (!isCheckpointing) {
+        return Status::ok();
+    }
     // Must take action for list of mounted checkpointed things here
     // To do this, we walk the list of mounted file systems.
     // But we also need to get the matching fstab entries to see
@@ -115,6 +124,8 @@
                 return Status::fromExceptionCode(EINVAL, "Failed to set bow state");
         }
     }
+    SetProperty("vold.checkpoint_committed", "1");
+    isCheckpointing = false;
     if (!android::base::RemoveFileIfExists(kMetadataCPFile, &err_str))
         return Status::fromExceptionCode(errno, err_str.c_str());
     return Status::ok();
@@ -152,10 +163,16 @@
     std::string content;
     sp<IBootControl> module = IBootControl::getService();
 
-    if (module && module->isSlotMarkedSuccessful(module->getCurrentSlot()) == BoolResult::FALSE)
+    if (module && module->isSlotMarkedSuccessful(module->getCurrentSlot()) == BoolResult::FALSE) {
+        isCheckpointing = true;
         return true;
+    }
     ret = android::base::ReadFileToString(kMetadataCPFile, &content);
-    if (ret) return content != "0";
+    if (ret) {
+        ret = content != "0";
+        isCheckpointing = ret;
+        return ret;
+    }
     return false;
 }
 
diff --git a/KeyStorage.cpp b/KeyStorage.cpp
index 035c7b7..9dd4991 100644
--- a/KeyStorage.cpp
+++ b/KeyStorage.cpp
@@ -202,7 +202,7 @@
                                 km::KeyPurpose purpose, const km::AuthorizationSet& keyParams,
                                 const km::AuthorizationSet& opParams,
                                 const km::HardwareAuthToken& authToken,
-                                km::AuthorizationSet* outParams) {
+                                km::AuthorizationSet* outParams, bool keepOld) {
     auto kmKeyPath = dir + "/" + kFn_keymaster_key_blob;
     std::string kmKey;
     if (!readFileToString(kmKeyPath, &kmKey)) return KeymasterOperation();
@@ -219,12 +219,14 @@
         if (!keymaster.upgradeKey(kmKey, keyParams, &newKey)) return KeymasterOperation();
         auto newKeyPath = dir + "/" + kFn_keymaster_key_blob_upgraded;
         if (!writeStringToFile(newKey, newKeyPath)) return KeymasterOperation();
-        if (rename(newKeyPath.c_str(), kmKeyPath.c_str()) != 0) {
-            PLOG(ERROR) << "Unable to move upgraded key to location: " << kmKeyPath;
-            return KeymasterOperation();
-        }
-        if (!keymaster.deleteKey(kmKey)) {
-            LOG(ERROR) << "Key deletion failed during upgrade, continuing anyway: " << dir;
+        if (!keepOld) {
+            if (rename(newKeyPath.c_str(), kmKeyPath.c_str()) != 0) {
+                PLOG(ERROR) << "Unable to move upgraded key to location: " << kmKeyPath;
+                return KeymasterOperation();
+            }
+            if (!keymaster.deleteKey(kmKey)) {
+                LOG(ERROR) << "Key deletion failed during upgrade, continuing anyway: " << dir;
+            }
         }
         kmKey = newKey;
         LOG(INFO) << "Key upgraded: " << dir;
@@ -233,12 +235,12 @@
 
 static bool encryptWithKeymasterKey(Keymaster& keymaster, const std::string& dir,
                                     const km::AuthorizationSet& keyParams,
-                                    const km::HardwareAuthToken& authToken,
-                                    const KeyBuffer& message, std::string* ciphertext) {
+                                    const km::HardwareAuthToken& authToken, const KeyBuffer& message,
+                                    std::string* ciphertext, bool keepOld) {
     km::AuthorizationSet opParams;
     km::AuthorizationSet outParams;
-    auto opHandle =
-        begin(keymaster, dir, km::KeyPurpose::ENCRYPT, keyParams, opParams, authToken, &outParams);
+    auto opHandle = begin(keymaster, dir, km::KeyPurpose::ENCRYPT, keyParams, opParams, authToken,
+                          &outParams, keepOld);
     if (!opHandle) return false;
     auto nonceBlob = outParams.GetTagValue(km::TAG_NONCE);
     if (!nonceBlob.isOk()) {
@@ -262,13 +264,14 @@
 static bool decryptWithKeymasterKey(Keymaster& keymaster, const std::string& dir,
                                     const km::AuthorizationSet& keyParams,
                                     const km::HardwareAuthToken& authToken,
-                                    const std::string& ciphertext, KeyBuffer* message) {
+                                    const std::string& ciphertext, KeyBuffer* message,
+                                    bool keepOld) {
     auto nonce = ciphertext.substr(0, GCM_NONCE_BYTES);
     auto bodyAndMac = ciphertext.substr(GCM_NONCE_BYTES);
     auto opParams = km::AuthorizationSetBuilder().Authorization(km::TAG_NONCE,
                                                                 km::support::blob2hidlVec(nonce));
-    auto opHandle =
-        begin(keymaster, dir, km::KeyPurpose::DECRYPT, keyParams, opParams, authToken, nullptr);
+    auto opHandle = begin(keymaster, dir, km::KeyPurpose::DECRYPT, keyParams, opParams, authToken,
+                          nullptr, keepOld);
     if (!opHandle) return false;
     if (!opHandle.updateCompletely(bodyAndMac, message)) return false;
     if (!opHandle.finish(nullptr)) return false;
@@ -474,7 +477,8 @@
         km::AuthorizationSet keyParams;
         km::HardwareAuthToken authToken;
         std::tie(keyParams, authToken) = beginParams(auth, appId);
-        if (!encryptWithKeymasterKey(keymaster, dir, keyParams, authToken, key, &encryptedKey))
+        if (!encryptWithKeymasterKey(keymaster, dir, keyParams, authToken, key, &encryptedKey,
+                                     false))
             return false;
     } else {
         if (!encryptWithoutKeymaster(appId, key, &encryptedKey)) return false;
@@ -502,7 +506,8 @@
     return true;
 }
 
-bool retrieveKey(const std::string& dir, const KeyAuthentication& auth, KeyBuffer* key) {
+bool retrieveKey(const std::string& dir, const KeyAuthentication& auth, KeyBuffer* key,
+                 bool keepOld) {
     std::string version;
     if (!readFileToString(dir + "/" + kFn_version, &version)) return false;
     if (version != kCurrentVersion) {
@@ -527,7 +532,8 @@
         km::AuthorizationSet keyParams;
         km::HardwareAuthToken authToken;
         std::tie(keyParams, authToken) = beginParams(auth, appId);
-        if (!decryptWithKeymasterKey(keymaster, dir, keyParams, authToken, encryptedMessage, key))
+        if (!decryptWithKeymasterKey(keymaster, dir, keyParams, authToken, encryptedMessage, key,
+                                     keepOld))
             return false;
     } else {
         if (!decryptWithoutKeymaster(appId, encryptedMessage, key)) return false;
diff --git a/KeyStorage.h b/KeyStorage.h
index 786e5b4..6aaf3ad 100644
--- a/KeyStorage.h
+++ b/KeyStorage.h
@@ -61,7 +61,8 @@
                         const KeyAuthentication& auth, const KeyBuffer& key);
 
 // Retrieve the key from the named directory.
-bool retrieveKey(const std::string& dir, const KeyAuthentication& auth, KeyBuffer* key);
+bool retrieveKey(const std::string& dir, const KeyAuthentication& auth, KeyBuffer* key,
+                 bool keepOld = false);
 
 // Securely destroy the key stored in the named directory and delete the directory.
 bool destroyKey(const std::string& dir);
diff --git a/KeyUtil.cpp b/KeyUtil.cpp
index a17b8b2..12cae9b 100644
--- a/KeyUtil.cpp
+++ b/KeyUtil.cpp
@@ -169,10 +169,10 @@
 }
 
 bool retrieveKey(bool create_if_absent, const std::string& key_path, const std::string& tmp_path,
-                 KeyBuffer* key) {
+                 KeyBuffer* key, bool keepOld) {
     if (pathExists(key_path)) {
         LOG(DEBUG) << "Key exists, using: " << key_path;
-        if (!retrieveKey(key_path, kEmptyAuthentication, key)) return false;
+        if (!retrieveKey(key_path, kEmptyAuthentication, key, keepOld)) return false;
     } else {
         if (!create_if_absent) {
             LOG(ERROR) << "No key found in " << key_path;
diff --git a/KeyUtil.h b/KeyUtil.h
index b4115f4..7ee6725 100644
--- a/KeyUtil.h
+++ b/KeyUtil.h
@@ -33,7 +33,7 @@
                            const std::string& key_path, const std::string& tmp_path,
                            std::string* key_ref);
 bool retrieveKey(bool create_if_absent, const std::string& key_path, const std::string& tmp_path,
-                 KeyBuffer* key);
+                 KeyBuffer* key, bool keepOld = true);
 
 }  // namespace vold
 }  // namespace android
diff --git a/MetadataCrypt.cpp b/MetadataCrypt.cpp
index e156424..8b4d04e 100644
--- a/MetadataCrypt.cpp
+++ b/MetadataCrypt.cpp
@@ -30,6 +30,7 @@
 
 #include <linux/dm-ioctl.h>
 
+#include <android-base/file.h>
 #include <android-base/logging.h>
 #include <android-base/properties.h>
 #include <android-base/unique_fd.h>
@@ -40,6 +41,7 @@
 #include "EncryptInplace.h"
 #include "KeyStorage.h"
 #include "KeyUtil.h"
+#include "Keymaster.h"
 #include "Utils.h"
 #include "VoldUtil.h"
 #include "secontext.h"
@@ -52,6 +54,9 @@
 
 static const std::string kDmNameUserdata = "userdata";
 
+static const char* kFn_keymaster_key_blob = "keymaster_key_blob";
+static const char* kFn_keymaster_key_blob_upgraded = "keymaster_key_blob_upgraded";
+
 static bool mount_via_fs_mgr(const char* mount_point, const char* blk_device) {
     // fs_mgr_do_mount runs fsck. Use setexeccon to run trusted
     // partitions in the fsck domain.
@@ -74,12 +79,41 @@
     return true;
 }
 
+namespace android {
+namespace vold {
+
+// Note: It is possible to orphan a key if it is removed before deleting
+// Update this once keymaster APIs change, and we have a proper commit.
+static void commit_key(std::string dir) {
+    while (!android::base::WaitForProperty("vold.checkpoint_committed", "1")) {
+        LOG(ERROR) << "Wait for boot timed out";
+    }
+    Keymaster keymaster;
+    auto keyPath = dir + "/" + kFn_keymaster_key_blob;
+    auto newKeyPath = dir + "/" + kFn_keymaster_key_blob_upgraded;
+    std::string key;
+
+    if (!android::base::ReadFileToString(keyPath, &key)) {
+        LOG(ERROR) << "Failed to read old key: " << dir;
+        return;
+    }
+    if (rename(newKeyPath.c_str(), keyPath.c_str()) != 0) {
+        PLOG(ERROR) << "Unable to move upgraded key to location: " << keyPath;
+        return;
+    }
+    if (!keymaster.deleteKey(key)) {
+        LOG(ERROR) << "Key deletion failed during upgrade, continuing anyway: " << dir;
+    }
+    LOG(INFO) << "Old Key deleted: " << dir;
+}
+
 static bool read_key(struct fstab_rec const* data_rec, bool create_if_absent, KeyBuffer* key) {
     if (!data_rec->key_dir) {
         LOG(ERROR) << "Failed to get key_dir";
         return false;
     }
     std::string key_dir = data_rec->key_dir;
+    std::string sKey;
     auto dir = key_dir + "/key";
     LOG(DEBUG) << "key_dir/key: " << dir;
     if (fs_mkdirs(dir.c_str(), 0700)) {
@@ -87,10 +121,30 @@
         return false;
     }
     auto temp = key_dir + "/tmp";
-    if (!android::vold::retrieveKey(create_if_absent, dir, temp, key)) return false;
+    auto newKeyPath = dir + "/" + kFn_keymaster_key_blob_upgraded;
+    /* If we have a leftover upgraded key, delete it.
+     * We either failed an update and must return to the old key,
+     * or we rebooted before commiting the keys in a freak accident.
+     * Either way, we can re-upgrade the key if we need to.
+     */
+    Keymaster keymaster;
+    if (pathExists(newKeyPath)) {
+        if (!android::base::ReadFileToString(newKeyPath, &sKey))
+            LOG(ERROR) << "Failed to read old key: " << dir;
+        else if (!keymaster.deleteKey(sKey))
+            LOG(ERROR) << "Old key deletion failed, continuing anyway: " << dir;
+        else
+            unlink(newKeyPath.c_str());
+    }
+    bool needs_cp = cp_needsCheckpoint();
+    if (!android::vold::retrieveKey(create_if_absent, dir, temp, key, needs_cp)) return false;
+    if (needs_cp && pathExists(newKeyPath)) std::thread(commit_key, dir).detach();
     return true;
 }
 
+}  // namespace vold
+}  // namespace android
+
 static KeyBuffer default_key_params(const std::string& real_blkdev, const KeyBuffer& key) {
     KeyBuffer hex_key;
     if (android::vold::StrToHex(key, hex_key) != android::OK) {