Is a "safely compliant" (semi-)centralized CoinJoin service possible?

[d5000]

I think everybody and their grandma has now already heard of the Samourai case.

I was thinking about if a service which could make CoinJoins easier would be possible in a totally compliant way, without any danger of it to be considered a "money transmitter" by any authority. (I still think the American authorities are wrong with Whirlpool being a "money transmitter", but I haven't seen the code, so I can't be sure.)

First, what do we need to build a CoinJoin facilitating service? First, some kind of storage for a pool of UTXOs which are available for CoinJoins. I guess Whirlpool did this in a centralized way on its server. But in theory this could be done by the users themselves: from the moment on they offer their own UTXO, they can get informations about other UTXOs which are available. (This is actually how JoinMarket seems to work afaik. But Joinmarket is not what I'm asking for - I'm thinking about a model to create a centralized service which could offer a fee but would be easier to use than JoinMarket.)

So the UTXOs would circulate in a P2P network completely independent from the centralized server.*

Second part would be the entity "building" the CoinJoin transactions. This could also happen in the P2P network. So basically, once an user sees enough UTXOs to form a CoinJoin, he uses let's say 5 or 10 UTXOs from this decentralized pool and builds his transaction, signs it and broadcasts it inside the P2P network, so all peers which have contributed UTXOs can sign it.

What can the centralized server do to make CoinJoins easy? As far as I have understood JoinMarket, you need a full node to participate there because otherwise there are security concerns, and thus it's limited to a relatively small and wealthy Bitcoin user group.

So the centralized server thus could simply offer you this service: a trusted Bitcoin Core node you can connect to and you can query as if it was your own Bitcoin Core node. So every user can always be sure that the UTXOs he uses for his CoinJoin transaction are really there.

Such a service would be able to charge a (low) fee, for example for a kind of API subscription, but would not be a money transmitter in any way as it's not at all involved in the creation of transactions.

This would make a JoinMarket-style CoinJoin network possible where users could participate with their SPV wallets (Electrum, Sparrow et al.).

Am I missing something? Does such a service perhaps already exist?


*Yes, chain analysis companies could of course use this P2P network too, but this would happen to all CoinJoin models.

[DaCryptoRaccoon]

I think something like a decentralized network where users could engage in privacy-enhancing transactions without the risk of running afoul of regulatory bodies is needed.  Given the situations with Samourai and Whirlpool and the scrutiny it faced it's crucial to brainstorm a structure that avoids being labeled as a money transmitter

The first challenge is managing the pool of UTXOs that users wish to mix.

Instead of a central server holding this info (which could draw legal and security concerns)why not let the users themselves manage their UTXOs in a peer-to-peer manner?

Distributed Hash Table? Utilize a DHT to store and retrieve UTXO information, each UTXO can be indexed by a hash derived from its attributeswhich could include the transaction ID and output index, masked with a privacy-preserving algorithm to prevent tracking

Adding a gossip protocol to propagate UTXO information across the network.  This ensures redundancy and availability of UTXO data without relying on a central server.  It would also be possible to use cryptographic commitment schemes to ensure that UTXO data remains confidential until participants are ready to reveal them. This can prevent premature exposure of UTXO details.

Apply homomorphic encryption to allow certain computations to be carried out on UTXOs, such as verification of amounts and eligibility, without revealing the underlying values.

Multi-Party Computation could be used for constructing the transaction where each participant computes a part of the transaction without revealing their inputs to others.  This can be crucial for maintaining the confidentiality of which inputs and outputs belong to whom.

Just some ideas 

[ABCbits]

This would make a JoinMarket-style CoinJoin network possible where users could participate with their SPV wallets (Electrum, Sparrow et al.).

Am I missing something? Does such a service perhaps already exist?

https://joinstr.xyz somewhat match idea you described.

[d5000]

https://joinstr.xyz somewhat match idea you described.

Looks really interesting, thank you! It seems however still not be ready for mainnet, but definitely a solution which is worthy to observe.

snip

Some good ideas here, thanks! Yes, what I had thought about was that users manage the UTXOs in a P2P manner. But my question was in reality if you could build a compliant business model with such an idea.

I don't know how many of those technologies you mentioned (DHT, gossip, homomorphic encryption/multiparty computation) are already implemented in JoinMarket and Joinstr. Specificly homomorphic encryption and multiparty computation could be a game-changer if that part is still lacking, because they would allow a similar level of privacy than a trusted centralized service.

My main doubt was about the need of a full node. JoinMarket requires it, Joinstr seems not, so it may already fit the idea of the service I had in mind. Possible business model could include to act as a market maker or even as a specialized Nostr relay maybe.

[DaCryptoRaccoon]

While Bitcoin's pseudonymous nature offers a level of privacy, all transactions are public on the blockchain, allowing for potential analysis that could link identities to transactions. To enhance privacy and security, advanced cryptographic techniques such as homomorphic encryption can be applied. using Microsoft SEAL, a C++ library for homomorphic encryption, to demonstrate how privacy could be further protected in Bitcoin transactions, particularly in privacy-focused protocols like CoinJoin.

Homomorphic encryption allows computations on encrypted data without needing to decrypt it first. This property can be particularly useful in Bitcoin transactions for various reasons...  Users can participate in transactions without revealing their transaction amounts or other sensitive data to other parties or the public blockchain.

Secure Multi-party Computations, enables the creation of complex multi-party protocols where inputs are kept private.

Setting up Encryption Each participant uses a common encryption scheme set up using Microsoft SEAL. This ensures all parties can operate on the data homomorphically. users encrypt their UTXO values. This encryption does not reveal the amount of bitcoins each user intends to mix, but allows operations to be performed on the encrypted values.

Code:

Ciphertext encrypted_utxo = encrypt_utxo_amount(context, utxo_amount, public_key, encryptor);

Serialize and Share Encrypted UTXOs, Once encrypted, UTXO data can be serialized and securely shared with other participants or a coordinating server without revealing the actual values.

Code:

string serialized_utxo = serialize_encrypted_utxo(encrypted_utxo);

Aggregate Encrypted UTXOs, A trusted coordinator or the participants themselves can aggregate the encrypted UTXOs. This aggregation is performed homomorphically, ensuring that no individual inputs are exposed.

Code:

Ciphertext aggregated_utxos = aggregate_utxos({encrypted_utxo1, encrypted_utxo2}, evaluator);

Check Aggregated UTXOs Against Threshold: To ensure the transaction meets certain criteria (e.g., minimum input threshold for a CoinJoin), a homomorphic operation checks if the aggregated encrypted value meets the required threshold.

Code:

bool meets_threshold = check_threshold(context, aggregated_utxos, threshold, decryptor, encoder);

Finalize Transaction: If the check passes, the transaction can proceed. This step would typically require converting the homomorphically encrypted data into a format suitable for a Bitcoin transaction, which may involve securely decrypting the data under strict protocols or through a zero-knowledge proof mechanism to maintain confidentiality.

Code:

#include <iostream>
#include "seal/seal.h"

using namespace std;
using namespace seal;

// setup the encryption context
shared_ptr<SEALContext> setup_context() {
    EncryptionParameters parms(scheme_type::ckks);
    size_t poly_modulus_degree = 8192;
    parms.set_poly_modulus_degree(poly_modulus_degree);
    parms.set_coeff_modulus(CoeffModulus::Create(poly_modulus_degree, { 60, 40, 40, 60 }));

    auto context = SEALContext::Create(parms);
    return context;
}

// encrypt a UTXO amount
Ciphertext encrypt_utxo_amount(shared_ptr<SEALContext> context, double amount, PublicKey public_key, Encryptor& encryptor) {
    CKKSEncoder encoder(context);
    Plaintext plain;
    double scale = pow(2.0, 40);
    vector<double> input{ amount };
    encoder.encode(input, scale, plain);

    Ciphertext encrypted;
    encryptor.encrypt(plain, encrypted);
    return encrypted;
}

// serialize a ciphertext (for sharing or storage)
string serialize_encrypted_utxo(const Ciphertext& encrypted) {
    stringstream ss;
    encrypted.save(ss);
    return ss.str();
}

// deserialize a ciphertext
Ciphertext deserialize_encrypted_utxo(shared_ptr<SEALContext> context, const string& data) {
    stringstream ss(data);
    Ciphertext encrypted(context);
    encrypted.load(context, ss);
    return encrypted;
}

// aggregate encrypted UTXOs
Ciphertext aggregate_utxos(const vector<Ciphertext>& utxos, Evaluator& evaluator) {
    Ciphertext aggregated = utxos[0];
    for (size_t i = 1; i < utxos.size(); ++i) {
        evaluator.add_inplace(aggregated, utxos[i]);
    }
    return aggregated;
}

// check if aggregated UTXOs meet the threshold
bool check_threshold(shared_ptr<SEALContext> context, const Ciphertext& aggregated, double threshold, Decryptor& decryptor, CKKSEncoder& encoder) {
    // Subtract the threshold homomorphically
    Plaintext plain_threshold;
    encoder.encode(vector<double>{threshold}, aggregated.scale(), plain_threshold);
    Ciphertext encrypted_threshold;
    Encryptor encryptor(context, decryptor.public_key());
    encryptor.encrypt(plain_threshold, encrypted_threshold);

    Ciphertext result;
    Evaluator evaluator(context);
    evaluator.sub(aggregated, encrypted_threshold, result);

    // Decrypt
    Plaintext result_plain;
    decryptor.decrypt(result, result_plain);
    vector<double> result_vector;
    encoder.decode(result_plain, result_vector);

    return result_vector[0] >= 0;
}

int main() {
    auto context = setup_context();
    KeyGenerator keygen(context);
    PublicKey public_key = keygen.public_key();
    SecretKey secret_key = keygen.secret_key();
    Encryptor encryptor(context, public_key);
    Decryptor decryptor(context, secret_key);
    CKKSEncoder encoder(context);

    Ciphertext encrypted_utxo1 = encrypt_utxo_amount(context, 2.5, public_key, encryptor);
    Ciphertext encrypted_utxo2 = encrypt_utxo_amount(context, 1.7, public_key, encryptor);

    vector<Ciphertext> utxos{ encrypted_utxo1, encrypted_utxo2 };
    Ciphertext aggregated = aggregate_utxos(utxos, Evaluator(context));

    bool meets_threshold = check_threshold(context, aggregated, 4.0, decryptor, encoder);
    cout << "Aggregated UTXOs meet threshold: " << (meets_threshold ? "true" : "false") << endl;

    return 0;
}

While it's not 100% solid idea yet could be worth exploring further.

[Medusah]

Such a service would be able to charge a (low) fee, for example for a kind of API subscription, but would not be a money transmitter in any way as it's not at all involved in the creation of transactions.

This doesn't resolve the issue.  You're still required to place trust in the service to provide you with accurate information.  There are still security concerns, just like previously. 

This would make a JoinMarket-style CoinJoin network possible where users could participate with their SPV wallets (Electrum, Sparrow et al.).

The problem (and feature) of JoinMarket lies in takers covering the costs of inputs and outputs for their makers.  When selecting an entity to mix coins with, I'm essentially covering the expenses for their inputs and outputs.  This quickly renders it unappealing in the present context, where we pay more than 15 sat/vB. 

What's required is a network with no distinctions between makers and takers, that consists solely of users leveraging the network to create a shared space, because the main problem with coinjoins is being online at the same time with the other joiners.  Once a collective of participants is created, they could merge their inputs, generate blinded outputs, and cover only their respective portions of the costs.  I believe this network is feasible to create.  Fidelity bonds could still serve to discourage sybil attackers. 

Instead of a central server holding this info (which could draw legal and security concerns)why not let the users themselves manage their UTXOs in a peer-to-peer manner?

Sybil attacks.  By selecting random users, you're essentially relying on the assumption that an attacker doesn't control all of them and inject their inputs.  While you might think your coins have been successfully mixed, the attacker would still be aware of your outputs. 

[Kruw]

I don't know how many of those technologies you mentioned (DHT, gossip, homomorphic encryption/multiparty computation) are already implemented in JoinMarket and Joinstr. Specificly homomorphic encryption and multiparty computation could be a game-changer if that part is still lacking, because they would allow a similar level of privacy than a trusted centralized service.

While Bitcoin's pseudonymous nature offers a level of privacy, all transactions are public on the blockchain, allowing for potential analysis that could link identities to transactions. To enhance privacy and security, advanced cryptographic techniques such as homomorphic encryption can be applied. using Microsoft SEAL, a C++ library for homomorphic encryption, to demonstrate how privacy could be further protected in Bitcoin transactions, particularly in privacy-focused protocols like CoinJoin.

Homomorphic encryption allows computations on encrypted data without needing to decrypt it first. This property can be particularly useful in Bitcoin transactions for various reasons...  Users can participate in transactions without revealing their transaction amounts or other sensitive data to other parties or the public blockchain.

...

While it's not 100% solid idea yet could be worth exploring further.

The WabiSabi coinjoin protocol deployed in Wasabi Wallet and BTCPay Server uses homomorphic value commitments  

Check out the WabiSabi research paper: https://eprint.iacr.org/2021/206.pdf

The problem (and feature) of JoinMarket lies in takers covering the costs of inputs and outputs for their makers.  When selecting an entity to mix coins with, I'm essentially covering the expenses for their inputs and outputs.  This quickly renders it unappealing in the present context, where we pay more than 15 sat/vB.  

What's required is a network with no distinctions between makers and takers, that consists solely of users leveraging the network to create a shared space, because the main problem with coinjoins is being online at the same time with the other joiners.  Once a collective of participants is created, they could merge their inputs, generate blinded outputs, and cover only their respective portions of the costs.  I believe this network is feasible to create.

This network has already been created, the coinjoin protocol you are referring to is called "WabiSabi":

- Users directly cover their own block space costs
- No distinction between makers and takers
- Timeout based rounds for liquidity

[Medusah]

This network has already been created, the coinjoin protocol you are referring to is called "WabiSabi"

As far as I know, WabiSabi doesn't have fidelity bonds.  How does it defend against Sybil attacks?  In a regular coinjoin, the coordinator must be relied upon not to orchestrate a Sybil attack.  I reviewed your research paper, and it doesn't explicitly address Sybil attack protection; it only briefly mentions it in section 7.2.2.  

Sybil attacks [Dou02] are an inherent threat to privacy in mixing scheme ...

A malicious coordinator may tag users by providing them with different issuer parameter ...

A malicious coordinator could also delay the processing of requests in order to learn more through timing and ordering leaks ...

[Kruw]

As far as I know, WabiSabi doesn't have fidelity bonds.  How does it defend against Sybil attacks?

There isn't a need for fidelity bonds with WabiSabi because no one is paying for anyone else's block space.

In a regular coinjoin, the coordinator must be relied upon not to orchestrate a Sybil attack.

I don't know what you mean by "a regular coinjoin". The coordinator is not "relied on not to orchestrate a Sybil attack", any non-coordinator entity can be a Sybil attacker:

Sybil attacks [Dou02] are an inherent threat to privacy in mixing scheme ...

I reviewed your research paper, and it doesn't explicitly address Sybil attack protection; it only briefly mentions it in section 7.2.2.  

I answered these questions here: https://bitcointalk.org/index.php?topic=5482818.msg63555300#msg63555300

[Medusah]

There isn't a need for fidelity bonds with WabiSabi because no one is paying for anyone else's block space.

What's the connection between block space and fidelity bonds?  I understand that fidelity bonds serve a purpose by discouraging attackers from launching sybil attacks, as they would need to lock up bitcoins for an extended period. 

I don't know what you mean by "a regular coinjoin".

I'm referring to a system where there's a coordinator and user connection.  Users register their coins through it. 

The coordinator is not "relied on not to orchestrate a Sybil attack", any non-coordinator entity can be a Sybil attacker

Especially the coordinator, as they are responsible for approving or disapproving coins in every round.

I answered these questions here: https://bitcointalk.org/index.php?topic=5482818.msg63555300#msg63555300

Can you quote your specific message instead?  There's a lot of discussion there. 

[Kruw]

What's the connection between block space and fidelity bonds?  I understand that fidelity bonds serve a purpose by discouraging attackers from launching sybil attacks, as they would need to lock up bitcoins for an extended period.

In JoinMarket and Whirlpool, one coinjoin participant pays for another participant's block space. This creates a misaligned incentive that encourages a single person to assume many identities in order to be chosen for this free handout as often as possible. This misaligned incentive is corrected by fidelity bonds in JoinMarket which allow the free handouts to be targeted towards distinct participants instead of unbonded identities.

Since there are no free handouts in WabiSabi, there's no job for fidelity bonds to accomplish.

Can you quote your specific message instead?  There's a lot of discussion there.  

I did quote the specific message, I'll just copy and paste the content here:

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.

As noted, you can register multiple inputs with WabiSabi to verify that the parameters match each other.

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 k = 1 and users have minimal dependencies between their requests and tolerate arbitrary timeouts but issue requests in a timely manner.

As noted, clients would be able to detect this and defeat it by disallowing arbitrary timeouts.

[Medusah]

Since there are no free handouts in WabiSabi, there's no job for fidelity bonds to accomplish.

Okay, I grasp the concept more clearly now.  Fidelity bonds come into play when there are takers and makers, such as in Joinmarket.  The method to establish provable identities within a decentralized network involves locked value.  An attacker cannot generate identities without first paying the corresponding amount of money.  In WabiSabi, this process isn't necessary because there are no distinct roles of takers and makers; each participant pays for their own inputs and outputs.  Correct? 

I did quote the specific message, I'll just copy and paste the content here

I still don't get how this stops sybil attacks or makes them less likely.  Imagine Alice registers input A, and the coordinator registers their own inputs B, C, and D.  Now, if Bob and Charlie want their inputs (E, F, G) mixed together, but the coordinator refuses, how can Alice be sure the coordinator isn't sybil attacking her in this situation? 

[Kruw]

Okay, I grasp the concept more clearly now.  Fidelity bonds come into play when there are takers and makers, such as in Joinmarket.  The method to establish provable identities within a decentralized network involves locked value.  An attacker cannot generate identities without first paying the corresponding amount of money.  In WabiSabi, this process isn't necessary because there are no distinct roles of takers and makers; each participant pays for their own inputs and outputs.  Correct?  

Mostly correct. Fidelity bonds are optional, so you can still generate as many identities as you want, it's just they won't be prioritized as often by takers.

I still don't get how this stops sybil attacks or makes them less likely.  Imagine Alice registers input A, and the coordinator registers their own inputs B, C, and D.  Now, if Bob and Charlie want their inputs (E, F, G) mixed together, but the coordinator refuses, how can Alice be sure the coordinator isn't sybil attacking her in this situation?  

The coordinator is not able to determine that E, F, and G do not belong to Alice. If Alice sees her other inputs are refused entry, then she can detect the coordinator targeting input A.

[Medusah]

The coordinator is not able to determine that E, F, and G do not belong to Alice.

This assumes that the coordinator isn't analyzing the blockchain.  It's plausible that the coordinator is fully aware of the inputs belonging to Alice, Bob, and Charlie. 

If Alice sees her other inputs are refused entry, then she can detect the coordinator targeting input A.

What if her additional inputs aren't denied access?  What if the coordinator has scrutinized her and can identify which of the requested coins belong to her?  What if the coordinator declines to coinjoin any other input?  Wouldn't that expose her anonymity without her knowledge? 

[Kruw]

This assumes that the coordinator isn't analyzing the blockchain.  It's plausible that the coordinator is fully aware of the inputs belonging to Alice, Bob, and Charlie.  

What if her additional inputs aren't denied access?  What if the coordinator has scrutinized her and can identify which of the requested coins belong to her?  What if the coordinator declines to coinjoin any other input?  Wouldn't that expose her anonymity without her knowledge?  

In this incredibly far fetched scenario, Alice can ask Bob or Charlie to verify they are able to join the same round.

[goldkingcoiner]

There is no such thing as "semi" centralized. Either it is centralized or not. And I would never trust any kind of centralized platform or service. And furthermore, regulations change with time, how will such a service update its compliance without a centralized entity governing responsibility?

[tromp]

There is no such thing as "semi" centralized. Either it is centralized or not.

Then please tell us: if mixing is done by a set of N servers each with its own published public key, and belonging to N different organizations from all over the world, then for which values of N is it centralized, and for which is it not?

Assume that mixing is done in such a way that privacy is compromised only if all N servers collude.

[goldkingcoiner]

There is no such thing as "semi" centralized. Either it is centralized or not.

Then please tell us: if mixing is done by a set of N servers each with its own published public key, and belonging to N different organizations from all over the world, then for which values of N is it centralized, and for which is it not?

Assume that mixing is done in such a way that privacy is compromised only if all N servers collude.

Are you equating N to the number of servers in each set or is N equal to the amount of organizations?  

But if you want my own personal benchmark, then let me give you a percentage: 51%. As long as the 51% attack is achievable, or in this case, 51% of servers are under control of one entity (government), I do not consider the service as decentralized.

[Medusah]

In this incredibly far fetched scenario, Alice can ask Bob or Charlie to verify they are able to join the same round.

There's nothing implausible here.  I'm presenting a realistic scenario where the coordinator operates under chain analysis without Alice, Bob, and Charlie knowing.  It's entirely feasible for a chain analysis company to trace Alice's inputs and launch a sybil attack against her. 

Your "solution" relies on Alice interacting with strangers, and it still doesn't address the core issue.  The coordinator could use the excuse that their round was already full before Bob and Charlie requested their coins to be combined, or they could claim they 'randomly' assigned Alice to a separate round from Bob and Charlie. 

[Kruw]

Your "solution" relies on Alice interacting with strangers

No it doesn't. You can interact with anyone.