multiformats / multicodec

Compact self-describing codecs. Save space by using predefined multicodec tables.
MIT License
340 stars 205 forks source link

Rescue Prime hash #287

Closed vladfaust closed 2 years ago

vladfaust commented 2 years ago

I propose adding the Rescue Prime hash function codec.

Use-case

Rescue Prime is the standard hashing algorithm used in Miden VM[^1]. With Miden, the ownership of a CID with rescue prime multihash may be efficiently proven without revealing the file contents.

[^1]: Miden VM is sponsored by Polygon.

rvagg commented 2 years ago

2.1 Parameters

A member of the Rescue-Prime family of hash functions is fully determined by a tuple of primary parameters (p, m, cq, s).

Because it's a family of parameterised hash functions then to adding it here just as "rescue-prime" is going to be a problem because it doesn't tell you how to re-run it to generate a digest for verification (the typical usage of multihashes in this table). So it needs to come along with additional context required to tell you that. This could be accomplished in a couple of different ways—either embed the primary parameters into the name of the function (rescue-prime-p-m-c-s where each of p, m, c and s are concrete values that determine the specific form of the function)—this is kind of exemplified by the blake2* entries, each of which specify a different way of operating blake2 to get the digest (skein is similar). Or, alternatively, and perhaps more realistically, by naming a variation of it that's used within some existing system (e.g. rescue-prime-midenvm).

Poseidon is a similarly parameterised hash function, the current two entries for it @ https://github.com/multiformats/multicodec/blob/d95df3a0a8809e7d7b50285d6e149740d1321a76/table.csv#L480-L481 embed details about the variations in the names, but anticipating that more could be added that have different permutations.

For Miden, I see it's using a specific version of it: https://docs.rs/winter-crypto/0.3.2/winter_crypto/hashers/struct.Rp64_256.html — interestingly, not only does it have specific parameters embedded but it also makes some specific changes to the way it operates. So this would suggest that maybe it needs to be named, either using miden to link it to Miden VM, or maybe after the project the hash function is implemented in (rescue-prime-wintercrypto-256 [there's also a 248 in there, perhaps there'll be more later!], or some such name that hopefully isn't too long and verbose).

So, if you have a usecase for this and want to get it in, open a PR to add an entry for it, somewhere up at the top of the table near the Poseidon but leaving plenty of room for adding permutaitons of both, 0xb600 perhaps.