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)

Algorithm:

Download block headers from peers, consisting of
- Merkle root
- Hash value from previous block
- Nonce
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
To find UTXOs:
- (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"
- Full node: Send the matching transactions and the other needed hashes from the Merkle tree to the light client (see, e.g., 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
- 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)