This is a proposal to halve the current Tendermint commit size when using Ed25519, with no changes required to hardware. I expect the verifier time to be notably improved.

The high level idea is we use Ed25519 batch verification algorithm, where the verifier randomness is obtained from hashing the entire commit. Ed25519 signatures are composed of two equal sized parts (R, s). Using batch verification, the verifier needs {R_i}_{i in validators}, but only needs the random linear combination of all s_i's. Thus, the commit will send all R_i, but only the single aggregated s. (This still must be proven sound)

Let G be the generator of the Ed25519 group, z_i be the ith random coefficient, P_i be the ith validators pubkey, m_i is the message which is being signed, (R_i, s_i) is the i-th Ed25519 signature and h_i = H(R_i, P_i, m_i). (Capitals are curve points, lower-case letters are scalars) The Ed25519 batch-verification equation that must be checked by the verifier is:

(-\sum_{i} z_i s_i)G + (\sum_{i} z_i R_i) + (\sum_{i} z_i h_i * P_i) = 0

One way to check the equation is to give the verifier (-\sum_{i} z_i s_i), and all of the R_i.

The proposed procedure is:

1. The next proposer aggregates all Ed25519 signatures (R_i, s_i) as before
2. The next proposer builds a pseudo-commit that contains all R_i, and timestamps_i for all validators. (Perhaps in a merkle tree, see optimization 1)
3. The proposer gets random coefficients {z_i} from H(pseudo-commit), where each z_i is 128 bits. (The hash can be ran in XOF mode)
4. The proposer builds the commit as {(-\sum_{i} z_i s_i), pseudo-commit}
5. Broadcast as before

To verify this, as either a full node or as a lite-client:

1. parse the commit as {(-\sum_{i} z_i s_i), pseudo-commit}
2. get random coefficients {z_i} from H(pseudo-commit)
3. Check the batch-verification equation

It remains to show that checking the equation given (-\sum_{i} z_i s_i) instead of all s_i is secure. I do not currently have a proof of it, but I have an impression that this is true. (EDIT: See following comment) The reason that it feels true is that we are taking a random linear combination of the relevant curve points we care about (which already depend on the public key and the message), and we are essentially asking for the discrete logarithm of the random linear combination. So if you didn't know any constituent signature, it seems unlikely you could know the resulting discrete logarithm. Random linear combinations of this sort typically have soundness 1/(Randomness sample size), and we choose each z_i from a set of size 2^128. Since h_i has key-prefixing and is therefore distinct for every pubkey, this builds some confidence against being able to do BLS-style rogue public key attacks.

Additional optimizations:

If the verifier wants to take the optimization where they only verify a particular subset D of size (2/3 weight) of the validators who signed the prior block, then we've already assumed a single round of communication from the verifier to their prover where they communicated D. In this model, the verifier can still achieve this same optimization. We redefine the commit to now be {(-\sum_{i} z_i s_i), MT of pseudo-commit}. The verifier receives {commit, {R_i, T_i}_{i \in D}, multi-membership proof for {R_i, T_i}_{i \in D} in pseudo-commit, (-\sum_{i \in D} z'_i s_i)}. The coefficients z'_i are all obtained from getting sufficient bytes from H({R_i, T_i}_{i \in D}).
Essentially the verifiers receives a commitment to the commit (essentially all signatures in a merkle tree), and is sent a multi-membership proof of all the signatures of interest. The random-coefficient optimization is the same, but is only for the received signatures, and so the size of the leafs is still halved.