diff --git a/ondevice-signing/Android.bp b/ondevice-signing/Android.bp
index 5db19b7..1c3706d 100644
--- a/ondevice-signing/Android.bp
+++ b/ondevice-signing/Android.bp
@@ -26,7 +26,6 @@
 tidy_errors = [
   "cert-err34-c",
   "google-default-arguments",
-  "google-explicit-constructor",
   "google-runtime-int",
   "google-runtime-member-string-references",
   "misc-move-const-arg",
@@ -87,17 +86,22 @@
     "CertUtils.cpp",
     "Keymaster.cpp",
     "KeymasterSigningKey.cpp",
+    "KeystoreKey.cpp",
     "VerityUtils.cpp",
   ],
 
   static_libs: [
     "libmini_keyctl_static", // TODO need static?
     "libc++fs",
+    "lib_odsign_proto",
   ],
 
   shared_libs: [
     "android.hardware.keymaster@4.1",
+    "android.system.keystore2-V1-cpp",
+    "android.hardware.security.keymint-V1-cpp",
     "libbase",
+    "libbinder",
     "libcrypto",
     "libcrypto_utils",
     "libfsverity",
@@ -106,6 +110,7 @@
     "libkeymaster4support", // For authorization_set
     "libkeymaster4_1support",
     "libkeyutils",
+    "libprotobuf-cpp-full",
     "libutils",
   ],
 }
diff --git a/ondevice-signing/CertUtils.cpp b/ondevice-signing/CertUtils.cpp
index 6b24391..cbd1942 100644
--- a/ondevice-signing/CertUtils.cpp
+++ b/ondevice-signing/CertUtils.cpp
@@ -25,6 +25,9 @@
 
 #include <fcntl.h>
 #include <vector>
+
+#include "KeyConstants.h"
+
 const char kBasicConstraints[] = "CA:TRUE";
 const char kKeyUsage[] = "critical,keyCertSign,cRLSign,digitalSignature";
 const char kSubjectKeyIdentifier[] = "hash";
@@ -52,6 +55,33 @@
     return true;
 }
 
+Result<bssl::UniquePtr<RSA>> getRsa(const std::vector<uint8_t>& publicKey) {
+    bssl::UniquePtr<RSA> rsaPubkey(RSA_new());
+    rsaPubkey->n = BN_new();
+    rsaPubkey->e = BN_new();
+
+    BN_bin2bn(publicKey.data(), publicKey.size(), rsaPubkey->n);
+    BN_set_word(rsaPubkey->e, kRsaKeyExponent);
+
+    return rsaPubkey;
+}
+
+Result<void> verifySignature(const std::string& message, const std::string& signature,
+                             const std::vector<uint8_t>& publicKey) {
+    auto rsaKey = getRsa(publicKey);
+    uint8_t hashBuf[SHA256_DIGEST_LENGTH];
+    SHA256(const_cast<uint8_t*>(reinterpret_cast<const uint8_t*>(message.c_str())),
+           message.length(), hashBuf);
+
+    bool success = RSA_verify(NID_sha256, hashBuf, sizeof(hashBuf),
+                              (const uint8_t*)signature.c_str(), signature.length(), rsaKey->get());
+
+    if (!success) {
+        return Error() << "Failed to verify signature.";
+    }
+    return {};
+}
+
 Result<void> createSelfSignedCertificate(
     const std::vector<uint8_t>& publicKey,
     const std::function<Result<std::string>(const std::string&)>& signFunction,
@@ -66,8 +96,13 @@
     X509_gmtime_adj(X509_get_notBefore(x509.get()), 0);
     X509_gmtime_adj(X509_get_notAfter(x509.get()), kCertLifetimeSeconds);
 
-    auto pubKeyData = publicKey.data();
-    EVP_PKEY* public_key = d2i_PUBKEY(nullptr, &pubKeyData, publicKey.size());
+    // "publicKey" corresponds to the raw public key bytes - need to create
+    // a new RSA key with the correct exponent.
+    auto rsaPubkey = getRsa(publicKey);
+
+    EVP_PKEY* public_key = EVP_PKEY_new();
+    EVP_PKEY_assign_RSA(public_key, rsaPubkey->release());
+
     if (!X509_set_pubkey(x509.get(), public_key)) {
         return Error() << "Unable to set x509 public key";
     }
@@ -117,6 +152,7 @@
     i2d_X509_fp(f, x509.get());
     fclose(f);
 
+    EVP_PKEY_free(public_key);
     return {};
 }
 
@@ -142,13 +178,25 @@
     return pubKey;
 }
 
-Result<std::vector<uint8_t>> extractPublicKeyFromX509(const std::vector<uint8_t>& keyData) {
+Result<std::vector<uint8_t>>
+extractPublicKeyFromSubjectPublicKeyInfo(const std::vector<uint8_t>& keyData) {
     auto keyDataBytes = keyData.data();
     EVP_PKEY* public_key = d2i_PUBKEY(nullptr, &keyDataBytes, keyData.size());
 
     return extractPublicKey(public_key);
 }
 
+Result<std::vector<uint8_t>> extractPublicKeyFromX509(const std::vector<uint8_t>& keyData) {
+    auto keyDataBytes = keyData.data();
+    bssl::UniquePtr<X509> decoded_cert(d2i_X509(nullptr, &keyDataBytes, keyData.size()));
+    if (decoded_cert.get() == nullptr) {
+        return Error() << "Failed to decode X509 certificate.";
+    }
+    bssl::UniquePtr<EVP_PKEY> decoded_pkey(X509_get_pubkey(decoded_cert.get()));
+
+    return extractPublicKey(decoded_pkey.get());
+}
+
 Result<std::vector<uint8_t>> extractPublicKeyFromX509(const std::string& path) {
     X509* cert;
     auto f = fopen(path.c_str(), "r");
diff --git a/ondevice-signing/CertUtils.h b/ondevice-signing/CertUtils.h
index d9172d0..66dff04 100644
--- a/ondevice-signing/CertUtils.h
+++ b/ondevice-signing/CertUtils.h
@@ -25,5 +25,11 @@
 android::base::Result<std::vector<uint8_t>> createPkcs7(const std::vector<uint8_t>& signedData);
 
 android::base::Result<std::vector<uint8_t>>
-extractPublicKeyFromX509(const std::vector<uint8_t>& path);
+extractPublicKeyFromX509(const std::vector<uint8_t>& x509);
+android::base::Result<std::vector<uint8_t>>
+extractPublicKeyFromSubjectPublicKeyInfo(const std::vector<uint8_t>& subjectKeyInfo);
 android::base::Result<std::vector<uint8_t>> extractPublicKeyFromX509(const std::string& path);
+
+android::base::Result<void> verifySignature(const std::string& message,
+                                            const std::string& signature,
+                                            const std::vector<uint8_t>& publicKey);
diff --git a/ondevice-signing/KeyConstants.h b/ondevice-signing/KeyConstants.h
new file mode 100644
index 0000000..9e1a513
--- /dev/null
+++ b/ondevice-signing/KeyConstants.h
@@ -0,0 +1,18 @@
+/*
+ * Copyright (C) 2020 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.
+ */
+
+static constexpr int kRsaKeySize = 2048;
+static constexpr int kRsaKeyExponent = 65537;
diff --git a/ondevice-signing/KeymasterSigningKey.cpp b/ondevice-signing/KeymasterSigningKey.cpp
index 2b748e4..dc3ef8a 100644
--- a/ondevice-signing/KeymasterSigningKey.cpp
+++ b/ondevice-signing/KeymasterSigningKey.cpp
@@ -33,30 +33,36 @@
 using android::base::Result;
 using android::base::unique_fd;
 
+const std::string kSigningKeyBlob = "/data/misc/odsign/key.blob";
+
 KeymasterSigningKey::KeymasterSigningKey() {}
 
-Result<KeymasterSigningKey> KeymasterSigningKey::loadFromBlobAndVerify(const std::string& path) {
-    KeymasterSigningKey signingKey;
+Result<std::unique_ptr<KeymasterSigningKey>>
+KeymasterSigningKey::loadFromBlobAndVerify(const std::string& path) {
+    auto signingKey = std::make_unique<KeymasterSigningKey>();
 
-    auto status = signingKey.initializeFromKeyblob(path);
+    auto status = signingKey->initializeFromKeyblob(path);
 
     if (!status.ok()) {
         return status.error();
     }
 
-    return std::move(signingKey);
+    return signingKey;
 }
 
-Result<KeymasterSigningKey> KeymasterSigningKey::createNewKey() {
-    KeymasterSigningKey signingKey;
+Result<void> KeymasterSigningKey::saveKeyblob(const std::string& path) const {
+    int flags = O_WRONLY | O_CREAT | O_TRUNC | O_CLOEXEC;
 
-    auto status = signingKey.createSigningKey();
-
-    if (!status.ok()) {
-        return status.error();
+    unique_fd fd(TEMP_FAILURE_RETRY(open(path.c_str(), flags, 0600)));
+    if (fd == -1) {
+        return ErrnoError() << "Error creating key blob file " << path;
     }
 
-    return std::move(signingKey);
+    if (!android::base::WriteFully(fd, mVerifiedKeyBlob.data(), mVerifiedKeyBlob.size())) {
+        return ErrnoError() << "Error writing key blob file " << path;
+    } else {
+        return {};
+    }
 }
 
 Result<void> KeymasterSigningKey::createSigningKey() {
@@ -78,41 +84,45 @@
     return {};
 }
 
-Result<void> KeymasterSigningKey::saveKeyblob(const std::string& path) const {
-    int flags = O_WRONLY | O_CREAT | O_TRUNC | O_CLOEXEC;
+Result<std::unique_ptr<KeymasterSigningKey>> KeymasterSigningKey::createAndPersistNewKey() {
+    auto signingKey = std::make_unique<KeymasterSigningKey>();
 
-    unique_fd fd(TEMP_FAILURE_RETRY(open(path.c_str(), flags, 0600)));
-    if (fd == -1) {
-        return ErrnoError() << "Error creating key blob file " << path;
+    auto status = signingKey->createSigningKey();
+
+    if (!status.ok()) {
+        return status.error();
     }
 
-    if (!android::base::WriteFully(fd, mVerifiedKeyBlob.data(), mVerifiedKeyBlob.size())) {
-        return ErrnoError() << "Error writing key blob file " << path;
-    } else {
-        return {};
+    status = signingKey->saveKeyblob(kSigningKeyBlob);
+    if (!status.ok()) {
+        return status.error();
     }
+
+    return signingKey;
+}
+
+Result<SigningKey*> KeymasterSigningKey::getInstance() {
+    auto key = loadFromBlobAndVerify(kSigningKeyBlob);
+
+    if (!key.ok()) {
+        key = createAndPersistNewKey();
+        if (!key.ok()) {
+            return key.error();
+        }
+    }
+
+    return key->release();
 }
 
 Result<std::vector<uint8_t>> KeymasterSigningKey::getPublicKey() const {
-    auto publicKeyX509 = mKeymaster->extractPublicKey(mVerifiedKeyBlob);
-    if (!publicKeyX509.ok()) {
-        return publicKeyX509.error();
-    }
-    return extractPublicKeyFromX509(publicKeyX509.value());
-}
-
-Result<void> KeymasterSigningKey::createX509Cert(const std::string& outPath) const {
     auto publicKey = mKeymaster->extractPublicKey(mVerifiedKeyBlob);
-
     if (!publicKey.ok()) {
         return publicKey.error();
     }
 
-    auto keymasterSignFunction = [&](const std::string& to_be_signed) {
-        return this->sign(to_be_signed);
-    };
-    createSelfSignedCertificate(*publicKey, keymasterSignFunction, outPath);
-    return {};
+    // Keymaster returns the public key not in a full X509 cert, but just the
+    // "SubjectPublicKeyInfo"
+    return extractPublicKeyFromSubjectPublicKeyInfo(publicKey.value());
 }
 
 Result<void> KeymasterSigningKey::initializeFromKeyblob(const std::string& path) {
diff --git a/ondevice-signing/KeymasterSigningKey.h b/ondevice-signing/KeymasterSigningKey.h
index 7631059..e66781f 100644
--- a/ondevice-signing/KeymasterSigningKey.h
+++ b/ondevice-signing/KeymasterSigningKey.h
@@ -23,30 +23,36 @@
 #include <utils/StrongPointer.h>
 
 #include "Keymaster.h"
+#include "SigningKey.h"
 
-class KeymasterSigningKey {
+class KeymasterSigningKey : public SigningKey {
     using KmDevice = ::android::hardware::keymaster::V4_1::IKeymasterDevice;
 
   public:
+    friend std::unique_ptr<KeymasterSigningKey> std::make_unique<KeymasterSigningKey>();
+    virtual ~KeymasterSigningKey(){};
+
     // Allow the key to be moved around
     KeymasterSigningKey& operator=(KeymasterSigningKey&& other) = default;
     KeymasterSigningKey(KeymasterSigningKey&& other) = default;
 
-    static android::base::Result<KeymasterSigningKey>
-    loadFromBlobAndVerify(const std::string& path);
-    static android::base::Result<KeymasterSigningKey> createNewKey();
+    static android::base::Result<SigningKey*> getInstance();
 
-    /* Sign a message with an initialized signing key */
-    android::base::Result<std::string> sign(const std::string& message) const;
-    android::base::Result<void> saveKeyblob(const std::string& path) const;
-    android::base::Result<std::vector<uint8_t>> getPublicKey() const;
-    android::base::Result<void> createX509Cert(const std::string& path) const;
+    virtual android::base::Result<std::string> sign(const std::string& message) const;
+    virtual android::base::Result<std::vector<uint8_t>> getPublicKey() const;
 
   private:
     KeymasterSigningKey();
 
+    static android::base::Result<std::unique_ptr<KeymasterSigningKey>> createAndPersistNewKey();
+    static android::base::Result<std::unique_ptr<KeymasterSigningKey>>
+    loadFromBlobAndVerify(const std::string& path);
+
     android::base::Result<void> createSigningKey();
     android::base::Result<void> initializeFromKeyblob(const std::string& path);
+    android::base::Result<void> saveKeyblob(const std::string& path) const;
+
+    static android::base::Result<KeymasterSigningKey> createNewKey();
 
     std::optional<Keymaster> mKeymaster;
     std::vector<uint8_t> mVerifiedKeyBlob;
diff --git a/ondevice-signing/KeystoreKey.cpp b/ondevice-signing/KeystoreKey.cpp
new file mode 100644
index 0000000..ea84183
--- /dev/null
+++ b/ondevice-signing/KeystoreKey.cpp
@@ -0,0 +1,233 @@
+/*
+ * Copyright (C) 2021 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.
+ */
+
+#include <string>
+
+#include <android-base/file.h>
+#include <android-base/logging.h>
+#include <binder/IServiceManager.h>
+
+#include <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include "CertUtils.h"
+#include "KeyConstants.h"
+#include "KeystoreKey.h"
+
+using android::defaultServiceManager;
+using android::IServiceManager;
+using android::sp;
+using android::String16;
+
+using android::hardware::security::keymint::Algorithm;
+using android::hardware::security::keymint::Digest;
+using android::hardware::security::keymint::KeyParameter;
+using android::hardware::security::keymint::KeyParameterValue;
+using android::hardware::security::keymint::KeyPurpose;
+using android::hardware::security::keymint::PaddingMode;
+using android::hardware::security::keymint::SecurityLevel;
+using android::hardware::security::keymint::Tag;
+
+using android::system::keystore2::CreateOperationResponse;
+using android::system::keystore2::Domain;
+using android::system::keystore2::KeyDescriptor;
+using android::system::keystore2::KeyEntryResponse;
+using android::system::keystore2::KeyMetadata;
+
+using android::base::Error;
+using android::base::Result;
+
+using android::base::unique_fd;
+
+static KeyDescriptor getKeyDescriptor() {
+    // AIDL parcelable objects don't have constructor
+    static KeyDescriptor descriptor;
+    static std::once_flag flag;
+    std::call_once(flag, [&]() {
+        descriptor.domain = Domain::SELINUX;
+        descriptor.alias = String16("ondevice-signing");
+        descriptor.nspace = 101;  // odsign_key
+    });
+
+    return descriptor;
+}
+
+KeystoreKey::KeystoreKey() {}
+
+Result<KeyMetadata> KeystoreKey::createNewKey(const KeyDescriptor& descriptor) {
+    std::vector<KeyParameter> params;
+
+    KeyParameter algo;
+    algo.tag = Tag::ALGORITHM;
+    algo.value = KeyParameterValue::make<KeyParameterValue::algorithm>(Algorithm::RSA);
+    params.push_back(algo);
+
+    KeyParameter key_size;
+    key_size.tag = Tag::KEY_SIZE;
+    key_size.value = KeyParameterValue::make<KeyParameterValue::integer>(kRsaKeySize);
+    params.push_back(key_size);
+
+    KeyParameter digest;
+    digest.tag = Tag::DIGEST;
+    digest.value = KeyParameterValue::make<KeyParameterValue::digest>(Digest::SHA_2_256);
+    params.push_back(digest);
+
+    KeyParameter padding;
+    padding.tag = Tag::PADDING;
+    padding.value =
+        KeyParameterValue::make<KeyParameterValue::paddingMode>(PaddingMode::RSA_PKCS1_1_5_SIGN);
+    params.push_back(padding);
+
+    KeyParameter exponent;
+    exponent.tag = Tag::RSA_PUBLIC_EXPONENT;
+    exponent.value = KeyParameterValue::make<KeyParameterValue::longInteger>(kRsaKeyExponent);
+    params.push_back(exponent);
+
+    KeyParameter purpose;
+    purpose.tag = Tag::PURPOSE;
+    purpose.value = KeyParameterValue::make<KeyParameterValue::keyPurpose>(KeyPurpose::SIGN);
+    params.push_back(purpose);
+
+    KeyParameter auth;
+    auth.tag = Tag::NO_AUTH_REQUIRED;
+    auth.value = KeyParameterValue::make<KeyParameterValue::boolValue>(true);
+    params.push_back(auth);
+
+    KeyMetadata metadata;
+    auto status = mSecurityLevel->generateKey(descriptor, {}, params, 0, {}, &metadata);
+    if (!status.isOk()) {
+        return Error() << "Failed to create new key";
+    }
+
+    return metadata;
+}
+
+bool KeystoreKey::initialize() {
+    sp<IServiceManager> sm = defaultServiceManager();
+    if (sm == nullptr) {
+        return false;
+    }
+    auto service = sm->getService(String16("android.system.keystore2"));
+    if (service == nullptr) {
+        return false;
+    }
+    mService = interface_cast<android::system::keystore2::IKeystoreService>(service);
+    if (mService == nullptr) {
+        return false;
+    }
+
+    auto status = mService->getSecurityLevel(SecurityLevel::STRONGBOX, &mSecurityLevel);
+    if (!status.isOk()) {
+        // TODO fallback to TEE
+        return false;
+    }
+
+    auto descriptor = getKeyDescriptor();
+    // See if we can fetch an existing key
+    KeyEntryResponse keyEntryResponse;
+    LOG(INFO) << "Trying to retrieve existing keystore key...";
+    status = mService->getKeyEntry(descriptor, &keyEntryResponse);
+    if (!status.isOk()) {
+        LOG(INFO) << "Existing keystore key not found, creating new key";
+        auto newKeyStatus = createNewKey(descriptor);
+        if (!newKeyStatus.ok()) {
+            LOG(ERROR) << "Failed to create new key";
+            return false;
+        }
+        mKeyMetadata = *newKeyStatus;
+    } else {
+        mKeyMetadata = keyEntryResponse.metadata;
+    }
+
+    LOG(ERROR) << "Initialized Keystore key.";
+    return true;
+}
+
+Result<SigningKey*> KeystoreKey::getInstance() {
+    static KeystoreKey keystoreKey;
+
+    if (!keystoreKey.initialize()) {
+        return Error() << "Failed to initialize keystore key.";
+    } else {
+        return &keystoreKey;
+    }
+}
+
+static std::vector<KeyParameter> getSignOpParameters() {
+    std::vector<KeyParameter> opParameters;
+
+    KeyParameter algo;
+    algo.tag = Tag::ALGORITHM;
+    algo.value = KeyParameterValue::make<KeyParameterValue::algorithm>(Algorithm::RSA);
+    opParameters.push_back(algo);
+
+    KeyParameter digest;
+    digest.tag = Tag::DIGEST;
+    digest.value = KeyParameterValue::make<KeyParameterValue::digest>(Digest::SHA_2_256);
+    opParameters.push_back(digest);
+
+    KeyParameter padding;
+    padding.tag = Tag::PADDING;
+    padding.value =
+        KeyParameterValue::make<KeyParameterValue::paddingMode>(PaddingMode::RSA_PKCS1_1_5_SIGN);
+    opParameters.push_back(padding);
+
+    KeyParameter purpose;
+    purpose.tag = Tag::PURPOSE;
+    purpose.value = KeyParameterValue::make<KeyParameterValue::keyPurpose>(KeyPurpose::SIGN);
+    opParameters.push_back(purpose);
+
+    return opParameters;
+}
+
+Result<std::string> KeystoreKey::sign(const std::string& message) const {
+    static auto opParameters = getSignOpParameters();
+
+    CreateOperationResponse opResponse;
+
+    auto status =
+        mSecurityLevel->createOperation(getKeyDescriptor(), opParameters, false, &opResponse);
+    if (!status.isOk()) {
+        return Error() << "Failed to create keystore signing operation: "
+                       << status.serviceSpecificErrorCode();
+    }
+    auto operation = opResponse.iOperation;
+
+    std::optional<std::vector<uint8_t>> out;
+    status = operation->update({message.begin(), message.end()}, &out);
+    if (!status.isOk()) {
+        return Error() << "Failed to call keystore update operation.";
+    }
+
+    std::optional<std::vector<uint8_t>> signature;
+    status = operation->finish({}, {}, &signature);
+    if (!status.isOk()) {
+        return Error() << "Failed to call keystore finish operation.";
+    }
+
+    if (!signature.has_value()) {
+        return Error() << "Didn't receive a signature from keystore finish operation.";
+    }
+
+    std::string result{signature.value().begin(), signature.value().end()};
+
+    return result;
+}
+
+Result<std::vector<uint8_t>> KeystoreKey::getPublicKey() const {
+    return extractPublicKeyFromX509(mKeyMetadata.certificate.value());
+}
diff --git a/ondevice-signing/KeystoreKey.h b/ondevice-signing/KeystoreKey.h
new file mode 100644
index 0000000..6b9cb57
--- /dev/null
+++ b/ondevice-signing/KeystoreKey.h
@@ -0,0 +1,52 @@
+/*
+ * Copyright (C) 2020 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.
+ */
+
+#pragma once
+
+#include <optional>
+
+#include <android-base/macros.h>
+#include <android-base/result.h>
+#include <android-base/unique_fd.h>
+
+#include <utils/StrongPointer.h>
+
+#include <android/system/keystore2/IKeystoreService.h>
+
+#include "SigningKey.h"
+
+class KeystoreKey : public SigningKey {
+    using IKeystoreService = ::android::system::keystore2::IKeystoreService;
+    using IKeystoreSecurityLevel = ::android::system::keystore2::IKeystoreSecurityLevel;
+    using KeyDescriptor = ::android::system::keystore2::KeyDescriptor;
+    using KeyMetadata = ::android::system::keystore2::KeyMetadata;
+
+  public:
+    virtual ~KeystoreKey(){};
+    static android::base::Result<SigningKey*> getInstance();
+
+    virtual android::base::Result<std::string> sign(const std::string& message) const;
+    virtual android::base::Result<std::vector<uint8_t>> getPublicKey() const;
+
+  private:
+    KeystoreKey();
+    bool initialize();
+    android::base::Result<KeyMetadata> createNewKey(const KeyDescriptor& descriptor);
+
+    android::sp<IKeystoreService> mService;
+    android::sp<IKeystoreSecurityLevel> mSecurityLevel;
+    KeyMetadata mKeyMetadata;
+};
diff --git a/ondevice-signing/SigningKey.h b/ondevice-signing/SigningKey.h
new file mode 100644
index 0000000..89294fc
--- /dev/null
+++ b/ondevice-signing/SigningKey.h
@@ -0,0 +1,29 @@
+/*
+ * Copyright (C) 2020 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.
+ */
+
+#pragma once
+
+#include <android-base/macros.h>
+#include <android-base/result.h>
+
+class SigningKey {
+  public:
+    virtual ~SigningKey(){};
+    /* Sign a message with an initialized signing key */
+    virtual android::base::Result<std::string> sign(const std::string& message) const = 0;
+    /* Retrieve the associated public key */
+    virtual android::base::Result<std::vector<uint8_t>> getPublicKey() const = 0;
+};
diff --git a/ondevice-signing/VerityUtils.cpp b/ondevice-signing/VerityUtils.cpp
index b4a6a54..71ba8f6 100644
--- a/ondevice-signing/VerityUtils.cpp
+++ b/ondevice-signing/VerityUtils.cpp
@@ -15,12 +15,14 @@
  */
 
 #include <filesystem>
+#include <map>
 #include <string>
 
 #include <fcntl.h>
 #include <linux/fs.h>
 #include <sys/stat.h>
 #include <sys/types.h>
+#include <sys/wait.h>
 
 #include <android-base/logging.h>
 #include <android-base/unique_fd.h>
@@ -28,13 +30,17 @@
 #include <linux/fsverity.h>
 
 #include "CertUtils.h"
-#include "KeymasterSigningKey.h"
+#include "SigningKey.h"
+
+#define FS_VERITY_MAX_DIGEST_SIZE 64
 
 using android::base::ErrnoError;
 using android::base::Error;
 using android::base::Result;
 using android::base::unique_fd;
 
+static const char* kFsVerityInitPath = "/system/bin/fsverity_init";
+
 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
 #define cpu_to_le16(v) ((__force __le16)(uint16_t)(v))
 #define le16_to_cpu(v) ((__force uint16_t)(__le16)(v))
@@ -50,13 +56,21 @@
     __u8 digest[];
 };
 
+static std::string toHex(const std::vector<uint8_t>& data) {
+    std::stringstream ss;
+    for (auto it = data.begin(); it != data.end(); ++it) {
+        ss << std::setfill('0') << std::setw(2) << std::hex << static_cast<unsigned>(*it);
+    }
+    return ss.str();
+}
+
 static int read_callback(void* file, void* buf, size_t count) {
     int* fd = (int*)file;
     if (TEMP_FAILURE_RETRY(read(*fd, buf, count)) < 0) return errno ? -errno : -EIO;
     return 0;
 }
 
-static Result<std::vector<uint8_t>> createDigest(const std::string& path) {
+Result<std::vector<uint8_t>> createDigest(const std::string& path) {
     struct stat filestat;
     unique_fd fd(TEMP_FAILURE_RETRY(open(path.c_str(), O_RDONLY | O_CLOEXEC)));
 
@@ -74,7 +88,7 @@
     return std::vector<uint8_t>(&digest->digest[0], &digest->digest[32]);
 }
 
-static Result<std::vector<uint8_t>> signDigest(const KeymasterSigningKey& key,
+static Result<std::vector<uint8_t>> signDigest(const SigningKey& key,
                                                const std::vector<uint8_t>& digest) {
     fsverity_signed_digest* d;
     size_t signed_digest_size = sizeof(*d) + digest.size();
@@ -94,7 +108,7 @@
     return std::vector<uint8_t>(signed_digest->begin(), signed_digest->end());
 }
 
-Result<void> enableFsVerity(const std::string& path, const KeymasterSigningKey& key) {
+Result<std::string> enableFsVerity(const std::string& path, const SigningKey& key) {
     auto digest = createDigest(path);
     if (!digest.ok()) {
         return digest.error();
@@ -121,10 +135,13 @@
         return ErrnoError() << "Failed to call FS_IOC_ENABLE_VERITY on " << path;
     }
 
-    return {};
+    // Return the root hash as a hex string
+    return toHex(digest.value());
 }
 
-Result<void> addFilesToVerityRecursive(const std::string& path, const KeymasterSigningKey& key) {
+Result<std::map<std::string, std::string>> addFilesToVerityRecursive(const std::string& path,
+                                                                     const SigningKey& key) {
+    std::map<std::string, std::string> digests;
     std::error_code ec;
 
     auto it = std::filesystem::recursive_directory_iterator(path, ec);
@@ -137,14 +154,18 @@
             if (!result.ok()) {
                 return result.error();
             }
+            digests[it->path()] = *result;
         }
         ++it;
     }
+    if (ec) {
+        return Error() << "Failed to iterate " << path << ": " << ec;
+    }
 
-    return {};
+    return digests;
 }
 
-Result<bool> isFileInVerity(const std::string& path) {
+Result<std::string> isFileInVerity(const std::string& path) {
     unsigned int flags;
 
     unique_fd fd(TEMP_FAILURE_RETRY(open(path.c_str(), O_RDONLY | O_CLOEXEC)));
@@ -156,11 +177,24 @@
     if (ret < 0) {
         return ErrnoError() << "Failed to FS_IOC_GETFLAGS for " << path;
     }
+    if (!(flags & FS_VERITY_FL)) {
+        return Error() << "File is not in fs-verity: " << path;
+    }
 
-    return (flags & FS_VERITY_FL);
+    struct fsverity_digest* d;
+    d = (struct fsverity_digest*)malloc(sizeof(*d) + FS_VERITY_MAX_DIGEST_SIZE);
+    d->digest_size = FS_VERITY_MAX_DIGEST_SIZE;
+    ret = ioctl(fd, FS_IOC_MEASURE_VERITY, d);
+    if (ret < 0) {
+        return ErrnoError() << "Failed to FS_IOC_MEASURE_VERITY for " << path;
+    }
+    std::vector<uint8_t> digest_vector(&d->digest[0], &d->digest[d->digest_size]);
+
+    return toHex(digest_vector);
 }
 
-Result<void> verifyAllFilesInVerity(const std::string& path) {
+Result<std::map<std::string, std::string>> verifyAllFilesInVerity(const std::string& path) {
+    std::map<std::string, std::string> digests;
     std::error_code ec;
 
     auto it = std::filesystem::recursive_directory_iterator(path, ec);
@@ -173,12 +207,50 @@
             if (!result.ok()) {
                 return result.error();
             }
-            if (!*result) {
-                return Error() << "File " << it->path() << " not in fs-verity";
-            }
+            digests[it->path()] = *result;
         }  // TODO reject other types besides dirs?
         ++it;
     }
+    if (ec) {
+        return Error() << "Failed to iterate " << path << ": " << ec;
+    }
+
+    return digests;
+}
+
+Result<void> addCertToFsVerityKeyring(const std::string& path) {
+    const char* const argv[] = {kFsVerityInitPath, "--load-extra-key", "fsv_ods"};
+
+    int fd = open(path.c_str(), O_RDONLY | O_CLOEXEC);
+    pid_t pid = fork();
+    if (pid == 0) {
+        dup2(fd, STDIN_FILENO);
+        close(fd);
+        int argc = arraysize(argv);
+        char* argv_child[argc + 1];
+        memcpy(argv_child, argv, argc * sizeof(char*));
+        argv_child[argc] = nullptr;
+        execvp(argv_child[0], const_cast<char**>(argv_child));
+        PLOG(ERROR) << "exec in ForkExecvp";
+        _exit(EXIT_FAILURE);
+    } else {
+        close(fd);
+    }
+    if (pid == -1) {
+        return ErrnoError() << "Failed to fork.";
+    }
+    int status;
+    if (waitpid(pid, &status, 0) == -1) {
+        return ErrnoError() << "waitpid() failed.";
+    }
+    if (!WIFEXITED(status)) {
+        return Error() << kFsVerityInitPath << ": abnormal process exit";
+    }
+    if (WEXITSTATUS(status)) {
+        if (status != 0) {
+            return Error() << kFsVerityInitPath << " exited with " << status;
+        }
+    }
 
     return {};
 }
diff --git a/ondevice-signing/VerityUtils.h b/ondevice-signing/VerityUtils.h
index 1eca5a6..84af319 100644
--- a/ondevice-signing/VerityUtils.h
+++ b/ondevice-signing/VerityUtils.h
@@ -18,8 +18,11 @@
 
 #include <android-base/result.h>
 
-#include "KeymasterSigningKey.h"
+#include "SigningKey.h"
 
-android::base::Result<void> verifyAllFilesInVerity(const std::string& path);
-android::base::Result<void> addFilesToVerityRecursive(const std::string& path,
-                                                      const KeymasterSigningKey& key);
+android::base::Result<void> addCertToFsVerityKeyring(const std::string& path);
+android::base::Result<std::vector<uint8_t>> createDigest(const std::string& path);
+android::base::Result<std::map<std::string, std::string>>
+verifyAllFilesInVerity(const std::string& path);
+android::base::Result<std::map<std::string, std::string>>
+addFilesToVerityRecursive(const std::string& path, const SigningKey& key);
diff --git a/ondevice-signing/odsign_main.cpp b/ondevice-signing/odsign_main.cpp
index 3baba68..eeef868 100644
--- a/ondevice-signing/odsign_main.cpp
+++ b/ondevice-signing/odsign_main.cpp
@@ -16,11 +16,12 @@
 
 #include <fcntl.h>
 #include <filesystem>
+#include <fstream>
 #include <iomanip>
 #include <iostream>
+#include <iterator>
 #include <sys/stat.h>
 #include <sys/types.h>
-#include <sys/wait.h>
 #include <unistd.h>
 
 #include <android-base/file.h>
@@ -30,69 +31,32 @@
 
 #include "CertUtils.h"
 #include "KeymasterSigningKey.h"
+#include "KeystoreKey.h"
 #include "VerityUtils.h"
 
+#include "odsign_info.pb.h"
+
 using android::base::ErrnoError;
 using android::base::Error;
 using android::base::Result;
 
+using OdsignInfo = ::odsign::proto::OdsignInfo;
+
 const std::string kSigningKeyBlob = "/data/misc/odsign/key.blob";
 const std::string kSigningKeyCert = "/data/misc/odsign/key.cert";
+const std::string kOdsignInfo = "/data/misc/odsign/odsign.info";
+const std::string kOdsignInfoSignature = "/data/misc/odsign/odsign.info.signature";
 
 const std::string kArtArtifactsDir = "/data/misc/apexdata/com.android.art/dalvik-cache";
 
 static const char* kOdrefreshPath = "/apex/com.android.art/bin/odrefresh";
 
-static const char* kFsVerityInitPath = "/system/bin/fsverity_init";
+static const char* kFsVerityProcPath = "/proc/sys/fs/verity";
 
 static const bool kForceCompilation = false;
+static const bool kUseKeystore = false;
 
-Result<void> addCertToFsVerityKeyring(const std::string& path) {
-    const char* const argv[] = {kFsVerityInitPath, "--load-extra-key", "fsv_ods"};
-
-    // NOLINTNEXTLINE(android-cloexec-open): Deliberately not O_CLOEXEC
-    int fd = open(path.c_str(), O_RDONLY);
-    pid_t pid = fork();
-    if (pid == 0) {
-        dup2(fd, STDIN_FILENO);
-        close(fd);
-        int argc = arraysize(argv);
-        char* argv_child[argc + 1];
-        memcpy(argv_child, argv, argc * sizeof(char*));
-        argv_child[argc] = nullptr;
-        execvp(argv_child[0], const_cast<char**>(argv_child));
-        PLOG(ERROR) << "exec in ForkExecvp";
-        _exit(EXIT_FAILURE);
-    } else {
-        close(fd);
-    }
-    if (pid == -1) {
-        return ErrnoError() << "Failed to fork.";
-    }
-    int status;
-    if (waitpid(pid, &status, 0) == -1) {
-        return ErrnoError() << "waitpid() failed.";
-    }
-    if (!WIFEXITED(status)) {
-        return Error() << kFsVerityInitPath << ": abnormal process exit";
-    }
-    if (WEXITSTATUS(status)) {
-        if (status != 0) {
-            return Error() << kFsVerityInitPath << " exited with " << status;
-        }
-    }
-
-    return {};
-}
-
-Result<KeymasterSigningKey> loadAndVerifyExistingKey() {
-    if (access(kSigningKeyBlob.c_str(), F_OK) < 0) {
-        return ErrnoError() << "Key blob not found: " << kSigningKeyBlob;
-    }
-    return KeymasterSigningKey::loadFromBlobAndVerify(kSigningKeyBlob);
-}
-
-Result<void> verifyExistingCert(const KeymasterSigningKey& key) {
+Result<void> verifyExistingCert(const SigningKey& key) {
     if (access(kSigningKeyCert.c_str(), F_OK) < 0) {
         return ErrnoError() << "Key certificate not found: " << kSigningKeyCert;
     }
@@ -114,19 +78,18 @@
     return {};
 }
 
-Result<KeymasterSigningKey> createAndPersistKey(const std::string& path) {
-    auto key = KeymasterSigningKey::createNewKey();
+Result<void> createX509Cert(const SigningKey& key, const std::string& outPath) {
+    auto publicKey = key.getPublicKey();
 
-    if (!key.ok()) {
-        return key.error();
+    if (!publicKey.ok()) {
+        return publicKey.error();
     }
 
-    auto result = key->saveKeyblob(path);
-    if (!result.ok()) {
-        return result.error();
-    }
-
-    return key;
+    auto keymasterSignFunction = [&](const std::string& to_be_signed) {
+        return key.sign(to_be_signed);
+    };
+    createSelfSignedCertificate(*publicKey, keymasterSignFunction, outPath);
+    return {};
 }
 
 bool compileArtifacts(bool force) {
@@ -143,73 +106,251 @@
            0;
 }
 
+static std::string toHex(const std::vector<uint8_t>& digest) {
+    std::stringstream ss;
+    for (auto it = digest.begin(); it != digest.end(); ++it) {
+        ss << std::setfill('0') << std::setw(2) << std::hex << static_cast<unsigned>(*it);
+    }
+    return ss.str();
+}
+
+Result<std::map<std::string, std::string>> computeDigests(const std::string& path) {
+    std::error_code ec;
+    std::map<std::string, std::string> digests;
+
+    auto it = std::filesystem::recursive_directory_iterator(path, ec);
+    auto end = std::filesystem::recursive_directory_iterator();
+
+    while (!ec && it != end) {
+        if (it->is_regular_file()) {
+            auto digest = createDigest(it->path());
+            if (!digest.ok()) {
+                return Error() << "Failed to compute digest for " << it->path();
+            }
+            digests[it->path()] = toHex(*digest);
+        }
+        ++it;
+    }
+    if (ec) {
+        return Error() << "Failed to iterate " << path << ": " << ec;
+    }
+
+    return digests;
+}
+
+Result<void> verifyDigests(const std::map<std::string, std::string>& digests,
+                           const std::map<std::string, std::string>& trusted_digests) {
+    for (const auto& path_digest : digests) {
+        auto path = path_digest.first;
+        auto digest = path_digest.second;
+        if ((trusted_digests.count(path) == 0)) {
+            return Error() << "Couldn't find digest for " << path;
+        }
+        if (trusted_digests.at(path) != digest) {
+            return Error() << "Digest mismatch for " << path;
+        }
+    }
+
+    // All digests matched!
+    if (digests.size() > 0) {
+        LOG(INFO) << "All root hashes match.";
+    }
+    return {};
+}
+
+Result<void> verifyIntegrityFsVerity(const std::map<std::string, std::string>& trusted_digests) {
+    // Just verify that the files are in verity, and get their digests
+    auto result = verifyAllFilesInVerity(kArtArtifactsDir);
+    if (!result.ok()) {
+        return result.error();
+    }
+
+    return verifyDigests(*result, trusted_digests);
+}
+
+Result<void> verifyIntegrityNoFsVerity(const std::map<std::string, std::string>& trusted_digests) {
+    // On these devices, just compute the digests, and verify they match the ones we trust
+    auto result = computeDigests(kArtArtifactsDir);
+    if (!result.ok()) {
+        return result.error();
+    }
+
+    return verifyDigests(*result, trusted_digests);
+}
+
+Result<OdsignInfo> getOdsignInfo(const SigningKey& key) {
+    std::string persistedSignature;
+    OdsignInfo odsignInfo;
+
+    if (!android::base::ReadFileToString(kOdsignInfoSignature, &persistedSignature)) {
+        return ErrnoError() << "Failed to read " << kOdsignInfoSignature;
+    }
+
+    std::fstream odsign_info(kOdsignInfo, std::ios::in | std::ios::binary);
+    if (!odsign_info) {
+        return Error() << "Failed to open " << kOdsignInfo;
+    }
+    odsign_info.seekg(0);
+    // Verify the hash
+    std::string odsign_info_str((std::istreambuf_iterator<char>(odsign_info)),
+                                std::istreambuf_iterator<char>());
+
+    auto publicKey = key.getPublicKey();
+    auto signResult = verifySignature(odsign_info_str, persistedSignature, *publicKey);
+    if (!signResult.ok()) {
+        return Error() << kOdsignInfoSignature << " does not match.";
+    } else {
+        LOG(INFO) << kOdsignInfoSignature << " matches.";
+    }
+
+    odsign_info.seekg(0);
+    if (!odsignInfo.ParseFromIstream(&odsign_info)) {
+        return Error() << "Failed to parse " << kOdsignInfo;
+    }
+
+    LOG(INFO) << "Loaded " << kOdsignInfo;
+    return odsignInfo;
+}
+
+Result<void> persistDigests(const std::map<std::string, std::string>& digests,
+                            const SigningKey& key) {
+    OdsignInfo signInfo;
+    google::protobuf::Map<std::string, std::string> proto_hashes(digests.begin(), digests.end());
+    auto map = signInfo.mutable_file_hashes();
+    *map = proto_hashes;
+
+    std::fstream odsign_info(kOdsignInfo,
+                             std::ios::in | std::ios::out | std::ios::trunc | std::ios::binary);
+    if (!signInfo.SerializeToOstream(&odsign_info)) {
+        return Error() << "Failed to persist root hashes in " << kOdsignInfo;
+    }
+
+    // Sign the signatures with our key itself, and write that to storage
+    odsign_info.seekg(0, std::ios::beg);
+    std::string odsign_info_str((std::istreambuf_iterator<char>(odsign_info)),
+                                std::istreambuf_iterator<char>());
+    auto signResult = key.sign(odsign_info_str);
+    if (!signResult.ok()) {
+        return Error() << "Failed to sign " << kOdsignInfo;
+    }
+    android::base::WriteStringToFile(*signResult, kOdsignInfoSignature);
+    return {};
+}
+
 int main(int /* argc */, char** /* argv */) {
-    auto removeArtifacts = []() {
+    auto removeArtifacts = []() -> std::uintmax_t {
         std::error_code ec;
         auto num_removed = std::filesystem::remove_all(kArtArtifactsDir, ec);
         if (ec) {
             // TODO can't remove artifacts, signal Zygote shouldn't use them
             LOG(ERROR) << "Can't remove " << kArtArtifactsDir << ": " << ec.message();
+            return 0;
         } else {
-            LOG(INFO) << "Removed " << num_removed << " entries from " << kArtArtifactsDir;
+            if (num_removed > 0) {
+                LOG(INFO) << "Removed " << num_removed << " entries from " << kArtArtifactsDir;
+            }
+            return num_removed;
         }
     };
     // Make sure we delete the artifacts in all early (error) exit paths
     auto scope_guard = android::base::make_scope_guard(removeArtifacts);
 
-    auto key = loadAndVerifyExistingKey();
-    if (!key.ok()) {
-        LOG(WARNING) << key.error().message();
-
-        key = createAndPersistKey(kSigningKeyBlob);
-        if (!key.ok()) {
-            LOG(ERROR) << "Failed to create or persist new key: " << key.error().message();
+    SigningKey* key;
+    if (kUseKeystore) {
+        auto keystoreResult = KeystoreKey::getInstance();
+        if (!keystoreResult.ok()) {
+            LOG(ERROR) << "Could not create keystore key: " << keystoreResult.error().message();
             return -1;
         }
+        key = keystoreResult.value();
     } else {
-        LOG(INFO) << "Found and verified existing key: " << kSigningKeyBlob;
-    }
-
-    auto existing_cert = verifyExistingCert(key.value());
-    if (!existing_cert.ok()) {
-        LOG(WARNING) << existing_cert.error().message();
-
-        // Try to create a new cert
-        auto new_cert = key->createX509Cert(kSigningKeyCert);
-        if (!new_cert.ok()) {
-            LOG(ERROR) << "Failed to create X509 certificate: " << new_cert.error().message();
-            // TODO apparently the key become invalid - delete the blob / cert
+        // TODO - keymaster will go away
+        auto keymasterResult = KeymasterSigningKey::getInstance();
+        if (!keymasterResult.ok()) {
+            LOG(ERROR) << "Failed to create keymaster key: " << keymasterResult.error().message();
             return -1;
         }
+        key = keymasterResult.value();
+    }
+
+    bool supportsFsVerity = access(kFsVerityProcPath, F_OK) == 0;
+    if (!supportsFsVerity) {
+        LOG(INFO) << "Device doesn't support fsverity. Falling back to full verification.";
+    }
+
+    if (supportsFsVerity) {
+        auto existing_cert = verifyExistingCert(*key);
+        if (!existing_cert.ok()) {
+            LOG(WARNING) << existing_cert.error().message();
+
+            // Try to create a new cert
+            auto new_cert = createX509Cert(*key, kSigningKeyCert);
+            if (!new_cert.ok()) {
+                LOG(ERROR) << "Failed to create X509 certificate: " << new_cert.error().message();
+                // TODO apparently the key become invalid - delete the blob / cert
+                return -1;
+            }
+        } else {
+            LOG(INFO) << "Found and verified existing public key certificate: " << kSigningKeyCert;
+        }
+        auto cert_add_result = addCertToFsVerityKeyring(kSigningKeyCert);
+        if (!cert_add_result.ok()) {
+            LOG(ERROR) << "Failed to add certificate to fs-verity keyring: "
+                       << cert_add_result.error().message();
+            return -1;
+        }
+    }
+
+    auto signInfo = getOdsignInfo(*key);
+    if (!signInfo.ok()) {
+        int num_removed = removeArtifacts();
+        // Only a warning if there were artifacts to begin with, which suggests tampering or
+        // corruption
+        if (num_removed > 0) {
+            LOG(WARNING) << signInfo.error().message();
+        }
     } else {
-        LOG(INFO) << "Found and verified existing public key certificate: " << kSigningKeyCert;
-    }
-    auto cert_add_result = addCertToFsVerityKeyring(kSigningKeyCert);
-    if (!cert_add_result.ok()) {
-        LOG(ERROR) << "Failed to add certificate to fs-verity keyring: "
-                   << cert_add_result.error().message();
-        return -1;
+        std::map<std::string, std::string> trusted_digests(signInfo->file_hashes().begin(),
+                                                           signInfo->file_hashes().end());
+        Result<void> integrityStatus;
+
+        if (supportsFsVerity) {
+            integrityStatus = verifyIntegrityFsVerity(trusted_digests);
+        } else {
+            integrityStatus = verifyIntegrityNoFsVerity(trusted_digests);
+        }
+        if (!integrityStatus.ok()) {
+            LOG(WARNING) << integrityStatus.error().message() << ", removing " << kArtArtifactsDir;
+            removeArtifacts();
+        }
     }
 
-    auto verityStatus = verifyAllFilesInVerity(kArtArtifactsDir);
-    if (!verityStatus.ok()) {
-        LOG(WARNING) << verityStatus.error().message() << ", removing " << kArtArtifactsDir;
-        removeArtifacts();
-    }
-
+    // Ask ART whether it considers the artifacts valid
+    LOG(INFO) << "Asking odrefresh to verify artifacts (if present)...";
     bool artifactsValid = validateArtifacts();
+    LOG(INFO) << "odrefresh said they are " << (artifactsValid ? "VALID" : "INVALID");
 
     if (!artifactsValid || kForceCompilation) {
-        removeArtifacts();
-
         LOG(INFO) << "Starting compilation... ";
         bool ret = compileArtifacts(kForceCompilation);
         LOG(INFO) << "Compilation done, returned " << ret;
 
-        verityStatus = addFilesToVerityRecursive(kArtArtifactsDir, key.value());
+        Result<std::map<std::string, std::string>> digests;
+        if (supportsFsVerity) {
+            digests = addFilesToVerityRecursive(kArtArtifactsDir, *key);
+        } else {
+            // If we can't use verity, just compute the root hashes and store
+            // those, so we can reverify them at the next boot.
+            digests = computeDigests(kArtArtifactsDir);
+        }
+        if (!digests.ok()) {
+            LOG(ERROR) << digests.error().message();
+            return -1;
+        }
 
-        if (!verityStatus.ok()) {
-            LOG(ERROR) << "Failed to add " << verityStatus.error().message();
+        auto persistStatus = persistDigests(*digests, *key);
+        if (!persistStatus.ok()) {
+            LOG(ERROR) << persistStatus.error().message();
             return -1;
         }
     }
diff --git a/ondevice-signing/proto/Android.bp b/ondevice-signing/proto/Android.bp
new file mode 100644
index 0000000..fd48f31
--- /dev/null
+++ b/ondevice-signing/proto/Android.bp
@@ -0,0 +1,29 @@
+/*
+ * Copyright (C) 2021 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.
+ */
+
+package {
+    default_applicable_licenses: ["Android-Apache-2.0"],
+}
+
+cc_library_static {
+    name: "lib_odsign_proto",
+    host_supported: true,
+    proto: {
+        export_proto_headers: true,
+        type: "full",
+    },
+    srcs: ["odsign_info.proto"],
+}
diff --git a/ondevice-signing/proto/odsign_info.proto b/ondevice-signing/proto/odsign_info.proto
new file mode 100644
index 0000000..9d49c6c
--- /dev/null
+++ b/ondevice-signing/proto/odsign_info.proto
@@ -0,0 +1,24 @@
+/*
+ * Copyright (C) 2021 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 = "proto3";
+
+package odsign.proto;
+
+message OdsignInfo {
+  // Map of artifact files to their hashes
+  map<string, string> file_hashes = 1;
+}