Challenges (bitcoin, script, keys, crypto etc.)

challenges.md

(parentheses + italics = commentary, questions on how these challenges are structured. obviously not intended to be in the text for the students.)

Challenge 1: The fees are all mine(d) (3/10)

(This challenge is focused on not needing any coding skills and just discussing/knowing basic bitcoin mechanisms)

Tx number	Fee /sats	Weight	Standard?	Consensus valid?	Spends from
1	58M	3.6M	✔️	✔️	4
2	10K	0.01M	✔️	✔️
3	10M	0.11M	❌	✔️	2
4	20M	0.5M	❌	✔️
5	20K	0.03M	✔️	✔️	1
6	0.01K	0.4M	✔️	✔️	5
7	0.12M	2.2M	✔️	✔️
8	0.11M	0.4M	✔️	✔️	7
9	0.65M	0.4M	✔️	❌
10	0.24M	0.4M	✔️	✔️	9

Terms: Weight : defined as (witness bytes + 4 * non-witness bytes). Hint: why is this important for mining a block?

Spends from (x) : means this transaction has an input which consumes an output from the other numbered transaction.

"Standard", "Consensus valid" : investigate what is the importance of a transaction being "standard" in bitcoin vs. a transaction being "consensus valid" (search on the internet!)

You are a miner of bitcoin, and these 10 are all the transactions available to you (in your "mempool").

Question : Which transactions do you choose to include in your block, and what is your overall block reward (in September 2024)?

Challenge 2: The transaction zoo (3/10)

(This is included, again, to allow progress for those who aren't able to do any coding; it just requires searching and understanding terminology)

Here is a list of transaction types:

1. Coinjoin transaction
2. Taproot spending transaction
3. Coinbase transaction
4. Transaction using OP_RETURN to inscribe data
5. Lightning channel open transaction
6. Lightning penalty (justice) transaction (they are rare!)
7. A transaction which has an output which you know for sure is of type "p2sh-p2wpkh".

Task: Find one example of each from the bitcoin blockchain and write down the transaction-id (txid) of each one.

(re: for sure - you have to provide evidence, in the form of another txid).

Challenge 3: Insecure nonce-sense (5/10)

(I put a lot of hand holding here to avoid, e.g., delving into BIP340 challenge construction details and x-only keys, way too much, I just want them to see the simple extraction of a key from nonce reuse. Also since I want to give people a chance that are not "math-freaks", I wrote some guidance on doing the division of (delta s)/(delta e)).

Here are two valid Schnorr signatures on my private key, for two different messages. They are formatted the same way as on the Bitcoin blockchain:

Sig A: d902ff7196ddc842ef5b4ea5d0aa17608e9b7f5f9a964ba1281cd432a7abe2e9 87f2c5c6f19d80ef12308a3e4ba10a91492feb4f37a1a5da48724fa86cff00d5

Sig B: d902ff7196ddc842ef5b4ea5d0aa17608e9b7f5f9a964ba1281cd432a7abe2e9 a861c9cff94fe4f715bc339a5962c9e7aebf018034a9d7a42cdf5e200f5b5f93

Do you notice something strange about these two signatures?

Background: The Schnorr signature 's' is calculated as:

s = (k + e * x) mod N

Here: N is the group order of secp256k1. k is the 'nonce'. And e is the 'hash challenge'. In bitcoin it is calculated with the formula in BIP340. For this challenge we will just give you the e values for each signature:

e for sig A: c5bd0b050471ec7820edeafdc94420d0216de07905aa3eb10782ba42cf22fa7

e for sig B: 28b9b2cea01bdddbc75258cf4603f6b57e46db2fdb9e38fdc454e0925998fe53

The values above are hexadecimal representations of integers.

Question : Can you find my private key? (Hint : if you can't see how, search for "nonce reuse" on the internet for more explanation)

Question (Optional) : What nonce did I use? What did i do wrong?

Hints: you need to be able to divide in modular arithmetic. For example, if you want to find the value of 7 / 3 in modulo 11, you need to find the modular inverse of 3 in mod 11, and then multiply the result by 7, mod 11. For that, in Python 3.8+ you can do:

y = pow(3, -1, 11)

.. while for other programming environments, you may need to search for the "Extended euclidean algorithm" or just "modular inverse".

Challenge 4: btc is not BITCOIN (5/10)

Step 1 Create a p2pkh (pay to public key hash) address ending in the character "b" (the fact that it's the end of the address is unusual, but shouldn't matter, even though this is the checksum portion; you just run the private key to address algo the same way, repeatedly)

Step 2 Create a p2sh-p2wpkh (so segwit wrapped with pay-to-script-hash) address ending in the two characters "tc"

Step 3 Explain why it's impossible to do the same for "BITCOIN" instead of "b" or tc" (Notice: impossible, not just difficult!).

(Scrap this! It's too complicated)(Optional) Step 4: how many sha2 calculations on average would you expect to run to generate a p2sh-p2wpkh address ending in the characters "btc"?

Challenge 5: Inscribe your name for eternity (7/10)

(This one requires some non-trivial setup, but is fairly easy for the students EXCEPT that they have to know how to craft and sign a transaction, given a privkey and a utxo; they could conceivably use tools to greatly simplify that, but they have to make an OP_RETURN output, so I guess not. Is that too hard?)

Here is a transaction on the signet blockchain, decoded into json for easier reading:

(provide the txid, then the json)

(Here we could make 1 transaction for each student group, perhaps 5 or more? Each transaction will have two outputs, both p2wpkh because that's the most 'vanilla' today)

In this transaction, the private key of the second output is:

SHA-256(the address of the first transaction)

Task: Find this private key then create a new transaction spending that (second output). Your new transaction should:

• pay a fee of between 1000 and 10000 sats
• have one output that is OP_RETURN and should encode your name(s)
• have one other output (so exactly 2 total) that is the change which should be returned to the first address

Then broadcast this transaction onto the signet network.

Hint: you can study OP_RETURN here (but do search for other info if you need it). This helpfully refers to examples, like this transaction: https://mempool.space/tx/6dfb16dd580698242bcfd8e433d557ed8c642272a368894de27292a8844a4e75 which has its third output as an OP_RETURN of the string "hello world".

Challenge 6: Odd one out (6/10)

(i originally thought about giving 5 "decoys", i.e. 'which one is unusual', but, this problem is hard enough; the critical thing is to give a guiding clue; I think the one I give here is reasonable)

Here is an address, holding a utxo (i.e. still unspent output) of type taproot:

bc1peyz0h83xfh9vqqymhhpj8jh9ze2quu4kys3u26x7c6s4djjcht9qrnd3ng

Investigate the utxo. There is something unique about it. What makes it unique amongst all the taproot utxos that exist?

Clue 1: why is it still unspent after a long time?

Clue 2: Think about the elliptic curve. (is this too easy?)

Challenge 7: Mallory's transaction

(Currently 'in limbo' since these can't be brcst; probably ditch it)

(I am going to have to prepare this non-taproot-spending signet tx in advance, but it's awkward because if anyone spends it it'll remove the ability for students to "check if valid". I guess we can just tell them to testmempoolaccept it and hope they do that?)

Clue: investigate what "malleated transaction" means in bitcoin.

Here is a hex-encoded fully-signed signet bitcoin transaction:

02....

Step 1: decode the transaction and describe its structure; describe the number and type of inputs and outputs.

Step 2: without knowing the private keys of the inputs, how can you change the transaction hex and still have the transaction be valid, i.e. you can have it confirmed in a block on signet? For full credit do this by making two different edits.

Step 3: Could you do step 2 if all the inputs are of type p2tr? Explain how you could, or why you could not.

Challenge 8: Insecure passwords (8/10)

(this first step is probably way too hard for anyone who hasn't even looked at taproot? i guess?)

Step 1: Create a taproot (p2tr) address that can be spent (or "unlocked") by providing the text "hunter2" as the preimage of the sha256 hash:

f52fbd32b2b3b86ff88ef6c490628285f482af15ddcb29541f94bcf526a3f6c7

Help: you need to make the 'script path spending' for the taproot spending be a script:

OP_HASH256 f52fbd32b2b3b86ff88ef6c490628285f482af15ddcb29541f94bcf526a3f6c7 OP_EQUAL

You can make the taproot internal key any value you like, but read BIP341 for a recommendation for cases where "key path spending" is not used. (todo: probably tell them what internal key to use, so there is one answer.)

Step 2: Explain why knowing the "password" (hunter2) is not enough to guarantee that you receive the money - even if no one else knows that secret password!.

Step 3: How do systems like the Lightning network prevent the problem described in Step 2?

Challenge 9: Half a puzzle (8/10)

(shamelessly cribbed from Greg Maxwell back in the day, but a way easier version. while it's "easy when you know how", actually arriving at that knowledge is absurdly arcane/obscure, so i put in a massive clue)

What is the private key for the public key:

0200000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63

Clue: what is half of a generator?

Notes for "Insecure nonce-sense":

Here is a dump of the part-random data I used to create this case:

privkey, as integer:  8717417697108723830302403292547906574814936478942302052750233322613099027783
and as hex:  0x1345e23166fb33e889c4e25c3089e99659486f9427c0143a7aa6b478ed4d5d47
R is:  CPubKey(x('03d902ff7196ddc842ef5b4ea5d0aa17608e9b7f5f9a964ba1281cd432a7abe2e9'))
Signature 0 is: 03d902ff7196ddc842ef5b4ea5d0aa17608e9b7f5f9a964ba1281cd432a7abe2e9 87f2c5c6f19d80ef12308a3e4ba10a91492feb4f37a1a5da48724fa86cff00d5
Signature 1 is: 03d902ff7196ddc842ef5b4ea5d0aa17608e9b7f5f9a964ba1281cd432a7abe2e9 a861c9cff94fe4f715bc339a5962c9e7aebf018034a9d7a42cdf5e200f5b5f93
Got e0:  0xc5bd0b050471ec7820edeafdc94420d0216de07905aa3eb10782ba42cf22fa7
Got e1:  0x28b9b2cea01bdddbc75258cf4603f6b57e46db2fdb9e38fdc454e0925998fe53

Signatures are of course (R, s). Maybe we should somehow emphasise more that it's about the fact that the first half of that string is the same in each case? no that's obvious enough!

Note I actually used sha256(R,m) as the challenge algo, before realising it was just too messy to include that, and instead just chose to give the reader the 'e' value directly.

The value of k that is repeated is 500.

Notes for "the transaction zoo"

This is perhaps not the best kind of challenge as it's a bit time consuming to verify answers, but, just in case it helps, here is a sample set of answers:

1 16a7c04139883d33997ed475918afcc4f54355478cb1737076cbb8b97c208316
2 https://mempool.space/tx/4b733bf77b59132d8b5473b77390c8137123815a87ab1cda546dcb0feed95aed
3 https://mempool.space/tx/879ca1c38e01528e908db1d4a83fd095fa80cd195535b7efb3fb4e55695cb095
4 https://mempool.space/tx/6dfb16dd580698242bcfd8e433d557ed8c642272a368894de27292a8844a4e75
5 https://mempool.space/tx/af3bc97316a29bc3cb958bc3c545059a61c9968d3944eaa715f71e34109eb8b1
6 https://mempool.space/tx/c5597bbe1f56ea72ae4b6e2835d69c1767c3ce1317da5352aa14dad8ed22df34

The last is definitely the trickiest because they can't just copy-paste findings from google; they need to look for a spending event that has a redeem script with 0 pushbytes_20 (i.e. in the corresponding input in the spending tx)

7 This: https://mempool.space/tx/be3c1a70dfcaa5c6c0cb2bbd2404ec93ede928b93b30fe41fce39af1c8b7ef40 which is the coinbase tx of block 750000 fits the bill, for example, since it's 0th output is spent in that way.

Notes for "Half a puzzle"

This was first published in the early days of blockstream by Greg maxwell, it is still up, here: https://blockstream.com/puzzle/

At least a trivial DDG search for that string does not, surprisingly, reveal the answer to the puzzle (edit: my bad, one link down from the reddit result gives you greg's detailed writeup here; I don't know if that really invalidates the challenge, because (a) they need to understand what the heck people are talking about in these threads, and (b) it does not contain a direct answer to the question (i.e. the private key)).

Just do (2^-1 mod n) * G and you get this pubkey. That privkey is therefore: 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1

The historical reason is something that's been debated ad infinitum in bitcoin circles, and not only: what is the origin of NIST's secp256k1 (and indeed secp256r1, which was extremely widely used in industry iirc)'s curve generator G? Though it has not been written down, it appears that some seed string was used to generate a hash value, call it 'h', and that hash value h was coerced-to-point, call it H, before doubling the point so that the generator G = 2H.

This logically explains why the above pubkey ("H") has a ridiculously low 256-88 = 168 bits, just above the 160 bits you might expect from say a sha1 output or something like that. (insert vague waffling: the incredible thing is that no one could tell us, even in like 2014, that info was lost!).