Ethash Functions

Table of Contents

Introduction

Ethash algorithm related functionalities.

Module Contents

Functions

`epoch`	Obtain the epoch number to which the block identified by block_number
`cache_size`	Obtain the cache size (in bytes) of the epoch to which block_number
`dataset_size`	Obtain the dataset size (in bytes) of the epoch to which block_number
`generate_seed`	Obtain the cache generation seed for the block identified by
`generate_cache`	Generate the cache for the block identified by block_number. This cache
`fnv`	FNV algorithm is inspired by the FNV hash, which in some cases is used
`fnv_hash`	FNV Hash mixes in data into mix using the ethash fnv method.
`generate_dataset_item`	Generate a particular dataset item 0-indexed by index using cache.
`generate_dataset`	Generate the full dataset for the block identified by block_number.
`hashimoto`	Obtain the mix digest and the final value for a header, by aggregating
`hashimoto_light`	Run the hashimoto algorithm by generating dataset item using the cache

Attributes

`EPOCH_SIZE`
`INITIAL_CACHE_SIZE`
`CACHE_EPOCH_GROWTH_SIZE`
`INITIAL_DATASET_SIZE`
`DATASET_EPOCH_GROWTH_SIZE`
`HASH_BYTES`
`MIX_BYTES`
`CACHE_ROUNDS`
`DATASET_PARENTS`
`HASHIMOTO_ACCESSES`

Module Details

EPOCH_SIZE

EPOCH_SIZE

EPOCH_SIZE = 30000

INITIAL_CACHE_SIZE

INITIAL_CACHE_SIZE

INITIAL_CACHE_SIZE = 2**24

CACHE_EPOCH_GROWTH_SIZE

CACHE_EPOCH_GROWTH_SIZE

CACHE_EPOCH_GROWTH_SIZE = 2**17

INITIAL_DATASET_SIZE

INITIAL_DATASET_SIZE

INITIAL_DATASET_SIZE = 2**30

DATASET_EPOCH_GROWTH_SIZE

DATASET_EPOCH_GROWTH_SIZE

DATASET_EPOCH_GROWTH_SIZE = 2**23

HASH_BYTES

HASH_BYTES

HASH_BYTES = 64

MIX_BYTES

MIX_BYTES

MIX_BYTES = 128

CACHE_ROUNDS

CACHE_ROUNDS

CACHE_ROUNDS = 3

DATASET_PARENTS

DATASET_PARENTS

DATASET_PARENTS = 256

HASHIMOTO_ACCESSES

HASHIMOTO_ACCESSES

HASHIMOTO_ACCESSES = 64

epoch

epoch(block_number: ethereum.base_types.Uint) → ethereum.base_types.Uint 

Obtain the epoch number to which the block identified by block_number belongs.

Parameters: block_number – The number of the block of interest.
Returns: epoch_number – The epoch number to which the passed in block belongs.
Return type: Uint

def epoch(block_number: Uint) -> Uint:
    return block_number // EPOCH_SIZE

cache_size

cache_size(block_number: ethereum.base_types.Uint) → ethereum.base_types.Uint 

Obtain the cache size (in bytes) of the epoch to which block_number belongs.

Parameters: block_number – The number of the block of interest.
Returns: cache_size_bytes – The cache size in bytes for the passed in block.
Return type: Uint

def cache_size(block_number: Uint) -> Uint:
    size = INITIAL_CACHE_SIZE + (CACHE_EPOCH_GROWTH_SIZE * epoch(block_number))
    size -= HASH_BYTES
    while not is_prime(size // HASH_BYTES):
        size -= 2 * HASH_BYTES

    return size

dataset_size

dataset_size(block_number: ethereum.base_types.Uint) → ethereum.base_types.Uint 

Obtain the dataset size (in bytes) of the epoch to which block_number belongs.

Parameters: block_number – The number of the block of interest.
Returns: dataset_size_bytes – The dataset size in bytes for the passed in block.
Return type: Uint

def dataset_size(block_number: Uint) -> Uint:
    size = INITIAL_DATASET_SIZE + (
        DATASET_EPOCH_GROWTH_SIZE * epoch(block_number)
    )
    size -= MIX_BYTES
    while not is_prime(size // MIX_BYTES):
        size -= 2 * MIX_BYTES

    return size

generate_seed

generate_seed(block_number: ethereum.base_types.Uint) → ethereum.crypto.hash.Hash32 

Obtain the cache generation seed for the block identified by block_number.

Parameters: block_number – The number of the block of interest.
Returns: seed – The cache generation seed for the passed in block.
Return type: Hash32

def generate_seed(block_number: Uint) -> Hash32:
    epoch_number = epoch(block_number)

    seed = b"\x00" * 32
    while epoch_number != 0:
        seed = keccak256(seed)
        epoch_number -= 1

    return Hash32(seed)

generate_cache

generate_cache(block_number: ethereum.base_types.Uint) → Tuple[Tuple[ethereum.base_types.U32, Ellipsis], Ellipsis]

Generate the cache for the block identified by block_number. This cache would later be used to generate the full dataset.

Parameters: block_number – The number of the block of interest.
Returns: cache – The cache generated for the passed in block.
Return type: Tuple[Tuple[U32, …], …]

def generate_cache(block_number: Uint) -> Tuple[Tuple[U32, ...], ...]:
    seed = generate_seed(block_number)
    cache_size_bytes = cache_size(block_number)

    cache_size_words = cache_size_bytes // HASH_BYTES
    cache = [keccak512(seed)]

    previous_cache_item = cache[0]
    for _ in range(1, cache_size_words):
        cache_item = keccak512(previous_cache_item)
        cache.append(cache_item)
        previous_cache_item = cache_item

    for _ in range(CACHE_ROUNDS):
        for index in range(cache_size_words):
            # Converting `cache_size_words` to int as `-1 + Uint(5)` is an
            # error.
            first_cache_item = cache[
                (index - 1 + int(cache_size_words)) % cache_size_words
            ]
            second_cache_item = cache[
                U32.from_le_bytes(cache[index][0:4]) % cache_size_words
            ]
            result = bytes(
                [a ^ b for a, b in zip(first_cache_item, second_cache_item)]
            )
            cache[index] = keccak512(result)

    return tuple(
        le_bytes_to_uint32_sequence(cache_item) for cache_item in cache
    )

fnv

fnv(a: Union[ethereum.base_types.Uint, ethereum.base_types.U32], b: Union[ethereum.base_types.Uint, ethereum.base_types.U32]) → ethereum.base_types.U32 

FNV algorithm is inspired by the FNV hash, which in some cases is used as a non-associative substitute for XOR.

Note that here we multiply the prime with the full 32-bit input, in contrast with the FNV-1 spec which multiplies the prime with one byte (octet) in turn.

Parameters

a – The first data point.
b – The second data point.

Returns

modified_mix_integers – The result of performing fnv on the passed in data points.

Return type

U32

def fnv(a: Union[Uint, U32], b: Union[Uint, U32]) -> U32:
    # This is a faster way of doing [number % (2 ** 32)]
    result = ((Uint(a) * 0x01000193) ^ Uint(b)) & U32_MAX_VALUE
    return U32(result)

fnv_hash

fnv_hash(mix_integers: Tuple[ethereum.base_types.U32, Ellipsis], data: Tuple[ethereum.base_types.U32, Ellipsis]) → Tuple[ethereum.base_types.U32, Ellipsis]

FNV Hash mixes in data into mix using the ethash fnv method.

Parameters

mix_integers – Mix data in the form of a sequence of U32.
data – The data (sequence of U32) to be hashed into the mix.

Returns

modified_mix_integers – The result of performing the fnv hash on the mix and the passed in data.

Return type

Tuple[U32, …]

def fnv_hash(
    mix_integers: Tuple[U32, ...], data: Tuple[U32, ...]
) -> Tuple[U32, ...]:
    return tuple(
        fnv(mix_integers[i], data[i]) for i in range(len(mix_integers))
    )

generate_dataset_item

generate_dataset_item(cache: Tuple[Tuple[ethereum.base_types.U32, Ellipsis], Ellipsis], index: ethereum.base_types.Uint) → ethereum.crypto.hash.Hash64 

Generate a particular dataset item 0-indexed by index using cache. Each dataset item is a byte stream of 64 bytes or a stream of 16 uint32 numbers.

Parameters

cache – The cache from which a subset of items will be used to generate the dataset item.
index – The index of the dataset item to generate.

Returns

dataset_item – The generated dataset item for passed index.

Return type

Hash64

def generate_dataset_item(
    cache: Tuple[Tuple[U32, ...], ...], index: Uint
) -> Hash64:
    mix = keccak512(
        (
            le_uint32_sequence_to_uint(cache[index % len(cache)]) ^ index
        ).to_le_bytes(number_bytes=HASH_BYTES)
    )

    mix_integers = le_bytes_to_uint32_sequence(mix)

    for j in range(DATASET_PARENTS):
        mix_word: U32 = mix_integers[j % 16]
        cache_index = fnv(index ^ j, mix_word) % len(cache)
        parent = cache[cache_index]
        mix_integers = fnv_hash(mix_integers, parent)

    mix = Hash64(le_uint32_sequence_to_bytes(mix_integers))

    return keccak512(mix)

generate_dataset

generate_dataset(block_number: ethereum.base_types.Uint) → Tuple[ethereum.crypto.hash.Hash64, Ellipsis]

Generate the full dataset for the block identified by block_number.

This function is present only for demonstration purposes, as it will take a long time to execute.

Parameters: block_number – The number of the block of interest.
Returns: dataset – The dataset generated for the passed in block.
Return type: Tuple[Hash64, …]

def generate_dataset(block_number: Uint) -> Tuple[Hash64, ...]:
    dataset_size_bytes: Uint = dataset_size(block_number)
    cache: Tuple[Tuple[U32, ...], ...] = generate_cache(block_number)

    # TODO: Parallelize this later on if it adds value
    return tuple(
        generate_dataset_item(cache, Uint(index))
        for index in range(dataset_size_bytes // HASH_BYTES)
    )

hashimoto

hashimoto(header_hash: ethereum.crypto.hash.Hash32, nonce: ethereum.base_types.Bytes8, dataset_size: ethereum.base_types.Uint, fetch_dataset_item: Callable[[ethereum.base_types.Uint], Tuple[ethereum.base_types.U32, Ellipsis]]) → Tuple[bytes, ethereum.crypto.hash.Hash32]

Obtain the mix digest and the final value for a header, by aggregating data from the full dataset.

Parameters

header_hash – The PoW valid rlp hash of a header.
nonce – The propogated nonce for the given block.
dataset_size – Dataset size for the epoch to which the current block belongs to.
fetch_dataset_item – The function which will be used to obtain a specific dataset item from an index.

Returns

mix_digest (bytes) – The mix digest generated from the header hash and propogated nonce.
result (Hash32) – The final result obtained which will be checked for leading zeros (in byte representation) in correspondance with the block difficulty.

def hashimoto(
    header_hash: Hash32,
    nonce: Bytes8,
    dataset_size: Uint,
    fetch_dataset_item: Callable[[Uint], Tuple[U32, ...]],
) -> Tuple[bytes, Hash32]:
    nonce_le = bytes(reversed(nonce))
    seed_hash = keccak512(header_hash + nonce_le)
    seed_head = U32.from_le_bytes(seed_hash[:4])

    rows = dataset_size // 128
    mix = le_bytes_to_uint32_sequence(seed_hash) * (MIX_BYTES // HASH_BYTES)

    for i in range(HASHIMOTO_ACCESSES):
        new_data: Tuple[U32, ...] = ()
        parent = fnv(i ^ seed_head, mix[i % len(mix)]) % rows
        for j in range(MIX_BYTES // HASH_BYTES):
            # Typecasting `parent` from U32 to Uint as 2*parent + j may
            # overflow U32.
            new_data += fetch_dataset_item(2 * Uint(parent) + j)

        mix = fnv_hash(mix, new_data)

    compressed_mix = []
    for i in range(0, len(mix), 4):
        compressed_mix.append(
            fnv(fnv(fnv(mix[i], mix[i + 1]), mix[i + 2]), mix[i + 3])
        )

    mix_digest = le_uint32_sequence_to_bytes(compressed_mix)
    result = keccak256(seed_hash + mix_digest)

    return mix_digest, result

hashimoto_light

hashimoto_light(header_hash: ethereum.crypto.hash.Hash32, nonce: ethereum.base_types.Bytes8, cache: Tuple[Tuple[ethereum.base_types.U32, Ellipsis], Ellipsis], dataset_size: ethereum.base_types.Uint) → Tuple[bytes, ethereum.crypto.hash.Hash32]

Run the hashimoto algorithm by generating dataset item using the cache instead of loading the full dataset into main memory.

Parameters

header_hash – The PoW valid rlp hash of a header.
nonce – The propogated nonce for the given block.
cache – The generated cache for the epoch to which the current block belongs to.
dataset_size – Dataset size for the epoch to which the current block belongs to.

Returns

mix_digest (bytes) – The mix digest generated from the header hash and propogated nonce.
result (Hash32) – The final result obtained which will be checked for leading zeros (in byte representation) in correspondance with the block difficulty.

def hashimoto_light(
    header_hash: Hash32,
    nonce: Bytes8,
    cache: Tuple[Tuple[U32, ...], ...],
    dataset_size: Uint,
) -> Tuple[bytes, Hash32]:

    def fetch_dataset_item(index: Uint) -> Tuple[U32, ...]:
        item: Hash64 = generate_dataset_item(cache, index)
        return le_bytes_to_uint32_sequence(item)

    return hashimoto(header_hash, nonce, dataset_size, fetch_dataset_item)