diff --git a/apkdmverity/Android.bp b/apkdmverity/Android.bp
index df46324..e6b1ca9 100644
--- a/apkdmverity/Android.bp
+++ b/apkdmverity/Android.bp
@@ -17,6 +17,7 @@
         "liblibc",
         "libnix",
         "libnum_traits",
+        "librustutils",
         "libscopeguard",
         "libuuid",
     ],
@@ -31,6 +32,8 @@
 rust_binary {
     name: "apkdmverity",
     defaults: ["apkdmverity.defaults"],
+    init_rc: ["apkdmverity.rc"],
+    bootstrap: true,
 }
 
 rust_test {
diff --git a/apkdmverity/apkdmverity.rc b/apkdmverity/apkdmverity.rc
new file mode 100644
index 0000000..c6ef52b
--- /dev/null
+++ b/apkdmverity/apkdmverity.rc
@@ -0,0 +1,3 @@
+service apkdmverity /system/bin/apkdmverity /dev/block/by-name/microdroid-apk /dev/block/by-name/microdroid-apk-idsig microdroid-apk
+    disabled
+    oneshot
diff --git a/apkdmverity/src/main.rs b/apkdmverity/src/main.rs
index 9d1ef1c..2cc0758 100644
--- a/apkdmverity/src/main.rs
+++ b/apkdmverity/src/main.rs
@@ -28,6 +28,7 @@
 use anyhow::{bail, Context, Result};
 use clap::{App, Arg};
 use idsig::{HashAlgorithm, V4Signature};
+use rustutils::system_properties;
 use std::fmt::Debug;
 use std::fs;
 use std::fs::File;
@@ -61,7 +62,13 @@
     let apk = matches.value_of("apk").unwrap();
     let idsig = matches.value_of("idsig").unwrap();
     let name = matches.value_of("name").unwrap();
-    let ret = enable_verity(apk, idsig, name)?;
+    let roothash = if let Ok(val) = system_properties::read("microdroid_manager.apk_roothash") {
+        Some(util::parse_hexstring(&val)?)
+    } else {
+        // This failure is not an error. We will use the roothash read from the idsig file.
+        None
+    };
+    let ret = enable_verity(apk, idsig, name, roothash.as_deref())?;
     if matches.is_present("verbose") {
         println!(
             "data_device: {:?}, hash_device: {:?}, mapper_device: {:?}",
@@ -80,7 +87,12 @@
 const BLOCK_SIZE: u64 = 4096;
 
 // Makes a dm-verity block device out of `apk` and its accompanying `idsig` files.
-fn enable_verity<P: AsRef<Path> + Debug>(apk: P, idsig: P, name: &str) -> Result<VerityResult> {
+fn enable_verity<P: AsRef<Path> + Debug>(
+    apk: P,
+    idsig: P,
+    name: &str,
+    roothash: Option<&[u8]>,
+) -> Result<VerityResult> {
     // Attach the apk file to a loop device if the apk file is a regular file. If not (i.e. block
     // device), we only need to get the size and use the block device as it is.
     let (data_device, apk_size) = if fs::metadata(&apk)?.file_type().is_block_device() {
@@ -108,7 +120,11 @@
     let target = dm::DmVerityTargetBuilder::default()
         .data_device(&data_device, apk_size)
         .hash_device(&hash_device)
-        .root_digest(&sig.hashing_info.raw_root_hash)
+        .root_digest(if let Some(roothash) = roothash {
+            roothash
+        } else {
+            &sig.hashing_info.raw_root_hash
+        })
         .hash_algorithm(match sig.hashing_info.hash_algorithm {
             HashAlgorithm::SHA256 => dm::DmVerityHashAlgorithm::SHA256,
         })
@@ -167,6 +183,16 @@
     }
 
     fn run_test(apk: &[u8], idsig: &[u8], name: &str, check: fn(TestContext)) {
+        run_test_with_hash(apk, idsig, name, None, check);
+    }
+
+    fn run_test_with_hash(
+        apk: &[u8],
+        idsig: &[u8],
+        name: &str,
+        roothash: Option<&[u8]>,
+        check: fn(TestContext),
+    ) {
         if should_skip() {
             return;
         }
@@ -174,7 +200,7 @@
         let (apk_path, idsig_path) = prepare_inputs(test_dir.path(), apk, idsig);
 
         // Run the program and register clean-ups.
-        let ret = enable_verity(&apk_path, &idsig_path, name).unwrap();
+        let ret = enable_verity(&apk_path, &idsig_path, name, roothash).unwrap();
         let ret = scopeguard::guard(ret, |ret| {
             loopdevice::detach(ret.data_device).unwrap();
             loopdevice::detach(ret.hash_device).unwrap();
@@ -312,7 +338,8 @@
 
         let name = "loop_as_input";
         // Run the program WITH the loop devices, not the regular files.
-        let ret = enable_verity(apk_loop_device.deref(), idsig_loop_device.deref(), name).unwrap();
+        let ret =
+            enable_verity(apk_loop_device.deref(), idsig_loop_device.deref(), name, None).unwrap();
         let ret = scopeguard::guard(ret, |ret| {
             loopdevice::detach(ret.data_device).unwrap();
             loopdevice::detach(ret.hash_device).unwrap();
@@ -325,4 +352,18 @@
         assert_eq!(verity.len(), original.len()); // fail fast
         assert_eq!(verity.as_slice(), original.as_slice());
     }
+
+    // test with custom roothash
+    #[test]
+    fn correct_custom_roothash() {
+        let apk = include_bytes!("../testdata/test.apk");
+        let idsig = include_bytes!("../testdata/test.apk.idsig");
+        let roothash = V4Signature::from(Cursor::new(&idsig)).unwrap().hashing_info.raw_root_hash;
+        run_test_with_hash(apk.as_ref(), idsig.as_ref(), "correct", Some(&roothash), |ctx| {
+            let verity = fs::read(&ctx.result.mapper_device).unwrap();
+            let original = fs::read(&ctx.result.data_device).unwrap();
+            assert_eq!(verity.len(), original.len()); // fail fast
+            assert_eq!(verity.as_slice(), original.as_slice());
+        });
+    }
 }
diff --git a/apkdmverity/src/util.rs b/apkdmverity/src/util.rs
index d2bc799..913f827 100644
--- a/apkdmverity/src/util.rs
+++ b/apkdmverity/src/util.rs
@@ -14,7 +14,7 @@
  * limitations under the License.
  */
 
-use anyhow::{bail, Result};
+use anyhow::{anyhow, bail, Result};
 use nix::sys::stat::FileStat;
 use std::fs::File;
 use std::os::unix::fs::FileTypeExt;
@@ -42,6 +42,19 @@
     s.iter().map(|byte| format!("{:02x}", byte)).reduce(|i, j| i + &j).unwrap_or_default()
 }
 
+/// Parses a hexadecimal string into a byte array
+pub fn parse_hexstring(s: &str) -> Result<Vec<u8>> {
+    let len = s.len();
+    if len % 2 != 0 {
+        bail!("length {} is not even", len)
+    } else {
+        (0..len)
+            .step_by(2)
+            .map(|i| u8::from_str_radix(&s[i..i + 2], 16).map_err(|e| anyhow!(e)))
+            .collect()
+    }
+}
+
 /// fstat that accepts a path rather than FD
 pub fn fstat(p: &Path) -> Result<FileStat> {
     let f = File::open(p)?;
diff --git a/microdroid/init.rc b/microdroid/init.rc
index f9cd915..f6a7ecc 100644
--- a/microdroid/init.rc
+++ b/microdroid/init.rc
@@ -17,6 +17,7 @@
 
     start ueventd
 
+    mkdir /mnt/apk 0755 system system
     start microdroid_manager
     # TODO(b/190343842) verify apexes/apk before mounting them.
 
@@ -26,9 +27,10 @@
 
     perform_apex_config
 
-    exec - root system -- /system/bin/apkdmverity /dev/block/by-name/microdroid-apk /dev/block/by-name/microdroid-apk-idsig microdroid-apk
-    mkdir /mnt/apk 0755 system system
-    start zipfuse
+    # Notify to microdroid_manager that perform_apex_config is done.
+    # Microdroid_manager shouldn't execute payload before this, because app
+    # payloads are not designed to run with bootstrap bionic
+    setprop apex_config.done true
 
 on init
     # Mount binderfs
diff --git a/microdroid_manager/src/main.rs b/microdroid_manager/src/main.rs
index 62af791..9cbcaf1 100644
--- a/microdroid_manager/src/main.rs
+++ b/microdroid_manager/src/main.rs
@@ -24,16 +24,17 @@
 use binder::unstable_api::{new_spibinder, AIBinder};
 use binder::{FromIBinder, Strong};
 use idsig::V4Signature;
-use log::{debug, error, info, warn};
+use log::{error, info, warn};
 use microdroid_payload_config::{Task, TaskType, VmPayloadConfig};
 use nix::ioctl_read_bad;
+use rustutils::system_properties;
 use rustutils::system_properties::PropertyWatcher;
 use std::fs::{self, File, OpenOptions};
 use std::os::unix::io::{AsRawFd, FromRawFd, IntoRawFd};
 use std::path::Path;
 use std::process::{Command, Stdio};
 use std::str;
-use std::time::Duration;
+use std::time::{Duration, SystemTime};
 use vsock::VsockStream;
 
 use android_system_virtualmachineservice::aidl::android::system::virtualmachineservice::IVirtualMachineService::{
@@ -46,6 +47,8 @@
 /// The CID representing the host VM
 const VMADDR_CID_HOST: u32 = 2;
 
+const APEX_CONFIG_DONE_PROP: &str = "apex_config.done";
+
 fn get_vms_rpc_binder() -> Result<Strong<dyn IVirtualMachineService>> {
     // SAFETY: AIBinder returned by RpcClient has correct reference count, and the ownership can be
     // safely taken by new_spibinder.
@@ -89,26 +92,36 @@
 
     let metadata = metadata::load()?;
 
-    if let Err(err) = verify_payloads() {
-        error!("failed to verify payload: {:#?}", err);
-        return Err(err);
+    // Try to read roothash from the instance disk.
+    // TODO(jiyong): the data should have an internal structure.
+    let mut instance = InstanceDisk::new()?;
+    let saved_roothash = instance.read_microdroid_data().context("Failed to read identity data")?;
+    let saved_roothash = saved_roothash.as_deref();
+
+    // Verify the payload before using it.
+    let verified_roothash =
+        verify_payload(saved_roothash).context("Payload verification failed")?;
+    if let Some(saved_roothash) = saved_roothash {
+        if saved_roothash == verified_roothash.as_ref() {
+            info!("Saved roothash is verified.");
+        } else {
+            bail!("Detected an update of the APK which isn't supported yet.");
+        }
+    } else {
+        info!("Saving APK roothash: {}", to_hex_string(verified_roothash.as_ref()));
+        // TODO(jiyong): the data should have an internal structure.
+        instance
+            .write_microdroid_data(verified_roothash.as_ref())
+            .context("Failed to write identity data")?;
     }
 
-    let mut instance = InstanceDisk::new()?;
-    // TODO(jiyong): the data should have an internal structure
-    if let Some(data) = instance.read_microdroid_data().context("Failed to read identity data")? {
-        debug!("read apk root hash: {}", to_hex_string(&data));
-        //TODO(jiyong) apkdmverity should use this root hash instead of the one read from the idsig
-        //file, if the root hash is found in the instance image.
-    } else {
-        let data = get_apk_roothash()?;
-        debug!("write apk root hash: {}", to_hex_string(&data));
-        instance.write_microdroid_data(data.as_ref()).context("Failed to write identity data")?;
-    }
+    wait_for_apex_config_done()?;
 
     let service = get_vms_rpc_binder().expect("cannot connect to VirtualMachineService");
-
     if !metadata.payload_config_path.is_empty() {
+        // Before reading a file from the APK, start zipfuse
+        system_properties::write("ctl.start", "zipfuse")?;
+
         let config = load_config(Path::new(&metadata.payload_config_path))?;
 
         let fake_secret = "This is a placeholder for a value that is derived from the images that are loaded in the VM.";
@@ -128,20 +141,58 @@
     Ok(())
 }
 
-// TODO(jooyung): v2/v3 full verification can be slow. Consider multithreading.
-fn verify_payloads() -> Result<()> {
-    // We don't verify APEXes since apexd does.
+type Roothash = [u8];
 
-    // should wait APK to be dm-verity mounted by apkdmverity
+// Verify payload before executing it. Full verification (which is slow) is done when the roothash
+// values from the idsig file and the instance disk are different. This function returns the
+// verified roothash that can be saved to the instance disk.
+fn verify_payload(roothash: Option<&Roothash>) -> Result<Box<Roothash>> {
+    let start_time = SystemTime::now();
+
+    let roothash_from_idsig = get_apk_roothash_from_idsig()?;
+    let roothash_trustful = roothash == Some(&roothash_from_idsig);
+
+    // If roothash can be trusted, pass it to apkdmverity so that it uses the passed roothash
+    // instead of the value read from the idsig file.
+    if roothash_trustful {
+        let roothash = to_hex_string(roothash.unwrap());
+        system_properties::write("microdroid_manager.apk_roothash", &roothash)?;
+    }
+
+    // Start apkdmverity and wait for the dm-verify block
+    system_properties::write("ctl.start", "apkdmverity")?;
     ioutil::wait_for_file(DM_MOUNTED_APK_PATH, WAIT_TIMEOUT)?;
-    verify(DM_MOUNTED_APK_PATH).context(format!("failed to verify {}", DM_MOUNTED_APK_PATH))?;
 
-    info!("payload verification succeeded.");
-    // TODO(jooyung): collect public keys and store them in instance.img
+    // Do the full verification if the roothash is un-trustful. This requires the full scanning of
+    // the APK file and therefore can be very slow if the APK is large. Note that this step is
+    // taken only when the roothash is un-trustful which can be either when this is the first boot
+    // of the VM or APK was updated in the host.
+    // TODO(jooyung): consider multithreading to make this faster
+    if !roothash_trustful {
+        verify(DM_MOUNTED_APK_PATH).context(format!("failed to verify {}", DM_MOUNTED_APK_PATH))?;
+    }
+
+    info!("payload verification successful. took {:#?}", start_time.elapsed().unwrap());
+
+    // At this point, we can ensure that the roothash from the idsig file is trusted, either by
+    // fully verifying the APK or by comparing it with the saved roothash.
+    Ok(roothash_from_idsig)
+}
+
+// Waits until linker config is generated
+fn wait_for_apex_config_done() -> Result<()> {
+    let mut prop = PropertyWatcher::new(APEX_CONFIG_DONE_PROP)?;
+    loop {
+        prop.wait()?;
+        let val = system_properties::read(APEX_CONFIG_DONE_PROP)?;
+        if val == "true" {
+            break;
+        }
+    }
     Ok(())
 }
 
-fn get_apk_roothash() -> Result<Box<[u8]>> {
+fn get_apk_roothash_from_idsig() -> Result<Box<Roothash>> {
     let mut idsig = File::open("/dev/block/by-name/microdroid-apk-idsig")?;
     let idsig = V4Signature::from(&mut idsig)?;
     Ok(idsig.hashing_info.raw_root_hash)