Communications of the ACM

ey based on the user-defined program that it executed privately, for example, an auction in this case, so the money goes from the winner to the seller, without leaking any information to the public. The manager submits a zk-SNARK proof indicating the correct execution of the private auction program, and the correct redistribution of money based on the private output of the program. Finally, the seller gets the new coins but nobody with access to the blockchain can find out who the winner was ( assuming the manager does not leak the bids when running the auction).

In terms of concrete performance, assuming an auction with 100 participants, each one needs to publish two separate statements in the blockchain in preparation for the auction. The manager then publishes a final statement that concludes the auction. Each participant spends approximately 35sec preparing these statements in a phase that requires 4GB in memory. The corresponding costs for the manager are 3 minutes and 27GB.

Comparison of Existing Schemes

Next we attempt a comparison of the approaches discussed so far.

Mixing services. First, we compare mixing schemes in terms of their features (see the accompanying table, which is largely based on a similar comparison from Heilman16). We note that all of them are fully compatible with Bitcoin and do not require any modification in the codebase.

Decentralized protocols on the one
hand avoid the need for a third party that
in practice may become a single point of
failure. However, they have the added
issue of requiring participant coordina-
tion ahead of time in order to identify
peers and form transactions. Also, the
communication cost often scales qua-
dratically in the number of participants,
which in practice significantly limits
the size of the anonymity set. For in-
stance, none of CoinShuffle, CoinParty,
or CoinShuffle++ scale the experimental
evaluation they provide to more than 50
participants. Moreover, decentralized
approaches are likely to achieve a quan-
titatively weaker privacy notion than the
centralized solutions as, in contrast to
the latter that hide an output address
within the set of all mixer clients (input
addresses) for a given time period, the
time). In October 2016, Zcashi—a cryp-
tocurrency based on Zerocash—was
officially launched. As of Jan. 26, 2017,
Zcash has a market capitalization of
$20.5 million. It uses a mining mecha-
nism similar to that of Bitcoin but
based on an alternative memory-hard
proof-of-work function3 and it has four
times smaller expected block creation
time. The developers of Zcash chose to
establish the public parameters upon
which its security is bootstrapped via
a secure multiparty computation pro-
tocol executed with a ceremony held
among remote practitioners (some of
which remained anonymous) and with
several defense mechanisms deployed.j
i https://z.cash
j https://goo.gl/fmHqUk
k https://www.ethereum.org
native cryptocurrency aimed at securely
executing such smart contracts on top of
a blockchain-like public ledger. Unfortu-
nately, Ethereum offers very weak privacy
guarantees, revealing the sender’s and
receiver’s addresses as well as all infor-
mation and internal values computed
inside the smart contract (in the exam-
ple here, the bids of each user would be
eventually leaked). Hawk19 aims to offer
notions of privacy while preserving arbi-
trary smart-contract functionality. The
main protocol involves a party called the
manager who is trusted for keeping par-
ticipants’ values (bids) secret, but not for
executing the contract correctly.

At a high level, the protocol starts by having Alice and Bob mint a certain number of Hawk coins, say ha and hb, as in Zerocash and Zerocoin. Then, to participate in the auction there is a bidding period where Alice and Bob commit to their bids xa and xb using a hiding commitment, also computing a zk-SNARK proof they have minted enough coins to support their bids. When the bidding period ends, Alice and Bob post an encryption of their plaintext bids on the blockchain under the manager’s public key, along with a zk-SNARK proof they have encrypted the same value as they committed in the bidding phase. Then the manager retrieves the plaintext values xa and xb, and redistributes the mon-

Comparison of the features of existing mixing schemes.

Avoids
Coin-theft Unlinkable
Anonymity
Set
Adopted
in practice
Untrusted mixer × × (mixer) large Bitmixer,
Bitlaunder, Helix
Mixcoin8 accountable × (mixer) large ×
BlindCoin37 accountable
large ×