Simple in theory, but .deb format makes it a little complicated.

I did a bit of work on this back in the day.

In principle this is really simple. Grab the .gz files out of the .deb using ar, zsync [1] them with the .gz files stored on some server (using either a cached .deb file or just $(cat `dpkg -L myoldpackage`). Then use ar to pack the .gz files back into a deb. Optionally also store some binary diffs from some particular versions the user might be likely to have lying round, as this is more efficient than zsyncing between arbitrary versions.

However, there are some issues with the .deb format. The compressed files are signed, so once you have updated your files you have to recompress them before you can feed them back into dpkg. Apart from slowing things down a bit this also means that you have to use tricks to get the resulting .gz to be bit for bit identical to the official .gz files. OK, it is possible create reproducable gzip files, but Debian seemed to be moving away from .gz compression.

If Debian decided to switch to a hsynz/zsync friendly format it should be easy. For example, if Debian switched to using uncompressed tars in their .deb files and instead distributed .deb.zstd files it should be way easier to support incremental updates than say, rewriting apt in rust.

[1] These days we would probably instead use https://github.com/sisong/hsynz