Cryptography: Projects

(Deadline: 10:00am, 2025-01-17)

Finish one project from Project One, Project Two and Project Three. Submit your source codes. If you submitted source codes for > 1 projects, TAs may arbitrarily choose one and grade it.

1 Project One (100 points)

In this project, you will implement the garbled circuit based protocol for computing GE(a, b), where a = a2a1a0 ∈ {0, 1} 3 and b = b2b1b0 ∈ {0, 1} 3 . The implementation should contain

(1) a procedure that takes a boolean circuit of GE(a, b) as input and outputs a garbled circuit of GE(a, b); and

(2) a procedure that takes a garbled circuit of GE(a, b) and a set of input labels as input, evaluates the garbled circuit, and produces an output label.

For simplicity, you do not need to implement OT. Instead, you may ask Alice to directly send the labels corresponding Bob’s input bits to Bob.

Hints. Given a length-preserving PRF H : {0, 1} n × {0, 1} n → {0, 1} n, the function G : {0, 1} n → {0, 1} 2n defined by G(k) = Hk(1)∥Hk(2) is a length-doubling PRG. For simplicity, you may define a keyed function F : {0, 1} n × {0, 1} n → {0, 1} 2n as follows

Fk(x) = G(Hk(x)), ∀k, x ∈ {0, 1} n

and use F as the length-doubling PRF. You may choose DES (n = 64) or AES (n = 128) as H.

2 Project Two (100 points)

In this project you will design a single-server private information retrieval (PIR) system that allows a client to privately retrieve any item xi from a database x = x1 . . . xn such that

(1) The client’s retrieval index i ∈ {1, . . . , n} remains secret for the database server;

(2) The client only needs to communicate O(n 1/3) Paillier ciphertexts with the database server;

(3) The client learns no information about other database items, i.e., {xj : 1 ≤ j ≤ n, j ≠ i}.

Note that the PIR system in lecture 21 requires the client to communicate O(n 1/2) Paillier ciphertexts with the server and so does not satisfy (2); the system does not satisfy (3), even if the client is honest.

Hints. You may represent the database as a cube {Xu,v,w : u, v, w ∈ {1, . . . , n1/3}}; let the client send three query vectors to the server; and let the server compress the whole database into a constant number of Paillier ciphertexts that contain no information about {xj : 1 ≤ j ≤ n, j ≠ i}.

3 Project Three (100 points)

In this project, you will gain experience creating transactions using the BlockCypher testnet blockchains and Bitcoin Script. This project consists of 3 questions, each of which is explained below. The starter code we provide uses python-bitcoinlib, a free, low-level Python 3 library for manipulating Bitcoin transactions.

3.1 Project Background

3.1.1 Anatomy of a Bitcoin Transaction

Figure 1: Each TxIn references the TxOut of a previous transaction, and a TxIn is only valid if its scriptSig outputs True when prepended to the TxOut’s scriptPubKey.

Bitcoin transactions are fundamentally a list of outputs, each of which is associated with an amount of bitcoin that is “locked” with a puzzle in the form. of a program called a scriptPubKey (also sometimes called a “smart contract”), and a list of inputs, each of which references an output from the list of outputs and includes the “answer” to that output’s puzzle in the form. of a program called a scriptSig. Validating a scriptSig consists of appending the associated scriptPubKey to it, running the combined script. and ensuring that it outputs True.

Most transactions are “PayToPublicKeyHash” or “P2PKH” transactions, where the scriptSig is a list of the recipient’s public key and signature, and the scriptPubKey performs cryptographic checks on those values to ensure that the public key hashes to the recipient’s bitcoin address and the signature is valid.

Each transaction input is referred to as a TxIn, and each transaction output is referred to as a TxOut. The situation for a transaction with a single input and single output is summarized by Figure 1 above.

The sum of the bitcoin in the unspent outputs to a transaction must not exceed the sum of the inputs for the transaction to be valid. The difference between the total input and total output is implicitly taken to be a transaction fee, as a miner can modify a received transaction and add an output to their address to make up the difference before including it in a block.

For the first 3 questions in this project, the transactions you create will consume one input and create one PayToPublicKeyHash output that sends an amount of bitcoin back to the testnet faucet. For these exercises, you will want to take the fee into account when specifying how much to send and subtract a bit from the amount in the output you’re sending, say 0.001 BTC (this is just to be safe, you can probably include a fee as low as 0.00001 BTC if your funds are running low). If you do not include a fee, it is likely that your transaction will never be added to the blockchain. Since BlockCypher (see Section 3.1.3) will delete transactions that remain unconfirmed after a day or two, it is very important that you include a fee to make sure that your transactions are eventually confirmed.

3.1.2 Script. Opcodes

Your code will use the Bitcoin stack machine’s opcodes, which are documented on the Bitcoin wiki [1]. When composing programs for your transactions’ scriptPubKeys and scriptSigs you may specify opcodes by using their names verbatim. For example, below is an example of a function that returns a scriptPubKey that cannot be spent, but rather acts as storage space for an arbitrary piece of data that someone may want to save to the blockchain using the OP RETURN opcode.

def save_message_scriptPubKey(message):

return [OP_RETURN,

message]

Examples of some opcodes that you will likely be making use of include OP_DUP, OP_CHECKSIG, OP_EQUALVERIFY, and OP_CHECKMULTISIG, but you will end up using additional ones as well.

3.1.3 Overview of Testnets

Rather than having you download the entire testnet blockchain and run a bitcoin client on your machine, we will be making use of an online block explorer to upload and view transactions. The one that we will be using is called BlockCypher, which features a nice web interface as well as an API for submitting raw transactions that the starter code uses to broadcast the transactions you create for the exercises. After completing and running the code for each exercise, BlockCypher will return a JSON representation of your newly created transaction, which will be printed to your terminal. An example transaction object along with the meaning of each field can be found at BlockCypher’s developer API documentation at https://www.blockcypher.com/dev/bitcoin/#tx. Of particular interest for the purposes of this project will be the hash, inputs, and outputs fields. Note that you will be using only one test network (“testnet”) for this project: the BlockCypher testnet for question 1-3. These will be useful in testing your code. As part of these exercises, you will request coins to some addresses (more details below).

3.2 Getting Started

1. Download the starter code from the course website, navigate to the directory and run pip install -r requirements.txt to intall the required dependencies. For this project, ensure that you are using Python 3. If you are not using a Python virtual environment, you must do two things differently. First, use pip3 instead of pip to install packages to Python 3. Second, use the python3 command to run scripts instead of python to run with the Python 3 interpreter.

2. Make sure you understand the structure of Bitcoin transactions and read the references in the Recommended Reading section below if you would like more information.

3. Read over the starter code. Here is a summary of what each of the files contain:

lib/split_test_coins.py:

You will run this script. to split your coins across multiple unspent transaction outputs (UTXOs). You will have to edit this file to input details about which transaction output you are splitting, the UTXO index, etc.

lib/config.py:

You will modify this file to include the private keys for your users. Note that you will make a web request to generate my_private_key. There are comments in config.py and instructions during setup for how to do this.

lib/utils.py:

Contains various util methods. You are not expected to modify this file.

Q1.py, Q2a.y, Q2b.py, Q3a.py, Q3b.py:

You will have to modify the various scriptSig and scriptPubKey methods, as well as fill the transaction parameters. Note that for question 3, you will have to generate additional private and public keys for customers using the web requests to BlockCypher.

docs/transactions.py

You are expected to fill this file with the transaction ids generated for questions 1-3.

4. Be sure to start early on this project, as block confirmation times can vary depending on how busy the network is!

3.3 Setup

1. Open lib/config.py and read the file. Note that there are several users that you will need to generate private keys and addresses for.

2. First, we are going to create generate key pairs for you on the BlockCypher testnet.

(a) Sign up for an account with Blockcypher to get an API token here:

https://accounts.blockcypher.com/

(b) Create BCY testnet keys for you and place into lib/config.py.

curl -X POST ’https://api.blockcypher.com/v1/bcy/test/addrs?token=YOURTOKEN’

Note, if you copy this command directly into your terminal from this handout, you’ll likely need to delete and retype the ’ for the command to work.

(c) Record the transaction hash the faucet provides as you will need it later. Viewing the trans-action in a block explorer (e.g. https://live.blockcypher.com/) will also let you know which output of the transaction corresponds to your address, and you will need this utxo index for the next step as well. If the faucet doesn’t give you a transaction hash, you can also paste the user address into the block explorer and find the transaction that way.

3. Give your address bitcoin on the Blockcypher testnet (BCY) and record the transaction hash.

curl -d ’{"address": "BCY_ADDRESS", "amount": 100000}’ \

https://api.blockcypher.com/v1/bcy/test/faucet?token=YOURTOKEN

Note, if you copy this command directly into your terminal from this handout, you’ll likely need to delete and retype the ’{ and the }’, delete the \, and condense the command into one line for it to work.

4. The faucets will give you one spendable output, but we would like to have multiple outputs to spend in case we accidentally lock some with invalid scripts. Edit the parameters at the bottom of split_test_coins.py, where txid_to_spend is the transaction hash from the faucet to your address, utxo index is 0 if your output was first in the faucet transaction and 1 if it was second, and n is the number of outputs you want your test coins split evenly into, and run the program with python split_test_coins.py. A perfect run through of questions 1-3 would require n = 3 for your address, one for each exercise, but if you anticipate accidentally locking an output due to a faulty script. a couple times per exercise then you might want to set n to something higher like 8 so that you don’t have to wait to access the faucet again or have to try with a different Bitcoin address. If split_test_coins.py was successful, you should get back some information about the transaction. Record the transaction hash, as each exercise will be spending an output from this transaction and will refer to it using this hash.

Note: The faucet transaction would need to be fully verified (at least 6/6 confirmations) before you can split the coins you received. Waiting times will vary based on how busy the network is.

5. At the end, verify that you created BlockCypher Testnet addresses for you. You should have some coins on this blockchain. Give yourself a pat on the back for finishing a long setup. Now it’s time to explore creating transactions with Bitcoin Script.

3.4 Questions

For each of the questions below, you will use the Bitcoin Script. opcodes to create transactions. To publish each transaction created for the exercises, edit the parameters at the bottom of the file to specify which transaction output the solution should be run with along with the amount to send in the transaction. If the scripts you write aren’t valid, an exception will be thrown before they’re published. For questions 1-3, make sure to record the transaction hash of the created transaction and write it to docs/transactions.py. After completing each exercise, look up the transaction hash in a blockchain explorer to verify whether the transaction was picked up by the network. Make sure that all your transactions have been posted successfully before submitting their hashes.

Exercise 1. Open Q1.py and complete the scripts labelled with TODOs to redeem an output you own and send it back to the faucet with a standard PayToPublicKeyHash transaction. The faucet address is already included in the starter code for you. Your functions should return a list consisting of only OP codes and parameters passed into the function.

Exercise 2. For question 2, we will generate a transaction that is dependent on some constants.

(a) Open Q2a.py. Generate a transaction that can be redeemed by the solution (x, y) to the following system of two linear equations:

x + y = (first half of your suid)     and     x − y = (second half or your suid)

For an integer solution to exist, the rightmost digit of the first and second halves of your suid must either be both even or both odd. Therefore, you can change the rightmost digit of the second half of your suid to match the evenness or oddness of the righmost digit of the first half. Make sure you use OP ADD and OP SUB in your scriptPubKey.

(b) Open Q2b.py. Redeem the transaction you generated above. The redemption script. should be as small as possible. That is, a valid scriptSig should consist of simply pushing two integers x and y to the stack.

Exercise 3. Next, we will create a multi-sig transaction involving four parties.

(a) Open Q3a.py. Generate a multi-sig transaction involving four parties such that the trans-action can be redeemed by the first party (bank) combined with any one of the 3 others (customers) but not by only the customers or only the bank. You may assume the role of the bank for this problem so that the bank’s private key is your private key and the bank’s public key is your public key. Generate the customers’ keys using web requests and paste them in Q3a.py.

(b) Open Q3b.py. Redeem the transaction and make sure that the scriptSig is as small as possible. You can use any legal combination of signatures to redeem the transaction but make sure that all combinations would have worked.

3.5 Submitting your code

Record your transaction hashes in the docs/transactions.py file for questions 1-3. The hashes should be listed one per line in the same order as the questions.

3.6 Recommended Reading

1. Bitcoin Script. https://en.bitcoin.it/wiki/Script.

2. Bitcoin Transaction Format: https://en.bitcoin.it/wiki/Transaction

3. Bitcoin Transaction Details: https://privatekeys.org/2018/04/17/anatomy-of-a-bitcoin-transaction/