me.edwards.des.util
Class HashUtil

java.lang.Object
  me.edwards.des.util.HashUtil

public class HashUtil
extends java.lang.Object

Utility class for generating and validating hashes. Also provides utility methods for manipulating and formatting hashes. Handles generation of the Proof of Work for Blocks.

SHA-256 is the hashing method used by this class, and all hashes (except for Merkle Root hashes) are squared, also known as SHA-256^2, or SHA-256(SHA-256(DATA)). This is meant to provide added security against a pre-image attack.

Created on: Oct 16, 2015 at 5:30:31 PM

Author:

Matthew Edwards

Field Summary

private static double	hashEst
private static java.util.logging.Logger	logger

Constructor Summary

HashUtil()

Method Summary

static int	estimateTime(double difficulty) Returns the estimated time (in seconds) to generate a proof of work.
static java.lang.String	generateBlockHash(byte[] bytes, int proof) Generates a Block hash from a byte array representing a Block Header.
static java.lang.String	generateHash(byte[] bytes) Generates a hash from given data as an array of bytes.
static java.lang.String	generateLeadingZeros(java.lang.String hash) Formats a hash string with the correct number of leading zeros (64 digits by default).
static java.lang.String	generateLeadingZeros(java.lang.String hash, int digits) Formats a hash string with the correct number of leading zeros.
static java.lang.String	generateMerkleRoot(java.lang.String root1, java.lang.String root2) Generates a Merkle Root hash based on two other Merkle Roots.
static int	generateProof(byte[] bytes, int target) Generates the Proof of Work for a given Block using the Block Header.
private static boolean	validateHash(java.math.BigInteger value, java.math.BigInteger target) Validates a hash against the specified target.
static boolean	validateProof(byte[] bytes, int proof, int target) Validates a generated Proof of Work for any given Block.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

logger

private static final java.util.logging.Logger logger

hashEst

private static double hashEst

Constructor Detail

HashUtil

public HashUtil()

Method Detail

generateLeadingZeros

public static java.lang.String generateLeadingZeros(java.lang.String hash)

Formats a hash string with the correct number of leading zeros (64 digits by default).

Parameters:

hash - String to format

Returns:

Hash String with 64 digits (including leading zeros)

generateLeadingZeros

public static java.lang.String generateLeadingZeros(java.lang.String hash,
                                                    int digits)

Formats a hash string with the correct number of leading zeros.

Parameters:

hash - String to format

digits - Number of digits to match (including leading zeros)

Returns:

Hash String with the specified number of digits (including leading zeros)

generateBlockHash

public static java.lang.String generateBlockHash(byte[] bytes,
                                                 int proof)

Generates a Block hash from a byte array representing a Block Header.

Parameters:

bytes - Byte array representing a Block Header

proof - Integer Proof of Work for the specified Block

Returns:

Hexadecimal String representing the hash of the Block Header

generateHash

public static java.lang.String generateHash(byte[] bytes)

Generates a hash from given data as an array of bytes.

Parameters:

bytes - Byte Array from which to generate hash

Returns:

Hexadecimal String representing the hash of the data

validateProof

public static boolean validateProof(byte[] bytes,
                                    int proof,
                                    int target)

Validates a generated Proof of Work for any given Block.

Parameters:

bytes - The Block in binary format

proof - Integer Proof of Work for the specified Block

target - Target in shorthand form. The hash of the Block Header must be less than the target to be valid (increasing the difficulty to create a proof with the power and speed of the network).

Returns:

True if the proof is valid, False otherwise

generateProof

public static int generateProof(byte[] bytes,
                                int target)
                         throws java.lang.InterruptedException

Generates the Proof of Work for a given Block using the Block Header. This algorithm is based on methods used in Adam Back's Hashcash, an anti-spam solution for email. The generation of the Proof of Work requires the most time and resources during the mining process. It is based on the difficulty of finding the pre-image of a hash. Theoretically, any hash String of 64 characters can be created, but it is difficult to compute the data that will result in the desired hash.

For example, let's make a rule that a valid data hash will begin with three zeros. Hashing "Hello" using SHA-256^2 would give a hash of 70BC18BEF5AE66B72D1995F8DB90A583A60D77B4066E4653F1CEAD613025861C. In order to find a pre-image that will result in a valid hash, a nonce (single-use value) will be randomly generated and appended to the original data. If the nonce 6591 is appended to our original data, hashing "Hello6591" using SHA-256^2 yields a hash of 0008A883DACB7094D6DA1A6CEFC6E7CBC13635D024AC15152C4EADBA7AF8D11C, which is valid with the three zero rule.

To successfully generate a Block, a challenge must be declared, called the Target. The hash resulting from the Block Header and a Proof of Work (nonce), called the solution, must be less than the Target. This usually causes a number of zero bits at the beginning of each hash, which is why the hash of every generated Block starts with a specific number of zeros. As the target decreases, the difficulty to generate each proof, and therefore the time it takes to generate a Block, increases. Because the beginning nonce is initialized with a secure random long (64-bit integer) on each Node, finding a valid solution is essentially a lottery among each Node in the network.

A Proof of Work is implemented in order to prevent manipulation of the BlockChain. The network can produce a new valid Block every few minutes as it may have hundreds or thousands of Miner Nodes all working to find a valid proof for a Block. This means generating a new Block for the BlockChain is a minor inconvenience to the network, as it may take a few minutes to generate a single Block. However, it is almost infeasible for any one Node to generate a valid Block on its own. A target allowing Blocks to generate every five minutes on the network, on average, could take a single Node several decades, on average. Therefore, to manipulate the BlockChain using falsely generated Blocks or to change previously added Blocks would require infeasible amounts of processing power, in addition to 51% of Nodes on the network (See 51% Attack).

The network can be configured to generate Blocks after a fixed time, on average. The target adjustment after Block generation can keep the configured time between Blocks fixed by increasing or decreasing the target. If more Miner Nodes were added to the network, Block generation would be faster, on average. The target would be adjusted to then increase the difficulty of each subsequent Block bringing the average Block generation time back to the configured time. (The fixed time is an average as Proof of Work generation is a lottery, and a Node's ability to mine a valid hash is largely based on luck. Half the time a Node can generate a Block faster than the desired time.)

Parameters:

bytes - The Block Header in binary format

target - The hash must be less than the target to be valid (increasing the difficulty to create a proof with the power and speed of the network).

Returns:

Integer Proof of Work for the specified Block (Nonce to generate Block's hash)

Throws:

java.lang.InterruptedException - Thrown if the Thread is interrupted by Node.stopBlockGeneration().

validateHash

private static boolean validateHash(java.math.BigInteger value,
                                    java.math.BigInteger target)

Validates a hash against the specified target.

Parameters:

value - The hash which must be validated

target - The hash must be less than the target to be valid (increasing the difficulty to create a proof with the power and speed of the network).

Returns:

True if the hash is valid (less than the target), False otherwise

generateMerkleRoot

public static java.lang.String generateMerkleRoot(java.lang.String root1,
                                                  java.lang.String root2)

Generates a Merkle Root hash based on two other Merkle Roots. A Merkle tree, also known as a Hash tree is a tree in which every non-leaf node is labeled with the hash of the labels of its children nodes, or values of leaf nodes. Merkle Roots allow efficient and secure verification of the contents of large data structures. A change in one of the leaf nodes would result in a completely different Merkle Root, as all changes would be propagated in the tree.

Parameters:

root1 - First Merkle Root

root2 - Second Merkle Root

Returns:

Merkle Root of root1 and root2

estimateTime

public static int estimateTime(double difficulty)

Returns the estimated time (in seconds) to generate a proof of work. This method runs a simulation the first time it is called to accurately predict the time to generate a hash given a difficulty.

Parameters:

difficulty - Difficulty of block

Returns:

Time in seconds to generate a proof of work