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 a 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(lastBlockPuz ++ lastBlockS) (so puz and s values from a previous block). 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(currentTarget). 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. While original paper suggests to use special hash-based FPS signature scheme to protect against work outsourcing, we use Ed25519. ECDSA could be a worse choice because of possible precomputation. Follow the description of ECDSA from wikipedia : The cost of signing is dominated by the single scalar multiplication, step 4, (x1,y1) = k * G. This step is entirely independent of the message being signed, and can therefore be precomputed. With Ed25519 we still have some open questions:

   • amortize the cost of attempting very many scalar multiplications at once
   • store a larger and larger lookup table that facilitates signing
   • get a significant advantage doing scalar multiplication in hardware
   • selectively discard attempts after computing just the hash, in order to only actually do scalar multiplication on the "easy" solutions

2. There is no a requirement for chunks to be unique in a subset. It gives a possibility for a miner to minimize storage costs by iterating over public keys to find a most compact subset.

3. It is hard or maybe even impossible to find a subset size to throw not throw individual miners away and prevent big players to store a subset in RAM at the same time. With a subset being stored fully in RAM, it is about computational work only then with an ability to parallelize it and build efficient special hardware. So we're getting back to Bitcoin-like centralization.

Testnet Constants

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

Acknowledgement

Permacoin Scorex module was implemented by kushti and catena2w. The original paper was done by Andrew Miller, Ari Juels, Elaine Shi, Bryan Parno and Jonathan Katz. Special thanks to Andrew Miller for discussions on the paper. In particular, concerns around ECDSA/Ed25519 usage stated in "Possible Attack Vectors and Open Problems" section were raised by Andrew. The development was sponsored by IOHK.