Computer-implemented method of generating a threshold vault

Abstract

A method and devices for securely and privately generating a threshold vault address and distributed individual key shares reliant upon individually selected polynomial functions, without revealing the key shares and without ever reconstructing the private key. A digital asset stored at the threshold vault address may be used as an input to a transaction through generating a digital signature corresponding to the threshold vault address. Methods and devices are described for collaboratively generating the digital signature without reconstructing the private key or revealing individual key shares. Methods and devices are described for refreshing the distributed private key shares.

1 . A computer-implemented method of securely generating a threshold vault, where the threshold vault has a public key address, a private key and a threshold k, each node of a plurality of nodes having a respective first secret and a respective k-1 degree polynomial function with that node's respective first secret set as a constant term of said polynomial function, the nodes including a first node having a first polynomial function, the method performed by the first node comprising:
 for each other node of the plurality of nodes, setting a variable in the first polynomial function to a value associated with that other node, finding a respective result of the polynomial function for that value, and securely communicating the respective result to that other node;   receiving, from a plurality of the other nodes, respective second secrets, where each of the respective second secrets is a result of that other node's respective polynomial function for a first value associated with said first node;   communicating, to the other nodes, an elliptic curve point multiplication of each of the respective results;   receiving, from the plurality of the other nodes, elliptic curve point multiplications of the respective second secrets shared by the other nodes with any of the nodes;   forming and storing a first private key share of the private key based on a sum of the respective second secrets received from the other nodes; and   determining, from at least a threshold number of nodes, the public key corresponding to the private key based on a sum of the received elliptic curve point multiplications of the respective second secrets and using polynomial interpolation.   
     
     
         2 . The method of  claim 1 , wherein each respective polynomial function is selected independently by the respective node corresponding to said polynomial function, and wherein each respective polynomial function has a different set of coefficients. 
     
     
         3 . The method of  claim 1 , wherein each respective polynomial function is of form:
   ƒ i =Σ t=0   (k−1) α t   x   t  mod η
   where ƒ i  is the polynomial function of an ith node, n is an integer order of an elliptic curve, x is the variable in the polynomial function, α t  is a set of coefficients for the polynomial function, and t is an index.   
     
     
         4 . The method of  claim 1 , further comprising communicating to the other nodes an elliptic curve point multiplication of each coefficient of the first polynomial function. 
     
     
         5 . The method of  claim 1 , further comprising receiving, from the plurality of the other nodes, an elliptic curve point multiplication of each coefficient of the respective polynomial functions corresponding to said nodes. 
     
     
         6 . The method of  claim 1 , further comprising validating the respective second secrets received from the other nodes. 
     
     
         7 . The method  claim 1 , wherein forming the first private key share includes determining a sum of form: 
       
         
           
             
               
                 
                   d 
                   
                     A 
                     ⁡ 
                     ( 
                     i 
                     ) 
                   
                 
                 = 
                 
                   
                     ∑ 
                     
                       h 
                       = 
                       1 
                     
                     j 
                   
                   
                     
                       f 
                       h 
                     
                     ( 
                     i 
                     ) 
                   
                 
               
               ⁢ 
               mod 
               ⁢ 
               n 
             
           
         
         where d A(i)  is the first private key share, h is an index of the other nodes, f h ( ) is the respective polynomial function of an h th  node, n is an integer order of an elliptic curve, and i is the first value associated with said first node, and wherein each non-null f h (i), h=1, . . . j is one of the respective second secrets. 
       
     
     
         8 . The method claimed in  claim 1 , further comprising modifying the first private key share through collaboratively participating with the other nodes in a dealerless secret distribution of a joint zero secret share whereby the first node receives a first zero secret share and modifies the first private key share by adding the first zero secret share to form and store a modified first private key share. 
     
     
         9 . The method of  claim 1 , wherein the step of determining the public key comprises determining said polynomial function, by means of determining coefficients of the polynomial function from a plurality of known values of the received elliptic curve point multiplications of the respective second secrets. 
     
     
         10 . The method according to  claim 9 , wherein the step of determining said polynomial function comprises executing an error correction algorithm. 
     
     
         11 . The method according to  claim 9 , wherein the step of determining said polynomial function comprises executing a Berlekamp-Welch decoding algorithm. 
     
     
         12 . The method according to  claim 9 , wherein the step of determining said polynomial function comprises:
 defining an error locator polynomial function and a second polynomial function, wherein the second polynomial function is a product of said polynomial function and said error locator polynomial function, determining coefficients of said second polynomial function and said error locator polynomial function from a plurality of known values of the received elliptic curve point multiplications of the respective second secrets, and determining said polynomial function from said second polynomial function and an error detector polynomial function.   
     
     
         13 . A computer-implemented method of securely generating a digital signature for a message relating to a threshold vault, where the threshold vault has a public key address, a private key and a threshold, each node of a plurality of nodes having a respective private key share, ephemeral key share, multiplicative mask share, first additive mask share, and second additive mask share, the method performed by a first node of the plurality of nodes comprising:
 generating and sharing a double masked key share from the ephemeral key share masked by the multiplicative key share and by the first additive key share, and an elliptic curve point multiplication of the multiplicative key share;   receiving, from a plurality of other nodes, the respective double masked key shares corresponding to said nodes and respective elliptic curve point multiplication (ECPM) of the multiplicative key shares corresponding to said nodes;   determining a first signature component using polynomial interpolation over the double masked key shares and polynomial interpolation over the ECPM of the multiplicative key shares; and   determining and revealing a second signature component share based on the message, the private key share, the first signature component, the ephemeral key share, masked by the second additive mask share,   whereby the second signature component is obtainable from signature shares of at least a threshold number of nodes, wherein the signature shares include the respective second signature component shares of the plurality of the nodes.   
     
     
         14 . The method of  claim 13 , further comprising using dealerless secret distribution to generate the first node's private key share, ephemeral key share, and multiplicative mask share. 
     
     
         15 . The method of  claim 13 , further comprising using joint zero secret share to generate the first node's first additive mask share and second additive mask share. 
     
     
         16 . The method of  claim 13 , wherein generating the double masked key share includes calculating:
   ϑ i   =D   k(i) α i +β i  mod η
   where ϑ i  is the double masked key share, D k(i)  is the first node's ephemeral key share, α i  is the first node's multiplicative mask share, β i  is the first node's first additive mask share, and η is an integer order of an elliptic curve.   
     
     
         17 . The method of  claim 13 , wherein the polynomial interpolation over the double masked key shares results in a multiplicatively-masked ephemeral key, the polynomial interpolation over the ECPM of the multiplicative mask shares results in an ECPM of a multiplicative mask, and wherein determining the first signature component includes determining a product of the ECPM of the multiplicative mask and an inverse of the multiplicatively-masked ephemeral key. 
     
     
         18 . The method of  claim 13 , wherein determining the second signature component share, s i , includes determining:
     s   i   =D   k(i) ( e+d   A(i)   r )+ c   i  mod η
   where D k(i)  is the first node's ephemeral key share, e is a hash of the message, d A(i)  is the first node's private key share, r is the first signature component, c i  is the second additive mask share, and n is an integer order of an elliptic curve.   
     
     
         19 . The method of  claim 13 , further comprising determining the second signature component through polynomial interpolation over the signature shares of at least the threshold number of the nodes. 
     
     
         20 . The method of  claim 19 , further comprising adding the first signature component and the second signature component to a transaction containing the message and submitting the transaction to a blockchain network. 
     
     
         21 . A computer implemented method of multi-party computation, the method comprising:
 distributing, among a plurality of first nodes, shares of a plurality of secrets, wherein each said secret is a constant term of a respective polynomial function, and each said share is a respective value of the polynomial function associated with said first node, wherein the secret is accessible by means of polynomial interpolation of a threshold number of said shares and is inaccessible in the absence of said threshold number of shares;   receiving, at a second node, from each of a plurality of said first nodes, a respective share of a computed secret, wherein each said first node calculates its share of the computed secret by carrying out at least one predetermined computation on shares of a respective plurality of said secrets allocated to said nodes; and   determining, at said second node, the computed secret by means of polynomial interpolation of at least a threshold number of shares, wherein said shares include said shares of said computed secret.   
     
     
         22 . The method according to  claim 21 , wherein each respective polynomial function is of form:
   ƒ i =Σ t=0   (k−1) α t   x   t  mod ƒ
   where ƒ i  is the polynomial function of an ith node, n is an integer order of an elliptic curve, x is a variable in the polynomial function, α t  is a set of coefficients for the polynomial function, and t is an index.   
     
     
         23 . The method according to  claim 21 , further comprising communicating to a plurality of nodes an elliptic curve point multiplication of each coefficient of a plurality of said polynomial functions. 
     
     
         24 . The method according to  claim 21 , further comprising communicating to a plurality of nodes an elliptic curve point multiplication of a value of at least one said polynomial function associated with each of said plurality of said nodes. 
     
     
         25 . The method according to  claim 24 , further comprising verifying consistency between an elliptic curve point multiplication of a value of at least one said polynomial function associated with at least one said node and a sum of elliptic curve point multiplications of coefficients of said polynomial function. 
     
     
         26 . The method according to  claim 21 , wherein determining a share of the computed secret includes determining:
   μ i   =x   i   .y   i  mod  n  
   wherein x i  is a share of a first secret, y i  is a share of a second secret and η is an integer order of an elliptic curve.   
     
     
         27 . The method according to  claim 21 , wherein determining a share of the computed secret includes determining:
     x   i   +y   i  mod  n      wherein x i  is a share of a first secret, y i  is a share of a second secret and η is an integer order of an elliptic curve.   
     
     
         28 . The method according to  claim 21 , wherein determining a share of the computed secret includes determining:
     x   i   −1  mod  n      wherein x i   −1  is a reciprocal, modulo n, of a share of a first secret, and n is an integer order of an elliptic curve.   
     
     
         29 . The method according to  claim 21 , further comprising providing a modified share of the computed secret by adding a share of a zero secret, wherein the zero secret is a constant term of a polynomial function, equal to zero, such that the computed secret is accessible by means of polynomial interpolation of a threshold number of said modified and is inaccessible in the absence of said threshold number of shares. 
     
     
         30 . The method according to  claim 21 , wherein the step of determining the computed secret comprises determining a polynomial function corresponding to the shares of the computed secret, by means of determining coefficients of the polynomial function from a plurality of known values of the shares of the computed secret. 
     
     
         31 . The method according to  claim 30 , wherein the step of determining said polynomial function comprises executing an error correction algorithm. 
     
     
         32 . The method according to  claim 30 , wherein the step of determining said polynomial function comprises executing a Berlekamp-Welch decoding algorithm. 
     
     
         33 . The method according to  claim 30 , wherein the step of determining said polynomial function comprises:
 defining an error locator polynomial function and a second polynomial function, wherein the second polynomial function is a product of said polynomial function associated with the shares of the computed secret and said error locator polynomial function, determining coefficients of said second polynomial function and said error locator polynomial function from a plurality of known values of said shares of said computed secret, and determining said polynomial function associated with said shares of said computed secret from said second polynomial function and an error detector polynomial function.   
     
     
         34 - 39 . (canceled) 
     
     
         40 . A computing device to participate in a blockchain transaction, the computing device being a first node of a plurality of nodes, the computing device comprising:
 a processor;   a memory;   a network interface to provide network connectivity to the other nodes in the plurality of nodes; and   a blockchain application containing computer-executable instructions that, when executed by the processor, cause the processor to carry out a method of securely generating a threshold vault, where the threshold vault has a public key address, a private key and a threshold k, each node of the plurality of nodes having a respective first secret and a respective k−1 degree polynomial function with that node's respective first secret set as a constant term of said polynomial function, the nodes including a first node having a first polynomial function, the method performed by the first node comprising:   for each other node of the plurality of nodes, setting a variable in the first polynomial function to a value associated with that other node, finding a respective result of the polynomial function for that value, and securely communicating the respective result to that other node;   receiving, from a plurality of the other nodes, respective second secrets, where each of the respective second secrets is a result of that other node's respective polynomial function for a first value associated with said first node;   communicating, to the other nodes, an elliptic curve point multiplication of each of the respective results;   receiving, from at least the plurality of other nodes, elliptic curve point multiplications of the respective second secrets shared by the other nodes with any of the nodes;   forming and storing a first private key share of the private key based on a sum of the respective second secrets received from the other nodes; and   determining the public key corresponding to the private key based on a sum of the received elliptic curve point multiplications of the respective second secrets and using polynomial interpolation.   
     
     
         41 . A computing device to participate in a blockchain transaction, the computing device being a first node of a plurality of nodes, the computing device comprising:
 a processor;   a memory;   a network interface to provide network connectivity to the other nodes in the plurality of nodes; and   a blockchain application containing computer-executable instructions that, when executed by the processor, cause the processor to carry out a method of securely generating a digital signature for a message relating to a threshold vault, where the threshold vault has a public key address, a private key and a threshold, each node of the plurality of nodes having a respective private key share, ephemeral key share, multiplicative mask share, first additive mask share, and second additive mask share, the method performed by a first node of the plurality of nodes comprising:
 generating and sharing a double masked key share from the ephemeral key share masked by the multiplicative key share and by the first additive key share, and an elliptic curve point multiplication of the multiplicative key share; 
 receiving, from a plurality of other nodes, the respective double masked key shares corresponding to said nodes and respective elliptic curve point multiplication (ECPM) of the multiplicative key shares corresponding to said nodes; 
 determining a first signature component using polynomial interpolation over the double masked key shares and polynomial interpolation over at least a threshold number of first signature shares including the ECPM of the multiplicative key shares; and 
 determining and revealing a second signature component share based on the message, the private key share, the first signature component, the ephemeral key share, masked by the second additive mask share, 
 whereby the second signature component is obtainable from at least the threshold number of second signature shares including the respective second signature component shares of the plurality of the nodes. 
   
     
     
         42 . A computing device to participate in a blockchain transaction, the computing device being a first node of a plurality of nodes, the computing device comprising:
 a processor;   a memory;   a network interface to provide network connectivity to the other nodes in the plurality of nodes; and   a blockchain application containing computer-executable instructions that, when executed by the processor, cause the processor to carry out a method of multi-party computation,   the method comprising:
 distributing, among the plurality of first nodes, shares of a plurality of secrets, wherein each said secret is a constant term of a respective polynomial function, and each said share is a respective value of the polynomial function associated with said first node, wherein the secret is accessible by means of polynomial interpolation of a threshold number of said shares and is inaccessible in the absence of said threshold number of shares; 
 receiving, at a second node, from each of a plurality of said first nodes, a respective share of a computed secret, wherein each said first node calculates its share of the computed secret by carrying out at least one predetermined computation on shares of a respective plurality of said secrets allocated to said nodes; and 
 determining, at said second node, the computed secret by means of polynomial interpolation of at least a threshold number of shares including said shares of said computed secret.