Reduce the number of PublicKey decompressions

[coltfred]

When interacting with other Ed25519 libraries one might need to be able to bring in a Public Key which is in x + y form ([u8,64]). One might also want to export the x + y form.

Neither of these use cases is currently supported by ed25519-dalek, which can be a deal breaker for some users. Is there something I'm missing that would allow the export of the public key in expanded form? Is there interest in adding this kind of support if it's not already possible?

[ValarDragon]

Allowing this library to take in the uncompressed public key would be super useful. A project I'm working on has a use case for using the uncompressed version. (Verifying many signatures from the same pubkey, might as well cache the decompression and avoid that performance hit)

[isislovecruft]

Hi @coltfred,

When interacting with other Ed25519 libraries one might need to be able to bring in a Public Key which is in x + y form ([u8,64]). One might also want to export the x + y form.

Out of curiosity, which library is doing that?

Apologies if you're already familiar with this background: The (x, y) form of a point on the curve is referred to as being in affine coordinates. Computation of the group law over affine coordinates is never as fast as computing it over various other forms; for points on Edwards curves the fastest known form for most use cases is extended, twisted Edwards coordinates which are in ℙ³ as (X : Y : Z : T). Our curve library does use some affine coordinates, specifically those that are attributable to Niels Duif and of the form (y+x, y-x, xyd²), however those are specialised to optimise precomputation for basepoint multiplications. Hence, my first complaint against the library you're using is that the affine coordinates they are using are inefficient.

My second complaint against that library is, given the affine y-coordinate (note that y is not the same as the projective Y-coordinate), one may trivially solve for x using the affine curve equation, ax² + y² = 1 + dx²y², so inclusion of the x coordinate is redundant and a waste of bytes.

Anyway, hope that helps. If you'd like further reading on the internals of point representations in curve25519-dalek they are documented here.

[ValarDragon]

Would accepting pubkeys already in Edwards form be reasonable? Or would that be too much API bloat?

EDIT: Never mind, this library is doing the much smarter thing of just having a public key object to avoid repeated decompressions, from its design. (My referrence was golang/crypto/ed25519, should have read this API before commenting, apologies)

[isislovecruft]

Hi @ValarDragon,

Allowing this library to take in the uncompressed public key would be super useful.

I might be mistaken in my understanding of what you and @coltfred are asking for, but the uncompressed form in this case would be an extended, twisted Edwards point (as described above) in the form (X : Y : Z : T), whereas I believe @coltfred was asking for the point in represented in affine coordinates.

A project I'm working on has a use case for using the uncompressed version. (Verifying many signatures from the same pubkey, might as well cache the decompression and avoid that performance hit)

On the surface, one would think this would be a good idea, until realising that the verification routine must compute H(R || A || M) where A is the compressed form of the public key (later in the verification routine the uncompressed form is used arithmetically). Therefore, if I changed the code to take an uncompressed public key, it would need to do a point compression. Point compression and decompression cost the same amount of cycles, so this doesn't save us anything.

[ValarDragon]

My bad, your totally right. I had also originally misread the issue and hurriedly replied as well.

What I intended to write was: could we cache both the compressed and internal representation of the pubkey curve point. e.g. cache the computation on lines:
https://github.com/dalek-cryptography/ed25519-dalek/blob/master/src/ed25519.rs#L813-L816.
From what I can tell, thats currently just using the internal edwards representation, and recomputes the compressed the point every time.

The intent of this would be a space / time trade-off, if your using the same pubkey repeatedly, this becomes a worthwhile trade imo.

[coltfred]

@isislovecruft To my embarrassment I had mixed up the value that was 64 bytes in my other library. I'm so sorry about the issue.

[isislovecruft]

@coltfred No worries at all! Did you figure out what it was or if there was a way to be compatible?

[isislovecruft]

@ValarDragon Aha, I see what you're saying. Sorry for misunderstanding! I'm wasn't sure much much noticeably faster it would be, but I tried it out since it was ten minutes to write the code to try it, if you want to benchmark it on the architecture(s) with the batch sizes you're using to see the tradeoffs. The results using the normal verify_batch() function with a Vec<PublicKey> (of the same key) are in the "Ed25519 batch signature verification with the same key" results, whereas with the new verify_batch_from_same_key() function which only takes one PublicKey and decompresses once are in the "Ed25519 batch signature verification with the same key cached" results.

On an i9-7800X using the avx2 backend, for each batch size below, the percent improvement of the new function is:

batch size	% improvement
4	-7.59%
8	-14.83%
16	-18.09%
32	-25.35%
64	-21.15%
96	-21.26%
128	-21.71%
256	-18.49%

If it's something you'll use, I'm happy to merge it! (What are you doing with so many signatures created with the same key, if you don't mind my asking?)

[ValarDragon]

Thanks for writing this, it would be awesome to have! I can easily optimize the batch size around the benchmarks. The idea is for a Proof of Stake blockchain (namely Tendermint), we have validators signing every block. If someone is trying to sync to download the entire chain, the bottleneck assuming sufficient bandwidth is verifying tons of signatures, which are from this same set of 100 people. (Especially so for light clients, who basically just download the signatures and a couple of hashes)

So instead of verifying signatures block by block, we could have them download the block, and then verify a batch of the given validators signatures. (Or alternatively verifying a batch of all 100 per block at once) We could cache the compressed and internal formats of the pubkey in that setting as well. It will probably be awhile before we integrate this (currently we are using agl's golang ed25519 library, we'll have to use cgo to use the rust api), but my hope is to switch to this library soon. I do think this is something we would use though!

I benchmarked with an avx2 backend as well on an i7-7700, the benchmarks are essentially in the same ratio as on your system.

As an aside, thanks for writing such well documented batch verification code in the main dalek repo! I was previously under the impression that DJB's suggestion in the ed25519 paper with heaps was the fastest way without switching to Pippenger's, which seemed slightly odd.

[ValarDragon]

This may be more re-usable for other projects as well if there was a "cached pubkey" struct (or something to that extent) which you can batchverify, and normal verify with. The point of such a struct would be to store both the edwards point and compressed point. Then it would be easier to batch verify signatures from multiple cached pubkeys together. Additionally you could single verify on a single already-cached pubkey a bit faster than you could otherwise.

Doing that cleanly though may require a pubkey trait, I'm unsure if rust incurs any performance overhead due to do that though. (I'm still fairly new to rust)

[hdevalence]

Since the PublicKey's CompressedEdwardsY is private to the crate, another option would be for the PublicKey to hold an EdwardsPoint and perform decompression during construction. This gives the speedup transparently and seems simpler than introducing yet another Ed25519 key variant.

[isislovecruft]

I believe this should be implemented by #61 and #62, which transparently caches the decompressed PublicKey point.

Potential remaining work to be done is to implement a generalised interface to verification which takes e.g. I: IntoIterator, I::Item: PublicKey, J: IntoIterator, J::Item: Signature, K: IntoIterator, K::Item: Vec<u8>, which would allow you to pass ::core::iter::once(my_public_key) and lazily iterate over the same pre-cached PublicKey decompressed point.