An Any t-from-n Threshold ECDSA Scheme using GG20, Krytology and Golang
An Any t-from-n Threshold ECDSA Scheme using GG20, Krytology and Golang
Satoshi Nakamoto select secp256k1 and used the ECDSA signature. This was then adopted by Ethereum. And so, we are building a world of trust around ECDSA signatures. With this we generate a key pair: a private key (sk) and a public key (pk). When we sign for data, we take a hash of it, and then use our private key and a random nonce value. This creates a signature defined by (r, s). We can then check with our public key and the data. But how do we protect the private key? Well we could split it into shares, and, when required, rebuild using a t-from-n approach, and where t is the threshold number, and n is the number of participants. So can we now split the signature up, so that each of the parties create part of the signature related to their shared key, and then for us to rebuild the complete signature, without ever needing to rebuild the private key. Well, yes, and one of the best around is the DD20 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,
}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 [here]:
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
And so here is the running code:
https://asecuritysite.com/kryptology/sss_gg03
Asecuritysite is provided free and without adverts. If you want to support its development and get access to this blog, subscribe here: