Batch verification of ed25519 signatures

[webmaster128]

Part of #751

Should be implemented via ed25519_zebra::batch. There you see we only get a single boolean result. And it turns out each item in the batch can be different. So the implementation looks something like

fn ed25519_batch_verify(message: &[&[u8]], pubkeys: &[&[u8]], signatures: &[&[u8]]) -> bool

Is there a need to optimize for a batch that all share the same message?

[webmaster128]

@ethanfrey @joe-bowman could you elaborate on your intended use case for bach verify, especially the range of the inputs (count and size)?

I still wonder:

Is there a need to optimize for a batch that all share the same message?

Ed25519 batch verification does not require the same message. If we keep it completely open, we need to allocate/copy m*n data in the contract and read that from the VM (where m is the message length (no pre-hashing applied) and n is the number of signatures).

[ethanfrey]

I will defer to Joe on this, but I think when validations sign block headers, they may use the same message. Not fully sure there

[maurolacy]

We can easily support two variants here:

• The messages, signatures and public key arrays are all of the same (greater than zero) length.
• One message in the messages array, and signatures and public key arrays of the same (greater than one) length.

All other combinations result in an error (including empty arrays, i. e. verifying nothing equals false / error).

[ethanfrey]

Agree with this. There are no other variants I can think of.

[maurolacy]

There's one more potential use case we can support:

• One pubkey in the pubkeys array, and multiple (more than one, same number of) messages and signatures.

This is for verifying multiple messages signed by a single user / with the same private key.

To be clear, we already support that conventionally: just send the same pubkey multiple times. It would be nice to support sending the pubkey only once, instead of multiple times. In the same way we support sending messages only once.

By the way, this case is the one in which batch verification provides a (algorithmic) performance improvement over multiple single verifications. See https://github.com/ZcashFoundation/ed25519-zebra/blob/main/src/batch.rs#L167L172.

[webmaster128]

Looking at the graph in https://docs.rs/ed25519-zebra/2.2.0/ed25519_zebra/batch/index.html it seems like batching saves more than 50% even when all pubkeys are distinct (blue vs. red line). Then if only one pubkey is used, you get another 2x improvement (green line vs. red line). So I wonder what the usual method is (in the comment).

[maurolacy]

You're right. Funny that the graph contradicts the text to a certain extent.

[webmaster128]

Given the state of this discussion, I would avoid any kind of optimizations that we need to build and maintain. Instead, let's focus on the most general API and use that to gather experience of its value and limitations.