Creator

Matteo Campanelli

Created

May 22, 2023 7:40 AM

Space-Hardness Assumption

Note: We will only focus on base step computation review and we will postpone the review on protocol constructions.

A general theoretical treatment

One could conceive a completely new design for PoS that does not use SHA, but some other type of cost assumptions. These costs assumptions could consist of, e.g.,:

• pairing
• VDFs
• multiscalar exponentiations (MSM), actually used in Aleo; see also here
• FFTs
• VCs

NB: the current document is a general treatment of this flavor of alternative assumptions. That means that there could be specific assumptions, such as VDFs which are easier to exploit. VDF exploration is still in progress.

We need to answer two questions in order to use them:

What is a way to abstract these objects and how could one use them to build Po(U)S?

Let’s work out the first part the question, first. Let’s take the assumption in Aleo as a study case for example:

if a party has only limited preprocessing time it will have to spend time $T_B$ to compute a batch of MSMs of size B.

Each MSM can be described as an oracle $O(\cdot)$ whose cost is somewhat non amortizable. It can be seen as a proof of (useful) work. (It is “useful” because MSMs have their usage in larger systems such as SNARKs, so this output can be used in a proof system for example).

Now that we have the abstraction, we could ask: how can we use it to build PoS?

There are additional difficulties here: how do we go from work to space?

One way to do that could be through the following design, partly based on the designs already in PoS. Take a graph (e.g. SDR) and replace its parent-child relationship with something else.\

Right now the parent-child relationship is

child = H(parents[child]) (1)

We could make it become

child = O(parents[child]) (2)

in order to instead use the oracle O. The advantage of this could be that the oracle O (an MSM) is quite algebraic and its costs are lower in a SNARK (compared to SHA).

However, (2) is not quite secure: this type of graphs need a random oracle property when going from parents to children (that is what SHA provides). We could then change it to this :

child = H(O(parents[child])) (3)

It may still be an improvement because now the size of the hashed object is quite smaller.

NB: we need to use the fact that O is a CRHF for security.

The security is not immediate and may be only heuristical. For example one could need to answer the following (which is possibly false):

Q: Can one argue that H(O( )) is a RO for an easier proof of security?

(One could also consider the opposite order:

child = O(H(parents[child]))

• pro: here it is easier to argue that the parents are absolutely necessary for computation
• con: one is losing efficiency (we are just adding cost)

)

Bottom line on cost assumptions:

• There seems to be a high risk and low reward in exploring this now.
• It would require substantial effort on:
• properly abstracting the approach and proving its security
• this would be a completely different paradigm of PoS
• finding an assumption that might offer both the security we are looking for and the efficiency gains we are hoping for
• the probability of finding a good assumption is probably low and uncertain:
• we could find an assumption with an external canary potentially (e.g. the assumption in Aleo)
• but none of these look as well-established and reliable as SHA and its main canary, bitcoin
• even if we found a promising assumption, what is the probability we assign to an assumption staying promising
• At the current stage, more concrete and familiar directions seem like a better bet
• we can explore this new flavor of PoS after we have a new stable PoS
• Other bottom lines/questions:
• the one in the text could be used as a way to leverage PoW to obtain PoS
• what are we obtaining concretely as an improvement here?
• The problem of assumption remains:
• what underlying assumptions are we confident enough to base ourselves on?