What would be a Message-Recovery variant of the Ed25519 signature scheme?
Ed25519-MR should be simple to use, fast, with a strong security argument, and striving to stay out of the patent minefield, as the original does.
[Ed25519] is a signature scheme with appendix: it adds a signature of 512 bits to the message that it signs, for 128-bit conjectured security. A Message-Recovery variant would embed some of the signed message into the signature, with that so-called recoverable part of the message a byproduct of successful verification, that needs not be explicitly transmitted. We wish to minimize the overall signed message size.
Signatures schemes with message recovery of the Elliptic Curve Discrete Logarithm family have been proposed, patented and standardized (see bibliography), including ECNR (Nyberg-Rueppel), ECMR (Miyaji), ECAO (Abe-Okamoto), ECPV (Pintsov-Vanstone, aka ECPVS, PVSSR, ECSSR-PV), ECKNR (KCDSA/Nyberg-Rueppel) per their name in [ISO 9796-3].
Addition: I'm puzzled at the achievable gain over a signature scheme with appendix. My reading of [PV1999] and [AO1999] is that for $b$-bit security and arbitrary message, ECPV and ECAO embed $b$ bits into a $4b$-bit signature; when my limited understanding of other schemes is that some aim at embedding $2b$ bits.
Bibliography on (possibly Elliptic Curve) Discrete Logarithm Signatures with Message Recovery.
[NR1993]: Kaisa Nyberg and Rainer A. Rueppel, A new signature scheme based on the DSA giving message recovery, in proceedings of CCS 1993;
[NR1994]: id., Message recovery for signature schemes based on the Discrete Logarithm problem, in proceedings of EuroCrypt 1994;
[US'725]: Rainer A. Rueppel and Kaisa Nyberg, Digital signature method and key agreement method, US 5,600,725.
[M1995a] and [M1995b]: Atsuko Miyaji, Weakness in message recovery signature schemes based on discrete logarithm problems (continued), in IEICE TF;
[Mi1996a]: id., Signature equation suitable for message recovery schemes in IEICE TF;
[Mi1996b]: id., A message recovery signature scheme equivalent to DSA over elliptic curves, in proceedings of AsiaCrypt 1996;
[Mi1997]: id., Another countermeasure to forgeries over message recovery signature in IEICE TF;
[JP'357]: Miyaji Mitsuko, Message decoding type signature system, JP Pub.# H09-034357 ;
[JP'492]: id., Signature system, JP Pub.# H09-160492 .
[AO1999]: Masayuki Abe and Tatsuaki Okamoto, A Signature Scheme with Message Recovery as Secure as Discrete Logarithm in proceedings of AsiaCrypt 1999;
[AO2001] id., id., in IEICE TF;
[JP'178]: id., Message recovery type signature system and program storage medium therefor, JP Pub.# 2001-134178 .
[PV1999]: Leon A. Pintsov and Scott A. Vanstone, Postal Revenue Collection in the Digital Age, in proceedings of FC 2000;
[PV2000]: id., submissions to IEEE P1363a, including [PVSSR-D2] and [PVSSR-D3].
[BJ2001]: Daniel R. L. Brown, Don B. Johnson, Formal Security Proofs for a Signature Scheme with Partial Message Recovery, in proceedings of CT-RSA 2001; drafts: [BJ2000-02], [BJ2000-06].
[P1363a]: IEEE Standard 1363a-2004 - Specifications for Public-Key Cryptography - Amendment 1: Additional Techniques.
[ISO ISO9796-3]: ISO/IEC 9796-3:2006, Information technology — Security techniques — Digital signature schemes giving message recovery — Part 3: Discrete logarithm based mechanisms. Free previews in HTML and PDF.
[X9.92-1]: ANS X9.92-1-2009 (reaffirmed 2017, reportedly without change). Public Key Cryptography for the Financial Services Industry - Digital Signature Algorithms Giving Partial Message Recovery - Part 1: Elliptic Curve Pintsov-Vanstone Signatures (ECPVS).
[Ed25519]: Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, Bo-Yin Yang, High-speed high-security signatures, in proceedings of CHES 2011.