Difference between revisions of "Proof-of-X"

From IridiaWiki
Jump to navigationJump to search
Line 15: Line 15:
 
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 28: Line 28:
 
# 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
   
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)
+
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:
 
Problems:

Revision as of 22:20, 21 November 2016

General

Goal: Secure updating of a state

Block time: trade off between time


Proof of Work

  • 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)

Light Clients

Algorithm:

  1. Download block headers from peers, consisting of
  • Merkle root
  • Hash value from previous block
  • Nonce
  1. Verify proof-of-work for each block header: hash(Merkle root, previous hash, nonce) < target (based on difficulty)
  2. 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: "Please give me all partial Merkle branches that match the Bloom filter for the 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)

Advantages

Disadvantages

Proof of Stake

Light Clients

Advantages

Disadvantages

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