Signature schemes for efficient and friendly zk proof verification

[damiannolan]

Problem to solve

The sequencer currently uses ed25519 for signing of Header and Data types before publishing SignedHeader and SignedData to the data availability layer (e.g. celestia).

Ed25519 is generally considered less zk friendly due to complex curve arithmetic and also signature algorithm complexity.

Proposed solution or feature

Determine a more efficient and zk friendly signature scheme to use, and employ this for signing Headers and Data blobs.

I briefly looked at BLS12-381 and Schnorr signatures, but will defer to others who have stronger cryptography.

[Manav-Aggarwal]

Worth noting that this signature verification can be entirely skipped in the future in favor of the sequencer electing to submit authored blobs introduced in https://github.com/celestiaorg/CIPs/blob/main/cips/cip-021.md

With this, a prover just needs to do is verify the signer for a blob is the same as the sequencer before even attempting to deserialize the blob, making proving even more efficient.

[damiannolan]

Agreed. The sequencer would need to put the same celestia address into the Blob signer as the account who's paying and signing for the PayForBlobs.

In that approach the blob data is not actually signed over by the priv key, producing a signature. We rely on the security of the signature over the PFB transaction, and the checks in Prepare/ProcessProposal ensuring the blob signer is equal to the PFB signer. https://github.com/celestiaorg/celestia-app/blob/main/x/blob/types/blob_tx.go#L80-L86