Tags: crypto
July 27, 2021

(sourced from: https://wiki.bitcoinsv.io/index.php/Secp256k1)

A typical bitcoin explanation goes something like this:

Using a bunch of fancy mathematics, we can create a series of transactions on a shared ledger. Whenever we want to know how much is in an account, we add up all the credits and subtract all the debits. The fancy mathematics prevents it from being tampered.

While this is a fine explanation, it leaves a lot lacking. In particular, this explanation doesn't give an intuitive sense on how innovations like zero-knowledge work (e.g. "why is Monero preferred by many over ZCash?")

This post aims to recitify that. Here, a more technical explanation of bitcoin will be explored, complete with some code snippets. Readers by the end should know how and why bitcoin works.

## The Key Problem Bitcoin Needs to Solve to Work

Bitcoin solves a major problem: we need to be able to write transactions into a ledger without any risk of "imposters." That is, nobody should be able to send money except for us. This is commonly referred to as Double-Spend.

This is easy to solve if we have a trusted source. That source can verify its us who wants to send or receive.

Bitcoin pulls this off without such a trusted source. This is why its called "trust-less."

That entails a further problem: all information needs to be out in the open such that everybody can see it.

That problem is the first we want to solve

## The Art of Cryptography: Sending Information in Plain Sight

Suppose we have two people: Alice & Bob. Alice wants to send a message to Bob such that only Bob can see it even if the message is intercepted ahead of time. To do this, she'll encrypt it. This is the fundamental problem cryptography aims to solve.

With bitcoin, we're also working in plain sight. All information is conveyed openly. What we need is a way to send information that only people we intend to decode can, in fact, decode it.

How can we solve this?

The most simple form of encryption is known as a cipher. This is what all good cold war spies used half a century ago.

The idea is that you shift every character in a message by a certain amount. In binary, this is done by XORing bits together. Analog ciphers involve a key of some kind that shifts the letter positions -- typically, it can get more complex such as with the Enigma.

Exchanging a cipher is tricky though. All the information exchanged needs to happen across a public channel. If a cipher is sent over public channels then an adversary can intercept the key and use it to decode any additional messages.

How do we send information without a cipher ahead of time?

Alice & Bob will need to send information to each other of some sort. Whatever is hidden from the adversary will also be hidden from each other.

Let's suppose the cipher is composed of three parts: a secret from Alice, a secret from Bob, and a common value that we'll label $$G$$. In order to use the cipher and decode the message, we need all three parts.

Alice cannot send her secret to Bob, but she can send a combination of the secret and $$G$$. Bob can likewise do the same. Then each party will have all three parts.

But can't the adversary listen for this like before? Won't they have two-thirds of the cipher?

The adversary being able to make use of two two-thirds of the cipher would mean they can differentiate where the secret and $$G$$ separate. If they can't, then the information will be gobbledy-gook to them.

To "scramble" the cipher like this, we need a special function that is commutative (i.e. $$\mathcal{f}(a,b,c) = \mathcal{f}(b,a,c)$$) and one-way: there's no way to get $$a$$ from $$\mathcal{f}(a,b)$$ even if I know $$b$$. Does such a function exist?

Indeed it does!

## Elliptic Curves

To get our function, we need to think outside of the box. It won't be a simple $$\mathcal{f}(x) = mx^2 + b$$ as these can be trivially reversed with the quadratic formula. We need something that's easy to prove but hard to find. Prime numbers fit this bill perfectly.

Next, we'll need a way to verify that the numbers are in a common set and follow a consistent set of rules. This will ensure our function is commutative.

Such an example exists with elliptic curves. These are functions that follow the following formula:

$$\mathcal{E}: y^2 = x^3 + ax + b$$

[1]

If Alice & Bob want to communicate, they can agree on a point $$G$$ in this set, create a secret key, then multiply all three together to get our cipher. The only part they need to share is their private key multiplied by this agreed upon, publicly-shared point of $$G$$. [2]

Our elliptic function, therefore, only needs to do two things: add and multiply. For the sake of brevity, they won't redrived here though you can find other examples online. Below are the resulting equations:

$$s = \frac{y_P - y_Q}{x_P - x_Q}$$
$$x_R = s^2 - (x_P + x_Q)$$
$$y_R = s(x_p - x_R) - y_P$$

Exception of Point Doubling (i.e. $P + P = R = 2P$)

$$s = \frac{3x_P^2 + a}{2y_P}$$
$$x_R = s^2 - 2x_P$$
$$y_R = s(x_P - x_R) - y_P$$

Exception of adding vertical points (known as the infinity point)

$$P + Q = O$$ if $$x_P = x_Q$$ or $$x_P = 0$$

This infinity point is important. Sets generated by multiplying an elliptic curve against a point repeat on themselves. This happens at the infinity point. If $$19G = 0$$, then $$20G = G$$.

Multiplication ($$Q=kP$$) is then a matter of repeating this addition over and over again. This would take a long time so we'll use an algorithm known as "double-and-add-one" which will double the running value if we're divisible by 2 and add one otherwise. The following pseudocode comes from wikipedia:

def double_and_add(Q, n):
R = Point(inf, inf)
while n > 0:
if (n % 2) == 1:
R = R + Q
Q = Q + Q
return R


Going forward, we'll call this scalar product a private key ($$k$$) and the multiplication of it against $$G$$ ($$k * G$$) the public key ($$K$$).

If we pick our curve function right, then it will be really hard to know what the individual private keys are. That's because an adversary would have to multiply every single possible key.

But Alice & Bob can easily confirm a given key is valid. They just compute the multiplication of their private key times this public key.

$$cipher = k_a * k_b * G$$

What they share:

$$G$$
$$K_a = k_a * G$$
$$K_b = k_b * G$$

For Bob to get the cipher, he multiplies his private key $$k_b$$ against Alice's public key $$K_a$$. Alice does the same with Bob's public key and her private key.

$$Bob: k_b * K_a = k_b * k_a * G$$
$$Alice: k_a * K_b = k_a * k_b * G$$

A full working implementation of this as an object is below:

import random
from typing import Union, Callable, Tuple

class EllipticPoint(object):
def __init__(
self,
x: int,
y: int = None,
a: int = 0,
b: int = 0,
c: int = 7,
prime: int = ((2 ** 255) - 19),
):
"""
For storing Elliptic Points corresponding to elements:

y^2 = x^3 + ax^2 + bx + c

Defaults to a secp256k1 -- save curve as in bitcoin

Example for ed25519 curve: a=486662, b = 1, & c = 0

:param x: the integer for the x coordinate of the point
:param y: the integer for the y cooirdinate. If none, it will calculate
this based on the curve parameters provided (a - c)
:param a: corresponds to the elliptic function (see above)
:param b: corresponds to the elliptic function (see above)
:param c: corresponds to the elliptic function (see above)
:param prime: prime to use for modulo operations, defaults to ((2**255) - 19)
from the ed25519 curve

>>> G = EllipticPoint(x=5, a=0, b=0, c=7, prime=((2**255) - 19))  # y**2 = x**3 + 7
>>> G.curve(G.x)**(0.5) == G.y
True
>>> ( ((G.y**2) - G.curve(G.x) ) % ((2**255) - 19) ) == 0
True
"""
self.x = x
self.curve = EllipticPoint._curve_factory(a, b, c, prime)
if y is not None:
self.y = y
else:
self.y = self.curve(x)**(0.5)   # modulo here?
self.a, self.b, self.c = a, b, c
self.prime = prime

def to_tuple(self):
return (self.x, self.y)

def __repr__(self):
return "<EllipticPoint: %r,%r>" % (self.to_tuple())

def __eq__(self, anotherObj):
if isinstance(anotherObj, EllipticPoint):
return (
self.x == anotherObj.x
and self.y == anotherObj.y
and self._same_curve(anotherObj)
)
elif isinstance(anotherObj, tuple):
return self.x == anotherObj[0] and self.y == anotherObj[1]

def __rmul__(self, scalar):
return self.__mul__(scalar)

def __lmul__(self, scalar):
return self.__mul__(scalar)

def __mul__(self, scalar):
"""
Elliptic Multiply two points together. Both must have the same parameters.

>>> G = EllipticPoint(x=5)
>>> 1*G == G
True
>>> 2*G == G+G
True
>>> 3*G == G+G+G
True
>>> (2*G)+G == G+(2*G)   # guess where I was having trouble
True
"""
if not type(scalar) in [int]:
try:
scalar = int(scalar)
if scalar == 0:
raise
except:
raise ValueError(
"Can only multiply against scalar values -- value of type %r passed in: %r"
% (type(scalar), scalar)
)
assert scalar >= 0
n = scalar
R, Q = self.copy(), self.copy()
R.x, R.y = float("inf"), float("inf")
while n:
if (n % 2) == 1:
R += Q
Q += Q
n //= 2
return R

"""
Given another point, it will add the two together and return the
corresponding point in an EllipticPoint object. Both must have the
same parameters

>>> P = EllipticPoint(x=5, y=1, a=0, b=2, c=2, prime=17)
>>> Q = EllipticPoint(x=5, y=1, a=0, b=2, c=2, prime=17)
>>> P + Q
<EllipticPoint: 6,3>

>>> P = EllipticPoint(x=7, y=6, a=0, b=2, c=2, prime=17)
>>> Q = EllipticPoint(x=5, y=1, a=0, b=2, c=2, prime=17)
>>> P + Q
<EllipticPoint: 7,11>
>>> Q + P == P + Q
True
"""
if not self._same_curve(anotherObj):
raise ValueError("Both points do not correspond to the same curve")

if self == (float("inf"), float("inf")):
return anotherObj
elif anotherObj == (float("inf"), float("inf")):
return self

x_p, y_p = self.x, self.y
x_q, y_q = anotherObj.x, anotherObj.y

# point doubling
if x_p == x_q and y_p == y_q:
s_num = 3 * (x_p ** 2) + self.b
s_denom = 2 * y_p
s = s_num * EllipticPoint._multiplicative_inverse(s_denom, self.prime)
x_r = (s ** 2) - (2 * x_p)
y_r = (s * (x_p - x_r)) - y_p

# adding vertical points -- point at infinity
elif x_p == x_q and self.y != anotherObj.y:
tmp = self.copy()
tmp.x, tmp.y = float("inf"), float("inf")
return tmp

else:
s_num = y_p - y_q
s_denom = x_p - x_q
s = s_num * EllipticPoint._multiplicative_inverse(s_denom, self.prime)
x_r = (s ** 2) - (x_p + x_q)
y_r = (s * (x_p - x_r)) - y_p

to_ret = self.copy()
to_ret.x = x_r % self.prime
to_ret.y = y_r % self.prime

def copy(self):
"""
Return a perfect copy of this elliptic point.
"""
return EllipticPoint(
x=self.x, y=self.y, a=self.a, b=self.b, c=self.c, prime=self.prime
)

def _same_curve(self, anotherObj) -> bool:
"""
Given a passed function _curve, this will return true if this curve
has the same parameters as the curve represented within the object. Not
meant for use outside of internal functions.
"""
return (
self.a == anotherObj.a
and self.b == anotherObj.b
and self.c == anotherObj.c
and self.prime == anotherObj.prime
)

@staticmethod
def _curve_factory(a: int, b: int, c: int, prime: int) -> Callable[[int], int]:
"""
Returns a lambda function corresponding to the curve:

y^2 = ( x^3 + ax^2 + bx + c ) % prime

All parameters passed in correspond

:returns: function corresponding to the curve
"""
return lambda x: (x ** 3) + (a * (x ** 2)) + (b * x) + c

@staticmethod
def _multiplicative_inverse(a: int, m: int) -> int:
"""
Find the multiplicative inverse using the GCD & Extended
Euclidean Algorith -- taken from
https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode

:param x: number
:param m: the modulo for the inverse

:returns: the multiplicative inverse

>>> EllipticPoint._multiplicative_inverse(3, 11)
4

>>> EllipticPoint._multiplicative_inverse(3, 17)
6

>>> EllipticPoint._multiplicative_inverse(2, 17)
9
"""
_r, r = a, m
_s, s = 1, 0
_t, t = 0, 1
while r != 0:
q = _r // r
_r, r = r, _r - q * r
_s, s = s, _s - q * s
_t, t = t, _t - q * t

return _s % m


## Bitcoin's other problem: Verification

This is a great start but Bitcoin has to solve the double-spend problem as well. That means somebody has to be able to verify that a transaction was legitimate (e.g. authorized by the sender) without knowing that sender's private key. If they know the private key, then they can spend for that person.

This scenario is very, very similar to the problem of Alice & Bob passing messages without anybody being able to intercept and decode it.

What we need is a function that can "sign" a message with a private key such that nobody else can sign it that way. A second, public key can be used to then verify that the private key was used to sign the message.

In this case, we want to sign transactions. The sender uses his private key to record a sending of value to the receiver's public key. Then the blockchain can verify using the known and avaiable public key.

How do we go about doing this?

We'll introduce a signature function. This function needs to be computable with both the private and public key. It will also need to use a random value of some sort; this will help prevent signatures from looking too similar which would make them prone to being deciphered. We can use a very similar method as before:

• r & s => represents the signature
• n (nonce) => random value that must be unique to this transaction, between 1 and p-1 (group order)
• z: hash of our message
• k: private key of sender
• K: public key of sender
• p: prime number and group order (e.g. infinity point) of the curve

Signing:

1. Generate point C: (x,y) = n * G w/curve
2. Compute r = x_c % p
3. Compute s = n^-1 * (z + r * d) % p, if s=0, generate another n and start over

The signature s and the nonce n are stored in the transaction data. Then to verify, we have to use k * G -- our public key.

Verification

1. r & s are between 1 and p-1
2. Compute u1 = z * s^-1 and u2 = r * s^-1
3. Compute (x, y) = u1 * G + u2 * K -- (expand this out)
4. if r = x mod p, then the signatures are valid, otherwise the check fails

Know that s contains our private key in both instances -- the only way to compute it is to know the private key as an adversary would otherwise need to "brute force" and try every possible key.

To make double and triply sure that everything is hard, we'll hash each step of the way. This will make the numbers look even more random than before.

## Bitcoin as Explained to a Bright High Schooler

My updated and more thorough explanation of Bitcoin & Blockchain:

Two people can communicate using a pair of keys, one private and one public. The public key is derived from the private key using a really difficult computation but can be verified quickly once known. This same process can be used to encrypt transactions on a blockchain. Only the sender can create a transaction in his name using his unique private key. His public key will let you ensure that the transaction was created by him. Because its virtually impossible to "guess" this private key, the resulting transaction is secure and safe.

Hope that explains a lot more than most explanations!

## Errata & Notes

[1]: I've seen many examples where an additional $$x^2$$ is included but most sources agree on the equation given. This includes Bitcoin but not Monero which follows a ed25519 curve.

[2]: Know that this gets tricky because $$G$$ is a point (x & y) while our secret keys are actually numbers.

Share On: