[bisq-contrib] Extended MultiSig for arbitrators

[neiman]

Hey,

I begin with rewriting the problem for clarity.

There are two groups: traders and arbitrators. For simplicity assume 2
traders and 3 arbitrators.

We want a signature that is valid if:
1. The 2 traders signed it, or
2. 3-out-of-5 signed it, where at least one of them a trader.

Limitation:
- No beautiful cryptography (as in Mats-Erik suggestion) since Bitcoin
doesn't support it.
- Only standard Bitcoin txs (regular txs and M-of-N txs), since more
composed script are problematic both with Bisq implementation and are
not mined by all miners. This was cleared to me by Manfred in Slack.

I'd avoid using oracles. As it stands, oracles add elements of
centralization and trusted third-parties to Bisq, which seems to me
against Bisq general goal. It may be possible to create a completely
decentralized distributed oracle, but that's a separate discussion.

Possible solution: I suggest an implementation that put "weights" on
signatures. It can be explained by an example.

Do the following.
- Give each of the 2 trader with two separate public keys (this can be
done in Bisq software a transparent way to users).
- Give each of the 3 arbitrator, one public key.

This gives double weight to trader signatures than arbitrators signatures.

Lock the tx in a 4-out-of-7 signature.

Then the tx can spent with signaures of:
- 2 traders (=4 signatures in total),
- 1 trader and 2 arbitrator (=4 signatures in total)

The tx *cannot* be spent with signatures of:
- 1 trader and 1 arbitrator (only 3 signatures in total),
- 3 arbitrators (only 3 signatures in total).

This results in the behaviour we want. The method can be extended to a
bigger number of arbitrators.

Problems: Bisq uses bitcoinj function createMultiSigOutputScript. This
in turn uses a simple OP_CHECKMULTISIG based script, whose standard
rules allow only M-of-N with N=3.

However, bitcoinj has also a createP2SHMultiSigInputScript function. If
we switch to this, the standard rules allow M-of-N with higher number of
N (7 or 15, see here:
https://bitcoin.stackexchange.com/questions/23893/what-are-the-limits-of-m-and-n-in-m-of-n-multisig-addresses
).

Is this solution possible?


On 10.02.2018 19:23, Manfred Karrer wrote:
> My assumption is that you can add 2 private keys (privKey1, privKey2) to get a new private key privKey3.
> By adding the corresponding public keys pubKey1 and pubKey2 you would get pubKey3 which is the corresponding public key to privKey3.
>
> If we would have a oracle which delivers you a pubKey per trade and has an internal counter per time for providing the corresponding private key we could limit risk with fraudulent arbitrators.
>
> The traders would receive the fixed pubKey from the arbitrator (pubKey1) and the pubKey from the oracle (pubKey2 - created for each trade) and add both to get pubKey3.  pubKey3 is used as the 3rd key for creating the MultiSig address of the deposit transaction.
>
> At payout (dispute case, otherwise its just the 2 traders priv keys required) the arbitrator would request the private key from the oracle and only receives it if he has not exceeded his threshold of payout tx per time interval.
> With the private key from the oracle (priKey2) and his own private key (privKey1) he can create privKey3 by adding both up. privKey3 is required for his signature for the MultiSig payout. privKey3 is only valid for that trade.
>
> Maybe there is an easier model by just using a multiplication point. If that point is in a sufficiently large number space then brute forcing the point would be infeasible.
> The oracle would create a random multiplication point for each trade, deliver the pubKey to the traders but not revealing the multiplication point:
> pubKey = pubKeyArbitrator * multiplication point
> At dispute payout the arbitrator would request the multiplication point so he can create from his private key the multiplied private key for the payout tx:
> privKey = privKeyArbitrator * multiplication point
>
> Of course the whole model depends on a oracle which is big unknown if such is reasonable possible, safe and censorship resistant. Also the requests to the oracle would make the whole scheme more fragile.
> Best would be if blockchain data could be used instead of the oracle. For instance to use a deposit tx as commitment where data is put in OP_RETURN and the payout tx will reveal the secret in the OP_RETURN. Each deposit tx will have a payout tx otherwise money stays locked up and has some min. time delay, so basically we would have the properties we want but a problem is that one trade would then depend on previous trades and that would open up a can or worms for gaming the model…
>
> Maybe someone else comes up with another idea?
>
> Maybe we will not need anything like that at all as the current plan to use the blockchain to lookup how many payout transactions an arbitrator has made might be good enough.
> The traders would verify if the max. number of payout transactions by the arbitrator has not exceeded and would use another arbitrator otherwise.
> Better would be if we could use the deposit transactions but there the arbitrators pub key is not visible. The traders would also check at payout time if the limit has not exceeded, so even if a fraudulent arbitrator would take all available offers at the same time he would fail as soon his limit is reached. The service for delivering those transactions would also report unconfirmed transactions.
>
>
>
>> On 10 Feb 2018, at 07:10, Mats-Erik Pistol <meapistol at gmail.com> wrote:
>>
>> Not sure I understand.
>> You want two keys (buyer-seller) if everything goes OK and three keys (arbiter-arbiter-trader) if there is a dispute?
>> This sounds a bit like homomorphic encryption where given f(x) and f(y) it is possible compute f(z) which is the encrypted image of z = x + y without knowing f. f stands for encryption so only the person with the private key can compute the inverse function f^-1. It can even be done for multiplication but addition is far more easy.
>> In short it might be possible and would be a beautiful high tech addition to Bisq. I am bad at homomorphic encryption but I am sure Eyal (and maybe Grazcoin) does it in his (their) sleep.
>>
>> -mep
>>
>>
>>> On 10 Feb 2018, at 03:55, Manfred Karrer <mk at nucleo.io> wrote:
>>>
>>> It would increase security against a fraudulent arbitrator if we could add more required keys in the MultiSig deposit transaction, but just extending the n-of-m scheme does not work.
>>> E.g. if we use a 2-of-4 Multisig with the keys of the 2 traders and 2 instead of just 1 arbitrator the 2 arbitrators could collude and steal the funds.
>>>
>>> What if we use Elliptic curve math (I am total layman to that) and create the 3rd key in our 2-of-3 MS by adding up 2 (or even more) keys?
>>> Adding 2 public keys to get the 3rd pubKey for creating the MultiSig transaction and when doing the payout the private keys of both arbitrators are required and need to by added up to calculate the privKey required for the payout transaction.
>>>
>>> That way the arbitrator who is doing the actual dispute work would be unable to steal a traders funds (in case he would be the counter party trader himself and thus have 2 keys accessible) as he would need the 2nd arbitrator.
>>>
>>> Maybe the 2nd key holder could be even an oracle (http://www.oraclize.it have some interesting ideas) with some time constraints built in (e.g. that a fraudulent arbitrator cannot make more payout transactions in a certain time frame, thus limiting possible damage as the defrauded trader will ring the alarm bells before the arbitrator could repeat his scam).
>>>
>>> All just a rough idea and maybe there is a big flaw in it as I am not really familiar with EC math. Also nothing urgent atm but might be an interesting approach once we improve out arbitration system.
>>>
>>> Maybe someone who has experience with EC math could give his/her opinion about it?
>>>
>>> Br,
>>> Manfred


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://lists.bisq.network/pipermail/bisq-contrib/attachments/20180218/f8a55e0f/attachment.sig>