aead: use IS_POSTFIX associated constant instead of the PostfixTagged marker trait?

[newpavlov]

The current design uses the PostfixTagged marker trait to provide the blanket impls of AeadInPlace and Aead traits. Meanwhile prefix AEAD construction are responsible for implementing AeadInPlace explicitly. It means that an AEAD implementation may not have implementation of the Aead trait, the "go-to" trait which we recommend to users.

I think we should instead introduce const IS_POSTFIX: bool; associated constant to the AeadCore trait. It would allow us to write generic implementation of AeadInPlace/Aead traits which would cover both prefix and postfix constructions. Blanket impl for the prefix construction would involve overlapping copies, but in future it may be overwritten by a more efficient implementation (e.g. after development of offsetting encryption/decryption APIs) in downstream crates.

We can not do the same with the PostfixTagged trait without relying on specialization, which is currently unstable with no clear path for stabilization.

There is a small wrinkle with the IS_POSTFIX approach. Some constructions (e.g. MGM) do not explicitly specify tag position. But I think it's fine to default to the postfix mode (which is the de facto standard) unless explicitly specified otherwise.

Previous discussions:

• aead: Proposal for revision to API surface for trait AeadInPlace #1672
• aead: rework traits #1713 (comment)
• aead: factor apart AeadInPlace/*Detached #1714 (comment)

[tarcieri]

Regardless of the marker-trait-versus-associated-constant discussion, I strongly dislike using a boolean flag.

What does it mean when IS_POSTFIX is false? It implicitly means a prefix tagged construction, but that's not immediately clear.

An enum with variants like Prefix and Postfix would be much clearer.

[newpavlov]

An enum with variants like Prefix and Postfix would be much clearer.

I agree, but remember that const generics have various restrictions around non-integer/bool generic constants. I don't remember the exact problems, so we would need to experiment with it.

Alternatively, we could use an associated type bounded by a sealed trait implemented only for two types.

[tarcieri]

...but the use case here is an associated constant, not const generics

[newpavlov]

I am fine with either. Associated type would be a bit less concise since we would need to define an additional trait and two types, but otherwise it's isomorphic to the associated bool constant.

[tarcieri]

I don't even see how const generics are applicable here. Your PR uses an associated constant.

[newpavlov]

I think I tried the enum approach, but it did not work out for some reason in the end. I don't remember the exact details, so I would need to experiment with it again.

[tarcieri]

Regarding the general question of a marker trait versus an associated constant, postfix tags
are trivial to support generically, while prefix tags are not.

The marker trait approach means the two constructions which use prefix tags, aes-siv and xsalsa20poly1305, can use bespoke implementations which we can evolve as new features to make them efficient become available. The path to optimizing it remains hypothetical. At least for now, a generic solution for prefix tags is at best a leaky abstraction (copying).

If we had a solution for writing a generic implementation which performs well in all cases, I think an associated constant would make more sense, but at this point we lack even a hypothetical design, which to me is the first step.

I guess it might be something like adding an offset to something like InOutBuf which can compute two different slices within the same buffer, but that doesn’t feel particularly type safe to me. It might make sense to have a completely different type designed specifically for this case. The underlying stream cipher implementations would need to be similarly “offset aware”.

Perhaps it would make sense to work on concrete implementations of this idea first, then try to build the stream cipher abstractions, and once we have the stream cipher abstractions, look at how we can use them generically within aead.

Since we have none of that yet, to me it’s a feature, and not a bug, that crates like aes-siv and xsalsa20poly1305 don’t receive generic impls of traits like Aead/AeadInPlace. They already use copies, but optimizing those copies away is easier to do ona crate-by-crate basis until we actually have generic abstractions in place.

[newpavlov]

As I wrote here, I don't have good ideas on how we could implement offset processing generically, safely, and efficiently.

a generic solution for prefix tags is at best a leaky abstraction (copying)

I don't see why it's a problem. The existing implementations in aes-siv and xsalsa20poly1305 are also "leaky" since they rely on copy_within. We would just replace the existing leaky implementations in crates with a leaky blanket implementation.

[tarcieri]

My suggestion was to start by fixing the concrete implementations, and once we have more than one implementation of a solution, building an abstraction.

If we can get there, maybe a generic solution for prefix tag handling in aead would make sense, but currently we have nothing.

I don’t think it makes sense to start with a leaky generic solution which codifies suboptimal copying. It just makes things that much harder to evolve.

[newpavlov]

We have two concrete implementations, both are implemented in terms of copy_within. I do not understand why you are fine with them using "suboptimal copying", but not with exactly the same approach implemented generically.

It just makes things that much harder to evolve.

How? Publicly we expose only the method API. We are completely free to overwrite the blanket impl in implementation crates and even to change the blanket impl later. In my opinion, while we don't have a clear solution for the offset processing it's fine to codify the "suboptimal" solution. We then can prototype efficient approaches in implementation crates and later migrate them into aead (potentially in a future breaking release).

And we probably should recommend the buffer-to-buffer Buffer methods instead of the in-place Buffer methods. They are easier to use and do not have the minor performance pitfall with prefix constructions.

[tarcieri]

A suboptimal concrete implementation is easy to improve.

A suboptimal generic implementation, with no plan for how to build optimal abstractions, is fundamentally leaky.

[newpavlov]

We are talking past each other...

How is it "fundamentally leaky" if we are able to overwrite the blanket implementation in downstream crates? The method would also have exactly the same signature as it has now.

UPD: Here and above I meant "trait methods with default implementations" instead of "blanket impl".