4
$\begingroup$

When I first came across the Bitcoin multisignature scheme, I wondered that it remarkably looked similar to what Shamir Secret Sharing does (SSS), but then by using facilities in the bitcoin scripting language instead. I recently read that the Monero cryptocurrency are also looking at implementing a multisig scheme.

I wonder, would it be possible to implement a multisign scheme completely separate from the cryptocurrency's blockchain just by using SSS?

Edit: To avoid confusion, I have now used the symbols $\oplus$ and $\odot$ for elliptic sum and multiplication, while using $+$ for undistorted arithmetic (for use in SSS).

Say that we have 3 parties, Alice, Bob, and Charlie, and that they want to set up a 2-of-3 signature scheme. If $s$ stands for secret (private key) and $p$ stands for public key, and $G$ stands for the generator, and if we carry out all multiplications in the associated modular field, we have:

  • Alice: $s_1$ and $p_1=G \odot s_1$
  • Bob: $s_2$ and $p_2=G \odot s_2$
  • Charlie: $s_3$ and $p_3=G \odot s_3$

We could create a composed key $(s_0,p_0)$ with these individual keys, just by adding them up:

  • $s_0 = s_1 \oplus s_2 \oplus s_3$
  • $p_0 = p_1 \oplus p_2 \oplus p_3$

Alice, Bob, and Charlie would disclose $p_1$, $p_2$, and $p_3$ to each other, and hence have knowledge of $p_0$, but would not know the combined secret $s_0$ that would control funds parked in $p_0$.

Alice now needs to split her secret over Bob and Charlie.

Say that Alice pick an arbitrary number $a_1$, and constructs a line $y=s_1+a_1x$, in which her secret $s_1$ is the intercept. In accordance with the SSS, she can arbitrarily pick two points $(x,y)$ on that line. The point $(x_{AB},y_{AB}=s_1+a_1x_{AB})$ will go to Bob and the point $(x_{AC},y_{AC}=s_1+a_1x_{AC})$ will go to Charlie.

Of course, Alice could be lying, and just share whatever numbers to Bob and Charlie. Therefore, in a elliptic twist to the Feldman scheme, to keep Alice honest, she also supplies the numbers $G \odot s_1$ and $G \odot a_1$. This should allow Bob and Charlie to verify that their shares in $s_1$ are valid, while Alice would also not reveal the secrets $s_1$ and $a_1$. For example, Bob could verify his share in Alice's secret by checking that the following holds: $$G \odot y_{AB} = G \odot (s_1 + a_1 x_{AB}) = G \odot s_1 + (G \odot a_1) x_{AB} $$

All players send their shares as following:

from/to     Alice   Bob     Charlie
Alice               AB      AC
Bob         BA              BC
Charlie     CA      CB        

Where each share is defined as the following tuples:

  • $AB = (x_{AB},y_{AB},G \odot s_1,G \odot a_1)$
  • $AC = (x_{AC},y_{AC},G \odot s_1,G \odot a_1)$
  • $BA = (x_{BA},y_{BA},G \odot s_2,G \odot a_2)$
  • $BC = (x_{BC},y_{BC},G \odot s_2,G \odot a_2)$
  • $CA = (x_{CA},y_{CA},G \odot s_3,G \odot a_3)$
  • $CB = (x_{CB},y_{CB},G \odot s_3,G \odot a_3)$

Not one party has full knowledge of $s_0$. However, any two parties have enough knowledge to reconstruct $s_0$.

Charlie now deposits the amount to escrow in the 2-of-3 signature scheme on public key $p_0$.

If Alice wants to assist Bob to gain control over $p_0$:

  • Alice discloses to Bob: $s_1$ and $(x_{CA},y_{CA})$
  • Bob reconstructs $s_3$ from $(x_{CA},y_{CA})$ and $(x_{CB},y_{CB})$
  • Bob reconstructs $s_0$ from $s_1$,$s_2$ and $s_3$ and now has control over the funds in $p_0$.

I wonder, is there a reason why this would not work as an alternative to the existing Bitcoin multisignature scheme?

$\endgroup$
13
  • $\begingroup$ It appears to me that this does not give the actual functionality of Bitcoin multisig transactions. Namely, your scheme simply gives a way to reveal $s_0$ to one of three parties, who then has control and can transfer the funds as he likes. As I understand Bitcoin multisig the funds should only be transferable if 2 out of 3 agree to do so. $\endgroup$
    – Guut Boy
    Aug 24, 2016 at 13:14
  • $\begingroup$ What you actually need to something that allows any 2 out of 3 parties to sign with $s_0$. This could of course be done using MPC. Or possibly some special signature scheme. $\endgroup$
    – Guut Boy
    Aug 24, 2016 at 13:27
  • $\begingroup$ This can be done using something called threshold signatures which is indeed a special case of MPC for signing. Threshold signature schemes are known for both RSA and ECDSA. $\endgroup$ Aug 24, 2016 at 21:06
  • 1
    $\begingroup$ @Guut Boy: In the example, it does require the collaboration of Alice and Bob to control the funds. Any combination (Alice,Bob), (Alice,Charlie), (Bob,Charlie) would also grant control over the funds to one chosen player. Isn't that roughly the same effect as in a 2-of-3 signature scheme? $\endgroup$
    – erik
    Aug 25, 2016 at 2:23
  • $\begingroup$ @Yehuda Lindell: Is it acceptable to do treshold signing using the Feldman scheme/addon to SSS? Or do they use an alternative verification algorithm (for security reasons or so)? $\endgroup$
    – erik
    Aug 25, 2016 at 3:57

1 Answer 1

0
$\begingroup$

As also mentioned in the comments, this scheme will not work similarly to how Bitcoin's multisig works, because when secret shares are revealed a party (e.g Bob in the above example) can get access to the key pair $s_0, p_0$. In contrast Bitcoin's multisig doesn't work that way. In a $t-n$ multisig, every party has its' key pair and every public key is written in the bitcoin script of the transaction. Take a look at this answer.

For the reference, a solution to this problem where the key pair is never revealed to any participant was provided and implemented by Yehuda Lindell et al., who has also commented above. Threshold signing was used. You can read more in [1] and [2]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.