bnb-chain / tss-lib

Threshold Signature Scheme, for ECDSA and EDDSA
MIT License
778 stars 265 forks source link

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

Open tnunamak opened 1 month ago

tnunamak commented 1 month ago

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 commented 1 month ago

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 commented 1 month ago

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.

Alkhtri77 commented 2 weeks ago

// 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:

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) } }

Alkhtri77 commented 2 weeks ago

Hello help me plaes my friend

Alkhtri77 commented 2 weeks ago

My Address wallet where