Ethereum以太坊DAG

DAG代表定向非循环图。在Ethereum中，每个epoch都会使用Dagger-Hashimoto算法，结合Vitalik Buterin的Dagger算法和Thaddeus Dryja的Hashimoto算法，创建DAG 。

DAG定义的整理:
Ethereum yellow paper中有提到

维基百科上 image.png

在数学和计算机科学中，有向无环图（DAG）是一个没有定向循环的有限有向图。也就是说，它由有限的多个顶点和边组成，每个边从一个顶点指向另一个顶点，这样就没有办法从任何顶点v开始，沿着一个连贯的边缘序列，最终循环回到v 。等价地，DAG是有向图，其具有拓扑排序，顶点序列，使得每个边缘从序列中的较早到较晚被引导。

在 [github上以太坊项目主页]中说明(https://github.com/ethereum/wiki/wiki/Ethash-DAG):
...一个巨大的数据集称为DAG ...
Ethash算法期望DAG是uint32s（4字节无符号整数）的二维数组，尺寸（n×16），其中n是一个很大的数字。（n从16777186开始）在幻数之后，DAG的行应该顺序地写入文件，在行之间没有分隔符，每个unint32以little-endian格式编码。

The Ethash algorithm expects the DAG as a two-dimensional array of uint32s (4-byte unsigned ints), with dimension (n × 16) where n is a large number. (n starts at 16777186 and grows from there.) Following the magic number, the rows of the DAG should be written sequentially into the file, with no delimiter between rows and each unint32 encoded in little-endian format.(我也不知道n，还有'幻数'是个啥)

而以太坊创始人Vitalik Buterin自己说的是
Dagger是基于适度连接的有向非循环图（DAG，因此得名）的memory-hard proof of work，虽然远不是最佳的，但其比现如今其他的工作具有更强的memory-hardness特性。

实质上，Dagger算法的工作原理是创建一个有向无环图（其实就是数据结构里面 允许节点有多个父节点 的树），共有十个级别，包括根和总共225-1个值。

Dagger, a memory-hard proof of work based on moderately connected directed acyclic graphs (DAGs, hence the name), which, while far from optimal, has much stronger memory-hardness properties than anything else in use today.

Essentially, the Dagger algorithm works by creating a directed acyclic graph (the technical term for a tree where each node is allowed to have multiple parents) with ten levels including the root and a total of 225 - 1 values.

在github上以太坊项目里介绍挖矿里的DAG定义
...计算PoW（工作量证明）需要固定量resource的子集，量大小取决于随机数和块头。这个resource（几GB的大小的数据）被称为DAG。每30000块的间隔之间（一个100小时的窗口，称为epoch）DAG是完全不同的，需要一段时间才能生成。

...calculating the PoW (Proof of Work) requires subsets of a fixed resource dependent on the nonce and block header. This resource (a few gigabyte size data) is called a DAG. The DAG is totally different every 30000 blocks (a 100 hour window, called an epoch) and takes a while to generate.

在github项目上mining中的ethash-dag
用于工作证明算法的DAG（有向无环图）

在github项目中https://github.com/ethereum/wiki/wiki/Mining#the-algorithm
一个大的，暂时的，随机生成的数据库

下面稍微总结一下：DAG是Ethash算法描述中的“数据集”

1 存在一个种子，可以通过扫描块标题直到该点为每个块计算。
2 从种子中，可以计算一个16 MB的伪随机缓存。轻客户端存储缓存。
3 从缓存中，我们可以生成一个1 GB的数据集，其属性是数据集中的每个项目仅依赖于缓存中的少量项目。完整的客户和矿工存储数据集。数据集随时间线性增长。
4 挖掘包括抓取数据集的随机片段并将它们混合在一起。通过使用缓存重新生成所需数据集的特定片段，可以使用低内存完成验证，因此您只需要存储缓存。

1.There exists a seed which can be computed for each block by scanning through the block headers up until that point.
2.From the seed, one can compute a 16 MB pseudorandom cache. Light clients store the cache.
3.From the cache, we can generate a 1 GB dataset, with the property that each item in the dataset depends on only a small number of items from the cache. Full clients and miners store the dataset. The dataset grows linearly with time.
4.Mining involves grabbing random slices of the dataset and hashing them together. Verification can be done with low memory by using the cache to regenerate the specific pieces of the dataset that you need, so you only need to store the cache.