Add a ToDigest trait

[hackaugusto]

Proposal

Allow to write generic code with type safe wrappers around Digest

Outline

use winter_crypto::Hasher;

/// Types that implement this trait can be hashed, and the result can be a type wrapper for
/// improved type safety
trait ToDigest<H: Hasher> {
    type Output: Into<H::Digest>;

    fn to_digest(&self) -> Self::Output;
}

Usage

use hash::rpo::{Rpo256, RpoDigest};

/// Type safe wrapper around [RpoDigest], represents a [NoteNullifier].
struct Nullifier(RpoDigest);

/// Complete representation of a [Nullifier].
struct NoteNullifier {
    serial_num: RpoDigest,
    // ... Note: sample code, missing fields
}

impl From<Nullifier> for RpoDigest {
    fn from(value: Nullifier) -> Self {
        value.0
    }
}

impl ToDigest<Rpo256> for NoteNullifier {
    type Output = Nullifier;

    fn to_digest(&self) -> Self::Output {
        // NOTE: sample code, missing fields
        Nullifier(Rpo256::hash_elements(self.serial_num.as_elements()))
    }
}

Notes

The implementation above could also be made generic over Rpo256, which would make it much easier to migrate to Rpx.

Issues

Just like #312 , it is unclear if this should include the padding or not.

[hackaugusto]

If we implement #312, then we can have a blanket implementation roughly like so:

use hash::rpo::{Rpo256, RpoDigest};
use winter_crypto::{ElementHasher, Hasher};
use winter_math::ToElements;

/// Trait used to associate a type with its digest wrapper
trait Digest<E: FieldElement, H: Hasher>: ToElements<E> {
    type Output;

    fn from_digest(digest: H::Digest) -> Self::Output;
}

/// Trait to perform conversion
trait ToDigest<E: FieldElement, H: Hasher>: Digest<E, H> {
    fn to_digest(&self) -> Self::Output;
}

/// Blanket implementation
impl<T: Digest<E, H>, E: FieldElement, H> ToDigest<E, H> for T
where
    H: ElementHasher<BaseField = E::BaseField>,
{
    fn to_digest(&self) -> Self::Output {
        Self::from_digest(H::hash_elements(&self.to_elements()))
    }
}

Usage

struct Nullifier(RpoDigest);
struct NoteNullifier {
    serial_num: RpoDigest,
}

impl<E> ToElements<E> for NoteNullifier
where
    E: FieldElement,
{
    fn to_elements(&self) -> alloc::vec::Vec<E> {
        todo!()
    }
}

impl<E> Digest<E, Rpo256> for NoteNullifier
where
    E: FieldElement,
{
    type Output = Nullifier;

    fn from_digest(digest: RpoDigest) -> Self::Output {
        Nullifier(digest)
    }
}

---

The same thing could be done with the Serializable instead, which may simplify things since it has use Hasher instead of ElementHasher. The code above could also be defined in terms of the From trait, which should give us automatic conversion, which may or may not be good (easier to write code, but less explicit code, so less benefit from type safety)

[hackaugusto]

@bitwalker it would be nice if you gave your input here. I feel like the blanket implementation above is cumbersome, I endedup because of 0447-no-unused-impl-parameters. But you may have a better approach for this.

[bobbinth]

I think one of the issues with this approach is that the same object may be reduced to Digest in multiple ways. Currently, a Note object is one example where we can reduce it to NoteId or Nullifier (both of which are wrappers for Digest). We can define multiple structs for Note to accomodate one-to-one mapping (as you've suggested with NoteNullifier) but I think this actually would be more confusing than having a single struct which can be committed to in different ways.

Another example is something like NoteScript where it could be committed to either as MAST root or just a sequential hash of the underlying MAST. We don't currently do the latter - but might have to in the future.

There may be other examples (though none come to mind) where commitment to the same data needs to be computed differently based on some context.

[bitwalker]

Leaving some feedback in your code snippet @hackaugusto, since it's a little easier that way:

use hash::rpo::{Rpo256, RpoDigest};
use winter_crypto::{ElementHasher, Hasher};
use winter_math::ToElements;

// I would remove the supertrait constraint of ToElements, as it seems orthogonal to this trait
trait Digest<E: FieldElement, H: Hasher>: ToElements<E> {
    type Output;

    // I find this a bit confusing - the implementation _is_ a digest, but the trait offers a
    // method to convert "from" a digest...to a digest? I'm sure this is just a naming conflict
    // but I do think it would make things a bit too confusing when reading code involving this method
    fn from_digest(digest: H::Digest) -> Self::Output;
}

// Same sort of issue here - it's quite confusing to have something that implements ToDigest _be_ a Digest,
// I would expect the `impl Digest` type here to be an associated type of the trait, since it's hard to imagine
// a case where the implementation of this trait wouldn't be sensitive to at least one of the type parameters
// here, and the type of the digest seems like a reasonable fixed point around which any implementation variance
// would occur - but you'd have a better sense for that than I.
trait ToDigest<E: FieldElement, H: Hasher>: Digest<E, H> {
    fn to_digest(&self) -> Self::Output;
}

// This seems fine, but a couple of thoughts:
//
//  * Blanket implementations make it all but impossible to customize the behavior, so you need to be
//    really super sure that the blanket covers _everything_, or you end up needing newtypes or some other workaround
//
//  * If the design of the Digest and ToDigest traits is oriented towards enabling the blanket implementation, what would
//     things look like if you decided not to provide the blanket? Would those traits be more general and thus more broadly
//     useful? If so, I would strongly consider going that route instead, even if it means needing to manually implement those
//     traits
impl<T: Digest<E, H>, E: FieldElement, H> ToDigest<E, H> for T
where
    H: ElementHasher<BaseField = E::BaseField>,
{
    fn to_digest(&self) -> Self::Output {
        Self::from_digest(H::hash_elements(&self.to_elements()))
    }
}

I'm not super familiar with the ways in which this set of traits would be used, so I'm not sure I can provide much in the way of interesting alternatives or advice - what you've laid out here seems reasonable though! If you have a few examples of where these traits would shine, that would help for sure.

I do think @bobbinth raises a good point, which is that when you have conversions like this that are ambiguous at a callsite without the turbofish operator (i.e. specifying the concrete types with ::<>), then it may be a sign that a different abstraction is more appropriate - but that's not always the case (consider collect, a method which often requires turbofish simply because the compiler isn't able to reason through all of the implicit types involved in a given iterator chain). Hard for me to say what a better approach would be though without feeling the pain points myself.

[hackaugusto]

We can define multiple structs for Note to accomodate one-to-one mapping (as you've suggested with NoteNullifier) but I think this actually would be more confusing than having a single struct which can be committed to in different ways.

If wrappers is a no-go, we can 1. use a method for these special cases (like we do now) 2. change the associated type to a generic. Which one do you prefer?

@bitwalker thanks for having a look! To give you more context. We use hashes everywhere, e.g. mast root, note id/nullifier/recipient, account/note/nullifier dbs root, and so on. In all these cases we have by default a Digest type, this means we often have functions with multiple Digest as arguments, and we have no type safety. So the idea above was 1. wrap the digest to improve typing 2. have a trait to abstract over all things that can be hashed.