If timelocked outputs are used as fidelity bonds, there is some inevitable degradation in the anonymity of users of a system that requires such bonds. Part of this would be entirely unavoidable - in that when the utxo is spent, the CLTV nature of the scriptPubKey must be revealed, and in most scenarios this would probably watermark that the utxo was being used for a fidelity bond purpose. But what might be avoided is the tracing, or linking, of a particular utxo used repeatedly for the same purpose.
To make the issue clearer, consider the specific case of Joinmarket, and the recent proposal on fidelity bonds by Chris Belcher [1]. Here, the fidelity bond would be used to sign an ephemeral identity used on a message channel. The user, having committed funds to the bond, would perforce re-use that same bond every time he reconnects to the trading pit and so what is currently a completely ephemeral identity (it can be changed as often as one wants) may now be required to stay persistent for the lifetime of the fidelity bond. While this is not unacceptable, it may be undesirable, and leaks a little more information about the agents behind these maker identities. Currently makers can regularly restart with different ephemeral identities ('nicks') and post randomized offer advertisements, so that it is at least very difficult to trace them over time (while they hold a single wallet, they are using different combinations of typically 20-40 utxos, so trivial linkage there isn't possible in general).
The remainder of this gist outlines a partial solution to this problem which could hopefully address the troublesome degradation in anonymity over the whole range of cases where a fidelity bond might be useful (so, not only Joinmarket, as recently discussed).
To lead into the idea, I'll outline a slightly simpler variant of the idea, and how it might work for some applications but not for fidelity bonds.
Suppose your goal was to be able to brag you had ~ 10 BTC (stored in a single utxo for simplicity), but not reveal it. Unfortunately, a direct application of the idea of a ring signature doesn't apply. The problem is that if you simply scan for all utxos with ~10BTC (say 5BTC to 15BTC), none of those unspent outputs reveal a public key for you to add to the key set over which you form the ring signature. So a completely spontaneous ring signature formation fails.
Let's suppose for a moment that this problem is artificially solved - that somehow magically you can convince all owners of such outputs to publish their pubkeys. What would you do?
For example, you could construct a Schnorr based AOS ring signature of some arbitrary message (say you're challenged by someone who doesn't believe you're rich). They would see that the signature is indeed valid for 1 of the pubkeys in the set, so with access to the blockchain they can independently verify that you are indeed 'rich' in the agreed sense. How much this reveals about you will depend of course on how many such keys you managed to include in the sig. The particular ring sig variant suggested is unfortunately linear in the number of pubkeys so for very good anonymity it may be a bit unwieldy but that might not matter too much for this use-case.
Of note: since this kind of signing is a kind of 'existence proof', it doesn't really matter that one can repeatedly sign against the same utxo without the recipient of the signature knowing about re-use. We aren't trying to enforce any scarcity in this use-case. This however, is, emphatically a problem in some other users of ring signatures - including the one intended in this gist.
The term 'linkable' can get very confusing here. I've gone through, in some technical detail, the different types of ring signature designs in a blog post [2] for those interested in more of a deep dive.
For now, note that to prevent someone signing twice with the same key, but still preserve the anonymity of which key they're using, a design from Liu-Wei-Wong sometimes called "LSAG" was created. This same design is used in Monero (extended to "MLSAG"). So we use in this context "linkable" to mean that whenever two ring signatures are produced, either on the same keyset or on any keyset (that's for a cryptocurrency), that double-usage can be revealed, and in the case of a cryptocurrency can be prevented from creating a double-spend of the same coins.
For the rest of the acronym, the "S" in LSAG refers to spontaneity - the ability to construct the ring signature without the participation of other keyholders. Generally this means you can "grab the keys from somewhere else", depending on the context. The "AG" means "anonymous group".
It's critical to understand though, that in these LSAG designs, even though this "linkability" is created, it does not mean that you can determine the key being used, even if an accidental or deliberate 'double-sign' event occurs.
In the bragging-rights signature scenario we already mentioned the problem of knowing the keys that hold coins (addresses don't reveal keys). My motivation for writing this came out of thinking: suppose everyone simply published keys, would it work? It seems that it works rather well.
If a whole bunch of users are interested in creating fidelity bonds, for any purpose, they could:
- Create a timelocked utxo within a particular value range
- Connect anonymously (e.g. Tor) to a bulletin board (e.g. Tor HS) and publish: utxo, pubkey, timelock value (so scriptPubKey preimage recreatable).
Notice that everything is verifiable by any reader of this information on the blockchain, and there is therefore no trust in the bulletin board. The bulletin board could conveniently sanity check the information, then arrange into groups, for example:
Set 1: 0.1-0.2 btc Set 2: 1.0-2.0 btc Set 3: 10.0-20.0 btc
.. etc. By arranging into non-contiguous groups of some reasonable range, you can achieve a tradeoff between large-ish anonymity sets and convenience for the users (they could make a 1 in 1 out tx for example which is ideal).
Having done this, when time comes to make a "claim" against this fidelity bond, so to speak, the user could:
- Read from the bulletin board all keys posted for their given range
- Verify each as genuine
- Create an LSAG of the LWW- type or most likely Adam Back's variant of that (see blog post [2] for details) with that keyset
- Post that ring signature for their use case, knowing that the exact owner is not revealed
An attractive aspect of this (but one which will require careful thought) is that we can reuse a single fidelity bond utxo for more than one system. For example, one system might be Joinmarket and the other might be some CoinSwap implementation. Here, since we are interested in disincentivising Sybil attacks on each separately, it makes sense to allow re-use.
To do so, the same anonymous bulletin board as discussed above can be used. This has the substantial advantage of allowing larger anonymity sets for the signatures where practical because more users would be involved.
The ring signatures for each application use-case could be delinked, for example, the key image I = x_i * H(P_i) as per the Back variant of LWW could be modified to include a tag like: I_1 = x_i * H(P_i || "tag1"), I_2 = x_i * H(P_i || "tag2"), so that we still have the "double use prevention" feature in each application separately, but they don't conflict.
Note that the Back variant of the LWW LSAG is asymptotically about 32 bytes per participant (pubkey), so it could get pretty large pretty fast in applications where signatures need to be pinged back and forth in quasi- real time (as in Joinmarket). We might need to find a more practical version of this idea if that is indeed too large (and unhelpfully, the relation is: more anonymity, more space/time cost). Perhaps some ZKP variant might work better; it's good to leveragte the fact that this is not a matter of blockchain consensus and is very much all client side crypto.
======================
[1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-July/017169.html
[2] https://joinmarket.me/blog/blog/ring-signatures/ (subsection "Back 2015; compression, single use")