Multiparty S6

Posted by: Adam Gibson | in Bitcoin | 3 weeks, 4 days ago | 8 comments

The multiparty symmetrical Schnorr signature scriptless script shuffle

This blog is in the category of "a new-ish idea about privacy tech"; like similar previous ones (e.g.: CoinJoinXT) it is little more than an idea, in this case I believe it is correct, but (a) I could be wrong and there could be a flaw in the thinking and (b) it's not entirely clear how practically realistic it will be. What I do hope, however, is that the kernel of this idea is useful, perhaps in Layer 2 tech or in something I haven't even thought about.

The Goal

As with similar writeups, I feel it's important that the reader has some idea what the goal is. Here is the goal I mostly had in mind when thinking this through:

  • 11 (or 6, or 24...) anonymous users coordinate (on a lobby server, with a Joinmarket-style incentive, on a p2p network somehow - whatever). They each have 1 BTC utxos (put off denomination questions for later) and they want a very meaningful privacy increase.
  • Instead of doing a CoinJoin which is obvious or a whole set of CoinSwaps (see earlier posts) which could get complicated for 11 people, they want to kind of "permute" or "shuffle" all their utxos.
  • It's a year or two from now and a Schnorr soft fork has gone through in Bitcoin mainchain; they're going to use the scriptless script primitive (see here or Poelstra and Nick's writeup here, or the following sections for more on this), to achieve the goal via multisig outputs that look like other outputs.
  • They do effectively a "multiparty swap" or "shuffle" to achieve this goal. Each of the 11 participants funds a single prepared destination address, which is (though not seen because Schnorr) an 11 of 11 multisig. Before they do so, they get hold of a presigned (by everyone) backout transaction to get their coins back if something goes wrong.
  • They decide a shuffle/permutation: e.g. Alice is paying Bob 1, Charlie is paying Edward etc etc. ... we're talking here about a member of the set of permutations of 11 objects. Obviously the idea is that everyone pays in 1, everyone gets back 1. They prepare transactions for these payments.
  • Once everything is set up they pass around adaptor signatures which create the atomicity effect we want - when any 1 of the 11 transactions goes through, all of them will go through.
  • In a certain order, that we'll discuss, they can now pass real (Schnorr) signatures (note that even though "real" they are still "partial" signatures - they're 1 of 11 needed in the multisig) on the transactions such that one member of the group has a full set and can broadcast the transaction paying themselves. Everyone else sees this on the blockchain, and combining the signatures in this published transaction, with the earlier adaptor signatures, has enough information to broadcast the other transaction which pays themself.

Let's consider the advantages of doing this:

  • Shared with a 2 of 2 CoinSwap: there is no linkage on the blockchain between the 11 transactions. Effectively, Alice has swapped her coin history with Bob,  Charlie with Edward etc..
  • Big difference from the above: we can create, like a multiparty coinjoin, the highly desirable scenario that individual participants do not know the linkages between inputs for transactions other than their own. As we know, there are various designs of CoinJoin metaprotocols that allow this to different extents, but if CoinSwap is restricted to 2 of 2 this is impossible (no cryptographic trickery prevents the deduction "if it's not mine, it's yours!").
  • Biggest difference from CoinJoin is that CoinSwap transactions (whether 2-2 or 11-11) can look like ordinary payments on the blockchain, although there's meaningful wiggle room in how exactly they will look. If we manage to combine this with even slight variations in size of individual payments, and probably a little timing de-correlation too, the task of a blockchain analyst in identifying these is near impossible (notice that this hugely desirable steganographic feature is shared with PayJoin and CoinJoinXT, previous blog posts - notice though, that it depends on Schnorr for indistinguishable multisig and for adaptor signatures, unless ECDSA-n-party computation is a thing, which I doubt is currently a thing for more than 2 parties, but see e.g. this for recent research in this area.).

Illustrations comparing CoinJoin, CoinSwap and multiparty S6:

Typical coinjoin

Typical CoinJoin transaction - it's very obvious because of equal output amounts; the histories of coins are not disconnected, but fused

Typical 2-party CoinSwap transactions; they are entirely separate on the blockchain, with different timestamps they could be extremely difficult to find.


A very simplified multiparty S6 as envisaged: note that Oscar to Peter shows on a diagonal a simple transaction of the type used in CoinSwap; in fact there is one such transaction for every red arrow; i.e. each red arrow represents a payment from one of the group of 11 to another, in a random permutation. All of these transactions will be atomic; either they will all happen or none will. But none will be linked on the blockchain.

Schnorr and adaptor signatures

Achieving the goals above is crucially dependent on the concept of an adaptor signature as developed by Andrew Poelstra (see some detailed descriptions as mentioned here) in his work on "scriptless scripts". A large part of the earlier blog post on the topic of the scriptless script based swap, was explaining this concept. I want to write an explanation which is easier to understand. I will try :)

A basic Schnorr signature on a message \(m\) using a public key \(P\) whose private key is \(x\), looks like this:

\(\sigma = k + \mathbb{H}(P||R||m) x \quad, R = kG \quad \textrm{Publish: }\ (R,\sigma)\)

\(k\) is called the nonce, and \(R\) is the nonce point (point on the curve corresponding). We shorten the hash function \(\mathbb{H}(\ldots)\) to just \(e\), often.

Schnorr signatures are linear in the keys, in that:

\(\sigma_1 + \sigma_2 = (k_1 + k_2) + e (x_1+x_2)\)

Combining signatures in this way is unsafe in many contexts, in particular multisignature in Bitcoin. See the paper on Musig and this summary for the details on how the weakness (basically, potential of key subtraction) is addressed in detail, using interactivity between the parties cooperating to create the agreggated Schnorr signature. As long as this is properly addressed, though, the linearity property is retained.

Let me emphasise that the rest of this post will ignore the correct construction of keys and nonce points for safe Schnorr multisig; we will just talk about Alice, Bob and Charlie adding keys together and adding signatures together; the difference is crucial in practice but I believe does not alter any of the concepts being outlined.

Partial Signatures

With the above bolded caveats in mind, it'll be important for the following to understand the idea of a "partial signature" in a Schnorr multisig context. What we're doing is to create a single signature \(\sigma\) which represents, say, a 2 of 2 multisignature. Say it's Alice and Bob (A, B). Then Alice would produce this partial signature:

\(\sigma_A = k_A + \mathbb{H}(P_A + P_B || R_A + R_B || m) x_A\)

Notice how it's not a valid signature according to the Schnorr definition because the nonce \(k_A\) does not correspond to the nonce point \(R_A + R_B\) and because the private key does not correspond to the public key \(P_A+P_B\).

However when Bob adds his partial signature:

\(\sigma_B = k_B + \mathbb{H}(P_A + P_B || R_A + R_B || m) x_B\)

... to Alice's, the sum of the two is a valid signature on the message, with the sum of the keys.

We will make use of this shortly.

Adaptor Signatures

A creator of a signature can hide a verifiable secret value in a signature, using simple addition. They can then pass across the signature without the secret value, making it not valid, but verifiable as "a signature with the secret not included". This is what Poelstra means by his concept "adaptor signature". It looks like this:

\(\sigma' = k + \mathbb{H}(P||R+T||m) x \quad R=kG,\ T=tG \)

(from now on, note that ' indicates adaptor signatures). To repeat, it's not a valid signature, but: it can be verified that adding the discrete log of \(T\) to \(\sigma'\) will yield a valid signature on the message m and the public key \(P\).

Refer back to the earlier blog post if you want to check the mathematical details on that.

The alert reader will notice how similar the "adaptor signature" and "partial signature" concepts are - it's almost the same mathematical change, but with a very different purpose/application, as we expand on below:

Atomicity for two parties

This trick is already cool - if I ever pass you the secret value \(t\), you'll be able to form a full valid signature. But with an additional nuance it's possible to make this a two-way promise, so we have the outline of an atomicity property, which can be very powerful. If the contents of the thing being signed, including the nonce points \(R\) and the public keys \(P\) are fixed in advance, we could create a situation where the promise works both ways:

\(P, R, m\) are known \(\therefore \sigma = k + t + \mathbb{H}(P||R+T||m) x\) is fixed. If the adaptor is shared by the owner of the private key \(x\), i.e. if he passes to a counterparty the value \(\sigma' = k + \mathbb{H}(P||R+T||m) x\), then either direction of publication reveals the other:

  • If the full signature \(\sigma\) is revealed, the secret is revealed as \(t = \sigma - \sigma'\)
  • If the secret \(t\) is revealed, the full signature is revealed: \(\sigma = t + \sigma'\)

This atomicity is the basic of the scriptless script atomic swap published by Poelstra and explained in my earlier post.

Atomicity for N parties

This is the novel idea in this post.

Suppose we have fixed \(\Sigma P\), \(\Sigma R\) and a single message \(m\). In other words several participants signing together the same message (Bitcoin transaction).This is the scenario for Schnorr aggregated multisig, modulo the complexity of Musig which as explained above I'm deliberately ignoring. Without adaptors, each party will have to produce a partial signature as already described, and then they can all be added together to create a fully valid Schnorr signature.

Now suppose each of 3 parties (Alice, Bob, Charlie) makes an adaptor signature for their partial signature:

\(\sigma_A' = k_A + \mathbb{H}(\Sigma P || \Sigma R + \Sigma T || m) x_A\)

Little explanatory note on this: each party will have to share their public \(T\) values (which, remember are curve points corresponding to the adaptor secrets \(t\)), so they will all know how to correctly calculate the hash preimage by "combining" (here just adding, but with musig it's more complicated) their public keys, and then linearly adding in all their \(T\) public values to the corresponding \(R\) nonce points as for a normal Schnorr signature.

Similarly for Bob, Charlie:

\(\sigma_B' = k_B + \mathbb{H}(\Sigma P || \Sigma R + \Sigma T || m) x_B\)

\(\sigma_C' = k_C + \mathbb{H}(\Sigma P || \Sigma R + \Sigma T || m) x_C\)

These can then be shared (all with all) and are verifiable in the same way as previously, e.g.:

\(\sigma_A' G \stackrel{?}{=} R_A + \mathbb{H}(\Sigma P || \Sigma R + \Sigma T ||m) P_A \)

But, it seems to get a bit confusing when you ask what happens if one party reveals either a full \(\sigma\) value, or a secret \(t\).

For example, what if Alice reveals her full partial signature (yes I meant that!) \(\sigma_A =k_A + t_A + \mathbb{H}(...) x_A\)?

One partial signature on its own is not enough for Bob or Charlie to do anything. If Alice and Bob do this, and pass these partials to Charlie, then he can complete and publish. But we want atomicity. What we want is:

  • If the complete transaction signature is ever published, all parties can learn the adaptor secrets \(t\).
  • If any or all parties learn the adaptor secrets \(t\) they can publish the complete transaction.

It's clear why that's the desire: that would mean you could make multiple different transactions, sharing the same set of adaptor secrets, and have it so that if one transaction gets published all the others do!

But wait! Something was horribly obfuscated in those bullet points. "learn the adaptor secrets"? All of them, or which ones?

That this is crucial is easily seen by considering the following "attack":

Suppose Alice, Bob, Charlie make three transactions, each of which pays out of a 3-of-3 Schnorr multisig, between them. The idea would be (as you've probably gathered from the build-up) that if any 1 transaction, say the first one paying Bob, gets broadcast, then both Alice and Charlie could broadcast the other 2 transactions, paying each of them, because they "learnt the adaptor secrets". But: if say Alice kicks off, reveals her adaptor secret \(t_A\), then couldn't Bob and Charlie collude? They could take the partial signature of Alice:

\(\sigma_A = k_A + t_A + \mathbb{H}(\ldots)x_A\)

and then between themselves share and construct their "joint" partial signature:

\(\sigma_{BC} = k_B + k_C + t_B + t_C +\mathbb{H}(\ldots)(x_B+x_C)\)

then add this to \(\sigma_A\). They could do this for the two transactions paying them and publish them to the blockchain. It may seem at first glance that this is a problem, because in doing so they haven't revealed their individual adaptor secrets \(t_B, t_C\) but have instead revealed their sum \(t_B+t_C\).

However this is not a problem! One way of looking at it is adaptor signatures are just as linear as proper Schnorr signatures. They are thus aggregatable. From Alice's point of view, although she is taking part in a 3-of-3 Schnorr multisig, she may just as well be participating in a 2-of-2 with a single party, if Bob and Charlie choose to collude and combine in that way. What will Alice see on the blockchain?

\(\sigma = k_A + k_B + k_C + t_A + t_B + t_C + \mathbb{H}(\ldots)(x_A+x_B+x_C)\)

But she already got adaptor signatures from Bob and Charlie, so she can remove them:

\(\sigma - \sigma_A - \sigma_B' - \sigma_C' = t_B + t_C\).

Now possessing the value of the sum \(t_B+t_C\), she can add this to pre-existing adaptor signatures for the transaction paying her and get the complete multisignature on those!

Unfairly linear signatures for the win!

Protocol Outline

We've now covered the meat of the concepts; so this instantiation phase will either be easy to follow, or, if you found the above slightly opaque, will hopefully make it clearer by being more concrete.

We're now ready to outline this "multiparty SSSSSS" design :) We'll break it into three phases.

Because 11 party would be too tedious, we'll stick to Alice, Bob, Charlie three party case as above.

Getting clear on notation: \(D_x\) will be destination addresses, transactions will be \(\tau_x\), adaptor secrets will be \(t_x\), corresponding curve points: \(T_x\). Signatures will be \(\sigma_x\) and adaptor signatures will be marked with a ', so \(\sigma_{x}'\). The subscripts will almost always be one of \(A, B, C\) for Alice, Bob, Charlie.

Phase 1 - Setup

We first negotiate three destination addresses: \(D_A, D_B, D_C\). Here the subscripts denote the payer into the address. So after the end of the setup the first will contain a coin paid by Alice, the second by Bob and the third by Charlie. The preparation of these addresses/keys will of course be done with Musig but to reiterate, we are ignoring the complexity there.

The three parties then all provide signatures on backout transactions such that each party gets their money back after a timeout. See the section "Timing Controls" for more details on this.

Once backouts are presigned, all parties pay into the destinations as above and wait for confirms.

Parties will agree in advance on the "shuffle"/permutation of coins, i.e. who will be paying who; this is related to Timing Control, so again, see that section. The exact negotiation protocol to decide the permutation is left open here. Once agreed, we know that we are going to be arranging three transactions paying out of \(D_A, D_B, D_C\), we'll call these \(\tau_{AB}, \tau_{BC}, \tau_{CA}\) respectively, where the second subscript indicates who receives the coin.

Phase 2 - Adaptors

Each participant chooses randomly their adaptor secret \(t_A, t_B, t_C\) and then shares \(T_A, T_B, T_C\) with all others (technical note: this might need to happen in setup phase). They then also all provide adaptor signatures on all of three transactions \(\tau_{AB}, \tau_{BC}, \tau_{CA}\) to each other. Note that there is no risk in doing so; the adaptor signatures are useless without receiving the adaptor secrets. Now each party must make two checks on each received adaptor signature:

  • That it correctly matches the intended transaction \(\tau\) and the set of agreed keys in the setup
  • Crucially that each of the adaptor signatures from any counterparty correctly matches the same adaptor secret point \(T\).

("Crucial" of course because without using the same adaptor secrets, we don't get our desired atomicity across a set of transactions).

To be more concrete, here are the actions of Bob:

  1. Generate a single adaptor secret randomly: \(t_B \stackrel{$}{\leftarrow} \mathbb{Z}_N\)
  2. Broadcast \(T_B = t_B G\) to Alice, Charlie
  3. Having agreed on all three payout transactions \(\tau_{AB}, \tau_{BC}, \tau_{CA}\), generate three adaptor signatures: \(\sigma_{B\tau_{AB}}' = k_{B\tau_{AB}} + \mathbb{H}(\Sigma P_{AB} || \Sigma R_{AB} + \Sigma T || m_{\tau_{AB}}) x_{B\tau_{AB}}\), \(\sigma_{B\tau_{BC}}' = k_{B\tau_{BC}} + \mathbb{H}(\Sigma P_{BC} || \Sigma R_{BC} + \Sigma T || m_{\tau_{BC}}) x_{B\tau_{BC}}\), \(\sigma_{B\tau_{CA}}' = k_{B\tau_{CA}} + \mathbb{H}(\Sigma P_{CA} || \Sigma R_{CA} + \Sigma T || m_{\tau_{CA}}) x_{B\tau_{CA}}\).
  4. Broadcast these adaptors to Alice, Charlie.
  5. Receive the 2 x 3 = 6 corresponding adaptors from Alice and Charlie. Verify each one (note the above bullet points).

Assuming all parties accept the adaptor signatures, we are ready to proceed to the last phase. If any communication or protocol failure occurs, all parties must fall back to the backout transactions presigned in the Setup phase.

(Technical note: it is not necessary for all parties to share all adaptors, in general, but for simplicity we use that model, since it hurts nothing I believe).

Phase 3 - Execution

The order of events in this final execution phase is important for safety, but we defer that to the next section "Timing Controls". Here we'll just show how events will proceed if everything goes correctly, in a randomly chosen order.

  • Alice and Charlie send full partial(! i.e. not adaptor) signatures on \(\tau_{AB}\) to Bob, i.e. the transaction that pays Bob. So they send \(\sigma_{A\tau_{AB}}\) and \(\sigma_{C\tau_{AB}}\), respectively.
  • Bob can add this to his own full partial signature on the same transaction, constructing: \(\sigma_{\tau_{AB}}\) and using this to broadcast \(\tau_{AB}\) to the network, receiving his coin.
  • Alice will read \(\sigma_{C\tau_{AB}} + \sigma_{B\tau_{AB}} = \sigma_{\tau_{AB}} - \sigma_{A\tau_{AB}}\) from this broadcast signature and from this deduce the value of \(t_B+t_C = \sigma_{C\tau_{AB}} + \sigma_{B\tau_{AB}} - \sigma_{C\tau_{AB}}' + \sigma_{B\tau_{AB}}'\).
  • Alice can add this aggregated adaptor secret \(t_B+t_C\) to the pre-existing adaptors \(\sigma_{B\tau_{CA}}' + \sigma_{C\tau_{CA}}'\) to get \(\sigma_{B\tau_{CA}} + \sigma_{C\tau_{CA}}\), which she can then add to \(\sigma_{A\tau_{CA}}\) to get a fully valid \(\sigma_{\tau_{CA}}\) and broadcast this to the network to receive her 1 coin.
  • Charlie can do exactly the same as Alice for the last transaction, \(\tau_{BC}\) and receive his coin.

Thus both other parties, after the first spend, were able to claim their coin by creating complete signatures through combining the adaptor signatures with the revealed (possibly aggregated) adaptor secrets. (Technical note: in a protocol we can allow participants to share adaptor secrets at the appropriate times instead of having it deduced from transaction broadcasts, as in the case of CoinSwap, just as a kind of politeness, but this is not important).

Timing Controls

In the 2 party scriptless script swap, as in earlier CoinSwap designs, we simply account for the asymmetry of timing of revealing priviliged information (e.g. signatures) using an asymmetry of timelocks. The one who transfers something valuable first (a signature) must have an earlier ability to refunds coins that are "stuck" due to protocol non-completion, else the possessor of the adaptor secret / CoinSwap secret, who does not reveal it first, may wait for the window where he can reclaim and the other cannot, to both reclaim and use the secret to steal the other's coins.

Here we must follow a similar principle, just extended to multiple parties.

Suppose, naively, we just used the same locktime on each of the three refund transactions.

Now suppose Alice, at the start of Phase 3, reveals her full signature first, on transaction \(\tau_{AB}\) which pays Bob. And suppose for maximal pessimism that Bob and Charlie are colluding to defraud Alice. They will simply wait until the moment of the timeout and attempt to cheat Alice: try to broadcast both of their own refunds, while spending the transaction for which Alice provided the full signature (having done so, she has revealed her adaptor secret to the other two).

Thus by instead making Alice's backout locktime the earliest, she is safe in transferring her full signature, and thus her adaptor secret first. In this case if Bob and Charlie collude, they can do no better than publish this spend before that (earliest) timeout, and in so doing, reveal the aggregate of their adaptor secrets atomically so Alice can claim her money well before their backouts become active, as intended by system design.

Now let's consider the second sender of a full signature, say it's Bob. Suppose we let Charlie's locktime be identical to Bob's. And for maximal pessimism let's say Alice and Charlie collude. Here, Charlie could refuse to pass his signature to Bob and attempt to reclaim his coin at the exact moment of the timeout, while spending Bob's (depending on the exact permutation of spends, but at least, it's possible). Even though Alice didn't back out at her timeout in this scenario, which is weird, clearly this scenario is not safe for Bob, he has passed across a signature to Charlie with no time based defence against him.

These considerations make it obvious, I think, that the obviously sound way to do it is to stagger the locktime values according to the order in which signatures, and therefore secrets, are revealed. If the order of signature transfers is: first Alice, then Bob, then Charlie, then the locktimes on the backouts which pay each must obey \(L_A < L_B < L_C\).

So I believe this ordering must be settled on in Phase 1 (because we define these locktimes before signing the backout transactions).

Generalisation from 3-3 to N-N.

I believe this is trivial, modulo practicality.

Practical considerations, advantages

The scenario described is a multiparty coinswap in which essentially a group of \(N\) parties could randomly shuffle history of their coins. This could be done with or without a coordinator (either Joinmarket style or server style), could possibly be done with a Coinshuffle++ type coordination mechanism and/or blinding.

Practicality: the biggest limitation is that of CoinSwap generally, but extended further: using staggered locktime backouts means that in cases of failure, participants may have to wait a long time for coin recovery. This gets linearly worse with anonymity set, which is not good. Would love to find a trick to avoid that.

Expanding further on that same limitation, a larger number of participants makes worse the problem that I've previously called "XBI", or "cross block interactivity". There's a lot of exposure to DOS attacks and simple network failure when participants not only have to coordinate, but have to do so more than once. This could partially be addressed with incentives, e.g. fidelity bonds, but I'm not convinced.

On the positive side, there could be a tremendous boon over the 2-party case in that it's possible here to have a group of anonymous participants shuffle the history of their coins without any of the parties knowing the others' linkages.

Also positively, such larger group swaps may offer much larger privacy improvements in a very economical way (a few hundred bytes on chain per participant vs tens or hundreds of kilobytes via coinjoin? complete finger in the air here of course).

Leaving open: can amount decorrelation be achieved in a more powerful way in this model? I believe so, for example by splitting amounts into subsets across subsets of participants in interesting ways. Fees can also be used for noise. I think the most powerful version of this model would be very powerful indeed, but needs more detailed analysis, and this blog post is already too long.

Other applications: also leaving this open. Perhaps using adaptor signatures in groups like this (exploiting the linearity of adaptor signatures) has applications to second layer tech like Lightning or similar contracting.

Current rating: 4

Comments

ZmnSCPxj 3 weeks, 2 days ago

I observe that it is possible for each client pair to use only a 2-of-2 multisig between themselves, without using an n-of-n at each pairing that requires everyone to sign.

One can observe that this would be similar to creating a mini-Lightning Network with 0 fees between participants, and using payment points/scalars instead of hashes/preimages. If LN can work with 2-of-2 between participants and use a Scriptless Script hosted transaction, then it seems that 2-of-2 between participants is enough.

From the point-of-view of one participant (who does not initially know the adaptor secret), if my outgoing UTXO has been claimed, then I want to claim my incoming UTXO immediately. Fortunately, via Scriptless Script, before offering to my outgoing counterparty I should have gotten an offer from my incoming counterparty that will release the payment to me once I have learned the adaptor secret. Somebody claiming the funds from me has to publish the complete signature and leak the adaptor secret to me, so I can now turn around and claim my incoming funds, also leaking the adaptor secret I have learned.

By using 2-of-2 we can use this with ECDSA today via 2p-ECDSA.

However it seems:

1. Everyone has to know the entire "circle" of swaps, because the timelocks have to be larger and larger until the circle is "closed" at the sole participant who knows the adaptor secret.
2. The larger "circle" of swaps, the longer the longest timelock.

The above seems to preclude simple Chaumian techniques.

Link | Reply
Currently unrated

waxwing 3 weeks, 2 days ago

Thanks for the thoughtful comment as usual! I'm going to have to think about this but just wanted to respond so you know the comment system works (requires manual approval unfortunately, so delayed often).

Link | Reply
Currently unrated

waxwing 3 weeks, 1 day ago

So on your first point, that functionally you can get the same effect with 2 of 2:
Not coincidentally, I was chatting with bitconner and roasbeef on IRC yesterday about this S6 idea, and it dawned on me that, at least mathematically, what's on this blog post is somewhat similar to the multi-hop lock design from Moreno Sanchez et al (I'm sure you know but for reference: https://eprint.iacr.org/2018/472 ). Not the same of course, but the similarity being linear addition of secrets from multiple parties. Your suggestion is that it's better to just do it in pairs with a lock between.

I think I agree, but it *might* depend on the exact intent of a protocol. I did wonder whether having the cartesian product approach N-N, not linear, might give a better anonymity condition, assuming you actually used a smart technique like Coinshuffle. Perhaps, but it's pretty unclear (after thinking about it I could at least imagine that you might not know who you are paying ("know" a person here only means: know the linked input)). That's all a bit murky.

However, thinking about it a bit more (I was thinking: hmm surely there must be *some* advantage to having an all-txs-atomicity instead of a chain) it suddenly occured to me that I may have missed a crucial point:

As I said "Practicality: the biggest limitation is that of CoinSwap generally, but extended further ... This gets linearly worse with anonymity set, which is not good. Would love to find a trick to avoid that." - and you emphasise the same point with (2) in your comment - but wait, it isn't true for N-N is it?

Because think, if we all agree (anonymity aside for a moment) that Charlie is the one whose payout happens first, all that's needed is that we all have defence against Charlie's stalling - so we can set back Charlie's locktime L1, and I think everyone else can have L0.
Because: remember, once any 1 transaction is fully published, *every* party has the aggregated adaptor secret needed to spend their own transaction.

I could be wrong, but if this is correct, then in this blog post I missed the real advantage of the "symmetrical" construct - unlike a lock-chain of HTLCs, you don't need to stagger timeouts linearly.

Link | Reply
Currently unrated

ZmnSCPxj 3 weeks, 1 day ago

Ah; it does seem to be the missing insight needed to get small locktimes.

To explain in other words:

1. One participant is selected (by some fair lot-drawing) to be the keymaker. Keymaker creates the adaptor secret.

2. We shuffle inputs and outputs and match them up. The only requirement is for the keymaker to link its input and output and ensure that the input of the keymaker does not go to its own output (other participants are allowed to let their own input go to their own output so that they do not have to reveal their input and output to anyone else). This leaks the keymaker privacy to everyone else within that round (so the keymaker has to participate in another round for privacy against members of this round; with large enough participant sets it becomes unlikely the keymaker will be keymaker for next round).

3. Participants provide public keys; keymaker provides a public key for its own signing and the point of the adaptor secret.

4. Inputs that will not be paid to the keymaker pay to aggregate key of non-keymaker participants, plus the adaptor secret point as the public key. The single input that *will* be paid to the keymaker pay to the aggregate key of all participants.

5. Before actually signing the transactions that pay out to those public keys, everybody creates backout transactions, with the backout for the input that will go to the keymaker having timeout L0 instead of L1, with L0 + n < L1.

6. Wait for them to confirm.

7. Create claim transactions that pay according to the shuffled schedule. Claim transactions for non-keymakers have partial signatures missing the signature using the keymaker *adaptor* secret, while the claim transaction for the keymaker has partial signature that requires revalation of the adaptor secret in order to complete.

8. Keymaker completes the signature for its own claim transaction, which reveals the adaptor secret.

9. Everyone else can now get the adaptor secret to complete the partial signatures for their own claim transactions.

Link | Reply
Currently unrated

ZmnSCPxj 3 weeks ago

Actually, no, the keymaker need not reveal its input and output: it is safe for it to end up having its input shuffled to its output (if we shuffle inputs and outputs separately while unable to know which output address is from the same participant as a particular input UTXO, there is a small chance that any participant will end up paying itself). It simply has no reason to reveal the adaptor secret if it ends up having its input going to its own output address, but it would be best to not leak that information and continue to reveal the protocol as normal.

But yes, there is a risk that some participant will end up getting its own input to have to pay to its indicated output address.

Link | Reply
Currently unrated

waxwing 3 weeks ago

On point 4, I'm slightly surprised/confused, you're saying the actual *funding destinations* (as keys) are, respectively, the aggregate of all users' keys + the adaptor point T in the first case, and then all keys aggregated (as usual) in the second case. What would be the advantage in making the pubkey be tweaked with tG?

(test: maths? \(P+tG\) ).

Also just to be 100% clear, in this proto description you're still talking about the goal of a multiparty shuffle, I think?

Link | Reply
Currently unrated

ZmnSCPxj 3 weeks ago

To be more precise, for example if A, B, C are the participant pubkeys, and T is the adaptor point, and Charlie is the participant who knows t such that T = t * G, then the UTXOs that will go to Alice and Bob outputs pay to (A + B + T) while the UTXOs that will go to Charlie output pay to (A + B + C). Then the signature to spend from (A + B + C) will require that the adaptor private key t be revealed, so Alice and Bob can claim their outputs using only information that Alice and Bob jointly know.

Intent is to reduce the number of round trips to complete signatures.

-- New thoughts --

Consider the outputs that go to non-keymaker participants.

The ones interested in those coins are the participant that contributes that coin (who wants to be able to back out of the protocol if it stalls) and the participant to whom the coin will go (who wants to be able to claim the coin if it completes).

So 2-of-2 should be enough for the coins that will go to non-keymaker participants.

For the coin that goes to the keymaker, all the non-keymaker participants are interested in this to ensure that (1) it gets a lower timelock than what their own coins get and (2) if the keymaker claims it, the non-keymakers can learn the adaptor secret.

So n-of-n is needed for the coin that goes to keymaker.

Now we only have a "reasonably performant" 2-of-2 for ECDSA, 2p-ECDSA, so the fact that we need n-of-n on the coin going to keymaker seems insufficient.

However, suppose that the keymaker might be willing to sacrifice its privacy if the other participants thereby gain it.

Then we could use 2-of-2 2p-ECDSA keys for the coins going to non-keymaker outputs, using standard SegWit v0 ECDSA P2WPKH addresses.

For the coin going to the keymaker, we could use a "n-of-n" multisig SCRIPT, with each pubkey actually being a 2-of-2 2p-ECDSA. Each such pubkey is between a non-keymaker participant and the keymaker.

So for example, suppose Alice will pay to Bob, Bob will pay to Charlie, and Charlie will pay to Alice.

The coin going to Bob will pay to the ECDSA a * B (== b * A) as is usual for 2p-ECDSA. The coin going to Alice will pay to the ECDSA c * A (== a * C).

However, the coin going to Charlie will pay to Bitcoin P2WSH of `2 <a * C> <b * C> 2 OP_CHECKMULTISIG`.

Alice and Bob coordinate to make a partial 2p-ECDSA signature for the coin going to Bob, requiring that Bob know the adaptor secret t. Charlie and Alice coordinate to make a partial 2p-ECDSA signature for the coin going to Alice, requiring that Alice know the adaptor secret t. Then finally Alice and Bob coordinate with Charlie to create multiple partial 2p-ECDSA signatures for the coin going to keymaker Charlie, requiring that Charlie reveal the adaptor secret.

Charlie publishes the transaction onchain; Alice and Bob can see the completed signatures to learn the adaptor secret t.

Charlie could be a server that always swaps coins, so loss of privacy is ok.

Link | Reply
Currently unrated

belcher 1 week, 4 days ago

Posting this here so it doesn't get lost after an IRC conversation.

This scheme requires that each escrow/destination address (D_1, D_2, D_3, etc) is known to each party. The result is that any single can tell which bitcoin addresses took part in the mix, and therefore the mix is not steganographic to any involved party. It is, however, steganographic to passive observers of the blockchain who didn't take part, so the coins being mixed could've gone to or come from anywhere on the blockchain.

In all this bitcoin fungibility stuff our adversary is not passive, so if this scheme was implemented and became popular then we could expect transaction surveillance companies to run such coinswap bots and if they ever get chosen to take part in a mix then they will seriously narrow down the source or destination of funds.

I've been thinking a more productive scheme might be something involving routed 2-of-2 coinswaps. If designed right, such a scheme would have individual coinswap nodes routing a mix but only knowing its immediate source and destination address, not knowing the final destination or initial source, or its position in the route. So it would have a similar security model and privacy model to onion routing and tor (again assuming that it can be designed to achieve that).

Link | Reply
Currently unrated

New Comment

required

required (not published)

optional