Proof of work and PoST proof generation

[iddo]

@iddo

The high-level idea of what I think is the best solution:

The above solution is insecure against an adversary that creates an alternative history. This is because we can only cancel the identity of the single creator of the k2pow, we cannot cancel those who buy the k2pow (because if we did then this single identity could equivocate in the future and thereby cancel many honest identities), and while denying the rewards in the current timeframe is indeed a countermeasure against imprudent miners that buy k2pow from a malicious identity, this countermeasture doesn’t work against an adversary that creates say an entire alternative history in secret.
Obviously we shouldn’t use this solution, because it’s pointless to make other parts of the protocol secure against an adversary (with 1/3 of the total spacetime resources) but be vulnerable to the such an adversary just because of k2pow delegation.

I think that the following is the only way to do k2pow delegation securely:

iddo (17 days ago, September 20, 2023)

1. After the PoET computation is done, the k2pow server Eve will accept out-of-band registrations from miners (each miner signs the PoET output + Eve’s identity + the requested k2pow difficulty threshold and the requested number-of-nonce-groups) and arranges these registrations in a merkle tree (just like the registrations to the PoET itself).

   • All the regitrations must be the leaf nodes (at the same height) of the merkle tree.

2. Eve then starts to compute k2pow values on input that include the root of this merkle tree.

3. The miner Bob is allowed to use Eve’s k2pow only by pointing to his index in an object which is a chain of Eve’s leaf nodes of the merkle tree (until reaching the first blank leaf).

   • This object is sync’d and kept in consensus.
   • Each identity Alice in this object is forced to pay to Eve’s acccount if the object contains the requested amount (according to Alice’s signature) of k2pow values with the proper difficulty threshold (when Eve accepted each registration, she made sure that Alice has enough locked money for k2pow payments)

4. If Bob registered to two such objects that are in consensus then his identity is canceled (no need to put an extra malfeasance proof into the consensus data, but aux hint is possible).

   • Example1: if Eve generated many such objects such that it each object has a chain of size=1 with only the same single identity, then the identity won’t be canceled by the energy usage for all the objects is same as no-delegation.
   • Example2: if Eve generated many such objects such that it each object has chain of size=2 that’s always Alice and Bob, then the object that Bob points to is w.h.p. diffrent than the object that Alice points to, so both Alice and Bob will be canceled.

Actually the Merkle tree is useless (because each honest miner registers to only one k2pow delegation service), so instead of the merkle root it should just be the hash of the of the list of all the “leaf nodes”,

Tal (16 days ago)
Interesting. It might work, although I’m not 100% sure. It’s critical that the registration object contains all of the registered identities themselves, so you can detect registration-equivocation (I think you were alluding to this when you said it can be a hash chain rather than a tree).I think might still be an attack, but it depends on whether there exists a bipartite graph family with certain properties. Here’s the attack parameterized by a specific graph G=(L,R,E)

• Eve has L identities
• She creates R registration objects, such that each object r\in R contains all the identities adjacent to r in the graph G
• She does R proofs of work.
• S\subset R is low-conflict subset if it doesn’t have many collisions in L (i.e., if we publish the registration objects in S, we don’t “burn” too many identities).
• Eve tries all the low-conflict subsets of R and publishes the best one.

The questions are: how many such subsets can there be, is the best one really better than just taking a single pow for all the identities, and if so, is there an efficient way to find it…

iddo (16 days ago)
Each object r is a predefined list of identities of L, but when Eve publishes r then only a subset of the identites in r are successful, and this subset is chosen randomly and independently (for example, each identity in r is successful with 80% probability).

• BTW if we the fee that each identity pays in according to how many k2pow values she wanted to buy (via her registration signature) then the problem is more complex, for example the identity Alice only wanted to pay for 64 nonces but the identity Bob wanted to pay for 160 nonces (the success will still be independent, but different, the success probability of Alice will be 80% and the success probability of Bob will be 98%)

As you say, the objective is to find S that covers the largest number of L successful identities (each identity that’s published twice is burned and therefore unsuccessful).

• The total number of objects that an identity Alice resides in measure the “happiness” of Alice (she can use less storage because she did the linear pass of the PoST proof generation with more potential nonces)

• In other words, the quality of the graph (from the point of view of the adversary) is higher an identity resides in many objects (the more the better).

If there are rivalries between the identities then the problem becomes more complex, in particular if Alice is will to pay a higher fee to become successful (a.k.a. neither burned nor unpublished) than Bob, then it can be regarded as the weighted variant of this optimization problem.I don’t think that such an adversary Eve will have any customers who just want to have many nonces while creating ballots for the honest mesh (there’s uncertaintly whether the customer will be burned after expending the effort to perform the linear pass), but if is a clandestine adversary that attempts a history reversal attack then it’s interesting to analyze whether she the advantage that she gets is significant or insignificant.

Tal (16 days ago)
Think of eve as a large pool. She fully controls everything, and “rivalries” are irrelevant…

iddo (16 days ago)
Regarding the efficiency,:

• Each object r can be just a single aggregated signature with a list of pubkeys (this already halves the size), if all the identities sign the same payload (i.e., they all pay for say 160 nonces).
• Furthermore, the encoding of this list of pubkeys can be just the delta relative to the previous epoch.
• So in the happy flow the entire data of Eve is just one object which is comprised of just a single signature and the delta of pubkeys relative to the previous epoch, and the k2pow values.