Composition. How. Send Help

[Cydhra]

So I have the following scenario:
I want to implement a set of protocols (for cryprographic secret sharing). Those protocols differ in complexity (by which I mean, some of them require state and some don't) and may depend on each other (in a tree-like structure).

For some (or all) of the protocols, different implementations exist (or different implementations are thinkable), so I started modelling them with traits. However, since there are so many protocols (since the whole thing is supposed to be expandable, there are effectively infinite), I want the user to be able to compose multiple protocols in a single type (the "super-protocol"), so they do not have to handle 20 objects.
Furthermore, since some of the protocols depend on each other and some of them have state, it is also very nice for implementation, if all protocols compose into one object, so my functions do not need 20 parameters just for dependencies.

There are two things I want to avoid:

• Having the user to write 20 boiler-plate delegation implementations if they need 20 protocols.
• Having the user handle more than one protocol instance

So for example I have:

pub trait ThresholdSecretSharingScheme<T, S> {
    fn generate_shares<R>(rng: &mut R, secret: &T, count: usize, threshold: usize) -> Vec<S>
    where
        R: RngCore + CryptoRng;

    fn reconstruct_secret(shares: &[S], threshold: usize) -> T;
}

pub trait MultiplicationScheme<T, S>:
    ThresholdSecretSharingScheme<T, S> + LinearSharingScheme<T, S>
{
    fn multiply<'a>(&'a mut self, lhs: &S, rhs: &S)
        -> Pin<Box<dyn Future<Output = S> + Send + 'a>>;
}

(These are not the real types by the way; those are even more complicated).

Now I want two default implementations for the MultiplicationScheme. That is, where it's getting complicated. I tried different approaches:

• Using trait inheritance obviously doesn't work, as I can't give default implementations for methods of super-traits (which would create the diamond problem, so I see why I can't do that)
• Using different proxy-structs and impl the traits for them does not work, as this kills composability: Creating struct MultiplicationA and struct MultiplicationB allows me to implement two different protocols for them, but the user cannot use those structs to create the "super-protocol" (technically the user could reimplement all protocols for the "super-protocol" struct and delegate all calls to members of that struct. But that is quite unhandy and that is exactly what I am trying to avoid here)
• Autodelegation does not exist. There is a delegate crate, but it does only save the methods' implementation (one line), because the method headers must be reiterated, because reflection does not exist.

So I came up with something, that I thought was quite clever, until the compiler kindly explained to me, that I can't do that:

pub trait BeaverRandomizationMultiplication<T, S>: MultiplicationScheme<T, S>
where
    T: PrimeField,
{
    // some methods special to this protocol implementation
}

impl<P, T, S> MultiplicationScheme<T, S> for P
where
    T: PrimeField,
    S:  'static,
    P: BeaverRandomizationMultiplication<T, S>
        + ThresholdSecretSharingScheme<T, S>,
{
    fn multiply<'a>(
        &'a mut self,
        lhs: &S,
        rhs: &S,
    ) -> Pin<Box<dyn Future<Output = S> + Send + 'a>> 
    {
        // snip
    }
}

(Again, the types and type bounds are simplified, the real code is more complicated)

My idea here was, that I can provide those marker traits (like BeaverRandomizationMultiplication) and implement the protocol trait (MultiplicationProtocol) for all P that implement the marker trait. The compiler didn't complain and so I got to work. I implemented lots of composed protocols like:

pub async fn joint_unbounded_inversion<R, T, S, P>(
    rng: &mut R,
    protocol: &mut P,
    elements: &[S],
) -> Vec<S>
where
    R: RngCore + CryptoRng,
    T: PrimeField,
    S: Clone + 'static,
    P: ThresholdSecretSharingScheme<T, S>
        + CliqueCommunicationScheme<T, S>
        + MultiplicationScheme<T, S>,
{
    // snip
}

I simplified the types again, but note, that this protocol requires

• ThresholdSecretSharingScheme
• CliqueCommunicationScheme
• MultiplicationScheme

so, if I were to split those, I would need more parameters. Furthermore, note, that protocol is a mutable reference, so even if I were to split all protocols in different parameters, it would also force the user to do the same. If the user tried to compose the split protocols into the "super-protocol" using boiler-plate delegation, they wouldn't be able to provide the "super-protocol" to the function, because they would need to create three mutable references to it.

So that worked great, but then I tried to add another MultiplicationProtocol: Now the compiler complained, because I tried to implement both implementations (the beaver one, and the new one) for all P, and a crate could implement both marker traits on the same type.

This confuses me a bit, because technically (at least from my perspective) it would make more sense to allow that and let the compiler complain if one tried to implement both marker traits on the same type, but guess what.

So I tried to be sneaky and did the following (I won't use the multiplication protocol example here, because it uses self as parameter, which isn't possible in my new solution):

pub trait RandomNumberGenerationScheme<T, S, P>
where
    P: ThresholdSecretSharingScheme<T, S>,
{
    fn generate_random_number_sharing<R>(
        rng: &mut R,
        protocol: &mut P,
    ) -> Pin<Box<dyn Future<Output = S>>>
    where
        R: RngCore + CryptoRng;
}

pub trait DefaultRandomNumberGenerationScheme<T, S, P>
where
    P: ThresholdSecretSharingScheme<T, S>,
{
    type DefaultImplementation: RandomNumberGenerationScheme<T, S, P>;
}

impl<T, S, P> RandomNumberGenerationScheme<T, S, P> for P
where
    P: DefaultRandomNumberGenerationScheme<T, S, P>
        + ThresholdSecretSharingScheme<T, S>,
{
    fn generate_random_number_sharing<R>(
        rng: &mut R,
        protocol: &mut P,
    ) -> Pin<Box<dyn Future<Output = S>>>
    where
        R: RngCore + CryptoRng,
    {
        P::DefaultImplementation::generate_random_number_sharing(rng, protocol)
    }
}

(again, I simplified the type bounds)
So now I thought that I would cheat death, because I would only ever have one impl for P. The user would be supposed to do this:

struct SumRandomNumberGeneration {}

impl<T, S, P> RandomNumberGenerationScheme<T, S, P> for SumRandomNumberGeneration
where
    P: ThresholdSecretSharingScheme<T, S>,
{
    // method implementation omited
}

However, death doesn't like to be cheated: This solution would be fine, if it wasn't generic. But because it is generic, the orphan rule no longer applies, so a downstream crate could very well implement DefaultRandomNumberGenerationScheme for SumRandomNumberGeneration which, again, creates a conflicting impl.

So, for the love of all the holy and unholy things in this world, please point me into a direction where I can find non-boilerplate composition of my protocols.

This post is quite long! I tried to reference everything I did and tried. But that is hard, considering, that I am working on this for several weeks now. So, if anything comes up in discussion, I will edit the post, adding more information about stuff that doesn't work (or why it doesn't work).
If you want the unsimplified and complete code, then head to the repository (there are other crates in the same repo: ignore those, they are mostly awful)

[Cydhra]

So after some discussion on the community discord, one Globi::<!> pointed me in the right direction. As Devid Wheeler said "All problems in computer science can be solved by another level of indirection". And this is true in this case, too:

Instead of implementing Delegates directly from their trait and resulting a clash between default implementations and delegates, three new traits are introduced per protocol:

• A marker trait, that is used to proof type-safety to the compiler (and is very inconvenient to use)
• An copy of the original trait that accepts the marker trait as another generic type parameter
• A delegate trait, that exposes an associated type as its only member and is later used for the delegation.

It looks like this:

pub trait MultiplicationScheme<T, S>
{
    fn multiply<'a>(&'a mut self, lhs: &S, rhs: &S)
        -> Pin<Box<dyn Future<Output = S> + Send + 'a>>;
}

pub trait MultiplicationSchemeImpl<T, S, Marker>
{
    fn multiply<'a>(&'a mut self, lhs: &S, rhs: &S)
        -> Pin<Box<dyn Future<Output = S> + Send + 'a>>;
}

pub trait MultiplicationSchemeMarker {
    type Marker;
}

pub trait MultiplicationSchemeDelegate<T, S> {
    type Delegate: MultiplicationScheme<T, S>;
}

Then, every default implementation just implements MultiplicationScheme just as always. If the user wants to implement the protocol theirself, they'll just implement MultiplicationScheme as well. If, however, they want to use one of the default implementations, they have to do something weird:

struct ExampleProtocol;

impl MultiplicationSchemeMarker for ExampleProtocol {
    type Marker = crate::Delegate;
}

impl MultiplicationSchemeDelegate<u32, (usize, u32)> for ExampleProtocol {
    type Delegate = SomeVeryFastDefaultMultiplicationScheme<u32, (usize, 32)>;
}

This works, because of the following implementation of MultiplicationScheme:

impl<T, S, Marker> MultiplicationScheme<T, S> for P
where
        P: MultiplicationSchemeMarker<Marker=Marker>,
        P: MultiplicationSchemeImpl<T, S, Marker>,
        {
            // method delegation
        }

A similar block just implements MultiplicationSchemeImpl for all MultiplicationSchemeDelegates:

impl<T, S> MultiplicationSchemeImpl<T, S, crate::Delegate> for P
where
        P: MultiplicationSchemeDelegate<T, S>,
        {
            // method delegation
        }

The ..Impl traits only exist, to hide the <..., Marker> generics from downstream protocols. The MultiplicationSchemeImpl trait should never be used outside of the crate that defines it. It cannot be private, though, because it is exposed in those public impl blocks.

Previously, the compiler wouldn't compile something, because a downstream crate could implement the original marker traits (like BeaverRandomizationMultiplication from the original post) for an existing type (that already implements MultiplicationScheme) thus creating a conflict for that type.
But because the new marker trait (MultiplicationSchemeMarker) is not generic, a downstream crate can never do that for an existing type (orphan rule) but only for its own types. Therefore the compiler can now proof, that my own types are free of conflicts and I don't have to worry about any downstream types (because those will be handled by the compiler in their own crates).

Of course, the solution is not very clean, because now the user always has to implement the marker trait whenever they want to use a default implementation and the type Marker will never assume any other value than the marker struct crate::Delegate. Maybe someone will solve that, too.

By the way: In my repository, I hid all this boilerplate behind a proc-macro. Only the user implementation of the Marker-trait cannot be hidden in a macro, because the macro cannot know the type bounds of the delegate impl block.