CP-20200206

Cryptography Primitives Intermediate February 6, 2020

Back to All Tasks

Problem Statement

Implement a simple proof-of-work (PoW) algorithm in Python. The goal is to find a nonce that, when concatenated with a given string and then hashed using SHA-256, produces a hash starting with at least three leading zeros. Your function should take the input string as an argument and return the nonce along with the resulting hash. Remember, the PoW concept is crucial in blockchain technology for securing transactions without a central authority.

Concepts

  • Hash Functions
  • Collision Resistance
  • Nonce

Constraints

  • Use Python's hashlib library for hashing
  • The nonce must be a positive integer
  • Your solution must efficiently find a valid nonce

Security Notes

  • Leading zeros in a hash are computationally expensive to achieve, which makes PoW a good mechanism for securing blockchain networks against spam and attacks.
  • Ensure that your implementation is not vulnerable to brute-force attacks by setting an appropriate difficulty level (number of leading zeros).

Solutions

Php Solution

function findNonce($inputString) {
    // Import the hash function from PHP's hash extension
    $nonce = 0;
    // Start with nonce 0
    $difficulty = 3; // Number of leading zeros required
    $targetHashPrefix = str_repeat("0", $difficulty);
    // Define the target prefix for the hash (e.g., '000')
    while (true) {
        // Create a string by concatenating inputString and nonce
        $dataToHash = $inputString . $nonce;
        // Compute the SHA-256 hash of the concatenated string
        $computedHash = hash("sha256", $dataToHash);
        // Check if the computed hash starts with the target prefix
        if (substr($computedHash, 0, $difficulty) === $targetHashPrefix) {
            // If it does, we've found a valid nonce
            return [$nonce, $computedHash];
        }
        // Increment the nonce to try the next possibility
        $nonce++;
    }
}

This PHP function implements a simple proof-of-work (PoW) algorithm. The goal is to find a nonce such that when it is concatenated with a given input string and hashed using SHA-256, the resulting hash starts with a specified number of leading zeros (in this case, three). This mimics the process used in blockchain technologies to validate transactions.

The function `findNonce` takes an `$inputString` as its parameter. It initializes a nonce at 0 and sets a difficulty level which determines how many leading zeros are required in the hash. The target prefix is created by repeating '0' according to the difficulty level.

A while loop runs indefinitely until a valid nonce is found. Inside the loop, the function concatenates the input string with the current nonce value, computes its SHA-256 hash, and checks if this hash starts with the required number of leading zeros. If it does, the function returns an array containing the nonce and the computed hash.

If the hash does not meet the criteria, the nonce is incremented by one, and the process repeats until a valid solution is found. This brute-force approach ensures that finding a suitable nonce requires significant computational effort, which is essential for the security of blockchain networks against spam and malicious attacks.