Table of Links
Abstract and 1. Introduction
-
Volunteer Computing
-
PNPCoin
3.1 Blockchain Integration and 3.2 Bounded Complexity
3.3 Runtime Authority and 3.4 Back-compatibility
-
Use case – Cellular Docking
-
Conclusion and References
3.1 Blockchain Integration
The PNPCoin proposal aims to replace the SHA256 hashing function at the core of Blockchain technology with useful computations. Instead of calculating the hash function of a randomized input, a one-way jash function is distributed at every block, and calculated instead of the hash. As in the original, results are shared by nodes communicating the hash of the blockchain, transactions are signed by new owners private keys, and timestamps are performed by distributed voting by proof-of-work.
The jash replaces the hash only in the proof-ofwork step. In order to achieve greater granularity than powers of two as Bitcoin does, the jash meta can contain an upper bound on the arg (eg.: n = 16 and max(arg)=47’000).
3.2 Bounded Complexity
Nested recursion among functions can be flattened into a single recursive function, and all recursive functions can be converted into unbounded loops. Loops which terminate after an unpredictable number of steps are replaced with for loops with a fixed upper bound, and a break statement is added for early termination. Figures 2 and 3 demonstrate this concept for the Collatz conjecture:
3.3 Runtime Authority
While Runtime Authority resources are available via peer to peer file hosting shared by research institutions and volunteers, the content is aggregated according to rules outlined here, a review process, and additional rules created by a committee. This
structure is similar to IANA, which manages Internet resources [2].
Each submitted jash is validated by checking whether it compiles, and estimating mean runtime and deviation by performing runs on random inputs. The functions are prioritized according to upper bound complexity (calculated at compile time), the upper bound time complexity, data size d, average and deviation runtime estimates, importance (0 to 1), and a veto to prevent malicious use. All but the last two criteria are fully automated, allowing fast turnaround.
There are two modes of execution for jash functions: full and optimal. Optimal execution accepts the lowest res, that is, the result with most leading zeros. Full execution returns the output of every valid input to the RA, and the reward is distributed evenly across all first submissions of results. The RA is also responsible for providing a reference node implementation.
3.4 Back-compatibility
In order to satisfy the requirements for a Soft Fork, the proposed system is compatible with the current SHA-256 hashes. For all historic blocks, the RA will publish jash functions containing the SHA256 hashes with fixed input, and empty meta files. In the future event that candidates are unavailable for computation, these Classic problems (SHA-256 hashes) will be published.
The RA aggregates all outputs of all sequences.
:::info
Author:
(1) Martin Kolar, Brno University of Technology (kolarmartin@fit.vutbr.cz).
:::
:::info
This paper is available on arxiv under CC BY 4.0 DEED license.
:::
