Proof-of-X

General

Goal: Reach consensus among untrusted agents and securely update the state (i.e., create a new block)

• Prevents Sybil attacks
• Gives incentive for participation
• Distributes block generation among the participants in a semi-random manner

Proof-of-Work

Idea: Solve a puzzle based on consumption of a resource external to the system

General algorithm

1. Collect transactions
2. Calculate Merkle root
3. Try HASH(Merkle root, previous hash, nonce) with changing nonce values until value is smaller than target (based on difficulty)
4. Distribute solution

Examples

• Bitcoin
• Namecoin
• Ethereum (plans to switch to Proof-of-Stake)

Light Client Algorithm

1. Download block headers from peers, consisting of:
   1. Merkle root
   2. Hash value from previous block
   3. Nonce
2. Verify proof-of-work for each block header: HASH(Merkle root, previous hash, nonce) < target (based on difficulty)
3. Consider longest chain (the one with the most work in it) as the true chain

To find UTXOs:

1. (optional) Light Client: Build Bloom filter for the desired transaction (a Bloom filter allows for testing set membership; it can have false positives but no false negatives)
2. Light client: Send request to a full node: "Use the Bloom filter and give me all matching Merkle paths for a given block"
3. Full node: Send the matching transactions and the other needed hashes from the Merkle tree to the light client (see, e.g., Merkle tree)
4. Light client: Calculate hash for the transaction, combine with other needed hashes until the Merkle root is reached, check that the Merkle root matches the one from the previously downloaded block headers

The link from the transaction to the Merkle root shows that a transaction is indeed contained in a block; the requested block is linked to the rest of the blockchain via the PoW; the combination of both links proves that the transaction is recorded in the blockchain (received data: about 1KB instead of 1MB for a entire block)

Problems:

• Depends on the willingness of full nodes to provide the requested information and they don't have an incentive to do it
• Full nodes can fool light clients and can say that a transaction is not included in a block (but they can not say that a transaction is included in a block when in fact it is not)

Disadvantages

• Economical footprint: huge amount of energy needed

Proof-of-Stake

Idea: Prove ownership of a certain amount of currency

General algorithm

see https://blog.ethereum.org/2015/01/10/light-clients-proof-stake/ :

1. Potential blockmaker/signer: Put down security deposit for a long period of time
2. For each block: a function generates a random number R; based on this number, the blockmaker and signers are selected (e.g., 1 blockmaker + 15 signers)
3. Blockmaker and signers potentially sign the block
4. Block header consists of:
   1. hash of the previous block
   2. list of signatures from the blockmaker and the signers
   3. Merkle root
5. A block is valid if it is signed by the blockmaker and m out of n signers (e.g., 10 out of 15)
6. Blockmaker and signers get a small signing reward
7. If blockmakers or signers try to sign a block that it not on the main chain, they get explicitly punished

Examples

Nxt (initial distribution of tokens: fundraising via Bitcoin)

Light Client Algorithm

1. Calculate random number R
2. Retrieve public keys of the blockmaker and the signers
3. Verify that the signatures in the blockheader belong to the public keys

Disadvantages

• Nothing at stake: Miners (voters) can vote on all forks of a blockchain

Proof-of-Retrievability

Idea: Prove local, random access to a copy of a file

Examples

Permacoin