Support Keccak-256 about plonky2 HOT 4 CLOSED

It might also be neat to support blake3, which winterfell uses, since it's so fast. I'm not sure we'd have a concrete use for it ourselves, just if someone very fast proofs that didn't need to be recursion-friendly or Ethereum-friendly.

from plonky2.

I was thinking we could have a hash trait like PlonkyHash, for hashes that plonky2 itself supports, but not necessarily in circuits. And then another one like PlonkyCircuitPermutation which can be used in circuits, and is specifically a permutation, so we can do sponges/duplexes, e.g. in Challenger. add_recursive_verifier could take <InnerHash: PlonkyCircuitPermutation> as a parameter.

I experimented a bit with <C: GenericConfig> a bit. I was hoping to have something like

pub trait GenericConfig where [(); { Self::D }]: {
    type F: RichField;
    const D: usize;
    type FE: FieldExtension<{ Self::D }, BaseField = Self::F>;
    type Hash: PlonkyHash;
}

(This is just a start. We could potentially move more fields from CircuitConfig into this new config type later, especially if we notice performance reasons, like allowing certain code to use arrays instead of Vecs.)

so that most definitions in our code base could have a single <C: GenericConfig> generic. But this doesn't work; it gives "cycle detected". We can instead do

pub trait GenericConfig<const D: usize> {
    type F: RichField;
    type FE: FieldExtension<D, BaseField = Self::F>;
    type Hash: PlonkyHash;
}

Then we'd have <C: GenericConfig<D>, const D: usize> on many definitions throughout our codebase. I suppose that's a bit better than the current <F: RichField + Extendable<D>, const D: usize>, although it's also worse in a way since Fs would be replaced with C::Fs.

from plonky2.

Good idea. Would we make PlonkyHash generic over the input/output types? Something like:

trait PlonkyHash<T> {
     fn compress(x: T, y: T) -> T;
}

so that we could have T = [F; 4] or [F; 3] for algebraic hashes and T = [u8; 32] or [u8;25] for Sha3/Blake3?

from plonky2.

Alternatively, maybe we could configure hashing in CircuitConfig (i.e. without using generics), and have the branching for various hashes occur at a high level to avoid the performance hit. E.g. maybe MerkleTree:new could take a hash config parameter, then branch into hash-specific methods like MerkleTree:new_with_poseidon (or MerkleTree:new_with_hash::<PoseidonHash>()).

from plonky2.