# Ethash proof - Command line to calculate ethash (ethereum POW) merkle proof

Ethashproof is a commandline to calculate proof data for an ethash POW, it is used by project `SmartPool` and a decentralized
bridge between Etherum and EOS developed by Kyber Network team.

## Features

1. Calculate merkle root of the ethash dag dataset with given epoch
2. Calculate merkle proof of the pow (dataset elements and their merkle proofs) given the pow submission with given block header
3. Generate dag dataset

## Installation

1. Install go1.11.2 (https://golang.org/doc/install#install)
2. Run export GO111MODULE=on 
3. Run `./build.sh`

## Usage

`ethashproof` comes with 3 tools:
1. `cmd/epoch/epoch` which calculate merkle root for epochs from [0, 512)
2. `cmd/relayer/relayer` which accepts block number to calculate all necessary information in order to prove the block
3. `cmd/cache/cache` which calculate cache merkle tree for an epoch

### The output

When you run `cmd/epoch/epoch`, it will print:
1. Merkle root of the DAG dataset

When you run `cmd/relayer/relayer`, it will print a json containing following information:

1. RLP encoding of the block header
2. Merkle root of the DAG dataset
3. An array of DAG dataset element arrays (that were used in ethash POW). The array is flatten. (Check DAG data element encoding section)
4. An array of all merkle proofs for all of the elements above (check Merkle audit proof encoding section)
5. Length of the proof for a DAG dataset element

*note: the first time you run `relayer` for a blockno corresponding to a new epoch, `relayer` will take several minutes to generate the DAG dataset and calculate everything as well as preparing the cache in order to improve its performance in next runs. It is recommended to run `epoch` for future epoches so it can prepare everything beforehand.*

## Explanations

### Merkle tree in ethashproof

In `ethashproof`, we construct a merkle tree out of ethash DAG dataset in order to get merkle root
of the dataset and get merkle proof for any specific dataset element.
Each DAG dataset is a sequence of many 128 bytes dataset elements, denoted as:
```
e0, e1, e2, ..., en
```

#### Merkle tree explanation

The merkle tree is constructed in the following way:

- Step 1: Calculate hash of each element using `elementhash` function. We would have:
```
h00, h01, h02, h03, ..., h0n
 |    |    |    |   ...   |
e0,  e1,  e2,  e3,  ..., en
```
where `h01` means hash at level 0, element 1. The hash is 32 bytes.

- Step 2: In this step, set the `working level` to 0.
calculate `h10 = hash(h00, h01)`, `h11 = hash(h02, h03)`, ...
if at the end of the level, there is only one element left, we duplicate it and calculate the hash out of them, eg. `h0x = hash(h0x*2, h0x*2)`
```
   h10       h11    ...  h1n/2
  /  \      /  \           /  \
h00, h01, h02, h03, ..., h0n  h0n
 |    |    |    |   ...   |
e0,  e1,  e2,  e3,  ..., en
```

- Step 3: Increase `working level` by 1 and go back to Step 2 until there is only 1 element in the working level. That element is the merkle root.
```
            merkle root
                .
              .....
            ..........
          ...............
        h20         ...  h2n/4
      /     \          /   |
   h10       h11    ...  h1n/2
  /  \      /  \           /  \
h00, h01, h02, h03, ..., h0n  h0n
 |    |    |    |   ...   |
e0,  e1,  e2,  e3,  ..., en
```

#### Hash function
0. Given `sha256(bytes) => bytes` is a function to hash an array of bytes
1. Hash function for data element(`elementhash`)
`elementhash` returns 16 bytes hash of the dataset element.
```
function elementhash(data) => 16bytes {
  h = sha256(conventional(data)) // conventional function is defined in dataset element encoding section
  return last16Bytes(h)
}
```

2. Hash function for 2 sibling nodes (`hash`)
`hash` returns 16 bytes hash of 2 consecutive elements in a working level.
```
function hash(a, b) => 16bytes {
  h = sha256(zeropadded(a), zeropadded(b)) // where zeropadded function prepend 16 bytes of 0 to its param	  h = sha256(a, b) // where a, b are 32bytes
  return last16Bytes(h)
}
```

#### Conventional encoding

To make it easier for ethereum smartcontract to follow the hash calculation, we use a convention to encode DAG dataset element
to use in hash function. The encoding is defined as the following pseudo code:

1. assume the element is `abcd` where a, b, c, d are 32 bytes word
2. `first = concat(reverse(a), reverse(b))` where `reverse` reverses the bytes
3. `second = concat(reverse(c), reverse(d))`
4. conventional encoding of `abcd` is `concat(first, second)`

#### Dataset element encoding

In order to make it easy (and gas saving) for ethereum smart contract (the earliest contract we used to verify the proof) to work with the
dataset element, `ethashproof` outputs a DAG dataset element as an array of 32 bytes word, the word is little endian.

#### Merkle audit proof

Please read more on http://www.certificate-transparency.org/log-proofs-work.

#### Merkle audit proof encoding

For a DAG dataset element, there is a list of hashes (the proof) to prove its existence. In `ethashproof`, we dont include dataset element's hash	
and the merkle root in the proof and format it in the following rules

1. assume the hashes are: `[h0, h1, h2, h3, ..., hn]` where `hi` is 16 bytes.
2. if n is odd, append a 16 bytes number of 0.
3. reorder the hashes to: `[h1, h0, h3, h2, ...]`
4. concatenate 2 consecutive hashes into one 32 bytes word so that the hashes becomes `[h1h0, h3h2, ...]`

In the output of `ethashproof`, all proofs of the elements are included in order in 1 array so that the proof
of dataset element 0 will be at the beginning of the array and element n's will be at the end. You will have to
determine the boundary of each proof yourself.