Mining signatures for single satoshis

[miner2251]

Classical mining is based on finding the smallest possible block hash. But as we know, r value of the signature can be smaller than usual if it starts with some zeros. Leaving half of the base point behind, I can imagine a system where miners collect transactions and try to find some value that can be added to "r" and can lead to smaller signatures. Users can receive such values in P2P way, because each miner can just share his "r2" public key to prove that miner found the lowest public key for that signature. Then, that user can send some satoshis in LN as a reward to that miner, and to unlock that coins, the miner have to reveal that private key for "r2" to the user. Then, that user can create smaller signature, leaving more room for other transactions in the blockchain.

Assuming one satoshi per byte fee rate and 2,000 transactions in the whole block, saving 5 bytes per transaction would mean earning 10k satoshi per block (and leaving some room for 40 more transactions 250 bytes each). Of course it is negligible for big miners, but for smaller ones it may be profitable, if they could fight for some satoshis. And the profitability limit will be quite high, because truncating five or six bytes may be profitable, but hitting eight or more will be exponentially more difficult, so it rather encourage hitting more transactions than more zeroes in single transaction.

It can be applied to any address type that involves public keys, including multisig and Segwit, because transaction fees are based on total transaction size. So, even if Segwit signatures are outside of the block, users can still pay less satoshis for including such transactions with "mined r values". Unfortunately, that kind of service cannot be applied for taproot, because that signatures has fixed size of 64 bytes, but they are compressed to single signatures anyway, so there is less need for that kind of compression.

[NotATether]

Assuming one satoshi per byte fee rate and 2,000 transactions in the whole block, saving 5 bytes per transaction would mean earning 10k satoshi per block (and leaving some room for 40 more transactions 250 bytes each). Of course it is negligible for big miners, but for smaller ones it may be profitable, if they could fight for some satoshis. And the profitability limit will be quite high, because truncating five or six bytes may be profitable, but hitting eight or more will be exponentially more difficult, so it rather encourage hitting more transactions than more zeroes in single transaction.

10k satoshis are only worth $3.62 currently so I don't think even the smaller miners will benefit from scouting smaller r-value transactions. They will be more focused on getting their blocks broadcasted as quickly as possible because them finding a block is rare, they wouldn't want to waste valuable seconds just to earn a few extra bucks.

[gmaxwell]

Bitcoin Core shaves a byte off each signature this way-- many blocks actually contain more total transactions due to this today.   But it becomes pretty computationally expensive pretty fast to shave more off.

One thing you don't point out is that it's possible to batch up generation of multiple users.  Say for example that Alice wants the shave 4 bytes off key A and Bob wants to shave 5 bytes off key B.   So you compute key C = A + B  and then search for a tweak to add to get a smaller solution. If you find a 4 byte solution you have Bob reveal his private nonce and he generates a new one and continues with someone else, if you find a 5 byte solution Alice reveals her private nonce and she continues with someone else, alice doesn't mind this delay because 5 byte solutions are really rare compared to 4.  This way you can do deeper searches on the backs of shallower searches.

You can also make signatures much smaller by also grinding s.  Only the private key holder can grind s, you can't delegate it like R.  First you get a small R then you change the content of the transaction (sequence numbers, nlock, order, output addresses, etc) until the s value is smaller.  Because of how DER encoding works, a smaller s value will also make the signature smaller regardless of R's size.  The s search doesn't involve any elliptic curve operations, just hashing and some field operations, so it is very fast. The annoying part is that you need something in the transaction you can modify, and you can't add a nonce (like an op_return) as that would defeat the purpose.

For taproot, the signatures are quite a bit smaller to begin with-- 64 bytes instead of 72, more than you can reasonably shave, so the fact that they're constant length matters less. It was chosen to make them constant length to simplify other future tricks.

[pooya87]

miners collect transactions and try to find some value that can be added to "r" and can lead to smaller signatures.

The hardware the miners have (ie. ASIC) is designed to compute one thing and one thing only. That is to compute double SHA256 of block headers. To compute EC operations you'll need to use regular hardware (CPU/GPU) or a different specialized hardware (a different type of ASIC) to make those computations.

Assuming one satoshi per byte fee rate and 2,000 transactions in the whole block, saving 5 bytes per transaction would mean earning 10k satoshi per block

Fees are paid per byte not per transaction. If a block contains 1x 200 byte transaction paying 1 sat/byte the miner makes 200 satoshi and if it contains 2x 100 byte transaction each paying 1 sat/byte the miner still makes 200 satoshi.

So, even if Segwit signatures are outside of the block,

SegWit signatures are NOT outside of a block. They contribute 1x to the total weight while everything else is 4x.

Unfortunately, that kind of service cannot be applied for taproot, because that signatures has fixed size of 64 bytes, but they are compressed to single signatures anyway, so there is less need for that kind of compression.

The main reason why Schnorr signatures are smaller is not because they are "compressed to a single signature" it is because we got rid of a lot of overhead with DER (8 bytes to be precise + 1 byte from pubkey). If you try to make r and s lengths variable you'll have to re-introduce DER (or a similar variable length encoding) which will add the overhead again.