[bisq-contrib] Extended MultiSig for arbitrators

Sun Feb 18 12:53:51 UTC 2018

Hello,

I can not really add much to the debate as am not an ECC expert, but I know
the private keys have a valid range. Not all numbers in the 2^256 range are
valid privkeys to secp256k1, as they would break the 1 privkey maps to 1
pub key.

So the private key upper bound is the order of the subgroup for secp256k1,
lets call it N.

One would need to check if p1+p2 is greater than N, if it is it can not be
used. It would just cause more headache in that case imho ... In case you
do mod n, you would have to check the lower bound. Either way it seems
cumbersome.

But again am not an expert in ECC, but this is one 'flaw' that might give
that a stop. Often knowing where not to go helps, so I hope this comme  is
helpful :)

Tomas

Dňa 18.2.2018 9:55 používateľ "neiman" <neiman at c-base.org> napísal:

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

_______________________________________________
bisq-contrib mailing list
bisq-contrib at lists.bisq.network
https://lists.bisq.network/listinfo/bisq-contrib
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.bisq.network/pipermail/bisq-contrib/attachments/20180218/017e4f52/attachment.html>