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 privately[1] as shown already in some of the earliest academic studies of Bitcoin [@reid2013analysis; @ron2013quantitative; @androulaki2013evaluating; @ober2013structure; @moeser2013inquiry; @meiklejohn2013fistful].
The conditions for spending an output are specified in its
scriptPubKey, typically requiring that the spending transaction be
signed by a specific 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 [@mizrahi2013blind; @maxwell2013coinjoin; @zerolink] is a privacy enhancing technique that uses this atomicity property and Chaumian blind signatures [@chaum1983blind] 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. To mitigate this the coordinator provides blind signatures representing units of standard denominations in response to submitted inputs. By unblinding and presenting this valid signature, the coordinator is unable to link the signed output to specific inputs but can be still verify that an output registration is authorized.
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.
In this work, we aim to improve on ZeroLink [@zerolink] as implemented by Wasabi, the most popular Chaumian CoinJoin implementation for Bitcoin. We identify several privacy shortcomings and inefficiencies of Wasabi CoinJoins. Some metrics comparing Wasabi, Samourai and other apparent CoinJoin transactions are provided. The “Other” category includes JoinMarket, but also has an inherent false positive error given these transactions are identified heuristically.
Due to the nature of blind signatures, mixed outputs of Wasabi CoinJoins are restricted to fixed set of multiples of a base denomination[2]. 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.
We define CoinJoin inefficiency as the fraction of non-mixed change outputs in a CoinJoin transaction, see [fig:cjinefficiency].
In order to participate, a user’s combined input amount must be greater or equal to the base denomination.[3] We observe, that considerable portion of CoinJoin inputs are less than this minimum denomination, see [fig:minimumdenomination].
Even when users are able to provide several smaller value inputs with total value greater than the minimum denomination, the coordinator knows those inputs belong to the same user. In an ideal mixing protocol the coordinator should not obtain more information than the already available public ledger data by coordinating the CoinJoin transaction. This information removes many degrees of freedom when assigning non-derived sub-transactions [@maurer2017anonymous], potentially removing ambiguity when there are multiple valid assignments or reducing the computational cost of such an analysis.
Furthermore if users consolidate coins before the CoinJoin in an additional transaction in order to be able to participate in a CoinJoin, then this link is revealed publicly based on the common input ownership heuristic [@meiklejohn2013fistful].
Since users pay mining and coordination fees the denominations are gradually reduced between rounds of consecutive CoinJoins in order to make it possible for users to mix several times without providing additional inputs. This 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 [fig:postmixmerging]) 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, and since they are a form of PayJoin[4] it would also improve privacy by introducing degrees of freedom in the interpretation of CoinJoins.
We present WabiSabi, a generalization of Chaumian CoinJoin based on a keyed-verification anonymous credentials (KVAC) scheme [@chase2019signal]. The use of KVACs replaces blind signatures’ standard denominations with homomorphic amount commitments, similar to Confidential Transactions [@maxwell2016confidential], 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 the privacy enhanced outputs[5].
WabiSabi can be instantiated to construct a variety of CoinJoin transaction structures that depart from the standard output denomination convention, used by SharedCoin[6] and CashFusion[7] style transactions and Knapsack [@maurer2017anonymous] mixing. Payments from CoinJoin transactions are possible, as are payments within them, effectively a multiparty PayJoin that trades the steganographic properties for improved privacy from counterparties. Additionally, restrictions on consolidation of inputs can be removed, and there are opportunities for reducing unmixed change and relaxing minimum required denominations, and improved block space efficiency.
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 do not reveal anything about the chosen message.
.
The
algorithm generates a commitment
to message
using randomness
.
:
one can verify the correctness of the opening of a commitment by
checking
.
If equality holds the algorithm outputs
,
otherwise
.
For ease of understanding one may assume in the following that the commitment scheme is instantiated as a Pedersen commitment.
A message authentication code (MAC) ensures the integrity of a message and consists of the following three probabilistic polynomial-time algorithms.
.
a party generates a secret key
for MAC generation and
verification.
.
one can generate a MAC
on a message
by using their
.
.
The issuer of the MAC can verify a MAC
given the message
it was issued on.
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
.
.
The verifier is given the proof
and
with which they determine whether the prover knows a secret
such that
holds.
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 cryptography in WabiSabi ensures honest participants always agree to sign the final CoinJoin transaction if the coordinator is honest. 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 [@chase2014algebraic]), in particular the scheme
from [@chase2019signal] 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 then
presented at output registration.
denotes the number of credentials used in registration requests, and
constrains the range of amount values[8]. 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 4.
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 user sends
credential requests with accompanying range and sum proofs to the
coordinator:
(((M_{a_i},\pi^{\textit{range}}{i})^{k}{i=1},\pi^{sum},a_{\textit{in}})). -
The coordinator verifies the received proofs. If they are not verified it aborts the protocol, otherwise it issues (k) MACs on the requested attributes ((\mathsf{MAC}\mathsf{sk}(M{a_i}), \pi_i^{\mathrm{iparams}})^{k}_{i=1}).
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 positive integers 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
[@chase2019signal].
-
The user sends
randomized commitments, a proof of a valid MAC for the corresponding
non-randomized commitments, serial numbers with a proof of their
validity, and finally a proof of the sum of the amounts:
(((C_{a_i},\pi_{i}^{\textit{MAC}},S_i,\pi_i^{\textit{serial}})^{k}{i=1}, \pi^{\textit{sum}}, a{\textit{out}})). -
The coordinator verifies proofs and registers requested output iff. all proofs are valid and the serial numbers have not been used before.
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 be
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.[9]
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.
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 small[10] value of
as a protocol level constant to reduce privacy leaks, 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 4.
-
During both input and output registration phases the user submits:
-
(k) credential requests with accompanying range and sum proofs to the coordinator: ((M_{a_i},\pi^{\textit{range}}{i})^{k}{i=1})
-
(k) randomized commitments, proofs of valid credentials issued for the corresponding non-randomized commitments, serial numbers, and proofs of their validity: ((C_{a_i},\pi_{i}^{\mathit{MAC}},S_i,\pi_i^{\textit{serial}})^{k}_{i=1})
-
A balance (\Delta_{a}) and a proof of its correctness (\pi^{\textit{sum}})
-
If (\Delta_{a} \ne 0), an input or output with value (|\Delta_{a}|).
-
-
The coordinator verifies the received proofs, and that the serial numbers have not been used before, and depending on the current phase, (\Delta_{a} \geq 0) (input) or (\Delta_{a} \leq 0) (output). If it accepts, it issues (k) MACs on the requested attributes ((\mathsf{MAC}\mathsf{sk}(M{a_i}), \pi_i^{\mathrm{iparams}})^{k}{i=1}), and if (\Delta{a} \ne 0), registers the input or output with value (|\Delta_{a}|).
The user submits
valid credentials and
credential requests, where the sums of the underlying amount commitments
must be balanced ([fig:reissue]).
-
During input registration phase the user submits
credential requests: ((M_{a_i},\pi^{\mathit{null}}{i})^{k}{i=1}) -
The coordinator verifies the received proofs. If it accepts, it issues (k) MACs on the requested attributes ((\mathsf{MAC}\mathsf{sk}(M{a_i}), \pi_i^{\mathrm{iparams}})^{k}_{i=1}).
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 ([fig:bootstrap]).
The user fetches the finalized but unsigned transaction from the coordinator. If it contains the outputs she registered she will sign her inputs and submit each signature separately using the network identity used for that input’s registration.
To illustrate the above protocols, [fig:ex1,fig:ex2] show how a user might register inputs and outputs when credentials are only presented during the output registration phase and [fig:ex3,fig:ex4] show the unified protocol, when credentials are both presented and requested in every registration request.
Registration requests are depicted as vertices labeled 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 labeled with the amount. The sum of a
vertex’s label and the labels of its incoming edges must be equal to the
sum of the labels of 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.
Following [@chase2019signal], the credential scheme for the protocol
in 3.3.3 is defined over a group
of prime order
written in multiplicative notation.
is a function from strings to group elements, based on a cryptographic
hash function[@fouque2012indifferentiable].
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 [@chase2019signal], 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
according to our fixed set of group attributes.
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 (4.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 there are no negative
values:
In credential bootstrap requests the range proofs can be replaced with
simpler proofs of
:
We note that if Bulletproofs [@bunz2018bulletproofs] are utilized for
the range proofs
a combined proof will significantly decrease the communication overhead
and that some implementations perform the
optimization already.
If the coordinator accepts the requests (see
[presentation,serial,balance]), 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 [@chase2019signal]:
-
She chooses
,
and computes (z_{0_i}=-{t_i} {z_i} (\bmod q)) and the randomized
commitments: [\begin{aligned}
C_{a_i} &= {G_a}^{z_i} M_{a_i} \
C_{x_{0_i}} &= {G_{x_0}}^{z_i} {U_i} \
C_{x_{1_i}} &= {G_{x_1}}^{z_i} {U_i}^{t_i} \
C_{V_i} &= {G_V}^{z_i} V_i\end{aligned}] -
To prove to the coordinator that a credential is valid she computes a proof: [\begin{aligned} \pi_{i}^{\mathit{MAC}}=\operatorname{PK}{ & (z_i, z_{0_i},t_i): \ & Z_i =I^{z_i} \land \ & C_{x_{1_i}} = {C_{x_{0_i}}}^{t_i} {G_{x_0}}^{z_{0_i}} {G_{x_1}}^{z_i} }\end{aligned}] which implies the following without allowing the coordinator to link (\pi_{i}^\mathit{MAC}) to the underlying attributes ((M_{a_i})): [\mathsf{Verify}((C_{x_{0_i}}, C_{x_{1_i}}, C_{V_i}, C_{a_i}, Z_i), \pi_i^{\mathit{MAC}}) \iff \mathsf{VerifyMAC}{\mathsf{sk}}(M{a_i})]
-
She sends ((C_{x_{0_i}}, C_{x_{1_i}}, C_{V_i}, C_{a_i},\pi_i^{\mathit{MAC}})) and the coordinator computes: [Z_i=\frac{C_{V_i}}{{G_w}^w {C_{x_{0_i}}}^{x_0} {C_{x_{1_i}}}^{x_{1}} {C_{a_i}}^{y_a} }] using its secret key (independently of the user’s derivation), and verifies (\pi_i^{\mathit{MAC}}).
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 (allowing for idempotent registration).
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:
where
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 we can add an additional randomness term
used with an additional generator
to the amount commitments
,
and similarly another randomness term
and generators
in order to obtain unconditional unlinkability for the
commitments.[11]
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, Lucas Ontivero, Tim Ruffing, Ruben Somsen and Greg Zaverucha to this paper.
[1] In this work we restrict the discussion of Bitcoin privacy to that of public ledger transactions, but there are other considerations especially at the network layer. For a more comprehensive discussion see https://en.bitcoin.it/wiki/Privacy.
[2] Approximately
[3] The observed base denominations in Wasabi’s CoinJoins are usually slightly higher than the announced, agreed upon base denomination. Thus participants sometimes get back slightly more value in the CoinJoins than they put in.
[4] https://en.bitcoin.it/wiki/PayJoin
[5] Note that the cleartext amounts appearing in the final transaction might still link individual inputs and outputs.
[6] https://github.com/sharedcoin/Sharedcoin
[7] https://github.com/cashshuffle/spec
[8]
[9] Note that there is no need for range proofs, since amounts have been previously validated.
[10] Specifically,
the maximum number of participants, because although
suffices for flexibility it limits parallelism, leaking privacy by
temporal fingerprinting. The limit on participant count is because 274
and 124 are the minimum weight units required for a participant with
only a single input and output, and 58 is the shared per transaction
overhead.
[11] Assuming the coordinator is not able to attack the network level privacy and the proofs of knowledge are unconditionally hiding.