[bisq-contrib] Extended MultiSig for arbitrators

Sun Feb 18 17:17:26 UTC 2018

Hi,

thanks a lot for your input and suggestion!

> On 18 Feb 2018, at 03:55, neiman <neiman at c-base.org> wrote:
> 
> 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.

In fact I would love to have an additional restriction:
The arbitrator can only sign n payout transactions in a certain time persiod. If we achieve that then even the additional signature is not that important as the rate limitation of payouts together with the trade amount limit will create a sufficient protection for limiting maximal damage. An arbitrator can be blocked by the trader and by the Bisq developers once detected as scammer.

> 
> 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.

The relay of non-standard transactions if probably the main problem. I don’t know about the policies of miners but I assume also there most will follow the standard rule.

> 
> 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.

Ah great idea! Someone came up in the past with that as well but I forgot about it!
> 
> 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
> ).

No, we use P2SH already.
Only limitations are the max. allowed size of scripts which seems to be too limiting for a 4of7 MS. Maybe they relaxed the rules in the meantime but from the link you posted it would old allow a 4of6 MS.

"For standardness, it depends on the version. Up to v0.9.*, the reference client required the total spending script to be at most 500 bytes.

For compressed keys, this means m*73 + n*34 <= 496 (up to 1-of-12, 2-of-10, 3-of-8 or 4-of-6)."
https://bitcoin.stackexchange.com/questions/23893/what-are-the-limits-of-m-and-n-in-m-of-n-multisig-addresses <https://bitcoin.stackexchange.com/questions/23893/what-are-the-limits-of-m-and-n-in-m-of-n-multisig-addresses>

But a 4of6 would be sufficient as well: 2 traders have 2 keys each and 2 arbitrators have 1 key each
- 2 traders have 4 keys
- 1 trader + 2 arbitrators have 4 keys

> 
> Is this solution possible?

Yes I think that would be possible.
Only downside is that the complexity of the payout tx will increase as 3 parties are involved instead of 2 as it is now.
Another downside is that the payout tx becomes larger and thus more expensive. That might be a considerable factor with the fee peaks we saw in December (though I think that was mainly caused by spam attack, but beside that high fees will become more and more an issue).

It would also shift the risk model from 1 fraudulent arbitrator to 2 fraudulent arbitrators. That might be not really sufficient if the additional arbitrator can be chosen freely.  The arbitrator is chosen by the traders and the intersection group of the selected arbitrators will be taken for the random selection. E.g. Trader 1 has arbitrator A, B and C. Trader 2 has B, C and D. So B and C are the intersection and randomly we chose atm 1 arbitrator from that group. The random selection happens based on trade ID so it is verifiable by both peers. The selection atm has its weakness as well but I think that could be fixed by using a past block ID to get a secure random input. NIST beacons or the random value generated for the TOR consensus protocol might be other options.

If we have once a lot of arbitrators in different regions with different languages, the language will become the main selection criterium. Traders will select those arbitrators which support their native language.
A fraudulent arbitrator could set up a second arbitrator and if there are not many more in that language, the chances the gets selected his both arbitrator in a trade are high.
All that will get mitigated by the plans to use mediators for dispute resolution who have no key at all. The dispute should get resolved by both traders if possible, so no 3rd key is required in the first place. Only for those few cases where one trader rejects to cooperate or is not available we need the arbitrators key and then the mediator will pass the result over to the arbitrator who does the signing. But in such cases the language is irrelevant as the arbitrator will not be part of the dispute resolution. So with that model we will not need a lot of arbitrators and language barriers are obsolete.

To use the blockchain data to see how many payout transactions an arbitrator has done in a certain time interval has it’s own problems:
- The payout tx does not reveal which key holder has added the signature. There are 3 pubkeys there but there is no correlation to the provided signatures. Only way would be to verify the script to see which key matches a provided signature and then see if the arbitrator was part of the signers.
- A fraudulent arbitrator could do all his payout transactions in one go so a lookup in the blockchain data will not work (would require scanning the mempool as well and also that is not reliable).

No clear idea yet how to make that really secure (we still have the BSQ bonding which gives game-theoretical incentives to not act malicious, but would prefer more “dry” security).

I still see a kind of rate limited "key dispenser” oracle as possible solution. I know oracles are an unsolved holy grail by itself, but http://www.oraclize.it/ <http://www.oraclize.it/> might be close to at least a reasonable approach for our needs.

So what would be our requirement?
- We want an oracle which delivers us a pubkey for a deposit tx. It gets mapped to the trade ID. So for each trade we have a separate key. Both traders give the selected arbitrators pubKey to the oracle when requesting. Only if both traders match the arbitrators pubKey it is considered valid.
- The oracle delivers the private key to the arbitrator in dispute case. The arbitrator need to provide a signature of the trade ID as proof that he is the right arbitrator for the trade in dispute. The oracle checks if the pubKey matches to the one the traders posted at their request earlier. The oracle checks how many payout requests the arbitrator has done in a certain time interval (e.g. not more then 10 the last 10 days). If exceeded he gets rejected and need to wait until he is below the threshold.

We could build that with the 4of6 scheme as you suggested. I am wondering if there would be a EC math based solution to create the pubkey and privkey for the MS in a way that it adds up both and we could stick with the 2of3 MS.
E.g.:
- pub key of oracle is one part of the addition, the pub key of the arbitrator the other part
- priv key the arbitrator requests from the oracle  is one part of the addition, the priv key of the arbitrator the other part

But the bigger problem is the question if a trust minimised oracle is feasible and if so what are the costs and risks from its complexity.
Further the whole scheme would add quite a lot of complexity which comes with it’s own new problems….

Best would be if we would find a way to use the blockchain for both main requirements:
- time based rate limiting
- providing additional key material for securing the MS

Br,
Manfred

> 
> 
> 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 --------------
An HTML attachment was scrubbed...
URL: <http://lists.bisq.network/pipermail/bisq-contrib/attachments/20180218/69666e6c/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: Message signed with OpenPGP
URL: <http://lists.bisq.network/pipermail/bisq-contrib/attachments/20180218/69666e6c/attachment-0001.sig>