safe_slates.md

Safe Slates

NOTE: This would have to be checked by a cryptographer. It merely serves as a collection of thoughts on what the issues are and what might be a solution to these.

Problem

This document suggests that a slate could commit to a certain outcome of the participants for instance, the outcome could be the following:

Alice:    -5
Bob:      +2
Charlie:  +3

Consider that Charlie is the last to do the key setup (partial excess and nonce) and the first to sign. This means that when he gets the slate, he sees all the previous contributed pairs of (excess, nonce) from both Alice and Bob:

Alice:
  excess: AE,
  nonce:  AR,
Bob:
  excess: BE,
  nonce:  BR,
Charlie:
  excess: null,
  nonce:  null,

Since Charlie received the slatepack from Bob, it's impossible for him to know that AE really came from Alice. It could have just as easily been planted by Bob. This can be solved by providing a signature from Alice signing her contribution e.g.

Alice:
  excess: AE,
  nonce:  AR,
  sig:    sig with Alice's grinaddress for challenge e=H(AE || AR),
Bob:
  excess: BE,
  nonce:  BR,
  sig:    sig with Bob's grinaddress for challenge e=H(BE || BR),
Charlie:
  excess: null,
  nonce:  null,
  sig:    null,

This might look secure at first, but it turns out it's not. This is because if Bob did a transaction with Alice before, they could have observed a triplet (AE, AR, valid_sig) which they could reuse the next time while choosing excess to be BE2 - AE to subtract the need for Alice's partial signature. This might convince Charlie (or someone else) that Alice is a part of the total excess we are signing when in fact she is not.

Solution

The idea is very simple. We have to come up with a way to prevent any possibility of key cancellation by another party. To achieve this, we do the following. When party is ready to sign, they compute a new randomly scaled total excess for the transaction. Given a sequence of contributions

[
  (AE, AR, sig(M=H(AE || AR)),
  (BE, BR, sig(M=H(BE || BR)),  
  (CE, CR, sig(M=H(CE || CR))
]

every party computes what we will call slate challenges:

e00 = H(AE || AR || BE || BR || CE || CR || 00)  # challenge for AE
e01 = H(AE || AR || BE || BR || CE || CR || 01)  # challenge for AR

e10 = H(AE || AR || BE || BR || CE || CR || 10)  # challenge for BE
e11 = H(AE || AR || BE || BR || CE || CR || 11)  # challenge for BR

e20 = H(AE || AR || BE || BR || CE || CR || 20)  # challenge for CE
e21 = H(AE || AR || BE || BR || CE || CR || 21)  # challenge for CR

and the final total excess is computed as

E = e00*AE + e01*AR + e10*BE + e11*BR + e20*CE + e21*CR

We have scaled every contributed key randomly to prevent any kind of key cancelling. The party contributes the "scaled by challenges" partial signature e.g. Charlie contributes a partial sig for partial excess e20*CE and nonce e21*CR.

This gives us the following properties:

1. Every party computes the same new excess deterministically from the given partial excess and nonce values
2. If a party contributes their own random partial excess and nonce (meaning it doesn't reuse an old one), it is impossible for any other party to cancel another key because every slate challenge includes this new key in the hash and hence to cancel a key, you'd need to predict the challenge values

I think computing the excess this way guarantees the contributed partial signature is a commitment to these exact excess and nonce values and every party involved will have to contribute a unique signature for the new excess.

Open questions

Is this secure?

It seems that if I'm a party in the transaction, all other parties will have to produce a partial sig that is unique for the slate's partial excess and nonce values.

Do we have to commit to amounts as well in slate challenges?

I think not. Even if we did commit to the amounts, it's impossible to tell the outputs reflect the commitment because we don't know how to open them.

@tromp these are valid question.

In what circumstance could one of 3 parties steal money by key cancellation
while still having all signatures and rangeproofs check out?

I myself am not sure how problematic this is. There's definitely an uncertainty in the slate because publicly contributed data could be planted or changed over time, but I'm not yet sure how this could be used apart from the "Charlie thought Alice was also a part of the transaction when she wasn't". Perhaps this cancellation could also be used in a m/n multisig by somehow convincing Alice is a part of the multisig they're making when she isn't, but I can't tell if that's the case since I don't know how a multisig on MW would look like. I agree that caring only about your net change seems enough and I've given up on this "immutable slate parts" idea since it adds too much complexity for some unknown gains. There's also a downside to committing to this state which is that you must know who the parties are which also removes plausible deniability. I decided to document this for when we encounter these ideas in the future.

Couldn't each party attach a MAC [1] to the entire slate section that they authored?

I hope I'm not missing something obvious here. If you want to guarantee that every party must use the partial excess and nonce that you saw in the slate as part of total excess signing, then I'm not sure how you'd guarantee this with a MAC since a party can only see all of these values once they are ready to sign the total excess. Before that, the partial excess and nonce are not yet populated by all the parties. It seems the safest (and most obvious) way to guarantee this is to capture the party contributed data and do the same trick as used in Schnorr signatures. For a sequence of (pubkey, nonce) pairs, generate a challenge for every pub key present (I think we could skip challenging the nonces, I don't think it adds any more security). It's really just the same trick for challenging pubkeys as done in Schnorr except that it's for many (pubkey, nonce) pairs and not just for 1.

But it's of course possible that I made mistakes.

You were worried about "Since Charlie received the slatepack from Bob, it's impossible for him to know that AE really came from Alice. It could have just as easily been planted by Bob." and I suggested MAC as a simple way to ensure integrity. Do you agree that a MAC guards against that?

Of course a MAC doesn't guard against key cancelling attacks. For that we may still rely on rangeproofs.

I worded it wrongly. It is impossible to know for Bob that AE came from Alice for this transaction. Knowing that it came from Alice could indeed be guaranteed with a MAC.

I don't see how rangeproofs help prevent key cancelling of partial excess and nonce. When you cancel the AE+AR from Alice, she's not a part of the transaction at all so the rangeproofs don't capture any of her data.

When you cancel the AE+AR from Alice, she's not a part of the transaction at all

Well then it's obvious that Bob is malicious, if he doesn't even let Alice contribute inputs and outputs to the transaction.
But in that case Bob also cannot defraud Alice...

Indeed, he can't defraud Alice, but can fool Charlie the multisig involved Alice.

can fool Charlie the multisig involved Alice

Alice could show Charlie the tx without Alice's input&output (if Charlie didn't see it himself yet; e.g. in mempool) as proof of Bob's foul play...

Alice could show Charlie the tx without Alice's input&output (if Charlie didn't see it himself yet; e.g. in mempool) as proof of Bob's foul play...

Yes, however, this assumes Alice knows that she was supposed to be a part of the transaction which isn't strictly necessary. I also think Bob could add an additional input and output as if Alice did that since these are indistinguishable for Charlie.

Yes, however, this assumes Alice knows that she was supposed to be a part of the transaction which isn't strictly necessary.

It's necessary if Alice has to authenticate a slate section.

I also think Bob could add an additional input and output as if Alice did that since these are indistinguishable for Charlie.

Bob cannot add inputs/outputs for Alice as these should be in the section that Alice needs to authenticate.

We may need to generalize payment proofs to multiparty contracts to decide whether parties can be fooled/defrauded.

It's necessary if Alice has to authenticate a slate section.

Yeah, it seems to depends which elements of a slate are authenticated. Things like slate uuid can't be used securely for instance as they could be reused. Inputs/outputs that you suggest would be better, but it's not obvious to me it's secure because if Alice has done a 1-2 transaction with Bob before where only Bob contributed an output, this authentication from Alice may be maliciously used in the next transaction by Bob.

Bob cannot add inputs/outputs for Alice as these should be in the section that Alice needs to authenticate.

I see, this would require early locking so that Alice could provide outputs before signing starts. There's a lot of details here that are not obvious to me whether this would work in all cases as mentioned above.

We may need to generalize payment proofs to multiparty contracts to decide whether parties can be fooled/defrauded.

Yeah, there will be a need to do this. I suspect these problems will be tackled a bit later on after we've made significant progress in the ease for use for regular transactions, but it's good to have them on our mind.

I now wonder if the suggestion with challenges (e10, e11,...) described above already makes payment proofs secure in a multiparty setting. All 3 parties pick their partial excess that together sum to E and compute the "safe scaled excess" E' as described in the document. The sender only signs a transaction iff they've received all the payment proofs that says "I consider myself paid X if E' is on chain" from the parties they sent the money to. The kernel E' can only land on the chain if everyone contributed their uniquely scaled partial excess to the total excess E', which is the same property as we have with 2 parties. I haven't checked your early payment proofs implementation in a while, but I hope this would work since it leaves the payment proof logic intact and only redefines what is used as a kernel. In fact, every transaction could randomly scale the partial excess (even in the case of 2 parties) to have a uniform logic for building a transaction regardless of how many parties are involved. It seems to me the case with 2 parties is an edge case that is safe only because the two parties communicate between each other and hence you are in an environment where every party communicates with every other party so you can't really "cancel" people out by doing key cancelling. When you go beyond 2 parties you probably want to get this same guarantee without the need for everyone to ask everyone else if they really are a part of this transaction. The scaling by challenges described above seems to bring this property to any N, including N=2 which is why I think it's a generalized solution and we may consider doing something like this even for the regular case at some point.

There is one thing that seems special in multiparty payment proofs, which is that since the ending kernel is a part of the proof, the parties could construct the proof only when they've seen the total kernel. In a 2-party computation, that's always true in step2, but that's not the case when you have 3 or more parties. Perhaps more communication would be needed to provide the payment proofs separately, but the senders can simply block signing until they've received them.

Ok, I've suspected this attack can also cancel out multisig parties which made me dig a bit into how multisig is done and I've found this post https://medium.com/blockstream/musig2-simple-two-round-schnorr-multisignatures-bf9582e99295. Specifically, the section "The challenge of constructing two-round multi-signatures" which says:

each signer creates two nonces R_i,1, R_i,2, sends them to the other signers in the first round and effectively uses a random linear combination R_i = R_i,1 + b*R_i,2 of those nonces in lieu of the former single nonce R_i. The coefficient b is the output of a hash function applied to all signers’ nonces, the aggregated public key, and the message. As in MuSig1, the aggregate nonce is then R = R_1 + … + R_n. If any signer changes any of their nonces, every other signer will use a different, random linear combination of their two nonces. This prevents the attacks that were discovered for other two-round multisignature schemes. You can find all the nitty-gritty details in our paper.

I think they do a very similar thing to achieve security because partial excess and nonce can be thought of as two random nonces. Then they collect all of these double nonces, and scale one from each pair randomly with a unique challenge for it. The slight difference in the attempt in this document is that in Grin, one of these nonces (partial excess) is the pubkey for this signing session, so including both "nonces" in the challenge already commits to the "aggregate public key" as far as I can tell (I'm assuming an ephemeral pubkey has the same properties as a nonce in this setting and can, in this special case, act as both at the same time securely, but I'm not 100% sure about this yet). I also don't yet understand how the mentioned concurrent attack looks like (the paper seems quite hard to read for me), but I can't figure out how you'd convince a party to sign the wrong message. From the blog post sentence "each signer creates two nonces R_i,1, R_i,2, sends them to the other signers in the first round", it seems that MuSig2 achieves the guarantee that the two generated nonces come from the right party (authentication guarantee) by manually communicating with everyone else and sending them the two nonces which I think makes roughly (N^2)/2 interactions to pass the nonces from each party to everyone else. I'd have to read the musig2 paper to see if they also show an authenticated variant (e.g. with a sig/hmac like we did above) which would allow appending them in a list (a slate in our case) and hence reduce communication overhead to just N. Both the concurrent attack and musig2 papers are quite dense for me and I don't understand these well, so it's quite likely I may have missed something they protect against. Nevertheless, it's good we have these thoughts documented somewhere.

Authenticated sections cannot be reused if the timestamp including memo of the slate is part of authentication.

Our mimblewimble setting makes our problem easier than the more general setting that musig2 was designed for.
You cannot cancel a key that is needed as excess for either an input or an output.
That's why I think we should try to make do with simpler solutions if possible.

Authentication (with memo) makes sense regardless of what else we do.

I see only one remaining case where key cancellation is an issue.
That is if Alice and Bob construct a 2-of-2 output that is funded solely by Bob.
In that case Bob could "cancel" Alice's contributing excess by just ignoring it.
This is already defended against by either Alice picking her excess/nonce after seeing Bob's,
or Alice signing after seeing Bob's signature.
The principle here is that signing should proceed in the opposite order of keying.

A memo (if present) might solve this issue as it's an identifier unique to a transaction, but I'd have to think in this direction some more to convince myself that's the case. The only thing I'd want is to have a single case that works and is safe for 1, 2 and N parties (including payment proofs). If we can achieve this without making the keys randomly jump around, then that's even better.