Change forwarding.mediawiki

    BIP: ????
    Title: Change forwarding
    Author: Yuval Kogman <nothingmuch@woobling.org>
    Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-????
    Status: Draft
    Type: Informational
    Created: 2018-11-05
    License: CC0-1.0
             GNU-All-Permissive

Table of Contents Abstract Definitions Motivation Specification Fungibility Wallet Account Hierarchy Serialization Format (TBD) Forwarding Wallet Setup Rationale Considerations Ensuring Proper Mixing Forwarding Wallet Implementation Code Changes Displaying Balances Fungibility Wallet Implementation Examples Unintended Linking Linking Prevention Test Vectors (TODO)

Abstract

This document proposes a method for configuring BIP32 capable wallets in order to improve UTXO handling for non privacy/fungibility oriented wallets, by forwarding change outputs to a privacy preserving wallet.

Definitions

• Forwarding wallet - any BIP32 capable wallet for day to day usage, for instance a hot wallet or special purpose application with embedded wallet (e.g. bisq, open bazaar, protip.is), extended with the functionality described in this document.
• Fungibility wallet - any BIP32 capable wallet with privacy and fungibility features, in particular mixing (e.g. join market, wasabi)

Motivation

Different BIP32 capable wallets have been designed with various use cases in mind. Many of these (especially mobile wallets) lack good controls over the outputs being spent, and fewer still are focused on maintaining good privacy and fungibility. This creates the potential for inadvertently linking otherwise unrelated transactions when change outputs are used as inputs to subsequent transactions.

By adding the ability to forward all change outputs from such wallets directly to a branch of the BIP44 account hierarchy of a specializing mixing wallet, accidental linking due to human error or naive coin selection can be prevented. If UTXOs of the forwarding wallet can be assumed to be fungible, transaction independence can be maintained without special coin selection functionality since each subset of outputs can only be used by the wallet exactly once, and none of the resulting outputs are directly usable by the forwarding wallet. Those change outputs can subsequently be mixed and then redistributed to the forwarding wallet(s), preserving the validity of fungibility assumptions.

Specification

Fungibility Wallet Account Hierarchy

BIP32 describes the "Unsecure money receiver" role, which derives addresses using the public extended key for a specific chain. The forwarding wallet will function as an unsecure money receiver for the fungibility wallet.

BIP44 recommends separate non-hardened derivation for receiving (external) and change (internal) address chains, created as children hardened account paths. Separate hardened accounts should therefore be created, one for each forwarding wallet, with the external non-hardened chain, denoted m below, being exported using the following serialization format.

Serialization Format (TBD)

In order to ensure that the fungibility wallet can recognize spendable outputs generated by the forwarding wallet, both wallets must agree on the script derivation for a given public key in the address chain.

The BIP32 serialization format can therefore be ammended by the fungibility wallet with additional information using one of the following options:

• SHA256( scriptPubKey_{m / 0} ) - allows arbitrary scripts/addresses, open for extension, multisig possible. Electrum protocol uses SHA256 but HMAC_SHA512(scriptPubKey_{m / 0}, xpub) could also be used. Simplest to implement for forwarding wallets (go/no-go during setup based on existing address derivation).
• SLIP32/SLIP132 or Electrum style version bytes - electrum also mentions but doesn't specify standard multsig version bytes, compact, only supports fixed script/address formats
• miniscript
• BIP124 templates - encoding/serialization format is still TODO, would allow arbitrary scripts, could in principle be parameterized over multiple xpubs to derive multisig scripts, relatively complex
• BIP178 version bytes - fixed script formats, compact, no standard multisig, intended for WIF keys (mainly included for completeness)

Forwarding Wallet Setup

In the forwarding wallet, an additional configuration option should be provided which overrides the standard change internal address chain.

The configuration value must only be accepted if the forwarding wallet is capable of deriving a matching script as specified by the fungibility wallet.

Rationale

(note: This section makes the assumption that SHA256(scriptPubKey) is the preferred option for the serialization format which is still TBD. However, this is not clearly the case, primarily because version bytes approach is already prevalent, and the hashes are significantly less compact. On the other hand SLIP-0032 style extended public keys can lead to non fail-safe behaviour if the two wallets differ in their interpretation of the version bytes, and the derivation sub-path is only specified by convention. BIP124 templates are still not fully specified, and would require forwarding wallets to construct scripts differently, instead of just verifying that the fungibility wallet recognizes scripts of a form they already implement)

This proposal aims to improve interoperability of less coupled wallet implementations, specifically in a way that ensures that forwarding wallet transactions utilize separate master seeds in their inputs and outputs, under the assumption that the master seed used for the outputs is managed by specialized fungibility wallet.

Public extended keys are already in common use, though their main application has been to protect key material, and this typically assumes a high degree of coupling between the implementation of the watching wallet and the signing wallet, and that address chains derive from a single master seed.

Furthermore, since improving fungibility through interoperability is the main goal, the changes required in order to add forwarding capabilities to existing wallets should be minimal and leave little room for implementation error (no ambiguity with respect either the derivation path or the script being used).

Considerations

Ensuring Proper Mixing

Any non-fungible coins sent to the forwarding wallet are in no way protected by this setup, so the fungibility wallet must first be used correctly to ensure fungibility.

Secondly, subset sum analysis could still be performed on the change outputs used as inputs into mixing transactions, potentially linking pre-mix transactions. This concern can be alleviated by mixing in larger batches but is otherwise beyond the scope of this document.

Forwarding Wallet Implementation

Code Changes

This proposal is designed to minimize the required changes to forwarding wallets.

When creating change outputs, the only required change should be the switch to an address chain based on a public key instead of the wallet's regular account hierachy. If change forwarding is not configured, the same code path can still be used to derive change addresses from the forwarding wallet's account hierarchy using public child key derivation.

Most of the complexity of any changes is expected to be in the configuration and balance UIs.

Displaying Balances

Since change outputs become unspendable, forwarding wallets should convey to the user that after a payment is made the usable balance may decrease by more than the payment amount. Forwarding wallets can still display balances from the unspendable address chain (e.g. as "locked" balances) similar to watching wallets.

Fungibility Wallet Implementation

The fungibility wallet should allow exporting of different forms of public extended keys, but only for its supported script/address types, to avoid loss of funds. If multiple options are available the user can manually select which type to use, or leave that choice up to the forwarding wallet.

The fungibility wallet should keep track of exported keys and use separate hardened account derivation paths for different forwarding wallets, to avoid address reuse when different forwarding wallets are used concurrently. To ensure account discovery when recovering from seed using another wallet in accordance with BIP44 recommendations, the receiving wallet should only export new accounts if the previous account index has a transaction history, and may create a transaction that utilizes the first address in the chain before exporting.

Examples

We can consider two example scenarios, though technically one is just a special case of the other:

• Wallet has one large UTXO
• Wallet has multiple UTXOs of uniform or varying size

Unintended Linking

When a wallet has a single large UTXO and a payment is made, a transaction with a single change output will typically be created, effectively returning to the starting condition.

The resulting transaction graph might look something like the following, where edges terminating in x denote fungible outputs, o denotes likely tainted outputs, and ... denotes outputs controlled by other parties:

    x--initial output--> TX_1--+--change--> TX_2--+--change--> TX_3--+--change---o
                               |                  |                  |
                               +--payment--...    +--payment--...    +--payment--...

With more fragmented UTXOs the situation might look more like:

    x--+
       |
    x--+--> TX_1--+--change---o
       |          |
    x--+          +--payment--...
    
    
    x--+                  x--+
       |                     |
    x--+--> TX_2--+--change--+--> TX_3--+--change---o
                  |                     |
                  +--payment--...       +--payment--...

In addition to coin selection features, BIP69 and BIP126 can be used to make inputs less distinguishable payment vs. change outputs, but we assume the forwarding wallets do not necessarily make such considerations.

Linking Prevention

By interspersing payment transactions with mixing transactions, the resulting transaction graph is harder to analyze, even if the forwarding wallet makes no considerations when constructing inputs, since the property that all spendable UTXOs are unlinkable is preserved by the mixing wallet.

Note that in the following diagrams mixing stages may represent multiple transactions. Additionally, change outputs of all transactions are only spendable by the mixing wallet, and at the end of the following sequence the forwarding wallet balance is 0, i.e. fungible outputs (x) are only spendable by the forwarding wallet, and tainted outputs (o) are only spendable by the mixing wallet:

                                                            :
                                                            |
                          :           :     ...--3rd party--+           :
                          |           |                     |           |
          ...--3rd party--+           +--3rd party--...     |           +--3rd party--...
                          |           |                     |           |
    x--> TX_1--+--change--+--> MIX_1--+--> TX_2--+--change--+--> MIX_2--+--> TX_3--+--change---o
               |                                 |                                 |
               +--payment--...                   +--payment--...                   +--payment--...

Similarly with higher UTXO fragmentation:

                             :           :
                             |           |
    x--+     ...--3rd party--+           +--3rd party--...
       |                     |           |
    x--+--> TX_1--+--change--+--> MIX_1--+--mixed------x
       |          |
    x--+          +--payment--...

                             :           :
                             |           |
    x--+     ...--3rd party--+           +--3rd party--...     
       |                     |           |
    x--+--> TX_2--+--change--+--> MIX_2--+--mixed------x
                  |
                  +--payment--...       

    x--+          
       |
    x--+--> TX_3--+--change---o
                  |
                  +--payment--...

Test Vectors (TODO)

This section will be added pending final decision on the preferrable serialization format(s).

Here are some thoughts about the tradeoffs implied by the proposal. I hope they will be useful. I apologize for the long wall of text.

My understanding:

• The goal of this proposal is to break the link between multiple transactions sent by a user (as in "all these transactions have been sent by the same entity").
• The proposal rightfully identifies that 2 heuristics used by analytics platforms (the "merged inputs" and "change ouput" heuristics) play an important role here.
• The proposal intends to break these links by systematically interspersing a mixing step between the change output being created and the change output being spent. It doesn't intend to directly mitigate the 2 heuristics.
• Payment output is sent to receiver's forwarding wallet and change output is sent to sender's fungibility wallet.

Under these assumptions, my analysis of the proposal is that the mixing step creates a pattern which, at the level of a single transaction, allows to identify the payment output from the change output with almost 100% certainty. This is where I think there's a tradeoff which should be discussed. With this scheme, we trade a "leak" about individual transactions for a better unlinkability of transactions sent by the user. Obviously, the question is: does it worth it?

In order to nurture the discussion, here are a few elements:

• AFAIK, "change output" heuristics (there are several "flavours") are used by almost all analytics platforms.

• All wallets currently do a bad job at protecting users against "change output" heuristics. Can wallet developers do better on this front?

• While being effective, "change output" heuristics used to have a high false positive rate (at least if we compare them with the "merged inputs" heuristics). Do we know if progresses have been made on this front?

• If we accept to make this tradeoff, we should be sure that the other component of the scheme (mixing service) is battle-hardened because the worst outcome would be to concede certainty about the change outputs without properly unlinking the transactions.

• IMHO, important questions are: "Do we have mixing services providing the properties required for this BIP? What are these required properties?". For instance, I don't think that the model implemented in the upcoming v1 of whirlpool is going to be a good match. Likewise, I don't think that current version of Wasabi would help for mixing a big change output because it seems to work like a peeling chain (but's it's just based on a few personal observations. Better to get a confirmation from Nopara). I'm not sure about Joinmarket. On the bright side, let's note that nothing is set in stone and all these tools may implement alternate models which better fit the requirements of this BIP.

• Another set of questions is:

  • Do we have enough insights about the protection provided by the mixing services?
  • How well do they resist to "advanced attacks" like timing analysis or Sybil attacks?
  • Is it better if payment outputs are directly sent to Bob's fungibility wallet?
  • Is is better if all transactions are done through a mixing service?
  • Can we make any assumption about how the receiving wallet will manage the incoming funds? What are the risks if we can't make this assumption ?

In conclusion, I think this BIP should take a more "holistic" approach and should include a detailed analysis/specification of the mixing component (requirements, risks, etc). Anyway, this proposal already raises 2 very interesting questions:

• Are we ready to concede a 'defeat' on the front of the 'change output' heuristics for the sake of an improved unlinkability of transactions? (I don't know the right answer to this question but it might be a good strategy... or not)
• Are we confident that existing mixing services are strong enough that it worths making this tradeoff?

My 2 satoshis.

Here are some thoughts about the tradeoffs implied by the proposal. I hope they will be useful. I apologize for the long wall of text.

Please don't apologize, this is very valuable input!

• The goal of this proposal is to break the link between multiple transactions sent by a user (as in "all these transactions have been sent by the same entity").
  ...
• The proposal intends to break these links by systematically interspersing a mixing step between the change output being created and the change output being spent. It doesn't intend to directly mitigate the 2 heuristics.
• Payment output is sent to receiver's forwarding wallet and change output is sent to sender's fungibility wallet.

1. no assumptions are made the receiver's wallets, this only addresses the sender's point of view, i.e. the payment output might be an arbitrary address
2. more precisely, the goal isn't even to break the links, the assumption is that the fungibility wallet provides functionality to handle that, but rather to allow BIP32 wallets in general, most of which have fairly opaque handling of UTXOs (just a single balance figure) to be able to delegate the handling of this to a specialized fungibility wallet with minimal changes, so i would say it's not even indirectly mitigating the heuristics, it's more about moving the mitigation problem to a more appropriate wallet with reduced possibility of user error or lack of control, (e.g. if you have a wallet daily use, and you decide to use a mixing wallet, moving the funds into the mixing wallet presents a significant hurdle if done manually).

I will attempt to clarify these points

Under these assumptions, my analysis of the proposal is that the mixing step creates a pattern which, at the level of a single transaction, allows to identify the payment output from the change output with almost 100% certainty.

This is correct, though I think not at the level of a single transaction - the forwarding wallet should still be utilzing outputs with scriptPubKeys of the same form as it would if not configured to forward change, the only difference in constructing transactions should be the BIP32 parent key being used to generate the address, which should be indistinguishable to anyone not in possession of the derivation keys.

However, outputs can be identified as change outputs in that they would likely be redeemed differently, i.e. the fungibility wallet would presumably use them as inputs into a mix. I'm not sure if this is what you meant? Either this is a serious concern that must be acknowledged in this BIP, even if it is not directly addressed.

• If we accept to make this tradeoff, we should be sure that the other component of the scheme (mixing service) is battle-hardened because the worst outcome would be to concede certainty about the change outputs without properly unlinking the transactions.
• IMHO, important questions are: "Do we have mixing services providing the properties required for this BIP? What are these required properties?". For instance, I don't think that the model implemented in the upcoming v1 of whirlpool is going to be a good match. Likewise, I don't think that current version of Wasabi would help for mixing a big change output because it seems to work like a peeling chain (but's it's just based on a few personal observations. Better to get a confirmation from Nopara). I'm not sure about Joinmarket. On the bright side, let's note that nothing is set in stone and all these tools may implement alternate models which better fit the requirements of this BIP.

This is indeed a critical question, and in its current form this proposal does makes the unqualified assumption the fungibility wallet functions optimally. At the very least I must qualify these assumptions better, but of course that would do little to actually help the state of bitcoin fungibility directly ;-)

As far as I know Joinmarket is somewhat more useful in this regard when using the tumbler script, as it attempts to achieve de-correlation of amounts as well sa of merged inputs by having multiple mixing stages.

(ab)using Joinmarket's terminology by analogy, forwarding wallets implementing this proposal configured with one of the mixing depths of the joinmarket wallet as the change chain, and assuming funds sent to the forwarding wallet are the outputs of SpendJMTxs, would allow all transactions made by the forwarding wallet to function as SourceJMTxs with respect to their change, as an alternative to using the sendpayment script (and with reduced benefits over the patient sendpayments mode). BTW, it should be noted that this entire proposal is basically just JM's concept of different mixing depths having different BIP32 branches .

FWIW, I have a related proposal for ZeroLink for to handling unequal input denominations based on fairly conservative assumptions, however I haven't yet finished writing it up. I believe that would hopefully improve its usefulness for handling change outputs of arbitrary sizes, while only trading off throughput (i.e. time to finish a mixing round, which is still arguably reduction in the anonymity set size for a given wallclock time interval, but not in terms of discrete time as measured by number of mixes).

• Another set of questions is:

These give me a lot to think about... Some very preliminary thoughts:

• Do we have enough insights about the protection provided by the mixing services?

While I certainly don't, the approach I was going for attempting to find a path of least resistance for substituting the (lack of) protection afforded by wallets whose functionality is focused on other features (ease of use, niche platforms, special purpose applications) for the arguably better protection afforded by mixing wallets.

• Is it better if payment outputs are directly sent to Bob's fungibility wallet?

I would think so, but I don't see a simple way to achieve that on a technical level (apart from the fact that this proposal requires fungibility wallets to be able to export BIP32 keys, which is more generally useful for receiving payments into them).

This question also seems important for BIP79, which I see as a sort of "transpose" of this proposal, but for the receiving side (incidentally, I think the two proposals can complement each other for payment processing, i.e. receiving payments via BIP79 into a forwarding wallet, but in this case more for security reasons - forwarding in order to limit the amount of funds spendable by the payment processing service hot wallet)

• Is is better if all transactions are done through a mixing service?

If I understand what you mean by this, then I believe that yes, i.e. like patient sendingpayments in joinmarket, or the GroupSend proposal for Wasabi, which is similar to the broken bc.i coinjoin, but which can still increase privacy if it only spends anonymized inputs. If I'm not mistaken Bisq can already be used in this way (it can fund transactions from its internal wallet or using an address with an external wallet), and this would be preferable to this change forwarding approach, but I can't think of other examples.

However, the barriers to achieving this seem very high in terms of design and implementation complexity, so the intent behind this proposal is to offer an incremental improvement in this direction.

• Can we make any assumption about how the receiving wallet will manage the incoming funds? What are the risks if we can't make this assumption ?

I believe that we can't, not in general, and that the risks are high, but this is part of the implicit design goals of fungibility wallets, so I have made that assumption in the proposal, and that also must be qualified.

In conclusion, I think this BIP should take a more "holistic" approach and should include a detailed analysis/specification of the mixing component (requirements, risks, etc).

Thank you for taking the time to review! I will do my best to iterate on it, this criticism is all on point. Regretfully I don't think I can answer these questions, but at the very least I can make it clearer that these questions are relevant to the proposal.

• Are we ready to concede a 'defeat' on the front of the 'change output' heuristics for the sake of an improved unlinkability of transactions? (I don't know the right answer to this question but it might be a good strategy... or not)

I don't think conceding defeat is a clear requirement, but rather that it depends on the form of the forwarding wallet's transactions, the fungibility wallet's handling of received funds, and the behaviour of the counterparty. For example, as a hypothetical, if Alice buys coffee from Bob, and both parties use Joinmarket afterwords, I believe that would actually reduce the effectiveness of the change output heuristic, but still allow Alice to buy the coffee, fully on chain as satoshi intended, without needing to use the sendpayment script at the point of sale.

This is definitely a concern for wallets like Bisq which use a recognizable transaction format (though if I'm not mistaken, it's been a while since I read the code, it also uses a consistent output ordering so perhaps it's not a good example since no heuristic would be necessary there...)

I have three questions about your interesting proposal. I would be so grateful if you answer me. First, as you mentioned your proposal is designed to minimize the required changes to forwarding wallets. How does your proposal minimize changes?
My second question is about mixing. Does fungibility wallet interact with mixing services to do mixing? If yes, which mixing service do you prefer?
And my last question is about something that @LaurentMT said. He said "mixing step creates a pattern which, at the level of a single transaction, allows to identify the payment output from the change output with almost 100% certainty." As far as I understood change output is sent to fungibility wallet and pass through multiple mixing transactions. Is this the something that determines which output is change output?

First, as you mentioned your proposal is designed to minimize the required changes to forwarding wallets. How does your proposal minimize changes?

Most BIP32 code I've seen do key or address derivation in a fairly general way, so the main change to the transaction building should just be dependency injection (instantiating an address chain separate from the one that is built from the wallet seed), and apart from this change everything else should be identical (same script/transaction structure).

The UI for the setup phase is more complex to implement, as that would require additional interfaces and new code functionality, but that too can reuse the change derivation code to ensure compatibility.

Compared to more comprehensive functionality like BIP47, or a specific transaction format, and based on my familiarity with wallet code (mostly reading bitcoinj based wallets), this seems like a relatively low complexity change.

My second question is about mixing. Does fungibility wallet interact with mixing services to do mixing? If yes, which mixing service do you prefer?

Right now I think the most appropriate implementation of a fungibility wallet is JoinMarket in tumbler mode.

I have also been working on some proposed changes to zerolink which if implemented would make Wasabi and Samourai appropriate for the kind of mixing I'm suggesting.

Apart from these I am not aware of any fungibility oriented wallets, from the point of view of this proposal I treated it as a black box. However, as @LaurentMT suggested, I should better qualify what I mean. I've been putting off revising this for now, as I've been focusing on some other things (and in general I find it much easier to write spaced out in time), so in the next iteration of this document I will try and clarify what criteria a fungibility wallet should meet in order to fulfill this role.

Secondly, I don't think this is the only use case for this specific proposal, since in terms of the technical details it's really just a way of checking and configuring two BIP32 wallets to share a public chain, it might also be useful for other use cases (e.g. configuring a watching wallet like sentinel or electrum personal server, or setting up something to receive payments directly to cold storage). This lack of clarity is another deficiency in the scope of the document that I'd like to improve.

And my last question is about something that @LaurentMT said. He said "mixing step creates a pattern which, at the level of a single transaction, allows to identify the payment output from the change output with almost 100% certainty." As far as I understood change output is sent to fungibility wallet and pass through multiple mixing transactions. Is this the something that determines which output is change output?

Considering just a single transaction, it should not be possible to distinguish, given that the script format of the forwarding wallet is retained, apart from the specific public key nothing is different.

However, if these change outputs are then directly used in coinjoin transactions but the payment outputs are not, this creates a pattern can be used to infer which outputs are change outputs and which aren't.

My assumption was that this kind of thing would happen anyway in wallets with no coin control, but instead of the change outputs being coinjoined afterwards, they would just be used as inputs to transactions of the same kind, so not just identifiable as change, but also clustered. In the ideal case, if the receiver (Bob in the examples above) provides an address from a fungibility wallet too, and then the change output would only be identifiable if the transaction follows a specific format (cf. output ordering discussions, like BIP69 or ideas about randomized orders, and BIP126 for relevant discussions)