Schnorr half-aggregation by default, opt-in non-aggregation

[adambor]

In the paper we discussed adaptor signatures (required for PTLCs) and their incompatibility with schnorr half-aggregation, coming into conclusion that half-aggregation cannot be used.

But, most transactions will probably not be PTLCs, so we can do schnorr half-aggregation by default and let people opt-in for non-aggregated signatures by a version bit in a transaction.

We can limit total amount of non-aggregated signatures per block to e.g. 2^17 (~130k), to make sure those transactions have to pay a higher fees (as there is more limited space for them).

This way we will be able to cut ephemeral data size from 56MB to (in the worst case scenario) 31.5MB - almost 45% reduction!

[adambor]

Further thinking about this, the only reason we needed tx ids to be signatures is for PTLCs.

So for transactions which don't require signature adaptors we can keep using just a hash of transaction, instead of schnorr half-aggregated signature (as all signatures are proven to be verified inside the STARK proof anyway).

I am no cryptographer but I think for those txIds we can use just 16 bytes - providing 2^128 bits of security, I believe we don't need to care about collision resistance (which would be just 2^64), since even if someone finds another pre-image it still HAS to be a hash of a valid transaction - which it most probably won't be. Alternatively we can also pad the txIds to 32 bytes, with 16 bytes coming from transaction hash and another 16 bytes coming from block's pseudo-randomness - this is equivalent to password salting, so should provide additional resistance to multi-target attack.

If this is possible it would further cut the ephemeral data size to 21MB in the worst case (2^17 PTLC txns - 7MB, and 2^20 - 2^17 normal txns - 14MB) and in best case to 16MB (all txns normal).

EDIT: Those 16 bytes for the txIds are coming from SHA256 (or other more STARK friendly hash function like MiMC or Poseidon), by taking first 16 bytes of the full hash. Signatures for the transactions are still computed over full 32-byte hash.

EDIT2: Okay, realized that using 16 bytes is definitely not enough and collision resistance (2^64) is a real issue - which would allow double commitment by a sophisticated attacker (committing to 2 different state transition in the same transaction and being able send one to party 1 and another one to party 2, leading to double-spending of client-side-validated state). But still I believe we don't need full 32 bytes of the hash function, maybe 20 bytes is enough (recall that this is what is used for P2WKH addresses), and this could especially be the case for arithmetic based hash function (which will be used for Abraxas because of the STARK proof). Arithmetic based hash functions are several times slower to compute than binary hash functions like sha256 (but the former is much cheaper to verify inside a STARK proof).

So with 20 bytes per normal txns the ephemeral data size looks as follows: 24.5MB in the worst case (2^17 PTLC txns - 7MB, and 2^20 - 2^17 normal txns - 17.5MB) 20MB in the best case (all txns normal).

[adambor]

So upon further inspection of schnorr signatures I realized that the only part you care about for adaptor signatures is the tweaked s value, recall that the signature is a pair (R, s), where R is an elliptic curve point (encoded as Y only coordinate) and s is a scalar. We can therefore drop the R point from the ephemeral data (the signature is properly verified with (R, s) inside the STARK proof, so we don't need it for verification again), and leave only the scalar s - with this the ephemeral data per PTLC tx is 28 bytes.

In such a case there is little point anymore to separate PTLC and non-PTLC transactions, since both would be almost the same size, this leads to ephemeral data size per block of 28MB and all the txns can be PTLC (so you have enough space to settle 1M stuck lightning PTLCs in a single block).

[cryptoquick]

That's incredible... To close this out, a PR should be made to update the README to capture this thinking.