3
$\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$
  • $\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 '16 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 '16 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$ – Yehuda Lindell Aug 24 '16 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 '16 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 '16 at 3:57

Your Answer

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

Browse other questions tagged or ask your own question.