equihash_verifier.rs

extern crate typenum;
extern crate generic_array;

use typenum::marker_traits::*;
use typenum::operator_aliases::*;
use typenum::type_operators::*;
use typenum::consts::*;
use generic_array::GenericArray;
use generic_array::ArrayLength;

#[derive(Clone)]
struct Node<HashLen: ArrayLength<u8>, Indicies: ArrayLength<u32>> {
    hash: GenericArray<u8, HashLen>,
    indicies: GenericArray<u32, Indicies>
}

trait Equihash {
    type N;
    type K;

    fn is_valid(a: &[u32]) -> bool;
}

type IndicesPerHashOutput<N> = Quot<U512, N>;
type HashOutput<N> = Quot<Prod<IndicesPerHashOutput<N>, N>, U8>;
type CollisionBitLength<N, K> = Quot<N, Add1<K>>;
type CollisionByteLength<N, K> = Quot<Sum<CollisionBitLength<N, K>, U7>, U8>;
type HashLength<N, K> = Prod<Add1<K>, CollisionByteLength<N, K>>;
type SolutionWidth<N, K> = Prod<Exp<U2, K>, Quot<Add1<CollisionBitLength<N, K>>, U8>>;

use std::ops::{Add, Sub, Mul, Div};

impl<N, K> Equihash for (N, K)
    where U2: Pow<K>,
          K: CheckTree<Self, HashLen=HashLength<N, K>, Indicies=U1>,
          SolutionWidth<N, K>: Unsigned,
          Exp<U2, K>: Mul<Quot<Add1<CollisionBitLength<N, K>>, U8>>,
          Add1<CollisionBitLength<N, K>>: Div<U8>,
          CollisionBitLength<N, K>: Add<B1>,
          N: Div<Add1<K>>,
          K: Add<B1>,
          HashLength<N, K>: ArrayLength<u8>,
          Add1<K>: Mul<CollisionByteLength<N, K>>,
          CollisionBitLength<N, K>: Add<U7>,
          Sum<CollisionBitLength<N, K>, U7>: Div<U8>
{
    type N = N;
    type K = K;

    fn is_valid(a: &[u32]) -> bool {
        if a.len() != SolutionWidth::<N, K>::to_usize() {
            return false;
        }

        let v: Vec<Node<HashLength<N, K>, U1>> = a.iter().map(|index| {
            let mut indicies = GenericArray::default();
            indicies[0] = *index;

            Node {
                hash: GenericArray::default(),
                indicies: indicies
            }
        }).collect();

        <K as CheckTree<Self>>::is_valid(v)
    }
}

trait CheckTree<P: Equihash> {
    type HashLen: ArrayLength<u8>;
    type Indicies: ArrayLength<u32>;

    fn is_valid(v: Vec<Node<Self::HashLen, Self::Indicies>>) -> bool;
}

impl<T: NonZero, P: Equihash> CheckTree<P> for T
    where U2: Pow<P::K>,
          SolutionWidth<P::N, P::K>: Unsigned,
          Exp<U2, P::K>: Mul<Quot<Add1<CollisionBitLength<P::N, P::K>>, U8>>,
          Add1<CollisionBitLength<P::N, P::K>>: Div<U8>,
          CollisionBitLength<P::N, P::K>: Add<B1>,
          P::N: Div<Add1<P::K>>,
          P::K: Add<B1>,
          HashLength<P::N, P::K>: ArrayLength<u8>,
          Add1<P::K>: Mul<CollisionByteLength<P::N, P::K>>,
          CollisionBitLength<P::N, P::K>: Add<U7>,
          Sum<CollisionBitLength<P::N, P::K>, U7>: Div<U8>,
          T: Add<B1>,
          CollisionByteLength<P::N, P::K>: Mul<Add1<T>>,
          Prod<CollisionByteLength<P::N, P::K>, Add1<T>>: ArrayLength<u8>
{
    type HashLen = Prod<CollisionByteLength<P::N, P::K>, Add1<T>>;
    type Indicies = U1;

    fn is_valid(v: Vec<Node<Self::HashLen, Self::Indicies>>) -> bool {
        true
    }
}

#[test]
fn lol() {
    <(U200, U9) as Equihash>::is_valid(&[])
}