Note: This is a reading note of chapter 1 in the book *Bitcoin and Cryptocurrency Technology*.

In this post we will talk about

- Hash function and its properties.
- Hash pointer and related date structure
- Digital signature

#### Hash Function

The following three properties of a hash function is extremely useful in cryptocurrency design:

- Collision resistance: It should be rare fro two different data have the same hash value.
- Hiding: It should be impossible to guess the data from its hash value.
- Puzzle friendliness: Given equation \(H(k||x) = y\), there is no shortcut to find \(x\) and the solver need to iterate all possible values.

The first two properties, collision resistance and hiding, allow us to make a commitment to a message/value.

Fig: Commit

Every time we commit to a value, it is important to choose a new random value nonce. In cryptography, the term nonce is used to refer to a value that can be only be used once.

The third property puzzle friendliness is useful for mining.

#### Hash Pointer

The idea of hash pointer is simple: in addition to an ordinary pointer, we also save the hash value of the content. In this way we can detect changes in the content and be confident that the data is not modified. When hash pointers are put together to form a list (e.g. BlockChain) or a tree (e.g. Merkle Tree), they become a powerful tool. Recall that hash value can be considered as a summary or a compressed version of the content being hashed. Thanks to the recursive structure, the last pointer on a given path contains all information of that path. This property makes data validation very fast. Instead compare two lists (or blockchains) node-by-node, it suffice to compare the hash values in the hash pointers that point to the blockchains.

Fig: Blockchain Structure

Merkle Tree allows us to check the membership or non-membership of an element in O(log N) time, where N is the number of elements. The idea is to use the information of the path between root and the element node. The information (e.g. hash values) of the path is a summary of information of the whole tree.

#### Digital Signature

Digital Signature consists of threes components

- key generation
- signing a message
- verification

A key generator generates two keys: (1) private key and (2) public key. The algorithm used in Bitcoin is *Elliptic Curve Digital Signature Algorithm*(ECDSA). As the name suggests, private key is supposed to be private and it cannot be shared with other people. If the private key is known to other people, they can then produce faked signature. On the contrary, public key can be shared. In reality, public key is used as an ID and the "address" in Bitcoin world is actually the hash of the public key.

A private key is needed to sign a message and in order to verify a signature we need the message, the signature and the public key. To summarize, we have the following methods

- generatePrivateAndPublicKey(randomSource)
- sign(message, privateKey)
- verify(message, signature, publicKey)

----- END -----

©2019 - 2021 all rights reserved