Jan Hesters

This article aims to be an intro to blockchain because I haven't found any good tutorials out there. You'll learn the first principles that enable blockchain and you'll build a simple app that interacts with real smart contracts by the end of it.

Never Roll Your Own Crypto

"Never roll your own crypto." - Bruce Schneier

Before we dive into blockchain, absorb this important disclaimer. None of the code below is production ready. It has all kinds of vulnerabilities. Avoid creating your own crypto code because it will certainly contain exploitable vulnerabilities, too. Always use peer-reviewed open-source libraries, instead. (See also "Amateurs Produce Amateur Cryptography" from Bruce Schneier.)

It bears repeating: Do NOT use this code in production. Use it to understand how the blockchain works.

I'm going to point out some of the code's flaws (and will update this list based on "Cunningham's law".)

  • The examples use the BigInt type. BigInt operations are susceptible to timing attacks.

What You Need to Know

You should be familiar with addition, subtraction, multiplication and division.

You should know what integers are ("whole" numbers).

Additionally, you should be familiar with functions such as f(x)=y.

It also helps if you know how to code. This article uses TypeScript for coding examples, so JavaScript and TypeScript developers will have it the easiest. However, even if you use a different language or do not code at all, you'll learn a lot because I kept it simple.

For example, the function above in f(x)=y would look like this in JavaScript:

const x = f(y);

Later in the article when we'll build an app that interacts with the blockchain is when you likely won't be able to follow if you don't code, or if you do but you are unfamiliar with frontend (specifically React).

Let's start with a refresher of elemantary math that we'll need to understand elliptic curves.

Remainder

If you have two whole numbers and you divide the larger by the smaller, the remainder is what is "left over" if the divisor doesn't fit the dividend perfectly.

// dividend / divisor = quotient
8 / 8;
// ↵ 1 - no remainder
42 / 21;
// ↵ 2 - no remainder
49 / 7;
// ↵ 7 - no remainder
49 / 21;
// ↵ 2.33333... - or in whole numbers 2 with a remainder of 7
9001 / 2012;
// ↵ 4.47365805169 - or in whole numbers 4 with a remainder of 953

For the two divisions with remainders, you can see that you obtain the dividend by multiplying the divisor with the whole number quotient and adding its remainder.

// dividend = quotient * divisor + remainder
8 * 1 + 0;
// ↵ 8
21 * 2 + 0;
// ↵ 42
7 * 7 + 0;
// ↵ 49
21 * 2 + 7;
// ↵ 49
2012 * 4 + 953;
// ↵ 9001

Modulo

Most programming language have an operator that gives us the remainder called "modulo". Similar to using / to divide something, we can use the modulo operator % to get the remainder.

8 % 8;
// ↵ 0
42 % 21;
// ↵ 0
49 % 7;
// ↵ 0
49 % 21;
// ↵ 7
9001 % 2012;
// ↵ 953

I recommend you take out a piece of paper and calculate the remainder for a bunch of numbers (for example 51 % 8, 86 % 9, 8011 % 8011 and 926 % 1012) and see what you get.

51 % 8;
// ↵ 3
86 % 9;
// ↵ 5
8011 % 8011;
// ↵ 0
926 % 1012;
// ↵ 926

The last one was a trick question. Because 1012 is bigger than 926 what is left over of the dividend is everything, so the remainder is 926.

Another special case is dividing by 0.

42 % 0;
// ↵ NaN

Division by 0 is not defined in mathematics and the same is true for the modulo operator. NaN means "not a number" and is TypeScript's way of saying "nope, not gonna happen".

BigInt

So far we've used Numbers. We're going to use BigInts from this point onwards because they're better suited for large numbers and our numbers are going to get huge, soon.

In TypeScript you create a bigint by adding an n to the number like this:

9001n % 2012n;
// ↵ 953n

As you can see, we get the same result.

To make the upcoming large numbers more readable, we're also going to put _ (underscores) every 3 digits, to make the numbers easier to read. _ will be our digit group separator.

// A billion "raw":
1000000000
// vs a billion formatted with `_`:
1_000_000_000

Greatest Common Divisor

Continuing our journey through 6th grade math, let's learn about the greatest common divisor (GCD) of two numbers.

Given two non-zero integers, the GCD is the largest positive integer that divides both numbers.

For example, gcd(8, 12) = 4 because

  • 8 and 12 are both divisible by 1.
    • 8 / 1 = 1
    • 12 / 1 = 1
  • 8 and 12 are both divisible by 2.
    • 8 / 2 = 4
    • 12 / 2 = 6
  • Only 12 is divisible by 3 (because 8 / 3 = 2.66666666667, which is NOT an integer).
    • 12 / 3 = 4
  • 8 and 12 are both divisible by 4.
    • 8 / 4 = 2
    • 12 / 4 = 3
  • Neither 8 nor 12 are divisible by 5.
  • And so on ...

4 is the greatest divisor for both 8 and 12 and therefore it is the GCD of 8 and 12.

Now let's do it for 1071 and 462! Wait ... doing it "manually" by calculating every permutation like we did above woudl be tedious. Luckily, there is a way to calculate the GCD using the ...

Euclidean Algorithm

The execute the Euclidean algorithm you first have to find the remainder. Then you make the previous divisor and the dividend and the previous remainder the divisor and get the new remainder of those two numbers. You repeat this process over and over until the remainder is 0. The last divisor is the greatest common divisor.

Let's demonstrate this first with 8 and 12.

  1. 12 % 8 = 4
  2. 8 % 4 = 0 => gcd(12, 8) = 4

Let's do it for 1071 and 462.

  1. 1071 % 462 = 147
  2. 462 % 147 = 21
  3. 147 % 21 = 0 => gcd(1071, 462) = 21

We can implement this beautifully using recursion and the modulio operator.

const greatestCommonDivisor = (a: bigint, b: bigint): bigint => {
  if (b === 0n) {
    return a;
  }
 
  return greatestCommonDivisor(b, a % b);
};
 
greatestCommonDivisor(1071, 462);
// ↵ 21

Extended Euclidean Algorithm

https://www.youtube.com/watch?v=hB34-GSDT3k

Hash

A hash function maps data of arbitrary size onto data of fixed size. These return values are called "hashes". It can be described as f(message) = hash.

type simpleHash = (stringToHash: string) => string;
const simpleHash: simpleHash = stringToHash =>
  (stringToHash.length % 10).toString();
 
simpleHash("foo");
// ↵ "3"
simpleHash("goo");
// ↵ "3"
simpleHash("A hash is always mapped to a fixed length.");
// ↵ "2"

simpleHash is a function that maps any string to another string of length 1. Specifically, the string is a single digit number, which is achieved by using the modulo operator with a divisor of 10. In case you didn't know, the modulo operator % returns the remainder of the division of its dividend and its divisor. For example, 4 % 2 is 0, 5 % 2 is 1, 137 % 10 is 7 and 140 % 10 is 0.

simpleHash maps many strings to the same value. For example, foo, bar and baz would all be mapped to "3". Any other string of length 3, 13, 23 etc. would be mapped to "3", too. When several inputs map to the same output, we call this a "collision". simpleHash produces a lot of collisions. If we make a simple change, and change "foo" to "goo", we get the same output "3".

We can write a more collision resistant hash function called sfoldHash.

type sfoldHash = (stringToHash: string, tableSize?: number) => number;
const sfoldHash: sfoldHash = (stringToHash, tableSize = Infinity) => {
  let sum: number = 0;
  let mul: number = 1;
 
  for (let i = 0; i < stringToHash.length; i++) {
    mul = i % 4 === 0 ? 1 : mul * 256;
    sum += stringToHash.charCodeAt(i) * mul;
  }
 
  return Math.abs(sum) % tableSize;
};

sfoldHash iterates through each character a string and processes that four byte chunk as a ASCII number. This causes a bigger spread of the hash values. Lastly, it sums up the four-byte chunks. In case a tableSize of M is provided, that sum is converted to the range 0 to M−1 using the modulo operator. sfoldHash returns numbers instead of strings because a hash function can map to any data type.

sfoldHash("foo");
// ↵ 7_303_014
sfoldHash("goo");
// ↵ 7_303_015
sfoldHash("aaaabbbb");
// ↵ 3_284_386_755
sfoldHash("Hashing is fun.");
// ↵ 4_012_487_055

The tableSize (called M below) determines the image - the set of all output values a function may produce - of the hash function.

const M = 101
sfoldHash("foo");
// ↵ 7
sfoldHash("goo");
// ↵ 8
sfoldHash("aaaabbbb", M);
// ↵ 75
sfoldHash("Wow, hashing is cool.", M);
// ↵ 39
sfoldHash("Collisions make hashing vulnerable!", M);
// ↵ 39

As you can see, a small change in the input produces a different output. However, even though this hashing function is spreading the values a lot better than our simpleHash function, we're still easily getting (and guessing) collisions, especially for small table sizes. We will explain later, why collisions can make blockchains vulnerable to attacks further below. Instead of any hash function, in blockchain we use hash functions with special properties called a ...

Cryptographic Hash

A cryptographic hash function is a trapdoor function (one-way), which deterministically calculates a seemingly random output given some input. (The word "cryptography" stems from "secret writing" in Greek.)

Let's unpack that definition. A cryptographic hash function is a ...

  • ... trapdoor function (one-way), ... - It is hard to calculate or guess the input value that produced a given output value.
  • ... which deterministically calculates ... - The same input value always maps to the same output value.
  • ... a seemingly random output given some input. - A small change in the input should on average lead to a totally different output.

Cryptographic hash functions should have at least the following 3 properties:

  1. Preimage resistant: Given an output it is computationally infeasible to find any input that hashes to that output. Given y it is difficult to find an x such that h(x) = y.
  2. Second-preimage resistant: Given an input and an output it is computationally infeasible to find any second input which has the same output as that of the given input. Given x, it is difficult to find a second value x', which is not equal to x, such that h(x) = h(x').
  3. Collision resistant: It should be hard to calculate another input which maps to the same output. It should be hard to find x and x' such that h(x) = h(x').

This means that given slightly different data, a cryptographic hash function should produce a completely different hash (hangman-resistant). A small change to a message should change the hash value so extensively that the new hash value appears uncorrelated with the old hash value (avalanche effect).

Cryptographic hash functions should be resistant against a variety of attacks. The most important ones are:

  • Preimage attack: Given any output find an input that hashes to that output. Given y find x such that h(x)=y.
  • Second-preimage attack: Given an input and its hash find any input that hashes to the same output. Given x find x' such that h(x) = h(x').
  • Collision attack: Find two inputs that map to the same output. Find x and x' such that h(x) = h(x').
  • Chosen-prefix collision attack: Given two different prefixes p1 and p2, find two appendages m1 and m2 such that h(p1 | m1) = h(p2 | m2).

When creating the example input values for sfoldHash, I brute-forced a collision attack to find that "Wow, hashing is cool." and "Collisions make hashing vulnerable!" with M=101 both map to 39.

If we use keccak256 (a SHA-3 hash), which is an actual cryptographic hash function, we get totally different results based on small changes.

import { keccakFromString } from "ethereumjs-util";
 
keccakFromString("foo").toString("hex");
// ↵ 41b1a0649752af1b28b3dc29a1556eee781e4a4c3a1f7f53f90fa834de098c4d
keccakFromString("goo").toString("hex");
// ↵ 55a1d10f5a7bb4b8da100e62a9ca0e09d2c8a171e25b4fb1435f0e1317a0810d
keccakFromString("Wow, hashing is cool.").toString("hex");
// ↵ acb89b0949f63b767e024210008446a360ca16b4eed8a582d5ff463f79aad1f4
keccakFromString("Collisions make hashing vulnerable!").toString("hex");
// ↵ 3cc52ced2ca8450affb70b7bb953d68a126f053e0e6468793d687c4073a37ebc

Hash Chains

A hash chain is a successive application of a cryptographic hash function h to a value x. It can be described as h(h(h(h(x)))) = h^{4}(x).

const fooHashed = keccakFromString("foo").toString("hex");
// ↵ 41b1a0649752af1b28b3dc29a1556eee781e4a4c3a1f7f53f90fa834de098c4d
const hashChain = keccakFromString(fooHashed).toString("hex");
// ↵ bb090922e78e117b909bacf3d6ed789eea14df09d32bbe8249f9a703d633e5c2

In blockchain we use a specific form of binary hash chains, which is the act of taking two hashes, concatenating them and then hashing the result again.

const fooHashed = keccakFromString("foo").toString("hex");
// ↵ 41b1a0649752af1b28b3dc29a1556eee781e4a4c3a1f7f53f90fa834de098c4d
const barHashed = keccakFromString("bar").toString("hex");
// ↵ 55a1d10f5a7bb4b8da100e62a9ca0e09d2c8a171e25b4fb1435f0e1317a0810d
const binaryHashChain = keccakFromString(fooHashed + barHashed).toString("hex");
// ↵ a6dd2d161b4cc53e18ee867c9a4f930e257c61329ea2a7084073aba1335a41a9

Repeating this technique in a tree gives you a ...

Merkle Tree

A Merkle tree is a tree in which every leaf node is the cryptographic hash of some data, and every non-leaf node is the cryptographic hash chain of its child nodes. The top node of the tree is referred to as the "top hash", "root hash" or "master hash".

Merkle tree, source: Wikipedia

Hash trees are used to effciently verify large data structures because any change in the tree affects the root hash. If you change the content of a leaf node or change a hash in a non-leaf node, the changes propagate through to the top of the tree, changing the root hash.

Merkle trees are prone to second image attacks, which can be guarded against by supplying node or tree depth.

Public Key Cryptography

Public key cryptography is an assymetric cryptographic system with private keys, public keys and signatures. A private key can be used to compute correspending public keys.

Public key cryptography is called assymetric because the private key must only be known by the owner, whereas the public keys can be shared with anyone. In symmetric cryptgraphic systems a unique shared secret key has to be shared between the communicating parties, which is hard to manage. For example, if Alice wants to private chat with Bob and Charlie, and have a group chat with the three, you need 3 secret keys. One between Alice and Bob, one between Alice and Charlie, and one for all three.

Assymetric cryptgraphic systems are computationally more expensive than symmetric ones. Therefore, there are also hybrid systems in which the assymetric system is used for the initial exchange of the symmetric key.

The two main use cases for public key cryptography are:

  • Encryption - Public key cryptography can be used to encrypt messages. For example, the public key can be used to encrypt data, which can only be decrypted using the private key.

  • Digital signatures - You can create a digital signature with a private key, that can be verified with the corresponding public key. Digital signatures can prevent messages from being tampered with and can prove authorship of a message. Blockchain makes heavy use of digital signatures.

  • Alteration of public keys - One issue with public key crytpography is proving authenticity of the public key, which means that the public key belongs to the right entity. Let's say Alice wants to send Bob a signed message. If Charlie maliciously replaced Bob's copy of Alice's public key with his own (e.g. by using a "man-in-the-middle" attack), Charlie can alter the message and sign it with his private key. When Bob now uses Charlie's public keys (thinking it is Alice's) to verify the message, he will get a false positive and think the signature is authentic.

  • Exposure of private key - The private key becoming known by others is another security risk.

  • Algorithms -

Elliptic Curves

The paper "An Introduction to Bitcoin, Elliptic Curves and the Mathematics of ECDSA" by

"secp256k1 refers to the parameters of the elliptic curve used in Bitcoin's public-key cryptography, and is defined in Standards for Efficient Cryptography (SEC)" - Bitcoin Wiki

The noble-secp256k1 library from Paul Miller (and other contributors 🙏) implements the secp256k1 elegantly in JavaScript.

https://stackoverflow.com/a/32042290/8331756

/**

Private Key

We randomly generate a private key, with which we can compute a public key and then we can hash that to get a address.

The first step to generating a public and private key pair is to generate a random seed value.

import cryptoRandomString from "crypto-random-string";
 
const seed = cryptoRandomString({ length: 32 });
// ↵ 432db91daca6d7ad2615239d05d00525

When I called cryptoRandomString({ length: 32 }) it returned "432db91daca6d7ad2615239d05d00525". You'll likely get a different value 😎

It is important to use a cryptographically secure pseudorandom number generator (CSPRNG) for this. The crypto-random-string library is implemented cryptographically secure.

Public Key

const BTC_PRIME_MODULO: number =
  Math.pow(2, 256) -
  Math.pow(2, 32) -
  Math.pow(2, 9) -
  Math.pow(2, 8) -
  Math.pow(2, 7) -
  Math.pow(2, 6) -
  Math.pow(2, 4) -
  1;
// ↵ 115_792_089_237_316_195_423_570_985_008_687_907_853_269_984_665_640_564_039_457_584_007_908_834_671_663

JavaScript has a BigInt type and a Number type. The maximum safe integer for the Number type is 2^53 - 1 = 9007199254740991

Number.MAX_SAFE_INTEGER;
// ↵ 9007199254740991

In Bitcoin a private key must be a number lower than 1.1578 * 1077.

Digital Signature

It is detrimental to select different k for different signatures. Using the same k would allow us to solve the equation for the private key.

However, k can be the same for the same message and private key. Therefore rfc6979 introduced a way to deterministically calculate k based on those inputs. Generating k deterministically makes implementations easier to test and computationally more feasable.

noble-secp256k1 sign implements rfc6979, so we're going to use its methods going forward.

Go ino how Twitter could've used this to protect against their hack. Many companies are sleeping on this.

Collision Attacks on Digital Signatures

The Web Crypto API

Modern browsers support the Web Crypto API, which can be accessed through the Window.crypto property. window.crypto is a Crypto.

The Web Crypto API exposes methods such as crypto.getRandomValues(typedArray), which return cryptographically strong random values. There is no guarantee for getRandomValues() to run in a secure context, so use crypto.subtle.generateKey(algorithm, extractable, keyUsages) to generate new keys or key pairs.

You should only play around with this API to teach yourself the concepts of this article. Avoid using the Web Crypto API in your apps, unless you know what you're doing.

Mnemonic Phrase

Block

type Block = {
  nonce: number;
  previousBlockHash: string;
  timestamp: number;
}

Adding more blocks validates because protection against attacks.

Proof of Work

Mining

Bitcoin

1/100,000,000th of a bitcoin is called a "Satoshi".

A transaction describes the change of ownership of the asset.

type Input = {}
 
type Output = {}
 
type Transaction = {
  txid: string;
  version: number;
  inputs: Input[];
  outputs: Output[];
}

In Bitcoin, inputs and outputs don't add up. The difference is the transaction fee.

Forks

Byzantine Fault Tolerance

Channels

And Lightning Network?

Where to Go From Here?

  • Bitcoin Whitepaper
  • State of the Metaverse
  • Mastering Bitcoin
  • Mastering Ethereum

Thank you so much for reading this. I hope you learned something. If you have any question, my Twitter DMs are open.

Ask better questions.

Learn senior fullstack secrets
Subscribe to my newsletter for weekly updates on new videos, articles, and courses. You'll also get exclusive bonus content and discounts.