Mining algorithm: proof-of-retrievability

mquandallemquandalle FranceMember Posts: 50 ✭✭
Hi,

Despite the significant progress on the different implementations of ethereum clients (mainly C++ AlethZero and Go Ethereal), there is still one technical area where we miss a community consensus, and that's the mining algorithm. Different ideas have been raised: a "turing-complete proof-of-work", a "punitive proof-of-stake", or an hybrid system a la Peercoin.

I'd like to put in the discussion another possibility called proof-of-retrievability and presented in the Permacoin paper [0]. The distributed storage (named F in the white paper) could be used to store any arbitrary data (encrypted "distributed dropbox"). Maybe it would also be possible to modify the Permacoin protocol to store the unencrypted static source code of Ðapps (currently the paper assume that the data are encrypted). Also this is the first time I read about proof-of-retrievability/storage as a mining puzzle, but maybe other projects (Maidsafe?) have proposed a similar design.

I think this option is worth considering either as a standalone solution, or as part of an hybrid system along with proof-of-{work|stake|excellence|velocity|burn|...}.

[0]: http://cs.umd.edu/~amiller/permacoin.pdf

Comments

  • mquandallemquandalle FranceMember Posts: 50 ✭✭
    On June 15, Vitalik "answered" here: https://github.com/ethereum/wiki/wiki/Problems (paragraph 9).
  • JasperJasper Eindhoven, the NetherlandsMember Posts: 514 ✭✭✭
    Not sure what text in there you mean, quote it?
  • mquandallemquandalle FranceMember Posts: 50 ✭✭
    Here it is:

    Proof of excellence

    One interesting, and largely unexplored, solution to the problem of distribution specifically (there are reasons why it cannot be so easily used for mining) is using tasks that are socially useful but require original human-driven creative effort and talent. For example, one can come up with a "proof of proof" currency that rewards players for coming up with mathematical proofs of certain theorems. There is no generic algorithm, aside from brute force, for proving theorems, and yet proofs of theorems are theoretically computationally easy to verify: one simply needs to write every step of the proof in a formal language, allowing the use of only one inference rule (eg. a + b = b + a or a * (b + c) = a * b + a * c but not a * (b + c) = a * c + b * a) between each step, and having a program verify the correctness of the inferences at each step.

    For example, a proof of a common algebraic factorization problem appears as follows:
      a^2 - b^2
    = a^2 - a*b + a*b - b^2
    = a*a - a*b + a*b - b^2
    = a*(a - b) + a*b - b^2
    = a*(a - b) + a*b - b*b
    = a*(a - b) + b*a - b*b
    = a*(a - b) + b*(a - b)
    = (a + b)*(a - b)
    Each step of the proof can be verified using pattern matching algorithms, but it is much harder for a computer to figure out that the trick is to add and subtract a*b into the expression (technically, in this case specialized algorithms can do it, but in more general cases especially involving second-order logic it becomes intractable). Note that for computers the proof must be written down in excruciating detail; blockchain-based algorithms specifically heavily benefit from simplicity. To alleviate this problem, compilers can likely be made that can make small two and three-step inferences and expand shorter proofs into more complete ones.

    Alternatives to proof-of-proof include proof-of-optimization, finding optimal inputs to some function to maximize a particular output (eg. the ability of a radio antenna to receive signals), algorithms involving playing strategy games or multiplayer AI challenges (one can even require users to submit programs to the blockchain that play against each other), and solving a specific math problem at greater and greater difficulty (eg. factoring). Note that because success in these problems is very sporadic, and highly inegalitarian, one cannot use most of these algorithms for consensus; rather, it makes sense to focus on distribution.

    Problem: create a proof-of-excellence distribution mechanism that rewards solving problems that are both dominated by human effort and whose solutions provide some benefit to humanity.

    Additional Assumptions and Requirements
    • Given a well-justified extrapolation of the global levels of human and computer competence at the underlying problem, over 75% of the rewards from the system should be provided by human labor, although software aids are allowed.
    • The algorithm must ideally be future-proof; that is to say, it must continue rewarding value production in the long term and should not be an area that will eventually be "solved" completely.
    • The distribution should be maximally egalitarian, though this is a secondary concern.
    • The system should be secure against front-running attacks, ie. if an individual submits a solution, then it should not be practical for even a moderately powerful attacker to look at the solution and then resubmit his own transaction containing the same solution and thereby steal the reward.
    by Vitalik Butterin
  • nejucomonejucomo Member Posts: 40
    > Maybe it would also be possible to modify the Permacoin protocol to store the unencrypted static source code of Ðapps (currently the paper assume that the data are encrypted).

    Why not all transactions, plus a canonical encoding of the block's contract state, as well as all contract code? This would reward miners for being full nodes. If designed to incentivize storing full state, it may incentivize against mining pools. (I believe Vitalik mentioned this or something similar at the meetup last night.)
Sign In or Register to comment.