Bitcoin transfers value on a public ledger of transactions anyone can verify. Coin ownership is defined in terms of public keys. Despite potential use for private transfers, research has shown that users’ activity can often be traced in practice. Businesses have been built on dragnet surveillance of Bitcoin users because of this lack of strong privacy, which harms its fungibility, a basic property of functional money.
Although the public nature of this design lacks strong guarantees for privacy, it does not rule it out. A number of methods have been proposed to strengthen privacy. Among these is CoinJoin, an approach based on multiparty transactions that can introduce ambiguity and break common assumptions that underlie heuristics used for deanonymization. Existing implementations of CoinJoin have several limitations which may partly explain the lack of their widespread adoption.
This work introduces WabiSabi,1 a new protocol for centrally coordinated CoinJoin implementations utilizing keyed verification anonymous credentials and homomorphic value commitments. This improves earlier approaches which utilize blind signatures in both privacy and flexibility, enabling novel use cases and reduced overhead.
Bitcoin transactions transfer funds by consuming unspent outputs of previous transactions as inputs to create new outputs . The protocol rules enforced by the network ensure that transactions do not arbitrarily inflate the money supply and that outputs are spent at most once. While some newer cryptocurrencies use more sophisticated approaches to define such rules, in Bitcoin the amounts, as well as the specific outputs being spent, are broadcast in the clear as part of the transaction. This presents significant challenges to transacting privately2 as shown already in some of the earliest academic studies of Bitcoin .
A fundamental requirement for electronic money is double-spending prevention, and Bitcoin’s main innovation was preventing double-spending and illegal inflation without relying on a trusted authority, thereby disintermediating transactions. This is in contrast to online e-cash schemes where a server authorizes transactions or offline schemes where the identity of the double spender is revealed allowing the authority to intervene after the fact. Bitcoin’s relative success in comparison suggests that the lack of trusted third parties factored more strongly in its adoption than the comparatively stronger privacy guarantees provided by the (possibly revocable) transaction anonymity traditionally associated with e-cash .
These shortcomings in privacy affect Bitcoin users, both individuals and organizations, leaving casual users especially vulnerable since power to surveil and resist surveillance is unevenly distributed . Even without address reuse, which is widespread , transactions still reveal some information. This makes clustering of outputs according to heuristics practical , with wallets of some well-known entities generally considered public knowledge. Exchanges complying KYC/AML requirements additionally must collect and safeguard information that links transactions to personally-identifying information.
The conditions for spending an output are specified in its
scriptPubKey, typically requiring that the spending transaction be signed by a particular key. The signatures authorizing a transaction usually commit to the transaction in its entirety, making it possible for mutually distrusting parties to jointly create transactions without risking misallocation of funds: participants will only sign a proposed transaction after confirming that their desired outputs are included and the transaction is only valid when all parties have signed.
Chaumian CoinJoin  is a privacy-enhancing technique that uses the atomicity of transactions and Chaumian blind signatures  to construct collaborative Bitcoin transactions, also known as CoinJoins. Participants connect to a server, known as the coordinator, and submit their inputs and outputs using different anonymity network identities. That alone would provide anonymity but since outputs are unconstrained it’s not robust against malicious users who may disrupt the protocol by claiming more than their fair share in the transaction outputs. To mitigate this the coordinator provides blind signatures representing units of standard denominations in response to submitted inputs. Clients unblind and submit the output with valid signature, which allows the to verify that an output registration is authorized without being able to link it to the corresponding inputs.
The use of standard denominations in the resulting CoinJoin transaction obscures the relationship between individual inputs and outputs, making the origins of each output ambiguous. Unfortunately, standard denominations limit the use of privacy-enhanced outputs for payments of arbitrary amounts and result in a change output which maintains a link to the non-private input.
We present WabiSabi, a generalization of Chaumian CoinJoin based on a keyed-verification anonymous credentials (KVAC) scheme . The use of KVACs replaces blind signatures’ standard denominations with homomorphic amount commitments, similar to Confidential Transactions , where the sum of any participant’s outputs does not exceed that of their inputs while hiding the underlying values from the coordinator. In addition to being more flexible, this improves privacy compared to blind signatures and standard denominations since smaller inputs can be combined and change outputs created with the same unlinkability guarantees as those of standard denominations when using blind signatures.3 WabiSabi builds on a successfully deployed and proven approach, aiming to reduce barriers to further adoption  by removing restrictions and strengthening unlinkability.
WabiSabi can be instantiated to construct a variety of CoinJoin transaction structures that depart from the standard output denomination convention, as in SharedCoin4 and CashFusion5 style transactions and Knapsack  mixing. Payments from CoinJoin transactions are possible which enhances sender privacy, as are payments within CoinJoin transactions, improving privacy for both sender and receiver and potentially hiding the payment amount. Additionally, restrictions on the consolidation of inputs can be removed, and there are opportunities for reducing unmixed change, relaxing minimum required denominations, and improved block space efficiency compared to what is possible with blind signatures.
The rest of this paper is organized as follows. We present necessary background knowledge about privacy issues of Bitcoin in Section 2. In Section 3 we provide some preliminaries on our applied cryptographic building blocks. We introduce our system model in Section 4. In Section 5 we introduce our protocol, WabiSabi, at a high-level, while in Section 6 we describe in-depth the cryptographic details of WabiSabi. In Section 7 we argue about the security and privacy of WabiSabi. A report on our preliminary implementation is provided in Section 8. We review related work in Section 9. We outline ongoing and future work in Section 10. Finally, we conclude our paper in Section 11.
In this section, we provide an introduction to Bitcoin privacy issues and proposals to enhance transaction privacy. We detail current limitations of Bitcoin privacy-enhancing tools and motivate our work.
Bitcoin is a pseudonymous cryptocurrency : coins are associated with so-called addresses, which encode the spending conditions of the coin (their
scriptPubKey). Bitcoin transactions spend coins as inputs and create new coins output in place of the spent ones. The Bitcoin protocol mandates the rules of a valid transaction (no double-spending, valid signatures, etc.), which is verified by all nodes of the network. Since every transaction is recorded in a public ledger, the flow of money is traceable. Several idioms of use allow one to cluster addresses likely to be controlled by the same user. Many heuristics were devised in previous work . The most commonly used heuristic to cluster Bitcoin addresses is the common input ownership heuristic. It states that in any Bitcoin transaction, all the inputs are likely controlled by the same user. This heuristic already facilitates a fine-grained clustering of Bitcoin addresses, with alarming accuracy.
CoinJoin transactions aim to contradict to the common ownership heuristic, because multiple users collaboratively create the transaction. There are several types of privacy-enhancing techniques in Bitcoin, e.g., PayJoin,6 CoinSwap . However, in this work, we solely focus on CoinJoins. In an equal-amount CoinJoin transaction (see Figure 1), each user contributes at least one input and receives at least one output with the same amount as the other users. Assuming the output types are uniform individual outputs differ only in the keys associated with them, which are indistinguishable from uniformly random data. Consequentially it is not possible to link inputs to specific mixed outputs. The privacy of such outputs can be modeled using -anonymity  with amounts and script types as quasi-identifiers, but this analysis becomes rather complicated in a broader context than that of a single transaction in isolation because the graph structure can reveal additional information.
Several CoinJoin protocols have been implemented and many more proposed, with varying privacy and trust models. For an overview see Section 9. ZeroLink  is one such protocol implemented by Wasabi, the most popular Chaumian CoinJoin implementation for Bitcoin. Although the coordinator must be trusted to ensure availability, but no trust is required with regards to safeguarding users’ funds or keeping mapping between inputs and outputs private. The protocol breaks down into three main phases:
Input Registration: Users register their inputs along with proofs (digital signatures) that they own those inputs. Additionally, users provide their change outputs and blinded outputs to the coordinator. The coordinator blindly signs the requested blinded output.
Output Registration: Users unblind their signatures received from the coordinator and register their outputs. We note that input and output registrations are completed using different network identifiers (Tor circuits) to ensure network-level privacy as well.
Signing: Users receive the unsigned CoinJoin transaction from the coordinator. If it contains their requested inputs and outputs, users sign the transaction and send back to the coordinator their signature(s). If all signatures are received, the coordinator broadcasts the final, signed CoinJoin transaction.
In this work, we aim to improve on the ZeroLink protocol as implemented in Wasabi. We identify several privacy shortcomings and inefficiencies of Wasabi CoinJoins. Specifically, we are interested in quantifying block-space and other inefficiencies stemming from the imposed minimum denomination. These metrics comparing Wasabi, Samourai’s Whirlpool,7 and other apparent CoinJoin transactions are provided. The “Other” category includes JoinMarket,8 but also has an inherent false positive error given these transactions are identified heuristically. We collected every equal output CoinJoin-like transactions from the Bitcoin blockchain until May 22, 2020. Wasabi and Samourai CoinJoin transactions are trivial to detect. A transaction that has more than equal amount outputs are surely Wasabi CoinJoins, while a Samourai CoinJoin transaction has the same structure, with five equal amount outputs of a fixed size, three inputs of exactly the same amount, while fees are paid by two inputs of a slightly higher amount which are direct descendants of a so called “tx0,” a transaction that prepares outputs for mixing and pays the coordination fees. However, other CoinJoin transactions, e.g., JoinMarket, are more difficult to identify . Heuristically, we deem every transaction being in the “Other” CoinJoin transaction category if they simultaneously satisfy the following conditions:
There are at least two equal amount outputs. We refer to the number of equal amount outputs as the size of the anonymity set.
The number of distinct public keys of the inputs is at least the size of the anonymity set.
The number of distinct public keys of the outputs is at least the size of the anonymity set.
The first requirement ensures that transactions in the “Other” category are indeed privacy-enhancing transactions. The second and third requirements filter out batching and exchange deposit/withdraw transactions. However, we acknowledge that this heuristic might incur a few false positives as well as false negatives.
A cross platform tool for the reproducible analysis of Bitcoin privacy-enhancing transactions was developed and released 9 to facilitate this as well as further research. We report our findings in more detail.
Due to the nature of blind signatures, mixed outputs of Wasabi CoinJoins are restricted to a fixed set of multiples of a base denomination.10 This creates friction when sending or receiving arbitrary amounts of Bitcoin, as using fixed denomination generally creates change, both when mixing and when spending mixed outputs. Non-mixed change outputs in a CoinJoin are almost always linkable to their corresponding inputs. Therefore, every Bitcoin privacy-enhancing tool should aim to minimize the number of unmixed change outputs.
We define CoinJoin inefficiency as the fraction of non-mixed change outputs in a CoinJoin transaction. In Figure 2, we observe the large amount of non-mixed outputs of essentially all Bitcoin privacy-enhancing tools. Samourai has the lowest CoinJoin inefficency, since it always applies five equal amount of inputs and outputs. We note a sharp decline of CoinJoin inefficiency in Wasabi CoinJoins around January 2019 due to the introduction of multiples of the base denomination.
In order to participate in a CoinJoin, a user’s combined input amount must be greater or equal to the base denomination.11 We observe that considerable portion of CoinJoin inputs are less than this minimum denomination, see Figure 3.
Even when users are able to provide several smaller value inputs with a total value greater than the minimum denomination, the coordinator learns that those inputs belong to the same user. In an ideal mixing protocol, the coordinator should not obtain more information by coordinating the CoinJoin transaction than what the publicly available blockchain data reveals. This information removes many degrees of freedom when assigning non-derived sub-transactions  or link probability , reducing intrinsic ambiguity as well as the computational cost when evaluating potential links.
Furthermore, if users consolidate coins in an additional transaction before participating in a CoinJoin, then this link is revealed publicly based on the common input ownership heuristic .
Since users pay mining and coordination fees the base denomination is gradually reduced between rounds of consecutive CoinJoins. This makes it possible for users to mix several times without providing additional inputs. In Wasabi remixed coins are not required to pay coordination fees if they are very close to the base denomination, which introduces a perverse incentive to minimize coordination fees by remixing in quick succession in order, resulting in a smaller anonymity set than with time-staggered remixes.
The rigidity of the current transaction structure, i.e., fixed denominations, constrains users’ unspent transaction output set structure as well. These limitations force users to consolidate their coins (see Figure 6) and create additional intermediate outputs with constrained amounts when interspersing CoinJoin transactions with transactions that send or receive value.
Currently, Wasabi supports neither payments from a CoinJoin, nor payments in a CoinJoin. Payments from a CoinJoin would protect sender privacy and improve efficiency by requiring fewer intermediate outputs. Payments within a CoinJoin would protect both sender and receiver privacy, as well as undermine clustering heuristics since they are analogous to PayJoins. It would also improve privacy by introducing degrees of freedom in the interpretation of CoinJoins.
Hereby we give an informal and high-level description of applied cryptographic primitives. In the following, the security parameter is denoted as .
A commitment scheme allows one to commit to a chosen message while preventing them from changing the message after publishing the commitment. Secure commitments hide the chosen message until they are opened. We assume Pedersen commitments throughout this work.
:: generate a commitment to message using randomness .
:: verify the correctness of the opening of a commitment by checking . If equality holds the algorithm outputs , otherwise .
A message authentication code (MAC) ensures the integrity of a message and consists of the following three probabilistic polynomial-time algorithms:
:: generate a secret key for MAC generation and verification.
:: generate a tag on a message using secret key .
:: verify that tag is valid for message using secret key .
One might intuitively think of a MAC as the symmetric-key counterpart of digital signatures. They both have the same goals and similar security requirements, however a MAC requires a secret rather than public key to verify.
A very high-level, and hence somewhat imprecise, description of zero-knowledge proofs is provided. This protocol involves a prover and a verifier. A prover wishes to prove that a relation holds with respect to a secret input , called witness, and public input . Specifically, the prover wants to prove that without revealing anything about .
:: Given and the private witness the prover generates a proof . For the specific outputs of we use the notation of , with the witness and statement: .
:: The verifier is given the proof and with which they determine whether the prover knows a secret such that holds.
In this section, we introduce our system model. We present the participants of our mixing protocol. Subsequently, we describe our communication and threat models along with our high-level goals.
There are four components of the WabiSabi system: the users, the coordinator, the anonymity network nodes and the Bitcoin peer-to-peer (P2P) network nodes.
User: Numerous users wish to enhance their transaction privacy by collaboratively creating a CoinJoin transaction. Each of them registers at least one input and output in an unlinkable manner.
Coordinator: To avoid quadratic communication-complexity in the number of users , we apply a central, untrusted coordinator. The coordinator aids users in creating their CoinJoin transaction. The coordinator stores registered inputs and outputs. At last, it serves users with the final CoinJoin transaction for signing. Users sign the final transaction if and only if all of their registered input and outputs are contained in the transaction.
Anonymity network nodes: Users need to communicate with the coordinator in an unlinkable fashion. To that end, we apply onion-routing . Users send messages to the coordinator using a path consisting of multiple intermediary anonymity network nodes. Each anonymity network node only knows her preceding and succeeding destination along the path. Therefore, the coordinator cannot link users to a specific request or output registration.
Bitcoin P2P network nodes: Typically users do not run Bitcoin full nodes. Therefore, they rely on other full nodes to serve them necessary data from the Bitcoin blockchain. For instance, users invoke full nodes whenever they verify the inclusion of a CoinJoin transaction in the blockchain or query their own balance. Note, that for the sake of privacy, these queries needs to be made unlinkable as well.
We assume all messages (onion-routed messages, broadcast transactions, queries about the blockchain) are delivered with a maximum delay under the bounded synchronous communication setting . Furthermore, we assume all actors can access and read the current head of the blockchain to verify if transactions are appended to the blockchain. We remark that these are standard assumptions in the blockchain literature .
We assume that the cryptographic primitives (see Section 3) are secure. Specifically, we assume that the discrete logarithm is hard in the underlying group, as well as the validity of the random oracle model for hash functions. We further assume that adversaries are computationally bounded and can only corrupt at most of the consensus participants of the blockchain. We assume that users can always read the blockchain state and write to the blockchain. Also, we assume that the adversary can always read all transactions issued, while the transactions are propagating on the P2P network, and afterwards when they are written to the blockchain. We assume that the coordinator remains available throughout the entire mixing protocol. Last but not least, we presume that in case of onion-routed messages for network privacy, at least one intermediary on the source-routed path is not controlled by the adversary, i.e., users can achieve network-level privacy.
We state informally our desired security and privacy goals.
Availability: An ideal CoinJoin protocol should remain secure and should eventually complete successfully even if certain mixing participants are malicious or off-line.
Unlinkability: WabiSabi users aim to create outputs in a CoinJoin transaction, that have enhanced transaction privacy than their corresponding inputs.
Theft prevention: Mixing participants should not be able to obtain more funds from the CoinJoin transaction than they are rightfully entitled to.
Performance: We aim to create a high performance mixing protocol that supports computationally or bandwidth constrained users.
We remark that we consider network-level privacy as given. It can be achieved by using, for example, onion-routing  or mix-networks .
In this section, we provide a high-level overview of the WabiSabi protocol.
A CoinJoin round consists of an Input Registration, an Output Registration and a Transaction Signing phase. To defend against Denial of Service attacks it is important to ensure the inputs of users who do not comply with the protocol are identified so these inputs can be excluded from the following rounds in order to ensure completion of the protocol.
While identifying non-compliant inputs during Input Registration phase is trivial, there is no reason to issue penalties at this point.
Identifying non-compliant inputs during Output Registration phase is not possible, thus this phase always completes and progresses to the Signing phase.
During Signing phase, inputs which are not signed are non-compliant inputs, and they shall be issued penalties.
The protocol ensures that if the coordinator is honest the transaction would be valid once signed and honest participants would always agree to sign the final CoinJoin transaction as it would not misallocate their funds. Anonymous credentials allow the coordinator to verify that amounts of each user’s output registrations are funded by input registrations without learning specific relationships between inputs and outputs.
The coordinator issues anonymous credentials  which authenticate attributes in response to registration requests. We use keyed-verification anonymous credentials (introduced in ), specifically the scheme from  which supports group attributes (attributes whose value is an element of the underlying group ). A user can then prove possession of a credential in zero-knowledge in a subsequent registration request, without the coordinator being able to link it to the registration from which it originates.
In order to facilitate construction of a CoinJoin transaction while protecting the privacy of participants, we instantiate the scheme with a single group attribute which encodes a confidential Bitcoin amount as a Pedersen commitment. These commitments are never opened. Instead, properties of the values they commit to are proven in zero-knowledge, allowing the coordinator to validate requests made by honest participants. In ideal circumstances, the coordinator would not learn anything beyond what can be learned from the resulting CoinJoin transaction but despite the unlinkability of the credentials timing of requests or connectivity issues may still reveal information about links.
To aid intuition we first describe a pair of protocols, where credentials are issued during input registration, and then presented at output registration. denotes the number of credentials used in registration requests, and constrains the range of amount values.12 For better privacy and efficiency, these are then generalized into a unified protocol used for both input and output registration, where every registration involves both presentation and issuance of credentials. This protocol is described in detail in Section 6.
In order to maintain privacy clients must isolate registration requests using unique network identities. A single network identity must not expose more than one input or output, or more than one set of requested or presented credentials.
For fault tolerance, request handling should be idempotent, allowing a client to retry a failed request without modification using a fresh network identity, or one which was previously used to attempt that request (the same network identity should not be associated with more than one input or output).
The user submits an input of amount along with group attributes, She proves in zero-knowledge that the sum of the requested sub-amounts is equal to and that the individual amounts are fall within in the allowed range.
The coordinator verifies the proofs, and issues MACs on the requested attributes, along with a proof of correct generation of the MAC, as in Credential Issuance protocol of .
To register her output the user randomizes the attributes and generates a proof of knowledge of valid credentials issued by the coordinator.
Additionally, she proves the serial number is valid. These serial numbers are required for double-spending protection and must correspond but unlinkable to a specific .
Finally, she proves that the sum of her randomized amount attributes matches the requested output amount , analogously to input registration.13
She submits these proofs, the randomized attributes, and the serial numbers. The coordinator verifies the proofs, and if accepted the output will be included in the transaction constructed by the coordinator.
In order to increase flexibility in a dynamic setting where a user may not yet know her desired output allocations during input registration, and to allow setting a small14 value of as a protocol level constant (ensuring that requests are uniform) we can generalize input and output registration into a single unified protocol for use in both phases, which also supports reissuance. For complete definitions see Section 6.
The user submits valid credentials and credential requests, where the sums of the underlying amount commitments must be balanced (Figure 9).
To prevent the coordinator from being able to distinguish between initial vs. subsequent input registration requests (which may merge amounts) credential presentation should be mandatory. Initial credentials can be obtained with an auxiliary bootstrapping operation (Figure 10). A more sophisticated approach would be to prove knowledge of a valid MAC or that the amount attribute has value a value of zero, but because the input registration phase starts synchronously when enough users have indicated their intent to participate this would not actually save a round trip in practice.
The user fetches the finalized but unsigned transaction from the coordinator. If it contains her registered output she will sign her inputs and submit each signature separately using the network identity used for the corresponding input’s registration.
To illustrate the above protocols, Figure 11a and Figure 11b show how a user might register inputs and outputs with the simplified protocols, where credentials are only requested at input registration and presented at output registration. Figure 11c and Figure 11d show the unified protocol, when credentials are both presented and requested in every request.
Input and output registrations are depicted as vertices labelled by , with a double stroke denoting output registrations. A credential is an edge from the registration in which it was requested to the registration where it was presented, also labelled with the amount. The vertex’s label must be equal to the balance of the labels of its incoming edges and its outgoing edges. Note that edges and their labels are only known to the owners of the credentials. For simplicity, we omit credentials with zero value.
In Figure 11a, Alice first registers an input of amount and requests two credentials with amount and in a single input registration request. At the output registration phase, Alice, with a different network level identity registers one output with each.
The flexibility of the credential scheme allows to achieve the same outputs originating from multiple different inputs. For instance, in Figure 11b, Alice registers inputs (with different network identities) of value and . The input of value is broken up to credentials of value and . At output registration Alice then combines her credentials of value and to be able to register an output (with yet another network identity) of value . Note that individual credential amounts are not known to the coordinator, which only learns their sum.
In the unified protocol at every step users must request as well as present credentials. Alice begins by obtaining bootstrap credentials (credentials with a 0 amount) in order to be able to make her first input registration. The example in Figure 11c achieves the same results as Figure 11b, but utilizes the credentials differently. At input registration Alice first obtains a credential with value , and then presents it in her next input registration for the input valued .
The most interesting application of the credential system is presented in Figure 11d. Here Alice begins by registering her inputs as in Figure 11c. Another user, Bob, also obtains bootstrap credentials, but does not register an input of his own at this point. Alice and Bob can then communicate out of band, with Alice giving Bob the credential valued , which he then presents when registering his own input worth , effectively receiving a privacy enhanced payment of from Alice. Note that in this last example Alice must ask Bob before signing during the final phase to ensure her funds were allocated as intended, and Bob must trust Alice to provide him with a valid credential, and cannot verify its validity without presenting it to the coordinator.15
In this section we provide the details of the unified protocol (Section 5.3.3) and its use of the KVAC scheme introduced in . Following that work, our protocol is defined over an Abelian group of prime order , written in multiplicative notation. is a function from strings to group elements, based on a cryptographic hash function .
We require the following fixed set of group elements for use as generators with different purposes:
chosen so that nobody knows the discrete logarithms between any pair of them, e.g. .
Our notation deviates slightly from , in that we subscript the attribute generators as instead of using numerical indices, and we require two additional generators and for constructing the attribute as a Pedersen commitment. As with the generator names, we modify the names of the attribute related components of the secret key .
The coordinator parameters are computed as:
and published as part of the round metadata and are used by the coordinator to prove correctness of issued MACs, and by the users to prove knowledge of a valid MAC.
For each the user chooses an amount subject to the constraints of the balance proof (Section 6.5). She commits to the amount with randomness , and these commitments are the attributes of the requested credentials:
For each amount she also computes a range proof which ensures the amounts are in the allowed range which ensures that finite field arithmetic will not overflow and the values will behave like positive integers when added or subtracted:
In credential bootstrap requests the range proofs can be replaced with simpler proofs of :
If the coordinator accepts the requests (see Section 6.3 – Section 6.5), it registers the input or output if one is provided, and for each it issues a credential by responding with , which is the output of , where:
To rule out tagging of individual users the coordinator must prove knowledge of the secret key, and that are correct relative to :
The user chooses unused credentials issued in prior registration requests, i.e., valid MACs on attributes .
For each credential she executes the protocol described in :
She chooses , and computes and the randomized commitments:
To prove to the coordinator that a credential is valid she computes a proof:
which implies the following without allowing the coordinator to link to the underlying attributes :
She sends and the coordinator computes:
using its secret key (independently of the user’s derivation), and verifies .
The user proves that the group element , which is used as a serial number, was generated correctly with respect to :
The coordinator verifies and checks that the has not been used before (but allowing for idempotent registrations).
Note that since the logical conjunction of and is required for each credential, and because these proofs share both public and private inputs it is appropriate to use a single proof for both statements.
The user needs to convince the coordinator that the total amounts redeemed and the requested differ by the public input , which she can prove by including the following proof of knowledge:
with denoting the randomness terms in the attributes of the credentials being requested and denoting the ones in the randomized attributes of the credentials being presented.
During the input registration phase may be positive, in which case an input of amount must be registered with proof of ownership. During the output registration phase may be negative, in which case an output of amount is registered. If credentials are simply reissued, with no input or output registration occurring.
Note that is not perfectly hiding because there is exactly one such that . Similarly, randomization by only protects unlinkability of issuance and presentation against a computationally bounded adversary. Null credentials have the same issue, since the amount exponent is known to be zero.
To unconditionally preserve user privacy in the event that the hardness assumption of the discrete logarithm problem in is broken it is possible to add an additional randomness term used with an additional generator to the amount commitments , and similarly another randomness term and generators . Assuming the coordinator is not able to attack network level privacy and proofs of knowledge are unconditionally hiding this would ensure unconditional unlinkability.
In this section, we discuss the security and privacy guarantees of the WabiSabi credential scheme for construction of CoinJoin transactions. Theft concerns are addressed through Bitcoin’s security model, making WabiSabi trustless in that regard. Since CoinJoin is an overt technique privacy strongly depends on the structure of the transactions themselves. WabiSabi is designed as a general-purpose mechanism, so those details are outside of the scope of this work, and further research into its safe application is ongoing.
The goal of the protocol is to allow a coordinator to provide the service to honest participants, without learning anything about the mapping between registered input and outputs, apart from what is already deducible given the public amounts visible on the Bitcoin blockchain. WabiSabi leverages the unlinkability of anonymous credentials and the hiding property of the amount commitments to minimize privacy leaks when a set of participants utilizes a centralized coordinator to reach agreement about such a transaction.
Being a central point of failure, the coordinator is a trusted party with regards to availability. If competing coordinators charge fees for their services then this is a minimal assumption in practice given the financial incentive.
A malicious coordinator can fully disrupt the protocol by censoring certain inputs either at input registration or during the signing phase. The coordinator can also drop messages causing any user to appear to be non-compliant, and therefore disrupt the protocol arbitrarily.
Signatures can only be made after a transaction has been negotiated, and all inputs must provide a valid signature. Consequentially users can always disrupt the protocol during the final phase. Failure to sign is attributable to specific inputs and therefore can be mitigated by the coordinator, allowing the remaining honest participants to restart the protocol and ensuring that a valid transaction can be output after a finite number of attempts. Denial of service is not costless because unspent transaction outputs are a limited resource.
A mixing scheme should ensure that any links between registered inputs and outputs are only known to their owners. The unlinkability property in  ensures that the presentation of credentials cannot be linked back to their issuance. Since every registration request is only associated with a single input or output, the only information that would need to be broadcast publicly on the blockchain if the protocol succeeds is revealed directly.
However, because the protocol may be repeated several times before resulting in a valid transaction, and because the transaction data is still overt the unlinkability of credentials is not enough to guarantee privacy, and there are other means participants or the coordinator could attack it.
We can model registration requests as vertices of a directed acyclic graph labeled by and credentials as edges labelled by the amount in the attribute, connecting the registration request where a credential was issued to where it was presented, much like the graph depicted in Section 5.5. Apart from the bootstrap requests which have indegree 0 (no credentials are presented) and final output requests which have outdegree 0 (requested credentials are not presented in any subsequent request), this graph is -regular. The serial number and balance proofs enforce a global invariant where the sums of the inwards and outwards edges of every vertex differ by its label, and so long as honest participants are able to make their registrations it will be balanced (both vertex and edge labels will sum to 0).
The unlinkability of credentials and hiding property of the amount commitments obscure the edges and their labels from the coordinator and other participants. However, the coordinator observes registration requests according to a partial order which is an extension of the partial order defined by the DAG, in other words, the coordinator knows that parallel requests do not share an edge and that dependent requests must be made sequentially. In other words information about the order and timing of requests as well as the inherently overt transaction data relayed in the registration requests can constrain the graph topology allowing the coordinator to draw inferences about the edges despite not being able to observe the edge set directly.
Clients can mitigate these leaks by minimizing dependencies between requests and scheduling requests randomly during the registration phases. Additional reissuance requests can be made by clients, including clients which do not actively participate in the transaction (cover traffic can be created using only the bootstrap credentials).
Sybil attacks  are an inherent threat to privacy in mixing schemes because a transaction between apparent participants of which are controlled by an attacker will fully link the victim’s coins on both sides of the CoinJoin while giving the impression that the victim’s privacy has been improved. There is a liquidity requirement for such an attack since participants must provide valid inputs,16 as well as a cost imposed by mining fees.
An attacker attempting to Sybil attack all CoinJoins would need to control some multiple of the combined Bitcoin volume contributed by honest participants, and to successfully partition honest participants to a sufficient degree. In the centrally coordinated setting, fees paid by users can arbitrarily increase the cost of Sybil attacks by other users. However, this does not protect against a malicious coordinator which is only bound by liquidity and mining fees. Furthermore, service fees paid by honest participants may reduce the cost of such an attack or even make it profitable.
A malicious coordinator may tag users by providing them with different issuer parameters. When registering inputs a proof of ownership must be provided. If signatures are used, by covering the issuer parameters and a unique round identifier these proofs allow other participants to verify that everyone was given the same parameters.
A malicious coordinator could also delay the processing of requests in order to learn more through timing and ordering leaks. In the worst case, the coordinator can attempt to linearize all requests by delaying individual to recover the full set of labelled edges. This is possible when and users have minimal dependencies between their requests and tolerate arbitrary timeouts but issue requests in a timely manner.
Similarly the coordinator may delay information such as the set of ownership proofs or the final unsigned transaction. In the case of the latter, this can be used to learn about links between inputs. This is because a signature can only be made after the details of the transaction are known. If the unsigned was only known to one user but multiple inputs have provided signatures, it follows that those inputs are owned by the same user.
Since the coordinator must trusted with regards to denial of service a more practical variant of this attack would involve more subtle delays followed by sabotaging multiple successive rounds during the signing phase in order to learn of correlations between registrations while maintaining deniability.
More generally denial of service can amplify attacks on unlinkability, as it can be used to perform intersection attacks. The coordinator always learns the requested inputs and outputs, even if a round fails, and is able to partition users. A malicious participant will also learn all the input and output registrations if they wait until the signing phase to defect.17
Since the output of the protocol is a single Bitcoin transaction theft is prevented by only signing the transaction if the outputs are as expected, so the protocol inherits theft resistance directly from Bitcoin’s security model.
A malicious user could claim more funds than she registered if and only if she is able to forge the coordinator’s MAC on some credential. This is certainly not possible unless credentials can be forged under chosen message attacks, but even if that were the case this would only result in denial of service, as the honest users would refuse to sign such a transaction.
The above outlined security and privacy guarantees directly follow from the applied KVAC scheme of . The unlinkability of WabiSabi credentials follow from the unlinkability of the underlying keyed-verification anonymous credential scheme. The theft prevention of the WabiSabi protocol follows from the unforgeability of the KVAC scheme. We refer the to  for formal security arguments.
In this section we discuss the efficiency of our protocol. Because the protocol can only complete successfully when all participants are both honest and available, and due to the underlying anonymous overlay network it is desirable to operate with as little communication complexity as possible. Reducing communication costs can also make the protocol more robust against traffic analysis by a global passive adversary or targeted censorship by an active one. Computational complexity is mainly a consideration for the coordinator it must process the requests of all users, which follow a bursty pattern.
The following table estimates communication overheads for the protocol assuming simple -protocol for linear relations . These proofs are amenable to compression  and could be reduced to a size that is logarithmic in the bit width and the number of credentials per request.
A proof of concept implementation of the credential system has been added to the open source Wasabi wallet.18 This implementation relied on
NBitcoin.Secp256k119 a port of
libsecp256k1.20 Due to limitations of the .NET runtime only 32-bit limb field elements are supported. All proofs were made non-interactive using the strong variant of the Fiat-Shamir transform .
Performance was measured on an Intel Core i7-7500U CPU 2.70GHz (Kaby Lake) using BenchmarkDotNet version 0.12.1 on Ubuntu 20.04 with .NET Core version 5.0.101. We ran a unified registration request-response flow21 with and 51 bit range proofs, and observed a seconds mean time with a standard deviation of seconds in iterations.
The Bitcoin privacy-enhancing literature is extensive, with notable published works including: . The deployed solutions so far have been mostly CoinJoin based , with various limitations. This leaves a gap between the privacy technology available to Bitcoin users in the real world and the stronger decentralization or trustlessness properties of schemes that remain unused. We believe that the lack of practical use and deployment of most of the Bitcoin privacy-enhancing literature is due to shortcomings in one or more of these aspects.
Denomination: Some of the proposed and deployed schemes only support fixed amounts. Support for variable amounts typically add complexity, reduces privacy, or both.
Performance: Fully decentralized schemes, CoinJoin based or otherwise, typically have higher communication complexity and therefore support fewer participants compared to centralized ones. CoinJoin-based mixing protocols provide mixing in a single Bitcoin transaction. Non-CoinJoin schemes often require more block space, for instance Xim  requires on-chain transactions, TumbleBit  transactions, Blindcoin  and Mixcoin  both require transactions. Long sequence of on-chain transactions result in longer delays for users.
Infrastructure: Several mixing-protocols assume and rely on infrastructure which is not practically available. For example, CoinShuffle assumes a peer-to-peer public bulletin board.
Trustlessness: Some protocols have stronger trust assumptions with respect to theft, for example Mixcoin and Blindcoin,22 whereas other protocols utilize Bitcoin’s scripting capabilities to secure user funds.
Additional related work on Bitcoin privacy that is based on longer lived payment channels  is less directly comparable and have been omitted. Some of the listed approaches, namely TumbleBit , BlindCoin  and custodial services can be used more similarly, but here we consider their use in mixes.
In Table 2 and Table 3, denotes the number of participants. The number of transactions is not necessarily comparable because different protocols have a significantly different transaction structures. Cost in terms of network fees is better provided in terms of the block weight, in terms of the minimum the number of outputs created and destroyed, with any change outputs incurring additional constant overhead. Overall wait times are also bounded by the minimum number of phases which require transactions to be confirmed in a block. Furthermore, some protocols like Chris Belcher’s recent CoinSwap proposal  are designed to provide robust privacy with a single iteration of the protocol, whereas others such as Mixcoin  require multiple mixes to achieve privacy. Secondly, the various protocols are qualitatively different, so comparing overall cost for a desired level of privacy is difficult. Overt transactions are apparent and fingerprintable on the blockchain, but still, provide privacy within the transaction. Disjoint transactions do not link individual users’ inputs and outputs on the blockchain. Covert transactions are not fingerprintable as privacy-enhancing transactions.
Since Chaumian CoinJoins have been successfully deployed despite some limitations (see Section 2.2), it appears that centrally coordinated CoinJoins achieve a conservative balance in the Bitcoin privacy design space. It is non-custodial, has low messaging complexity, and results in a single transaction minimizing delays and network fees.
Our application of  has similarities to Danake , another recent application of KVACs which has additional considerations for longer-lived tokens. It uses the credentials of , hiding the amounts using blind issuance with ElGamal encrypted attribute values.
Fully addressing the limitations discussed in Section 2.2 is the subject of ongoing work instantiating the credential scheme introduced in this work with a concrete protocol and a specific transaction structure. Due to the transparency of Bitcoin transactions the transaction structure further study is required in order to make use of the additional flexibility without compromising privacy.
The scope of such inquiries also extends to usability and user interface questions. For instance, making payments from CoinJoin transactions may benefit not just in costs but also in privacy by scheduling and batching payments, a technique which has mostly been applied to high volume wallets such as exchanges but not to wallets designed for end users. Payments made within a CoinJoin by transferring credentials (as in Figure 11d) present even more of a challenge for usability both due to the interactivity requirements and because of the departure from familiar mechanisms such as Bitcoin addresses.
In this work, we introduced WabiSabi, an application of the keyed-verification anonymous credentials scheme proposed in  to centrally coordinating CoinJoin transactions. WabiSabi builds on Chaumian CoinJoins, adding support for arbitrarily variable amounts. The goal of extending previous work in this way is as an enabler, removing restrictions imposed on currently deployed solutions and opening up new use cases. We note that the credential scheme can also be applied in centrally coordinated settings which are not necessarily based on CoinJoins for a wider range of theft and availability threat models.
We would like to acknowledge the inputs and invaluable contributions of ZmnSCPxj, Yahia Chiheb, Thaddeus Dryja, Adam Gibson, Dan Gould, Ethan Heilman, Max Hillebrand, Aviv Milner, Jonas Nick, Tim Ruffing, Ruben Somsen, and Greg Zaverucha to this paper.