Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS595 / IS795 Homework 2

Due electronically via Gradescope, Thursday February 12 11:59pm

Submission Instructions

Please submit to Gradescope. All answers must fit in the provided solution box. You may either use LaTeX (recommended and encouraged) or handwrite your solutions legibly. There are 100 points total in this assignment. The final question (worth 0 points) requires you to acknowledge use of AI and external resources.

Important: Points will be deducted from submissions that fail to answer this final question.

1 UTXO Model (40 points)

We will start by developing a deeper understanding of Bitcoin’s Unspent Transaction Output (UTXO) model while analyzing both blockchain data and pending transactions. Your task is to manually track the UTXO set, calculate individual balances, and analyze why certain transactions have been left out of blocks.

The UTXO Model and Transaction Structure

Recall that the Bitcoin blockchain follows the Unspent Transaction Output (UTXO) model. In this model, the funds belonging to one wallet are not stored in a single account balance, but rather in a series of “unspent transactions”, each of which represents funds that have been sent to that wallet but not yet spent. To make a transaction, a wallet must prove ownership over one or more unspent transactions (called inputs), and create one or more new unspent transactions (called outputs), sending the funds to the recipient(s). Naturally, the total value of all output transactions must not exceed the total value of all input transactions. Once a UTXO is “spent”, i.e. included as an input for some transaction, miners will enforce that it can never appear in a future block. This ensures that funds can never be spent more than once.

Coinbase Transactions The exception to all the above is what’s called the coinbase transaction. This is a special transaction included in every block – it’s always the first transaction. As a reward for creating a new block, the node that created it (the miner ) can claim some newly produced bitcoin for themselves (currently, the rate is 3.125 BTC per new block). The coinbase transaction sends this reward to the miner’s wallet. Since these newly-minted coins do not come from prior transactions, coinbase transactions do not have any input UTXOs.

In this homework, we will represent Bitcoin transactions in the following format:

• Transaction ID: A unique identifier for the transaction

• Inputs: An array of inputs, each of which contains the following:

– Previous Output Reference: The transaction ID of a previous UTXO (unspent transaction output)

– scriptSig: A digital signature proving ownership of the above UTXO

• Outputs: An array of outputs, each of which will designate a new UTXO. Each output contains the following:

– Amount: The value (in BTC) transferred.

– scriptPubKey: A locking script specifying the recipient’s public key.

For this assignment, assume that all scriptPubKeys are of type pay-to-public-key (P2PK). When we write “Public key of Alice” we mean the binary string representing Alice’s public key.

The Mempool

The mempool is a set of pending transactions that have been generated but not yet included in any block. There is no single, universally agreed-upon mempool (i.e., the consensus covers the chain of blocks, but not the mempool). Each node in the network maintains its own set of unconfirmed transactions, and these sets can vary from one node to another. In this assignment, we are examining the mempool of a specific node.

Problem Setup

Suppose the current state of the blockchain (as established by the consensus mechanism) is as follows:

Block 0

• Transaction TX0 (Coinbase):

– Inputs: None

– Outputs:

0. (10 BTC, OP PUSH [Public key of Alice] OP CHECKSIG)

Block 1

• Transaction TX1 (Coinbase):

– Inputs: None

– Outputs:

0. (10 BTC, OP PUSH [Public key of Alice] OP CHECKSIG)

• Transaction TX2:

– Inputs:

0. UTXO: (TX1, Output 0), scriptSig: Valid signature valid under Alice’s public key

– Outputs:

0. (6 BTC, OP PUSH [Public key of Bob] OP CHECKSIG)

1. (4 BTC, OP PUSH [Public key of Carol] OP CHECKSIG)

Block 2

• Transaction TX3 (Coinbase):

– Inputs: None

– Outputs:

0. (10 BTC, OP PUSH [Public key of Carol] OP CHECKSIG)

• Transaction TX4:

– Inputs:

0. UTXO: (TX2, Output 0), scriptSig: Valid signature under Bob’s public key

– Outputs:

0. (2 BTC, OP PUSH [Public key of David] OP CHECKSIG)

1. (4 BTC, OP PUSH [Public key of Bob] OP CHECKSIG)

• Transaction TX5:

– Inputs:

0. UTXO: (TX2, Output 1), scriptSig: Valid signature valid under Carol’s public key

1. UTXO: (TX3, Output 0), scriptSig: Valid signature valid under Carol’s public key

– Outputs:

0. (12 BTC, OP PUSH [Public key of David] OP CHECKSIG)

1. (2 BTC, OP PUSH [Public key of Alice] OP CHECKSIG)

Problems

Problem 1.1. (6 points)

The UTXO set is the set of all unspent transaction outputs in the entire blockchain. For example, after processing (just) Block 0 there is one unspent transaction, and the UTXO set looks like:

Transaction ID       Output Index

TX0                      0

What is the UTXO set after processing Block 1?

Problem 1.2. (10 points) What is the UTXO set after processing Block 2? Explain how the inputs and outputs of TX4 affect the UTXO set.

Problem 1.3. (8 points) Calculate the total coins spendable by each individual (Alice, Bob, Carol, David) after block 2.

Problem 1.4. (10 points)

Suppose that immediately after Block 2 is confirmed, Bob wants to send 3 BTC to Carol with no transaction fee. Write a transaction that accomplishes this.

Problem 1.5. (6 points)

Suppose the current state of the mempool is as follows:

• Transaction TX6:

– Inputs:

0. UTXO: (TX0, Output 0), scriptSig: Valid signature under Alice’s public key

– Outputs:

0. (5 BTC, OP PUSH [Public key of David] OP CHECKSIG)

1. (5 BTC, OP PUSH [Public key of Alice] OP CHECKSIG)

• Transaction TX7:

– Inputs:

0. UTXO: (TX2, Output 0), scriptSig: Valid signature under Bob’s public key

– Outputs:

0. (1 BTC, OP PUSH [Public key of Carol] OP CHECKSIG)

1. (5 BTC, OP PUSH [Public key of David] OP CHECKSIG)

• Transaction TX8:

– Inputs:

0. UTXO: (TX5, Output 0), scriptSig: Valid signature under Carol’s public key

– Outputs:

0. (12 BTC, OP PUSH [Public key of Bob] OP CHECKSIG)

For each transaction in the mempool, determine if it is valid or invalid. If it is invalid, explain why. (You may ignore the hypothetical transcation of problem 5. Assume Block 2 is the most recent confirmed block.)

2 Bitcoin Scripting Language (60 points)

In Bitcoin, transactions are not authorized by simple account balances but by a stack-based scripting language called Script. Every transaction output has a locking script, and every input has an unlocking script.

• scriptPubKey (Locking Script): A script placed on an output (UTXO) that defines the conditions under which these funds can be spent. It effectively “locks” the funds.

• scriptSig (Unlocking Script): A script provided in the input of a spending transaction. It produces the data (signatures, public keys, etc.) needed to satisfy the locking script.

To validate a transaction, the network concatenates the unlocking script and the locking script:

scriptSig ∥ scriptPubKey

The script is executed sequentially on a stack. If the execution completes successfully and the top item on the stack is TRUE (non-zero), the transaction is valid.

Digital Signatures & The Message

Standard Bitcoin scripts rely on digital signatures—a type of electronic signature used to show that someone who generated a public key is “signing” a particular message.

There is a signature verification algorithm that takes three inputs: a Message, a Signature, and a Public Key. The algorithm returns TRUE if and only if:

1. The signature was created using the Private Key corresponding to the given Public Key.

2. The signature was created specifically for that exact Message.

If the message changes by even one bit, the signature becomes invalid.

What is the Message?   In the context of a Bitcoin transaction, the “message” being signed is a hash of the spending transaction itself.

• The signer takes the transaction they are creating (inputs, outputs, amounts).

• They modify it slightly (e.g., emptying the scriptSig fields) to prevent infinite recursion.

• They hash this modified transaction data.

This ensures that the signature is inextricably bound to this specific payment.

Common Scripts   In class, we saw the following two standard script types.

1. Pay-to-Public-Key (P2PK): The funds are locked to a specific public key. To spend, one provides a signature.

2. Pay-to-Public-Key-Hash (P2PKH): The funds are locked to the hash of a public key (a Bitcoin address). To spend, one provides the public key and a signature.

Notation & Stack Rules

• Stack Representation: We represent the stack as a list growing to the right.

– The Rightmost element is the Top (where items are added/removed).

– The Leftmost element is the Bottom.

– Example: In the stack A, B, a pop operation would remove and return B.

• Pushing Data: We use square brackets to denote data being pushed onto the stack. For example, [Alice] means “push the public key of Alice onto the stack.”

• Operations: Words starting with OP (e.g., OP ADD) are operations. They pop items from the top of the stack, perform a calculation, and push the result back.

• Success: If the execution completes without error and the top item on the stack is non-zero (True), the transaction is valid.

Opcode Reference

Use the following definitions for the problems below:

• OP DUP: Duplicates the top item on the stack. (Stack: x → x, x)

• OP HASH160: Pops the top item, hashes it (SHA256 followed by RIPEMD160), and pushes the result.

• OP EQUAL: Pops the top two items. If they are identical, pushes 1 (True); otherwise pushes 0 (False).

• OP EQUALVERIFY: Same as OP EQUAL, but if the result is False, it immediately halts and fails the transaction. (Consumes both items).

• OP ADD: Pops the top two items (a, b), adds them (a + b), and pushes the result.

• OP MUL: Pops the top two items (a, b), multiplies them (a · b), and pushes the result.

• OP CHECKSIG: Pops a Public Key (pk) and a Signature (sig). Implicitly calculates the transaction hash (msg) and validates the signature. Pushes 1 if valid, 0 otherwise.

• OP SWAP: Swaps the top two items on the stack. (x, y → y, x)

• OP BOOLOR: Pops two items. If either (or both) are non-zero, pushes 1. Otherwise pushes 0.

• OP GREATERTHAN: Pops b first, then pops a second. Pushes 1 if a > b, and 0 otherwise.

• OP IF / OP ELSE / OP ENDIF: The top item is popped off of the stack. If this item is non-zero, the IF branch is taken; if it is zero, the ELSE branch is taken.

Example Trace

In Table 1, we show an example of how to trace the script: [3] [4] OP ADD [7] OP EQUAL

Operation    Stack

Push 3          3

Push 4          3, 4

OP ADD        7

Push 7          7, 7

OP EQUAL     1

Table 1: Stack Execution Trace

Problem 2.1. (16 points)

Context: Digital signatures do not just prove ownership of a private key; they authorize a specific message.

In Bitcoin, that “message” is the hash of the transaction being created.

Suppose Alice holds a UTXO locked with a standard P2PK script:

scriptPubKey: [PubK A] OP CHECKSIG

The Setup:

1. Alice creates a transaction Talice sending coins to Bob. Alice creates a digital signature σ as Bitcoin’s protocol prescribes. In transaction Talice, Alice sets scriptSig accordingly. This transaction is then sent to multiple nodes.

2. Eve sees Alice’s transaction before it’s confirmed on the blockchain, and modifies it so that the coins are sent to herself. She submits this new transaction Teve using the original scriptSig containing σ.

Your Task: Trace the stack execution for the two scenarios below and explain what OP CHECKSIG does in both scenarios.

Scenario A: The network validates Talice.

Scenario B: The network validates Teve.

Problem 2.2. (24 points)

Consider a UTXO locked with a mysterious custom script. This script contains two Public Keys.

• scriptPubKey: [PubK A] OP CHECKSIG OP SWAP [PubK B] OP CHECKSIG OP BOOLOR

A user creates a transaction TA to spend this output with the following scriptSig, containing valid signa-tures, with respect to this transaction TA, for both public keys.

• scriptSig: [Sig A] [Sig B]

Your Tasks

1. Is transaction TA valid? Explain why or why not.

2. Construct two variants of TA, which we will call TB and TC , that differ only in their scriptSig. Both TB and TC should be different valid transactions. Explain why they are valid.

3. Suppose both TB and TC are broadcast to the network simultaneously. Can both transactions be permanently confirmed on the blockchain? Explain the mechanism that resolves this situation.

Problem 2.3. (20 points)

You are trying to spend a UTXO locked with a mysterious script.

scriptPubKey: OP DUP OP DUP OP MUL OP MUL 83 OP ADD 595 OP EQUAL

Find a scriptSig that makes this transaction valid. Trace the execution to prove your answer.

3 Acknowledgment of AI and external resources

Problem 3.1.   (0 points) Please provide links to external references you used for this portion of the assignment and any prompts, session links or session copies for substantial use of generative AI, or attest that you did not use any external resources.

NOTE: Five points will be deducted for all submissions that fail to answer this question.