Lec 5: Bitcoin Transaction

Bitcoin Transaction

Transaction

• Transaction is references previous transaction outputs as new transaction inputs and dedicates all input Bitcoin values to new outputs (input money == output money)
• Transactions are not encrypted
• Standard tx outputs nominate address, and the redemption of any future inputs requires a relevant signature
• in Bitcoin transaction, if money left, must spend it to myself

Input: a reference to an output from a previous tx

• multiple inputs are possible
• Previous tx: hash of a previous transaction
• Index: specific output in the referenced transaction (because output also can be multiple)
• ScriptSig: first half of a script

Output: instruction for sending bitcoins

• multiple outputs are possible
• Value: number of Satoshi (1 BTC = 100,000,000 Satoshi)
• ScriptPubKey: second half of a script

Script

• signature(ScriptSig) in input + public key(ScriptPubKey) in previous transaction's output
• public key must match the hash given in the script of the redeemed output
• public key is used to verify the redeemer's signature, which is the first component in ScriptSig == the first component is an ECDSA signature over a hash of a simplified version of the transaction
• proves the transaction was created by the real owner of the address

---

UTXO

UTXO (Unspent Transaction Outputs)

• the amount of digital currency someone has left remaining after executing a cryptocurrency transaction such as Bitcoin
• implies that the all outputs which are not yet redeemed by anyone

---

Types of Bitcoin Transaction

Pay-to-PubKey (P2PK)

• Redeeming coins that have been sent to a Bitcoin public key
• scriptSig: <sig>
• scriptPubKey: <pubKey> OP_CHECKSIG

Stack	Script	Description
Empty	<sig> <pubKey> OP_CHECKSIG	combine scirptSig and scriptPubKey
<sig>	<pubKey> OP_CHECKSIG	Signature is added to the stack
<sig> <pubKey>	OP_CHECKSIG	Pubkey is added to the stack
true	Empty	Signature is checked

 

Pay-to-Pubkey-Hash (P2PKH)

• Bitcoin address is only a hash value of public key because full public key is too long, so the sender can't provide a full pubKey in scriptPubKey
• Recipient provides both the signature and the public key
• scriptSig: <sig><pubKey>
• scriptPubKey: OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG

Stack	Script	Description
Empty	<sig><pubKey> OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG	Combine scriptSig and scriptPubKey
<sig><pubKey>	OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG	Constants are added to the stack
<sig><pubKey><pubKey>	OP_HASH160 <pubKeyHash>  OP_EQUALVERIFY OP_CHECKSIG	Top stack item is duplicated
<sig><pubKey><pubHashA>	<pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG	Top stack item is hashed
<sig><pubKey><pubHashA><pubKeyHash>	OP_EQUALVERIFY OP_CHECKSIG	Constant added
<sig><pubKey>	OP_CHECKSIG	Equality checking btw the top two stack items
true	Empty	Signature checking for top two stack items

 

Pay-to-Multi Signature (P2MS)

• to lock coins with a requirement for multiple parties to sign the scriptSig before coins can be spent.
• scriptSig: <sig1> <sig2>
• scriptPubKey: OP_2 <pubKey1> <pubKey2> <pubKey3> OP_3 OP_CHECKMULTISIG

Stack	Script	Description
Empty	OP_1 <sig1> <sig2> OP_2 <pubKey1> <pubKey2> <pubKey3> OP_CHECKMULTISIG	Combine scriptSig and scriptPubKey
1 <sig1><sig2>	OP_2 <pubKey1><pubKey2><pubKey3> OP_CHECKMULTISIG	Constants added
1 <sig1><sig2> 2 <pubKey1><pubKey2><pubKey3> 3	OP_CHECKMULTISIG	Contants added
true	Empty	Multisignature checking

 

Pay-to-Script-Hash (P2SH)

• to lock bitcoins to the hash of a script, and you then provide that original script when you come unlock those bitcoins
• you can create your own "redeem scripts", script is kind of very simple smart contract
• scriptSig: <script>
• scriptPubKey: OP_HASH160 <script> OP_EQUALVERIFY

---

Coding Practice - Digital Signature

Digital Signature Algorithm (DSA)

Bitcoin uses ECDSA and user's address is the hash of the public key of the user

• ECDSA is the elliptic curve version of DSA.
• DSA uses a multiplicative group of integers modulo a prime $p$, but ECDSA uses a multiplicative group of points on an elliptic curve

Digital Signature Algorithm (DSA)

• widely used digital signature scheme.
• In python, Pycryptodome is one of packages supporting DSA.

 

Coding Practice

Generate a key pair for DSA, sign a message and verify the signature

 

Import Packages

from Cryptodome.PublicKey import DSA
from Cryptodome.Signature import DSS
from Cryptodome.Hash import SHA256
import binascii

• binascii: convenient package to handle hexadecimal numbers.

Generate Key Pair

# generate parameters(g, p, q) with a 1024 bit public key and private key
key = DSA.generate(1024)
# to share for verification
tup = [key.y, key.g, key.p, key.q]

• for verification, signer must shsare some public parameters $(g, p, q)$ and a public key $(y)$
• signer keeps its private key $(x)$ to sign a message

Signing a message

message = b"Hello" # convert string into byte array
hash_obj = SHA256.new(message) # hashing using SHA256 algorithm
print(hash_obj.hexdigest()) # convert hash_obj into hexadecimal number

signer = DSS.new(key, 'fips-186-3')
signature = signer.sign(hash_obj)
signature_hex = binascii.hexlify(signature) # convert signature into hexadecimal number
# signature = binascii.unhexlify(signature_hex) # convert hexadecimal number to binary

• DSS is used instead of the DSA class to generate a signature
  • DSS is a standard for digital signature
  • Using DSS means. that we will use the DSA algorithm in a way recommended in DSS which is published by NIST, as 'fips-186-3'

Verifying a message

pub_key = DSA.construct(tup) # tup = [key.y, key.g, key.p, key.q]
verifier = DSS.new(pub_key, 'fips-186-3')
try:
    verifier.verify(hash_obj, signature)
    print("The message is authentic")
except ValueError:
    print("The message is not authentic")

---

Other Consensus Algorithms

Proof of Space

• Proof of Space is very similar to PoW, except that instead of computation(using processor), storage is used
  • memory-hard functions, more environment friendly
• SpaceMint and Burstcoin use Proof of Space

Verification

• verifify the prrof where the prover has reserved a certain amount of space
• verification process needs to be efficient, it should be hard for the prover to pass the verification if it doesn't actually reserve the claimed amount of space

Trivial Proof of Space

• Exchanging a large file to verify prover to have enough space
• Impractical -> Verifier also needs a large space, Large network costs

Hard-to-Pebble Graphs

• Using hash chain graph, we can compute the space (the number of pebbles) - can reuse memory space unused
• Graphs are hard to pebble if you need many pebbles to pebble a vertex
  • High interconnectedness (Many edges)

 

Proof of Elapsed Time

Proof of Elapsed time (POET) can use in private chain to give random opportunity

• fair lottery system
• Each node in the blockchain network generates a random wait time and goes to sleep for that specified duration.