Proof-of-X

From IridiaWiki
Jump to navigationJump to search

General

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

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)


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
  • Ethereum (plans to switch to Proof-of-Stake)

Light Clients

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)

Advantages

Disadvantages

  • Economical footprint: huge amount of energy needed

Proof-of-Stake

Examples

Nxt (initial distribution of tokens: fundraising via Bitcoin)

Light Clients

Advantages

Disadvantages

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