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?
