codingquest
feature image

Spot the forgery

You discover an antique shop that specialises in Earth relics from the 20th and 21st century! Very excited you wander inside!

You see a range of ancient tech such as an early Apple iPod, VR headsets, the first real hoverboards and so on.

The store uses a blockchain to maintain the certificates of authenticity of the antiques. Blockchains are a useful technology invented in the early 21st century and are commonly used to guard against tampering of the historical record stored within the chain.

The blockchain at the store uses the SHA256 hashing algorithm. Modern computers in the year 2222 have no trouble brute forcing this, however, and it seems someone may have tampered with the blockchain data. You get to work verifying the blockchain to ensure you don't accidentally purchase a fake antique!

Each record on this particular blockchain is stored in one line of text, with each field separated by a | character. The records in each block are:

Description of the item|mined number|previous hash|hash for this record

Example

As an example, consider the first item in the block chain

Original iPhone still in box|3595421|0000000000000000000000000000000000000000000000000000000000000000|00000078f97879b26be6baf2adb520b126f84ed10464ed4e9a77b8ed87e07468
  • The description is "Original iPhone still in box".
  • The mined number is 3595421 (more on this later).
  • Given this is the first item, there isn't a previous hash, so 64 zeros are provided.
  • The SHA256 hash for the record.

The hash for the record consists of description|mined number|previous hash. So, in this case, the SHA256 function call may have looked like:

hash = sha256("Original iPhone still in box|3595421|0000000000000000000000000000000000000000000000000000000000000000")

It is important to hash the exact content as a small difference can produce a very different result. Consider that the following two examples:

sha256("Hello, world!")
=> 315f5bdb76d078c43b8ac0064e4a0164612b1fce77c869345bfc94c75894edd3

sha256("Hello, world.")
=> f8c3bf62a9aa3e6fc1619c250e48abe7519373d3edf41be62eb5dc45199af2ef

Moving on...

Consider the second record in the blockchain.

Apollo 11 moon rock|27703084|00000078f97879b26be6baf2adb520b126f84ed10464ed4e9a77b8ed87e07468|00000068a1e823c97e72ff22b0450dc4cfa66495b6ac56266edb0389c2d9a045

Notice the third field is the hash generated by the first record. By including the hash of the previous item into the next is how the entire chain becomes tamper-proof. Make one change in any of the previous items and incorrect hash values will flow through the rest of the chain.

In this case, to calculate the hash, the following function call would have been made.

sha256("Apollo 11 moon rock|27703084|00000078f97879b26be6baf2adb520b126f84ed10464ed4e9a77b8ed87e07468")

What is the mined number?

Did you notice that all of our hashes start with 6 zeros? That is where the mining comes in. Mining involves "work" by way of performing mathematical calculations. In the case of our blockchain it quick to calculate but it is the same concept used by more famous blockchains.

Because a hash number is mathematically generated from its input data, we can experiment with different input values until such time as we find one that happens to create a hash that generates six zeros at the start.

The mined number starts at 0, and increments by 1 continually until the goal is met. In the case of our second example...

sha256("Apollo 11 moon rock|0|00000078f97879b26be6baf2adb520b126f84ed10464ed4e9a77b8ed87e07468")
=> a2d15a7408b702a99c0f96e04edb5ac1f9b51c6744d62eba65d6629fdd384fd1

sha256("Apollo 11 moon rock|1|00000078f97879b26be6baf2adb520b126f84ed10464ed4e9a77b8ed87e07468")
=> 7e780ee3d40748a845ef39fa13ae215f8db9e4a8e284cacbc2475c9583641431

sha256("Apollo 11 moon rock|2|00000078f97879b26be6baf2adb520b126f84ed10464ed4e9a77b8ed87e07468")
=> 9da5f6a94c0c09ee691d4cfa35aa8e1c6d9b233e4f64ba4a90771bb1eb9361ea

sha256("Apollo 11 moon rock|3|00000078f97879b26be6baf2adb520b126f84ed10464ed4e9a77b8ed87e07468")
=> d747567711f5ff534296eed56c28e04bd19b951dfe8580e0c6d20f0379c33689

sha256("Apollo 11 moon rock|4|00000078f97879b26be6baf2adb520b126f84ed10464ed4e9a77b8ed87e07468")
=> 983a76764800619c0e01fe665011eb544c1fb0d8efdd3b0d784e9f0d2f45e8c6

...
keep incrementing until 
...

sha256("Apollo 11 moon rock|27703084|00000078f97879b26be6baf2adb520b126f84ed10464ed4e9a77b8ed87e07468")
=> 00000068a1e823c97e72ff22b0450dc4cfa66495b6ac56266edb0389c2d9a045

The purpose of the mining is prevent someone altering the blockchain and instantly updating all the hashes to match their fraudulent data. Mining takes time, it slows the process down, so that editing an older record and recalculating updated hashes is not feasible (especially if the requirement is larger than just the six zeros we require here).

Your task

Somewhere in the blockchain there is data that has been tampered with.

  1. Find the hash that is broken.
  2. Calculate its correct value.
  3. Calculate the corrected hashes for all subsequent links in the chain. Remember you have to update each record's previous before attempting to calculate its new hash. You will then need to perform mining to find the hash for the record that will start with 6 zeros before you can then move on to the next record.

To assist you in checking that your calculations and mining are producing expected results, it is guaranteed the first five records have not been tampered with.

What is the final hash of the final record?

Input data

Get your puzzle input data

What is the solution?

 

Hint

Learn how to use the SHA256 hashing function for your language of choice: