search

trezor / trezor-firmware

:lock: Trezor Firmware Monorepo
https://trezor.io
Other
1.36k stars 661 forks source link

Transaction weight revision #1889

Open andrewkozlik opened 3 years ago

andrewkozlik commented 3 years ago

The weight of the transaction produced by Trezor is currently indeterminate if non-Taproot inputs are present. The reason for this is that the DER encoding of the signature is between 70 and 71 bytes depending on the particular signature. There is no way to tell in advance what the length will be. (To be precise, there is a small chance that it will be less than 70, but never more than 71.) Taproot signatures are not a problem because they are always 64 bytes.

TxWeightCalculator in core currently assumes that the signature will be 71 bytes in length, i.e. the maximum. We should evaluate whether this is a good choice. One thing to take into consideration here is to make Trezor transactions indistinguishable from transactions produced by other wallets. If there is a consensus in the community about the assumed signature size, then we should adopt it in Suite and Trezor.

Another option is to change the signing algorithm to always produce signatures that are 70 bytes in length, i.e. if the signature does not come out as 70 bytes, then retry. This would make the transaction weight deterministic and would save on transaction fees. The number of retries would be 1 on average, i.e. a total of 2 signing operations per signature.

Summary of options for DER signature length:

  1. Nondeterministic length. Assume maximum length of 71 bytes. Requires 1 signature computation.
  2. Deterministic length of 70 bytes. Requires 2 signature computations on average.

(Edited, because I previously forgot about the low-S rule.)

matejcik commented 3 years ago

Another option is to change the signing algorithm to always produce signatures that are 70 bytes in length

wouldn't this make Trezor transactions (weakly) distinguishable?

andrewkozlik commented 3 years ago

Another option is to change the signing algorithm to always produce signatures that are 70 bytes in length

wouldn't this make Trezor transactions (weakly) distinguishable?

Correct, option 2. allows an analyst to determine that a transaction was not signed by Trezor when the length doesn't match. BTW there are several other things in addition to fees/weight and signature lengths that can be used for analysis: transaction version, locktime, sequence, input and output ordering, maybe UTXO selection. So making Trezor indistinguishable from other wallets may prove challenging.

matejcik commented 3 years ago

all of those are supplied externally though (so you're distinguishing Trezor Suite, not the device)

andrewkozlik commented 3 years ago

Update: I forgot about the low-S rule, which means that signatures are between 70 and 71 bytes. I fixed the original post to account for this.

Electrum generates signatures of (at most) 70 bytes in length [1], but they assume the maximum of 71 bytes [2], because hardware wallets may generate 71-byte signatures. Apparently Bitcoin core also generates signatures of 70 bytes in length [3].

[1] https://github.com/spesmilo/electrum/blob/master/electrum/ecc.py#L473

[2] https://github.com/spesmilo/electrum/blob/a5c4b9e719b5ed06375fca2bddace1151e583df2/electrum/transaction.py#L687-L692

[3] https://github.com/bitcoin/bitcoin/pull/13666

andrewkozlik commented 2 years ago

I looked at two more wallets.

Sparrow Wallet generates signatures of 70 bytes in length: https://github.com/sparrowwallet/drongo/blob/083288061ffe6e08805bb58108a9afab0d93fb0f/src/main/java/com/sparrowwallet/drongo/crypto/ECKey.java#L353 and assumes 70 bytes for fee estimation: https://github.com/sparrowwallet/drongo/blob/083288061ffe6e08805bb58108a9afab0d93fb0f/src/main/java/com/sparrowwallet/drongo/protocol/TransactionSignature.java#L47-L56

Mycelium Wallet generates signatures of at most 71 bytes: https://github.com/mycelium-com/wallet-android/blob/aea49dc14314eec461ad307af7f8f99abe4ddf79/bitlib/src/main/java/com/mrd/bitlib/crypto/InMemoryPrivateKey.java#L353-L366 Mycelium's fee estimator is here: https://github.com/mycelium-com/wallet-android/blob/master/bitlib/src/main/java/com/mrd/bitlib/FeeEstimator.kt

andrewkozlik commented 2 years ago

Based on the statistics from https://transactionfee.info/charts/bitcoin-script-ecdsa-r-value/ it appears that currently 1/3 of transactions signatures are generated by wallets that enforce a low-r value.

andrewkozlik commented 1 year ago

FTR, an interesting blog about wallet fingerprinting https://ishaana.com/blog/wallet_fingerprinting/, where this is referred to as "low-r grinding".