To build the project I mentioned in this topic I started learning about zk-SNARKs. One of the things I seem to understand is that the ECDSA signature scheme and the SHA-3 hash (formerly known as Keccak) don’t play well with zk-SNARKs because they result in massive circuits. IIUC, EdDSA with certain curves and the Poseidon hash fare much better in that regard, with circuits that could be hundreds of times smaller.
Hashing and verifying signatures are very common use cases in Solidity smartcontracts, but Solidity uses SHA-3 for hashes and AFAIK all Ethereum wallets are based on ECDSA. Does that mean that all Solidity smartcontracts are inherently hard to prove in zk-SNARKs? If so, how did Polygon zkEVM solve that problem? What zk-SNARK scheme does it use (Groth16 / PLONK / PLONKish / Halo2 / other) ?
No, Solidity contracts are not “inherently” impossible to SNARK—what’s expensive are the EVM primitives you happened to pick: KECCAK256 (opcode 0x20) and ECRECOVER (secp256k1 ECDSA).
In zk circuits, ECDSA-on-secp256k1 and Keccak, generally, blow up constraint counts: a Circom ECDSA verifier is ~1.5 M constraints (a ~200,000 implementation exists), while an EdDSA (baby-Jubjub) + Poseidon verifier is only a few thousand (~4.2k–10k), i.e. two orders of magnitude smaller.
Polygon zkEVM handles this by not changing Solidity, but by building custom gadgets/circuits for those ZK-unfriendly ops, batching them, and then proving the whole EVM execution with a multi-stage pipeline:
PIL/STARK circuits for opcode/state-machine correctness,
STARK recursion & aggregation using a PLONKish arithmetization with custom gates/lookups,
wrap the big STARK in a tiny SNARK (FFLONK) that’s verified on Ethereum via the pairing precompile.
The first one should be extremely widespread though, considering that all mappings use it. You can’t do much without Keccak256, you can’t even implement an ERC-20.
Yeah, you are right. But, most hash functions are not very zk-friendly, and it might take some time to get to the hardware stage that these hash functions become an easy task.