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 to hash to be unique, it just needs to acts 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? My intuition says that it might become questionable if both strings can be chosen freely, but the typical situation is where one of the strings is tied to something else, like its sha2 hash in the case of email.

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