Reduce space taken by resident keys

[sosthene-nitrokey]

Investigation on the space taken by resident keys:

Tested with 5 resident keys:

case	blocks consumed
5 keys For 1 rp	24
5 keys, no per-rp folder	22
5 keys, no per-rp folder, without trussed overhead	14
5 keys in 1 file	17
5 keys in 1 file, without trussed overhead	9
5 keys in 4 rp	30
5 keys in 4 rp, without trussed overhead	25

We see that the current approach is the worst, but the others make it harder to iterate over relying parties. Storing everything in 1 file seems to be the most efficient, though the approach tested does not account for the (small) overhead of separating each key in the file.
On the other hand having everything in one file makes us face the max file size limitation faster to encounter. We can split the file once it gets bigger than say 1kB (around 7 keys in average), but then removing 1 key becomes a harder problem. Some files could end up storing a non-optimal amount of keys. But in that case we can still remove from the key from this file and this is still always better than the second better

1 file per resident key could be an improvement thanks to littlefs2 inlining capabilities, though not as good as 1 file for all keys.

[sosthene-nitrokey]

Updating the littlefs version to 2.9 does not yield any improvement.

[robin-nitrokey]

Can you add a line with 5 keys in 4 rp, no per-rp folder? I think that is the most common case and has more potential for improvement than the 1 rp case.

[sosthene-nitrokey]

What would be the difference with 5 keys, no per-rp folder ? From the point of view of the filesystem it's the same.

[robin-nitrokey]

Didn’t you mention some overhead for the RP metadata? Or was it the other way round, that reducing the overhead is another potential improvement?

[sosthene-nitrokey]

These measurement don't change the internal data of the files. I just move the files around and test the space taken. It's faster than actually changing and regenerating everything each time.

Removing the RP ID from the files in the no-folder case would also required storing it once someplace else, which complexifies the approach and would add its own overhead.

[sosthene-nitrokey]

It would be easier to do in the one file approach. The matching RP ID could be stored in a map once and each credential could just store a u16 ID that references the full RP ID.

[robin-nitrokey]

I see. Did you check the serialized size of a typical credential? AFAIR FIDO operations are already rather heavy in stack usage so we probably cannot afford to use too much stack for deserialization. So I’m not sure if we can reliably fit 10 credentials in a single file. Theoretically, it would be possible to use n files with up to m credentials each, but that would basically mean reimplementing the FS. Edit: I see you mentioned that typically 7 keys fit into 1024 bytes.

[sosthene-nitrokey]

5 credentials take 665 bytes for the 1file approach. This will vary depending on RP and User ID size for each credential.

Theoretically, it would be possible to use n files with up to m credentials each, but that would basically mean reimplementing the FS

But I think that is the optimal solution.

The way I would do it would be something like len1 | credential1 | len2 | credential2|... That way we can load 1 file, and iterate over each credential without needing to parse all of them at once. And by adding zero-copy deserialisation we would not need that much stack.

[robin-nitrokey]

One benefit of the 1-file-per-credential approach is the easy lookup. This is especially relevant in two settings: Firstly, in NFC-powered mode, we want to reduce the complexity as much as possible because of the power constraints. Secondly, if we add support for storing credentials on the EFS, we could significantly bump the limit, so it is more important that we can quickly find a credential.

In the second setting, we could use the one-file-for-all implementation for the IFS while keeping the 1-file-per-credential implementation for the EFS.

[sosthene-nitrokey]

Right,

So it would make sense to use 1 file per-rp with a name like rp_hash.uid_hash where it's currently rp_hash/uid_hash