Bitcoin Puzzle #1: Building Blocks
This is a first part in a series, that describes way Bitcoin is built and how different technologies work together inside it. This part will introduce you to the most important building blocks, which are assembled together in Bitcoin, and how they work.
Here, at Akvelon, we often do free-form talks related to interesting technology or interesting development approach used in one of projects. This series is based on an internal talk/presentation, that I did to describe blockchain technology and how it was utilized to start Bitcoin.
The main goal of the talk was to show, which building blocks are used in top cryptocurrency and how they interact with each other in its implementation. This talk and series’ intended audience is developers of all levels, since we are development company.
The goal for this story is to build a basis for the “Bitcoin Puzzle” series, that will provide deeper technical and economical dive into the new world of cryptocurrencies and ways they can change our lives.
But for now, let’s start building Bitcoin!
Hash Functions
One of the very basic block to build Bitcoin is a “hash function”.
The main purpose of hash function (according to Wikipedia) is to map an arbitrary size data to a fixed size value. This mapping should follow simple rules:
- Determinism: Same input must produce same output.
- Uniformity: Different inputs should produce different output, that are uniformly spread across function’s range. Since hash function’s range is usually fixed and small, it is impossible to strictly follow this rule, so collisions, when hash(a) = hash(b), are always possible.
- Avalanche effect: Even minor change in input should lead to significant change of output — this rule is not always true, however, hash functions used in Bitcoin follow it.
If you’re interested in counter-example: in “perceptual hash” functions similar inputs produce similar outputs. This property is called “continuity”. - It should be really-really hard to find a collision. Depending on what data is used to search for collision, such property is called:
- “Pre-image resistance” — if you know the hash value, it is impossible to calculate message, such that hash(message) = value.
- “Second pre-image resistance” — if you know message, it is impossible to calculate another message, such that hash(message) = hash(another_message).
- “Collision resistance” — it is impossible to find two messages with same hash.
The combination of all these four properties allows us to be quite certain, that nobody can change our data, without also changing its hash. In such case, the hash function is called “cryptographic hash function” and its value is called “digest”.
Homework question: when receiving data (message and its digest), is correct to claim that data is not changed by a third party, if cryptographic_hash(data.message) equals data.digest?
Asymmetric Cryptography
Nowadays, everyone has heard of public/private keys and algorithms like RSA (named after surnames of authors Rivest, Shamir, Adleman) or ECC (Elliptic Curve Cryptography). Those are also used in Bitcoin and we will now describe ideas of asymmetric encryption and way it is implemented.
The key idea under asymmetric encryption is, that one key is used to encrypt message and only its’ sibling key from the pair can be used to decrypt. Usually, you keep one of keys safe — that’s private key. The other one is shared — public key. In case someone wants to securely send you a message, your public key is used to encrypt the message, and only you can decrypt it. Cool, right?
Here is a complex image that does not really help to understand details of RSA, but I will explain:
In the image above, it is assumed that “HELLO” is translated in our computer as number “2”. The public key is a pair of numbers (5, 14) and the encrypt function is (X⁵ mod 14). The private key is (11, 14). Now, after encryption, source message becomes “4” and, after decryption, it is back “2”. You can check this with any other number (less than 14), e.g. (11⁵ mod 14) = 9 and (9¹¹ mod 14) = 11, decrypted back. Note: in real life the all the numbers (5, 11, 14) are calculated using a pair of enormously large primes and are even bigger, than those primes.
Most of asymmetric encryption algorithms are based on trapdoor functions. These are functions, which are:
- Easy to calculate forward, e.g. 2⁵ mod 14 = 4.
- Hard to calculate back, e.g. hard to find X, such that X⁵ mod 14 = 4.
- Easy to calculate back, if you know some additional info, called “trapdoor” and equal to 11 in our case. So, to find X, such that X⁵ mod 14 = 4 we use formula X = 4¹¹ mod 14 = 2.
Elliptic Curve Cryptography
The key difference between RSA and ECC is the trapdoor function used, in RSA it is (x^a mod b), while ECC is more complex. Here is one more image:
The function (red) is an elliptic curve: y^2 = x^3 + ax + b.
The black dot, moving around the curve is our “trapdoor function value”, that is calculated forward. Each function step is drawing a line from point “A” and projecting new point of curve intersection to another half of the curve (up or down). It turns out, that given many steps, it is very hard to find the starting point, so this function is hard to calculate back. But, there is also a trapdoor possible, which allows to find the starting point easily (trapdoor explanation is too heavy to explain here).
How private and public keys are used
Using someone’s public key, you can securely message someone. But, since it all is based on functions, you could also use private key to encrypt something.
Homework question: what is the point of sending private-key-encrypted message to someone, given that anyone could intercept and decipher it, using your public key?
See answer just below!
When private key is used to encrypt something, it is quite obvious, that anyone can decrypt it. But this situation gives one good benefit: it is you and only you, who could encrypt the message in such way, that your public key decrypts it. It means, that if you share your message along with its encrypted version, then anyone can check the authenticity of the message, by comparing deciphered message value to publicly shared one. This is how digital signatures work. And, by the way, in real-world only hash of message is encrypted.
Asymmetric cryptography and digital signatures are two major building blocks of Bitcoin.
Blockchain
The blockchain is the most popular, yet by far the simplest concept , used in Bitcoin:
Blockchain is just a data structure, that usually implies following properties:
- Can keep anything in “data” field (there are limitations in real life).
- Hash of previous block is part of current block hash, just like all other fields. And they use cryptographic hash function here.
- Resistant to modifications, since all chain of hashes after updated block will change.
- Distributed and has consensus algorithm (this will be described later).
I say “usually implies”, since blockchain is not a well-defined data-structure or concept, like a queue or a tree. That is why there’s no exact definition. Some people might always think that “blockchain is distributed”, while others treat it more just like a linked-list.
This is just as simple as above, there is really nothing special in this idea, besides its impressive use in Bitcoin and other cryptos.
Blockchain is a core concept of Bitcoin. We have now discussed all the building blocks of Bitcoin, now it is time to dive into putting all the parts of the puzzle together. See you in the next part!
I am Rustem Mustafin, PM at Akvelon and a fan of IT and management worlds and a developer with 10+ years of experience. Feel free to contact me on twitter @rulikkk, or just leave a comment here. Thanks for reading!
