Permacoin: Repurposing Bitcoin Work for Data Preservation

Andrew Miller

Ari Juels

Elaine Shi

Bryan Parno

Jonathan Katz

IEEE S&P 2014

Bitcoin Mining is Expensive

- At least $80 Million spent in computing hardware

- At least 35 Megawatts (a hydroelectric powerplant)

- Bitcoin is an unusual p2p network.

- At its core is a computational “puzzle”

- In ordinary operation, Bitcoin consumes massive computational resources

- Requirements and security/incentive analysis are as-of-yet lacking

We propose an alternate construction of a puzzle with a beneficial side effect, that “recycles” some of the expense of the network.

- The beneficial side effect is a highly-fault tolerant, global decentralized archival storage, Permacoin.

- We state several requirements, and show that Permacoin satisfies them.

Permacoin

Goal: Repurposing Bitcoin Mining

Massively distributed, replicated storage system

Bitcoin

Why Mining?

1

2

5

4

3

Alice

Bob

?

?

?

?

?

?

?

Nontraditional assumptions: resource allocation, rationality

H(puz||pubkey||nonce) < target

Every ~10 minutes

Bitcoin Puzzle:

expensive by design, proxy for identity?

Incentives Matter

Mining is expensive! So why participate at all?

1st order: Power 2nd: Hardware 3rd: R&D

Answer: Rewards (fees/inflation)

Security relies on predictable user responses to incentives

Assumptions:

large number of independent users

no large coalitions

Minimal Puzzle Requirements

1. Difficult: no shortcuts

2. Fair: even a participant with a very small budget has a proportional chance of winning

H(puz||pubkey||nonce) < target

[Miller et al. 2014, manuscript]

“Scratch-off” Puzzles

Bitcoin Puzzle:

everyone knows what a puzzle is

Useful Puzzles are Hard to Find

…. while preserving Bitcoin’s security and incentive structure

Natural choices for “useful” puzzles:

- Protein folding, SETI@Home, finding prime numbers

Challenges:

a) incentive argument: must be “public good” or else subsidizes an attacker

b) randomly selected instances aren’t hard

c) randomly selected instances aren’t useful

Kroll, Davies, Felten, WEIS 2014

Permacoin: Our approach

Puzzle integrated with “Proofs of Retrievability”

Work is still intrinsically useless, but recycled

Jakkobson and Juels, 1999

Permacoin: Features

- Storage: a large public dataset (e.g. Library of Congress)

optionally, users can submit their own data to archive

- Recoverability: even after catastrophic failure

- Diversity: geographical, as well as administrative

Like Amazon Glacier…

Cheap to store, but expensive to recover

Permacoin: High Level Design

1. Setup: erasure code a *full entropy* file F

Erasure Coding

F

Original Dataset

Dealer

Miner

Miner

Miner

...

...

Puzzle solution

2. KeyGen: users generate keypairs

and fetch random subsets of segments

3. Mining: users attempt to find winning puzzle solutions. Each attempt requires accessing locally stored segments.

Proofs of Retrievability (PoR)

Server (untrusted) proves to Client that it stores the file F

1. Random sample of “challenges”

2. Erasure coding

3. Merkle tree over the file

4. Non-interactive

F0

F1

F2

F3

F4

F5

F6

F7

Juels and Kaliski, 2007

Note - to summarize what a Proof of retrievability is, some intuition.

Strawman (PoR-based puzzle)

3. Each mining attempt:

a) Select a random nonce r

b) h1 := H(puz | pk | r )

1. Build a Merkle tree, where each leaf is a segment of the file

F0

F1

F2

F3

F4

F5

F6

F7

F1

F2

F4

F5

F2

F4

Each *Attempt* requires responding to a challenge.

If less than a constant fraction stored, must perform

exponential work.

This satisfies the puzzle requirements.

2. Generate a public signing key pk, which determines a random subset of file segments

F1

F2

F4

F5

F2

F4

d) h2 := H(puz | pk | r | segments)

e) Winner if h2 < 2^(-d)

(d is difficulty parameter)

c) h1 selects k segments from subset

too much text here

Problem: Outsourced Storage

Users might hire a server to store data

Result: less diversity

New requirement: discourage centralization

$

$

Miner

Miner

Idea: Local PoR Puzzle

- Bake a “signing” step into the puzzle

- Mining requires knowledge of secret key

- Knowledge of secret key can be used to

spend (or steal!) the reward

Local PoR puzzle

c) h1 selects a random segment from subset

For k iterations:

c.1) SIGN(segment) using secret key

c.2) select random next iteration

F1

F2

F4

F5

F2

F4

F0

F1

F2

F3

F4

F5

F6

F7

F1

F2

F4

F5

*In general, signature schemes aren’t sufficient.

F2

F4

d) h2 := H(puz | pk | r | segments | sigs)

e) Winner if h2 < 2^(-d)

(d is difficulty parameter)

1. Build a Merkle tree, where each leaf is a segment of the file

2. Generate a public signing key pk, which determines a random subset of file segments

Skippable details

“Floating Preimage Signature”

Secret key (leaves)

σ4,0

σ4,1

σ1,0

σ2,0

σ2,1

σ3,0

σn,0

σn,1

...

q=k leaves revealed during attempt

4q’ more leaves selected

Public key

(Merkle root)

σ1,1

Based on BIBA, Perrig et al.,

and others….

any q’ of these revealed

to claim reward

σ3,1

Possible Mining Configurations

Miner

Local Mining: good!

Trusted Cloud: deterred

Miner

$

$

Miner

Miner

Miner

Miner

data

data

Cloud assisted mining: economic argument

Local vs Remote Storage

Effective cost per attempt ($USD x10-5)

k (x1000 puzzle iterations)

Choosing Fair Parameters

“Small” players should have a proportional chance of winning

This depends on mining hardware configuration

Assume ASIC +RAM/SSD

with balanced throughput

Micro Benchmark Example

Storage goal:

200+ TB of storage

Assumption:

$80 million spent on mining equipment

Validation cost:

6 seconds to validate a day’s worth (144) of puzzle solutions

Future Work

Forthcoming:

- Formally justify the requirements of Scratch-off puzzles

- “Outsource resistance” - what happens to mining pools?

Longer term:

- User-submitted updates:

Idea: butterfly-network erasure code, dynamic PoR

- Incentivize serving requests for individual file segments

Shi et al. 2013

Conclusion

Permacoin

An archival storage system “for free” by recycling Bitcoin work

Can store 200+ terabytes based on current participation

Leaves Bitcoin’s security and incentive structure intact

Thank you for listening!

more resilient and diverse than amazon glacier

Role of Puzzles in Bitcoin? (1/3)

Bank

Alice: $10

Bob: $20

Ledger

Alice

Bob

“Send $2 from my account to Bob.”

“You’ve got Money! $2 from Alice.”

Alice: $08

Bob: $22

Checking Account Service

The Bitcoin network provides a very simple functionality

Role of Puzzles in Bitcoin? (2/3)

Alice

Bob

P1

P2

P5

P4

P3

Standard Distributed Network

Fixed set of N participants, with pairwise authenticated channels.

Strong setup assumption!

Permacoin - Oakland 2014 (2) - Google Slides