The GG20 (Gennaro, R., & Goldfeder, S. (2020) [1]) method implements an ECDSA signing algorithm using threshold protocols. In this case, Bob and Alice will communicate using a DKG method, and then Bob will be able to create a valid signature. We can use the Kryptology library developed by Coinbase to implement 2-of-2 threshold ECDSA signing algorithm of the GG20 method. Once Bob and Alice have communicated, Bob will hold a signature for the message. We will then check this signature for its validity. We will thus split a private key up into two secret shares and then will be able to sign with the shares of the key.
2-of-2 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 2-from-2 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:
pubSharesMap, _ := dealer.PreparePublicShares(sharesMap)
We then create Paillier keys which will be used to distribute the key signing:
keyPrimesArray := genPrimesArray(2) paillier1, _ := paillier.NewSecretKey(keyPrimesArray[0].p, keyPrimesArray[0].q) paillier2, _ := paillier.NewSecretKey(keyPrimesArray[1].p, keyPrimesArray[1].q) dealerSetup := &signingSetup{ curve: k256, pk: pk, sharesMap: sharesMap, pubSharesMap: pubSharesMap, pubkeys: map[uint32]*paillier.PublicKey{ 1: &paillier1.PublicKey, 2: &paillier2.PublicKey, }, privkeys: map[uint32]*paillier.SecretKey{ 1: paillier1, 2: paillier2, }, 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:
r1_s1_bcast, r1_s1_p2p, _ := s1.SignRound1() r1_s2_bcast, r1_s2_p2p, _ := s2.SignRound1() r2_s1_p2p, _ := s1.SignRound2(map[uint32]*Round1Bcast{2: r1_s2_bcast},map[uint32]*Round1P2PSend{2: r1_s2_p2p[1]},) r2_s2_p2p, _ := s2.SignRound2(map[uint32]*Round1Bcast{1: r1_s1_bcast},map[uint32]*Round1P2PSend{1: r1_s1_p2p[2]},) r3_s1_bcast, _ := s1.SignRound3(map[uint32]*P2PSend{2: r2_s2_p2p[1]},) r3_s2_bcast, _ := s2.SignRound3(map[uint32]*P2PSend{1: r2_s1_p2p[2]},) r4_s1_bcast, _ := s1.SignRound4(map[uint32]*Round3Bcast{2: r3_s2_bcast}) r4_s2_bcast, _ := s2.SignRound4(map[uint32]*Round3Bcast{1: r3_s1_bcast}) r5_s1_bcast, r5_s1_p2p, _ := s1.SignRound5(map[uint32]*Round4Bcast{2: r4_s2_bcast},)r5_s2_bcast, r5_s2_p2p, _ := s2.SignRound5(map[uint32]*Round4Bcast{1: r4_s1_bcast},) r6_s1_bcast, _ := s1.SignRound6Full(msgHash, map[uint32]*Round5Bcast{2: r5_s2_bcast},map[uint32]*Round5P2PSend{2: r5_s2_p2p[1]},)r6_s2_bcast, _ := s2.SignRound6Full(msgHash, map[uint32]*Round5Bcast{1: r5_s1_bcast}, map[uint32]*Round5P2PSend{1: r5_s1_p2p[2]},)
Now each party can generate the shared signature:
s1_sig, _ := s1.SignOutput( map[uint32]*Round6FullBcast{2: r6_s2_bcast}, ) s2_sig, _ := s2.SignOutput( map[uint32]*Round6FullBcast{1: r6_s1_bcast}, )
We can then check the signature that has been generated against the public key:
publicKey := ecdsa.PublicKey{ Curve: ecc.P256k1(), //secp256k1 X: setup.pk.X, Y: setup.pk.Y, } fmt.Printf("Message: %s\n", msg) fmt.Printf("Node 1 signature: (%d %d)\n", s1_sig.R, s1_sig.S) fmt.Printf("Node 2 signature: (%d %d)\n", s2_sig.R, s2_sig.S) rtn := ecdsa.Verify(&publicKey, msgHash, s1_sig.R, s1_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
Theory
Some sample code is:
package main import ( "crypto/ecdsa" "crypto/elliptic" "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" // "github.com/coinbase/kryptology/pkg/tecdsa/gg20/participant" ) 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 } type signingSetup struct { curve elliptic.Curve pk *curves.EcPoint sharesMap map[uint32]*dealer.Share pubSharesMap map[uint32]*dealer.PublicShare pubkeys map[uint32]*paillier.PublicKey privkeys map[uint32]*paillier.SecretKey proofParams *dealer.TrustedDealerKeyGenType } func sign2p(msg string, setup *signingSetup) { // Hash of message for signature m := []byte(msg) msgHash := sha256.Sum256(m) // Create signers p1 := Participant{*setup.sharesMap[1], setup.privkeys[1]} s1, _ := p1.PrepareToSign( setup.pk, k256Verifier, setup.curve, setup.proofParams, setup.pubSharesMap, setup.pubkeys) p2 := Participant{*setup.sharesMap[2], setup.privkeys[2]} s2, _ := p2.PrepareToSign( setup.pk, k256Verifier, setup.curve, setup.proofParams, setup.pubSharesMap, setup.pubkeys) // // Sign Round 1 // r1_s1_bcast, r1_s1_p2p, _ := s1.SignRound1() r1_s2_bcast, r1_s2_p2p, _ := s2.SignRound1() // // Sign Round 2 // r2_s1_p2p, _ := s1.SignRound2( map[uint32]*Round1Bcast{2: r1_s2_bcast}, map[uint32]*Round1P2PSend{2: r1_s2_p2p[1]}, ) r2_s2_p2p, _ := s2.SignRound2( map[uint32]*Round1Bcast{1: r1_s1_bcast}, map[uint32]*Round1P2PSend{1: r1_s1_p2p[2]}, ) // // Sign Round 3 // r3_s1_bcast, _ := s1.SignRound3( map[uint32]*P2PSend{2: r2_s2_p2p[1]}, ) r3_s2_bcast, _ := s2.SignRound3( map[uint32]*P2PSend{1: r2_s1_p2p[2]}, ) // // Sign Round 4 // r4_s1_bcast, _ := s1.SignRound4( map[uint32]*Round3Bcast{2: r3_s2_bcast}) r4_s2_bcast, _ := s2.SignRound4( map[uint32]*Round3Bcast{1: r3_s1_bcast}) // // Sign Round 5 // r5_s1_bcast, r5_s1_p2p, _ := s1.SignRound5( map[uint32]*Round4Bcast{2: r4_s2_bcast}, ) r5_s2_bcast, r5_s2_p2p, _ := s2.SignRound5( map[uint32]*Round4Bcast{1: r4_s1_bcast}, ) // // Sign Round 6 // r6_s1_bcast, _ := s1.SignRound6Full(msgHash[:], map[uint32]*Round5Bcast{2: r5_s2_bcast}, map[uint32]*Round5P2PSend{2: r5_s2_p2p[1]}, ) r6_s2_bcast, _ := s2.SignRound6Full(msgHash[:], map[uint32]*Round5Bcast{1: r5_s1_bcast}, map[uint32]*Round5P2PSend{1: r5_s1_p2p[2]}, ) // // Compute signature // s1_sig, _ := s1.SignOutput( map[uint32]*Round6FullBcast{2: r6_s2_bcast}, ) s2_sig, _ := s2.SignOutput( map[uint32]*Round6FullBcast{1: r6_s1_bcast}, ) publicKey := ecdsa.PublicKey{ Curve: ecc.P256k1(), //secp256k1 X: setup.pk.X, Y: setup.pk.Y, } fmt.Printf("\nNode 1 signature: (%d %d)\n", s1_sig.R, s1_sig.S) fmt.Printf("Node 2 signature: (%d %d)\n", s2_sig.R, s2_sig.S) rtn := ecdsa.Verify(&publicKey, msgHash[:], s1_sig.R, s1_sig.S) fmt.Printf("\nSignature Verified: %v", rtn) } func main() { tshare := uint32(2) nshare := uint32(2) msg := "Hello" 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 i := range sharesMap { fmt.Printf("Share: %x\n", sharesMap[i].Bytes()) } pubSharesMap, _ := dealer.PreparePublicShares(sharesMap) keyPrimesArray := genPrimesArray(2) paillier1, _ := paillier.NewSecretKey(keyPrimesArray[0].p, keyPrimesArray[0].q) paillier2, _ := paillier.NewSecretKey(keyPrimesArray[1].p, keyPrimesArray[1].q) dealerSetup := &signingSetup{ curve: k256, pk: pk, sharesMap: sharesMap, pubSharesMap: pubSharesMap, pubkeys: map[uint32]*paillier.PublicKey{ 1: &paillier1.PublicKey, 2: &paillier2.PublicKey, }, privkeys: map[uint32]*paillier.SecretKey{ 1: paillier1, 2: paillier2, }, proofParams: &dealer.TrustedDealerKeyGenType{ ProofParams: dealerParams, }, } sign2p(msg, dealerSetup) }
The source code for these rounds is here:
A sample run is:
Message: hello Sharing scheme: Any 2 from 2 Random secret: (9f191dc8656d2b9103e685738eafa901ba95099a2fcb449840c467ebdd421d31) Public key: (19020667506323879884523239684361495106492527784803536443833251197800096205913 13125823545704930172415770586468991344953848676289996210521922186220526983398) Share: 00000001f0daf9cf24e34745fc2764e4dd575fcb05181764ed0acc8a82e34e0b1eddedb4 Share: 00000002429cd5d5e45962faf46844562bff169594ec4848fb01b441052fd59d90437cf6 Node 1 signature: (53101636157497881556656858841576394324433929135244801801330587084743419330424 16506227295858998413169021633963208931303509353025805696990905473013335144442) Node 2 signature: (53101636157497881556656858841576394324433929135244801801330587084743419330424 16506227295858998413169021633963208931303509353025805696990905473013335144442) Signature Verified: true
References
[1] Gennaro, R., & Goldfeder, S. (2020). One Round Threshold ECDSA with Identifiable Abort. IACR Cryptol. ePrint Arch., 2020, 540 [here].