Public key vs Address handling

[PopcornPaws]

Description

We are going to need the public key of the signer which cannot be directly obtained from Metamask. However, using ethers public key recovery function, we can recover the public key from the signed message (digest) and the signature.

The recovered public key will be passed to the exponentiation proof (through a wasm interface) that proves that the signer is, in fact, the owner of the public key, and hence the address.

We are not going to need the public keys for the ring signature, only the addresses will suffice. This means that anybody can create a membership proof to one of the addresses in the ring, but they won't have a matching ECDSA signature proof alongside it.

[PopcornPaws]

At the core of the proof we are essentially using the public key (which is recovered from a signature). In the original implementation the ring contains public keys, thus the proof uses the public key for both the ECDSA signature zkp generation and the membership proof.

However, Balancy will provide rings with addresses in them, which means that we need to generate membership proofs using the address, not the public key. Unfortunately, there's no mathematical (elliptic curve) connection between the address and the public key because the address is simply the last 20 bytes of the public key's hash.

[PopcornPaws]

So the main problem is the following: since there's no algebraic connection between Ethereum addresses and public keys (only a hash function) it's not easy to prove that a given address belongs to a public key via algebraic methods, i.e. pedersen commitments.

However, we could use garbled circuits to prove in zero knowledge that a we have a commitment that is the hash of another commitment, which is exactly what we need to bridge the gap between an address and a public key.

The proposed method is thus given as:

• prover generates a commitment to their public key and their address as well
• prover uses the public key to generate the ECDSA proof
• prover uses the address to generate the membership proof in the ring provided by balancy
• prover generates a proof via a garbled circuit that binds together the public key commitment and the address commitment in zero knowledge
• verifier verifies the three proofs separately

[PopcornPaws]

Some useful papers on the topic:

• crypto stack exchange

Some useful crates:

• an implementation in Rust
• another implementation in Rust
• python implementation

Misc:

• someone was trying to implement a GC in a secure enclave

[PopcornPaws]

ZKBoo implementation in rust Keccak-f boolean circuit txt (?)

[PopcornPaws]

This is too complicated for the project and would definitely require SNARKs or boolean circuits to make it work.