Homework on Hash Functions - Questions

Blockchain and Bitcoin 101
#41
  1. a hashing function is a one-way function that takes in any text-number-data as input and returns a number of fixed length
  2. hashing is used in bitcoin for mining, as proof of work (=miners need to find a hash result with a specific parameter) and in each new block the hash of the previous block is used as part of the input to ensure that the chain can’t be easily overwritten
  3. collision resistance in a hash function means that it needs to have a very low probability that any two random inputs can generate the same hash output
#42
  1. hash function is basically a unique code of the command in the program
  2. In bitcoin it is used to hash the transaction data
  3. it means that is hard to find same inputs that hashes same outputs
#43

*Hash Function is the protocol layer between input and output
*It’s used to generate input to output, which also means that you can never go back to input, For example, when you are logging in to your Facebook account, you are using these mathematical functions to safeguard your password. Another characteristic of one-way functions is that if you slightly change the input, the output is completely changed.

For example:

  • hash(“The Money Mongers rocks !! “) = 66925f1da83c54354da73d81e013974d

  • hash(“The Money Mongers rocks !!! “) = c8de96b4cf781a6373766c668ceac0f0

  • hash(“The Money Mongers rocks !!! “) = 9ea367cea6a2cc4a6f5a1d9a334d0d9e

  • Every hash function with more inputs than outputs will necessarily have collisions.

#44

Hash functions are a means of outputting very large numbers that are derived from the input. The process is irreversible so that the input can’t be guessed from the output.

This is how I understand it: The data in a block is added to a hash of the previous block plus a nonce (unique number which is a hash that is difficult but not impossible to derive) and then this is all hashed to create part of the next block. hashes are also pointers to the previous blocks.

Collision resistance is where a hash output is the same for two different inputs. This creates a problem where the input data can be swapped out.

#45

Question 1

A hash function takes an input of any length and returns an output (the hash value) of a fixed length. In other words, whatever length the input is, its hash will always be the same length. Hash functions are used in cryptography (cryptographic hash functions) where they must have the following properties to ensure efficiency, and security against attack:

(i) The same input must always generate the exact same hash value (deterministic).

(ii) It should be very quick and easy to generate the hash value from the input. However, they must be one-way functions: finding the original input from the hash value should be almost impossible (pre-image resistance).

(iii) It should be almost impossible to generate the exact same hash value from two different inputs (collision resistant). Taken together, the deterministic and collision resistant nature of a cryptographic hash function enables it to generate unique hash values from unique inputs i.e. digital fingerprints, which can be used for unique identification, authentication, and validation purposes. The fact that the number of possible input strings is theoretically limitless (they can be of any length), whereas the number of possible hash values that can be generated is finite, means that collisions are theoretically possible. However, as long as the number of bits in the hash value is large enough, the birthday paradox equation provides certainty that, theoretically, collisions will be highly improbable.

(iv) A very small change to the input should generate a very large change in the hash. In other words, very similar inputs should generate two very different hash values.

Cryptographic hash functions are used in different areas of information security e.g. password encryption, authentication of files and messages, checking for tampering or data corruption using checksum validation, blockchain and cryptocurrencies.

Question 2

In Bitcoin, the cryptographic hash function SHA-256 is used in mining, to create Merkle trees, and to generate new addresses.

Bitcoin mining

In Bitcoin mining SHA-256 is used in the proof-of-work algorithm, which is essentially a very difficult puzzle miners have to solve in order to successfully add new blocks to the blockchain. Solving this puzzle, and then having the ‘solution’ confirmed by the whole network, proves that the work has been done according to the protocol, and it also generates new coins which are awarded to the successful miner, together with the transaction fees. This reward mechanism incentivises the miners to continue running the mining algorithm (which requires a large investment in time and resources) and also creates new coins. Because the output hash value of a cryptographic hash function can be generated quickly and easily from the input, newly mined blocks can be quickly and easily verified by the rest of the network by simply running the same algorithm once on the copies they receive.

The proof-of-work algorithm generates a single 64-character hexadecimal (256-bit) hash value by running SHA-256 once on all of the data contained in the candidate block’s header, including:

  • the hash value of the previous block (i.e. the ‘winning’ hash value that successfully mined that block);
  • a single hash value generated from all the as-yet-unconfirmed transactions;
  • the difficulty target;
  • the nonce (a value generated randomly by the miner);
  • a counter.

The resulting hash value is compared with the difficulty target, which is also expressed as a 64-character hexadecimal value, and begins with a set number of zeros depending on the difficulty level. To solve the puzzle, the resulting hash value must be less than or equal to the difficulty target value. This is likely to take an incredibly large number of attempts. On each attempt the above algorithm is repeated. On each iteration, in order to generate a different result, both the counter and the nonce increment.

Including the hash value of the previous block in each subsequent block is what links the blocks together in a blockchain. It is also key to ensuring the security and immutability of the transaction data stored in the blockchain. If a block is hacked and even the tiniest change made to any of its transactions, this will invalidate that block and all subsequent blocks. This is because the new hash value generated by the algorithm will not only change in the compromised block, but it will also change the hash pointer in the next block. As the hash pointer is included in each block’s algorithm input, any change in the hash pointer will also change that block’s output hash value. And so there is a knock-on effect all the way up the blockchain. This copy of the blockchain with the compromised block will be shorter than the confirmed blockchain, which all the other nodes have a copy of, meaning that it won’t be accepted by the rest of the network.

All of the unconfirmed transactions included in a candidate block’s body are first individually hashed using SHA-256. Each resulting hash value is then paired with the one adjacent to it, and then each of these pairs is hashed using SHA-256 again, creating one parent hash for each pair. This ‘pairing-then-hashing’ process is repeated until only one hash value remains. The resulting formation is called a Merkle tree: the original individual transactions are the leaves (leaf nodes), and the single resulting hash value is the root (Merkle root). This Merkle root hash, the end result of a series of stages, each running SHA-256 hash functions, is what is included in the block header, together with the other data items mentioned above, and passed through another SHA-256 hash function as part of the proof-of-work algorithm (as described above). By using SHA-256 to create a Merkle tree and a single Merkle root hash from a very large number of individual transactions within a single block, transaction data is stored more securely on the blockchain, and tracing and verifying individual transactions is made quicker due to their more efficient organisation.

Generating new Bitcoin addresses

SHA-256 is one of the hash functions used to generate new Bitcoin addresses from a user’s public key. This increases security of transactions by allowing a different address to be used for each new transaction.

Question 3
(see Question 1, property (iii), for an explanation of collision resistant)

4 Likes
#46

  1. Hash functions are functions that receive an input and gives an unique output with something called Fingerprint(ID) witch is used as identification of the input.
    Its a one way function witch means that its impossible to go from an output to a input.

  2. Some examples of the usage of Hash functions in crypto currencies are the creation of Public Keys and Private Keys and the crypto hashing of transactions.

  3. A collusion resistant hash function means that one hash built from an input “should” never be equal to other hash built from another input.

#47

  1. A hash function is a one-way function in that an input can not be determined by the output

  2. Hash functions are used in crypto to help organize the information generated by transactions???

  3. Hash functions need to be collision resistant, otherwise it would allow an attacker to substitute a “signature” of lesser value while still producing the same output, which the receiver of that value would have no way of knowing.

#48

1 - Functions where each unique input gives a unique output/fingerprint. It’s a one way function (input of any size into output of fixed size).

2 - In the bitcoin protocol, hash functions are part of the block hashing algorithm which is used to write new transactions into the blockchain through the mining process.

3 - A hash function is collision resistant if it is very difficult to find two inputs that hash to the same output.

#49

  1. A hash function is an algorithm that takes any kind of input data and calculates it into an output data of a fixed number of hexadecimal characters, where it’s impossible to guess the input of the data by trying to guess the output data. If any single point of the input data is changed, the complete hash of the output data becomes different, ensuring a temper proof way of securing data.

  2. Hash functions are used when connecting the blocks of data in the bitcoin network. If anyone tries to change the data of a block, it automatically changes the complete hash of all the previous blocks. This will be rejected by the miners why are running the complete blockchain on their machines.

  3. By collision resistance it’s meant that a hash function has to be very intricate and difficult in order to make sure that there is almost no possibility to guest the input date when looking at the output data. This way it’s not impossible, but extremely difficult to break the hash function and find out the input data

#50
  1. one way function
  2. the blockchain uses hash functions by building each block based on the previous block. so that if someone tried to “cheat” a block, it would break all the previous blocks and not be accepted by the consensus network.
  3. this means that no 2 inputs should produce the same output
#51

  1. Hash functions are ways to take a piece of data and create an output that is totally unique to that data. The data structure is “shuffled” in a way that makes it impossible to guess the original input or usefully compare it to any other output.

  2. The blockchain containing all the transactions throughout history contains hashes of all those transactions, also combining hashes to create further hashes makes up what is a Merkle Tree. Any alteration to the data in a block changes the data in the previous block and will be rejected by the Network. This is what makes consensus simple to achieve.

  3. Collision is where the hash of two different sets of data are the same. Collision resistance means making this event unlikely. If there is a lot of collision it means that the Network has to decide which data to accept between two sets of data with the same hash output. The more collisions the busier the Network, and less efficient the process. This would be bad for everyone involved.

1 Like
#52

An hash function is a cryptographic formula [ like sha256 ] with an unique output for every input which cannot be reversed.

#53

Hash functions are used to create public keys for example and to validate a new block ( PoW by miners - solving a cryptographic puzzle )

#54

It is highly unlikely to get the same output from two different inputs.

#55

  1. a hash function is a one way function which creates from an individual input string/number an output string/number with a fix length. The slightest change in the input leads to a massive change in the output

  2. Hash Funktion are used to create a bitcoin address from the private key and is used in Mining to create block hashes

  3. this means that there never exist a second input which leads to the same output. So the output always is unique

#56
  1. A function which gives a unique output for every single input.
  2. Hash functions produce a Merkle tree of all transactions, produce a block hash that links one block to another with a pointer, produce a hash of the nonce and the block that can be checked with the difficulty rate.
  3. No two inputs may create the same output.
#57
  1. hash function is a mathematical algorithm that takes an input and turns it into an output. There arte many types of hash algorithms example md5 (not used) and sha 256 (the one used in bitcoin).
  2. The hash function is used to hash the block header with SHA 256 which in turn, as specified above, produces an output. This output is stamped in the block and will serve as the unique identifier of this block. this data / information is used in mining and adding the block to the network.
  3. Collision resistant means that each hash is unique. 2 different inputs can never generate the same hash.
#58

  1. A Hash function is a digital fingerprint that only works one way. If you for example type something and later hashes it, it will give you a hexagon (If we talking SHA256) representation of the typing.

  2. Hashing is used when transactions are made on the blocks. Because the transactions aren’t hashed directly, a block of 100 transactions take the same time as a block with one transaction. Hashing is also used when creating wallets.

  3. If anyone is able to reverse the SHA256, that will mean that bitcoin is basicly broken. But still, a SHA256 hash function has never been broken that’s why it is the most popular cryptographic hash function of today.

#59
  1. Describe hash functions with your own words. Hash functions are one way functions that produce a single fingerprint.
  2. How are hash functions used in cryptocurrencies like bitcoin? Hash functions are used in cryptocurrencies to create a difficult equation that when solved creates new bitcoin.
  3. What does it mean when we say that hash functions need to be collision resistant? Collision resistant means that it would be difficult or hard to find two inputs that will produce the same output in a hash function. It would not be realistic to find two messages which produce the same Hash or Message-Digest. If it is not collision resistant, it would be considered weak.
#60
  • Describe hash functions with your own words
  • algorithmic calculation - an unique input with an unique output - calculation can not be reversed.
  • How are hash functions used in cryptocurrencies like bitcoin? (Try to research this on your own, we will cover this later in the course but challenge yourself and see if you can find information on this already now).
  • hash functions are used to create public keys ( from private keys ) for example or are used by miners to create and identify new blocks.
  • What does it mean when we say that hash functions need to be collision resistant? (We didn’t use the term “collision resistant” in the lecture, but you will easily find this on Google, we add this question intentionally to make you research information on your own, that’s how you learn best).
    An unique input in a hash function creates an unique output. It is almost mathematically impossible to get the same output from another input.