Is there any documentation to visualize example of the original DAG graph that Ethereum generates?

Question

Directed Acyclic Graph (DAG) is well explained here. On Vitalik Buterin's Dagger algorithm's link, the image does not show up. I assume it shows the example of 9 level DAG graph.

In levels 1 through 8, the value of each node depends on three nodes in the level above it, and the number of nodes in each level is eight times larger than in the previous. In level 9, the value of each node depends on 16 of its parents, and the level is only twice as large as the previous;

[Q] Is there any documentation to visualize example of the original DAG graph (showing the 9 level and node's connection between each other) that Ethereum generates?

Thank you for your valuable time and help.

score 0 · Answer 1 · edited Dec 22 '17 at 14:51

This is the best image I could find to help visualize what is happening.

If you keep this in mind then look at the next image you should at least start to be able to visualise what is going on.

Here is a good read.

This is taken directly from Ethereum, if you read it you can almost visualise what it describes.

Essentially, it starts off a graph as a single node, sha3(seed), and from there starts sequentially adding on other nodes based on random previous nodes. When a new node is created, a modular power of the seed is computed to randomly select some indices less than i (using x % i above), and the values of the nodes at those indices are used in a calculation to generate a new a value for x, which is then fed into a small proof of work function (based on XOR) to ultimately generate the value of the graph at index i. The rationale behind this particular design is to force sequential access of the DAG; the next value of the DAG that will be accessed cannot be determined until the current value is known. Finally, modular exponentiation is used to further hash the result.

This is the actual code that builds the DAG Graph in python

def produce_dag(params, seed, length):
    P = params["P"]
    picker = init = pow(sha3(seed), params["w"], P)
    o = [init]
    for i in range(1, length):
        x = picker = (picker * init) % P
        for _ in range(params["k"]):
            x ^= o[x % i]
        o.append(pow(x, params["w"], P))
    return o

Whats is the complexty to access each Page_N? Is it O(1) or O(n) ? I guess since DAG is created as a tree worst case it should be O(log(n)) ? Those page memories shouldn’t be consequences I assume. @Lismore — alper, Dec 21 '17 at 05:32
Shouldn’t be 9 levels in the DAG on the image? Thank you for your well written answer but my real question was related to: how to represent 9-level DAG? but you just show DAG as a sequential array. @Lismore — alper, Dec 21 '17 at 05:35

Is there any documentation to visualize example of the original DAG graph that Ethereum generates?

1 Answers1