Implement powers of alpha trick to compare strings

[mitschabaude]

found in the zk-email-verify repo:

• absorb both strings (cheap, with Poseidon on 62 chars at a time) into "challenge" $\alpha$
  • note: it's ok to hash unconstrained pieces of the strings here as well, since we don't need the hash to be unique, it just needs to act as a sponge which commits the prover to this string
• define $C(s) = s[0] + \alpha s[1] + ... + \alpha^{n-1} s[n-1]$ (cheap, ~3N double generic gates)
• checking that $C(s) == C(t)$ proves that the strings $s$, $t$ are equal

How sound is this?

with this, the cost of operations like assertContains(), concat() is O(N) with a smallish constant, compared to

• O(N^2) for naive techniques
• 2N hashes when doing an entire hash per char, which is 22N Poseidon gates in Kimchi