DOCSEARCHbyAlgolia
Submit Docs

libsecp256k1 Documentation

repository·master·Indexed 25 days ago

https://github.com/bitcoin-core/secp256k1

A high-performance, high-assurance C library for cryptographic primitives on the secp256k1 elliptic curve, optimized for the Bitcoin system. It provides ECDSA signing, verification, key generation, and support for optional modules including Schnorr signatures (BIP-340), ECDH key exchange, ElligatorSwift (BIP-324), MuSig2 (BIP-327), and Silent Payments (BIP-352). The library features constant-time and constant-memory access for signing and public key generation, with no runtime dependencies or heap allocation.

Tokens
7.3K
Snippets
12
Records
31
Agent score
82%

What's inside libsecp256k1

  1. Overview of libsecp256k1

    master

    libsecp256k1 is a high-performance, high-assurance C library providing cryptographic primitives for the secp256k1 elliptic curve. It is designed for high quality and efficiency, with a primary focus on the Bitcoin system.

    Key features include:

    • ECDSA signing, verification, and key generation.
    • Additive and multiplicative tweaking of keys.
    • Serialization/parsing of keys and signatures.
    • Constant-time, constant-memory access for signing and public key generation.
    • Derandomized ECDSA (RFC6979).
    • No runtime dependencies and no runtime heap allocation.
    • Support for optional modules: Schnorr signatures (BIP-340), ECDH key exchange, ElligatorSwift (BIP-324), MuSig2 (BIP-327), and Silent Payments (BIP-352).

  2. Understand the ElligatorSwift module for secp256k1

    master

    The ellswift module provides a way to encode secp256k1 public keys into a 64-byte format that is computationally indistinguishable from uniform random byte arrays. This is useful for privacy, as the encoded keys do not reveal the underlying elliptic curve structure.

    Key Features

    • 64-byte Public Key Format: Encodes public keys as two concatenated 32-byte big-endian field elements ($u$ and $t$).
    • Encoding/Decoding: Functions to convert between standard public keys and the ellswift format.
    • Convenience Functions: Includes specialized functions for key generation and Elliptic Curve Diffie-Hellman (ECDH) that operate directly on ellswift-encoded keys.

    Conceptual Model

    • Encoding: Conceptually, an x-coordinate is encoded by picking a random field element $u$ and finding a $t$ such that the ElligatorSwift function $F_u(t)$ results in the target x-coordinate. The algorithm ensures the resulting $(u, t)$ pair is uniformly random.
    • Decoding: The process takes the 64-byte input, splits it into $u$ and $t$, and evaluates $F_u(t)$ to recover the x-coordinate on the curve.

  3. How the safegcd algorithm computes the GCD

    master

    The safegcd algorithm computes the Greatest Common Divisor (GCD) of an odd integer f and any integer g using a series of "division steps" (divsteps). It maintains a state variable delta (starting at 1) to guide the algorithm toward shrinking the magnitudes of f and g without needing to inspect high-order bits, making it suitable for constant-time implementations.

    Algorithm Logic:

    • The loop continues until g == 0.
    • In each step, f is kept odd.
    • If g is odd, it is transformed into an even number by either (g - f) // 2 or (g + f) // 2 depending on the value of delta.
    • If g is even, it is simply replaced by g // 2.
    • Once g == 0, the GCD is |f|.
    def gcd(f, g):
    """Compute the GCD of an odd integer f and another integer g."""
    assert f & 1  # require f to be odd
    delta = 1     # additional state variable
    while g != 0:
        assert f & 1  # f will be odd in every iteration
        if delta > 0 and g & 1:
            delta, f, g = 1 - delta, g, (g - f) // 2
        elif g & 1:
            delta, f, g = 1 + delta, f, (g + f) // 2
        else:
            delta, f, g = 1 + delta, f, (g    ) // 2
    return abs(f)

  4. Encode and decode full (x, y) coordinates using ElligatorSwift

    master

    While ElligatorSwift is often used for x-only encoding, it can be extended to encode full $(x, y)$ coordinates. This is achieved by using the sign of the encoded value $t$ to represent the sign of the y-coordinate.

    To encode the sign of $y$ in the sign of $Y$, the encoding function $G_{c,u}(x, y)$ is modified such that the sign of $w'$ is decided based on the sign of $y$. This allows the range of $c$ to be reduced to $[0, 4)$ because the sign information is no longer carried by $c$ itself.

    Warning: This method is intended for encoding points where both the x-coordinate and y-coordinate are unpredictable. If you are encoding x-only points where the y-coordinate is implicitly defined (e.g., always even or always in $[0, q/2]$), you must use the x-only encoder described in Section 3.5 to avoid reintroducing bias.

  5. Avoid API misuse in the MuSig module

    master

    The MuSig API is designed for misuse resistance, but the interactive nature of the protocol introduces failure modes that can lead to catastrophic results like secret key leakage. To use the module safely, you must adhere to these three requirements:

    1. Unique Nonces: Generate a unique nonce per signing session using secp256k1_musig_nonce_gen. Refer to the comments in include/secp256k1_musig.h for implementation guidance.
    2. No Serialization of Nonces: Never copy or serialize the secp256k1_musig_secnonce structure. Use the provided accessor functions instead.
    3. Use Accessors for Opaque Data: Never read from or write to opaque data structures directly; always use the provided accessor functions.

  6. Understand the ElligatorSwift encoding process

    master

    ElligatorSwift encoding is the process of finding a pair $(u, t)$ such that the Elligator function $F_u(t)$ results in a given $x$.

    To implement the inverse function $F_u^{-1}(x)$, the algorithm follows these conceptual steps:

    1. Find all $(X, Y)$ solutions in the set $S_u$ that could produce $x$ via the $x_1, x_2,$ or $x_3$ formulas.
    2. Map those $(X, Y)$ solutions back to $t$ values using the inverse mapping $P_u^{-1}(X, Y)$.
    3. Verify each $t$ value by checking if $F_u(t) = x$ to ensure the round-trip is valid.
    4. Return the valid $t$ values.

    To optimize performance and ensure correctness, the decoder uses a precedence order of $(x_3, x_2, x_1)$. This allows the encoder to use a simpler round-trip check: for $x_1$ and $x_2$ decodings, one can simply check if $g(-u-x)$ is a square to determine if $x_3$ would have taken precedence.

  7. Batching multiple divsteps for efficiency

    master

    To optimize performance, multiple divsteps can be batched. Instead of updating the full-size f, g, d, and e variables every iteration, the algorithm computes a combined transition matrix t for N steps.

    Key Components of Batching:

    1. divsteps_n_matrix: Computes the delta and a transition matrix t (scaled by $2^N$) using only the bottom $N$ bits of f and g. This allows using small integer arithmetic (e.g., 64-bit) to process many steps at once.
    2. update_fg: Applies the transition matrix to the integers f and g. Since the result of the combined steps is guaranteed to be a multiple of $2^N$, the division is performed via a bitwise right shift (>> N).
    3. update_de: Applies the transition matrix to the modular variables d and e. This requires a specialized division div2n which uses a precomputed value Mi = 1/M mod 2^N to perform division by $2^N$ modulo M efficiently.

    This batching approach is highly efficient because it minimizes the number of expensive updates to the full-precision large integers.

    def modinv(M, Mi, x):
    """Compute the modular inverse of x mod M, given Mi=1/M mod 2^N."""
    assert M & 1
    delta, f, g, d, e = 1, M, x, 0, 1
    while g != 0:
        # Compute the delta and transition matrix t for the next N divsteps
        delta, t = divsteps_n_matrix(delta, f % 2**N, g % 2**N)
        # Apply the transition matrix t to [f, g]:
        f, g = update_fg(f, g, t)
        # Apply the transition matrix t to [d, e]:
        d, e = update_de(d, e, t, M, Mi)
    return (d * f) % M

  8. Optimize safegcd by avoiding modulus operations

    master

    To improve performance in the safegcd implementation, expensive generic modulus operations can be avoided in update_de and modinv.

    In update_de, instead of requiring $d$ and $e$ to be in the range $[0, M)$ at all times, you can allow them to expand into the range $(-2M, M)$. This is achieved by inlining the div2n logic and using a correction factor to cancel out the bottom $N$ bits of the intermediate products.

    To ensure the variables do not grow indefinitely, you can increment $d$ or $e$ by $M$ whenever they are negative. This can be optimized by computing the necessary multiples of $M$ to add to the intermediate products $cd$ and $ce$ directly, rather than modifying $d$ and $e$ first.

  9. Achieve constant-time execution in divsteps

    master

    To prevent side-channel attacks, the safegcd algorithm must run in constant time. This requires removing data-dependent branches and loop iterations:

    1. Constant Iterations: Replace the while g != 0 loop in modinv with a fixed number of iterations. For 256-bit inputs, 741 iterations are sufficient (724 is a tighter known bound).
    2. Bitwise Operations: Replace conditional branches (e.g., if delta > 0) with bitwise masks and arithmetic.

    Conditional Negation Trick: To negate a value $v$ conditionally based on a mask $c$ (where $c$ is $-1$ if the condition is true and $0$ otherwise), use the two's complement identity: v_new = (v ^ c) - c.

    Mask Generation: To generate a mask $c$ from a condition like delta > 0, use a right shift: c = (delta) >> 63 (on a 64-bit system). This maps positive numbers to $0$ and negative numbers to $-1$.

  10. Calculate the Jacobi symbol using `safegcd`

    master

    The safegcd approach can be extended to calculate the Jacobi symbol $(x | M)$ by tracking an extra variable $j$ that maintains the relationship $(x | M) = j imes (g | f)$ at every step.

    Because the Jacobi symbol is only defined for positive odd integers, the implementation uses a modified step called a posdivstep (e.g., (g + f) // 2 instead of (g - f) // 2).

    Requirements:

    • $\gcd(x, M) = 1$
    • $x \neq 0$

    Implementation Note: Since convergence for posdivsteps is empirical, the algorithm performs a bounded number of steps and falls back to a square-root based Jacobi calculation if convergence is not reached.

  11. Understand variable-time optimizations in safegcd

    master
    The safegcd implementation in libsecp256k1 can be optimized for speed when computing modular inverses of non-secret data. While constant-time operations are required for secret data to prevent side-channel attacks, non-constant time versions are significantly faster. These optimizations involve consolidating multiple divstep operations by counting trailing zeros and using precomputed tables (like NEGINV16) to cancel multiple bits of the divisor simultaneously.

  12. Verify libsecp256k1 release signatures

    master

    To ensure the integrity of your source code, you should verify the GPG-signed git tags for each release.

    1. Obtain the GPG keys listed in SECURITY.md.
    2. Clone the repository: git clone https://github.com/bitcoin-core/secp256k1.
    3. Checkout the desired release tag (e.g., v0.7.1).
    4. Use git tag -v to verify the signature and look for 'Good signature'.
    git clone https://github.com/bitcoin-core/secp256k1
git checkout v0.7.1
git tag -v v0.7.1 | grep -C 3 'Good signature'