Skip to main content

S𝛑PETs: Sustainable Practically Indistinguishable Privacy-Enhanced Transactions

Timofey Yaluhin
Timofey YaluhinResearch engineer

Universal covert privacy-enhancing transactions for any blockchain that supports ECDSA or Schnorr.

1. Introduction​

Existing privacy solutions leave traces that make them a clear target for bans and censorship, which as a result hurts fungibility, e.g. blacklisting coins that were used in the banned protocols. Now, imagine signing a private transaction that reveals nothing about your identity and, at the same time, is indistinguishable from any other regular transactions on-chain. Such privacy overlay would be radically more censorship-resistant and uniquely sustainable. Furthermore, anyone analyzing the chain would have to deal with the possibility that any transaction can secretly be a covert privacy-enhanced one. So overall privacy is improved for all users even without coordinated changes in behavior.

This work describes a way to achieve covert privacy-enhanced transactions on any public blockchain that supports ECDSA or Schnorr. Our method applies two-party computation combined with adaptor signatures and verifiable timed commitments. In the rest of the post, we will take a brief look at the CoinSwap protocol, from which we draw inspiration for S𝛑PETs. We will then introduce cryptographic primitives used as building blocks for our construction. In Section 4, we specify our protocol along with some extensions (delayed withdrawals to mitigate time correlation). In Section 5 we go over some practical considerations and possible use cases for deploying S𝛑PETs on Ethereum. For more details please have a look at the full paper and the github repository.

2. CoinSwap​

This idea of covert private transactions is actually nothing new: the protocol described here is based on CoinSwap, which was proposed by Greg Maxwell in 2013 and revisited recently by Chris Belcher [1]. In hindsight, CoinSwap is a non-custodial way of swapping one coin for another one. Alice can swap coins with Bob by first sending them to a CoinSwap address and having those coins then sent to Bob:

Alice's Address 1 ----> CoinSwap Address 1 ----> Bob's Address 1

An entirely separate set of transactions gives Bob's coins to Alice in return:

Bob's Address 2 ----> CoinSwap Address 2 ----> Alice's Address 2

Privacy is improved because on-chain there is no explicit link between Alice's Address 1 and Alice's Address 2. All that is seen is a regular transfer to Bob. In practice, to be effective CoinSwap must be combined with a few more things: liquidity market, multi-hop routing, and multi-transaction. We won’t get into more details here, but we strongly encourage readers to check Chris Belcher’s design [1].

Before today CoinSwap protocol was only been considered for Bitcoin and its deployment on other networks wasn't possible. The main goal of this work is to allow having CoinSwap-like transactions on any public blockchain network that supports ECDSA or Schnorr. In the next section, we describe cryptographic primitives that allow doing CoinSwaps in a completely scriptless fashion. The reason why it's crucial not to rely on scripts (smart contracts) is due to their inherent identifiability, ie. it's easy to distinguish transactions that involve calls to the same unique smart contract.

3. Building blocks​

3.1 2-Party ECDSA​

We would use a 2-party computation (2PC) to jointly produce a valid ECDSA signature for a transaction that claims previously locked ETH from CoinSwap address. The chosen protocol is Lindell’17 [2] - it’s a widely used, battle-tested, and virtually state-of-the-art implementation of 2P-ECDSA.

The natural intuition now would be to go ahead and use 2PC protocol to compute two signatures, one for each swap. However, this naive attempt leads to an insecure scheme: the 2PC protocol doesn't guarantee output delivery, so nothing prevents Bob from going offline after receiving a valid signature for his transaction.

3.2 Adaptor Signatures​

There exists another cryptographic primitive that is suited to solve such fairness problems — adaptor signatures, which is a special kind of signature encryption. When an encrypted signature (adaptor, owned by Alice) is combined with a decrypted signature (revealed by Bob) - they together yield a decryption key (witness). It's possible to use this weird leakage property to construct an atomic swap protocol: As soon as Alice publishes a claim transaction with a decrypted signature attached, Bob is able to download it and use it to recover a key corresponding to the wallet where his swapped coins are locked. I refer all interested readers to check Lloyd Fournier’s survey [3] about adaptor signatures.

This construction works well for UTXO chains like Bitcoin but has a fundamental flaw on account-based blockchains like Ethereum: Bob can front-run Alice’s attempt to send a signed transaction by publishing a transaction with the same nonce shortly before. If Alice misses noticing that and publishes the compromised transaction anyway, Bob can take a decrypted signature from the mempool and claim coins unfairly.

3.3 Joint Adaptor Signing​

Fortunately, we can solve both problems with introduced primitives by combing them together into a brand new 2P-AdaptorECDSA scheme. The shared key component of Lindell’17 prevents front-running attacks, as there’s no way to sign a conflicting transaction without a mutual agreement from both sides. At the same time, adaptor signatures guarantee the fairness of the exchange, ie. by claiming from CoinSwap Address 1 Alice releases the decryption key y that Bob can use to claim from CoinSwap Address 2.

More specifically, during the ”Lock” phase we require both parties to jointly generate two adaptor signatures over the same witness yy. This way, Alice who initially knows yy will publish her transaction first, thereby allowing Bob to extract yy and use it to adapt his signature and publish next. The specific scheme used is described in [4] and later applied in the context of universal atomic swap in [5].

3.4 Verifiable Timed Commitments​

As the problem with fairness is fixed, there appears to be a new one with fault tolerance: if Alice deposits to CoinSwap Address 1 and Bob goes offline before the pre-signature is generated, Alice’s coins will be forever locked. The standard solution here is hash-time lock contract (HTLC), but using it would ruin the indistinguishability we have established so far. Likely, we can simulate HTLC using verifiable timed commitments (VTC), which lets a user (committer) to generate a timed commitment CC of a some witness xx. The commitment CC must hide witness xx for time T\bf{T} (which can be chosen arbitrarily by the committer). At the same time, the committer also generates a proof π\pi that proves that the commitment CC contains a valid witness xx. This guarantees that xx can be publicly recovered in time T\bf{T} by anyone who owns CC.

The notion of validity will vary depending on the witness. It's entirely possible to have a verifiable timed signature (VTS) where xx is a valid signature for a refund transaction. While nice on paper, this option is expensive in practice, taking ~7 seconds for setup and ~10 seconds for verification. Instead, the committer can prove that the witness is a valid discrete logarithm (VTD) of some known element, which is much simpler algebraic statement.

The idea is for Bob to time-lock his key share x(b)x_{(b)} inside a VTC. Upon receiving Alice could use proof π\pi to verify that Gx(b)⋅Gx(a)=XG^{x_{(b)}} \cdot G^{x_{(a)}} = X where instances x(a)x_{(a)} (Alice's key share) and XX (public key) is known to her. In case Bob goes offline Alice can take her time to open VTC, combine both shares into a valid private key xx, and sign the refund transaction by herself. Next, we take a look at two ways to implement VTC in practice.

3.4.1 Homomorphic Time-Lock Puzzles​

The construction of VTD from [6] makes use of the homomorphic time-lock puzzles (HTLP) that lets one to encapsulate a secret inside a puzzle with the guarantee that it can be opened only after a certain time T\bf{T}. Thanks to it inherent additive homomorphism one can construct cut-and-choose style NIZK proof for a statement H=GxH = G^x.

The biggest challenge with time-lock puzzles is to choose the time hardness parameter. While HTLP guarantees that users with a large number of CPU cores won't be able to solve puzzles quicker than if they would only have one, the speed of individual CPU cores does make a difference. Since the claim timeout should only be a few minutes, we are generally fine if for some users opening of VTD would take double that. Furthermore, in practice, we expect that the presence of VTD will mostly function as a deterrent for users not to misbehave and the parties will not have to open them, except for rare cases.

3.4.2 Distributed Time-Lock Systems​

Similarly how HTLC prevents coins to be released until a certain block height is mined, one can rely on some untrusted third party to release the decryption key when a certain time is reached. An example is tlock system where an untrusted party is replaced with the Drand threshold network and messages are locked using the identity-based encryption (IBE) - a scheme where public key can be an arbitrary string. The Drand network generates randomness in rounds at specific time intervals (30 seconds on the mainnet). Anyone can time-lock a message by encrypting it with a public key, derived from an arbitrarily chosen round number. When the randomness associated with this round is released, it in effect releases the private key associated with the round’s identity public key. Note, that this scheme is non-interactive, so the committer doesn't need to participate in the decryption process.

By itself, tlock encryption is just that - an elaborate encryption scheme. It does not guarantee anything about the witness validity, so one can still cheat by encrypting some random bytes and just pretend that they have used proper key material. To make it verifiable we implement IBE inside an arithmetic circuit that checks the aforementioned discrete log relation. To learn more about this, please refer to the timoth-y/zk-timelock repository.

4. S𝛑PETs: A Covert-PETs protocol​

In this section, we present our covert PETs protocol built using the cryptographic building blocks we have introduced so far.

We assume a public bulletin board where users (market-takers) can find relayers (market-makers). In the following notation, Bob is a market-maker, he runs a relayer server and advertises its address on a bulletin board. Alice wishes to swap her coins, thereby she is a market-taker. She finds a relayer that has enough liquidity for the amount she wishes to swap. For choosing this amount Alice can pay Bob a fee.

Initialize: Alice generate a new destination address DaD_a, where swapped coins will go. Bob can choose to generate a new destination address DbD_b or use an existing one.

Parties agree on the amount α\alpha, time parameters ta,tbt_a, t_b and work as follows:

  1. Alice's first message (Taker::Setup):
    • Alice takes P2's role in [2] and computes two KeyGen::P2::Msg1, one for each CoinSwap account (S1S_1, S2S_2) and sends it to Bob.
  2. Bob's first message (Maker::Setup):
    • Bob takes P1’s role in [2] and computes KeyGen::P1::Msg1 for S1,S2S_1, S_2. Using the tuple of KeyGen::P2::Msg1 received from Alice, he also computes KeyGen::P1::Msg2 for S1,S2S_1, S_2.
    • Bob sends tuple of KeyGen::P1::Msg1, tuple of KeyGen::P1::Msg2 to Alice.
  3. Alice’s second message (Taker::Lock):
    • Using the both sets of KeyGen::P1::Msg1 and KeyGen::P1::Msg2 received from Bob, Alice computes KeyGen::P2::Msg2 for S1,S2S_1, S_2.
    • Alice chooses a random scalar yy and computes Sign::P2::Msg1 according to [4] and sends it to Bob.
  4. Bob’s second message (Maker::Lock):
    • Bob computes hash hbh_b of the transaction that transfer α coins from S1S_1 into DbD_b.
    • Bob encloses for time tat_a his local key share xp1S1x^{S_1}_{p_1} into commitment CaC_a and proof πa\pi_a according to VTC scheme.
    • Bob compute Sign::P1::Msg1 according to [4] and sends it to Alice along with CaC_a, πa\pi_a and hbh_b.
  5. Alice’s third message (Taker::Swap):
    • Alice verifies proof πa\pi_a. If VTC is an HTLP scheme, Alice also starts solving puzzles to unlock CaC_a received from Bob.
    • Alice deposits α\alpha coins to S1S_1 and computes hash hah_a of the transaction that transfer α\alpha coins from S2S_2 to DaD_a.
    • Alice encloses for time tt her local key share xp2S1x^{S_1}_{p_2} into commitment CbC_b and proof πb\pi_b.
    • Using local shares xaS1x_a^{S_1} and xaS2x_a^{S_2} Alice computes Sign::P2::Msg2 for hb,hah_b, h_a respectively and sends them to Bob along with Cb,πbC_b, \pi_b.
  6. Bob’s third message (Maker::Swap):
    • Bob verifies dlog proofs from Sign::P2::Msg2 according to commitments received earlier as a part of Sign::P2::Msg1
    • Bob verifies proof πb\pi_b. If VTC is an HTLP scheme, Bob starts solving puzzles to unlock CbC_b.
    • Bob deposits α\alpha coins to S2S_2. Using local shares xbS1x_b^{S_1} and xbS2x_b^{S_2} he computes σb′,σa′\sigma'_b,\sigma'_a (pre-signatures) for hb,hah_b, h_a respectively.
    • Bob sends σa′\sigma'_a to Alice and listens to chain events for Alice to broadcast a valid signature σa\sigma_a.
  7. Output:
    • Alice decrypts σa′\sigma'_a using key yy to get a valid signature σa\sigma_a, which she then broadcasts on-chain along with the transaction that transfers α\alpha coins from S2S_2 to DaD_a.
    • Bob downloads σa\sigma_a to recover witness yy from σa′\sigma'_a and decrypts σb′\sigma'_b using key yy to get a valid signature σb\sigma_b, which he then broadcasts on-chain along with the transaction that transfers α\alpha coins from S1S_1 to DbD_b.

4.1 Refund paths​

Bob goes offline after Alice deposits in step 5:

  • After time tat_a Alice opens timed commitment CaC_a and acquires Bob's key share xp1S1x^{S_1}_{p_1}, which she then multiple by the local xp2S1x^{S_1}_{p_2} to get valid key xS1x^{S_1}.
  • Having xS1x^{S_1}, Alice can now sign the transaction to transfer α\alpha from S1S_1 to other account of her choice.
  • When Bob is back online and time tbt_b has passed, he opens timed commitment CbC_b and multiples its opening on xp1S2x^{S_2}_{p_1} to get valid key xS2x^{S_2}.
  • Having xS2x^{S_2}, Bob can now sign the transaction to transfer α\alpha from S2S_2 to other account of his choice.

Alice goes offline before broadcasting a valid signature in step 7:

  • After time tbt_b Bob opens timed commitment CbC_b and acquires Alice's key share xp2S2x^{S_2}_{p_2}, which he then multiples by the local xp1S2x^{S_2}_{p_1} to get valid key xS2x^{S_2}.
  • Having xS2x^{S_2}, Bob can now sign the transaction to transfer α\alpha from S2S_2 to other account of his choice.
  • When Alice is back online and time tat_a has passed, she opens timed commitment CaC_a and multiples its opening on xp2S1x^{S_1}_{p_2} to get valid key xS1x^{S_1}.
  • Having xS1x^{S_1}, Alice can now sign the transaction to transfer α\alpha from S1S_1 to other account of her choice.

4.2 Delayed withdrawals​

The CoinSwap design proposed in [1] covers amount-correlation attacks, but has no additional defense from time-correlation. On the other hand, the current generation of contract-based privacy solutions, such as TornadoCash come with the ability to delay withdrawals for an arbitrary time. VTC allows us to support such functionality here as well.

Alice can ask Bob to delay his withdrawal from a shared account for some arbitrary time and to enforce this she will time-lock an intermediary value needed for Bob to complete his withdrawal. The most obvious candidate is an adaptor of Bob's withdrawal transaction signature. However, in our protocol Bob is the one who generates all adaptors, so instead we propose time-locking rxr_x scalar from [4] needed to decrypt the adaptor along with a key recovered by combining valid signature and its corresponding adaptor in Step 7. The rxr_x witness is also much simpler to generate proof for, compared to an adaptor or something else entirely. This is because rxr_x is a regular 32-byte scalar that is revealed along with RxR_x point such that Rx=rxGR_x = {r_x}G which can be proved using trivial discreet log proofs.

5. Deployment on Ethereum​

The recommended way of deploying S𝛑PETs is using server-client architecture, where market-makers maintain high-uptime servers with sufficient liquidity to address the needs of users (maker-takers) of fee cuts. This way, users can run clients on resource-constraint devices including their smartphones, and enjoy good UX because there always be some market-maker ready to help with coin-swapping. However, it's entirely possible to deploy S𝛑PETs as a P2P system, where any client can act as both a market-maker and market-taker. In this case, one should consider the challenge of peer matching, which is would require having a distributed bulletin board for discovery purposes.

5.1 Use cases​

On the Ethereum blockchain, users pay for requested computation in gas using ether cryptocurrency. Determining the source of funds deposited to pay these network fees is essentially the way of de-anonymizing users on public pseudo-anonymous networks. Hence, the aim of privacy-enhanced transactions in the context of functional blockchains - is to hide who and when “enters” and “leaves” certain dApps, i.e. privacy-enhanced on/off-ramping.

However, while originally shared CoinSwap addresses are merely seen as an intermediary pit stop where coins are locked for parties to agree on their further destination, in S𝛑PETs their role is extended to support arbitrary contract invocation. Once funded with ETH by Bob, parties can use 2P-ECDSA to sign any type of transaction requested by Alice, including contract calls. Again, on-chain there is no direct link that connects Alice to that transaction, all that is seen is Bob interacting with some dApp from his ”new” address.

We identify several types of Ethereum applications where such an exploit would make sense:

  1. Exchange coins on DEX;
  2. Purchase or mint NFT;
  3. Deposit coins into a pool in exchange for liquidity-provider (LP) tokens.

This also underpins another relevant functionality that S𝛑PETs is able to support - privacy-enhanced ERC20 operations. Note, that it would still require someone to pay for gas, so the number of transactions to be signed will equal 1 + (whatever is needed to transact with a given ERC20 token).

5.2 Cost​

The simplest form of CoinSwap transaction would cost double what the traditional transfer does - 2∗21000=420002 ∗ 21000 = 42000 gas ($2.12 at the time of writing). An interaction that includes 3 input multi-transactions and 3 hops routing is expected to provide an excellent privacy guarantee for a cost of 21000∗18=37800021000∗18 = 378000 gas ($19 at the time of writing), which is about the same cost as withdrawing from the Tornado Cash pool. However, such complex multi-transaction routed coin-swaps are only for the highest threat models where Bob is assumed to act adversarially. In practice, most users would probably choose to use just one or two hops.

Deploying S𝛑PETs protocol on Ethereum L2s AKA Rollups will result in multiple CoinSwap transactions being sequenced and batched together. This will reduce operational costs while preserving unique privacy and indistinguishability properties. Users could then leverage the cheapest L2 which supports S𝛑PETs for anonymously on-ramping into the Ethereum ecosystem and then use the deposited funds elsewhere.

6. Conclusion​

We have presented a way of implementing a Privacy-Enhanced Transactions protocol similar to Bit- coin’s CoinSwaps on any blockchain that supports ECDSA or Schnorr. Our construction assumes no scripting/smart-contract capabilities of the hosting chain. Instead, a special combination of cryptographic primitives (2P-AdaptorECDSA + Verifiable Timed Commitments) is used to allow parties to engage in the atomic-swap-like protocol in a scriptless and offchain manner.

Apart from being universally compatible with a wide variety of blockchains, including scriptless ones such as Stellar and Ripple, our protocol is also covert — meaning that the resulting transactions are virtually indistinguishable from any other coin-transfer transaction on the ledger. The latter is especially valuable as it underpins the sustainability of privacy-enhancing technology and the fungibility of assets it’s applied to.

All in all, Covert PETs have a strong premise to provide anonymity to those who use them. Moreover, by virtue of being indistinguishable from other on-chain interactions, it can also improve privacy for those who do not and perhaps never even heard about this protocol.

References​