This project implements the Proofs Sequential Work (PoSW) protocol construction defined in Simple Proofs of Sequential Work, which can be used as a proxy for Proof of Elapsed Time (PoET). We follow the paper's definitions, construction and are guided by the reference python source code implementation.
The executable package in this repository is the PoET service, which harness the core protocol in order to provide proving services to multiple clients, with amortized CPU cost. It is designed to be used by the Spacemesh network and is part of the broader Spacemesh protocol.
For more information, visit the PoET protocol specification.
Since the project uses Go 1.11's Modules it's best to place the code outside your $GOPATH. Read this for alternatives.
git clone https://github.com/spacemeshos/poet.git
cd poet
go build./poet --genesis-time=2022-08-09T09:21:19+03:00 --epoch-duration=60s --cycle-gap=5s--genesis-time is set according to RFC3339.
./poet --configfile=$PWD/sample-poet.conf./poet --helpgo test ./...Section numbers in Simple Proofs of Sequential Work are referenced by this spec.
t:int = 150. A statistical security parameter. (Note: is 150 needed for Fiat-Shamir or does 21 suffices?). Shared between prover and verifier
w:int = 256. A statistical security parameter. Shared between prover and verifiers
n:int - time parameter. Shared between verifier and prover
Note: The constants are fixed and shared between the Prover and the Verifier. Values shown here are just an example and may be set differently for different POET server instances.
x: {0,1}^w = rndBelow(2^w - 1) - verifier provided input statement (commitment)
N:int - number of iterations. N := 2^(n+1) - 1. Computed based on n. For the purposes of the implementation N is determined after running poet for a specific amount of time.
m:int , 0 <= m <= n. Defines how much data should be stored by the prover.
M : Storage available to the prover, of the form (t + nt + 1 + 2^{m+1})w, 0 <= m <= n . For example, with w=256, n=40, t=150 and m=20 prover should use around 70MB of memory and make N/1000 queries for openH.
Hx : (0, 1)^{<= w(n+1)} => (0, 1)^w . Hx is constructed in the following way: Hx(i) = H(x,i) where H() is a cryptographic hash function. The implementation should use a macro or inline function for H(), and should support a command-line switch that allows it to run with either H()=sha3() or H=sha256().
φ : (phi) value of the DAG Root label l_epsilon computed by PoSW^Hx(N)
φP : (phi_P) Result of PoSW^Hx(N) stored by prover. List of labels in the m highest layers of the DAG.
γ : (gamma) (0,1}^{t*w}. A random challenge sampled by verifier and sent to prover for interactive proofs. Created by concatenation of {gamma_1, ..., gamma_t} where gamma_i = rnd_in_range of (0,1)^w
τ := openH(x,N,φP,γ) proof computed by prover based on verifier provided challenge γ. A list of t tuples, where each tuple is defined as follows for 0 <= i < t: {label_i, list_of_siblings_to_root_from_i }. So, for each i, the tuple contains the label of the node width identifier i, as well as the labels of all siblings of the nodes on the path from the node i to the root.
NIP (Non-interactive proof): a proof τ created by computing openH for the challenge γ := (Hx(φ,1),...Hx(φ,t)). e.g. without receiving γ from the verifier. Verifier asks for the NIP and verifies it like any other openH using verifyH.
verifyH(x,N,φ,γ,τ) ∈ {accept, reject} - function computed by verifier based on prover provided proof τ.
The core data structure used by the verifier.
We define n as the depth of the DAG. We set N = 2^(n+1)-1 where n is the time param. e.g. for n=4, N = 31
We start with Bn - the complete binary tree of depth n where all edges go from leaves up the tree to the root. Bn has 2^n leaves and 2^n -1 internal nodes. We add edges to the n leaves in the following way:
For each leaf i of the 2^n leaves, we add an edge to the leaf from all the direct siblings of the nodes on the path from the leaf to the root node.
In other words, for every leaf u, we add an edge to u from node v{b-1}, iff v{b} is an ancestor of u and nodes v{b-1}, v{b} are direct siblings.
Each node in the DAG is identified by a binary string in the form 0, 01, 0010 based on its location in Bn. This is the node id
The root node at height 0 is identified by the empty string ""
The nodes at height 1 (l0 and l1) are labeled 0 and 1. The nodes at height 2 are labeled 00, 01, 10 and 11, etc... So for each height h, node's id is an h bits binary number that uniquely defines the location of the node in the DAG
We say node u is a parent of node v if there's a direct edge from u to v in the DAG (based on its construction)
Each node has a label. The label li of node i (the node with id i) is defined as:
li = Hx(i,lp1,...,lpd)` where `(p1,...,pd) = parents(i)For example, the root node's label is lε = Hx(bytes(""), l0, l1) as it has 2 only parents l0 and l1 and its id is the empty string "".
Given a node i in a DAG(n), we need a way to determine its set of parent nodes. For example, we use the set to compute its label. This can be implemented without having to store all DAG edges in storage.
Note that with this binary string labeling scheme we get the following properties:
1001 is 10001011 is 101If id has n bits (node is a leaf in DAG(n)) then add the ids of all left siblings of the nodes on the path from the node to the root, else add to the set the 2 nodes below it (left and right nodes) as defined by the binary tree Bn.
So for example, for n=4, for the node l1 with id 0, the parents are the nodes with ids 00 and 01 and the ids of the parents of leaf node 0011 are 0010 and 000. The ids of the parents of node 1101 are 1100, 10 and 0.
Note that leaf nodes parents are not all the siblings on the path to the root from the leaf. The parents are only the left siblings on that path. e.g. siblings with ids that end with a 0.
Recursive computation of the labels of DAG(n):
Please use a binary data file to store labels and not a key/value db. Labels can be stored in the order in which they are computed.
Given a node id, the index of the label value in the data file can be computed by:
idx = sum of sizes of the subtrees under the left-siblings on path to root + node's own subtree.The size of a subtree under a node is simply 2^{height+1}-1 * the label size. e.g. 32 bytes.
arbitrary length bytes. Verifier implementation should just use H(commitment) to create a commitment that is in range (0, 1)^w . So the actual commitment can be sha256(commitment) when w=256.
A challenge is a list of t random binary strings in {0,1}^n. Each binary string is an identifier of a leaf node in the DAG.
Note that the binary string should always be n bytes long, including trailing 0s if any, e.g. 0010.
A proof needs to include the following data:
So, for example for DAG(4) and for a challenge identifier 0101 - The labels that should be included in the list are: 0101, 0100, 011, 00 and 1. This is basically an opening of a Merkle tree commitment.
The complete proof data can be encoded in a tuple where the first value is φ and the second value is a list with t entries. Each of the t entries is a list starting with the node with identifier_t label, and a node for each sibling on the path to the root from node identifier_t:
{ φ, {list_of_siblings_on_path_to_root_from_0}, .... {list_of_siblings_on_path_to_root_from_t} }
Note that we don't need to include identifier_t in the proof as the identifiers needs to be computed by the verifier.
Also note that the proof should omit from the siblings list labels that were already included previously once in the proof. The verifier should create a dictionary of label values keyed by their node id, populate it from the siblings list it receives, and use it to get label values omitted from siblings lists - as the verifier knows the ids of all siblings on the path to the root from a given node.
a NIP is a proof created by computing openH for the challenge γ := (Hx(φ,1),...Hx(φ,t)). e.g. without receiving γ from the verifier. Verifier asks for the NIP and verifies it like any other openH using verifyH. Note that the prover generates a NIP using only Hx(), t (shared security param) and φ (generated by PoSW(n)). To verify a NIP, a verifier generates the same challenge γ and verifies the proof using this challenge.
Hx(φ,i) output is w bits but each challenge identifier should be n bits long. To create an identifier from Hx(φ,i) we take the leftmost t bits - starting from the most significant bit. So, for example, for n == 3 and for Hx(φ,1) = 010011001101..., the identifier will be 010.
The verifier only stores up to m layers of the DAG (from the root at height 0, up to height m) and the labels of the n leaves. Generating a proof involves computing the labels of the siblings on the path from a leaf to the DAG root where some of these siblings are in DAG layers with height > m. These labels are not stored by the prover and need to be computed when a proof is generated. The following algorithm describes how to compute these siblings:
For each node_id included in the input challenge, compute the node id of the node n. The node on the path from node_id to the root at DAG level m
Construct the DAG rooted at node n. When the label of a sibling on the path from node_id to the root is computed as part of the DAG construction, add it to the list of sibling labels on the path from node_id to the root
When we hash 2 (or more) arguments to hash, for example Hx(φ,1). We need to agree on a canonical way to pack params across implementations and tests into 1 input bytes array. We define argument packing in the following way:
Hx(φ,i) = Hx([]byte(φ) ... []byte(i))