How Incremental Installation and Android V4 Signature Speed Up App Deployment

Incremental Installation Overview

Frequent updates have made large mobile applications common, causing long download times for full APK packages. Traditional installation requires the entire package before the app can start, leading to poor user experience.

Incremental installation is a streaming approach where the core files of an APK are transferred first; once these are received, the app can launch while the remaining data continues to stream in the background.

Android 11 Incremental File System Support

Android 11 introduces an incremental file system (incfs) in the kernel to support incremental installation. This allows ADB to stream APK data and adds a new V4 signature scheme.

V4 Signature Based on Merkle Trees

The V4 signature creates a Merkle hash tree over all bytes of the APK. The root hash and a salt are stored as signature data for integrity verification. The signature is saved in an .idsig file and must be generated before incremental installation.

Merkle Tree Fundamentals

A Merkle tree combines multiple Lamport public keys into a single hash (the root hash). Leaf nodes are hashes of individual data block public keys; non‑leaf nodes are hashes of their children. Verification involves checking a data block’s one‑time signature and the path up to the root hash.

Code Structures for V4 Signature

struct V4Signature {
    int32 version; // only version 2 is supported as of now
    sized_bytes<int32> hashing_info;
    sized_bytes<int32> signing_info;
    sized_bytes<int32> merkle_tree; // optional full Merkle tree
};

template <class SizeT>
struct sized_bytes {
    SizeT size;
    byte bytes[size];
};

public static class HashingInfo {
    public final int hashAlgorithm;
    public final byte log2BlockSize;
    public final byte[] salt;
    public final byte[] rawRootHash;
    // ...
};

public static class SigningInfo {
    public final byte[] apkDigest;
    public final byte[] certificate;
    public final byte[] additionalData;
    public final byte[] publicKey;
    public final int signatureAlgorithmId;
    public final byte[] signature;
};

Generating the V4 Signature

The APK is divided into 4 KB blocks, each padded if necessary. SHA‑256 hashes of these blocks form the first layer of the Merkle tree. Subsequent layers are built by grouping hashes into 4 KB blocks, hashing again, and repeating until the root hash is obtained. The resulting hash tree and signing information are stored in the .idsig file.

When ADB requests an incremental install, the Package Manager reads the V4 signature from the .idsig file, extracts the signature data and public key, and verifies them similarly to previous signature schemes.

Summary

Incremental installation enables apps to start quickly by streaming core APK data, while Android’s V4 signature provides a Merkle‑tree‑based integrity check that secures the incremental delivery process.