Difference between revisions of "Proof-of-X"

From IridiaWiki
Jump to navigationJump to search
 
(37 intermediate revisions by the same user not shown)
Line 1: Line 1:
  +
TODO: Read https://github.com/ethereum/wiki/wiki/Proof-of-Stake-FAQ
  +
 
= General =
  
= General =
   
  +
Goal: Reach consensus among untrusted agents and securely update the state (i.e., create a new block)
−
Goal: Secure updating of a state
  
   
  +
* Prevents Sybil attacks
−
Block time: trade off between time
 
  +
* 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
⚫
= Proof of Work =
  
  ⚫
<!-- * Miners choose one of all possible forks to contribute to (or splits among chains but with reduced efficiency per chain) -->
   
  +
== General algorithm ==
⚫
* Right to create new block: be the first to solve a puzzle based on consumption of a resource external to the system
  
⚫
* Miners choose one of all possible forks to contribute to (or splits among chains but with reduced efficiency per chain)
  
   
  +
# Collect transactions
⚫
== Light Clients ==
  
  +
# Calculate Merkle root
  +
# Try HASH(Merkle root, previous hash, nonce) with changing nonce values until value is smaller than target (based on difficulty)
  +
# Distribute solution
  +
  +
== Examples ==
  +
  +
* Bitcoin
  +
* Namecoin
  +
* Ethereum (plans to switch to Proof-of-Stake using the Casper protocol in the Serenity release; date is not known yet, maybe in 2017)
  +
  ⚫
== Light Client Algorithm ==
   
−
Algorithm:
  
 
# Download block headers from peers, consisting of:
  
# Download block headers from peers, consisting of:
 
##Merkle root
  
##Merkle root
 
## Hash value from previous block
  
## Hash value from previous block
 
## Nonce
  
## Nonce
−
# Verify proof-of-work for each block header: hash(Merkle root, previous hash, nonce) < target (based on difficulty)
 +
# Verify proof-of-work for each block header: HASH(Merkle root, previous hash, nonce) < target (based on difficulty)
 
# Consider longest chain (the one with the most work in it) as the true chain
  
# Consider longest chain (the one with the most work in it) as the true chain
   
Line 24: Line 39:
   
 
# (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)
  
# (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)
−
# Light client: Send request to a full node: "Please give me all partial Merkle branches that match the Bloom filter for the given block"
 +
# Light client: Send request to a full node: "Use the Bloom filter and give me all matching Merkle paths for a given block"
 
# Full node: Send the matching transactions and the other needed hashes from the Merkle tree to the light client (see, e.g., [http://orm-chimera-prod.s3.amazonaws.com/1234000001802/images/msbt_0705.png Merkle tree])
  
# Full node: Send the matching transactions and the other needed hashes from the Merkle tree to the light client (see, e.g., [http://orm-chimera-prod.s3.amazonaws.com/1234000001802/images/msbt_0705.png Merkle tree])
 
# 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
  
# 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
Line 33: Line 48:
 
* Depends on the willingness of full nodes to provide the requested information and they don't have an incentive to do it
  
* 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)
  
* 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)
−  
−
== Advantages ==
  
   
 
== Disadvantages ==
  
== Disadvantages ==
  +
* Economical footprint: huge amount of energy needed
  +
* Centralization: It i possible to own a majority of hashpower
  +
  ⚫
= 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/ :
  +
  +
# Potential blockmaker/signer: Put down security deposit for a long period of time
  +
# For each block: a function generates a random number R (in a deterministic manner based on information in the blockchain); based on this number and the deposit amount, the blockmaker and signers are selected (e.g., 1 blockmaker + 15 signers)
  +
# Blockmaker and signers potentially sign the block
  +
# Block header consists of:
  +
## hash of the previous block
  +
## list of signatures from the blockmaker and the signers
  +
## Merkle root
  +
# A block is valid if it is signed by the blockmaker and m out of n signers (e.g., 10 out of 15)
  +
# Blockmaker and signers get a small signing reward
  +
# 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)
⚫
= Proof of Stake =
  
  +
* Blackcoin
   
−
== Light Clients ==
 +
== Light Client Algorithm ==
   
  +
# Calculate random number R
−
== Advantages ==
  
  +
# Retrieve public keys of the blockmaker and the signers
  +
# Verify that the signatures in the blockheader belong to the public keys
   
 
== Disadvantages ==
  
== Disadvantages ==

Latest revision as of 01:29, 22 November 2016

TODO: Read https://github.com/ethereum/wiki/wiki/Proof-of-Stake-FAQ

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 using the Casper protocol in the Serenity release; date is not known yet, maybe in 2017)

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
  • Centralization: It i possible to own a majority of hashpower

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 (in a deterministic manner based on information in the blockchain); based on this number and the deposit amount, 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)
  • Blackcoin

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
Retrieved from "https://iridia.ulb.ac.be/w/index.php?title=Proof-of-X&oldid=7684"