Zebra: Add an Amount type.

[hdevalence]

This should be a newtype wrapper around i64 that enforces range constraints. This means that arithmetic operations are fallible, so working with Amounts will require lifting into the Option monad, but by careful implementation of the ops traits, it should be possible to make this relatively ergonomic.

[hdevalence]

The Amount type in librustzcash says:

/// A type-safe representation of some quantity of Zcash.
///
/// An Amount can only be constructed from an integer that is within the valid monetary
/// range of `{-MAX_MONEY..MAX_MONEY}` (where `MAX_MONEY` = 21,000,000 × 10⁸ zatoshis).
/// However, this range is not preserved as an invariant internally; it is possible to
/// add two valid Amounts together to obtain an invalid Amount. It is the user's
/// responsibility to handle the result of serializing potentially-invalid Amounts. In
/// particular, a [`Transaction`] containing serialized invalid Amounts will be rejected
/// by the network consensus rules.

We can do slightly better by preserving the invariant internally, and we can do it without sacrificing ergonomics in the following way. We keep an Amount type, say, Amount(i64), and then provide impls

impl Add<Amount> for Amount {
    type Output = Option<Amount>;
    // ...
}

impl Add<Amount> for Option<Amount> {
    type Output = Option<Amount>;
    // ...
}

impl Add<Option<Amount>> for Amount {
    type Output = Option<Amount>;
    // ...
}

impl Add<Option<Amount>> for Option<Amount> {
    type Output = Option<Amount>;
    // ...
}

The impls check for overflow and return None if the resulting amount is out of range.

Although this requires more impls, it produces very good ergonomics: API users can write arbitrary expressions using Amounts, and the whole computation will be lifted into the Option monad. At the end, they can either .expect or .ok_or to handle an overflow, as appropriate for the situation.

Operations we should implement:

• [x] Add (for the 2x2 possibilities above);
• [x] Sub (for the 2x2 possibilities above);
• [x] AddAssign, but only assigning to an Option<Amount>, not an Amount;
• [x] SubAssign, but only assigning to an Option<Amount>, not an Amount;
• [ ] Sum, but probably only summing Option<Amount>s to Option<Amount>? (since Sum works on iterators, and iterators must have a common item type, so we can either sum only Amounts or only Option<Amount>s, and the latter seems more useful)

Conversions we should provide:

• [ ] conversion from u64/i64 to Amount;
• [ ] conversion from Amount to u64/i64;

Two questions that arise here and affect the rest:

Q1. If we provide a fallible conversion to Amounts, the natural way to do that would be using TryFrom/TryInto. But these work with Results, not with Options. We should be consistent, so using these would mean using Results instead of Options above. This is fine, because we can use thiserror to generate a zero-alloc error type for Amounts. Alternatively, we could use From/Into but implement them for Option<Amount>s.

Q2. If our Amount can be signed, we can't provide an infallible conversion to u64s. The bigger picture issue is that sometimes it's appropriate to have a signed Amount and other times it isn't. These seem like they should really be separate types, because confusing one case for the other case would be bad.

On Q2, looking at the Amount type in librustzcash shows a bunch of methods like from_nonnegative_i64_le_bytes that apply different validation criteria when trying to parse an Amount, but the validation information is immediately discarded (the function just returns an Amount). I feel pretty strongly that each type we have should have one implementation of our ZcashSerialize/ZcashDeserialize traits, and that requiring two different serialization methods is a sign that there are really two types being mixed into one.

How could we address this? One possibility would be to make the Amount generic over a marker type that implements a sealed trait, providing a type-level enum (as used also in redjubjub):

pub trait Marker: private::Sealed {}

pub struct Amount<M: Marker> {
    value: i64,
    _marker: PhantomData<M>,
}

pub enum NonNegative {}
pub enum AllowNegative {}
impl Marker for NonNegative {}
impl Marker for AllowNegative {}

Now an Amount is either an Amount<NonNegative> or an Amount<AllowNegative>, and the invariant is encoded into the type system. Providing an impl like

impl TryFrom<Amount<AllowNegative>> for Amount<NonNegative> {
    type Error = /* ... */;
    fn try_from(a: Amount<M>) -> Result<Amount<NonNegative>>, Self::Error> {
        // check if a.value >= 0
    }
}

allows refining the invariant on the Amount type. The ops traits could be specialized to various combinations of optional/non-optional and non-negative/negative-allowed, so that for instance adding two non-negative amounts is non-negative, but this is a lot of impls, so a simpler way might be to make the ops traits be generic over the marker:

impl<M1, M2> Add<Option<Amount<M1>>> for Option<Amount<M2>> {
    // Because the markers are unknown, we assume AllowNegative
    type Output = Option<Amount<AllowNegative>>;
    // ...
}

(or using Result depending on thoughts on Q1). This means that someone who needs to get a non-negative amount from an expression involving Amounts has to call try_into or something at the end to re-check non-negativity, but they already have to do a check anyways to ensure there were no overflows.

WDYT?

[yaahc]

@dconnolly I'm going to take over this issue rn, lmk if there's any extra context not in this issue

[yaahc]

To save time I'm thinking about only implementing the subset of the mentioned trait impls that end up being needed to make the current code that manipulates Amounts compile while maintaining an ergonomic API. In the future it should be easy to add each missing impl when they're needed.

[hdevalence]

SGTM, missing impls are fine as long as the impls that are there lift everything into the Option monad.

[yaahc]

I'm thinking instead of using a pure Marker trait we can use a trait that encodes the actual validation check that is needed for that Amount, which lets you write something like this

trait AmountConstraint {
    fn validate(value: i64) -> Result<(), &'static str>;
}

impl<C> std::convert::TryFrom<i64> for Amount<C>
where
    C: AmountConstraint,
{
    type Error = &'static str;

    fn try_from(value: i64) -> Result<Self, Self::Error> {
        C::validate(value).map(|()| value).map(Self)
    }
}

The exact shape of the constraint type is up in the air right now, I might be able to only require that the impl defines a range and then provide a validate fn that uses the given range to validate the value.

Also I'm using static strs instead of custom defined error types to interoperate with the Parse variant of SerializationError. And letting the error be returned by the Constraint trait lets each constraint type return its own more relevant errors.

[yaahc]

This issue is super fun

[yaahc]

This impl is impossible

impl Add<Option<Amount>> for Option<Amount> {
    type Output = Option<Amount>;
    // ...
}

Amount is covered by a foreign type on both sides and the trait is foreign, so it's non-coherent.

[hdevalence]

Sad. I assumed that the orphan rules would not apply because we're working with Option<Amount> rather than Option<T> but I guess this is not the case.

[yaahc]

Sad. I assumed that the orphan rules would not apply because we're working with Option<Amount> rather than Option<T> but I guess this is not the case.

Might be possible if it weren't for the constraint parameter? Or maybe it will work if I hardcode the parameter... I'll try fiddling with it for Sum because I can't impl it at all unless I figure a way around this.

[yaahc]

nope, parameterization doesn't play into the orphan rules as far as I can tell. I think the only thing that would matter is if it was wrapped in a fundamental type like Box, but I don't think Option is marked as fundamental.

Doesn't seem like I can impl std::iter::Sum at all for Amount, unless you're down with having a non Option impl that panics on validation failures...

rust impl std::iter::Sum for Option<Amount<NegativeAllowed>> { fn sum<I: Iterator<Item = Self>>(iter: I) -> Self { todo!() } }