Protocol: Blind BLS Signatures

Let me draft the protocol we came up with so far!

Problem statement:

We would like to have an enhanced Chaumian CoinJoin mixing protocol which allows mixing participants not only to mix to their own addresses (Mix2Self), but potentially mix to an address belonging to another entity (Mix2Other). Put differently mixer participants should be able to register an output UTXO with an arbitrary payment amount, different from the equal value denomination. This would allow users to use CoinJoins not only for mixing but also for payments. This would increase the practicality of CoinJoins and would hopefully attract more users, hence increasing our anonymity sets. What lower level functionalities we need to achieve our goals?

Input UTXO splitting Whenever a user registers an input UTXO, say 5 BTC, should be able to receive blind signatures on several, say two, output UTXO values, for instance one with 2 BTC and one with 3 BTC, in a way that users can convince the coordinator that values "inside" the blinded messages add up to the input UTXO value, in this example 5 BTC, while still maintaining the confidentiality of the committed values from the coordinator.
Input UTXO merging To make a payment users might need to consolidate (merge) their registered input UTXOs. Therefore, we would like to allow users to merge their registered input UTXOs without disclosing to the coordinator which input UTXOs were merged.

Note that since most of the protocol happens off-chain we have the freedom to freely use almost any kind of cryptography to achieve our goals.

Blind BLS Signatures

In order to generate a BLS-signature, the signer with private key $x \in_R \mathbb{Z}_p$ ( $y=g^x$ is the public key) computes the signature $\sigma=H(m)^x$ and the verifier checks whether $e(H(m),y)=e(\sigma,g)$ %3De(%5Csigma%2Cg)%24) holds. The correctness is obvious, since $e(H(m),y)=e(H(m),g^x)=e(H(m),g)^x = e(H(m)^x,g) = e(\sigma,g)$ %3De(H(m)%2Cg%5Ex)%3De(H(m)%2Cg)%5Ex%20%3D%20e(H(m)%5Ex%2Cg)%20%3D%20e(%5Csigma%2Cg)%24).

The BLS blind signature scheme works as follows:

Receiver (blinding): Holding message $m$ , choose $r\in_R \mathbb{Z}_p$ and compute $\overline{m}=H(m)g^r$ and send $\overline{m}$ to the signer.
Signer: Compute $\overline{\sigma}=\overline{m}^x$ and send $\overline{\sigma}$ to the receiver.
Receiver (unblinding): Compute $\sigma=\overline{\sigma}y^{-r}$ , which is a signature for $m$ .

Blind BLS Signature verification: It's easy to verify that this is correct, since $\overline{\sigma}y^{-r} = (H(m)g^r)^xy^{-r}=H(m)^xg^{rx}g^{-rx}=H(m)^x=\sigma$ %5Exy%5E%7B-r%7D%3DH(m)%5Exg%5E%7Brx%7Dg%5E%7B-rx%7D%3DH(m)%5Ex%3D%5Csigma%24).

Instantiating the hash function

How shall we instantiate the hash function applied in the Blind BLS signature scheme? We would like to retain nice algebraic properties, hence in our case the hash function might be modular exponentiation, namely $H(m)=h^{m \mod p}$ for another generator element $h$ . This is a hard to invert function if the DLOG assumption holds in the group we're working in. However, this is not a second-preimage resistant hash function as $H(m)=H(m+p-1)$ by applying Fermat's little theorem. This can be fixed, if we restrict the message space to be $m\in\mathbb{Z}_p$ . This can be enforced by using some efficient range proof system.

Note that if we apply the aforementioned hash function then at blinding phase essentially users end up obtaining a Pedersen commitment to their messages, ie. $\overline{m}=h^m\cdot g^r$ .

The proposed mixing protocol

Input registration phase Users send a public input UTXO with value $m$ and several blinded messages $(\overline{m_1},\dots, \overline{m_k})=(h^{m_1}g^{r_1},\dots,h^{m_k}g^{r_k})$ with values adding up to the public input UTXO. Users can convince coordinator about this fact. Let's see this for two blinded messages, but this naturally generalizes to more than two blinded messages. Once again, you can think of the blinded messages as Pedersen commitments due to our choice of the applied hash function.

Input UTXO splitting functionality With public input UTXO value $m$ and with blinded messages $(\overline{m_1}, \overline{m_2})=(h^{m_1}g^{r_1},h^{m_2}g^{r_2})$ users can convince coordinator that values add up by opening the product of the commitment corresponding to the product of the blinded messages. More precisely, $\overline{m_1}\cdot\overline{m_2}=h^{m_1}g^{r_1}\cdot h^{m_2}g^{r_2}=h^{m_1+m_2}g^{r_1+r_2}\stackrel{?}{=}h^{m}g^{r_1+r_2}$ and coordinator can open the very last commitment $h^{m}g^{r_1+r_2}$ and verify the equality if user provides him with $r_1+r_2$ . It is easy to see that by disclosing $r_1+r_2$ coordinator still does not learn anything about individual commitments, coordinator only learns that the sum of the committed values add up to the public input UTXO value $m$ .

For ease of exposition we omitted the range proofs but naturally whenever users send their blinded messages to the coordinator they also send rangeproofs to the coordinator to convince her about the fact that the values inside the blinded messages are less than $p$ . We need this to ensure the second preimage resistance of the applied hash function. Note that for Pedersen commitmens we have several efficient range proofs we can choose from.

Output registration phase At output registration phase users would like to output blindly signed output UTXO values. However as they might issue a payment transaction we need to allow them to merge possibly several blindly signed input UTXOs without revealing to the coordinator which input UTXOs user would like to merge.

This is an example of merging two blindly signed input UTXOs, but this naturally generalizes to arbitrary number of blindly signed input UTXOs.

Input UTXO merging functionality Providing the coordinator $(H(m_1),\sigma(m_1),H(m_2),\sigma(m_2))$ %24) two hashes and two valid signatures one can merge two input UTXOs to an output UTXO with value $m_1+m_2$ as a user could prove that two values "in a signature" add up to a public value (UTXO merging) by this verification equality: $\sigma(m_1)\sigma(m_2)=H(m_1)^x\cdot H(m_2)^x=h^{m_{1}x}h^{m_{2}x}=h^{x(m_1+m_2)}$ .
Achieving double-spending Coordinator will accept each valid signature once and only once.

Signing phase Once the CoinJoin transaction is ready, user sign the transaction in the same way as it is done in current Wasabi.

Padding Scheme

Note that messages represent UTXO values. Since coordinator could know that input UTXOs will never be more than 21,000,000BTC, which amounts to $2^50$ satoshi, coordinator by seeing a hash value $y=H(m)=h^m$ could quite easily brute force the exponent due to the small message space. This attack vector might be alleviated to pad each message with, say 196 bits of random values corresponding to subsatoshi amounts. This padding scheme will thwart such an attack from the coordinator.

Security and Privacy of the protocol

Do you see any problem with the proposed scheme? Any dangerous edge case? Any attack vector we do not address so far? Questions?

We would like to have an enhanced Chaumian CoinJoin mixing protocol which allows mixing participants not only to mix to their own addresses, but potentially mix to an address belonging to another entity. This would allow users to use CoinJoins also for payments.

I don't think that the address is the main issue here. It is one of the issues, and in the case a round fails, we need to get a new address of the receiver somehow. So, it's not unsolved.

However, I think that it must be an arbitrary payment amount, different from the equal value denomination is the tricky part too, maybe this should be reflected.

I don't think that the address is the main issue here. It is one of the issues, and in the case a round fails, we need to get a new address of the receiver somehow. So, it's not unsolved.

I think, this is somewhat an orthogonal problem to the mixing protocol itself. Since we could assume that the sender can non-interactively derive multiple addresses for the recipient. So even if a round fails, a payment sender can create another fresh address for her recipient which she can use in the next round. Could we assume that sender and receiver use some key-derivation protocol or stealth addresses? Or is this a strong assumption Max, @nopara73 ?

However, I think that it must be an arbitrary payment amount, different from the equal value denomination is the tricky part too, maybe this should be reflected.

I'll update now the post above. Although I do think that what we call input UTXO splitting and merging essentially solves this very same problem you mentioned here. I did not articulate this well.

If the round fails then the blame round starts with the exact same participants with the exact same inputs and exact same outputs. Don't assume stealth addresses and similar exotic stuff those didn't gain adoption even without the complexity of coinjoins.

$H(m)=h^m \mod p$

This should be $H(m)=h^m$ since $h^m$ is an element of the group, not a scalar (unless the mod is meant to be in the exponent, which doesn't really matter since the group is cyclic?)

Reiterating some points from previous issues and slack:

Do we actually require bilinearity? Isn't the linearity of Schnorr blind signatures sufficient? The main advantage seems to be lack of Wagner attack but this seems irrelevant since the number of signatures is limited.
To prevent double spending how does the coordinator know the user only submits the unblinded signatures for originally submitted amounts, and not arbitrary combinations of unblinded signatures? For example if I have three registered amounts $m_1, m_2, m_3$ , how does the coordinator detect that a malicious set of output registrations that double spends $m_1$ : $(H(m_1+m_2), \sigma_1\sigma_2), (H(m_1+m_3), \sigma_1\sigma_3)$ %2C%20(H(m_1%2Bm_3)%2C%20%5Csigma_1%5Csigma_3)), the two ~~sums~~ products of the signatures are distinct
Are we convinced that bias in the amount values is not a concern for deanonymizing them? This is way over my head, but after reading a few abstracts about lattice attacks on elliptic curves, I think this is still a concern we must address since the coordinator knows quite a bit about the values, since the coordinator knows quite a bit about the top bits of the various messages both at input registration time and at output registration time. Does the argument rely on the fact that only the sums of the blinding factors is revealed?

$H(m)=h^m \mod p$

This should be $H(m)=h^m$ since $h^m$ is an element of the group, not a scalar (unless the mod is meant to be in the exponent, which doesn't really matter since the group is cyclic?)

Indeed! Good catch! Should be fixed now!

Do we actually require bilinearity? Isn't the linearity of Schnorr blind signatures sufficient? The main advantage seems to be lack of Wagner attack but this seems irrelevant since the number of signatures is limited.

Later we should definitely explore the practicality of other blind signature schemes as well in this context.

To prevent double spending how does the coordinator know the user only submits the unblinded signatures for originally submitted amounts, and not arbitrary combinations of unblinded signatures? For example if I have three registered amounts $m_1, m_2, m_3$ , how does the coordinator detect that a malicious set of output registrations that double spends $m_1$ : $(H(m_1+m_2), \sigma_1\sigma_2), (H(m_1+m_3), \sigma_1\sigma_3)$ %2C%20(H(m_1%2Bm_3)%2C%20%5Csigma_1%5Csigma_3)), the two ~sums~ products of the signatures are distinct

This is a serious issue we should fix in the coming days!

Are we convinced that bias in the amount values is not a concern for deanonymizing them? This is way over my head, but after reading a few abstracts about lattice attacks on elliptic curves, I think this is still a concern we must address since the coordinator knows quite a bit about the values, since the coordinator knows quite a bit about the top bits of the various messages both at input registration time and at output registration time. Does the argument rely on the fact that only the sums of the blinding factors is revealed?

I'm kind of convinced that lattice attack are not relevant here. Or would be computationally infeasible but it is definitely good that you brought up and let's not forget about it! Coordinator might guess 30 bits of the values or so but the remaining 200 bits or so (the subsatoshi values in the padding scheme) should be totally random, hence this attack is not a threat I would say.

Lolll. Sorry! Shame on me! We need to reiterate the protocol! The chosen hash function allows arbitrary signature forgeries composed with BLS signatures. Kudos to @kobigurk

Specifically, if you have a valid signature $h^{mx}$ on message $m$ , then you can forge signature on an arbitrary message $m^{*}$ by computing $(h^{mx})^{m^{-1}m^{*}}=h^{m^{*}x}$ , which is a valid signature on $m^{*}$ .

This scheme could still work, since our double spending solution (the zero knowledge accumulator stuff I don'understand: https://eprint.iacr.org/2019/1255.pdf) not only prevents double spending, but also prevents the malleability issue @seresistvanandras thought ruins everything.

WalletWasabi / WabiSabi