Understanding Cryptography for Bitcoin by John Newberry

The following is a lecture by John Newberry. Essentially, it’s a lecture that describes the proofs and mathematics underpinning the calculations for private keys and public keys. I’ve followed along and wrote down everything that has been said here, in order to get a better grasp on elliptic curves, finite fields, etc.

Transaction example from Bitcoin Whitepaper

A transaction consists of:

  • one or more txins, which contain:
    • a reference to the txout that is being spent
    • a digital signature proving that the owner of the private key authorized the transaction
  • one or more txouts, which contain:
    • the amount
    • the public key of the recipient

Verifying A Transaction

Bitcoin nodes do the following to verify each transaction:

  • Check that each txin, corresponds with an unspent txout.
  • Checks that the total amount in the txouts, does not exceed the total amount from the txins.
  • Check that each txin contains a valid signautre for the public key from the txout referenced.

Digital Signature

Digital Signatures are used to transfer ownership of coins.

A digital signature proves that the owner of the coin authorised the transfer:

  • only someone with the private key can sign the transaction (authentication)
  • no-one can change the transaction after it has been signed (integrity

What is a digital signature?

Digital signatures make use of asymmetric cryptography.

The user has a public key (which is published and known), and a corresponding private key.

Only someone with this private key can create a valid signature over a message. Anyone with the public key and the message, can confirm that the signature is valid.

Digital Signatures and Bitcoin

Bitcoin uses ECDSA over secp256k1, however a better signature algorithm is the Schnorr signature algorithm, as ECDSA is a bit of a hack to get around the patent reserving the Schorr signature.

ECDSA is an application of the discrete log problem, essentially meaning it is easy to multiply in this system, but much more difficult to divide.

Discrete logs are defined for cyclic groups with a generator G. The problem is defined as:

for a given H in the group, what is the scalar X, such that XG=H

Bitcoin uses the group of points on the elliptic curve secp256k1 defined over a finite field.

Finite Fields

Group

Defined as a set of objects along with a binary operator +.
The binary operator has the following settings.

  • Closure
    If you add two elements together, they are still an element within the group.
  • Identity
    Adding 0 to X, results in X
  • Inverse
    If you have a number X within a group, you also have the inverse, and when adding these two elements together, it returns 0.
  • Associativity
    (a + b) + c = a + (b + c)
  • Communicativity
    a + b = b + a

Cyclic Group

A group is considered cyclic, if there is a generator element:

a = g +g + g … (n times)

This I really didn’t understand, and the more I rewatched this part, the more I got confused. The following Youtube video explained the nature of cyclic groups and helped me understand a lot more about what we’re dealing with here.

Additionally, some of the notation in this video is explained, and it makes sense of the notation in the original lecture.

Field

A field is a commutative group with a secondary binary operator X.

The second binary operator is also closed, has an identity (1), has inverses (except for 0), is associative and commutative.

The binary operators are also distributive:

a x (b + c) = (a x b) + c

We can add, subtract, multiply, and divide over a field.

Example Fields

The real numbers are thought of as an infinite field.

The rational numbers, with addition and multiplication defined as normal, is an infinite field.

Integers from 0 to (n – 1), with addition and multiplication defined modulo n is a finite field.

Fp = {0,1,2,3,4,....,p-1}
F13 = {0,1,2,3,4,...,12}
4 + 5 = 9
8 + 9 = 4, (17 % 13 = 4)
4 - 8

Elliptic Curves

An elliptic curve is a curve of the form:

y2 = x3 + ax + b

In Bitcoin, we use the secp256k1 curve

y2 = x3 + 7

Instead of defining secp256k1 over all reals, we define it over a finite field of integers mod p.

Defining a Group Operation for the Elliptic Curve

To add two points:

  • Take the line meeting the two points
  • Find where the line intersects the curve again
  • Reflect through the x axis

To double a point:

  • Take the tangent at that point
  • Find where the tangent meets the curve again
  • Reflect through the X axis

A point’s inverse is the reflection in the X axis.

Adding a point to its inverse, yields our group identity: the point a infinity.

Adding the point at infinity to any point P, yields P.

Generating a Cyclic Group

  • Take any point G on the curve.
  • Repeatedly add it to itseflf until you reach G again.
  • The set of points generated is a cyclic group.
The generator point for secp256k1
The generator point for secp256k1

Discrete Log Problem For An Elliptic Curve

The private key, x, is scalar, 256 bit number in the range, [0, .., n-1], where n is the order of the group.

The public key is a point P on the curve where:

P = xG

It is easy to go from x to P.

It is computationally difficult to go from P to x.

This essentially means, it is easy to generate a public key from a private key, but much more difficult to generate a private key from a public key, because division in finite fields is difficult. This is how we know that our public and private keys are secure.

Schnorr Signatures

Schnorr Identification Protocol

A prover can prove to a verifier that she knows the private key x corresponding to a public key P without revealing x.

The verified learns nothing about x from the proof (except the fact that the prover knows x).

This is called a proof in zero knowledge.

Zero-Knowledge Proof

A zero-knowledge proof requires three properties:

  • Completeness – the proof convinces the verifier
  • Zero-knowledgeness – the proof doesn’t leak information
  • Soundness – a proof can only be produced by a prover who knows the private key

Schnorr Identification Protocol Steps

  1. Commitment – The prover picks a nonce scalar k and commits to it by sending K = kG to the verifier.
  2. Challenge – The verifier sends a challenge scalar e
  3. Response – The prover sends the response scalar:
    s = k + ex

The verified is convinced that the prover knows x if the identity holds:

sG = kG + exG
= K + eP

The transcript of the 3 step protocol is: (K, e, s)

If you can produce a proof, for any challenge e, then you must know x.

If verifier has:

s1 = k + e1x
and
s2 = k + e2x

They can now calculate:
x = s1 - s2 / e1 - e2

Non-Interactive Schorr Identification Protocol

The verifier’s only role was to provide a “random” challenge.

If we can replace the verifier with a random oracle that simply provides a random number after the commitment step, then we don’t need a verifier.

We treat a hash function as a random oracle.

“After” is key here. It means that the prover cannot know the output to a hash function before evaluating it.

This is called a Fiat-Shamir transform.

This has 3 steps:

  1. The prover picks a nonce scalar k
  2. The prover calculates e=H(kG)
  3. The prover computes the scalar s = k + ex

The proof is (s,e)

Anyone can verify by checking:

sG = kG + exG

Signature of A Message

Since H is a random oracle and returns different values for different inputs, the prover can add extra inputs to H.

The result is a signature of knowledge over a mesage.

The prover can set:

e = H(m||kg)

The prover calculates s in the normal way:

s = k + ex

The verifier then checks that:

sG = kG + exG
and
e = H(m||kg)

ECDSA

We use ECDSA with Bitcoin because Schnorr signatures were encumbered by a patent.

Few disadvantages compared to Schnorr:

  • Signatures are not linear (makes threshold and adaptor signatures much more difficult)
  • There is no security proof for ECDSA
  • ECDSA signatures are malleable.

ECDSA Signing

The prover signs a message m as follows:

  1. Set z as the leftmost bits of H(m)
  2. Pick a random nonce scalar k
  3. Set K = kG and r as the x coordinate of K
  4. Set s = k-1(z + rx)

The signature is the pair (r,s)

Verification of ECDSA

The signatures are verfiied as follows:

  1. Set z as the leftmost bits of H()m
  2. Set u = z/s and v = r/s
  3. If the x coordinate of uG + vP is equal to r, then the signature is valid.

More Reading

Borromean Ring Signatures

Confidential Transactions and Bulletproofs

Zero-knowledge proofs

Schorr Signatures