Previously, we have analyzed how hash functions work. This was necessary to understand another cryptographic primitive called Digital Signature. A digital signature is supposed to be the digital analog to a handwritten signature on paper and we desire two properties that correspond to the analogy.
First of all, we require that only you can make your signature, but everyone is able to verify that it's valid; this property is called verifiability and is a basic requirement for signatures to be useful at all. More technically, we want that when one signs a message with his secret key sk, others should be able to validate correctly the signature with the corresponding public key pk.
Then, "we want the signature to be tied to a particular document so that the signature cannot be used to indicate your agreement or endorsement of a different document" . We want also that it is computationally infeasible to forge signatures for an adversary that knows your public key; this property is called unforgeability. That is, an adversary who knows your public key and gets to see your signatures on some other messages can't forge your signature on some message for which he has not seen your signature.
This property is generally formalized in terms of a game that we play with an adversary, quite common practice in cryptographic security proofs. The scheme is represented below (taken from ). Note that generateKeys and sign can be randomized algorithms, because the aim is to generate different keys for different people. Verify, on the other hand, will always be deterministic.
In the unforgeability game, there is an adversary who claims that he can forge signatures and a challenger that will test this claim.
Therefore the challenger generates a secret signing key and a corresponding public verification key, giving the adversary only the public information. Because the challenger knows the secret key, he can always make signatures and demonstrate the integrity of a document. Instead, the adversary can only try random guesses and see the response of the verify function of the signature he propose, that can only be true or false.
If it successfully verifies, the attacker wins the game.
"Intuitively, the setup of this game matches real-world conditions and we say that the signature scheme is unforgeable if and only if, no matter what algorithm the adversary is using, his chance of successfully forging a message is extremely small - so small that we can assume it will never happen in practice ".
It follows that to fulfill these properties, we need a good source of randomness, otherwise bad randomness will make our secure algorithm insecure. Moreover, we need mathematical functions that are practically irreversible, meaning that they are easy to calculate in one direction and infeasible to calculate in the opposite direction. Fortunately, the mathematical tools we have, enable the creation of digital secrets and unforgeable digital signatures through public-key cryptography.
In particular, the Bitcoin protocol uses a specific digital signature scheme called the Elliptic Curve Digital Signature Algorithm (ECDSA), which is another US government standard believed to be extremely secure.
We start picking from the space of 2^256 bits, the private key sk in the form of a randomly generated number shown in the hexadecimal format of the type (256 binary digits shown as 64 hexadecimal digits, each 4 bits):
Then, we multiply this number by a predetermined point on the elliptic curve, called the generator point G, to produce another point somewhere else on the curve, which is the corresponding public key pk:
pk = sk * G
Without going into other mathematical details, just know that the relationship between sk and pk is fixed, but can only be calculated in one direction, from sk to pk. Therefore the mathematical relationship between the public and the private key, allows the private key to be used to generate signatures on messages. This is because the reverse operation, known as "finding the discrete logarithm" - that is calculating sk if you know pk - is as difficult as trying all possible values of the private key, i.e. a brute-force search .
The creation of a public and private keys works as follows:
After obtaining the public key from the elliptic curve, we compute in sequence the SHA256 hash, the RIPEMD160 hash of the result, a checksum to verify that the pair of keys contains valid characters and finally we apply a function called BASE58 that simplifies the string of data producing a 20-byte number (160-bit) similar to:
This string of letters and numbers is what we can call a public address, which appears most commonly in a transaction as the "recipient" of the funds.
So, finally, we have a pair of keys tied cryptographically, where we can receive funds publicly and we can commit ourselves into a transaction by demonstrating our property of the private keys.
Ownership and control over the private key is the root of user control over all funds associated with the corresponding coin address. This also means that the secret key, as the name suggests, has to be put in a safe place because, if one knows it, he can easily sign your message.
The private key is used to create signatures that are required to spend coins by proving ownership of funds used in a transaction. That's why a bitcoin public address can be shared with anyone without revealing the user's private key.
We can further use another nice trick that goes along with digital signatures. "The idea is to take a public key from a digital signature scheme, and equate that to an identity of a person or an actor in a system ". That is, if you see a message with a signature that verifies correctly under the public key pk, you can literally think of this public key as an actor who can make statements by signing with the secret key sk those statements.
From this point of view, the public key is an identity and in order for someone to speak for the identity pk, he must know the corresponding secret key, sk .
Furthermore, because by default the public key looks completely random, nobody will be able to uncover the real-world identity by examining pk; we have obtained unforgeability. And because the secret key is generated from a very large set of numbers, you can also generate a fresh identity that looks random whenever you want, by simply creating a new pair via the generateKeys operation in our digital signature scheme.
"This brings us to the idea of decentralized identity management, where rather than having a central authority that you have to go to in order to register as a user in a system, you can register as a user all by yourself ".
However, addresses are not anonymous but pseudonymous, because even if you don't need to explicitly register your identity, your behavior makes a series of statements, that could be connected to your real identity. As we will see, this is one of the concerns about privacy that Bitcoin should take in account for the next future.
Another practical concern for the blockchain is the message size. This is because there is a limit on the message that can be signed and real schemes operate on bit strings of limited length. Fortunately, there is an easy way to overcome this issue: one can sign the hash of the message, rather than the message itself.
When "we use a cryptographic hash function with a 256-bit output, then we can effectively sign a message of any length as long as our signature scheme can sign 256-bit messages ". This will be very useful in the Blockchain architecture, because having hashed a single hash pointer, the signature allows to cover not just the hash pointer itself, but everything the chain of hash points to.
Hash pointers and Data structures
Now that we know the basics of addresses and digital signatures, we can discuss about hash pointers and their applications in the Bitcoin Blockchain. A hash pointer is a pointer to the place where some information is stored. This gives you a way to retrieve the information but also gives you a way to verify that information has not changed. They can be used to build all kinds of structures.
So, firstly we can build a linear structure, linked through hash pointers and we are going to call this structure Blockchain.
"In this way, each block has data as well as a pointer to the previous block in the list; blocks not only tell us where the value of the previous block was, but it also contains a digest of that value that allows us to verify that the value hasn't changed ". In other words, we say that the blockchain is a tamper-evident log, when the data structure allows to store securely a bunch of data and to append other data onto the end of the log.
The benefit of this is that, "if the adversary wants to tamper with data anywhere in the entire chain, in order to keep the story consistent, he's going to have to tamper with the hash pointers all the way back to the beginning ".
This means that by just remembering this single hash pointer, we've essentially remembered a tamper-evident hash of the entire list. So we can build a blockchain like this containing as many blocks as we want, going back to some special block towards the beginning of the list, until we reach the first block, which is called the genesis block.
We can apply a similar logic but with a more sophisticated binary structure that branches down by adding new data, the Merkle-Tree. In this structure, we can group blocks containing data - the leaves - into pairs of two, and then for each pair, we build a data structure that has two hash pointers, one to each of these blocks. "These data structures make the next level up of the tree, until it is reached a single block - the root of the tree ".
The Merkle-tree structure is useful because it stores the data in a more efficient way; now, we have to remember just the hash pointer at the head of the tree.
If an adversary tampers with some data at the low levels of the tree, just like in the case of the blockchain he will cause all the hash pointers of "the level up to not match, and even if he continues to tamper with this block, the change will eventually propagate to the top of the tree where he won't be able to tamper with the hash pointer that we've stored ".
It follows that Merkle-trees has a nice feature to proof efficiently the membership. Everyone can prove that a certain data block is a member of the Merkle-tree, showing only the path from this data block to the root of the tree, verifying the hash pointers all the way up, while ignoring the other branches.
And so "even if the Merkle tree contains a very large number of blocks, we can still prove membership in a relatively short time ". One limitation of the Merkle-trees is that if there are cycles on the data structure, it is not possible to make all the hashes to match up, but this does not affect the functioning of Bitcoin and it is in line with the protocol.
We can further combine these two data structures to benefit their different qualities. The optimization relies on the fact that organizing data in this way makes the system much faster in verifying data and makes the chain shorter as long as data is gathered into blocks.
In this way, each block has a block header, a hash pointer to some transaction data, and a hash pointer to the previous block in the sequence. Information is included in that block and arranged into the tree structure. Hence, to prove that a transaction is included in a specific block, we can provide a secure path through the tree thanks to cryptographic functions.
This is because this mechanism gives us an append-only ledger, a data structure that we can only write to, and once data is written, it's there until the system is shut down. And of course, this data can be used to represent a currency and its transactions.
When a data structure achieves the quality of tamper-evident log, as we will see in more detail, it allows different applications in several interesting fields. Then, the blockchain can be represented in this form, that is the current form of the blockchain of Bitcoin:
- Cryptocurrencies for friends who don't care about cryptocurrencies
- 1 - Bitcoin and money
- 2 - The history of money
- 3 - Characteristics of money
- 4 - A glimpse into the Austrian school of Economics
- 5 - The history behind Bitcoin and cryptocurrencies
- 6 - Understanding cryptographic hash functions
- 7 - The basic mechanism of digital signatures, addresses and the Blockchain