Initializing a graph for providing proof of space includes generating an initial graph at a device. The initial graph is acyclic. Content of a first node in the initial graph is generated based at least in part on (1) a predecessor node that is a predecessor of the first node and (2) on a godparent node. A position of the godparent node is based at least in part on content of the predecessor node. It further includes storing at least a portion of the initial graph on the device.