ECDSA signature aggregation for the same address: Is there a "soft" way?

[aliashraf]

It'd be  very easy to implement:

1- Generating transactions with multiple UTXOs with the same P2PKH/P2SH address, the wallet does not bother including the same witness data for each input, instead it adds a simple placeholder with length 1.

2- Verifying any transaction with multiple inputs, the client software temporarily saves addresses for the duration of the same transaction verification thread, that are signed and processed routinely, and whenever encounters the placeholder instead of rejecting the txn, checks whether the input address is already processed or not.

Use cases
Organizations/individuals maintain a single address for very long periods of time to collect funds like donations, etc.

Miners keep mining on the same address as a pool client, receiving funds on this address continuously.

Some financial relations, legally depend on a specific number of addresses to which payments should take place repeatedly.

Historical Objection
I remember this idea been discussed and denounced by Greg Maxwell because he believes such options possibly encourage address re-use that is considered a bad practice in bitcoin.

Possible modern objection
With Schnorr and taproot with signature aggregation built-in capabilities coming, it is just useless.

My stand
I don't think the re-use problem is relevant here, either people understand the risks involved in re-using their addresses or they don't in the second case they will do it anyway while the first group, the knowledgeable user, may find the risks involved affordable in special use-cases.
As of Schnorr signature support, I think the adoption process will be slow, and for a very long period of time we have to deal with ECDSA as the main trend and forever as a legacy one.

The problem
Unfortunately, as much as it is easy to implement, it looks to be very hard in terms of forking, legacy wallets will reject such blocks and won't commit to the legal chain anymore, so, this proposal should be dropped unless somebody could find a soft way to do it.

[1714145176]

1714145176

[pooya87]

It is not possible to implement this as a soft fork (it won't be backward compatible) specially for existing script types including but not limited to P2PKH, P2WPKH, P2SH, P2WSH because all current clients expect a signature per output being spent.
It could be implemented as a soft fork for a new script such as version 2 witness program but that won't provide any benefits to existing outputs such as a legacy address receiving hundreds of transactions.

[vjudeu]

What is the purpose of such improvement? For now, I can see that the only goal is just compressing the data. If so, then it would be easier (and backward-compatible) to create some new transaction type that will compress transaction data by using some kind of compression algorithm. Then, we would have old, uncompressed transactions doing things in old style and new, compressed transactions that could be easily decompressed and passed to all old nodes in uncompressed form when needed.

[aliashraf]

It could be implemented as a soft fork for a new script such as version 2 witness program but that won't provide any benefits to existing outputs such as a legacy address receiving hundreds of transactions.

Good idea, it happens to be more interesting than what it sounds 

I mean, having a specialized address type for gathering micro payments from casual payers has a wide range of applications right now.

[aliashraf]

What is the purpose of such improvement? For now, I can see that the only goal is just compressing the data. If so, then it would be easier (and backward-compatible) to create some new transaction type that will compress transaction data by using some kind of compression algorithm. Then, we would have old, uncompressed transactions doing things in old style and new, compressed transactions that could be easily decompressed and passed to all old nodes in uncompressed form when needed.

It is not just about data compression, performance is on the table as well because having nodes to go through the same signature generating/verification process for tens/hundreds times is a significant waste of time, remembering the nature of ECDSA as a cpu intensive task.

On the other hand, your compression idea isn't backward compatible either because transactions broadcasted in their compressed form will never get decompressed by legacy nodes and there is no practical way to make them doing this. Please note that txid is generated with the compressed form and you just can't have a same txn with two txids in the network.

[vjudeu]

It is not just about data compression, performance is on the table as well because having nodes to go through the same signature generating/verification process for tens/hundreds times is a significant waste of time, remembering the nature of ECDSA as a cpu intensive task.

To make it backward compatible, you have to keep it that way for all old nodes, as far as I know. Making some new version that will have better performance should give enough incentive to upgrade.

On the other hand, your compression idea isn't backward compatible either because transactions broadcasted in their compressed form will never get decompressed by legacy nodes and there is no practical way to make them doing this. Please note that txid is generated with the compressed form and you just can't have a same txn with two txids in the network.

It is backward compatible, because old nodes will receive transactions in uncompressed form and new nodes will receive them in compressed form. For backward compatibility, calculating transaction hash from uncompressed form is needed. So: old nodes will process such transactions as they do it today. Old nodes will keep sending and receiving these transactions the same way as today. But new nodes will process them faster, because they will be able to compress/decompress such transactions. And they have to do it only once and then remember that Alice's transaction uncompressedTxidA is equal to Alice's transaction compressedTxidA. New nodes could send, receive and process transactions in compressed form. Old nodes have to process all of them in uncompressed form, unless you move the coins to some future-segwit-version-outputs, then they will blindly accept it without processing.

Edit: some description to explain all cases:

1) old node to old node will send everything in uncompressed form (to make it backward-compatible)
2) old node to new node will send everything in uncompressed form, but that new node will compress it once, and then will be able to store and process such transaction in compressed form
3) new node to old node will send everything in uncompressed form, but decompression will be simple and could be done on-the-fly, because it will contain simple things like "repeat N bytes M times"
4) new node to new node will send everything in compressed form (and because it will have better performance, people will upgrade quite soon)

Edit:

I remember this idea been discussed and denounced by Greg Maxwell because he believes such options possibly encourage address re-use that is considered a bad practice in bitcoin.

In my idea, transaction hashes are still calculated from their uncompressed form. And that means that fees for spending such transaction should be the same. So, if you have some 100 kB transaction that can be compressed to 1 kB transaction, you still have to pay for taking 100 kB blockchain space.

With Schnorr and taproot with signature aggregation built-in capabilities coming, it is just useless.

It is useless for new addresses, but still, compressing the history is an incentive, so such things should be done to make running full archival nodes cheaper if possible.

And with my compression idea, it requires no forks, you can apply any kind of compression you want just right now without asking. The only reason to standardize it is that if there will be many nodes compressing data in the same way, then less bandwidth will be used, because then it will be possible to send and receive things in compressed form.

[NotATether]

When you make a new signature format that's got to be used by scripts, you have to consider how much space will be saved on the blockchain, and whether the savings over time will be enough to justify its implementation. It is entirely possible that this signature aggregation could actually be deployed in a new address type, but for nobody to actually use the new address types.

Most people will just use whatever default their wallet makes them. Also exchanges and web wallets will likely not transition from segwit addresses to a newer kind of address for their own internal policy reasons. So that's already a majority of users who aren't using the smaller-sized signatures which makes the actual savings a small fraction of what they were originally intended to be.

Meanwhile special cases in the verification code for these kind of signatures have to be made and as little as they are used, they can never be removed, increasing code complexity.

[aliashraf]

It is not just about data compression, performance is on the table as well because having nodes to go through the same signature generating/verification process for tens/hundreds times is a significant waste of time, remembering the nature of ECDSA as a cpu intensive task.

To make it backward compatible, you have to keep it that way for all old nodes, as far as I know. Making some new version that will have better performance should give enough incentive to upgrade.

On the other hand, your compression idea isn't backward compatible either because transactions broadcasted in their compressed form will never get decompressed by legacy nodes and there is no practical way to make them doing this. Please note that txid is generated with the compressed form and you just can't have a same txn with two txids in the network.

It is backward compatible, because old nodes will receive transactions in uncompressed form and new nodes will receive them in compressed form. For backward compatibility, calculating transaction hash from uncompressed form is needed. So: old nodes will process such transactions as they do it today. Old nodes will keep sending and receiving these transactions the same way as today. But new nodes will process them faster, because they will be able to compress/decompress such transactions. And they have to do it only once and then remember that Alice's transaction uncompressedTxidA is equal to Alice's transaction compressedTxidA. New nodes could send, receive and process transactions in compressed form. Old nodes have to process all of them in uncompressed form, unless you move the coins to some future-segwit-version-outputs, then they will blindly accept it without processing.

Edit: some description to explain all cases:

1) old node to old node will send everything in uncompressed form (to make it backward-compatible)
2) old node to new node will send everything in uncompressed form, but that new node will compress it once, and then will be able to store and process such transaction in compressed form
3) new node to old node will send everything in uncompressed form, but decompression will be simple and could be done on-the-fly, because it will contain simple things like "repeat N bytes M times"
4) new node to new node will send everything in compressed form (and because it will have better performance, people will upgrade quite soon)

Edit:

I remember this idea been discussed and denounced by Greg Maxwell because he believes such options possibly encourage address re-use that is considered a bad practice in bitcoin.

In my idea, transaction hashes are still calculated from their uncompressed form. And that means that fees for spending such transaction should be the same. So, if you have some 100 kB transaction that can be compressed to 1 kB transaction, you still have to pay for taking 100 kB blockchain space.

With Schnorr and taproot with signature aggregation built-in capabilities coming, it is just useless.

It is useless for new addresses, but still, compressing the history is an incentive, so such things should be done to make running full archival nodes cheaper if possible.

And with my compression idea, it requires no forks, you can apply any kind of compression you want just right now without asking. The only reason to standardize it is that if there will be many nodes compressing data in the same way, then less bandwidth will be used, because then it will be possible to send and receive things in compressed form.

I've to admit that your proposal holds some water  

I mean it doesn't help with block space compression and the network throughput, as the 1 MB rule and/or 4 MB block Weight are to be applied to the uncompressed format anyway, but it could be helpful with the block verification process, hence performance, IF we apply a little tweak: let's forget about a general idea of compression and stay focused on signature aggregation.
Generalizing your compression/decompression idea I'd propose a 2-way deterministic map such that a given legacy transaction with multiple identical P2PKH, P2WPKH, P2SH, P2WSH, ... addresses used in its inputs is mapped to a canonical form with just the first input having witness data included, upgraded nodes would be free to transmit this mapped version between themselves and the original one in other cases.

Now here comes a minor problem: Does the client software use a different entropy for the same public keys in the same transaction? If it is the case which I'm afraid it is more likely to be, we'd have a problem because generating the legacy transaction format from its mapped version is not possible unless it is produced and tagged by an upgraded wallet.

[vjudeu]

let's forget about a general idea of compression and stay focused on signature aggregation

It does not matter that much what data will be compressed. You can define some "standard" compressed transactions, for example for address reuse and allow some kind of "compression script" to extend it in the future if needed. And then, you can process "standard" compressed transactions faster, because you would know that for example in that kind of transaction you have to deal with address reuse. But having open doors for future kind of compression should be there. As long as "compression script" will be turing-incomplete-on-purpose and will consist of some simple operations, the cost of expanding the system in the future will be lower. Next versions will just define more types of compression, but old compression nodes will correctly store and process everything in compressed form, if they will use some simple things like "repeat M bytes N times". Then, future improvements can focus on processing rather than compression if "compression script" will be good enough for all cases.

I'd propose a 2-way deterministic map such that a given legacy transaction with multiple identical P2PKH, P2WPKH, P2SH, P2WSH, ... addresses used in its inputs is mapped to a canonical form with just the first input having witness data included

There is no need to limit it to the standard transactions. If you can handle the whole input as compressed and if you have 100 identical inputs, you can validate it once, even if it is nonstandard, as long as the whole script and input data are identical.

Does the client software use a different entropy for the same public keys in the same transaction?

Yes. There are completely different (r,s) pairs for each of them. And that is why your idea is useful only in some general compression scheme, because you cannot compress much data without knowing how to handle it efficiently, you can do some simple guessing like "there are many zeroes, so put OP_REPEAT OP_ZERO OP_TIMES 100", but the user (or its wallet) will probably know it better. And that is the reason why user (or software used by that user) should specify "compression script", then that user (and that software developers) are incentivized to handle it as efficient as it could be, because it will be cheaper (in terms of processing power and capacity needed to store and process such transaction). But of course for historical transactions, you have to guess it on your own, based just on blockchain data you have.

[gmaxwell]

To use this it requires a new script type and requires solving all the engineering challenges of aggregation such has how do you handle aggregation in the face of soft-forks which might be used by some inputs and not others, where do you place the aggregate, how do you handle multiple aggregate groups in a single txn, etc...  And, as noted, it would create a extraordinary super-massive benefit for privacy damaging address reuse and would erode the privacy of coinjoins.

Instead, use schnorr aggregation -- which would be _strictly easier_ to implement-- probably about 5% less code in total.  The general engineering challenges are the same and the downsides are a strict subset (no problems with forcing reuse) and the benefits are much greater.  Literally why would you do anything else?  Doesn't make any sense at all.

Even if you imagine implementing it as a hard fork, it would still be easier to implement as schnorr signatures.  The challenges in aggregation are the ones that arise from the fact that aggregation inherently violates the isolation/independence of separate inputs, and that remains true regardless of how aggregation is implementated.  The only thing a hardfork would potentially gain would be the ability to spend existing outputs that way, and even that is dubious because adding additional ways to spend existing outputs might violate user's security because they made a strong assumption that an output could only be spent a particular way.

What is the purpose of such improvement? For now, I can see that the only goal is just compressing the data. If so, then it would be easier (and backward-compatible) to create some new transaction type that will compress transaction data by using some kind of compression algorithm.

Sure, proposed back in 2016 and it exists today as part of the blockstream satellite repository, as discussed on bitcointalk previously.

The blockstream satellite node implementation supports an alternative serialization that operates on a single transaction at a time and shrinks them 20-30% on current typical transactions.   For the bandwidth limited satellite transmission it makes a big difference-- ... elsewhere I tried pretty hard to get people interested in it, but had no success (I had a bit more influence over what blockstream implemented when I worked there than what the community works on or takes interest in. ).

Now here comes a minor problem: Does the client software use a different entropy for the same public keys in the same transaction?

Yes. There are completely different (r,s) pairs for each of them.

The signatures on each input *must* be distinct, other otherwise they would be vulnerable to malleation or replay.  You can only aggregate signatures by actually having aggregated signature support.

[aliashraf]

... how do you handle aggregation in the face of soft-forks which might be used by some inputs and not others

Sorry, but I didn't get your objection here.

where do you place the aggregate

In front of the first redundant input

, how do you handle multiple aggregate groups in a single txn,

Not a challenge at all, first occurence of any redundant input is signed, a completely consistent and smooth process.

it would create a extraordinary super-massive benefit for privacy damaging address reuse and would erode the privacy of coinjoins.

Unfortunately, for the mapped/compressed  version discussed above, there is no super-massive benefit from the perspective of users, just ease of use. It is due to backward compatibility needed for keeping legacy nodes on-chain. For the new-opcode version of the proposal, you need legacy segwit nodes to upgrade which doesn't look promising given the current status of Bitcoin ecosystem.

Instead, use schnorr aggregation -- which would be _strictly easier_ to implement-- probably about 5% less code in total.  The general engineering challenges are the same and the downsides are a strict subset (no problems with forcing reuse) and the benefits are much greater.  Literally why would you do anything else?  Doesn't make any sense at all.

Somehow, this proposal could apply to Shnorr signature implementation in Bitcoin as well!
AFAIK, current implementation follows the same roadmap as legacy one-input-one signature policy THEN it aggregates (by multiplication) all the signatures, and respectively client software processes inputs one by one regardless of the rendundant public keys. I suppose this is a followup of your Discourage-Address-Reuse policy, isn't it?

As of this policy:
With all due respect Greg, I'm completely against it because of its negative impact on bitcoin adoption. I've already listed some critical use cases in OP but regardless of that I find this kind of policies too much patronizing. Users are free to make their own risk assessments and trade-offs, I'm afraid overusing incentivize/de-incentivize tools and policies violates this basic right.

The signatures on each input *must* be distinct, other otherwise they would be vulnerable to malleation or replay.  You can only aggregate signatures by actually having aggregated signature support.

In this proposal, signatures are literally unique, though I don't understand how and why different entropy is strictly necessary when the message (tx) and the public key are the same?
On the contrary I suppose it is the current implementation that is (kinda) malleating the network by filling the witness part with tens of signatures that weigh nothing more than just ONE signature.