diff --git a/compos/apex/Android.bp b/compos/apex/Android.bp
index f40da9c..564a380 100644
--- a/compos/apex/Android.bp
+++ b/compos/apex/Android.bp
@@ -59,7 +59,6 @@
     ],
 
     prebuilts: [
-        "CompOSPayloadApp.apk.idsig",
         "com.android.compos.init.rc",
     ],
 }
diff --git a/compos/apk/Android.bp b/compos/apk/Android.bp
index 3a68b8e..c6192b9 100644
--- a/compos/apk/Android.bp
+++ b/compos/apk/Android.bp
@@ -3,42 +3,7 @@
 }
 
 android_app {
-    name: "CompOSPayloadApp.unsigned",
+    name: "CompOSPayloadApp",
     sdk_version: "current",
     apex_available: ["com.android.compos"],
 }
-
-// TODO(b/190409306) this is temporary until we have a solid way to pass merkle tree
-java_genrule {
-    name: "CompOSPayloadApp.signing",
-    out: [
-        "CompOSPayloadApp.apk",
-        "CompOSPayloadApp.apk.idsig",
-    ],
-    srcs: [":CompOSPayloadApp.unsigned"],
-    tools: ["apksigner"],
-    tool_files: ["test.keystore"],
-    cmd: "$(location apksigner) sign " +
-        "--ks $(location test.keystore) " +
-        "--ks-pass=pass:testkey --key-pass=pass:testkey " +
-        "--in $(in) " +
-        "--out $(genDir)/CompOSPayloadApp.apk",
-    // $(genDir)/CompOSPayloadApp.apk.idsig is generated implicitly
-}
-
-android_app_import {
-    name: "CompOSPayloadApp",
-    // Make sure the build system doesn't try to resign the APK
-    dex_preopt: {
-        enabled: false,
-    },
-    apk: ":CompOSPayloadApp.signing{CompOSPayloadApp.apk}",
-    presigned: true,
-    filename: "CompOSPayloadApp.apk",
-    apex_available: ["com.android.compos"],
-}
-
-prebuilt_etc {
-    name: "CompOSPayloadApp.apk.idsig",
-    src: ":CompOSPayloadApp.signing{CompOSPayloadApp.apk.idsig}",
-}
diff --git a/compos/apk/test.keystore b/compos/apk/test.keystore
deleted file mode 100644
index 2946641..0000000
--- a/compos/apk/test.keystore
+++ /dev/null
Binary files differ
diff --git a/compos/common/compos_client.rs b/compos/common/compos_client.rs
index 9c23fac..3bb066f 100644
--- a/compos/common/compos_client.rs
+++ b/compos/common/compos_client.rs
@@ -72,6 +72,7 @@
     pub fn start(
         service: &dyn IVirtualizationService,
         instance_image: File,
+        idsig: &Path,
         parameters: &VmParameters,
     ) -> Result<VmInstance> {
         let instance_fd = ParcelFileDescriptor::new(instance_image);
@@ -83,9 +84,18 @@
             .context("Failed to open config APK file")?;
         let apk_fd = ParcelFileDescriptor::new(apk_fd);
 
-        let idsig_fd = File::open(apex_dir.join("etc/CompOSPayloadApp.apk.idsig"))
-            .context("Failed to open config APK idsig file")?;
-        let idsig_fd = ParcelFileDescriptor::new(idsig_fd);
+        if !idsig.exists() {
+            // Prepare idsig file via VirtualizationService
+            let idsig_file = File::create(idsig).context("Failed to create idsig file")?;
+            let idsig_fd = ParcelFileDescriptor::new(idsig_file);
+            service
+                .createOrUpdateIdsigFile(&apk_fd, &idsig_fd)
+                .context("Failed to update idsig file")?;
+        }
+
+        // Open idsig as read-only
+        let idsig_file = File::open(idsig).context("Failed to open idsig file")?;
+        let idsig_fd = ParcelFileDescriptor::new(idsig_file);
 
         let (console_fd, log_fd, debug_level) = if parameters.debug_mode {
             // Console output and the system log output from the VM are redirected to file.
diff --git a/compos/common/lib.rs b/compos/common/lib.rs
index 6e397a2..9a4d0e3 100644
--- a/compos/common/lib.rs
+++ b/compos/common/lib.rs
@@ -55,6 +55,9 @@
 /// The file that holds the instance image for a CompOS instance.
 pub const INSTANCE_IMAGE_FILE: &str = "instance.img";
 
+/// The file that holds the idsig for the CompOS Payload APK.
+pub const IDSIG_FILE: &str = "idsig";
+
 /// The path within our config APK of our default VM configuration file, used at boot time.
 pub const DEFAULT_VM_CONFIG_PATH: &str = "assets/vm_config.json";
 
diff --git a/compos/compos_key_cmd/compos_key_cmd.cpp b/compos/compos_key_cmd/compos_key_cmd.cpp
index f8b3d16..0b6750b 100644
--- a/compos/compos_key_cmd/compos_key_cmd.cpp
+++ b/compos/compos_key_cmd/compos_key_cmd.cpp
@@ -58,6 +58,7 @@
 using aidl::android::system::virtualizationservice::VirtualMachineConfig;
 using aidl::com::android::compos::CompOsKeyData;
 using aidl::com::android::compos::ICompOsService;
+using android::base::Dirname;
 using android::base::ErrnoError;
 using android::base::Error;
 using android::base::Fdopen;
@@ -73,8 +74,6 @@
 
 constexpr const char* kConfigApkPath =
         "/apex/com.android.compos/app/CompOSPayloadApp/CompOSPayloadApp.apk";
-constexpr const char* kConfigApkIdsigPath =
-        "/apex/com.android.compos/etc/CompOSPayloadApp.apk.idsig";
 
 // These are paths inside the APK
 constexpr const char* kDefaultConfigFilePath = "assets/vm_config.json";
@@ -211,6 +210,8 @@
             return Error() << "Can't specify both cid and image file.";
         }
 
+        // Start a new VM with a given instance.img
+
         // We need a thread pool to receive VM callbacks.
         ABinderProcess_startThreadPool();
 
@@ -242,10 +243,25 @@
             return ErrnoError() << "Failed to open config APK";
         }
 
+        // Prepare an idsig file
+        std::string idsigPath = Dirname(mInstanceImageFile) + "/idsig";
+        {
+            ScopedFileDescriptor idsigFd(TEMP_FAILURE_RETRY(
+                    open(idsigPath.c_str(), O_RDWR | O_CREAT | O_TRUNC | O_CLOEXEC,
+                         S_IRUSR | S_IWUSR | S_IRGRP)));
+            if (idsigFd.get() == -1) {
+                return ErrnoError() << "Failed to create an idsig file";
+            }
+            auto status = service->createOrUpdateIdsigFile(apkFd, idsigFd);
+            if (!status.isOk()) {
+                return Error() << status.getDescription();
+            }
+        }
+
         ScopedFileDescriptor idsigFd(
-                TEMP_FAILURE_RETRY(open(kConfigApkIdsigPath, O_RDONLY | O_CLOEXEC)));
+                TEMP_FAILURE_RETRY(open(idsigPath.c_str(), O_RDONLY | O_CLOEXEC)));
         if (idsigFd.get() == -1) {
-            return ErrnoError() << "Failed to open config APK signature";
+            return ErrnoError() << "Failed to open an idsig file";
         }
 
         ScopedFileDescriptor instanceFd(
diff --git a/compos/composd/src/instance_starter.rs b/compos/composd/src/instance_starter.rs
index 8189fe0..91a0e61 100644
--- a/compos/composd/src/instance_starter.rs
+++ b/compos/composd/src/instance_starter.rs
@@ -26,7 +26,7 @@
 use compos_aidl_interface::binder::{ParcelFileDescriptor, Strong};
 use compos_common::compos_client::{VmInstance, VmParameters};
 use compos_common::{
-    COMPOS_DATA_ROOT, INSTANCE_IMAGE_FILE, PRIVATE_KEY_BLOB_FILE, PUBLIC_KEY_FILE,
+    COMPOS_DATA_ROOT, IDSIG_FILE, INSTANCE_IMAGE_FILE, PRIVATE_KEY_BLOB_FILE, PUBLIC_KEY_FILE,
 };
 use log::{info, warn};
 use std::env;
@@ -51,6 +51,7 @@
     instance_name: String,
     instance_root: PathBuf,
     instance_image: PathBuf,
+    idsig: PathBuf,
     key_blob: PathBuf,
     public_key: PathBuf,
     vm_parameters: VmParameters,
@@ -59,14 +60,16 @@
 impl InstanceStarter {
     pub fn new(instance_name: &str, vm_parameters: VmParameters) -> Self {
         let instance_root = Path::new(COMPOS_DATA_ROOT).join(instance_name);
-        let instant_root_path = instance_root.as_path();
-        let instance_image = instant_root_path.join(INSTANCE_IMAGE_FILE);
-        let key_blob = instant_root_path.join(PRIVATE_KEY_BLOB_FILE);
-        let public_key = instant_root_path.join(PUBLIC_KEY_FILE);
+        let instance_root_path = instance_root.as_path();
+        let instance_image = instance_root_path.join(INSTANCE_IMAGE_FILE);
+        let idsig = instance_root_path.join(IDSIG_FILE);
+        let key_blob = instance_root_path.join(PRIVATE_KEY_BLOB_FILE);
+        let public_key = instance_root_path.join(PUBLIC_KEY_FILE);
         Self {
             instance_name: instance_name.to_owned(),
             instance_root,
             instance_image,
+            idsig,
             key_blob,
             public_key,
             vm_parameters,
@@ -124,6 +127,8 @@
         let _ = fs::create_dir(&self.instance_root);
 
         self.create_instance_image(virtualization_service)?;
+        // Delete existing idsig file. Ignore error in case idsig doesn't exist.
+        let _ = fs::remove_file(&self.idsig);
 
         let compos_instance = self.start_vm(virtualization_service)?;
         let service = &compos_instance.service;
@@ -170,9 +175,13 @@
             .write(true)
             .open(&self.instance_image)
             .context("Failed to open instance image")?;
-        let vm_instance =
-            VmInstance::start(virtualization_service, instance_image, &self.vm_parameters)
-                .context("Starting VM")?;
+        let vm_instance = VmInstance::start(
+            virtualization_service,
+            instance_image,
+            &self.idsig,
+            &self.vm_parameters,
+        )
+        .context("Starting VM")?;
         let service = vm_instance.get_service().context("Connecting to CompOS")?;
         Ok(CompOsInstance { vm_instance, service, lazy_service_guard: Default::default() })
     }
diff --git a/compos/tests/Android.bp b/compos/tests/Android.bp
index 7e00d7b..d380059 100644
--- a/compos/tests/Android.bp
+++ b/compos/tests/Android.bp
@@ -14,7 +14,4 @@
         "VirtualizationTestHelper",
     ],
     test_suites: ["general-tests"],
-    data: [
-        ":CompOSPayloadApp.signing",
-    ],
 }
diff --git a/compos/tests/java/android/compos/test/ComposKeyTestCase.java b/compos/tests/java/android/compos/test/ComposKeyTestCase.java
index eacf3fb..14d02e1 100644
--- a/compos/tests/java/android/compos/test/ComposKeyTestCase.java
+++ b/compos/tests/java/android/compos/test/ComposKeyTestCase.java
@@ -151,13 +151,12 @@
     }
 
     private void startVm() throws Exception {
-        final String apkName = "CompOSPayloadApp.apk";
         final String packageName = "com.android.compos.payload";
         mCid =
                 startMicrodroid(
                         getDevice(),
                         getBuild(),
-                        apkName,
+                        /* apkName, no need to install */ null,
                         packageName,
                         "assets/vm_test_config.json",
                         /* debug */ true,
diff --git a/compos/verify_key/verify_key.rs b/compos/verify_key/verify_key.rs
index e0ed5e5..a028264 100644
--- a/compos/verify_key/verify_key.rs
+++ b/compos/verify_key/verify_key.rs
@@ -21,7 +21,7 @@
 use compos_aidl_interface::binder::ProcessState;
 use compos_common::compos_client::{VmInstance, VmParameters};
 use compos_common::{
-    COMPOS_DATA_ROOT, CURRENT_INSTANCE_DIR, INSTANCE_IMAGE_FILE, PENDING_INSTANCE_DIR,
+    COMPOS_DATA_ROOT, CURRENT_INSTANCE_DIR, IDSIG_FILE, INSTANCE_IMAGE_FILE, PENDING_INSTANCE_DIR,
     PRIVATE_KEY_BLOB_FILE, PUBLIC_KEY_FILE, TEST_INSTANCE_DIR,
 };
 use std::fs::{self, File};
@@ -99,6 +99,7 @@
     let blob = instance_dir.join(PRIVATE_KEY_BLOB_FILE);
     let public_key = instance_dir.join(PUBLIC_KEY_FILE);
     let instance_image = instance_dir.join(INSTANCE_IMAGE_FILE);
+    let idsig = instance_dir.join(IDSIG_FILE);
 
     let blob = read_small_file(blob).context("Failed to read key blob")?;
     let public_key = read_small_file(public_key).context("Failed to read public key")?;
@@ -108,6 +109,7 @@
     let vm_instance = VmInstance::start(
         &*virtualization_service,
         instance_image,
+        &idsig,
         &VmParameters { debug_mode, ..Default::default() },
     )?;
     let service = vm_instance.get_service()?;
diff --git a/tests/hostside/helper/java/android/virt/test/VirtualizationTestCaseBase.java b/tests/hostside/helper/java/android/virt/test/VirtualizationTestCaseBase.java
index 8d9a7e3..c71d6ac 100644
--- a/tests/hostside/helper/java/android/virt/test/VirtualizationTestCaseBase.java
+++ b/tests/hostside/helper/java/android/virt/test/VirtualizationTestCaseBase.java
@@ -186,9 +186,11 @@
             throws DeviceNotAvailableException {
         CommandRunner android = new CommandRunner(androidDevice);
 
-        // Install APK
-        File apkFile = findTestFile(buildInfo, apkName);
-        androidDevice.installPackage(apkFile, /* reinstall */ true);
+        // Install APK if necessary
+        if (apkName != null) {
+            File apkFile = findTestFile(buildInfo, apkName);
+            androidDevice.installPackage(apkFile, /* reinstall */ true);
+        }
 
         // Get the path to the installed apk. Note that
         // getDevice().getAppPackageInfo(...).getCodePath() doesn't work due to the incorrect