Reusable taproot addresses
This document proposes a new scheme to avoid address reuse while retaining some of the convenience of address reuse, keeping recoverability purely from Bitcoin time chain and avoiding visible fingerprint. The scheme has negligible average overhead.
Address reuse is one of the most horrible things people can do for privacy. However, the convenience can not be ignored and human beings are therefore incentivized to reuse addresses. This is especially the case in long-term business relationships, when it's convenient to avoid roundtrip of generating a new address.
There are existing schemes that tried to address this issue:
- Stealth addresses - they used ECDH to generate a new address for a new transaction putting ephemeral public keys in OP_RETURN outputs As a result they had significant overhead and visible footprint. Nonetheless their version is being used in Monero.
- Reusable payment codes (BIP 47) - a slight improvement over Stealth addresses. While they only require special transaction for initialization, subsequent transactions being free from overhead and visible fingerprint, the initial transaction must happen before real business activity and it produces effectively toxic change that may be difficult to handle. The initial transaction has no value besides providing convenient privacy. An alternate version proposed sending the required data over Bitmessage. This solved the problem with cost and footprint but introduced inability to recover coins purely from seed. In other words, the key received over bitmessage has to be backed up for every counterparty. Further, it requires yet another protocol that is not widely used.
This document proposes to solve the size/footprint issues of BIP 47 without losing the ability to recover from seed even if one of the parties is unavailable.
Similarly to BIP 47, this scheme uses a notification transaction. However unlike BIP 47, the notification transaction is also a "real" transaction. It is the transaction performed when the parties conduct business for the first time using this scheme. The sender of notification transaction MUST be spending at least one input of one of these types:
The sender MUST be capable of receiving to Taproot. The receiver MUST use Taproot for receiveing. (In principle, P2PK could be used instead of Taproot but such would be very unusual and thus suspicious.) The transacting parties MAY use PayJoin but MUST NOT involve a third party in it.
When using this scheme, the sender MUST generate a change using the following algorithm.
- Select an input with lowest index, belonging to the sender, being one of the types listed above. Let's call it sender key input.
p_senderbe the private key associated with sender key input.
P_receiverbe the Taproot address used by the receiver.
shared_secret = SHA256(p_sender*P_receiver)(ECDH)
offset = HMAC(shared_secret, CHANGE_KEY_CONSTANT)where
CHANGE_KEY_CONSTANTis an arbitrary constant defined by the protocol
P_change = (offset + p_sender)*G
- Calculate and securely cache
relationship_seed = HMAC(shared_secret, RELATIONSHIP_SEED_CONSTANT)where
RELATIONSHIP_SEED_CONSTANTis an arbitrary constant defined by the protocol that MUST NOT be equal to
P_changein the change output script
The receiver watches the address and reacts to received transaction by performing this check:
- Select an input with lowest index, not belonging to the receiver, being one of the types listed above - the sender key input.
P_senderbe the public key associated with sender key input.
p_receiverbe the private key associated with Taproot address used by the receiver.
shared_secret = SHA256(P_sender*p_receiver)(ECDH)
offset = HMAC(shared_secret, CHANGE_KEY_CONSTANT)
P_change = offset*G + P_sender
- Check that
P_changematches the key used in change.
- If the key doesn't match, don't continue
relationship_seed = HMAC(shared_secret, RELATIONSHIP_SEED_CONSTANT)and cache it securely
- Precompute a reasonably large number of offsets using a cryptographically secure PRNG seeded by
- For each offset compute
P_i = (offset_i + p_receiver) * G
- Start watching the chain for incoming transactions on public keys generated above
Each time the sender wishes to send to the receiver he computes
P_i = offset_i * G + P_receiver, where
offset_i denotes a random nonce generated by same PRNG mentioned in step 9 above.
The sender then sends coins to
The receiver has these addresses and private keys pre-cached so he can easily identify incoming transaction and spend the associated coins whenever needed.
In case of data loss, the sender recovers the history, coins and relationships using this algorithm:
- Scan the chain for all transactions associated with BIP32 addresses
- Every time a transaction is found which cointains at least two Taproot outputs that don't match any of the BIP32 addresses perform the following
- For each output attempt to repeat the algorithm above deriving the
shared_secretand the change output and check if the change output matches one of the outputs in the transaction
- If match was found precompute offsets and the associated addresses and add them with the change output to the list of scanned addresses.
- Scan the chain for all transactions associated with BIP32 addresses
- Every time a transaction is found which contains at least one additional Taproot output, attempt to recompute
shared_secretand check if any of the outputs matches expected change
- If a match is found, precompute the offsets and add the corresponding keys to the list of scanned addresses.
As can be seen from the above, the notification transaction looks like a regular transaction.
Since the outside observers can not compute
shared_secret (assuming ECDH is secure), they can not determine whether this protocol is being used nor compute the following addresses.
The protocol has same advantages over Stealth addresses as BIP 47, but in addition, the notification transactions can not be identified by outside parties,
the changes are not neccessarily that toxic (mixing is obviously still recommended) and the overhead is generally lower.
While it may seem that the overhead is zero, it's not exactly the case. The overhead of notification transaction over not using this protocol is:
- The contruction requires Taproot which is on average a little bit larger than P2WPKH.
- Skipping the change output in the rare cases when it wouldn't be needed (sufficient UTXO available) is not possible.
- Tricks using PayJoin to open a Lightning channel or participate in other contracts are not possible or require additional output.
- Opening a Lightning channel with the change or sending the change to someone else is impossible.
- Batching several notification transactions produces a change output for each receiver. On the bright side, this can be used to simulate Samourai-style Stonewall, getting a bit more privacy for the added fee.
It can be argued that until various batching tricks become widely used this overhead is small.
Nice write-up. It makes a lot of sense that you're bringing this up now, since taproot exposes the pubkey by default, which makes things a lot easier.
Your protocol variant does re-introduce one of the issues that the original stealth protocols sought to avoid: having to calculate a shared secret for (almost) every transaction on the blockchain. Since you never know when a new person might want to establish a shared secret with you, you have to keep scanning forever. ECC multiplication isn't cheap (especially when not multiplying by G), but it can basically be seen as an added validation cost to running a full node (and restoring back-ups) for those who want more privacy.
What's perhaps more problematic is that in your protocol the sender is forced to follow a special protocol to recover their coins after restoring a backup, which may cause reluctance to use it, especially in cases where the sender doesn't particularly care about privacy.
But I believe a more simple protocol will suffice, as well as remove the complexity on the sender side. Instead of marking a change output, Bob (B) can just directly pay Alice into her stealth key (A) by sending funds to A'=hash(b*A)+A. This gets rid of the requirement of needing the sender to make a special change output, makes the payment immediate, and the cost for the recipient stays the same because they already had to scan every transaction anyway.
There are three downsides I can think of:
It's also possible to still preserve the payment code property by just making the first payment as I described above, and then continuing to use the shared secret for the payment code, but I do think there's a lot to say for the simplicity of foregoing the need for payment codes completely, and the downsides seem relatively minor.
In any case, I'm glad to see you revitalize this topic. It's something I had been meaning to revisit by the time taproot came out, but had completely forgotten.