Short version: we’re considering a design that would require transactions to compute ~30 poseidon hashes on a 254-bit field in StarkNet. Long term we could potentially have 10,000+ of these transactions a day. Would this design be prohibitively expensive, compute-wise?
Long version
Hey there! We’re working on Zorro, a proof-of-personhood protocol hosted on StarkNet. One important property we want is to (1) verify users’ identity publicly, while (2) not linking their on-chain activity to their specific identity.
To accomplish that, we’re planning on maintaining a Merkle tree of users’ identities on-chain within StarkNet. To prove to apps that they’re real humans, users can publish a zk-SNARK containing a Merkle proof demonstrating that their identity is in the tree.
There aren’t many zk-SNARK implementations that can generate proofs efficiently in a web browser. So tentatively, we’re using circomlib+snarkjs to generate groth16 proofs over the bn254 curve (still open to replacing any of these dependencies with equivalents that might be a better fit). We’ve also tentatively chosen the poseidon hash function to construct our tree since it’s efficient to compute within a SNARK and has an existing circom implementation.
One annoyance of this design is that bn254 uses a 254-bit prime field, whereas the StarkNet prime field is only 252 bits. Our tentative plan is to get around this by using 2-felt structs to represent all intermediate values while calculating the poseidon hashes in our Merkle tree, and manually performing the $mod p$ operations after each step with the bn254 prime.
We’re worried that the combination of (a) modular operations on a larger prime field and (b) writing our hash function in userspace, instead of using the (maybe more optimized?) Pedersen builtin might make this design impractically expensive. Is this something we should be worried about? Any changes to the design that might make it more tractable?
Thanks!