[XXX This is too long. Need to shorten.] Gzz [1]_ stores its data in *Storm*, a storage layer abstraction providing for network transparency. In Storm, all data is stored in *blocks*, file-like immutable byte sequences identified by an SHA-1 cryptographic hash. A Storm data pool is therefore *append-and-delete-only*: Blocks can be added or removed, but an existing block cannot be changed (as long as the hash function is not compromised). This property has many desirable implications; for example, when dealing with files, a faulty program may overwrite an existing file with illegal data when a user hits 'save', while with Storm, the old data would remain accessible even when the new, faulty data is added, so the faulty program would not automatically destroy the correct previous version. Another potential benefit is versioning: By simply not deleting old blocks, all previous versions of all documents remain accessible. However, in practice it is not a trivial task to maintain a version history in Storm. As a first cut, we may attempt to store each new version as a new block; however, for a document of say 500KB size, storing a slightly modified copy each time a user saves the document will quickly use up a lot of storage space. Simply deleting old versions helps that problem, but destroys both advantages of using Storm, above. The more standard way of keeping a version history is to store only the *differences* between versions. In a first cut, a block would contain a reference to a previous version (as a reference to another Storm block, i.e., a cryptographic hash) as well as the differences from that previous to the current version. We imply that the reference to the previous version is a reference to a similar block, containing a reference to an earlier version and a diff (set of differences), except for the very first version in the chain. Indeed this is the scheme that Gzz has used for a long time. However, it is not without problems. Consider a chain of diffs a,b,c,d,e (so that a is the first version, or diff from the empty version, b is a diff from a, c is a diff from b and so on). If we remove c, there is no way to reconstruct the versions represented by d or e, since the chain of versions is broken. In other words, we can keep the old versions now, but we have to keep them *all* in order to keep the current versions accessible. (This is an even bigger problem if, to provide protection from system failure, we want to save every ten seconds or so, later removing the spurious versions.) The solution proposed here is as follows: Versions can be stored as blocks in Gzz (like in the first trivial scheme above). When the user hits 'save', we first construct a block for that version and store it in Storm. The mapping from version to block is canonical, so that the same version is always mapped to the same block. Then, we generate the diff from the previous version to the current version. We save this diff in a block, additionally containing the ids (cryptographic hashes) of the previous and current versions. We can then reconstruct the current version-- byte for byte-- from the previous version and the diff. If the diff is invertible, we can also reconstruct the previous version-- byte for byte-- from the current version and the diff. The byte-for-byte equality is important, since it allows us to verify that the diff is correct: we need not trust its claim that it represents a diff between two given versions, we can verify by checking the resulting version's cryptographic hash. (If the representations of a version weren't equal byte-for-byte, the hashes would of course not match.) Now, say we have a chain of versions, 1,2,3,4,5,6, represented by version 1 and diffs a,b,c,d,e (where a is the diff between versions 1 and 2, b the diff between 2 and 3 and so on). Assume we want to remove versions 3 and 4, only keeping versions 1, 2, 5 and 6. We can do so by: - Generating version 5 using version 1 and diffs a, b, c, and d. - Remove diffs b, c and d. We then have versions 1 and 5 as well as diffs a and e; this suffices for re-constructing versions 2 and 6 as well. (An alternative is to store the diff between version 2 and version 5 instead of storing version 5 explicitly.) An additional benefit is that we can easily provide backward diffing: By storing the current version (6 in this case) as well as the diffs, we have quick access to the current version, and reasonably quick access to the more current past versions. Backward diffing is a usual technique used by e.g. CVS; however, while it fits well with the present design, it would have been hard to archieve with the trivial diffing design, above. This paper describes this method for storing differences in detail. An architecture for implementation is given, and our current implementation for the Gzz project is discussed. \- Benja .. [1] http://gzz.info/