u160 arithmetic

[aszepieniec]

We need this for block consensus programs, for the difficulty adjustment.

Needed operations:

• equality
• comparision (less than)
• addition
• subtraction maybe not needed
• multiplication of a u160 with a u32 (asserting no overflow) maybe not needed
• multiplication of two u160s (asserting no overflow)
• division -- Handled through non-deterministic input and above operations.

The compiler should be able to handle this as well through an array of 5 u32s.

Co-authored-by: @Sword-Smith

[Sword-Smith]

As far as I can see, we need to implement the safe_mul_fixed_point_rational found in neptune-core. And the target method on Difficulty. Considering the latter:

    pub(crate) fn target(&self) -> Digest {
        let difficulty_as_bui: BigUint = BigUint::from(*self);
        let max_threshold_as_bui: BigUint =
            Digest([BFieldElement::new(BFieldElement::MAX); Digest::LEN]).into();
        let threshold_as_bui: BigUint = max_threshold_as_bui / difficulty_as_bui;

        threshold_as_bui.try_into().unwrap()
    }

If we ignore the conversion to BigUint in the above algorithm, then we need to be able to calculate q = n / d where all numbers are u160, or five u32s. If we divine in the result q and show that q * d + r == n && r < d, then we don't need to implement generic division. We only need multiplication, addition, equality (already there), and less than (all operations for pairs of u160s). The uniqueness of q and r follow from Euclid's division lemma.

We also have a conversion method from BigUint -> Digest, which I think can be reinterpreted as a u160 -> Digest conversion:

impl TryFrom<BigUint> for Digest {
    type Error = TryFromDigestError;

    fn try_from(value: BigUint) -> Result<Self, Self::Error> {
        let mut remaining = value;
        let mut digest_innards = [BFieldElement::ZERO; Self::LEN];
        let modulus: BigUint = BFieldElement::P.into();
        for digest_element in digest_innards.iter_mut() {
            let element = u64::try_from(remaining.clone() % modulus.clone()).unwrap();
            *digest_element = BFieldElement::new(element);
            remaining /= modulus.clone();
        }

        if !remaining.is_zero() {
            return Err(Self::Error::Overflow);
        }

        Ok(Digest::new(digest_innards))
    }
}

For this, we need modulus and division which should be covered by the above technique of divining-in the result. Euclid's division lemma ensures the uniqueness of the solution.

[Sword-Smith]

u160 safe multiplication added in 52e7cf5.

[Sword-Smith]

div-mod handled in #158

[Sword-Smith]

closed by the merge of #158 in f7dedc2.