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) Build Bloom filter for the desired transaction (a Bloom filter allows for testing set membership; it can have false positives but no false negatives)
- Send request to a full node: "Please give me all partial Merkle branches that match the Bloom filter for the given block"
- Full node sends the matching transactions and the other needed hashes from the Merkle tree (see, e.g., Merkle tree)

Problem: Depends on the willingness of full nodes to provide the requested information and they don't have an incentive for doing so