Schnorr vs ECDSA Signatures

signatures.typ

#import "@preview/polylux:0.3.1": *
#import themes.simple: *
#set text(font: "Inria Sans")
#set align(horizon)
#show: simple-theme.with(footer: [Bitcoin Signatures])

#title-slide[
  = Bitcoin Signatures
  #v(2em)

  Jose Storopoli #footnote[Alpen Labs] #h(1em)

  October 2023
]

#slide[
  == What are Digital Signatures?

  - Verify sender identity and message integrity.
  - Placed in the *input* of a Bitcoin transaction.
  - Purpose: Ensure authenticity and prevent unauthorized spending.
]

#slide[
  == Other Uses of Digital Signatures

  - Secure email communication.
  - Code signing for software.
  - Digital certificates for secure web browsing.
]

#slide[
  == ECDSA ($mod n$ implicitly)

  - Widely used in Bitcoin.
  - Complex and non-linear.
  - Signature malleability issues.
  - Signature components:

    - $r = (g^k)_x$
    - $e = H(m)$
    - $s = k^(-1)(e + r dot.c d)$
]

#slide[
  == Schnorr ($mod n$ implicitly)

  - Simpler and linear.
  - Supports multi-signatures.
  - Non-malleable and more efficient.
  - Signature components:

    - $r = (g^k)_x$
    - $e = H(r || m)$
    - $s = k + d dot.c e$
]

#slide[
  == Why Schnorr is Linear? ($mod n$ implicitly)

  - $s = k + d dot.c e mod n$, then you can write it as:
    $ s = k + (d_1 + dots + d_m) dot.c e. $
  - Whereas ECDSA uses $s = k^(-1)(z + r dot.c d)$.
    The $k^(-1)$ term makes the equation non-linear.
]

#centered-slide[
  = The Discrete Log Problem
]

#slide[
  == What is the Discrete Log Problem?

  - Given $g$ and $g^k mod p$, finding $k$ is hard.
  - Basis for cryptographic security.
  - "DLP is hard" means no efficient algorithm exists to solve it: $cal(N P)$-problem.
  - If DLP were easy, cryptographic systems would be insecure: $cal(P)$-problem.
  - NOTE: In post-quantic computing, DLP is no longer a secure assumption.
    See Shor's algorithm and lattice-based cryptography.
]

#slide[
  == DLP in Practice $ZZ_7$

  Find $b^x mod 7 = y$.

  #text(size: 22pt)[
    #table(
      columns: (auto, auto, auto, auto, auto, auto, auto),
      inset: 10pt,
      align: horizon,
      table.header(
        [$b$],
        [$b^1 mod 7$],
        [$b^2 mod 7$],
        [$b^3 mod 7$],
        [$b^4 mod 7$],
        [$b^5 mod 7$],
        [$b^6 mod 7$],
      ),

      [1], [1], [1], [1], [1], [1], [1],
      [2], [2], [4], [1], [2], [4], [1],
      [3], [3], [2], [6], [4], [5], [1],
      [4], [4], [2], [1], [4], [2], [1],
      [5], [5], [4], [6], [2], [3], [1],
      [6], [6], [1], [6], [1], [1], [1],
    )
  ]
]

#slide[
  == Signature Malleability

  - ECDSA signatures can be altered without changing the message.

  - Example: Modifying $s$ to $-s mod n$ still yields a valid signature.

  - Leads to transaction malleability.

  - Schnorr signatures prevent this due to their structure.

  - *Fixes:*
    - Use Schnorr signatures.
    - Implement protocol-level solutions like SegWit.
]