BLS Signatures

Boneh-Lynn-Shacham signature scheme with aggregation and threshold support

BLS Signatures

BLS (Boneh-Lynn-Shacham) signatures are a critical component of Lux's consensus mechanism, enabling efficient signature aggregation for validator voting and threshold cryptography. This implementation uses BLS12-381 curve for 128-bit security.

Overview

BLS signatures offer unique properties that make them ideal for blockchain consensus:

  • Signature Aggregation: Combine multiple signatures into a single constant-size signature
  • Threshold Signatures: Enable k-of-n signature schemes
  • Non-interactive Aggregation: No additional communication between signers
  • Deterministic Verification: Signature verification is deterministic and efficient

Technical Details

Cryptographic Parameters

ParameterValueDescription
CurveBLS12-381Pairing-friendly elliptic curve
Security Level128-bitEquivalent to 3072-bit RSA
Public Key Size48 bytesCompressed G1 point
Private Key Size32 bytesScalar field element
Signature Size96 bytesCompressed G2 point
Aggregated Signature Size96 bytesConstant size regardless of signers

Mathematical Foundation

BLS signatures are based on bilinear pairings over elliptic curves:

e: G1 × G2 → GT

Where:

  • G1, G2 are cyclic groups of prime order r
  • GT is the target group
  • e is the bilinear pairing function

Implementation

Key Generation

Generate a new BLS key pair for validators:

package main

import (
    "fmt"
    "log"
    "github.com/luxfi/crypto/bls"
)

func main() {
    // Generate new private key
    privateKey, err := bls.NewSecretKey()
    if err != nil {
        log.Fatal("Failed to generate private key:", err)
    }

    // Derive public key
    publicKey := bls.PublicKeyFromSecretKey(privateKey)

    // Serialize for storage
    privBytes := bls.SecretKeyToBytes(privateKey)
    pubBytes := bls.PublicKeyToCompressedBytes(publicKey)

    fmt.Printf("Private Key: %x\n", privBytes)
    fmt.Printf("Public Key: %x\n", pubBytes)
}

Signing Messages

Sign messages for consensus voting:

func signMessage(privateKey *bls.SecretKey, message []byte) (*bls.Signature, error) {
    // Sign the message
    signature := bls.Sign(privateKey, message)

    // Serialize signature for transmission
    sigBytes := bls.SignatureToBytes(signature)

    // Verify signature locally (optional)
    publicKey := bls.PublicKeyFromSecretKey(privateKey)
    if !bls.Verify(publicKey, message, signature) {
        return nil, errors.New("signature verification failed")
    }

    return signature, nil
}

Signature Verification

Verify individual signatures from validators:

func verifySignature(publicKey *bls.PublicKey, message []byte, signature *bls.Signature) bool {
    // Simple verification
    return bls.Verify(publicKey, message, signature)
}

// Batch verification for efficiency
func batchVerify(publicKeys []*bls.PublicKey, messages [][]byte, signatures []*bls.Signature) bool {
    if len(publicKeys) != len(messages) || len(messages) != len(signatures) {
        return false
    }

    for i := range publicKeys {
        if !bls.Verify(publicKeys[i], messages[i], signatures[i]) {
            return false
        }
    }
    return true
}

Signature Aggregation

The key feature of BLS signatures is efficient aggregation:

Basic Aggregation

Aggregate multiple signatures on the same message:

func aggregateSignatures(signatures []*bls.Signature) (*bls.AggregateSignature, error) {
    if len(signatures) == 0 {
        return nil, bls.ErrNoSignatures
    }

    // Aggregate all signatures
    aggregated, err := bls.AggregateSignatures(signatures)
    if err != nil {
        return nil, fmt.Errorf("aggregation failed: %w", err)
    }

    return aggregated, nil
}

// Verify aggregated signature
func verifyAggregated(publicKeys []*bls.PublicKey, message []byte, aggregatedSig *bls.AggregateSignature) bool {
    return bls.VerifyAggregateCommon(publicKeys, message, aggregatedSig)
}

Proof of Possession

Prevent rogue key attacks with proof of possession:

func generateProofOfPossession(privateKey *bls.SecretKey) *bls.Signature {
    publicKey := bls.PublicKeyFromSecretKey(privateKey)
    publicKeyBytes := bls.PublicKeyToCompressedBytes(publicKey)

    // Sign own public key as proof of possession
    pop := bls.Sign(privateKey, publicKeyBytes)
    return pop
}

func verifyProofOfPossession(publicKey *bls.PublicKey, pop *bls.Signature) bool {
    publicKeyBytes := bls.PublicKeyToCompressedBytes(publicKey)
    return bls.Verify(publicKey, publicKeyBytes, pop)
}

Threshold Signatures

Implement k-of-n threshold signatures for distributed consensus:

// Threshold signature share generation
type ThresholdSigner struct {
    index      int
    privateKey *bls.SecretKey
    publicKeys []*bls.PublicKey
    threshold  int
}

func (ts *ThresholdSigner) SignShare(message []byte) *bls.Signature {
    return bls.Sign(ts.privateKey, message)
}

// Combine threshold signature shares
func combineThresholdSignatures(shares []*bls.Signature, indices []int, threshold int) (*bls.Signature, error) {
    if len(shares) < threshold {
        return nil, fmt.Errorf("insufficient shares: need %d, got %d", threshold, len(shares))
    }

    // Use first k shares (simplified - actual implementation uses Lagrange interpolation)
    validShares := shares[:threshold]

    // Aggregate the shares
    combined, err := bls.AggregateSignatures(validShares)
    if err != nil {
        return nil, err
    }

    return combined, nil
}

Performance Benchmarks

Performance characteristics on modern hardware (Apple M1):

OperationTimeThroughputNotes
Key Generation150 μs6,666 ops/secOne-time per validator
Sign1.2 ms833 ops/secPer message signing
Verify2.5 ms400 ops/secSingle signature
Aggregate (100 sigs)0.5 ms2,000 ops/secConstant time
Verify Aggregate (100)250 ms4 ops/secBatch verification available
Pairing2.1 ms476 ops/secCore operation

Optimization Techniques

  1. Signature Caching: Cache verified signatures to avoid repeated verification
  2. Batch Verification: Verify multiple signatures in a single operation
  3. Parallel Verification: Use goroutines for concurrent signature verification
  4. Precomputed Tables: Use precomputed pairing tables for faster verification

Security Considerations

Best Practices

  1. Key Generation

    // Always use cryptographically secure randomness
privateKey, err := bls.NewSecretKey() // Uses crypto/rand internally

// Never use deterministic key generation in production

  2. Proof of Possession

    // Always verify proof of possession before accepting public keys
if !verifyProofOfPossession(publicKey, pop) {
    return errors.New("invalid proof of possession")
}

  3. Message Domain Separation

    // Use domain separation for different message types
func signWithDomain(sk *bls.SecretKey, message []byte, domain string) *bls.Signature {
    prefixedMsg := append([]byte(domain), message...)
    return bls.Sign(sk, prefixedMsg)
}

Attack Vectors and Mitigations

AttackDescriptionMitigation
Rogue Key AttackAdversary creates key to cancel honest signaturesProof of Possession
Related Key AttackExploiting algebraic relationshipsDomain separation
Small Subgroup AttackUsing points from small subgroupsSubgroup checks
Side Channel AttackTiming/power analysisConstant-time implementation

Integration Examples

Consensus Voting

Implement efficient consensus voting with BLS aggregation:

type ConsensusVote struct {
    Height    uint64
    BlockHash []byte
    Signature *bls.Signature
}

type VoteAggregator struct {
    votes      map[string]*ConsensusVote
    publicKeys map[string]*bls.PublicKey
}

func (va *VoteAggregator) AddVote(voterID string, vote *ConsensusVote) error {
    // Verify individual vote
    pubKey := va.publicKeys[voterID]
    message := append(toBytes(vote.Height), vote.BlockHash...)

    if !bls.Verify(pubKey, message, vote.Signature) {
        return errors.New("invalid vote signature")
    }

    va.votes[voterID] = vote
    return nil
}

func (va *VoteAggregator) GetQuorumCertificate(threshold int) (*QuorumCertificate, error) {
    if len(va.votes) < threshold {
        return nil, errors.New("insufficient votes")
    }

    // Collect signatures
    var signatures []*bls.Signature
    var signers []string

    for voterID, vote := range va.votes {
        signatures = append(signatures, vote.Signature)
        signers = append(signers, voterID)
    }

    // Aggregate signatures
    aggregatedSig, err := bls.AggregateSignatures(signatures)
    if err != nil {
        return nil, err
    }

    return &QuorumCertificate{
        Height:      va.votes[signers[0]].Height,
        BlockHash:   va.votes[signers[0]].BlockHash,
        Signature:   aggregatedSig,
        Signers:     signers,
    }, nil
}

Multi-Signature Wallets

Implement multi-signature wallets with threshold BLS:

type MultiSigWallet struct {
    threshold  int
    publicKeys []*bls.PublicKey
    pending    map[string][]*bls.Signature
}

func (w *MultiSigWallet) SubmitSignature(txHash []byte, signature *bls.Signature, signerIndex int) error {
    key := hex.EncodeToString(txHash)

    // Verify signature
    if !bls.Verify(w.publicKeys[signerIndex], txHash, signature) {
        return errors.New("invalid signature")
    }

    w.pending[key] = append(w.pending[key], signature)

    // Check if threshold reached
    if len(w.pending[key]) >= w.threshold {
        return w.executeTx(txHash)
    }

    return nil
}

Testing

Comprehensive testing for BLS signatures:

func TestBLSAggregation(t *testing.T) {
    // Generate validators
    validators := make([]*bls.SecretKey, 100)
    publicKeys := make([]*bls.PublicKey, 100)

    for i := range validators {
        validators[i], _ = bls.NewSecretKey()
        publicKeys[i] = bls.PublicKeyFromSecretKey(validators[i])
    }

    // Sign message
    message := []byte("consensus block at height 12345")
    signatures := make([]*bls.Signature, len(validators))

    for i, validator := range validators {
        signatures[i] = bls.Sign(validator, message)
    }

    // Aggregate
    aggregated, err := bls.AggregateSignatures(signatures)
    require.NoError(t, err)

    // Verify aggregated signature
    valid := bls.VerifyAggregateCommon(publicKeys, message, aggregated)
    require.True(t, valid)

    // Test with subset (threshold)
    threshold := 67 // 2/3 + 1
    subsetSigs := signatures[:threshold]
    subsetPubs := publicKeys[:threshold]

    subsetAgg, err := bls.AggregateSignatures(subsetSigs)
    require.NoError(t, err)

    valid = bls.VerifyAggregateCommon(subsetPubs, message, subsetAgg)
    require.True(t, valid)
}

Advanced Features

Aggregate Verification

Verify multiple messages with different signers efficiently:

func aggregateVerifyDistinct(publicKeys []*bls.PublicKey, messages [][]byte, signatures []*bls.Signature) bool {
    // Each signer signs a different message
    if len(publicKeys) != len(messages) || len(messages) != len(signatures) {
        return false
    }

    // Aggregate signatures
    aggregated, err := bls.AggregateSignatures(signatures)
    if err != nil {
        return false
    }

    // Verify using distinct message aggregation
    return bls.VerifyAggregateDistinct(publicKeys, messages, aggregated)
}

Distributed Key Generation (DKG)

Setup for threshold signatures without trusted dealer:

type DKGParticipant struct {
    index      int
    secret     *bls.SecretKey
    shares     map[int]*bls.SecretKey
    publicPoly []*bls.PublicKey
}

func (p *DKGParticipant) GenerateShares(threshold, total int) {
    // Generate polynomial coefficients
    coeffs := make([]*bls.SecretKey, threshold)
    coeffs[0] = p.secret

    for i := 1; i < threshold; i++ {
        coeffs[i], _ = bls.NewSecretKey()
    }

    // Generate shares for each participant
    for j := 1; j <= total; j++ {
        share := evaluatePolynomial(coeffs, j)
        p.shares[j] = share
    }

    // Publish public polynomial
    for _, coeff := range coeffs {
        p.publicPoly = append(p.publicPoly, bls.PublicKeyFromSecretKey(coeff))
    }
}

References

Introduction

Cryptographic primitives including BLS signatures and post-quantum algorithms

C++ Libraries

High-performance C++ cryptography libraries for GPU acceleration

On this page

BLS SignaturesOverviewTechnical DetailsCryptographic ParametersMathematical FoundationImplementationKey GenerationSigning MessagesSignature VerificationSignature AggregationBasic AggregationProof of PossessionThreshold SignaturesPerformance BenchmarksOptimization TechniquesSecurity ConsiderationsBest PracticesAttack Vectors and MitigationsIntegration ExamplesConsensus VotingMulti-Signature WalletsTestingAdvanced FeaturesAggregate VerificationDistributed Key Generation (DKG)References