– Transactions, blocks,
4 network, mining
Transactions, blocks,
blockchain
Copyright By PowCoder代写 加微信 powcoder
Bitcoin transaction example
“version”: 1, “locktime”: 0, “vin”: [
“txid”: “7957a35fe64f80d234d76d83a2a8f1a0d8149a41d81de548f0a65a8a999f6f18”, “vout”: 0,
“scriptSig” :
“3045022100884d142d86652a3f47ba4746ec719bbfbd040a570b1deccbb6498c75c4ae24cb02204b9f039ff08df09c be9f6addac960298cad530a863ea8f53982c09db8f6e38130484ecc0d46f1918b30928fa0e4ed99f16a0fb4fde0735e 7ade8416ab9fe423cc5412336376789d172787ec3457eee41c04f4938de5cc17b4a10fa336a8d752adf”,
“sequence”: 4294967295 }
], “vout”: [
“value”: 0.01500000,
“scriptPubKey”: “OP_DUP OP_HASH160 ab68025513c3dbd2f7b92a94e0581f5d50f654e7
OP_EQUALVERIFY OP_CHECKSIG” },
“value”: 0.08450000,
“scriptPubKey”: “OP_DUP OP_HASH160 7f9b1a7fb68d60c536c2fd8aeaa53a8f3cc025a8
OP_EQUALVERIFY OP_CHECKSIG”, }
• UTXO: unspent transaction output.
• A transaction usually creates one or two UTXOs.
• A transaction input must be an UTXO of an existing transaction on blockchain.
• When used as input, an UTXO is completely consumed. (Why?)
• As far as account balance is concerned, it suffices to keep track of the collection of all UTXOs. (Why?)
• Why not keep track of credits/debits of accounts as banks do?
• By keeping track of the UTXO pool, there is no need to go through the entire chain to verify a transaction.
transaction
Transaction output
Two parts:
• an amount, denominated in satoshis,
• a cryptographic puzzle, also known as a locking script, a
witness script, or a scriptPubKey.
“scriptPubKey”: “OP_DUP OP_HASH160 ab68025513c3dbd2f7b92a94e0581f5d50f654e7 OP_EQUALVERIFY OP_CHECKSIG”
“value”: 0.01500000,
Transaction input
• Use a pointer to an UTXO by reference to the transaction hash.
• The unlocking script should satisfy the spending conditions set in the UTXO.
• Most often, the unlocking script is a digital signature and public key proving ownership of the bitcoin.
Transaction fees
• = the total input amount – the total output amount.
• Up to the sender.
Compensate the miners.
Make transaction spams costly.
• Miners prioritize transactions based on fees, wait times, etc.
• The fee typically increases with the transaction size (number of bytes) and network congestion level.
• Third-party fee estimation service makes suggestions (depending on how long the sender is willing to wait).
Transaction scripts
• A simple stack-based execution language with a set of operators (arithmetic, logic, throwing errors, returning early, crypto, …).
• A locking script resides in each output.
• An unlocking script resides in each input.
• To validate a transaction, the unlocking script in each input is executed alongside the corresponding (output) locking script to see if the spending condition is satisfied.
• Stateless.
• Conditional flow control. No loops.
• Execution time is predictable.
• Not Turing complete (unlike that of Ethereum).
A toy script
• Locking script:
3 OP_ADD 5 OP_EQUAL
• Unlocking script 2
• Used by most transactions.
• Redeemably by the owner of a key with the specified hash.
• E.g., locking script for paying a cafe:
OP_DUP OP_HASH160
Unlocking script:
hash (P2PKH)
Addresses, balances
• Total received: sum of all outputs with P2PKH locking script that contains the 160-bit hash of the public key.
• Final balance: sum of all current UTXO referencing the public key hash.
• More complex scripts are ignored here.
Multisignature
• M
• To protect against losing a key.
• To allow complicated contracts (e.g., escrows, a lawyer
executing a will, etc).
• Side note: There is a bug in CHECKMULTISIG’s execution – it will pop an extra value or one value more than expected. It is costlier to fix (requires a hard fork) than to work around.
• A notable feature added in 2012.
• Pay-to-Script-Hash: Send coins to the hash of this script.
• Greatly simplifies the use of complex transaction scripts.
• The script is needed to unlock.
• Complex script without P2SH
• Complex script as P2SH
hash (P2SH)
Locking Script
2 PubKey1 PubKey2 PubKey3 PubKey4 PubKey5 5 CHECKMULTISIG
Unlocking Script
Redeem Script
2 PubKey1 PubKey2 PubKey3 PubKey4 PubKey5 5 CHECKMULTISIG
Locking Script
HASH160 <20-byte hash of redeem script> EQUAL
Unlocking Script
Sig1 Sig2
Proof of burn
• A script that can never be redeemed.
• One use is to bootstrap an alternative to bitcoin—one need to
destroy one’s bitcoin in order to gain altcoins.
• May use OP_RETURN to throw an error and ignore the remaining script (an opportunity to put arbitrary data here).
• nLocktime defines the earliest time a transaction is valid and can be relayed on the network or added to the blockchain.
• nLocktime = 0 means immediate propagation and execution.
• Check Lock Time Verify (CLTV) added in 2015: Per output
Flow control in scripts
<30 days> CHECKSEQUENCEVERIFY DROP
<90 days> CHECKSEQUENCEVERIFY DROP
0
A hash chain of blocks
Each block has
• a block header,
• a hash pointer to the previous block, and
• a hash pointer to transaction data.
Tree of transactions
• To prove a transaction is included in a specific block of N transactions, one provides a path through the tree.
• One only verifies the hashes along that path (with O(log N) complexity) in lieu of verifying the hash of the entire block (with O(N) complexity).
(Duplicate the last hash to an even number of leaf nodes when necessary.) “+” in the graph means concatenation, not addition.
tree construction
Blockchain
Block header
• 80 bytes.
• Version number.
• A hash of the previous block’s header (aka hash pointer);
• A timestamp;
• Difficulty (nBits).
• The only transaction data included in the header is the root of the transaction tree—mrkl_root;
• A nonce chosen by the miner;
• The nonce is such that the hash of the current header begin with some number of zeros.
• The first transaction in a block;
• It always has a single input and a single output;
• The input doesn’t redeem a previous output and thus contains a null hash pointer, since it is minting new bitcoins and not spending existing coins;
• The output value is the miner’s revenue from the block. It consists of two components:
o a flat mining reward (6.25 BTC today), which is set by the system and which halves every 210,000 blocks (about 4 years), and
o the transaction fees collected from every transaction included in the block;
• There is a special “coinbase” parameter, which is completely arbitrary — miners can put whatever they want in there.
transaction
• Block reward is how new bitcoins are created.
• Runs out in around 2040.
• No new bitcoins from then on unless rules change.
Total supply: 21 million
First inflection point:
reward halved from 50BTC to 25BTC
Total bitcoins in circulation
Linking blocks
• When a miner mines a block of its own, its previousblockhash field points to the previous block;
• A block always points to a single parent;
• When a node receives a new block, its previousblockhash field is expected to point to the previous block; (What to do if not?)
distributed consensus
peer network,
• All peers are equal in the sense that none has more authority than others; (like bittorrent)
• Typically a node has direct connection to a small subset of nodes (called its peers);
• “Flat” mesh network topology;
• This is in contrast to the server-client network architecture;
• Some peers may have more computational or networking
resources than others;
• In a permissionless system, nodes are free to join or leave; to follow or not follow the default protocol; to form alliances or collude.
Broadcasting transaction
• When Alice wants to pay Bob, she makes a transaction to Bob’s address and broadcasts the transaction to all peers.
• Bob need not be involved at all.
peer (P2P) network
signed by to pkBob : H( )
Consensus is hard
• Nodes need to agree on which transactions are valid and in what order.
• Each node has its own ledger (a blockchain) and a pool of outstanding transactions yet to be included or discarded.
• Nodes’ views are generally (somewhat) different.
• Nodes may crash.
• Some nodes may even be adversarial (or malicious).
• Network limitations:
o Not all pairs of nodes are connected; o Faults in network;
o No notion of global time.
Implicit consensus
• In each round, a random node is picked.
• This node proposes the next block in the chain.
• Other nodes (implicitly) accept/reject this block by either o extending it, or
o ignoring it and extending chain from earlier block.
• Every block contains hash of the block it extends.
Consensus algorithm
simplified, in discrete rounds)
1. New transactions are broadcast to all nodes;
2. Each node collects new transactions into a block;
3. In each round a random node – called a proposer – is selected by a random oracle to broadcast its block;
4. Other nodes accept the block only if all transactions in it are valid (unspent, valid signatures);
5. Nodes express their acceptance of the block by including its hash in the next block they create.
Double spending
signed by A
PaytopkB :H( )
Honest nodes will extend the longest valid branch. Protection against double-spending hinges on consensus.
signed by A
PaytopkA’ :H( )
Incentiviz
Everything so far is just a distributed consensus protocol; But now we utilize the fact that the currency has value.
Rewards of coinbase and transaction fees become consensus only if the block is included in the consensus blockchain.
Can we reward nodes
that created these blocks?
Can we penalize the node that created this block?
Longest chain protocol
Where should the mined block hash-point to?
Blockchain may have forks
because of network delays
because of adversarial action
Longest chain protocol
attach the block to the leaf of the longest chain in the block tree what if two equal length chains?
Remaining problems
• How to pick a random node?
• How to avoid a free-for-all due to rewards?
• How to prevent Sybil attacks? (If pseudonymous identities are
cheap, then create a large number of identities and use them to gain a disproportionally large influence.)
Proof of work
• To approximate selecting a random node: select nodes in proportion to a resource that no one can monopolize (we hope).
• In proportion to ownership: proof of stake.
• In proportion to computing power: proof of work. o Select nodes in proportion to computing power; o Let nodes compete for right to create block;
o Make it moderately hard to create new identities. o Adopted by bitcoin and many other systems.
Hash puzzles
To create block, find nonce s.t.
H(nonce ‖ prev_hash ‖ merkle_root ) is sufficiently small.
Output space of hash
nonce prev_h
Target space
Recall: If the cryptographic hash function is puzzle friendly, the only way to succeed is to try enough nonces until you get lucky.
How many times? What kind of random variable is this?
PoW compute
property 1: difficult to
In Jan. 2023, of the order of 1023 hashes are computed on average to produce a block.
Current total network hash rate: 2 x 1020 H/s.
Only some nodes bother to compete — miners.
PoW parameterizable
property 2: cost
Nodes automatically re-calculate the target every two weeks.
Goal: The average time between blocks = 10 minutes
Prob (Alice wins next block) = fraction of global hash power she controls
Nonce must be published as part of block
Other miners simply verify that
H(nonce | prev_hash | merkle_root(tx,…,tx) ) < target
property 3: trivial to verify
Key security assumption
Attacks infeasible if majority of miners weighted by hash power follow the protocol.
Mining economics
Complications:
• fixed vs. variable costs
• reward depends on global hash rate
If mining reward (block reward + Tx fees)
hardware + electricity cost
Block difficulty
• The hash of any valid block must be below a mining target.
• The mining target/threshold (in hexadecimal):
0000000000000000172EC0000000000000000000000000000000000000000000 (March 2015) 0000000000000000000ed0eb0000000000000000000000000000000000000000 (Sept. 2021)
• Today, only one in about 1023 nonces that you try will be successful.
• Difficulty of a block:
Block_difficulty = 1/mining_target
Why variable difficulty?
Total hash rate increases rapidly with price and technological advances. About 10 orders of magnitude increase in 10 years.
Bitcoin protocol
(a) The mining difficulty changes every 2016 blocks
next_difficulty = (previous_difficulty * 2016 * 10 minutes) / (time to mine last 2016 blocks) (b) Adopt the heaviest chain instead of the longest chain
chain_difficulty = sum of block_difficulty
(c) Allow the difficulty to be adjusted only mildly every epoch
1⁄4 < next_difficulty/previous_difficulty < 4
Bitcoin has
• Value • State • Rules
types of consensus
Bitcoin is bootstrapped
security of block chain
health of mining ecosystem
value of currency
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com