Notes

Applying Hash Functions... for real Different applications:

1. Comparing data

2. Detecting changes in data

3. Referring to data in a change-sensitive way (very important!)

4. Storing data in a change-sensitive way

5. Causing time-consuming computations

6. Hashing to Compare Data The goal is to compare data without looking at their content. Also, the comparison should be fast and completely independent on the type of data and its size. So here is the idea: just compare hash values. How: if all the hash values are different, then all the data chunks are different as well. It works because hash functions are collision resistant.

7. Hashing to Detect Changes in Data If we can compare, we can also detect changes. We want to be able to say if data which should remain unchanged, has changed at a certain point in time. So we throw a comparison between two hash values belonging to the same chunk of data. If both hash values are identical it implies no change. Once again, detecting changes in data that are supposed to stay unchanged works due to collision resistance of cryptographic hash functions.

8. Having to Refer to Data in a Change-Sensitive Way Comparing and detecting changes are the basics. A more advanced approach is hash references and then ensure the data remain unchanged. To achieve this, we combine the hash value itself associated with stored data with information about where that data is located. The moment there is a change, both information will be no more consistent: the hash reference becomes invalid. Example: a cloakroom ticket is a hash reference to your jacket.

• The physical data is the jacket.
• Add-on information is the place where your jacket has been stored.

Computers use reference addresses to remember where they store things that we told them to store. Hash references refer to data and at the same time they verify the data has not changed since the reference was created. Example: the cloakroom ticket points at an empty cloaca hook.

We use hash references to protect users from retrieving wrong data (i.e. unintentionally or intentionally changed). The whole idea is properly based on the fact that hash values are encrypted: it is very unlikely that different chunks of data have identical hash values.

4. Hashing to Store Data in a Change-Sensitive Way The goal is to extend the reference method to be able to store data through hash values. Cloakroom tickets work in a straightforward way under optimal conditions ... but. Let's play with this:

• We give a jacket and we get a ticket.
• We take the ticket and we put it in the pocket of another jacket.
• We give this second jacket and we get another ticket.
• Imagine to keep going on with this to form a very long list of tickets...

We can do the same with data and form a chain of data. If at any point in time either the data or the hash references are changed all the hash references are broken. But this is the warning that advises us that a change occurred after the initial reference was created. There exist two patterns that can be used to store data in a change-sensitive way:

• The chain
• The tree

Hash Pointers and Data Structures

Definition: a hash pointer is simply a pointer to where some information is stored together with a cryptographic hash of the information. Whereas Ed a regular pointer gives you a way to retrieve the information, a hash pointer also gives you a way to verify that the information hasn't changed.

The Chain Pattern

Here is an example of a blockchain with hash pointers. Each block tells us where the value of the previous block was and a digest of that value which allows us to verify that the value itself hasn't changed. This comes in handy when we know data will arrive step by step.

The Tree Pattern

This structure is called Merkle Tree and was proposed by the computer scientist Ralph Merkle in 1979. It is an important structure because it allows to group distinct pieces of data available at the same time and make them accessible via a single hash value.

5. Causing Time-Consuming Computations So far, we know we can combine, refer and store data securely and efficiently. Here we want to allow computers to challenge other computers with games. This is a fundamental step to understand blockchain which is strongly based on. It's a game, but with certain rules:

• It should not be possible to solve the game based on knowledge or previously stored data.
• Forget about being smart.
• The only way is by brute computational power. How could you open a lock if you don't know the sequence?
• Well, we try all the possible combinations.
• Time consuming!

The process of just trying all the combinations implies no knowledge nor reasoning of any sort. You just put hard work on this task. Hash puzzles (games) are computational games which can be considered as the equivalent of opening a lock.

Authorizing Transactions with Digital Signature We know a bit about cryptography. We know a bit about hash functions, how they work and how we could use them. Now, we need to understand how to rightfully transfer a property from one account to another. In other words, we need an authorization. We obtain authorization through digital signatures. Think about handwritten signatures: through them we state agreement. We accept them because we think they are unique. Now, we transfer this concept tot the digital world of the blockchain. Digital signatures is a crucial concept for the security of individual transactions in a blockchain.

The Importance of Ordering One of the fundamental problem with blockchain is that the order of blocks doesn't always reflect the one of transaction. Recognizing the order in which transactions occurred is key to achieve the same identical results. Changing the order of transaction data implies a change in the aggregation of them. Receiving a payment from a friend seems to be the trivial case.

• I don't care about the order as far as I get the money.
• The logical thing is: money are transferred from my friend's account and then put on mine. What if the two transactions occurred in the opposite order?

Integrity of the Transaction History The history of transactions is really the core of the blockchain. Why? Because history is the way we reconstruct the state of the ownership. We want the history of data to be safe, complete, correct and consistent such that the integrity of the system is maintained. We need a system to validate transaction:

• Formal correctness, implies that the description of a transaction contains all the required data and those data are correctly formatted.
• Semantic correctness, deals with the meaning of a transaction and its scope.
  • Preventing double-spending
• Authorization, implies that every transaction carries all the necessary information to prove that the owner of the account agrees with the transfer.

The Double-Spending Problem The idea: if we spend $1 to buy an apple, we can't use that same $1 to buy an orange. Why? Just because you have to give $1 to the vendor. With digital currencies, or assets, there is no such thing. We can spend the same currency for two or more transactions, in principle. Let's imagine we have a P2P system for managing ownership of real estate. Ledgers is maintained by individual computers so each peers has its own copy. The minute the ownership of a house is transferred from one account to another, all the ledgers must be updated to match the latest version of reality.

Issue: someone who already know the latest info could do something bad to someone else who is not up-to-date.

Example: Frodo is sick and tired of carrying the ring around. So he decides to sell it but before doing it, he hides the ring where no one can spot it. He then goes to one of his fellow hobbits telling him about the ring and closes the deal for a considerable amount of pipeweed. However, Frodo is very smart. He wants more pipeweed so he quickly goes to another hobbit and sells the same ring for another honest amount of pipeweed.

• The first transaction is a transfer of ownership and is documented in one of the ledgers in the system.
• We might have a problem with the second transaction... Hobbits are slow we all know that... (i.e., the system needs time to get updated).
• What if the second hobbit doesn't know about the first transaction? He will approve the deal!
• Frodo would have been able to sell the ring twice.

The term double-spending can be used to refer to different concepts:

• A problem of copying digital goods.
  • Easy: on a computer you can take as many copies as you want.
  • No noticeable limitations.
  • We have seen how digital money can be copied such that it can be used more than once.
  • Digital equivalent to replication bank notes with a copying machine.
  • This violates the core principle of money: an identical piece of money cannot be given to different people at the same time.
  • The ability to copy and spend digital money multiple times decreases value of the money, hence, the double-spending problem.
• A problem that can occur in distributed P2P systems.
  • Transferring (distributing) information to all the nodes requires time.
  • This implies that not all nodes know the latest state of the system.
  • This is a threat which can be exploited who already knows the latest information.
  • As a result, one may be able to transfer ownership more than once, resulting in double-spending.
• A threat that can violate the integrity in purely distributed P2P systems.
  • Distributed systems are not restricted to just the management of ownership.
  • One other problem is to maintain data consistency in such systems.
  • Data consistency is one of the aspect of integrity.
  • We can argue that the double-spending problem is an example of violated system integrity.