The GG20 (Gennaro, R., & Goldfeder, S. (2020) [1]) method implements an ECDSA signing algorithm using threshold protocols. In this case we define that at least \(t\) shares are required to rebuild the signature, for \(n\) parties. With this, we generate a private key that will be used to sign our data. This private key is then split into a number of shares (\(n\)) and then \(t\) or more parties can come together to generate a valid ECDSA signature.
Any t-of-n threshold ECDSA signing algorithm using GG20 with Kryptology |
Method
The focus of the paper [1] is to create an ECDSA signature using secret shares of a private key. In this way we can create an ECDSA signature using multiple Shamir shares, and where the private is never actually revealed, but split over two or more parties.
So, let’s use the Coinbase Kryptology library to implement a \(t\)-from-\(n\) theshold ECDSA scheme using GG20 (Gennaro and Goldfeder, 2020). Initially we will use the secp256k1 curve and then generate a new private key (ikm):
k256 := btcec.S256()ikm, _ := dealer.NewSecret(k256)
This private key will not be stored on the parties which receive the shares, and can be deleted afer the shares have been distributed. We can then generate the associated public key (pk) and split the key into a number of shares (sharesMap):
pk, sharesMap, _ := dealer.NewDealerShares(k256, tshare, nshare, ikm) fmt.Printf("Message: %s\n", msg)fmt.Printf("Sharing scheme: Any %d from %d\n", tshare, nshare) fmt.Printf("Random secret: (%x)\n\n", ikm)fmt.Printf("Public key: (%s %s)\n\n", pk.X, pk.Y)
This public key will be used to check that the signature that the parties create. We also create public shares which can be used to verify the shares created. We then create Paillier keys which will be used to distribute the key signing:
for len(sharesMap) > int(tshare) { delete(sharesMap, uint32(len(sharesMap))) } pubSharesMap, _ := dealer.PreparePublicShares(sharesMap) keysMap := make(map[uint32]*paillier.SecretKey, tshare) pubKeys := make(map[uint32]*paillier.PublicKey, tshare) keyPrimesArray := genPrimesArray(int(tshare)) for i := range sharesMap { keysMap[i], _ = paillier.NewSecretKey(keyPrimesArray[i-1].p, keyPrimesArray[i-1].q) pubKeys[i] = &keysMap[i].PublicKey fmt.Printf("Share: %x\n", sharesMap[i].Bytes()) } proofParams := &dealer.TrustedDealerKeyGenType{ ProofParams: dealerParams, }
The dealer of the shares is now setup. What we need now is two parties to receive the shares, and for them to sign for a message (msg). We can create a hash of the message with:
m := []byte(msg)msgHash := sha256.Sum256(m)
Next we will create two participants (p1 and p2), and where p1 gets the first set of shares (sharesMap1), and the ID for these, and p2 gets the second set of shares (sharesMap2), and the required ID for these:
p1 := Participant{*setup.sharesMap[1], setup.privkeys[1]} p2 := Participant{*setup.sharesMap[2], setup.privkeys[2]}
And then set them up for split the share. These will be run of either of the parties:
s1, _ := p1.PrepareToSign(setup.pk,k256Verifier,setup.curve,setup.proofParams,setup.pubSharesMap,setup.pubkeys) s2, _ := p2.PrepareToSign(setup.pk,k256Verifier,setup.curve,setup.proofParams,setup.pubSharesMap, setup.pubkeys)
We then go into a number of rounds, and where s1 is run on one party, and s2 on another party:
// Run signing rounds // Sign Round 1 var err error signerOut := make(map[uint32]*Round1Bcast, tshare) for i, s := range signersMap { signerOut[i], _, err = s.SignRound1() if err != nil { return } } // Sign Round 2 p2p := make(map[uint32]map[uint32]*P2PSend) for i, s := range signersMap { in := make(map[uint32]*Round1Bcast, tshare-1) for j := range signersMap { if i == j { continue } in[j] = signerOut[j] } p2p[i], err = s.SignRound2(in, nil) // TODO: fix me later if err != nil { return } } // Sign Round 3 r3Bcast := make(map[uint32]*Round3Bcast, tshare) for i, s := range signersMap { in := make(map[uint32]*P2PSend, tshare-1) for j := range signersMap { if i == j { continue } in[j] = p2p[j][i] } r3Bcast[i], err = s.SignRound3(in) if err != nil { return } } // Sign Round 4 r4Bcast := make(map[uint32]*Round4Bcast, tshare) for i, s := range signersMap { in := make(map[uint32]*Round3Bcast, tshare-1) for j := range signersMap { if i == j { continue } in[j] = r3Bcast[j] } r4Bcast[i], err = s.SignRound4(in) if err != nil { return } } // Sign Round 5 r5Bcast := make(map[uint32]*Round5Bcast, tshare) r5P2p := make(map[uint32]map[uint32]*Round5P2PSend, tshare) for i, s := range signersMap { in := make(map[uint32]*Round4Bcast, tshare-1) for j := range signersMap { if i == j { continue } in[j] = r4Bcast[j] } r5Bcast[i], r5P2p[i], err = s.SignRound5(in) if err != nil { return } } // Sign Round 6 r6Bcast := make(map[uint32]*Round6FullBcast, tshare) for i, s := range signersMap { in := make(map[uint32]*Round5Bcast, tshare-1) for j := range signersMap { if i == j { continue } in[j] = r5Bcast[j] } r6Bcast[i], err = s.SignRound6Full(msgHash[:], in, r5P2p[i]) if err != nil { return } }
Now each party can generate the shared signature:
var sig *curves.EcdsaSignature for i, s := range signersMap { in := make(map[uint32]*Round6FullBcast, tshare-1) for j := range signersMap { if i == j { continue } in[j] = r6Bcast[j] } sig, _ = s.SignOutput(in) }
We can then check the signature that has been generated against the public key:
fmt.Printf("\nOverall signature: (%d %d)\n", sig.R, sig.S) publicKey := ecdsa.PublicKey{ Curve: ecc.P256k1(), //secp256k1 X: pk.X, Y: pk.Y, } rtn := ecdsa.Verify(&publicKey, msgHash[:], sig.R, sig.S) fmt.Printf("\nSignature Verified: %v", rtn)
A sample run is:
Message: hello Sharing scheme: Any 2 from 2 Random secret: (4ba8a796f32ec45a1197de6089fa236e50801928ad24fecac8c1ab09e531a166)Public key: (26312696491752052329024843181188922148239837748725137580407874797348180244367 15363854046934109047334192976294337901992160667810868208924200646181218876027)Node 1 signature: (58831626654799325138549587498198878137267315963404497589755928522155537172377 52424895795438944536339814184633346175739904425137488476336337801850504274550) Node 2 signature: (58831626654799325138549587498198878137267315963404497589755928522155537172377 52424895795438944536339814184633346175739904425137488476336337801850504274550)Signature Verified: true
Coding
In this case we will define \(t\) for the threshold and \(n\) for the number of shares:
package main import ( "crypto/ecdsa" "crypto/sha256" "fmt" "math/big" "github.com/dustinxie/ecc" "os" "strconv" "github.com/btcsuite/btcd/btcec" "github.com/coinbase/kryptology/pkg/core/curves" "github.com/coinbase/kryptology/pkg/paillier" "github.com/coinbase/kryptology/pkg/tecdsa/gg20/dealer" ) var ( testPrimes = []*big.Int{ B10("186141419611617071752010179586510154515933389116254425631491755419216243670159714804545944298892950871169229878325987039840135057969555324774918895952900547869933648175107076399993833724447909579697857041081987997463765989497319509683575289675966710007879762972723174353568113668226442698275449371212397561567"), B10("94210786053667323206442523040419729883258172350738703980637961803118626748668924192069593010365236618255120977661397310932923345291377692570649198560048403943687994859423283474169530971418656709749020402756179383990602363122039939937953514870699284906666247063852187255623958659551404494107714695311474384687"), B10("62028909880050184794454820320289487394141550306616974968340908736543032782344593292214952852576535830823991093496498970213686040280098908204236051130358424961175634703281821899530101130244725435470475135483879784963475148975313832483400747421265545413510460046067002322131902159892876739088034507063542087523"), B10("321804071508183671133831207712462079740282619152225438240259877528712344129467977098976100894625335474509551113902455258582802291330071887726188174124352664849954838358973904505681968878957681630941310372231688127901147200937955329324769631743029415035218057960201863908173045670622969475867077447909836936523"), B10("52495647838749571441531580865340679598533348873590977282663145916368795913408897399822291638579504238082829052094508345857857144973446573810004060341650816108578548997792700057865473467391946766537119012441105169305106247003867011741811274367120479722991749924616247396514197345075177297436299446651331187067"), B10("118753381771703394804894143450628876988609300829627946826004421079000316402854210786451078221445575185505001470635997217855372731401976507648597119694813440063429052266569380936671291883364036649087788968029662592370202444662489071262833666489940296758935970249316300642591963940296755031586580445184253416139"), } dealerParams = &dealer.ProofParams{ N: B10("135817986946410153263607521492868157288929876347703239389804036854326452848342067707805833332721355089496671444901101084429868705550525577068432132709786157994652561102559125256427177197007418406633665154772412807319781659630513167839812152507439439445572264448924538846645935065905728327076331348468251587961"), H1: B10("130372793360787914947629694846841279927281520987029701609177523587189885120190605946568222485341643012763305061268138793179515860485547361500345083617939280336315872961605437911597699438598556875524679018909165548046362772751058504008161659270331468227764192850055032058007664070200355866555886402826731196521"), H2: B10("44244046835929503435200723089247234648450309906417041731862368762294548874401406999952605461193318451278897748111402857920811242015075045913904246368542432908791195758912278843108225743582704689703680577207804641185952235173475863508072754204128218500376538767731592009803034641269409627751217232043111126391"), } k256Verifier = func(pubKey *curves.EcPoint, hash []byte, sig *curves.EcdsaSignature) bool { btcPk := &btcec.PublicKey{ Curve: btcec.S256(), X: pubKey.X, Y: pubKey.Y, } btcSig := btcec.Signature{ R: sig.R, S: sig.S, } return btcSig.Verify(hash, btcPk) } ) func getParams(msg *string, t, n *uint32) { argCount := len(os.Args[1:]) if argCount > 0 { *msg = os.Args[1] } if argCount > 1 { val, _ := strconv.Atoi(os.Args[2]) *t = uint32(val) } if argCount > 2 { val, _ := strconv.Atoi(os.Args[3]) *n = uint32(val) } } func genPrimesArray(count int) []struct{ p, q *big.Int } { primesArray := make([]struct{ p, q *big.Int }, 0, count) for len(primesArray) < count { for i := 0; i < len(testPrimes) && len(primesArray) < count; i++ { for j := 0; j < len(testPrimes) && len(primesArray) < count; j++ { if i == j { continue } keyPrime := struct { p, q *big.Int }{ testPrimes[i], testPrimes[j], } primesArray = append(primesArray, keyPrime) } } } return primesArray } func B10(s string) *big.Int { x, ok := new(big.Int).SetString(s, 10) if !ok { panic("Couldn't derive big.Int from string") } return x } func main() { tshare := uint32(2) nshare := uint32(3) msg := "Hello" m := []byte(msg) msgHash := sha256.Sum256(m) getParams(&msg, &tshare, &nshare) k256 := btcec.S256() ikm, _ := dealer.NewSecret(k256) pk, sharesMap, _ := dealer.NewDealerShares(k256, tshare, nshare, ikm) fmt.Printf("Message: %s\n", msg) fmt.Printf("Sharing scheme: Any %d from %d\n", tshare, nshare) fmt.Printf("Random secret: (%x)\n\n", ikm) fmt.Printf("Public key: (%s %s)\n\n", pk.X, pk.Y) for len(sharesMap) > int(tshare) { delete(sharesMap, uint32(len(sharesMap))) } pubSharesMap, _ := dealer.PreparePublicShares(sharesMap) keysMap := make(map[uint32]*paillier.SecretKey, tshare) pubKeys := make(map[uint32]*paillier.PublicKey, tshare) keyPrimesArray := genPrimesArray(int(tshare)) for i := range sharesMap { keysMap[i], _ = paillier.NewSecretKey(keyPrimesArray[i-1].p, keyPrimesArray[i-1].q) pubKeys[i] = &keysMap[i].PublicKey fmt.Printf("Share: %x\n", sharesMap[i].Bytes()) } proofParams := &dealer.TrustedDealerKeyGenType{ ProofParams: dealerParams, } signersMap := make(map[uint32]*Signer, tshare) for i, k := range keysMap { p := Participant{*sharesMap[i], k} signersMap[i], _ = p.PrepareToSign(pk, k256Verifier, k256, proofParams, pubSharesMap, pubKeys) } // Run signing rounds // Sign Round 1 var err error signerOut := make(map[uint32]*Round1Bcast, tshare) for i, s := range signersMap { signerOut[i], _, err = s.SignRound1() if err != nil { return } } // Sign Round 2 p2p := make(map[uint32]map[uint32]*P2PSend) for i, s := range signersMap { in := make(map[uint32]*Round1Bcast, tshare-1) for j := range signersMap { if i == j { continue } in[j] = signerOut[j] } p2p[i], err = s.SignRound2(in, nil) // TODO: fix me later if err != nil { return } } // Sign Round 3 r3Bcast := make(map[uint32]*Round3Bcast, tshare) for i, s := range signersMap { in := make(map[uint32]*P2PSend, tshare-1) for j := range signersMap { if i == j { continue } in[j] = p2p[j][i] } r3Bcast[i], err = s.SignRound3(in) if err != nil { return } } // Sign Round 4 r4Bcast := make(map[uint32]*Round4Bcast, tshare) for i, s := range signersMap { in := make(map[uint32]*Round3Bcast, tshare-1) for j := range signersMap { if i == j { continue } in[j] = r3Bcast[j] } r4Bcast[i], err = s.SignRound4(in) if err != nil { return } } // Sign Round 5 r5Bcast := make(map[uint32]*Round5Bcast, tshare) r5P2p := make(map[uint32]map[uint32]*Round5P2PSend, tshare) for i, s := range signersMap { in := make(map[uint32]*Round4Bcast, tshare-1) for j := range signersMap { if i == j { continue } in[j] = r4Bcast[j] } r5Bcast[i], r5P2p[i], err = s.SignRound5(in) if err != nil { return } } // Sign Round 6 r6Bcast := make(map[uint32]*Round6FullBcast, tshare) for i, s := range signersMap { in := make(map[uint32]*Round5Bcast, tshare-1) for j := range signersMap { if i == j { continue } in[j] = r5Bcast[j] } r6Bcast[i], err = s.SignRound6Full(msgHash[:], in, r5P2p[i]) if err != nil { return } } // Signature output var sig *curves.EcdsaSignature for i, s := range signersMap { in := make(map[uint32]*Round6FullBcast, tshare-1) for j := range signersMap { if i == j { continue } in[j] = r6Bcast[j] } sig, _ = s.SignOutput(in) } fmt.Printf("\nOverall signature: (%d %d)\n", sig.R, sig.S) publicKey := ecdsa.PublicKey{ Curve: ecc.P256k1(), //secp256k1 X: pk.X, Y: pk.Y, } rtn := ecdsa.Verify(&publicKey, msgHash[:], sig.R, sig.S) fmt.Printf("\nSignature Verified: %v", rtn) }
A sample run:
Message: Hello Sharing scheme: Any 3 from 3 Random secret: (c271efce18143d061fc038520bf237d54bc1bae30102a6865415469395c828e9) Public key: (57755611822377136447302262937396184048650892670209379601281857181998065978443 44413617945939969186822341967546876716017422443472796955428443139294461366744) Share: 00000001d626949296c762aed6b05487089a1e8427eab17517b1cbf50452c20d721ee6d0 Share: 00000002101c511c26b51045ee6bd4d9b765dca488a724408d2b612bc40e59804b3a40f0 Share: 000000037053256ac7dd45cb66f2b94a18557233e354cd12c000a6a212ecca05c186b9cb Overall signature: (41380358919718061219799007246292506717162956461936762477573221474876405792049 38097776260715345652427955489175480176251297451389595674385725752408498422410) Signature Verified: true
References
[1] Gennaro, R., & Goldfeder, S. (2020). One Round Threshold ECDSA with Identifiable Abort. IACR Cryptol. ePrint Arch., 2020, 540 [here].