Error: "failed to calculate Alice_end or Alice_end_wc" in Round 3

[tnunamak]

I am working on a small proof of concept (code) and would appreciate any suggestions for further debugging. My goal is to use DKG to create a threshold signature whose shares can be refreshed. This ran successfully a few times (successful signature verification). Most of the time, signature verification fails. During round 3 of the signing process, when a party receives a message and calls UpdateFromBytes, this line from ecdsa/signing/round_3.go is throws an error:

if len(culprits) > 0 {
    return round.WrapError(errors.New("failed to calculate Alice_end or Alice_end_wc"), culprits...)
}

It seems that ProofBobWC.Verify() is returning false here:

// 4. runs only in the "with check" mode from Fig. 10
if X != nil {
    s1ModQ := new(big.Int).Mod(pf.S1, ec.Params().N)
    gS1 := crypto.ScalarBaseMult(ec, s1ModQ)
    xEU, err := X.ScalarMult(e).Add(pf.U)
    if err != nil || !gS1.Equals(xEU) {
       return false
    }
}

Logs and code:

2024/07/16 12:13:40 Starting Key Generation
2024/07/16 12:13:56 Received key share from party 1
...
2024/07/16 12:13:56 All key shares received
2024/07/16 12:13:56 Key generation completed successfully.
2024/07/16 12:13:56 All ECDSA public key components are verified and intact.
2024/07/16 12:13:56 Message to sign: 275416438502019691922108054646891190369
2024/07/16 12:13:56 Starting Signing Process
2024/07/16 12:13:56 Attempting to update party {0,party-1} with message from {2,party-3}
...
2024/07/16 12:13:56 Attempting to update party {0,party-1} with message from {2,party-3}
2024/07/16 12:13:56 Successfully updated signing party {0,party-1}
2024/07/16 12:13:56 Successfully updated signing party {1,party-2}
2024/07/16 12:13:56 Successfully updated signing party {1,party-2}
2024/07/16 12:13:56 Attempting to update party {0,party-1} with message from {1,party-2}
2024/07/16 12:13:56 Attempting to update party {2,party-3} with message from {1,party-2
2024/07/16 12:13:56 Failed to update signing party: task signing, party {0,party-1}, round 3, culprits [{1,party-2} {2,party-3}]: failed to calculate Alice_end or Alice_end_wc

// Note: The current implementation is encountering errors in the signing phase.
// This could be due to issues with how the key shares are being used or how the
// signing parties are communicating. Further investigation and debugging are needed.

/*
TSS (Threshold Signature Scheme) Tutorial

This tutorial demonstrates how to use the tss-lib to implement a threshold signature scheme.
The process involves distributed key generation and collective signing, which are fundamental
to creating a system where multiple parties can jointly manage encrypted data without any
single party having complete control.

Flow of the program:
1. Generate party IDs for participants
2. Perform distributed key generation (DKG)
3. Use the generated keys to create a threshold signature

This implementation is a simplified version of a system where:
- A group (e.g., a DAO) elects leaders
- Leaders generate a shared public key and individual private key shares
- Data can be encrypted with the public key
- A threshold of leaders can collaborate to decrypt the data
- Leaders can be replaced and shares can be refreshed for security

Note: This example doesn't include the encryption/decryption or share refresh processes,
      focusing instead on the key generation and signing aspects.

Important: This is a proof of concept and should not be used in production without
           further security considerations and error handling.
*/

package main

import (
	"crypto/ecdsa"
	"crypto/rand"
	"fmt"
	"log"
	"math/big"

	"github.com/bnb-chain/tss-lib/v2/common"
	"github.com/bnb-chain/tss-lib/v2/ecdsa/keygen"
	"github.com/bnb-chain/tss-lib/v2/ecdsa/signing"
	"github.com/bnb-chain/tss-lib/v2/tss"
)

// Constants for the number of participants and the threshold
// In a real-world scenario, these might be configurable or determined by the DAO
const (
	threshold    = 2 // Number of parties required to sign
	participants = 3 // Total number of parties
)

func main() {
	log.Println("Starting TSS demonstration")

	// Key Generation
	keys, err := runKeygen()
	if err != nil {
		log.Fatalf("Keygen failed: %v\n", err)
	}
	log.Println("Key generation completed successfully.")

	// Signing
	// Generate a random message to sign
	message := common.GetRandomPrimeInt(rand.Reader, 128)
	log.Printf("Message to sign: %s\n", message.String())

	signature, err := runSigning(message, keys)
	if err != nil {
		log.Fatalf("Signing failed: %v\n", err)
	}
	log.Printf("Signature generated: R=%x, S=%x\n", signature.R, signature.S)

	// Verify signature
	publicKey := &ecdsa.PublicKey{
		Curve: tss.S256(), // We're using the secp256k1 curve
		X:     keys[0].ECDSAPub.X(),
		Y:     keys[0].ECDSAPub.Y(),
	}
	R := new(big.Int).SetBytes(signature.R)
	S := new(big.Int).SetBytes(signature.S)
	verified := ecdsa.Verify(publicKey, message.Bytes(), R, S)
	log.Printf("Signature verified: %v\n", verified)
}

// generatePartyIDs creates a sorted list of party IDs for the TSS protocol
// Each party needs a unique identifier for the protocol to work correctly
func generatePartyIDs(count int) tss.SortedPartyIDs {
	var partyIDs tss.UnSortedPartyIDs
	for i := 0; i < count; i++ {
		id := fmt.Sprintf("%d", i+1)
		moniker := fmt.Sprintf("party-%d", i+1)
		key := big.NewInt(int64(i + 1))
		// NewPartyID creates a new party ID with the given id, moniker, and key
		partyIDs = append(partyIDs, tss.NewPartyID(id, moniker, key))
	}
	// SortPartyIDs sorts the party IDs, which is required for the protocol
	return tss.SortPartyIDs(partyIDs)
}

// runKeygen performs the distributed key generation process
func runKeygen() ([]*keygen.LocalPartySaveData, error) {
	log.Println("Starting Key Generation")
	partyIDs := generatePartyIDs(participants)

	// Create a peer context, which holds information about all participants
	peerCtx := tss.NewPeerContext(partyIDs)
	// Create parameters for the TSS protocol
	params := tss.NewParameters(tss.S256(), peerCtx, partyIDs[0], len(partyIDs), threshold)

	// Channels for communication between parties
	outCh := make(chan tss.Message, len(partyIDs))
	endCh := make(chan *keygen.LocalPartySaveData, len(partyIDs))

	parties := make([]*keygen.LocalParty, len(partyIDs))
	for i := 0; i < len(partyIDs); i++ {
		// Create new parameters for each party, ensuring they have the correct PartyID
		params := tss.NewParameters(params.EC(), params.Parties(), partyIDs[i], params.PartyCount(), params.Threshold())
		parties[i] = keygen.NewLocalParty(params, outCh, endCh).(*keygen.LocalParty)
	}

	// Start each party in a separate goroutine
	for _, p := range parties {
		go func(p *keygen.LocalParty) {
			if err := p.Start(); err != nil {
				log.Printf("Failed to start party: %v\n", err)
			}
		}(p)
	}

	keys := make([]*keygen.LocalPartySaveData, len(partyIDs))
	keyCount := 0
	// Main event loop for key generation
	for {
		select {
		case msg := <-outCh:
			// Handle outgoing messages
			dest := msg.GetTo()
			if dest == nil {
				// Broadcast message
				for _, p := range parties {
					if p.PartyID().Index != msg.GetFrom().Index {
						go handleMessage(p, msg)
					}
				}
			} else {
				// Point-to-point message
				go handleMessage(parties[dest[0].Index], msg)
			}
		case key := <-endCh:
			// Collect key shares from each party
			keys[keyCount] = key
			keyCount++
			log.Printf("Received key share from party %d\n", keyCount)
			if keyCount == len(partyIDs) {
				log.Println("All key shares received")
				return keys, nil
			}
		}
	}
}

// runSigning performs the distributed signing process
func runSigning(message *big.Int, keys []*keygen.LocalPartySaveData) (*common.SignatureData, error) {
	log.Println("Starting Signing Process")
	// For signing, we only need threshold + 1 parties
	signPartyIDs := generatePartyIDs(threshold + 1)

	peerCtx := tss.NewPeerContext(signPartyIDs)
	params := tss.NewParameters(tss.S256(), peerCtx, signPartyIDs[0], len(signPartyIDs), threshold)

	outCh := make(chan tss.Message, len(signPartyIDs))
	endCh := make(chan *common.SignatureData, len(signPartyIDs))

	parties := make([]*signing.LocalParty, len(signPartyIDs))
	for i := 0; i < len(signPartyIDs); i++ {
		params := tss.NewParameters(params.EC(), params.Parties(), signPartyIDs[i], params.PartyCount(), params.Threshold())
		parties[i] = signing.NewLocalParty(message, params, *keys[i], outCh, endCh).(*signing.LocalParty)
	}

	// Start each signing party in a separate goroutine
	for _, p := range parties {
		go func(p *signing.LocalParty) {
			if err := p.Start(); err != nil {
				log.Printf("Failed to start signing party: %v\n", err)
			}
		}(p)
	}

	// Main event loop for signing
	for {
		select {
		case msg := <-outCh:
			// Handle outgoing messages
			dest := msg.GetTo()
			if dest == nil {
				// Broadcast message
				for _, p := range parties {
					if p.PartyID().Index != msg.GetFrom().Index {
						go handleSigningMessage(p, msg)
					}
				}
			} else {
				// Point-to-point message
				go handleSigningMessage(parties[dest[0].Index], msg)
			}
		case signature := <-endCh:
			// Signature is ready
			log.Println("Signature generated")
			return signature, nil
		}
	}
}

// handleMessage processes incoming messages for key generation
func handleMessage(p *keygen.LocalParty, msg tss.Message) {
	bytes, _, err := msg.WireBytes()
	if err != nil {
		log.Printf("Error getting wire bytes: %v\n", err)
		return
	}
	if _, err := p.UpdateFromBytes(bytes, msg.GetFrom(), msg.IsBroadcast()); err != nil {
		log.Printf("Failed to update party: %v\n", err)
	}
}

// handleSigningMessage processes incoming messages for signing
func handleSigningMessage(p *signing.LocalParty, msg tss.Message) {
	bytes, _, err := msg.WireBytes()
	if err != nil {
		log.Printf("Error getting wire bytes: %v\n", err)
		return
	}
	if _, err := p.UpdateFromBytes(bytes, msg.GetFrom(), msg.IsBroadcast()); err != nil {
		log.Printf("Failed to update signing party: %v\n", err)
	}
}

[ozanyurt]

You know that your code works with 1-2 values, right? I am encountering a similar error in my own code, but mine says “failed to calculate Bob_mid or Bob_mid_wc”. I can’t figure out why it doesn’t work when I change the number of participants and the threshold. It might be related to the transmission of messages.

[ozanyurt]

You know that your code works with 1-2 values, right? I am encountering a similar error in my own code, but mine says “failed to calculate Bob_mid or Bob_mid_wc”. I can’t figure out why it doesn’t work when I change the number of participants and the threshold. It might be related to the transmission of messages.

Yes it is giving error randomly.