** As it stands, this protocol seems not to achieve the intended goal at all, see https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-November/018278.html **
Leaving it here for now, but obviously read the above if you read it!
==================================
Makers need a reasonable guarantee that their offers will not be censored, and therefore will be available to any taker requesting the joining service.
This is today, in Joinmarket specifically, somewhat achieved through the use of redundancy. In particular, 2 or sometimes 3 independent IRC servers are used simultaneously, and the makers and takers use digitial signatures to ensure that spoofing other users is not possible. This model is limited however; not only because IRC servers are not ideal for this purpose (being principally designed for human text chat, not bot traffic), but also because at the least, we trust that the IRC servers are not colluding together to selectively censor individual participants. The risk of censorship of that type is ameliorated by the fact that makers connect (almost exclusively) over Tor, to the hidden service / onion of the IRC servers. Still, since these bots persist and use the same nick over multiple servers, and since their offering amounts, fees etc. may sometimes fingerprint them, selective censorship is possible, again, if there is collusion.
In this document I present a sketch of an approach to make such selective censorship very difficult using cryptographic blinding as well as a proof-of-misbehavior approach; the former making selective censorship very difficult to achieve, and the latter strongly disincentivising it.
Note that here "selective" is a very important word, but total censorship and random censorship should also be ineffective and disincentivised, for fairly obvious reasons, although I will outline them.
If the desired effect is achieved, we can reasonably run Joinmarket or a similar system on a single bulletin board server, with the caveat that it will need to be sufficiently easy to stand up a new instance; this should be true as long as the code is open source and the resource requirements are not excessive.
It should also be noted that the design here is of course not specific to CoinJoin, but would also work the same way for CoinSwap (so "bitcoin fungibility markets") and perhaps other similar bitcoin-native systems whenever the concept of a "liquidity maker" (henceforth "maker") applies, so perhaps second layer also (this has not been investigated).
The idea for using this in Joinmarket was elucidated by Chris Belcher here. I here treat this as a generic algorithm of the following type: there are two entities, prover P and verifier V.
- Creation: P creates a bitcoin transaction, amount A and paid into scriptpubkey: (key X and timelocked until t=T).
- Proof of fidelity: For a given message m, it can be signed with X and (sigma, m, X) given to V (X may be implicit).
- Verifier checks conditions: (does sigma verify as a signature on m against X, does m not conflict with an earlier message m' on X, is t < T); if all conditions verify as true, then V returns true.
Notes: there are clearly several ways these fidelity bond utxos could be instantiated in current and future (tapscript) versions of Bitcoin Script/ protocol. We will assume current p2wsh on a script of this type, or sometimes postulate a tapscript version, in which the pubkey is revealed on-chain before spending. Also, note there is a cost on the verifier here, who has to look up the utxos on chain, but notably, only the utxo set. Finally, "conflicts with an earlier message" will clearly be context-specific.
Another important practical detail about fidelity bonds of this type (covered in the above gist) is hotness of the keys, and related to that, expiration.
The ring signature primitive allows the owner of a single private key to sign a message "in conjunction" with the holders of any number of other private keys, without the signer knowing those other private keys, and without the verifier of the message knowing which private key of the set, was used, only validating that one of them was. There are a host of complex variants, one important property that they usually have is 'spontaneity', i.e. that the owners of the other private keys do not have to interact or cooperate with the signer.
See this earlier gist of mine for some ideas about how ring signatures could be used in conjunction with fidelity bonds, in a way that could prevent dual-use of the same key, if your goal was to thus sign a single bot or agent identity, in a market like Joinmarket.
But in this document, the idea is different, and simpler: we will not require banning of dual-use with cryptography (note how that is absolutely required in a ring-signature based cryptocurrency), because we are only using the ring signature delinking effect as a first step, to make fraud provable. So we can use any of the variants of the basic AOS Schnorr ring signature, see my earlier blog post for a detailed review of a lot of these ideas.
Notes: ring signatures have two practical considerations that have to be borne in mind: size; the above mentioned flavor tends to be O(N) in the number of pubkeys. As long as we are talking about 10^2 - 10^3 pubkeys this can be workable (in lower interactivity contexts), but for very large set a more advanced cryptographic construct may be needed. Second, note that pubkeys must be publically available; this could mean, for ring signatures on pubkeys-of-utxos, taproot, or some public database (even embedded into the blockchain).
We first postulate a single centralized server S that will host the bulletin board (we will also use 'S' for the public key of the server), which will list offers in the same way as the current Joinmarket "trading pit" (currently to be seen on IRC server public #joinmarket-pit channels). Each offer consists of some list of data (amounts, fees etc), connected to a pubkey (currently - that is embedded in the IRC nick, similar to how it's done in Tor hidden services). We discuss the origin of these pubkeys next.
As was discussed in belcher's gist, the creation of fidelity bond timelocked outputs would desirably be offline for better security (e.g. a hardware wallet), hence real-time signing with those keys may be worth avoiding. Since the protocol in this section must be carried out regularly, whenever makers want to create or update offers (which is necessary, approximately, after every transaction in a system like Joinmarket), it makes sense to have the fidelity bond key F delegate to a medium-term-expiring key D with a signature on the message (D, expiry). Notably hardware wallets may easily support simple message signing (but not more exotic constructs like PoDLE).
Assuming therefore that participant makers M have such a key D_M, they can upload them to the server via an anonymous Tor connection, and/or publish them to another server, along with the signature of F_M as mentioned above.
From now on, we address the central question: how do makers, who have such keys D_M uploaded and widely known, upload market offers to S such that they have security that their offers won't be censored?
M sends in their request (over Tor or any anonymising network):
- A commitment (let's say, hash-based, but could be Pedersen or similar): C = H(offer string, z, q) where:
- H is a hash function like SHA256, "offer string" is the normally formatted set of request data like min and max amount, coinjoin fee etc
- z is a signature using the private key of D_M on a fixed tag or null string "", i.e. a proof of knowledge of that private key
- q is a random value for blinding.
Note that this commitment does not reveal the contents of the offer, but fixes it.
- A ring signature sigma on the message C, formed using the private key of D_M and using the ring of all publically known keys D, or if that is too large, a random subset of the known keys D. For example, in the case of 100 keys, a typical AOS style ring signature would consist of a single 32 byte hash plus 100 32 byte 's' values, leading to about 3kB of data in the request, which is not unreasonable.
Thus M sends to S: (C, sigma).
If the server S simply ignores the request, or sends a malformed response, this is "total censorship" discussed below under practical considerations (because no part of the tuple (C, sigma) reveals any information at all about the offer or who is making it).
Assuming the conversation continues, S sends:
- receipt r_S = signature on the message (C ,sigma).
The last step of communication is for M to simply open their commitment: they send: (q, z, offer string, D_M).
Then S carries out checks:
- Does H(offer string, z, q) =?= C
- Is D_M part of the set {D}?
- Does sig-verify(z, null message/tag, D_M) =?= true
If all checks pass, then S will update (or make a new entry) in the orderbook for D_M, having been satisified that this offer was made by the correct party. Note how the cryptography did not prevent S from linking this requester to the specific identity D_M, but only gave to that requester a proof that the request was validly made, and accepted, before the linking occurred.
The main purpose of the above protocol is to achieve the following: if S, on receipt of the third message (q, z, offer string, D_M), decides that they don't want to accept that new offer or update, or chooses to not publish it, then the maker M has r_S(C, sigma) and can publish: (r_S, D_M, q, z, offer_string) as proof that they were censored, pointing out that this offer is not available on the public orderbook, but should be. Any individual case of such a thing would be problematic, for example, the orderbook must be checked real time, but certainly any pattern of behaviour like this would mark S as a bad actor, in a publically verifiable way.
As was briefly mentioned in the previous section, the server is of course never forced to do anything at any stage; if they ignore the first message, or send an invalid response, this is basically equivalent to DoS (not in the usual client side sense, perhaps call it "jamming"); since the server has no way to distinguish the requests, he cannot do this selectively, so the broad community of users will see the behaviour and agree the server cannot be trusted (or .. outage; the point is, the community can agree because the behaviour is not selective).
The server could also "selectively" censor by just throwing out "some fraction" of requests and not responding. This is of course unlikely to achieve any goal apart from annoyance.
A more serious critique would be something like: suppose there are ~ 100 makers currently active with F keys, and 80 of them are colluding with the server operator to get rid of the other 20. In this case, the colluders could let S know in advance which blinded requests belonged to them, and have him ignore any other requests (thus no "proof of fraud"). However persistent behaviour like this would be recognized fairly quickly, because the system is open. However, it is important to point out the cryptographic construct in this document is not really helping with this problem, it is specifically designed to address the server actively targetting a user or set of users with censorship. It cannot prevent blanket censorship, and the scenario of 80 insiders is just a very extreme version of the same thing (essentially: censor everyone in the world except those 80).
- How difficult is it to run such a server?
Bandwidth usage may not be too high, but such a server would need to resist DoS fairly effectively.
- How big are the ring signatures?
This is a potential stumbling block, above a few hundred F keys for makers. If we have a few thousand, then the protocol must be extended to allow makers to choose a random subset of perhaps a few hundred at most, over which to form a ring signature.
- Public storage/accessibility of the fidelity bond keys F and their delegated keys D
This seems like an important side-element; with delegation, the existence of taproot doesn't change the scenario that much, because we still need all parties to be able to easily access the delegated key set {D}.
I got a comment on mastodon, I will replicate here so I can more easily give a very detailed answer, as I think there are some practical considerations that weren't yet mentioned:
from @roshii@bitcoinhackers.org:
My initial response:
But further, as I think it needs discussing more:
Here's an interesting comparison: if you use a server for coinjoin coordination (ie the tx construction process), then there is always the risk, however small, of the server batching you with counterparties it owns or colludes with.
Now imagine a server like in the gist, where it is colluding with some large group to only show counterparties it colludes with (they still need fidelity bonds): it looks at first glance like the same risk, but it's different:
The orderbook is a continuously updated public object, where inability to update by valid participants will be broadcast as an alert, whereas a single tx construction is a one-shot deal unconnected with any public information. So if the server colludes and censors the orderbook, it could get away with it for some short period, but the alert would be raised before any meaningful number of txs were arranged, unlike the former case, where the server could do this indefinitely (and of course, single coinjoins failing to provide meaningful anon sets is not at all a disaster ... which is one reason why even the former server-as-tx-coordinator construct is far from unworkable).
I would envisage some additional details: takers obviously request the orderbook anonymously, and may connect to makers over private channels (makers can easily run their own onions for this) to do the tx coordination. This could help with the scalability problem of doing large scale e2e encrypted messaging over a server, as well as spread risk, and is probably simpler than using a full p2p network, especially if over something like Tor.