Dagger-Hashimoto EthHash - Mining a PoW Block from scratch and verifying it
Going through the GETH codebase to figure out how ethhash works.
So I’ve been really into the geth and lighthouse codebases for the past few months now and kind of really at the end stage on so before really understanding how geth and the beacon chain methods are interconnected, I thought I’d just go back in time and figure out how the proof of work on Ethereum actually worked under the hood. Yk, why not build an actual miner to mine a block? This post will be going into the algorithmic part of ethhash rather than the consensus part of it.
So basically what is mining at the simplest level? Keep on guessing random numbers until we find a valid one that matches the difficulty or the target. In Bitcoin, if I’m not wrong, we take a block, add a nonce, then hash it and check if the hash starts with a desired number of zeroes. If not, try another, and then this process just goes on. Now for ETH, the same process but with memory hardness and increased I/O count, which was again built in mind to prevent ASIC majority.
The point of this article is that I’d be going into the geth source code in try building a simple miner, or the simplest miner possible.
If I’m not wrong before the merge, meaning one of the last versions that used the pow is version v1.10.26. If you were to look at the source code of ethhash in geth under consensus in the latest version, you’d just get a fake PoW scheme that accepts all blocks’ seals as valid.
So guess we’d start. The Ethereum website has two main articles regarding Dagger Hashimoto and Ethhash, but the articles are just too abstract, and also it’s kind of missing out on stuff.
https://ethereum.org/developers/docs/consensus-mechanisms/pow/mining/mining-algorithms/dagger-hashimoto/ https://ethereum.org/developers/docs/consensus-mechanisms/pow/mining/mining-algorithms/ethash/
So the main thing to understand is that Ethhash is the upgraded version of dagger hashimoto, where the dag (which I’d explain) will be created from a cache instead of a direct seed.
The website first talks about ASIC resistance, and this is the most important difference from the mining algorithm used in Bitcoin. The whole point is how Ethash is designed such that it prevents ASIC miners from dominating the hash rate by imposing memory hardness, meaning it requires a huge amount of RAM to compute the final target. But again, that doesn’t mean that Asic can’t use memory, nor was the whole point a success… ASIC miners for Ethereum had eventually been developed.
DAG
Directed acyclic graph, okay, now that sounds kinda scary, but those are basically nodes (directed ofc) which are one-way directions from one another. -> represents a dependency; this is the most important feature of a DAG, meaning if A -> B, B needs A to happen first. And the asyclic part means the nodes shouldn’t form a cycle.
Now with this, how do we implement memory constraints? If we were to store a DAG in an array, it’s basically indexes in the array that are dependent on the previous indexes. Here’s where you’d get that click, so what happens when the array grows larger and it needs to access previous elements? Memory! Here’s how the memory imposing is done if the indexes hadn’t been dependent on previous indexes, thus not needing much memory access at all.
So this is the dagger part, where we have a huge array stored in memory, which during the mining process will be accessed pseudorandomly.
Now here is the difference between Dagger Hashimoto and Ethash: in Dagger Hashimoto, the seed is directly used to create the DAG, whereas in Ethash, first a cache is generated, then this particular cache is used to generate the final day.
The cache is basically a pseudo-random array but with a significantly smaller size; in ethhash it’s called the verification cache.
It is designed for light clients, which are used to verify the proofs, wherein generating the whole DAG in memory for light clients doesn’t make sense.
| Dagger | seed -> dag |
| EthHash | seed -> dag -> cache |
Now let’s see how it’s implemented in the code.
Calculating the cache and dataset sizes
go-ethereum/consensus/ethash/algorithm.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// cacheSize returns the size of the ethash verification cache that belongs to a certain
// block number.
func cacheSize(block uint64) uint64 {
epoch := int(block / epochLength)
if epoch < maxEpoch {
return cacheSizes[epoch]
}
return calcCacheSize(epoch)
}
// calcCacheSize calculates the cache size for epoch. The cache size grows linearly,
// however, we always take the highest prime below the linearly growing threshold in order
// to reduce the risk of accidental regularities leading to cyclic behavior.
func calcCacheSize(epoch int) uint64 {
size := cacheInitBytes + cacheGrowthBytes*uint64(epoch) - hashBytes
for !new(big.Int).SetUint64(size / hashBytes).ProbablyPrime(1) { // Always accurate for n < 2^64
size -= 2 * hashBytes
}
return size
}
This particular snippet is used to calculate the cache size for an epoch; we can see the cache. Sizes array:
1
2
3
4
// cacheSizes is a lookup table for the ethash verification cache size for the
// first 2048 epochs (i.e. 61440000 blocks).
var cacheSizes = [maxEpoch]uint64{
16776896, 16907456, 17039296, 17170112, 17301056, 17432512, 17563072, ...
For epoch 0 : the cache size is 16776896, which is 16mb in size.
From the calcCacheSize() function we can see that it grows linearly in size.
Next is the function to see calculate the size of the dag:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// datasetSize returns the size of the ethash mining dataset that belongs to a certain
// block number.
func datasetSize(block uint64) uint64 {
epoch := int(block / epochLength)
if epoch < maxEpoch {
return datasetSizes[epoch]
}
return calcDatasetSize(epoch)
}
// calcDatasetSize calculates the dataset size for epoch. The dataset size grows linearly,
// however, we always take the highest prime below the linearly growing threshold in order
// to reduce the risk of accidental regularities leading to cyclic behavior.
func calcDatasetSize(epoch int) uint64 {
size := datasetInitBytes + datasetGrowthBytes*uint64(epoch) - mixBytes
for !new(big.Int).SetUint64(size / mixBytes).ProbablyPrime(1) { // Always accurate for n < 2^64
size -= 2 * mixBytes
}
return size
}
Again we can see that it grows linearly on increasing epochs.
1
2
3
4
// datasetSizes is a lookup table for the ethash dataset size for the first 2048
// epochs (i.e. 61440000 blocks).
var datasetSizes = [maxEpoch]uint64{
1073739904, 1082130304, 1090514816, 1098906752, 1107293056, ...
For epoch zero it’s 1073739904, which is roughly around 1gb in size.
Calcuating the seed
Now every epoch has a seed, which would be put into the algorithm to generate the verification cache and the dataset, which is a DAG ofc.
From the code we can see that :
1
2
3
4
5
6
7
8
9
10
11
12
13
// seedHash is the seed to use for generating a verification cache and the mining
// dataset.
func seedHash(block uint64) []byte {
seed := make([]byte, 32)
if block < epochLength {
return seed
}
keccak256 := makeHasher(sha3.NewLegacyKeccak256())
for i := 0; i < int(block/epochLength); i++ {
keccak256(seed, seed)
}
return seed
}
Which is pretty much self-explanatory: if it’s the 0th epoch, then the seed is 0, and for further epochs, it’s basically the hash of the previous epochs’ seed.
seed1 = kecaak256(seed0)
Calculating the final dag/dataset
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// generateCache creates a verification cache of a given size for an input seed.
// The cache production process involves first sequentially filling up 32 MB of
// memory, then performing two passes of Sergio Demian Lerner's RandMemoHash
// algorithm from Strict Memory Hard Hashing Functions (2014). The output is a
// set of 524288 64-byte values.
// This method places the result into dest in machine byte order.
func generateCache(dest []uint32, epoch uint64, seed []byte) {
// Print some debug logs to allow analysis on low end devices
logger := log.New("epoch", epoch)
start := time.Now()
defer func() {
elapsed := time.Since(start)
logFn := logger.Debug
if elapsed > 3*time.Second {
logFn = logger.Info
}
logFn("Generated ethash verification cache", "elapsed", common.PrettyDuration(elapsed))
}()
// Convert our destination slice to a byte buffer
var cache []byte
cacheHdr := (*reflect.SliceHeader)(unsafe.Pointer(&cache))
dstHdr := (*reflect.SliceHeader)(unsafe.Pointer(&dest))
cacheHdr.Data = dstHdr.Data
cacheHdr.Len = dstHdr.Len * 4
cacheHdr.Cap = dstHdr.Cap * 4
// Calculate the number of theoretical rows (we'll store in one buffer nonetheless)
size := uint64(len(cache))
rows := int(size) / hashBytes
// Start a monitoring goroutine to report progress on low end devices
var progress uint32
done := make(chan struct{})
defer close(done)
go func() {
for {
select {
case <-done:
return
case <-time.After(3 * time.Second):
logger.Info("Generating ethash verification cache", "percentage", atomic.LoadUint32(&progress)*100/uint32(rows)/(cacheRounds+1), "elapsed", common.PrettyDuration(time.Since(start)))
}
}
}()
// Create a hasher to reuse between invocations
keccak512 := makeHasher(sha3.NewLegacyKeccak512())
// Sequentially produce the initial dataset
keccak512(cache, seed)
for offset := uint64(hashBytes); offset < size; offset += hashBytes {
keccak512(cache[offset:], cache[offset-hashBytes:offset])
atomic.AddUint32(&progress, 1)
}
// Use a low-round version of randmemohash
temp := make([]byte, hashBytes)
for i := 0; i < cacheRounds; i++ {
for j := 0; j < rows; j++ {
var (
srcOff = ((j - 1 + rows) % rows) * hashBytes
dstOff = j * hashBytes
xorOff = (binary.LittleEndian.Uint32(cache[dstOff:]) % uint32(rows)) * hashBytes
)
bitutil.XORBytes(temp, cache[srcOff:srcOff+hashBytes], cache[xorOff:xorOff+hashBytes])
keccak512(cache[dstOff:], temp)
atomic.AddUint32(&progress, 1)
}
}
// Swap the byte order on big endian systems and return
if !isLittleEndian() {
swap(cache)
}
}
The function takes in the epoch and the seed to generate the final DAG; there are basically two phases happening here:
In the first phase:
1
2
3
4
for offset := uint64(hashBytes); offset < size; offset += hashBytes {
keccak512(cache[offset:], cache[offset-hashBytes:offset])
atomic.AddUint32(&progress, 1)
}
Which is essentially:
cache[0] = Keecack512(seed) cache[1] = Keecack512(cache[0]) and on and on
Then in the next part which is this loop:
1
2
3
4
5
6
7
8
9
10
11
12
13
for i := 0; i < cacheRounds; i++ {
for j := 0; j < rows; j++ {
var (
srcOff = ((j - 1 + rows) % rows) * hashBytes
dstOff = j * hashBytes
xorOff = (binary.LittleEndian.Uint32(cache[dstOff:]) % uint32(rows)) * hashBytes
)
bitutil.XORBytes(temp, cache[srcOff:srcOff+hashBytes], cache[xorOff:xorOff+hashBytes])
keccak512(cache[dstOff:], temp)
atomic.AddUint32(&progress, 1)
}
}
It kind of depends on how well you want to understand this function, but what it is doing is doing the “memory dependency,” wherein the C[j] depends on the previous cache and on a pseudo-random cache, which ensures the memory hardness part, just like from the website.
Which pretty much ends on our “dagger” part since we have no generated the final dag part.
But again what is the use without actually testing it out and seeing it in action?!
Testing it out
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package main
import (
"fmt"
"github.com/ethereum/go-ethereum/consensus/ethash"
"github.com/ethereum/go-ethereum/ethclient"
"math/big"
"context"
"github.com/ethereum/go-ethereum/params"
)
func main() {
config := params.MainnetChainConfig
blockNumber := big.NewInt(15537393)
epoch := uint64(blockNumber.Uint64() / 30000)
cacheSize := ethash.CacheSize(blockNumber.Uint64())
datasetSize := ethash.DatasetSize(blockNumber.Uint64())
fmt.Printf("Epoch: %d\n", epoch)
fmt.Printf("Cache: %.2f MiB\n", float64(cacheSize)/(1024*1024))
fmt.Printf("Dataset: %.2f GiB\n", float64(datasetSize)/(1024*1024*1024))
seedHash := ethash.SeedHash(blockNumber.Uint64())
verificationCache := make([]uint32, cacheSize/4)
ethash.GenerateVerificationCache(verificationCache, epoch, seedHash)
dataset := make([]uint32, datasetSize/4)
ethash.GenerateDataset(dataset, epoch, verificationCache)
Here I’m using a really old block which was one of the last blocks to use the Pow.
ethhash is not exposing the methods, so created a file in the codebase which exports it.
When running it we can see that the verification cache takes around 80 mb and the dataset being at 5gb! Depending on your system, it’s going to take time… again I can’t print and show the array here ;)
Now guess it’s time to move the next stage of the algorithm.
Hashimoto
I’m adding my point regarding mining from above once again;
So basically what is mining at the simplest level? Keep on guessing random numbers until we find a valid one that matches the difficulty or the target. In Bitcoin, if I’m not wrong, we take a block, add a nonce, then hash it and check if the hash starts with a desired number of zeroes. If not, try another, and then this process just goes on. Now for ETH, the same process but with memory hardness and increased I/O count, which was again built in mind to prevent ASIC majority.
With the memory hardness, another thing the algorithm ensures is that it increases the i/o count, meaning it keeps on jumping between random memory locations. Let’s get to the algorithm directly now:
1
2
3
4
5
6
7
8
9
10
11
12
// hashimotoFull aggregates data from the full dataset (using the full in-memory
// dataset) in order to produce our final value for a particular header hash and
// nonce.
func hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
lookup := func(index uint32) []uint32 {
offset := index * hashWords
return dataset[offset : offset+hashWords]
}
return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)
}
const maxEpoch = 2048
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// hashimoto aggregates data from the full dataset in order to produce our final
// value for a particular header hash and nonce.
func hashimoto(hash []byte, nonce uint64, size uint64, lookup func(index uint32) []uint32) ([]byte, []byte) {
// Calculate the number of theoretical rows (we use one buffer nonetheless)
rows := uint32(size / mixBytes)
// Combine header+nonce into a 64 byte seed
seed := make([]byte, 40)
copy(seed, hash)
binary.LittleEndian.PutUint64(seed[32:], nonce)
seed = crypto.Keccak512(seed)
seedHead := binary.LittleEndian.Uint32(seed)
// Start the mix with replicated seed
mix := make([]uint32, mixBytes/4)
for i := 0; i < len(mix); i++ {
mix[i] = binary.LittleEndian.Uint32(seed[i%16*4:])
}
// Mix in random dataset nodes
temp := make([]uint32, len(mix))
for i := 0; i < loopAccesses; i++ {
parent := fnv(uint32(i)^seedHead, mix[i%len(mix)]) % rows
for j := uint32(0); j < mixBytes/hashBytes; j++ {
copy(temp[j*hashWords:], lookup(2*parent+j))
}
fnvHash(mix, temp)
}
// Compress mix
for i := 0; i < len(mix); i += 4 {
mix[i/4] = fnv(fnv(fnv(mix[i], mix[i+1]), mix[i+2]), mix[i+3])
}
mix = mix[:len(mix)/4]
digest := make([]byte, common.HashLength)
for i, val := range mix {
binary.LittleEndian.PutUint32(digest[i*4:], val)
}
return digest, crypto.Keccak256(append(seed, digest...))
}
Leave everything and just focus on the header and nonce part, basically a brute-force algorithm that takes in a block header hash and a nonce whose output is compared with a target number and sees if it is less than that (the target part will be explained shortly).
Now the function;
The entire dataset is first treated as a row, then the header and the nonce are hashed, then comes the mixing part wherein for every nonce 64 rounds of dataset access and mixing. During each round the mix is changed. Making the next dataset location depending on the previous dataset access. Again, there is a lot going on here, but I don’t really want to go so deep into that. Then finally, the digest is returned, which is the compressed mix, which is a block’s mixHash, and then the next value is that which is checked against the difficulty target.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
client, _ := ethclient.Dial("http://localhost:8545")
block, _ := client.BlockByNumber(context.Background(), blockNumber)
header := block.Header()
nonce := header.Nonce.Uint64()
sealHash := ethash.SealHashExport(header)
digest, result := ethash.HashimotoFull(
dataset,
sealHash[:],
nonce,
)
fmt.Println("Digest:", digest)
fmt.Println("Result:", result)
fmt.Println("Block mix digest:", header.MixDigest)
Running it:
Target
EthHash exposes a method CalcDifficulty which can be used to calculate the difficulty:
1
2
3
4
5
6
// CalcDifficulty is the difficulty adjustment algorithm. It returns
// the difficulty that a new block should have when created at time
// given the parent block's time and difficulty.
func (ethash *Ethash) CalcDifficulty(chain consensus.ChainHeaderReader, time uint64, parent *types.Header) *big.Int {
return CalcDifficulty(chain.Config(), time, parent)
}
Trying it out of the same block:
1
2
3
4
5
6
7
8
9
config := params.MainnetChainConfig
parentBlock, _ := client.BlockByNumber(
context.Background(),
new(big.Int).Sub(blockNumber, big.NewInt(1)),
)
parentHeader := parentBlock.Header()
difficulty := ethash.CalcDifficulty(config, header.Time, parentHeader)
Now the output is valid if it is less than the difficulty.
So the mining is basically this. Keep on trying until we find something that is less than the target value.
Add a for loop for the nonce part and put the Hashimoto inside, and boom! We have ourselves a miner!
Here is the full code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package main
import (
"fmt"
"github.com/ethereum/go-ethereum/consensus/ethash"
"github.com/ethereum/go-ethereum/ethclient"
"math/big"
"context"
"github.com/ethereum/go-ethereum/params"
)
func main() {
config := params.MainnetChainConfig
blockNumber := big.NewInt(15537393)
epoch := uint64(blockNumber.Uint64() / 30000)
cacheSize := ethash.CacheSize(blockNumber.Uint64())
datasetSize := ethash.DatasetSize(blockNumber.Uint64())
fmt.Printf("Epoch: %d\n", epoch)
fmt.Printf("Cache: %.2f MiB\n", float64(cacheSize)/(1024*1024))
fmt.Printf("Dataset: %.2f GiB\n", float64(datasetSize)/(1024*1024*1024))
seedHash := ethash.SeedHash(blockNumber.Uint64())
verificationCache := make([]uint32, cacheSize/4)
ethash.GenerateVerificationCache(verificationCache, epoch, seedHash)
dataset := make([]uint32, datasetSize/4)
ethash.GenerateDataset(dataset, epoch, verificationCache)
client, _ := ethclient.Dial("http://localhost:8545")
block, _ := client.BlockByNumber(context.Background(), blockNumber)
header := block.Header()
nonce := header.Nonce.Uint64()
sealHash := ethash.SealHashExport(header)
digest, result := ethash.HashimotoFull(
dataset,
sealHash[:],
nonce,
)
fmt.Println("Digest:", digest)
fmt.Println("Result:", result)
fmt.Println("Block mix digest:", header.MixDigest)
parentBlock, _ := client.BlockByNumber(
context.Background(),
new(big.Int).Sub(blockNumber, big.NewInt(1)),
)
parentHeader := parentBlock.Header()
difficulty := ethash.CalcDifficulty(config, header.Time, parentHeader)
fmt.Println(difficulty)
two256 := new(big.Int).Lsh(big.NewInt(1), 256)
target := new(big.Int).Div(
two256,
difficulty,
)
resultInt := new(big.Int).SetBytes(result)
fmt.Printf("Target: %064x\n", target)
fmt.Printf("Result: %064x\n", resultInt)
if resultInt.Cmp(target) <= 0 {
fmt.Println("PoW: VALID")
} else {
fmt.Println("PoW: INVALID")
}
}
Make sure to set the golang version to: 1.17.13