USK and Date-Hints: Finding the newest version of a site in Freenet's immutable datastore

Freenet provides a global, anonymous datastore where you can upload sites which then work like normal websites. But different from websites, they have a version-number.

The reason for this is, that you can only upload to a given key once¹. This data then gets stored in the network and is effectively immutable (much like immutable data structures in functional programming).

In this model conflicts can arise from uploads of different users and from uploads of different versions of the site.

Avoid conflicts between users

So what if Alice uploads the file gpl.txt, and then Mallory tries to upload it again before users get the upload from Alice?

To avoid these conflicts between users, you can upload to an address defined by a key-pair. That key-pair has two keys, a public and a privat one. The URL of the site is derived from the public key. Everyone who has this URL can access the site. The private one allows uploading new data to the site. Only the owner of the private key can upload files to the site. This is the SSK: The Signed Subspace Key. It defines a space in Freenet which only you can update.

An SSK looks like this: SSK@[key]/[sitename]/[path/to/file]

Avoid conflicts between versions

But now what if Alice wants to upload a new version of gpl.txt - say GPLv3?

To avoid conflicts between different versions, each new version gets a unique identifier. The reason for using version numbers and not some other identifier is historical: To update sites despite not being able to rewrite published data, freenet users started to version their sites by simply appending a number to the name and then adding small images for future versions. If these images showed up, the new version existed.²

Most sites in freenet had a section like this (the images might take a bit to load - they are downloaded from a freenet outproxy):

technophob-116

technophob-117

technophob-118

technophob-119

At some point, the freenet developers decided to integrate that function into freenet. They added a new key-type: The Updatable Subspace Key, in short: USK.

A USK looks like this: USK@[key]/[sitename]/[version]/[path/to/file]
(The difference to the SSK is that there is a path-element for the version).

If you enter a USK, freenet automatically checks for newer versions and then shows you the most recent version of the site.

As a practical example:

technophob

Note that this link will automatically get you to version 117 (or whatever version is the current one when you read this article), even though it has version 116 in its URL.

Internally the USK simply gets translated to an SSK in the form of SSK@[key]/[sitename]-[version]/[path/to/file]. You’ll surely recognize the scheme which is used here.

This is a prime example of demand-driven development: Users found a way to make sites dynamic with the activelink-hack. Then the Freenet developers added this as official feature. As nice side-effect, the activelink-images stayed with us as part of the Freenet Culture: Almost every site in freenet has a small logo with width and height 108x36 (pixels).

Date-Hints

USKs solved the problem of having updatable sites by checking some versions into the future. But they had a limitation: If your USK-Link was very old, freenet would have to check hundreds or even thousands of URLs to find the newest version. And this would naturally be very, very slow. Due to the distributed nature of Freenet, it is also not possible to just list all files under a given Key. You can only check for directories - the sitenames.

Also files in Freenet only stay available when people access them - but checking to see whether some file might still be accessible isn’t a defined problem: The data to that file could be on the computer of someone who is currently offline. When he or she comes online again, the file could suddenly be available, so determining whether a file does not exist isn’t actually possible.

A timeline of versions could look like this:

Now imagine that you find a link on a site which was added in 2010. It would for example link to version 4 of the site. If you access this site in 2014, freenet has to check versions 5,6,7,8...18 to find the most recent version. That requires 13 downloads - and for normal freesites the versions can be as high as 1200.

But remember that you can upload to arbitrary filenames. So what if the author of the site gave you a hint of the first version in 2014? With that, freenet would only have to start at version 16 - just 3 versions to check, and the hint.

Why the first? Remember that files cannot be overwritten, so the author cannot give you the most recent version in 2014.

And this is just what the freenet developers did: Date-Hints are simply files in freenet which contain the information about the most recent version of the site at some point in time.

The datehint keys look like this: SSK@[key]/[sitename]-DATEHINT-[year]

The file found at this key is a simple plain text file with content like the following:

HINT
46
2013-7-5

The first line is the identifier, the second is the most recent version at the time of insert (the first version in the year) and the last is the date of the upload of that version.

A yearly date-hint speeds up getting the most recent version a lot. But since sites in freenet have hundreds of versions rather then tens, it is a bit too coarse. It can still leave you with 20 or 30 possible new versions. So it actually provides additional date hints on a monthly, weekly and daily basis:

• SSK@[key]/[sitename]-DATEHINT-[year]
• SSK@[key]/[sitename]-DATEHINT-[year]-WEEK-[week]
• SSK@[key]/[sitename]-DATEHINT-[year]-[month]
• SSK@[key]/[sitename]-DATEHINT-[year]-[month]-[day]

If you give freenet a USK-link, it starts on the order of 10 requests: 4 date hints with the current date and requests for versions following the version in the link. Normally it gets a result in under 10 seconds.

The algorithmic cost should be 4 additional inserts per insert, and at least 4 fetches (current year, month, week, day) followed by N fetches (with N the uploads since the last found DATEHINT) to find the most recent version.

In case of strictly periodical uploads N should be capped at the number of uploads per day, or 7 (days per week) or 4 (weeks per month) or 12 (months per year), so Freenet would need to start at most 16 fetches to get the most recent version of a USK.

Conclusion

With USKs and Date-Hints Freenet implements updatable sites with acceptable performance in its anonymous datastore with effectively immutable data.

If you want to see it for yourself, come to freenetproject.org and install freenet. It’s free software and available for Windows, GNU/Linux and MacOSX.