[bisq-contrib] Extended MultiSig for arbitrators

Sun Feb 18 17:20:52 UTC 2018

Hi Tomas,

thanks for your input!

That might be indeed a problem as at time when the pub key is requested the addition of the priv keys cannot be checked if they are in the valid range. So it might be that the pubkeys fall in the valid range but not the priv keys. The oracle would never get the arbitrators priv key so the arbitrator would be the only one at dispute payout time to be able to check for valid range of the priv keys.

Br,
Manfred

> On 18 Feb 2018, at 07:53, Tomas Kanocz <tomas.kanocz at cnl.sk> wrote:
> 
> 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 <mailto: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 <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 <mailto: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 <mailto: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 <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 <https://lists.bisq.network/listinfo/bisq-contrib>
> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.bisq.network/pipermail/bisq-contrib/attachments/20180218/2f470193/attachment.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/2f470193/attachment.sig>