Why 3 party contracts are insecure

insecure_3_party.md

insecure 3-party contracts

Consider a 3-party transaction with A, B and C.

The flow is the following:

new -> setupA -> setupB -> setupC -> signC -> signB -> signA

Let's say B calls the following two at setup and sign steps

contract setup --receive=5
contract sign

We have 3 partial signatures with (pubkey, nonce, sig) pairs:

(pubA, nonceA, sigA), (pubB, nonceB, sigB), (pubC, nonceC, sigC)

When party B signs, they:

1. verify all the partial signatures till now (for pubC)
2. add together all the pubkeys to get the total kernel and compute the challenge e for it
3. produce a partial signature

If anyone after B cancels pubB e.g. pubC = -pubB + x*G, then the partial signature for pubC will not be valid because they can't know the private key for -pubB. This means that you know nobody after you was able to cancel your pubkey because you can verify partial sigs from them. Nobody before you could also not cancel your pubkey because they were defined before you picked your key.

Insecure if you don't remember the partial excess of everyone else in the setup phase

This means that your wallet MUST remember the (partial_excess, partial_nonce) pairs it saw at the setup stage. Otherwise, C could set a different key for A e.g. set it to pubA = -pubB + x*G; nonceA = -nonceB + y*G. Making partial excess and nonces be:

(-pubB + x*G, -nonceB + y*G), (pubB, nonceB), (pubC, nonceC)

K = -pubB + x*G + pubB + pubC
  = x*G + pubC
R = -nonceB + y*G + nonceB + nonceC
  = y*G + nonceC

e = H(K | R)  # note that these have nothing from B

The wallet from B would check the partial sig from C which would be valid and sign a payment proof stating "if kernel K gets on the chain I was paid". Party A and C could simply construct a new transaction with the same kernel because they know all the values in the total K and R. Since B signed a payment proof saying that if this kernel lands on the chain, A and C were able to scam the receiver B.

Insecure if the order parties make setup/sign changes

Consider the setup phase is setupA -> setupB -> setupC, but B is the first to do the sign step. This means that C would be able to set pubC = -pubB + x*G; nonceC = -nonceB + y*G. This is the same attack as the one above.

Conclusion

When extending this flow to 3 or more parties, it seems that you need to:

1. remember the slate information you saw (there should be no changes to it between setup and sign phases)
2. make sure that everyone that did setup after you also signs before you do and their partial signatures are valid

Another solution would be to add scaling to pubkeys, but this adds complexity to the underlying cryptographic scheme.

I want to share some lose ideas that are forming but lack mostly fundamental backing for now.

A) If I understand the problem correctly, the main issue is that if there are 3 or more parties is that you need to be sure that no one meddled with the setup before signing. Can this not be done by letting each party sign/commit to the state of the contact as additional information in the contract? As long as these signatures are there committing to the initial state all participants agree that the partial_excess, partial_nonce pairs it saw at the setup were not changed. This information can be shared as part of the message between nodes and can be used in the payment proof.

B) Perhaps a more strict version of idea A, how about first having all parties commit to the state, before putting any signatures?
So commit to setup parameters and out, in any order A, B, C, then sign in any order A, B, C. If A and B cheat C, C would have prove. Only cancelling the transaction might then be seen as proof of cheating.

C) Not sure it this idea makes sense, but I would think that perhaps having a initiator of a multiparty contract e.g. MultSig, providing additional security checks between interaction with other parties and could mitigate the chance of having any fraud and could help coordinate all the interactions. The initiator/coordinator can provide additional checks could make a transaction more secure. So instead of A-> B ->C interaction, do A- >B-> A -> C.
Meaning the initiator/orchestrate provides an additional check that the state is what it should be. I am aware I am just explaining a flow and not actual cryptographic steps here, but intuitively I think that having one wallet coordinating all the transactions somehow would make sense and would simplify multi-party transaction contracts.

D) as a more script version of C, how about fixing the order and committing to that as initiator/coordinator? Perhaps it would even make sense to fix the order of signing in advance since that would remove the ambiguity of not knowing in what state a transaction is in. Having the initiator do all the orchestration would at least mean that two people would have cooperate to scam. Lets say there would be a single receiver, why would the receiver ever want to cheat himself?

These are just lose thoughts, so I am hoping to get a better understanding from the feedback from people who do actually understand the cryptography behind this instead of just intuitively guessing like I do.

@Anynomouss thanks for reading, I'll try to answer these, but I'll first explain in short what the problem is.

Suppose we have Alice, Bob and Carol who want to construct a transaction. We'll refer to the as A, B and C. A performs the setup phase, then B does it and C is the last one. If B signs before C, he will see the picked pubkeys for the excess as A', B' and C'. But B can't know if C' is -A' + x*G. If I were B, I'd want to know that the keys I see will in fact sign the transaction and thus be a part of it. If B signs first, since C' = -A' + x*G, the signature of C would negate key A' and we'd get a valid signature for the sum of A' + B' + C'. So B was tricked into thinking A would be a part of transaction when they aren't.

With that, I don't think A) solves it because a specific signing order is required. Afaict, committing to what you saw doesn't seem to be enough as you can still show the partial excesses and nonces while providing a valid signature (because the some keys cancel other keys). I think B) wouldn't work for the same reason. I'm not sure how exactly C) would work, but it seems to me it would require everyone to trust the initiator to not lie or collude with others. Maybe this could help or provide some different directions though I'd prefer if we had a solution that would not rely on a specific coordinator. Regarding D), if you fix the order then I think you can effectively solve the above problem without a coordinator. This is the proposed solution above in the "Conclusion" section. If everyone remembers what they saw at the setup phase and checks what they see at the sign phase and follow the simple rule whatever we didn't see at the setup phase must have a valid signature, then I think it's impossible to fool them because the keys that arrived after could not have canceled the keys that arrived before because they came with a valid signature. That is, unless the key that came before you colludes with the key that comes after you in which case, they could cancel out the key that came before. It's a bit tricky and would probably need some more thinking.

Thx for explaining it. So the problem is in essence that multiple parties can create valid signatures with keys that cancel each-other out by colluding.
Can this trick also be applied if the receiving party adds an output of their own to the transaction?
In any case, I see I am just scratching the surface, this is a nice challenge to think about and discuss with other crypto enthusiast, luckily we are not in a hurry to solve this.

Yeah, that's exactly the problem. There might be other problems too, I can't recall where I saw some issues with payment proofs at the moment and whether it was related to this scheme.

Can this trick also be applied if the receiving party adds an output of their own to the transaction?

If the output stays, then the person adding that output would need to sign. The issue is that you could simply delete the output, obtain a valid transaction and send it over the wire.