Add EdDSA verification to standard library

[kevaundray]

Problem

Signature verification is an important building block for many protocols. The most popular in this domain being EcDSA. One problem with EcDSA is that it is not deterministic and so it is not suitable for usecases where one would want to use the signature as a nullifier.

Proposed solution

EdDSA is a suitable alternative for this, moreover it is the alternative is the circomlib that many folks who are using circom will default to.

A link to EdDSA is here: https://github.com/iden3/circomlib/blob/master/circuits/eddsaposeidon.circom

Since we already have poseidon and Twisted edwards curve logic in our stdlib, we can implement the above by composing those two algorithms like in the circom library.

Alternatives considered

No response

Additional context

No response

Submission Checklist

• Once I hit submit, I will assign this issue to the Project Board with the appropriate tags.

[joss-aztec]

Circom's implementation multiples various expressions by 8. Any idea why this was necessary?

S*8*G = (R*8) + H((R*8), A, m) * 8 * A

Not all implementations seem to do this. E.g.
https://github.com/dusk-network/EdDSA/blob/master/src/lib.rs#L160

[kevaundray]

Because Edwards curves has a cofactor of 8, so we need to multiply by 8 to ensure that the point is in the prime order subgroup

[joss-aztec]

So if I understand, any group element in this expression should be multiplied by 8 to map it into the sub group. Why isn't the pub key also multiplied by 8 before it is hashed?

[kevaundray]

So if I understand, any group element in this expression should be multiplied by 8 to map it into the sub group. Why isn't the pub key also multiplied by 8 before it is hashed?

The rationale should be in the specs -- For now, lets just re-implement this in Noir so that it is interopable.

[joss-aztec]

This work is being parked due to the following blockers:

• The circuit is huge
  • A single stdlib ec mul currently costs 240K constraints (two muls are required)
  • Our solution needs to be ~24K
• We still need a working solution for checking the signature is less than subgroup order
  • Calling x.to_le_bytes(32) hits the compiler error:

The application panicked (crashed).
Message:  assertion failed: max < FieldElement::modulus()
Location: crates/noirc_evaluator/src/ssa/acir_gen/constraints.rs:414

[joss-aztec]

Broken impl for reference: #1136

[shuklaayush]

I was able to reduce the circuit size of a single ec mul to 20k. Most of the constraints were coming from the custom to_bits implementation. I replaced it with the builtin to_le_bits

Here are the changes:
master...shuklaayush:noir:fix/eddsa

Had to fix some bugs along the way in the to_bits and to_bytes opcodes to make them work properly for elements that don't fit in u128 (see master...shuklaayush:noir:fix/to-bits)

Let me know what's the best way to get this merged. Should I just open a PR?

[kevaundray]

I was able to reduce the circuit size of a single ec mul to 20k. Most of the constraints were coming from the custom to_bits implementation. I replaced it with the builtin to_le_bits

Here are the changes:

master...shuklaayush:noir:fix/eddsa

Had to fix some bugs along the way in the to_bits and to_bytes opcodes to make them work properly for elements that don't fit in u128 (see master...shuklaayush:noir:fix/to-bits)

Let me know what's the best way to get this merged. Should I just open a PR?

This is amazing. A PR with the fix would be great, @guipublic will take a look next week.