Consider using longer hashes than 128 bit

[bob1de]

Hi,

While working with kopia over the last days, I noticed that root and snapshot IDs are only 128 bit long, so they are the same size as md5 hashes. I suppose the same hash size is used for addressing content blocks, correct?

Given that even git, which used sha1 (160 bit) now moves to sha256 (256 bit), kopia should probably switch to a larger hash size as well. Kopia repos store an enormous amount of blocks, comparable to huge git repos, so the chance of a hash collision seems present here as well.

I don't know much about the internals of kopia's repo format, but if switching the hash size would require existing blocks to be re-hashed in order to rebuild the indexes, such a decision should probably be made as early as possible.

What do you think?

Best regards
Robert

[jkowalski]

There is an option to use longer hashes when creating a repository. The downside is that the indexes would be twice as large.

Based on the birthday paradox the 50% chance of collision is when you have around 1/2^64 contents when using 128 bit hashes and 1/2^128 when using 256 bit hashes. Both seem crazy low even for very large repositories which are way beyond what anybody has ever done with Kopia, so something else (in terms of scalability) is likely to fail before we get hash collisions.

Given that all hashes include secret that is different per repository, a malicious collision is very unlikely and will certainly not spread to other repositories (two files hashing to same value in one repo will hash to different values in another).

[bob1de]

Given that all hashes include secret that is different per repository, a malicious collision is very unlikely and will certainly not spread to other repositories (two files hashing to same value in one repo will hash to different values in another).

I wasn't refering to malicious attempts here, just the incidence of two blocks in the same repo hashing to the same value, which is of course extremely low as you pointed out correctly.

Nevertheless, the main point here was to say that git as another popular project which also uses content-addressed storage seemed to feel the need for larger hashes recently, and due to the parallels to kopia I wanted to bring this up.

BTW, are the supported values for encryption algorithm, hash size etc. documented somewhere? I couldn't find something in --help-full.

[bob1de]

There is an option to use longer hashes when creating a repository. The downside is that the indexes would be twice as large.

Couldn't this be mitigated by using a more compact serialization method for the data? In the architecture docs you mention JSON, wouldn't e.g. msgpack with something like this library be a smaller and even better performing alternative?

[bob1de]

Just as an addition: I checked their docs again and it turned out that in case of git, the main reason for switching algorithms wasn't hash size, instead it was the goal to move away from sha1 in the first place, which doesn't apply to kopia anyway.

[jkowalski]

Currently supported hashes are:

BLAKE2B-256      BLAKE2S-128      BLAKE3-256       HMAC-SHA224      HMAC-SHA256-128  HMAC-SHA3-256                                                 
BLAKE2B-256-128  BLAKE2S-256      BLAKE3-256-128   HMAC-SHA256      HMAC-SHA3-224                                                                

Unfortunately they are not listed in the docs yet (patches welcome). They are listed in the UI when you create a repository and in CLI you can do something like this:

$ kopia repo create --block-hash help                                                                                                                         1 ↵
kopia: error: enum value must be one of BLAKE2B-256,BLAKE2B-256-128,BLAKE2S-128,BLAKE2S-256,BLAKE3-256,BLAKE3-256-128,HMAC-SHA224,HMAC-SHA256,HMAC-SHA256-128,HMAC-SHA3-224,HMAC-SHA3-256, got 'help', try --help

Kopia already uses custom-designed index format, much more densely packed than JSON and msgpack for that matter. It is also optimized for memory-mapped traversal without having to parse the whole thing into RAM. It uses 20 bytes + hash length per content ID (+minor constant overhead), so for 256-bit hashes it would be 52 bytes per content and for 128-byte hashes it's 36 bytes per content.

The main limiting factor is that all indexes must be downloaded and cached on the client before the repository can be used, so if you had 100M contents, that would require ~3.6 GB of indexes for 128-bit hashes and ~5.2 GB for 256-bit hashes.

[bob1de]

Unfortunately they are not listed in the docs yet (patches welcome).

I'll look into docs structure again and make a PR soon.

Kopia already uses custom-designed index format, much more densely packed than JSON and msgpack for that matter. It is also optimized for memory-mapped traversal without having to parse the whole thing into RAM. It uses 20 bytes + hash length per content ID (+minor constant overhead), so for 256-bit hashes it would be 52 bytes per content and for 128-byte hashes it's 36 bytes per content.

I see, thanks for explaining!

I confused indexes with manifest storage, where JSON is used for serialization, so I was under the impression you also do so for indexes. But I guess for manifests size is not as crucial because they don't have to be cached on the client, right? And even the order of magnitude slower (de)serialization is probably not that noticeable here.