Transaction signature verification

[han0110]

In Tx circuit, we need to verify each transaction has valid signature.

The following should be described as part of specs/circuits/tx.md:

• How it RLP encodes transaction and verify hash is correct using circuit keccak256 by lookup
• How it recovers address from signature

[ed255]

An initial version of the tx circuit is now specified at https://github.com/appliedzkp/zkevm-specs/blob/master/specs/transactions-proof.md

* How it RLP encodes transaction and verify hash is correct using circuit `keccak256` by lookup

For the first iteration we have made a shortcut to simplify the design in which we skip the RLP encoding of the transaction and the hashing of the RLP encoded transaction. Instead we ask the verifier to calculate the hash of the transaction and pass it to the circuit via the tx table.

Future iteration TODO:

• [ ] Calculate RLP encoding of the transaction and accumulate it in an RLC encoded value.
• [ ] Perform a keccak lookup to get the transaction hash (to be used for signature verification).

* How it recovers address from signature

For the first iteration we integrate an ECDSA verification chip in the tx circuit. The address recovery is done by the prover, and the circuit verifies that the address corresponds to a public key for which the signature and hash verify.

Future iteration TODO:

• [ ] Specify an ECDSA verification circuit with a lookup table to check signature verifications.
• [ ] From the tx circuit, verify signatures by doing lookups to the ECDSA table.