3
$\begingroup$

In Bitcoin proof-of-work, the difficulty of Proof-of-Work is estimated and calculated based on total hashing power of the participants. If total hashing power of the participants is higher, then PoW is more difficult.

  • If we use a Memory-Hard-Proof-of-Work scheme, the difficulty of Proof-of-Work is still estimated based on the hashing power ? OR based on the size of memory ?

  • In other word, is it feasible to design a Memory-Hard-Proof-of-Work scheme in which we could estimate the Pow difficulty based on the size of memory, instead of hashing power of participants ?

  • Has such a Memory-Hard-Proof-of-Work scheme designed yet by which we could estimate the difficulty based on memory size?

Just as an example: a Memory-Hardened Proof-of-Work Scheme: https://eprint.iacr.org/2017/1168.pdf

P.S. 1: Related question: Memory-hard proof-of-work: are they ASIC-resistant?

P.S. 2: If you need any further complementary explanation about the question, please let me know.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The measure of resource typically used to evaluate memory-hard functions is not the amount of work (i.e., $T$-complexity) but rather the space-time complexity (i.e., $ST$-complexity) of the computation. As the name suggests, it is the product of the maximum amount of space used and the time taken for the computation. (Strictly speaking, we have to also take in account amortization of the cost and the exact measure used is the cumulative space-time complexity, but the notion of space-time complexity still conveys the basic ideas: see [AS] for more details.) Good memory hard functions require $ST=\Theta(n^2)$.

The motivation behind this switch is to discourage the use of ASICs in computing proofs of work. The rationale of using ASICs in computing proofs of work is that they are much faster than CPUs. The speed-up is primarily due to its application-specificity, and the availability of large-scale parallelism. However, there is an asymmetry in the cost of memory (space, i.e.) as it is much costlier in ASICs compared to CPUs. Therefore, if one can construct a function that can be computed “fast” using “sufficient” space (even) on a sequential machine, but takes “more” time if the amount of space used is “lesser” (even with parallelism), then ASICs are not practical anymore as the increased cost of memory counteracts the increased computation power, but computing the function is cheap on a GPU.

Now, to your questions.

  • If we use a Memory-Hard-Proof-of-Work scheme, the difficulty of Proof-of-Work is still estimated based on the hashing power? OR based on the size of memory?

The amount of work considered is still in terms of the amount of hashing power, the role of the memory as explained above is just to discourage the use of ASICs.

  • In other word, is it feasible to design a Memory-Hard-Proof-of-Work scheme in which we could estimate the Pow difficulty based on the size of memory, instead of hashing power of participants?

There has been a lot of work in the recent years addressing this exact question --- the main motivation being that if space is used instead of work/time as a resource then there would be less energy wasted. The object is called a proof-of-space [D+,A+,F] and the prover/miner is rewarded for dedicating some disk space instead of doing work. (There is also a cryptocurrency, called Chia, that is being deployed based on proofs of space.)

[AS]: Alwen and Serbinenko. High Parallel Complexity Graphs and Memory-Hard Functions.

[A+] Abusalah et al. Beyond Hellman's Time-Memory Trade-Offs with Applications to Proofs of Space

[D+]: Dziembowski et al. Proofs of Space

[F]: Fisch. Tight Proofs of Space and Replication

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.