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.

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.