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

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

@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.

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