Including additional characteristics of the preimage in the the proof

[zmanian]

How difficult is it in the current construction to prove additional characteristics about the preimage of the hash in additional to the hash output?

I.e. I want to to prove that the message hashes to x and the message does not contain the letter a.

It seems like should be possible with the bitwise comparisons in the DSL.

[jancarlsson]

I like this idea. You want an 8 bit character type for plaintext (hash preimage). The EDSL can do this using shift and masking. This is just terrible for the applications programmer. Let me try it and see what makes sense. I may have to extend the EDSL. Internally, the identity of each bit is preserved in the circuit. There are no technical obstacles to exposing bits in other ways beyond the current EDSL types. I've kind of anticipated this happening although for other reasons.

[zmanian]

I'm pleased this interests you. I'm interested in applications other kinds of privacy preserving proofs than the zerocash pour function.

We could use this to implement weaker versions of Greg Maxwell's zk contingent payment schemes if you don't mind revealing the hash preimage at the end of the tx. https://en.bitcoin.it/wiki/Zero_Knowledge_Contingent_Payment

The full version would require a zk AES implementation.

[jancarlsson]

The test_sha example supports pre-image constraints now. Each byte in the pre-image can be constrained to equal or not-equal a value. The output message digest can also be specified. This supports the use case "message hashes to x and the message does not contain the letter a". There is an example in the README.

You have identified a major omission. Besides the example you identified, zero knowledge symmetric decryption allows search of ciphertext (without resorting to infeasible FHE). I agree that a zero knowledge AES implementation is important.

[jancarlsson]

There is a zero knowledge AES implementation now. The test_aes example in the README shows roundtrip encryption/decryption for AES-128, AES-192, and AES-256 using Barreto-Naehrig and Edwards elliptic curve pairings. I have not implemented any block cipher modes, only the specification in NIST FIPS PUB 197.

[zmanian]

I'm just in the process of digesting and exposing functionality from the preimage proofs.

They work exactly how I imagined they would. Amazing work!

[jancarlsson]

Would recovering multiple bits from the "same" proof be useful? A symmetric block cipher like AES with zero knowledge proofs implies a construction equivalent to FHE in the limit. Without changing any math (so security is not changed), I believe there is a way to color the circuit and re-use the pieces across multiple keys and proofs. This allows a ZKP per bit at much lower cost if the circuits for each mostly "overlap".

There are other problems also demanding attention so I am trying to get a sense of priorities. This is also why there is no documentation except for the README file. Building out functionality is more important in my view than documentation, although this sentiment may be misguided.

[jancarlsson]

The original issue is addressed. I am closing this issue. Thank you very much for asking about it.

[zmanian]

Thanks for your response on this. Deeply appreciated.

I haven't haven't much time to work on my proof of concept. But I'm intending too.

I've been mentioning how great your work is to Zooko and his Zerocash effort. :-)