1  # Player 1:
  2  #
  3  #   $ sage multisig.sage genshare 2 3
  4  #   A_0 = (17885028560402702239015261002188504514192120716688655005384557793085172279782, 8478670718018646753668209243232218399157692386519596227477013206445567901574)
  5  #   A_1 = (24159996358010728217037819815568538754372914232633035350125672407860245980511, 25930880768349059332486494233731724414031492717763788767169325464072537905825)
  6  #   
  7  #   18245370559787825905107196417449809168129753681991950558452633836050485263625*X + Y + 21540401009192565430578225487575742717824479971010380831145688671749585986737
  8  #   
  9  #   Player 1's R = (1, 18110273049677706376100070599318402040771879310880963369761162988986654645832)
 10  #   Player 2's R = (2, 28812924799218929326885620434040569836005182110830660190988271901329532330304)
 11  #   Player 3's R = (3, 10567554239431103421778424016590760667875428428838709632535638065279047066679)
 12  #
 13  # Player 2:
 14  #
 15  #   $ sage multisig.sage genshare 2 3
 16  #   A_0 = (802940932777049145807706375204159819724468245569326332695920733054960506640, 16355306126743352920399387200062438463930792131448355230670435463427127600465)
 17  #   A_1 = (18141591414190824859071415735841428554530479628199222928098733408655160229999, 8126608045648459195646305845881115977993411928279311595258374101920586157117)
 18  #   
 19  #   11632470451635415873896303993978816754215391793499851090581681689882331027728*X + Y + 14165208049524082319699866276606579004249018988481566200129536690961988099823
 20  #   
 21  #   Player 1's R = (1, 3150343808169550662296575981586581204898645699960230088968524367549043820546)
 22  #   Player 2's R = (2, 20465895665863183644293018239779741414046310388402026378066585426060075740915)
 23  #   Player 3's R = (3, 8833425214227767770396714245800924659830918594902175287484903736177744713187)
 24  #
 25  # Player 3:
 26  #
 27  #   $ sage multisig.sage genshare 2 3
 28  #   A_0 = (18050147058625614196833411623290233672504963362553094195996683497184802776885, 1558020177192412780876956779873498858051955811269538614817345479760770446460)
 29  #   A_1 = (8859924332949089269591379272271847007387528856001855566494832087904814398546, 27961455601858187272958269886544614132704520355314277906405837204662338231452)
 30  #   
 31  #   22603695278713704898809499991696306162603661219853447180662052608597912268649*X + Y + 26665809323852841663944379970510953158263212308412307792093486582513151778711
 32  #   
 33  #   Player 1's R = (1, 8626540016091551149031612542136694605859239435617539786603946305675661848834)
 34  #   Player 2's R = (2, 14970867046706895106114858802612365406618634697705739985621636445471112528282)
 35  #   Player 3's R = (3, 21315194077322239063198105063088036207378029959793940184639326585266563207730)
 36  
 37  # Each player has now generated the curve, shared its commits, and distributed shares.
 38  # Now we recover the public key using all A0s
 39  #
 40  #   $ sage multisig.sage pubkey "(17885028560402702239015261002188504514192120716688655005384557793085172279782, 8478670718018646753668209243232218399157692386519596227477013206445567901574)" "(802940932777049145807706375204159819724468245569326332695920733054960506640, 16355306126743352920399387200062438463930792131448355230670435463427127600465)" "(18050147058625614196833411623290233672504963362553094195996683497184802776885, 1558020177192412780876956779873498858051955811269538614817345479760770446460)"
 41  #
 42  #   (9803495978299341257553881350441085748898862974053305000078308077444698847765 : 7803011951094511021525891181798443393652882333120996671357964800654859381546 : 1)
 43  
 44  # To recover the shared secret, player's 1 and 2 will work together to
 45  # recreate all 3 curves.
 46  #
 47  #   $ sage multisig.sage recover "(1, 18110273049677706376100070599318402040771879310880963369761162988986654645832)" "(2, 28812924799218929326885620434040569836005182110830660190988271901329532330304)"
 48  #   21540401009192565430578225487575742717824479971010380831145688671749585986737
 49  #
 50  #   $ sage multisig.sage recover "(1, 3150343808169550662296575981586581204898645699960230088968524367549043820546)" "(2, 20465895665863183644293018239779741414046310388402026378066585426060075740915)"
 51  #   14165208049524082319699866276606579004249018988481566200129536690961988099823
 52  #
 53  #   $ sage multisig.sage recover "(1, 8626540016091551149031612542136694605859239435617539786603946305675661848834)" "(2, 14970867046706895106114858802612365406618634697705739985621636445471112528282)"
 54  #   26665809323852841663944379970510953158263212308412307792093486582513151778711
 55  #
 56  # You can see each command returns the constant coefficient in each curve.
 57  # Finally we combine these to get the final curve and hence shared secret.
 58  #
 59  #   $ sage multisig.sage combine 14165208049524082319699866276606579004249018988481566200129536690961988099823 21540401009192565430578225487575742717824479971010380831145688671749585986737 26665809323852841663944379970510953158263212308412307792093486582513151778711
 60  #   Secret: 4475373763911391702436979230349320953610598304020960064009226448437999969077
 61  #   Pubkey: (9803495978299341257553881350441085748898862974053305000078308077444698847765 : 7803011951094511021525891181798443393652882333120996671357964800654859381546 : 1)
 62  #
 63  # We can see the public key matches what we got in the 'pubkey' step.
 64  
 65  import argparse, base64, sys
 66  
 67  q = 0x40000000000000000000000000000000224698fc0994a8dd8c46eb2100000001
 68  K = GF(q)
 69  P.<X, Y> = K[]
 70  
 71  p = 0x40000000000000000000000000000000224698fc094cf91b992d30ed00000001
 72  Fp = GF(p)
 73  E = EllipticCurve(Fp, (0, 5))
 74  G = E(
 75      23241645597038891398529199502196854108878665864265357905694087894995100434173,
 76      14702009283686283423048268817274882285027504402886079870290245450065579125215
 77  )
 78  assert G.order() == q
 79  
 80  def genshare(args):
 81      t, n = args.t, args.n
 82      assert t <= n
 83      C = Y
 84      A = []
 85      for i in range(t):
 86          a_i = K.random_element()
 87          C += a_i * X^i
 88          A_i = a_i*G
 89          print(f"A_{i} = ({A_i[0]}, {A_i[1]})")
 90          A.append(A_i)
 91  
 92      print()
 93      print(C)
 94      print()
 95  
 96      R = []
 97      for j in range(1, n+1):
 98          x_j = j
 99          y_j = -C(X=x_j, Y=0)
100          assert C(X=x_j, Y=y_j) == 0
101          R_j = (x_j, y_j)
102          print(f"Player {j}'s R = {R_j}")
103          R.append(R_j)
104  
105      # Each player upon receiving their shares should perform this check
106      def eval_C(x):
107          P = E(0)
108          for i, A_i in enumerate(A):
109              P += x^i * A_i
110          return P
111  
112      for R_j in R:
113          x_j, y_j = R_j
114          assert y_j*G + eval_C(x_j) == E(0)
115  
116  def pubkey(args):
117      P = E(0)
118      for A0str in args.A0:
119          x, y = A0str.split(",")
120          x = x.strip("(")
121          y = y.strip(") ")
122          x, y = K(x), K(y)
123          A0 = E(x, y)
124          P += A0
125      print(P)
126  
127  def recover(args):
128      R = []
129      for Rjstr in args.Rj:
130          x, y = Rjstr.split(",")
131          x = x.strip("(")
132          y = y.strip(") ")
133          x, y = K(x), K(y)
134          R_j = (x, y)
135          R.append(R_j)
136  
137      # Create the Vandermonde matrix with a₀, …, aₜ₋₁ as indeterminates.
138      V = []
139      t = len(R)
140      y = []
141      for R_j in R:
142          x_j, y_j = R_j
143          y.append(y_j)
144  
145          V.append([x_j^i for i in range(t)])
146      V = matrix(V)
147      y = vector(y)
148  
149      a = V^-1 * -y
150      print(a[0])
151  
152  def combine(args):
153      a0 = K(0)
154      for a in args.a0:
155          a0 += a
156      print(f"Secret: {a0}")
157      print(f"Pubkey: {a0*G}")
158  
159  def main():
160      parser = argparse.ArgumentParser(prog="multisig.sage")
161      subparsers = parser.add_subparsers(required=True)
162  
163      parser_genshare = subparsers.add_parser("genshare", help="Generate a share")
164      parser_genshare.add_argument("t", type=int, help="threshold for recovery")
165      parser_genshare.add_argument("n", type=int, help="total players")
166      parser_genshare.set_defaults(func=genshare)
167  
168      parser_pubkey = subparsers.add_parser("pubkey",
169                                            help="Compute shared pubkey")
170      parser_pubkey.add_argument("A0", nargs="+")
171      parser_pubkey.set_defaults(func=pubkey)
172  
173      parser_recover = subparsers.add_parser("recover",
174                                             help="Recover shared secret")
175      parser_recover.add_argument("Rj", nargs="+")
176      parser_recover.set_defaults(func=recover)
177  
178      parser_combine = subparsers.add_parser("combine",
179                                             help="Combine shared secrets")
180      parser_combine.add_argument("a0", type=int, nargs="+")
181      parser_combine.set_defaults(func=combine)
182  
183      args = parser.parse_args()
184      args.func(args)
185  
186  main()
187