Add Proof of Work

[tsunrise]

Looks that arkworks does not have the implementation of proof of work (even the simplest one). We can probably add one here (use the one similar to libiop? )

We can use existing CRH trait to make it generic. Also, we will need to write the constraints. (For now all CRH has its constraints written, so we just need to wrap it.)

"one line algo"

For a message M and difficulty k, the prover will bruteforce a nonce N such that the last k bits of the output of H(M || N) are zero.

[Pratyush]

The constraints version is fairly easy, right? Just check the output of H(M||N) contains k trailing zeros.

[tsunrise]

The constraints version is fairly easy, right? Just check the output of H(M||N) contains k trailing zeros.

Yes, should be. Just some constraints for CRH + constraints to enforce k trailing zeros

[Pratyush]

@tsunrise, @alexchmit pointed out that for PoW it does not suffice to use a CRH. Rather we have to use something that is RO like. I think for this we would have to create a "Cryptographic Hash Function" primitive that achieves these properties. Then you can instantiate it with the existing Blake2s and Poseidon implementations. I imagine the interface is going to be fairly simple:

pub trait CryptoHash {
    type Parameters;
    type Input;
    type Output;
    fn setup(&mut rng) -> Self::Parameters;
    fn hash(params: &Self::Parameters, input: &Self::Input) -> Self::Output;
}

Similarly for the gadget version.

[tsunrise]

Got it, will send a PR here later. Thanks!