search

hdevalence / ed25519consensus

Go Ed25519 suitable for use in consensus-critical contexts.
BSD 3-Clause "New" or "Revised" License
50 stars 11 forks source link

Use 2x faster SUPERCOP amd64-51-30k port #2

Closed lukechampine closed 3 years ago

lukechampine commented 3 years ago

Hi there! I work on Sia, which uses Ed25519 for all of its signatures. As a result of your post, we're considering switching to ed25519consensus in a future hardfork.

I was wondering if you're open to incorporating George Tankersley's port of amd64-51-30k to Go. For whatever reason, it's been stuck in review limbo for 2 years, which is a shame because it achieves ~2x faster verification than the current implementation. I checked it against your test vectors and it has the same pass/fail pattern as stdlib crypto/ed25519, which is reassuring. (It passes all the usual vectors too, of course.)

From what I can tell, integration would be pretty simple: just add the CofactorEqual and (*ProjectiveGroupElement).ToExtended functions to gtank's code. ed25519consensus.Verify shouldn't require any changes.

Another option would be to lobby for gtank's CL to be merged upstream; maybe @FiloSottile could help there? In any case, I suppose it would be irresponsible to use it in ed25519consensus without proper review from another crypto dev. 😅

FiloSottile commented 3 years ago

@gtank's implementation made its way into github.com/gtank/ristretto255, from where I extracted it into filippo.io/edwards25519 to serve ristretto255 and this package. It should be just a matter of porting this package to filippo.io/edwards25519 to get the speedup (and a properly maintained library rather than the internal guts of crypto/ed25519).

hdevalence commented 3 years ago

Yep! Using that package in this one was actually the plan -- I talked with @marbar3778 about doing that, but I've been busy with other work so I haven't written up a series of issues yet, sorry about that. I'll try to write up a plan in the next few days.

lukechampine commented 3 years ago

Ah, excellent. I've been using those "internal guts" in one of my own packages as well, so I'll definitely switch to filippo.io/edwards25519.

Do you expect that the speedup will eventually be merged into crypto/ed25519, though? Seems strange that it wouldn't be, unless there's a weird licensing issue or something.

gtank commented 3 years ago

Author here. There's no licensing issue as far as I know. For the record, I think the review limbo is a matter of reviewer bandwidth and occasionally shifting ideas about what should live in the crypto/ tree. The way would be clear if @FiloSottile wants to upstream it, but I'm not if sure it's worth reworking that particular CL now since we've refined this code's layout and API in subsequent work over the years. I guess if it's still drop-in compatible (unsure), that's as compelling as it was two or three years ago. If not, our collective intent at the moment is for filippo.io/edwards25519 to be the site of future improvements.

lukechampine commented 3 years ago

I took at a stab at the port myself, but got stuck. I think there are two areas where a change to filippo.io/edwards25519 might be required:

1) In some places (e.g. the expanded secret key in Sign), we need to cast 32 bytes to a Scalar directly rather than using FromCanonicalBytes, but there's no way to do that. 2) I couldn't figure out how to port GeDoubleScalarMultVartime. I tried VarTimeDoubleScalarBaseMult but that produced different results.

Also, not a huge deal, but since scReduce is not exported, I had to call Multiply and Add separately in Sign.

Happy to submit PRs as needed!

FiloSottile commented 3 years ago

Ok, finished a deep cleanup pass, and tagged v1.0.0-alpha.1. There are missing APIs, but the ones that are there might be stable.

  1. In some places (e.g. the expanded secret key in Sign), we need to cast 32 bytes to a Scalar directly rather than using FromCanonicalBytes, but there's no way to do that.

Technically you could have done it with FromUniformBytes but I don't want anyone to do that, so I made SetBytesWithClamping. (I changed a few names, sorry!)

  1. I couldn't figure out how to port GeDoubleScalarMultVartime. I tried VarTimeDoubleScalarBaseMult but that produced different results.

Ouch, open an issue?

Also, not a huge deal, but since scReduce is not exported, I had to call Multiply and Add separately in Sign.

Do you mean scMulAdd? I should add MultiplyAdd, yeah.

lukechampine commented 3 years ago

Thanks! Maybe I'm just using VarTimeDoubleScalarBaseMult wrong, but it definitely produces different output for the same inputs. I've filed an issue with a repro.

I don't think (*ExtendedGroupElement).FromBytes or (*ProjectiveGroupElement).ToBytes can be ported without access to FieldElement, so that'll have to be exposed somewhere; likely a separate package, from the sound of https://github.com/FiloSottile/edwards25519/commit/90c35a7f43280c4802b9238ff3b17b99dbfd5b96.

FiloSottile commented 3 years ago

Thank you!

(*Point).Bytes and (*Point).SetBytes are definitely missing and I'm working on them today. What will end up in a separate package is FieldElement and ExtendedCoordinates, but those shouldn't be necessary for Ed25519 implementations. (Correct me if I'm wrong!)

FiloSottile commented 3 years ago

I landed encoding functions in v1.0.0-alpha.2 and I think it should now have everything necessary to implement this package!

https://pkg.go.dev/filippo.io/edwards25519@v1.0.0-alpha.2