Permacoin Implementation

Permacoin whitepaper describes how to use non-interactive Proof-of-Retrievability scheme to build a consensus protocol for a blockchain-based system thus repurposing miners work for data preservation. This article describes how Permacoin concept is implemented as Scorex module. Please note,there are some improvements known, e.g. Retricoin, and they are not considered for inclusion yet.

How Permacoin Is Implemented

All the Scala code implementing Permacoin is located within scorex-perma/src/main/scala/scorex/perma/consensus folder. Other parts of the module are describing storage, settings, API, network protocol additions. Functions are defined in PermaConsensusModule.scala. An algorithm is based on "Local-POR lottery"(Fig. 2, p. 7 in the paper) and works as follows:

1. Trusted system setup. No maximum-distance-separable encoding has been implemented. So trusted dealer just breaks dataset into n chunks and then builds . A Merkle tree root hash is then hardcoded into a node settings.

2. Mining setup. A miner chooses l chunk indexes to store by calculating i-th index as hash(pubKey ++ i) mod n, or in form of Scala code: BigInt(1, Hash(pubKey ++ BigInt(i).toByteArray)).mod(PermaConstants.n).toLong . Miner downloads chunks from the network.

3. Ticket generation. A ticket a result of one mining process iteration. It includes epoch-dependent puz value, iterable nonce value denoted as s, and k chunks of data along with Merkle proofs. Indexes of chunks and their order are depend on s and puz and so cannot be precomputed. Ticket is generated exactly as described in "Scratch-off" step of "Local-POR lottery", Scala code is there. To calculate puz value, we take hash(lastBlockId) (and lastBlockId is a signature of all the last block bytes except of its signature). In our implementation s length is fixed and set to 32 bytes.

4. Winning ticket determination. This is missed in the original paper so we had to develop own solution. To generate a ticket, a miner signs k hashes, where a hash depends on a corresponding chunk, puz, public key and a previous signature. A generated signature is then used to determine an index of a next chunk to be included into ticket. We use all the k signatures to determine ticket score by interpreting hash(signature1 ++ ... ++ signaturek) as a positive number. Then ticket is valid if its score is less than target.

5. Ticket validation. To validate block containing a ticket, every chunk included is to be checked by using its Merkle proof as well as every signature produced, puz, target and whether a ticket is winning. Validation is surely more costly than in Bitcoin, in particular, we need to calculate k*(h+1)+1 hashes(where h is Merkle tree height) and k signatures.

6. Difficulty and retargeting. Our Permacoin implementation has retargeting similar to Bitcoin, so each T blocks target changes to make average gap between blocks closer to planned one. The code for retargeting logic is there. Initial target is in each node settings.

7. Blockchain score. As well as Bitcoin after 0.1 we use not chain length, but a cumulative difficulty function. A score for a block having currentTarget is calculated as log2(initialTarget) - log2(target). Then blockchain score is a sum of all the scores of its blocks. The bigger score means the better chain.

We use Blake for hashing and Ed25519 for signing.

Possible Attack Vectors and Open Problems

1. Ed25519 vs FPS.

Testnet Constants

chunkSize = 1024 bytes
n = 1048576
l = 1024
k = 2
initialTarget = 7998056171325776434104437152907813376728872407881581793920540837651058889700
average delay between blocks = 15 seconds
retargeting every 50 blocks