Delta Update Patches: Source Identity, Not Just a Diff

An update that transmits a patch instead of a whole archive has to answer a question the whole-archive path never faces: which installed bytes is this patch for. A patch computed against one build will produce garbage against another, and the failure is silent — the output is a well-formed file with the right length and wrong contents — unless the patch is bound to a source identity that the installer can check.

A patch is a function of two specific files

Binary differencing algorithms produce a set of instructions that reconstruct the target from the source: copy a range from the source at some offset, and insert literal bytes. The classic formulation is BSDiff, which sorts suffixes of the source to find the longest matches for each region of the target, then compresses the difference stream with bzip2. VCDIFF, specified in RFC 3284, formalises the same idea as a portable format with a windowed instruction stream and separate sections for instructions, copy addresses, and literal data.

Both are functions of the pair. The copy instructions carry offsets into the source file, so any byte inserted or removed near the beginning of the source shifts every subsequent offset and invalidates every later copy. That sensitivity is not a defect of the algorithm; it is what makes the patch small. A patch that tolerated arbitrary source changes would have to describe the target without reference to the source, which is just the target.

In practice this means the storefront must know, per device, exactly which build is installed before it can choose a patch. The identity it uses cannot be a version code alone, because two builds can share a version code (through a mistake) and because the installed APK may have been re-signed or re-split by the store itself, changing its bytes without changing its version. The usable identity is a digest of the installed artifact, reported by the installer after it validates the package signature.

File-by-file patching versus whole-archive patching

Two strategies exist and they trade differently.

A whole-archive delta treats the APK as one byte string. It finds matches across the entire file, including across entry boundaries, so a resource that moved from one entry to another can still be copied from the old location. The resulting patch is the smallest available, but it must be applied to the complete old file in one pass, which means the device needs both files on disk simultaneously plus the patch.

A file-by-file delta decompresses each entry, diffs it against the corresponding entry in the old archive, and recompresses. It cannot match across entries, so a rename or a reordering of resources costs a full entry rather than a few bytes of copy instruction. In exchange it works on uncompressed content, which is far more stable: a ZIP entry’s compressed bytes change completely when one byte of the input changes, because the compressor’s dictionary state diverges, whereas the uncompressed content differs in one place.

That stability is the dominant factor. A native library rebuilt with a new compiler flag produces a compressed entry that shares almost nothing with its predecessor, but the uncompressed library may differ in a handful of functions. Diffing the uncompressed form finds those; diffing the compressed form finds nothing. The same holds for DEX files, where a small code change perturbs the whole compressed entry but leaves the rest of the bytecode structurally identical.

The cost of the uncompressed approach is that each entry must be inflated and re-deflated, which is CPU work on a device with a modest core budget, and the recomputation must produce a byte-identical recompression or the resulting APK will not match the store’s expected digest. That requirement means the patcher and the verifier must agree on the compressor’s exact output, which is why the compressed-entry path is used for entries whose compression is deterministic and the stored-entry path for those that are not.

# Entry-level delta: diff uncompressed content, not the deflate stream.
import zlib

def patch_entry(old_raw: bytes, new_raw: bytes) -> bytes:
    # A real implementation emits VCDIFF instructions; this shows the identity
    # check that makes the result trustworthy.
    out = apply_vcdiff(old_raw, build_vcdiff(old_raw, new_raw))
    if zlib.crc32(out) & 0xFFFFFFFF != zlib.crc32(new_raw) & 0xFFFFFFFF:
        raise ValueError("patched entry does not match target checksum")
    return out

The check at the end is not redundant with the package signature. A patch applied to the wrong source produces output that fails the entry checksum, which localises the failure to one entry instead of leaving a whole archive that fails signature verification with no indication of where.

What splitting does to the savings

Splitting an app bundle into per-device APKs reduces the size of the target, and the savings of a delta do not scale with it. A universal APK of 100 MB with a 20 MB change yields a patch around 20 MB; the split APKs for a given device might total 40 MB, and a change of the same logical size still yields a patch close to 20 MB, because the patch is dominated by the changed content, not by the unchanged remainder.

The ratio worsens for small updates on small bases. A patch carries fixed overhead — the instruction stream’s structure, the literal section’s compression framing, and the per-entry table — of a few kilobytes, which is irrelevant against 20 MB and significant against a 300 KB split. Below some threshold the storefront simply serves the whole APK, because the patch plus its bookkeeping is not smaller. The threshold is a policy choice, not a constant of the format.

There is also a case where splitting makes deltas more effective: a change confined to one split. Updating a language split that changed does not require transmitting a patch for the other splits, because they are unchanged and the installer can leave them in place. That is the case the split model was designed for, and it is the reason an update to a split app can be far smaller than the same change in a universal APK — not because the delta is better, but because the unit of replacement is smaller.

Applying a patch safely

The installer’s sequence is: identify the installed source, download the patch, verify the patch’s own signature, apply, verify the result’s signature, then install. Each step has a failure mode.

Applying a patch requires the source bytes to be readable while the target is being written, so peak storage is roughly source plus target plus patch. On a device near capacity this is the step that fails, and the failure is a storage error rather than an integrity error — the update does not apply, and the app remains at its old version, which is the correct outcome. Reporting it as a generic update failure is a common mistake, because the user’s remedy is to free space, not to retry.

Verifying the result’s signature is the step that makes the whole path trustworthy. A patch is attacker-controlled input that produces executable code, so the only defensible position is that the output must satisfy the same whole-file verification as a downloaded APK — the signature block described in APK signing block layout covers every byte, so a patch that produced a subtly different archive fails at the same check a tampered download would fail. Applying a patch and skipping verification would mean the patch itself is the trust anchor, which it is not.

The source identity check is weaker than it looks. The installer can verify that the installed package’s signature is valid and that its digest matches the one it reported, but it cannot prove that the source is the build the patch was computed against unless the patch declares that digest and the installer compares. Where the storefront selects the patch, that binding is implicit in the store’s own record of what it delivered; where patches are fetched from a third-party CDN, it must be explicit, because the CDN has no such record.

The case against deltas

A delta update is only cheaper when the changed fraction is small and the source is exactly known. Both conditions fail often enough that the whole mechanism is optional on both major platforms: Android’s store serves deltas where it can identify the installed build and falls back to the full APK otherwise, and iOS’s store does the same with its own patch format. The engineering cost — a patch generator per source-target pair, a source-identity registry, a storage headroom requirement, and a verification path that must not be skipped — is real, and it buys a reduction that disappears the moment the app’s assets are regenerated wholesale.

The case where it pays reliably is an app with a large, stable body and a small, frequently changed surface: a game with fixed assets and a changing code layer, or a reference app with a large bundled dataset and a small UI. In those, the delta is a small fraction of the full download for every release. For an app whose releases touch every resource, the patch approaches the size of the target and the mechanism contributes overhead without benefit.