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.
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.
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:
- Every party computes the same new excess deterministically from the given partial excess and nonce values
- 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.
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.
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.
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.
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 kernelE'
can only land on the chain if everyone contributed their uniquely scaled partial excess to the total excessE'
, 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.