{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Hash functions"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## hash and sha256"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Computer scientists have invented the hash functions. An hash function is a function which, when applied to a string, it gives you a value which is a sort of fingerprint of the string. If you just change the string a little bit, the hash function gives you a very different result. It is extremely rare that two strings have the same hash result.\n",
"\n",
"There exist several hash functions. The easy ones, such as the hash(< string >) function in Python, give you an integer result. However, with an integer result it can happen that two strings have the same result (one probability out of some billions). More complex hash function are more interesting because they give you a long alphanumeric string, such as the sha256 sha256(< string >).hexdigest() contained in Python library hashlib.\n",
" \n",
"Please note that the result of hash functions is never random, you get always the same result if you apply it to the same string."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"scrolled": true
},
"outputs": [],
"source": [
"print(hash(\"Satoshi\"))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from hashlib import sha256 # do not forget this, or you won't have sha256 available\n",
"\n",
"print(sha256(\"Satoshi\".encode('utf-8')).hexdigest()) "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## First usage: fingerprint of large data"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You can use the hash functions as a fingerprint of large data. If you have a large amount of data and your scope is not keeping these data completely into your computer memory but simply keeping track of whether you have already examined them or not, you can store hash functions of those data. Whenever you are wondering whether you have already examined a set of data, you calculate its hash and check whether you have it.\n",
"\n",
"One of the reasons why you do not want to keep your original data could be because they are large and use a lot of space, while another one could be because of privacy regulations (imagine if you had medical data, you do not want to keep the name and surename of the patient)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Example"
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {},
"outputs": [],
"source": [
"def veryComplexFunction(S):\n",
" # we do not care about what this function really does (it is used only as an example), but we care about\n",
" # the fact that it is very complex! N=len(s): complexity is 3*N^3 str joins\n",
" p=\"\"\n",
" for x in S:\n",
" for y in S:\n",
" for z in S:\n",
" p=p+x+y+z\n",
" return(p[int(len(p)/3):(int(len(p)/3)+9)]) "
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {},
"outputs": [],
"source": [
"# test the function on these examples and you will see that it is really slow!\n",
"\n",
"text1=\"imagine this is a large text, such as a web page\"\n",
"text2=\"imagine this is another large text, such as another web page\"\n",
"text3=\"imagine this is a third large text, not so large\"\n",
"text4=\"this is a large text that you must check whether you have it already\"\n",
"\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Your task is to apply veryComplexFunction to this list of texts without repeating the calculations for text that you have already examined and at the same time without storing the original text."
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {},
"outputs": [],
"source": [
"L=[text1,text2,text1,text3,text4,text1,text1,text3,text4,text1,text1,text3,text4,text1,text1,text3,text4,text1]\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Second usage: keeping passwords secret"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Have you ever wondered whether your bank knows the PIN of your ATM card (it: bancomat, de: Karte)? It must know it, otherwise how could it check whether you have digited it correctly?\n",
"\n",
"Have you ever asked yourself why some websites, when you click on \"I forgot my password\" send you your password, while others don't and send you a link to set up a new password? It is because some website store your password \"clear\" (as you have written it), a strategy which is very dangerous. Other website, or your bank for the ATM card's PIN, do not store that value, they do not have any idea of what it is. But in this case, how can they know whether my PIN/password is correct when I digit it?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Your ATM card has a number, let's say 1137862. The bank creates a PIN randomly and then calculates the hash of the ATM card number together with the PIN."
]
},
{
"cell_type": "code",
"execution_count": 69,
"metadata": {},
"outputs": [],
"source": [
"from hashlib import sha256\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This number is then stored inside the bank's server. Using this number and the card's number it is **impossible** to deduce the PIN, as the hash functions are very complicated functions! In this way not even the bank knows your PIN and not even criminal employees or hackers can find it."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Whenever you slide in your card into the ATM and digit your PIN, the ATM calculates your hash and asks the bank's server whether that hash is correct."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Third usage: proving the existence"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This part can be asked in the theoretical part of the exam about cryptocurrencies and blockchain technology."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Imagine you have written a book and you are submitting it to the editors, or whatever other good idea/product which can be easily copied electronically. You face the risk of an editor rejecting it and then publishing it with another author's name. There are old-tech ways to protect yourself: you may give a copy to an official authority (e.g. patent office for an invention or in Italy giving a printed copy of your book to a notary) but this is usually expensive and not fast in case you produce a lot of these products.\n",
"\n",
"It is more convienent to calculate the hash function of your product (you can hash a book without any problems, but you can hash even a picture or a video just converting the file content to a string) and put it into a public place, which could be an announcment on the local newspaper if you live in the 19th century or a crypto blockchain in the 21st. The reason why using an hash function is clear: publishing an entire book or picture on a newspaper/blockchain is very expensive (just to give you an idea 1 MB on Ethereum blockchain costs 4000 dollars in transaction fees). Publishing the hash you have the proof that the hash-ed item existed at that time because you need to have the item to create that hash fingerprint and thus you have the proof that you had the item at that date.\n",
"\n",
"How to write hash fingerprints on crypto blockchain? Almost every crypto blockchain accepts a very short description for each transaction and you can make a transaction to yourself for a very small amount and write the hash fingerprint in the description. \n",
"
I have seen a conference of a water company in Sardinia that was taking pictures of the water meters of their customers. To prove that they had taken the picture before a certain date, they calculate the hash of each picture, put all the hash fingerprints together, calculate the hash of this sequence of hash fingerprints and write the final result on the Bitcoin blockchain. For a fee of maximum 10 euros they have a legal proof that those pictures were takes before a certain date."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Fourth usage: mining bitcoins"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This part can be asked in the theoretical part of the exam about cryptocurrencies and blockchain technology."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Do you remember the solution invented by Satoshi Nakamoto to decide who shall add the next block to the Bitcoin blockchain? The first one who solves a \"difficult mathematical puzzle that can be solved only by trial and error\". Well, it's now time to tell you what is that puzzle. We will just have an idea of it, some technicalities will be omitted and simplified.\n",
"\n",
"That puzzle is the following: take the hash fingerprint of the previous block (this is only to prevent somebody from starting to solve the puzzle in advance before the previous block is added), concatenate it with a file containing all the transactions that you want to confirm, concatenate it with whatever you want and try to get a hash fingerprint which starts with 8 zeros. You can really add whatever you want and try and retry until you manage to get it.\n",
"\n",
"In its very first block, Satoshi managed to find an hash fingerprint with 10 zeros!!! 000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For example, when I am writing this file, the last block which was mined was block 605377. I go on www.blockchain.info/explorer and see the hash of the previous block 605376. I get three transactions from block 605377 (getting manually all of them would require too much manual work, obviously) and put them into a list.\n",
"\n",
"Then, following Satoshi's rule, I calculate the hash of the previous block's hash, the transactions and some characters (we shall use only numbers as they are simpler) to see whether I am lucky and get a hash with some zeros at the beginning."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Beware that we haven't been so lucky to find the number randomly at first attempt. My computer spend some hours of attempts to find it..."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The amount of zeros that you must get in your hash fingerprint is the **mining difficulty** and it is determined automatically every two weeks depending on how many computers are in the network. Currently, as you can see from the hash of the previous block, is 19 zeros, a really huge amount very difficult to get."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.11"
}
},
"nbformat": 4,
"nbformat_minor": 4
}