I want to read and verify a standard raw bitcoin transaction.

This will involve:
- learning about the transaction format
- checking the validity of the transaction signature









- Goal
- Contents
- Brief Summary
- Transaction Verification Recipe
- Downloadable Assets
- Representative Sample Of Bash Commands Used
- Notes / Discoveries
- Slightly-Less-Certain Notes
- Further Work
- Thoughts
- Project Log









I chose a bitcoin transaction to analyse. I studied prior work by Ken Shirriff (and retraced many of his steps) in order to learn how to read and verify a transaction. I then applied this process to my selected transaction and successfully verified it.

I developed code that significantly streamlined the verification process. This code is available in the Downloadable Assets section. A recipe for repeating this process is available in the Transaction Verification Recipe section. This recipe and code can only handle transactions of a particular type (one-input single-signature Pay-To-Public-Key-Hash (P2PKH)).

I learned a lot about how bitcoin transactions are structured. See the Notes / Discoveries section in particular.

In the Project Log section, I included a fairly thorough snapshot sequence of the development of parser1.py (a script for reading a transaction and reporting its structure to the user), which may be helpful for those who are new to programming and are wondering what they can usefully do.









Create a work directory. Download all assets associated with this article and place them into the work diretory.

Unzip ecdsa-0.10.tar.gz. Within the resulting ecdsa-0.10 directory, find the ecdsa directory and copy it to the work directory.

The inputs for each script must be edited manually. None have command-line argument processing.

On blockchain.info, a blockchain explorer web application, the raw form of a transaction can be looked up by using a request in this format:

http://blockchain.info/tx/[txid]?format=hex

where [txid] is the transaction identifier.

Example:
http://blockchain.info/tx/9ff7742262f68c560efd352f435b977c024797dc538f7efa08a467039858e42f?format=hex



### TRANSACTION VERIFICATION PROCESS (version 1)


Select a transaction to verify. It must have exactly one input. It can have multiple outputs. The input and the outputs must all be single-signature Pay-To-Public-Key-Hash (P2PKH). The public key in the input scriptSig may be compressed.

Get the raw form of the selected transaction. Save this in a file in the work directory.

Run parser2.py, targeted at this file.
- In the single input information, get these values:
-- [derived property] previous_output_hash (no spaces, big-endian)
-- previous_output_index
-- scriptSig

Use the "previous_output_hash (no spaces, big-endian)" value (a.k.a. the txid) to look up the transaction that supplied an output for use as the input to the selected transaction. Get the raw form of this previous transaction. Save it in a file in the work directory.

Run parser2.py, targeted at this file.
Use the previous_output_index found earlier to select the appropriate output in the result.
- In the information for this output, get this value:
-- scriptPubKey

For the selected transaction to be valid, its scriptSig needs to satisfy the cryptographic condition set by the previous transaction's scriptPubKey.

Use the scriptPubKey and the scriptSig as inputs to script_processor1.py.
Run script_processor1.py. From the output, get these values:
- signature_data
- public_key_data
- public_key_hash

Use public_key_data and public_key_hash as inputs to check_hash1.py. This script will check that the public_key_data in the selected transaction's scriptSig hashes to the public_key_hash in the previous transaction's scriptPubKey.

Use these items produced by script_processor1.py:
- signature_data
- public_key_data
this item produced by parser2.py when parser2.py was targeting the previous transaction:
- scriptPubKey
and the file containing the selected transaction
as inputs to check_signature2.py.

check_signature2.py will raise an informative error if the public_key_data is compressed.

If the public_key_data is compressed, uncompress it using uncompress.py. From the output, get the X and Y values, and use them as input for check_validity_of_point.py, which will check whether the uncompressed form of the public key is a valid point on the secp256k1 curve (if successful, the result is "True"). From the output of uncompress.py, get the uncompressed form of the public key and use it as input to check_signature2.py. Run check_signature2.py again.

check_signature2.py will use the public key to check the validity of the signature of the selected transaction in signable form. The public key and the signature are stored in the selected transaction's scriptSig. The scriptPubKey of the previous transaction is used as part of the transaction-in-signable-form.

If both check_hash1.py and check_signature2.py return successful results, then the selected transaction has been verified.


### END TRANSACTION VERIFICATION PROCESS (version 1)









The following assets comprise a toolset for verifying a standard transaction. See the Transaction Verification Recipe section.


bjorn_edstrom_ripemd160.py

check_hash1.py

check_signature2.py

check_validity_of_point.py

ecdsa-0.10.tar.gz

parser2.py

pypy_sha256.py

script_processor1.py

uncompress.py




















My working definition of a standard transaction:
- It can have multiple inputs and outputs.
- The input and the outputs must all be single-signature Pay-To-Public-Key-Hash (P2PKH).
- The public key in the input scriptSig may be compressed.


The verification recipe I have developed in this article has been written and tested only with single-input transactions. Some code sections would have to be rewritten, expanded, and tested in order to handle multiple-input transactions.


Here is my current working description of the final raw form of a transaction:



Note: I might find in future that other transactions have formats that don't match this expected format.

Note: A var_int ("variable integer") value is used to store a number of variable length. It can be used to indicate the length in bytes of the next item, e.g. script_length, which contains the byte length of scriptSig. It can also be used to store a number, e.g. input_count (number of input items). A one-byte var_int has a maximum value of 0xFC (252 in decimal).


On blockchain.info, a blockchain explorer web application, the raw form of a transaction can be looked up by using a request in this format:

http://blockchain.info/tx/[txid]?format=hex

where [txid] is the transaction identifier.

Example:
http://blockchain.info/tx/9ff7742262f68c560efd352f435b977c024797dc538f7efa08a467039858e42f?format=hex



I chose the transaction with txid
9ff7742262f68c560efd352f435b977c024797dc538f7efa08a467039858e42f
in the block with hash
0000000000000000001a226aea1237aa124c741d73e897cc8384f273578a682e
at block height 519883 for analysis. It has 1 input and 2 outputs. All the addresses start with a "1", i.e. are not multisig.


Note: txid == "transaction id".


In raw form, this transaction is:




In space-separated hex bytes, this transaction is:




In subdivided readable form, this transaction is:




In subdivided readable form, the scriptSig is:



In subdivided readable form, the scriptPubKey from the previous transaction (that supplied the unspent output used as the input for this transaction) is:



The inputs for a new transaction are a set of as-yet-unspent outputs from previous transactions. Inputs transfer value out of a previous address and outputs transfer value into a new address. (It would perhaps be more accurate to say that value is "associated with" an address, rather than that the value is "contained within" it.) A transaction is a collection of inputs and outputs, formatted into a single item.

Blocks are collections of transactions, formatted into a single item.

The bitcoin amount associated with an address does not specifically exist anywhere on the blockchain. It is an implicit value - it is calculated as the sum of the values of the currently-unspent outputs associated with an address (i.e. sent to that address by previous transactions). When some of these unspent outputs are used in a new transaction, value is transferred out of the address.

A bitcoin address is not just a global ID, like an account number in a bank. A standard* address is a value that encodes a hash of a bitcoin public key. The network nodes, following the bitcoin ruleset, verify that new transactions that spend bitcoin from an address are signed by a public key that hashes to the value encoded in that address. The nodes reject transactions that do not satisfy this cryptographic condition.

* My working definition of a standard address is: single-signature Pay-To-Public-Key-Hash (P2PKH).

The cryptographic proof is contained in each input (a.k.a. "as-yet-unspent-output") and is specific to that input. For standard* inputs, this proof consists of:
- A public key that hashes to the value encoded in the address that holds the unspent-output.
- A signature, made by the private key associated with the public key, of the entire transaction (albeit an altered form of the transaction).

* My working definition of a standard input is: an input that spends an unspent output from a standard single-signature Pay-To-Public-Key-Hash (P2PKH) address.

If a public key is compressed:
- This will produce a different hash and thus a different address.
- The compressed form must also be used in a transaction input that spends from this address. (It will be hashed and the result compared to the hash encoded in the address.)

It is worth noting that when an address is used to receive bitcoin, only the hash of the public key is revealed. Later, if and when bitcoin is sent from this address, the actual public key will be revealed in the relevant input of the transaction.


Bitcoin ECDSA public keys represent a point on a particular Elliptic Curve (EC) defined in secp256k1. This curve is y^2 = x^3 + 7. In their traditional uncompressed form, public keys contain an identification byte, a 32-byte X coordinate, and a 32-byte Y coordinate.

The Elliptic Curve DSA algorithm generates a 512-bit public key from the private key.


Each input used must be entirely spent in a transaction.

Suppose that an address that you own contains 1 bitcoin and that you want to send 0.01 bitcoin to someone else from this address. The transaction must spend the entire 1 bitcoin. The solution is to spend the remaining 0.99 bitcoin to another of your addresses, which can in fact be the original address that contained the 1 bitcoin.

Transactions can also include a mining fee. The fee is an implicit value - if there is any bitcoin left over after adding up the inputs and subtracting the outputs, the remainder is the fee paid to the miner. The fee isn't strictly required, but transactions without a fee will be a low priority for miners and may not be processed for days or may be discarded entirely.


In order to learn how to read and verify a signed transaction, I studied Ken Shirriff's article Bitcoins the hard way: Using the raw Bitcoin protocol, in which he created and signed a transaction, and the associated code [link]. I read and verified his signed transaction, and used the process/knowledge from this to read and verify my selected transaction.


The txid of Ken Shirriff's signed transaction is:
3f285f083de7c0acabd9f106a43ec42687ab0bebe2e6f0d529db696794540fea


Here is Ken Shirriff's signed transaction in raw form:




Here is Ken Shirriff's signed transaction in subdivided readable form:




In subdivided readable form, the scriptSig is:


In subdivided readable form, the scriptPubKey from Ken Shirriff's previous transaction (that supplied the unspent output used as the input for this transaction) is:



The value in bitcoin of an output is actually an integer and is denominated in satoshis, the smallest unit of bitcoin. Bitcoin values used for display often include a decimal point, but on the blockchain they are all actually satoshi integer values.


In a transaction, scriptSig and scriptPubKey are small stack programs in a Bitcoin-specific language called Script. These programs contain the instructions for verifying the validity of a transaction input. A bitcoin node must use an implementation of a stack machine to run these programs. Script is simple, stack-based, and processed from left to right.

Some reading indicates that a "stack" is the abstract idea of a sequential collection of objects on which certain operations are defined. A stack machine can process a stack and produce an output. Stack machine implementations may vary across platforms but must behave in the same way in order to be considered to be the same stack machine. A stack machine can therefore be implemented in Python on one computer and in C++ on another computer, but as long as the two stack machine implementations can perform the same operations on the same domain, they can pass data (stack items) between themselves without any trouble.

The stack code does not implement a SHA256 hash function - it simply indicates when and on what data a SHA256 function should operate. The details of implementing SHA256 are left to the stack machine.

Stack code can be manually processed by reading the code and performing the indicated operations e.g. checking that the two top stack items are equal or applying the SHA256 hash function to the data in a specified stack item.

The scriptPubKey is contained within an output of a previous transaction (the one that sent bitcoin to a particular address). The scriptSig is contained within an input of a new transaction (the one that spends bitcoin from a particular address).

The scriptPubKey in the old transaction defines the condition for spending the bitcoins (a hash of a public key). The scriptSig in the new transaction provides data that satisfies this condition (a signature and a public key).

The scriptPubKey from the previous transaction is needed for transaction validation. An input in the new transaction will identify the previous transaction and include the index of the relevant output from the previous transaction. The transaction identifier can be used to look up the previous transaction.
- Note: I think that a standard scriptPubKey could be constructed from the address alone, but it is preferable to source the scriptPubKey directly from the blockchain, so as to avoid any discrepancy.

The scriptSig signature in a valid transaction accomplishes several things:
- It proves that the transaction has not been changed since it was created.
- It proves that the transaction was signed by someone who had a particular public key (which is contained in the scriptSig).
- It proves that the transaction was signed by someone who had the specific public key required by the scriptPubKey of the relevant previous output.

Note: It is perhaps more accurate to say something like "It proves that the transaction was signed by someone who had the private key that corresponds to a particular public key.".

During transaction validation, scriptSig and scriptPubKey are combined into a single script. The resulting script program is then run. A transaction is valid if nothing in the combined script triggers failure and the top stack item is True (non-zero) when the script exits.




Particular byte values are "opcodes". They indicate an stack operation that should be performed. Many byte values signify PUSHDATA (push n subsequent bytes onto the stack as a new stack item), but each indicates a different number of bytes to push.

SIGHASH_ALL is a single byte appended to the signature data. Its value is 0x01.

The signature is in DER encoding and must be unpacked before it can be checked.

The first byte of the public key data will be 0x04 if the public key is uncompressed. It will be 0x02 or 0x03 if compressed. If it is 0x02, the Y value is even. If it is 0x03, the Y value is odd.

Note: The public key data in the input of my selected transaction begins with 02 and is compressed. The public key data in Ken Shirriff's signed transaction begins with 04 and is uncompressed.





The input signatures in a transaction are created by this process:



Note: The transaction-in-signable-form differs for each input.

To construct the final transaction:
- After all signatures have been constructed, place all the final scriptSigs in the appropriate locations within the transaction.









The items in these notes require more testing/checking/confirmation.


Here is my current understanding of possible var_int values:




An almost 50% reduction in public key size can be realised by dropping the Y coordinate. This is possible because only two points along the curve share any particular X coordinate, so the 32-byte Y coordinate can be replaced with a smaller value indicating whether the Y value is even or odd. I think that the terms "even" and "odd" are derived from the modular arithmetic used to calculate Y from X. The actual equation for calculating Y from X is y = sqrt(x^3 + 7), which will produce a negative result and a positive result.


A transaction signature can be altered by a third party and rebroadcast. This is known as Transaction Malleability. This new version will not be a valid transaction and will be rejected. I think that this can be a problem in two cases:
- Someone tries to DDOS bitcoin nodes by rebroadcasting many altered transactions. CPU effort is required to process and reject altered transactions (more effort than is required to reject normal pings, I think).
- The altered version may prevent the valid transaction from being mined (included in a block) for a while. This can particularly cause trouble if a person receiving payment attempts to spend the output from an unconfirmed transaction. A third party can then rebroadcast an altered version of the unconfirmed transaction, delaying the secondary payment.


A Bitcoin ECDSA private key in standard format is simply a 256-bit number, between the values:
- 0x01
and
- 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140
This range represents nearly the entire range of 2^256-1 values. It is set by the secp256k1 ECDSA encryption standard.


Script is intentionally not Turing-complete, with no loops or GOTO instructions.


A different random number is needed for every ECDSA signature. If an insufficiently random number is used, an attacker can derive the private key from a sufficient number of signatures.








Find out how to calculate the transaction identifier (TXID) of a signed transaction.


"In Bitcoin, a private key in standard format is simply a 256-bit number, between the values:
- 0x01
and
- 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140, representing nearly the entire range of 2^256-1 values. The range is governed by the secp256k1 ECDSA encryption standard used by Bitcoin."
-> Investigate this. Are these values accurate?


"However, Bitcoin Core prior to 0.6 used uncompressed keys."
-> How do versions prior to 0.6 verify transactions (produced by other versions) in which a compressed public key is used in an input scriptSig?


Investigate the format of the block_lock_time value. It's apparently not a straightforward little-endian integer value.


Investigate whether any transactions have included a two-byte var_int length value.
E.g. a transaction with 253 inputs.
-> Do other limits within the bitcoin code prevent a transaction having 253 inputs?
- This limit was mentioned in an excerpt: "The transaction must be smaller than 100,000 bytes. That's around 200 times larger than a typical single-input, single-output P2PKH transaction."
-- However, a transaction with 253 inputs and one output would presumably not exceed 100 000 bytes.



Read and verify a multiple-input transaction. Develop appropriate code to streamline this process.


Add block_lock_time to the output of Transaction.to_string() in parser2.py.


A different random number is needed for every ECDSA signature. If an insufficiently random number is used, an attacker can derive the private key from a sufficient number of signatures.
-> How is this attack performed, exactly?
- Note: I think that this random number has to be the same length as the ECDSA public key (which is twice the length of the ECDSA private key). Is this true?









Ken Shirriff wrote that "A transaction is the basic operation in the Bitcoin system.". I think it might actually be the basic conceptual item in the Bitcoin system. The definitions/designs of all the other items could be considered as flowing from the idea of a transaction.

Examples:
- A bitcoin address can be thought of as "the condition that must be satisfied by a transaction input scriptSig".
- Blocks are collections of transactions. They lay down a transaction history that is very difficult to alter.
- New bitcoin is generated by using a special case of a transaction (a "coinbase" transaction in a new block).

This is different from gold as a basis for a currency. The physical item "gold" is the basic conceptual item in a gold-based currency system. The idea of a "transaction" derives from the existence of the gold e.g. "what if I give you gold in exchange for your grain?". The amount of money that you have is equivalent to the amount of gold that you have. However, in the Bitcoin system, the amount of money you have is equivalent to: the sum of the values of the currently-unspent transaction outputs associated with addresses that you control. Here, the existence of the monetary item "bitcoin" derives from the existence of previous transactions.

The universe and its physical behaviour enforces the relative scarcity of gold. The mining competition in the Bitcoin system enforces the relative scarcity of coinbase transactions that create new bitcoin.

Any miner could of course devise and follow a new ruleset, e.g. one that doubled the amount of new bitcoin in a coinbase transaction, but other miners would continue mining on the pre-existing chain, so there would be a "fork" - two transaction history chains that diverge from a particular block on the original chain. Each of these transaction history chains ("blockchains") would acquire a market price. Market participants would prefer coins on one chain to the coins on the other. The chain that inflated more (created more coins) would probably be worth less over time (if supply increases, demand/supply ratio i.e. price decreases). This means that although a miner could fork and create a chain in which he acquired more currency units per block created, each unit would be worth less, perhaps much less, thus over time lowering the return on his investment in mining equipment. The fear of loss is what drives the miners to keep using the same ruleset and incidentally to preserve a single transaction history chain with relatively scarce currency unit creation.
- Note: This last thought is not my own, although I arrived at it here from a different starting point - it comes from reading discussions in the #trilema chat channel log and articles from Mircea Popescu.
- Note: Fear of loss for a miner applies when the miner is small relative to the total mining effort. In the case where mining is sufficiently centralised for a sufficient long period of time, the central mining entity would begin to be able to make changes to the ruleset with much less fear of loss.









I want to find a small standard transaction, i.e. one with 1 input and 1 or 2 outputs.


Update: My working definition of a standard transaction:
- It can have multiple inputs and outputs.
- The input and the outputs must all be single-signature Pay-To-Public-Key-Hash (P2PKH).
- The public key in the input scriptSig may be compressed.


Work computer: Aineko, a 2008 Macbook running Mac OS X 10.6.8 Snow Leopard.


First, I need a sample transaction.

Browse to:
blockchain.info

Newest block listed: 519889

Click "See More" link to browse to larger list of most recent blocks.

Choose seventh-to-last block: 519883

Click its block height to browse to block height page.
blockchain.info/block-height/519883

Block Height 519883: Blocks at depth 519883 in the bitcoin blockchain

Summary:
- Height: 519883 (Main chain)
- Hash:
0000000000000000001a226aea1237aa124c741d73e897cc8384f273578a682e
- Previous Block:
000000000000000000306d04afee78bf94eafee3108b0e9a5a855bf8ecd398c3
- Next Blocks:
00000000000000000003b14ec2a3ac99ec3269b9f9b5a133a96f258ea31f706c
- Time: 2018-04-25 15:45:09
- Received Time: 2018-04-25 15:45:09
- Relayed By: BTC.com
- Difficulty: 3,839,316,899,029.67
- Bits: 390680589
- Number Of Transactions: 2819
- Output Total: 19,872.3921596 BTC
- Estimated Transaction Volume: 1,268.15051772 BTC
- Size: 1157.477 KB
- Version: 0x20000000
- Merkle Root:
38fed9146fcd86d5aaee12b9785e2fe2ec84a4efe15e5ebb6273f70e90884df0
- Nonce: 2668289829
- Block Reward: 12.5 BTC
- Transaction Fees: 1.12204974 BTC

There's only one block displayed. However, if there was an another block at this block height, which was not added to the main chain, then the details of two blocks would probably be displayed.

"Next Blocks" should perhaps be "Next Block(s)".

The hash value is a link.
Clicking it leads to:
blockchain.info/block/0000000000000000001a226aea1237aa124c741d73e897cc8384f273578a682e

Block #519883
Summary:
- Number Of Transactions: 2819
- Output Total: 19,872.3921596 BTC
- Estimated Transaction Volume: 1,268.15051772 BTC
- Transaction Fees: 1.12204974 BTC
- Height: 519883 (Main Chain)
- Timestamp: 2018-04-25 15:45:09
- Received Time: 2018-04-25 15:45:09
- Relayed By: BTC.com
- Difficulty: 3,839,316,899,029.67
- Bits: 390680589
- Size: 1157.477 kB
- Weight: 3992.867 kWU
- Version: 0x20000000
- Nonce: 2668289829
- Block Reward: 12.5 BTC

Hashes:
- Hash
0000000000000000001a226aea1237aa124c741d73e897cc8384f273578a682e
- Previous Block
000000000000000000306d04afee78bf94eafee3108b0e9a5a855bf8ecd398c3
- Next Block(s)
00000000000000000003b14ec2a3ac99ec3269b9f9b5a133a96f258ea31f706c
- Merkle Root
38fed9146fcd86d5aaee12b9785e2fe2ec84a4efe15e5ebb6273f70e90884df0

Many transactions are listed on the page (presumably 2819 in total).

First one:

fdf94f02a95e08c034d248f77c3cadd8fa0e870342f63caaa73f6e4186fcd8cb
2018-04-25 15:45:09

- No Inputs (Newly Generated Coins)
=>
- 1C1mCxRukix1KfegAY5zQQJV7samAciZpv: 13.62204974 BTC
- Unable to decode output address: 0 BTC

[Total] 13.62204974 BTC

The transaction hash is a link to:
blockchain.info/tx/fdf94f02a95e08c034d248f77c3cadd8fa0e870342f63caaa73f6e4186fcd8cb


This transaction lacks an input, which means that it's the mining reward for the miner who created the block.


Let's move on to the second transaction.

c023284e8ba0eee2f71fc07121a9364900c8af7d8ec9fe0266a6b768dd9c1b74
2018-04-25 11:30:08

- 1G1jQNuLLgYBrS8WPoyg1Hxhv7AdXgL66K
=>
- 3QUseoZurNCbLAMPNSedphGNdM796B9MhQ: 1.135445 BTC

[Total] 1.135445 BTC

The "3" at the start of the output address indicates a multi-signature address.


Let's move on through the transactions until I find a non-multisig transaction with 1 input and 1 or 2 outputs.

9ff7742262f68c560efd352f435b977c024797dc538f7efa08a467039858e42f
2018-04-25 15:33:43

- 1CXg2fkCXCoHHnr4ijvZCTdqe9hPQkyDZG
=>
- 15haDNxwdj5Q4TgphVtg3CakrYZUBdY3Qu 0.04315624 BTC
- 15o4XcczE8Vx5kVwqGSjCNUh5V9R8sbbeW 0.240153 BTC

[Total] 0.28330924 BTC

Looks good. 1 input, 2 outputs. All addresses start with "1".

The transaction hash is a link to:
blockchain.info/tx/9ff7742262f68c560efd352f435b977c024797dc538f7efa08a467039858e42f


Click the link to browse to the transaction page.

9ff7742262f68c560efd352f435b977c024797dc538f7efa08a467039858e42f

- 1CXg2fkCXCoHHnr4ijvZCTdqe9hPQkyDZG (0.28725795 BTC - Output)
=>
- 15haDNxwdj5Q4TgphVtg3CakrYZUBdY3Qu - (Unspent) 0.04315624 BTC
- 15o4XcczE8Vx5kVwqGSjCNUh5V9R8sbbeW - (Spent) 0.240153 BTC

11 Confirmations
[Total] 0.28330924 BTC


Summary
- Size: 226 (bytes)
- Weight: 904
- Received Time: 2018-04-25 15:33:43
- Lock Time: Block 519882
- Included In Blocks: 519883 ( 2018-04-25 15:45:09 + 11 minutes )
- Confirmations: 11 Confirmations

Inputs and Outputs
- Total Input: 0.28725795 BTC
- Total Output: 0.28330924 BTC
- Fees: 0.00394871 BTC
- Fee per byte: 1,747.217 sat/B
- Fee per weight unit: 436.804 sat/WU
- Estimated BTC Transacted: 0.04315624 BTC

Input Scripts

1)
ScriptSig:
PUSHDATA(72)
[3045022100d8321c3c4b3fc3a34e30547d1cb6aea6855cad330b590b53e824f647dd49239902201e9056e82297a2108b1969cc497150734ab78f51cbf979885afc104f70a6515001]
PUSHDATA(33)
[02a534d65273f8520e1e841ccbb782b71e06b4117a90bb92c655f8131cf6ae2261]

Output Scripts

1)
DUP
HASH160
PUSHDATA(20)
[338cdde52f708236affa5675f969606ff846ee6f]
EQUALVERIFY
CHECKSIG

2)
DUP
HASH160
PUSHDATA(20)
[3496950f1a01285a1605ac9337c06a5596b9fcd8]
EQUALVERIFY
CHECKSIG

I don't see an option for displaying the raw transaction.


Google "look up raw transaction bitcoin".


Excerpt from 5th result:
bitcointalk.org/index.php?topic=332706.0
Author: dserrano5
PGP 404B 1B79 DF33 2359 4C8F 0F5E 1BCC 1A1F 280A 01F9 (bitcointalkatdserrano5.es)
Date: November 13, 2013, 01:08:24 PM
Subject: Re: Get Hex transaction from nodes

Quote from: DualSignal on November 13, 2013, 12:55:56 PM

How do you get the raw transaction in Hex format, from a transaction that is unconfirmed, and I didn't make, but appears on http://blockchain.info in a format that allows it to be passed into http://blockchain.info/pushtx when it is dropped from all miners memory pools.

Subject line says "from nodes", is that a requirement? blockchain.info returns the raw transaction if you append '?format=hex' to the URL of a transaction, e.g.:

http://blockchain.info/tx/9021b49d445c719106c95d561b9c3fac7bcb3650db67684a9226cd7fa1e1c1a0?format=hex

I note the existence of a "pushtx" option on blockchain.info.


Ok.

Take the link to the selected transaction and append '?format=hex' to it.

http://blockchain.info/tx/9ff7742262f68c560efd352f435b977c024797dc538f7efa08a467039858e42f?format=hex


Browse to this link.

01000000014f8cad2ca3b602750e06c4300d91b22c17dd97bb5ce635d860df8b0ab325b336010000006b483045022100d8321c3c4b3fc3a34e30547d1cb6aea6855cad330b590b53e824f647dd49239902201e9056e82297a2108b1969cc497150734ab78f51cbf979885afc104f70a65150012102a534d65273f8520e1e841ccbb782b71e06b4117a90bb92c655f8131cf6ae2261fdffffff02e8d94100000000001976a914338cdde52f708236affa5675f969606ff846ee6f88acc4716e01000000001976a9143496950f1a01285a1605ac9337c06a5596b9fcd888accaee0700

Hm. So this is a raw transaction, shown in hex.


The first result for googling "look up raw transaction bitcoin" was:
blockchain.info/decode-tx

Browse to this page.
"This page will decode a raw transaction in hex format (i.e. characters 0-9, a-f) and display it in human readable format"
There is a text field and a button named "Submit Transaction".

Paste in the raw transaction in hex format and click Submit Transaction.

Result:

{ "lock_time":519882, "size":226, "inputs":[ { "prev_out":{ "index":1, "hash":"36b325b30a8bdf60d835e65cbb97dd172cb2910d30c4060e7502b6a32cad8c4f" }, "script":"483045022100d8321c3c4b3fc3a34e30547d1cb6aea6855cad330b590b53e824f647dd49239902201e9056e82297a2108b1969cc497150734ab78f51cbf979885afc104f70a65150012102a534d65273f8520e1e841ccbb782b71e06b4117a90bb92c655f8131cf6ae2261" } ], "version":1, "vin_sz":1, "hash":"9ff7742262f68c560efd352f435b977c024797dc538f7efa08a467039858e42f", "vout_sz":2, "out":[ { "script_string":"OP_DUP OP_HASH160 338cdde52f708236affa5675f969606ff846ee6f OP_EQUALVERIFY OP_CHECKSIG", "address":"15haDNxwdj5Q4TgphVtg3CakrYZUBdY3Qu", "value":4315624, "script":"76a914338cdde52f708236affa5675f969606ff846ee6f88ac" }, { "script_string":"OP_DUP OP_HASH160 3496950f1a01285a1605ac9337c06a5596b9fcd8 OP_EQUALVERIFY OP_CHECKSIG", "address":"15o4XcczE8Vx5kVwqGSjCNUh5V9R8sbbeW", "value":24015300, "script":"76a9143496950f1a01285a1605ac9337c06a5596b9fcd888ac" } ] }

I think "out" might mean "outputs".



Let's do some reading:

Excerpts from:
bitcoin.org/en/developer-guide

A pop-up note is included on this page: "This documentation has not been extensively reviewed by Bitcoin experts and so likely contains numerous errors."

Block Chain

The block chain provides Bitcoin's public ledger, an ordered and timestamped record of transactions. This system is used to protect against double spending and modification of previous transaction records.

Each full node in the Bitcoin network independently stores a block chain containing only blocks validated by that node. When several nodes all have the same blocks in their block chain, they are considered to be in consensus. The validation rules these nodes follow to maintain consensus are called consensus rules. [...]


Block Chain Overview

[...]

A block of one or more new transactions is collected into the transaction data part of a block. Copies of each transaction are hashed, and the hashes are then paired, hashed, paired again, and hashed again until a single hash remains, the merkle root of a merkle tree.

The merkle root is stored in the block header. Each block also stores the hash of the previous block's header, chaining the blocks together. This ensures a transaction cannot be modified without modifying the block that records it and all following blocks.

Transactions are also chained together. Bitcoin wallet software gives the impression that satoshis are sent from and to wallets, but bitcoins really move from transaction to transaction. Each transaction spends the satoshis previously received in one or more earlier transactions, so the input of one transaction is the output of a previous transaction.

[...]

A single transaction can create multiple outputs, as would be the case when sending to multiple addresses, but each output of a particular transaction can only be used as an input once in the block chain. Any subsequent reference is a forbidden double spend - an attempt to spend the same satoshis twice.

Outputs are tied to transaction identifiers (TXIDs), which are the hashes of signed transactions.

Because each output of a particular transaction can only be spent once, the outputs of all transactions included in the block chain can be categorized as either Unspent Transaction Outputs (UTXOs) or spent transaction outputs. For a payment to be valid, it must only use UTXOs as inputs.

Ignoring coinbase transactions (described later), if the value of a transaction's outputs exceed its inputs, the transaction will be rejected - but if the inputs exceed the value of the outputs, any difference in value may be claimed as a transaction fee by the Bitcoin miner who creates the block containing that transaction.

[...]


Block Height And Forking

Any Bitcoin miner who successfully hashes a block header to a value below the target threshold can add the entire block to the block chain (assuming the block is otherwise valid). These blocks are commonly addressed by their block height - the number of blocks between them and the first Bitcoin block (block 0, most commonly known as the genesis block).

[...]

Multiple blocks can all have the same block height, as is common when two or more miners each produce a block at roughly the same time. This creates an apparent fork in the block chain, as shown in the illustration above.

When miners produce simultaneous blocks at the end of the block chain, each node individually chooses which block to accept. In the absence of other considerations, discussed below, nodes usually use the first block they see.

Eventually a miner produces another block which attaches to only one of the competing simultaneously-mined blocks. This makes that side of the fork stronger than the other side. Assuming a fork only contains valid blocks, normal peers always follow the most difficult chain to recreate and throw away stale blocks belonging to shorter forks. (Stale blocks are also sometimes called orphans or orphan blocks, but those terms are also used for true orphan blocks without a known parent block.)

[...]

Since multiple blocks can have the same height during a block chain fork, block height should not be used as a globally unique identifier. Instead, blocks are usually referenced by the hash of their header (often with the byte order reversed, and in hexadecimal).


Transaction Data

Every block must include one or more transactions. The first one of these transactions must be a coinbase transaction, also called a generation transaction, which should collect and spend the block reward (comprised of a block subsidy and any transaction fees paid by transactions included in this block).

The UTXO of a coinbase transaction has the special condition that it cannot be spent (used as an input) for at least 100 blocks. This temporarily prevents a miner from spending the transaction fees and block reward from a block that may later be determined to be stale (and therefore the coinbase transaction destroyed) after a block chain fork.

Blocks are not required to include any non-coinbase transactions, but miners almost always do include additional transactions in order to collect their transaction fees.

All transactions, including the coinbase transaction, are encoded into blocks in binary rawtransaction format.

The rawtransaction format is hashed to create the transaction identifier (txid). From these txids, the merkle tree is constructed by pairing each txid with one other txid and then hashing them together. If there are an odd number of txids, the txid without a partner is hashed with a copy of itself.

The resulting hashes themselves are each paired with one other hash and hashed together. Any hash without a partner is hashed with itself. The process repeats until only one hash remains, the merkle root.

[...]


Transactions

Transactions let users spend satoshis. Each transaction is constructed out of several parts which enable both simple direct payments and complex transactions.

[...]

To keep things simple, this section pretends coinbase transactions do not exist.

[...]

Each transaction has at least one input and one output. Each input spends the satoshis paid to a previous output. Each output then waits as an Unspent Transaction Output (UTXO) until a later input spends it. When your Bitcoin wallet tells you that you have a 10,000 satoshi balance, it really means that you have 10,000 satoshis waiting in one or more UTXOs.

Each transaction is prefixed by a four-byte transaction version number which tells Bitcoin peers and miners which set of rules to use to validate it.

[...]

An output has an implied index number based on its location in the transaction - the index of the first output is zero. The output also has an amount in satoshis which it pays to a conditional pubkey script. Anyone who can satisfy the conditions of that pubkey script can spend up to the amount of satoshis paid to it.

An input uses a transaction identifier (txid) and an output index number (often called "vout" for output vector) to identify a particular output to be spent. It also has a signature script which allows it to provide data parameters that satisfy the conditionals in the pubkey script. (The sequence number and locktime are related and will be covered together in a later subsection.)

[...]

[Let's describe] the workflow Alice uses to send Bob a transaction and which Bob later uses to spend that transaction. Both Alice and Bob will use the most common form of the standard Pay-To-Public-Key-Hash (P2PKH) transaction type. P2PKH lets Alice spend satoshis to a typical Bitcoin address, and then lets Bob further spend those satoshis using a simple cryptographic key pair.

Bob must first generate a private/public key pair before Alice can create the first transaction. Bitcoin uses the Elliptic Curve Digital Signature Algorithm (ECDSA) with the secp256k1 curve; secp256k1 private keys are 256 bits of random data. A copy of that data is deterministically transformed into an secp256k1 public key. Because the transformation can be reliably repeated later, the public key does not need to be stored.

The public key (pubkey) is then cryptographically hashed. This pubkey hash can also be reliably repeated later, so it also does not need to be stored. The hash shortens and obfuscates the public key, making manual transcription easier and providing security against unanticipated problems which might allow reconstruction of private keys from public key data at some later point.

Bob provides the pubkey hash to Alice. Pubkey hashes are almost always sent encoded as Bitcoin addresses, which are base58-encoded strings containing an address version number, the hash, and an error-detection checksum to catch typos. The address can be transmitted through any medium, including one-way mediums which prevent the spender from communicating with the receiver, and it can be further encoded into another format, such as a QR code containing a bitcoin: URI.

Once Alice has the address and decodes it back into a standard hash, she can create the first transaction. She creates a standard P2PKH transaction output containing instructions which allow anyone to spend that output if they can prove they control the private key corresponding to Bob's hashed public key. These instructions are called the pubkey script or scriptPubKey.

Once Alice has the address and decodes it back into a standard hash, she can create the first transaction. She creates a standard P2PKH transaction output containing instructions which allow anyone to spend that output if they can prove they control the private key corresponding to Bob's hashed public key. These instructions are called the pubkey script or scriptPubKey.

When, some time later, Bob decides to spend the UTXO, he must create an input which references the transaction Alice created by its hash, called a Transaction Identifier (txid), and the specific output she used by its index number (output index). He must then create a signature script - a collection of data parameters which satisfy the conditions Alice placed in the previous output's pubkey script. Signature scripts are also called scriptSigs.

Pubkey scripts and signature scripts combine secp256k1 pubkeys and signatures with conditional logic, creating a programmable authorization mechanism.

[...]

For a P2PKH-style output, Bob's signature script will contain the following two pieces of data:

1) His full (unhashed) public key, so the pubkey script can check that it hashes to the same value as the pubkey hash provided by Alice.

2) An secp256k1 signature made by using the ECDSA cryptographic formula to combine certain transaction data (described below) with Bob's private key. This lets the pubkey script verify that Bob owns the private key which created the public key.

Bob's secp256k1 signature doesn't just prove Bob controls his private key; it also makes the non-signature-script parts of his transaction tamper-proof so Bob can safely broadcast them over the peer-to-peer network.

[...]

The data Bob signs includes the txid and output index of the previous transaction, the previous output's pubkey script, the pubkey script Bob creates which will let the next recipient spend this transaction's output, and the amount of satoshis to spend to the next recipient. In essence, the entire transaction is signed except for any signature scripts, which hold the full public keys and secp256k1 signatures.

After putting his signature and public key in the signature script, Bob broadcasts the transaction to Bitcoin miners through the peer-to-peer network. Each peer and miner independently validates the transaction before broadcasting it further or attempting to include it in a new block of transactions.

[...]


P2PKH Script Validation

The validation procedure requires evaluation of the signature script and pubkey script. In a P2PKH output, the pubkey script is:

OP_DUP OP_HASH160 [PubkeyHash] OP_EQUALVERIFY OP_CHECKSIG

The spender's signature script is evaluated and prefixed to the beginning of the script. In a P2PKH transaction, the signature script contains an secp256k1 signature (sig) and full public key (pubkey), creating the following concatenation:

[Sig] [PubKey] OP_DUP OP_HASH160 [PubkeyHash] OP_EQUALVERIFY OP_CHECKSIG

The script language is a Forth-like stack-based language deliberately designed to be stateless and not Turing complete. Statelessness ensures that once a transaction is added to the block chain, there is no condition which renders it permanently unspendable. Turing-incompleteness (specifically, a lack of loops or gotos) makes the script language less flexible and more predictable, greatly simplifying the security model.

To test whether the transaction is valid, signature script and pubkey script operations are executed one item at a time, starting with Bob's signature script and continuing to the end of Alice's pubkey script.

[...]

1) The signature (from Bob's signature script) is added (pushed) to an empty stack. Because it's just data, nothing is done except adding it to the stack. The public key (also from the signature script) is pushed on top of the signature.

2) From Alice's pubkey script, the OP_DUP operation is executed. OP_DUP pushes onto the stack a copy of the data currently at the top of it - in this case creating a copy of the public key Bob provided.

3) The operation executed next, OP_HASH160, pushes onto the stack a hash of the data currently on top of it - in this case, Bob's public key. This creates a hash of Bob's public key.

4) Alice's pubkey script then pushes the pubkey hash that Bob gave her for the first transaction. At this point, there should be two copies of Bob's pubkey hash at the top of the stack.

5) Alice's pubkey script then pushes the pubkey hash that Bob gave her for the first transaction. At this point, there should be two copies of Bob's pubkey hash at the top of the stack.

OP_EQUAL (not shown) checks the two values at the top of the stack; in this case, it checks whether the pubkey hash generated from the full public key Bob provided equals the pubkey hash Alice provided when she created transaction #1. OP_EQUAL pops (removes from the top of the stack) the two values it compared, and replaces them with the result of that comparison: zero (false) or one (true).

OP_VERIFY (not shown) checks the value at the top of the stack. If the value is false it immediately terminates evaluation and the transaction validation fails. Otherwise it pops the true value off the stack.

6) Finally, Alice's pubkey script executes OP_CHECKSIG, which checks the signature Bob provided against the now-authenticated public key he also provided. If the signature matches the public key and was generated using all of the data required to be signed, OP_CHECKSIG pushes the value true onto the top of the stack.

If false is not at the top of the stack after the pubkey script has been evaluated, the transaction is valid (provided there are no other problems with it).

[...]


Non-Standard Transactions

If you use anything besides a standard pubkey script in an output, peers and miners using the default Bitcoin Core settings will neither accept, broadcast, nor mine your transaction. When you try to broadcast your transaction to a peer running the default settings, you will receive an error.

[...]

Note: standard transactions are designed to protect and help the network, not prevent you from making mistakes. It's easy to create standard transactions which make the satoshis sent to them unspendable.

As of Bitcoin Core 0.9.3, standard transactions must also meet the following conditions:

1) The transaction must be finalized: either its locktime must be in the past (or less than or equal to the current block height), or all of its sequence numbers must be 0xffffffff.

2) The transaction must be smaller than 100,000 bytes. That's around 200 times larger than a typical single-input, single-output P2PKH transaction.

3) Each of the transaction's signature scripts must be smaller than 1,650 bytes.

[...]

4) The transaction's signature script must only push data to the script evaluation stack. It cannot push new opcodes, with the exception of opcodes which solely push data to the stack.

5) The transaction must not include any outputs which receive fewer than 1/3 as many satoshis as it would take to spend it in a typical input. That's currently 546 satoshis for a P2PKH or P2SH output on a Bitcoin Core node with the default relay fee. [...]

[...]


Locktime And Sequence Number

One thing all signature hash types sign is the transaction's locktime. (Called nLockTime in the Bitcoin Core source code.) The locktime indicates the earliest time a transaction can be added to the block chain.

Locktime allows signers to create time-locked transactions which will only become valid in the future, giving the signers a chance to change their minds.

If any of the signers change their mind, they can create a new non-locktime transaction. The new transaction will use, as one of its inputs, one of the same outputs which was used as an input to the locktime transaction. This makes the locktime transaction invalid if the new transaction is added to the block chain before the time lock expires.

Care must be taken near the expiry time of a time lock. The peer-to-peer network allows block time to be up to two hours ahead of real time, so a locktime transaction can be added to the block chain up to two hours before its time lock officially expires. Also, blocks are not created at guaranteed intervals, so any attempt to cancel a valuable transaction should be made a few hours before the time lock expires.

Previous versions of Bitcoin Core provided a feature which prevented transaction signers from using the method described above to cancel a time-locked transaction, but a necessary part of this feature was disabled to prevent denial of service attacks. A legacy of this system are four-byte sequence numbers in every input. Sequence numbers were meant to allow multiple signers to agree to update a transaction; when they finished updating the transaction, they could agree to set every input's sequence number to the four-byte unsigned maximum (0xffffffff), allowing the transaction to be added to a block even if its time lock had not expired.

Even today, setting all sequence numbers to 0xffffffff (the default in Bitcoin Core) can still disable the time lock, so if you want to use locktime, at least one input must have a sequence number below the maximum. Since sequence numbers are not used by the network for any other purpose, setting any sequence number to zero is sufficient to enable locktime.

Locktime itself is an unsigned 4-byte integer which can be parsed two ways:

1) If less than 500 million, locktime is parsed as a block height. The transaction can be added to any block which has this height or higher.

2) If greater than or equal to 500 million, locktime is parsed using the Unix epoch time format (the number of seconds elapsed since 1970-01-01T00:00 UTC - currently over 1.395 billion). The transaction can be added to any block whose block time is greater than the locktime.


Transaction Fees And Change

Transactions pay fees based on the total byte size of the signed transaction. Fees per byte are calculated based on current demand for space in mined blocks with fees rising as demand increases. The transaction fee is given to the Bitcoin miner, [...] and so it is ultimately up to each miner to choose the minimum transaction fee they will accept.

There is also a concept of so-called "high-priority transactions" which spend satoshis that have not moved for a long time.

In the past, these "priority" transaction were often exempt from the normal fee requirements. Before Bitcoin Core 0.12, 50 KB of each block would be reserved for these high-priority transactions, however this is now set to 0 KB by default. After the priority area, all transactions are prioritized based on their fee per byte, with higher-paying transactions being added in sequence until all of the available space is filled.

As of Bitcoin Core 0.9, a minimum fee (currently 1,000 satoshis) has been required to broadcast a transaction across the network. Any transaction paying only the minimum fee should be prepared to wait a long time before there's enough spare space in a block to include it. [...]

Since each transaction spends Unspent Transaction Outputs (UTXOs) and because a UTXO can only be spent once, the full value of the included UTXOs must be [sent to output addresses] or given to a miner as a transaction fee. Few people will have UTXOs that exactly match the amount they want to pay, so most transactions include a change output.

Change outputs are regular outputs which spend the surplus satoshis from the UTXOs back to the spender. They can reuse the same P2PKH pubkey hash [...] as was used in the UTXO.

[...]


Transaction Malleability

None of Bitcoin's signature hash types protect the signature script, leaving the door open for a limited denial of service attack called transaction malleability. The signature script contains the secp256k1 signature, which can't sign itself, allowing attackers to make non-functional modifications to a transaction without rendering it invalid. For example, an attacker can add some data to the signature script which will be dropped before the previous pubkey script is processed.

Although the modifications are non-functional - so they do not change what inputs the transaction uses nor what outputs it pays - they do change the computed hash of the transaction. Since each transaction links to previous transactions using hashes as a transaction identifier (txid), a modified transaction will not have the txid its creator expected.

This isn't a problem for most Bitcoin transactions which are designed to be added to the block chain immediately. But it does become a problem when the output from a transaction is spent before that transaction is added to the block chain.

[...]

New transactions should not depend on previous transactions which have not been added to the block chain yet. [...]

Transaction malleability also affects payment tracking. Bitcoin Core's RPC interface lets you track transactions by their txid - but if that txid changes because the transaction was modified, it may appear that the transaction has disappeared from the network.

Current best practices for transaction tracking dictate that a transaction should be tracked by the transaction outputs (UTXOs) it spends as inputs, as they cannot be changed without invalidating the transaction.

Best practices further dictate that if a transaction does seem to disappear from the network and needs to be reissued, that it be reissued in a way that invalidates the lost transaction. One method which will always work is to ensure the reissued payment spends all of the same outputs that the lost transaction used as inputs.

[...]


Private Key Formats

Private keys are what are used to unlock satoshis from a particular address. In Bitcoin, a private key in standard format is simply a 256-bit number, between the values:

0x01 and 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140, representing nearly the entire range of 2^256-1 values. The range is governed by the secp256k1 ECDSA encryption standard used by Bitcoin.


Wallet Import Format (WIF)

In order to make copying of private keys less prone to error, Wallet Import Format may be utilized. WIF uses base58Check encoding on an private key, greatly decreasing the chance of copying error, much like standard Bitcoin addresses.

1) Take a private key.

2) Add a 0x80 byte in front of it for mainnet addresses or 0xef for testnet addresses.

3) Append a 0x01 byte after it if it should be used with compressed public keys (described in a later subsection). Nothing is appended if it is used with uncompressed public keys.

4) Perform a SHA-256 hash on the extended key.

5) Perform a SHA-256 hash on result of SHA-256 hash.

6) Take the first four bytes of the second SHA-256 hash; this is the checksum.

7) Add the four checksum bytes from point 5 at the end of the extended key from point 2.

8) Convert the result from a byte string into a Base58 string using Base58Check encoding.

The process is easily reversible, using the Base58 decoding function, and removing the padding.

[...]


Public Key Formats

Bitcoin ECDSA public keys represent a point on a particular Elliptic Curve (EC) defined in secp256k1. In their traditional uncompressed form, public keys contain an identification byte, a 32-byte X coordinate, and a 32-byte Y coordinate. The extremely simplified illustration below shows such a point on the elliptic curve used by Bitcoin, y^2 = x^3 + 7, over a field of contiguous numbers.

[illustration not included]

(Secp256k1 actually modulos coordinates by a large prime, which produces a field of non-contiguous integers and a significantly less clear plot, although the principles are the same.)

An almost 50% reduction in public key size can be realized without changing any fundamentals by dropping the Y coordinate. This is possible because only two points along the curve share any particular X coordinate, so the 32-byte Y coordinate can be replaced with a single bit indicating whether the point is on what appears in the illustration as the "top" side or the "bottom" side.

No data is lost by creating these compressed public keys - only a small amount of CPU is necessary to reconstruct the Y coordinate and access the uncompressed public key. Both uncompressed and compressed public keys are described in official secp256k1 documentation and supported by default in the widely-used OpenSSL library.

Because they're easy to use, and because they reduce almost by half the block chain space used to store public keys for every spent output, compressed public keys are the default in Bitcoin Core and are the recommended default for all Bitcoin software.

However, Bitcoin Core prior to 0.6 used uncompressed keys. This creates a few complications, as the hashed form of an uncompressed key is different than the hashed form of a compressed key, so the same key works with two different P2PKH addresses. This also means that the key must be submitted in the correct format in the signature script so it matches the hash in the previous output's pubkey script.

For this reason, Bitcoin Core uses several different identifier bytes to help programs identify how keys should be used:

1) Private keys meant to be used with compressed public keys have 0x01 appended to them before being Base-58 encoded. (See the private key encoding section above.)

2) Uncompressed public keys start with 0x04; compressed public keys begin with 0x03 or 0x02 depending on whether they're greater or less than the midpoint of the curve. These prefix bytes are all used in official secp256k1 documentation.

[...]


Verifying Payment

[...] Broadcasting a transaction to the network doesn't ensure that the receiver gets paid. A malicious spender can create one transaction that pays the receiver and a second one that pays the same input back to himself. Only one of these transactions will be added to the block chain, and nobody can say for sure which one it will be.

Two or more transactions spending the same input are commonly referred to as a double spend.

[...]

6 confirmations: The network has spent about an hour working to protect the transaction against double spends and the transaction is buried under six blocks. Even a reasonably lucky attacker would require a large percentage of the total network hashing power to replace six blocks. Although this number is somewhat arbitrary, software handling high-value transactions, or otherwise at risk for fraud, should wait for at least six confirmations before treating a payment as accepted.

Hm.


I'm going to use Ken Shirriff's article Bitcoins the hard way: Using the raw Bitcoin protocol and the associated code [link] as a guide. Footnote 11 in the article provided the link to the code.


Excerpts from the article:

Bitcoin uses a variety of keys and addresses, so the following diagram may help explain them. You start by creating a random 256-bit private key. The private key is needed to sign a transaction and thus transfer (spend) bitcoins. Thus, the private key must be kept secret or else your bitcoins can be stolen.

The Elliptic Curve DSA algorithm generates a 512-bit public key from the private key. (Elliptic curve cryptography will be discussed later.) This public key is used to verify the signature on a transaction. Inconveniently, the Bitcoin protocol adds a prefix of 04 to the public key. The public key is not revealed until a transaction is signed, unlike most systems where the public key is made public.

The next step is to generate the Bitcoin address that is shared with others. Since the 512-bit public key is inconveniently large, it is hashed down to 160 bits using the SHA-256 and RIPEMD hash algorithms. The key is then encoded in ASCII using Bitcoin's custom Base58Check encoding. The resulting address, such as 1KKKK6N21XKo48zWKuQKXdvSsCf95ibHFa, is the address people publish in order to receive bitcoins. Note that you cannot determine the public key or the private key from the address. If you lose your private key (for instance by throwing out your hard drive), your bitcoins are lost forever.

Finally, the Wallet Interchange Format key (WIF) is used to add a private key to your client wallet software. This is simply a Base58Check encoding of the private key into ASCII, which is easily reversed to obtain the 256-bit private key. [...]

To summarize, there are three types of keys: the private key, the public key, and the hash of the public key, and they are represented externally in ASCII using Base58Check encoding. The private key is the important key, since it is required to access the bitcoins and the other keys can be generated from it. The public key hash is the Bitcoin address you see published.

[...]

A transaction is the basic operation in the Bitcoin system. You might expect that a transaction simply moves some bitcoins from one address to another address, but it's more complicated than that. A Bitcoin transaction moves bitcoins between one or more inputs and outputs. Each input is a transaction and address supplying bitcoins. Each output is an address receiving bitcoin, along with the amount of bitcoins going to that address.

[...]

Each input used must be entirely spent in a transaction. If an address received 100 bitcoins in a transaction and you just want to spend 1 bitcoin, the transaction must spend all 100. The solution is to use a second output for change, which returns the 99 leftover bitcoins back to you.

Transactions can also include fees. If there are any bitcoins left over after adding up the inputs and subtracting the outputs, the remainder is a fee paid to the miner. The fee isn't strictly required, but transactions without a fee will be a low priority for miners and may not be processed for days or may be discarded entirely.

[...]


Manually creating a transaction

For my experiment I used a simple transaction with one input and one output. [...] I started by bying bitcoins from Coinbase and putting 0.00101234 bitcoins into address 1MMMMSUb1piy2ufrSguNUdFmAcvqrQF8M5, which was transaction 81b4c832.... My goal was to create a transaction to transfer these bitcoins to the address I created above, 1KKKK6N21XKo48zWKuQKXdvSsCf95ibHFa, subtracting a fee of 0.0001 bitcoins. Thus, the destination address will receive 0.00091234 bitcoins.

[...]

Following the specification
[ http://en.bitcoin.it/wiki/Protocol_specification#tx ],
the unsigned transaction can be assembled fairly easily, as shown below. There is one input, which is using output 0 (the first output) from transaction 81b4c832.... Note that this transaction hash is inconveniently reversed in the transaction. The output amount is 0.00091234 bitcoins (91234 is 0x016462 in hex), which is stored in the value field in little-endian form. The cryptographic parts - scriptSig and scriptPubKey - are more complex and will be discussed later.

[Unsigned Transaction]
- version: 01 00 00 00
- input count: 01
- input
-- previous output hash (reversed): 48 4d 40 d4 5b 9e a0 d6 52 fc a8 25 8a b7 ca a4 25 41 eb 52 97 58 57 f9 6f b5 0c d7 32 c8 b4 81
-- previous output index: 00 00 00 00
-- script length:
-- scriptSig: script containing signature
-- sequence: ff ff ff ff
- output count: 01
- output
-- value: 62 64 01 00 00 00 00 00
-- script length:
-- scriptPubKey: script containing destination address
- block lock time: 00 00 00 00

[...]

The final transaction is shown below. This combines the scriptSig and scriptPubKey above with the unsigned transaction described earlier.

[Signed Transaction]
- version: 01 00 00 00
- input count: 01
- input:
-- previous output hash (reversed): 48 4d 40 d4 5b 9e a0 d6 52 fc a8 25 8a b7 ca a4 25 41 eb 52 97 58 57 f9 6f b5 0c d7 32 c8 b4 81
-- previous output index: 00 00 00 00
-- script length: 8a
-- scriptSig: 47 30 44 02 20 2c b2 65 bf 10 70 7b f4 93 46 c3 51 5d d3 d1 6f c4 54 61 8c 58 ec 0a 0f f4 48 a6 76 c5 4f f7 13 02 20 6c 66 24 d7 62 a1 fc ef 46 18 28 4e ad 8f 08 67 8a c0 5b 13 c8 42 35 f1 65 4e 6a d1 68 23 3e 82 01 41 04 14 e3 01 b2 32 8f 17 44 2c 0b 83 10 d7 87 bf 3d 8a 40 4c fb d0 70 4f 13 5b 6a d4 b2 d3 ee 75 13 10 f9 81 92 6e 53 a6 e8 c3 9b d7 d3 fe fd 57 6c 54 3c ce 49 3c ba c0 63 88 f2 65 1d 1a ac bf cd
-- sequence: ff ff ff ff
- output count: 01
- output:
-- value: 62 64 01 00 00 00 00 00
-- script length: 19
-- scriptPubKey: 76 a9 14 c8 e9 09 96 c7 c6 08 0e e0 62 84 60 0c 68 4e d9 04 d1 4c 5c 88 ac
- block lock time: 00 00 00 00

Very helpful. Bearing in mind the Signed Transaction format described above, let's have another look at the transaction selected earlier.




I'll split it into single bytes (two hex characters represent one byte).




So the selected transaction, in single bytes, is:




Analysis:

- The first four bytes are the version: 01 00 00 00

- The next byte is the input count: 01

- The next item on this tree level should be an "input", which will consist of: previous output hash (reversed), previous output index, script length, scriptSig, and sequence.
-- If the input count were e.g. 02, then there would be two input items.
--- A single byte for input count would imply a maximum of 255 input items. Is this right?

I'll look at the specification linked from Ken Shirriff's article.
en.bitcoin.it/wiki/Protocol_specification#tx

I see that tx_in (transaction input) has a field size of 1+ (i.e. 1 or more bytes). Its data type is var_int.

The text "var_int" links to:
en.bitcoin.it/wiki/Protocol_documentation#Variable_length_integer

Excerpt:

Variable length integer

Integer can be encoded depending on the represented value to save space. Variable length integers always precede an array/vector of a type of data that may vary in length. Longer numbers are encoded in little endian.

- var_int value: < 0xFD
-- Storage length = 1
-- Format = uint8_t

- var_int value: <= 0xFFFF
-- Storage length = 3
-- Format = 0xFD followed by the length as uint16_t

- var_int value: <= 0xFFFF FFFF
-- Storage length = 5
-- Format = 0xFE followed by the length as uint32_t

- var_int value: -
-- Storage length = 9
-- Format = 0xFF followed by the length as uint64_t

If you're reading the Satoshi client code (BitcoinQT) it refers to this encoding as a "CompactSize".

Hm. 0x is a prefix used to indicate a hex number.

I'm not sure what the "-" represents. I would have thought that "<= 0xFFFF FFFF FFFF FFFF" would be written there instead.

Ok, let's work through this:
- If the value of the first byte is less than 253 (< 0xFD), then there is only one byte in the number, and this byte is the number's value. Largest number that can be represented in this format: 252.
- If the value of the first byte is 253 (0xFD), then there are three bytes in the number, and the next two bytes are the number's value. Largest number that can be represented in this format: FF FF, which in decimal is 255*256 + 255 = 65535.
- If the value of the first byte is 254 (0xFE), then there are five bytes in the number, and the next four bytes are the number's value. Largest number that can be represented in this format: FF FF FF FF, which in decimal is 255*(256^3) + 255*(256^2) + 255*256 + 255 = 4294967295.
- If the value of the first input count byte is 255 (0xFF), then there are nine bytes in the number, and the next eight bytes are the number's value. Largest number that can be represented in this format: FF FF FF FF FF FF FF FF, which in decimal is 255*(256^7) + 255*(256^6) + 255*(256^5) + 255*(256^4) + 255*(256^3) + 255*(256^2) + 255*256 + 255 = 18446744073709551615.

There are presumably several limits (explicit or emergent) on the number of transaction inputs in the bitcoind code.

One mentioned in an earlier excerpt was:
"The transaction must be smaller than 100,000 bytes. That's around 200 times larger than a typical single-input, single-output P2PKH transaction."


Let's move back to analysis.

- Within the input item, the first item should be the "previous output hash (reversed)". I think this is the hash of the previous transaction that contains this input.

In Ken Shirriff's signed transaction, this is: 48 4d 40 d4 5b 9e a0 d6 52 fc a8 25 8a b7 ca a4 25 41 eb 52 97 58 57 f9 6f b5 0c d7 32 c8 b4 81

Let's find its length. Hashes have a fixed length, so I should be able to use this length to select the previous output hash in the transaction I am analysing.



Note: If I pipe to directly:

then the result is 65. (I knew this result was wrong because a hex number's length should be even.) I think that a newline character is added by . Some reading indicates that this behaviour may be specific to OS X.


64 hex letters == 32 bytes.

32 bytes == 256 bits.


If the output hash is 256 bits, it's probably produced by the SHA256 hash function.


I'll use python to select slices of the transaction.





So, in the raw transaction, the output hash appears here:




Next comes the "previous output index", the position of the input within the previous transaction. Technically "input" here means "unspent output".

In Ken Shirriff's transaction, the bytes for the previous output index were: 00 00 00 00

So, four bytes.

In my selected transaction, the next four bytes are: 01 00 00 00

This appears to be in little-endian format i.e. the value is "1". The implied indices for unspent outputs in a transaction start from 0, so this is the second unspent output.

Browse to:
blockchain.info/tx/9ff7742262f68c560efd352f435b977c024797dc538f7efa08a467039858e42f
The source address is: 1CXg2fkCXCoHHnr4ijvZCTdqe9hPQkyDZG
and it has an "Output" link, which leads to:
blockchain.info/tx-index/341730624/1
It is indeed displayed as the second output address in the previous transaction.


Next is the script length, which according to
en.bitcoin.it/wiki/Protocol_specification#tx
is a var_int.

The next byte for this transaction is 6b, which is less than FD, so it is itself the value. 6b = 6*16 + 11 = 107

Therefore, the next 107 bytes are the scriptSig.



The transaction as a whole is:



452 hex characters long.

452/2 = 226 bytes, which matches the length reported by blockchain.info earlier.


Our current position in the transaction is: 4 + 1 + 32 + 4 + 1 = 42. We have just looked at byte 42.
Starting from index 0, we are at index 41.

In python, print transaction[2*42:2*(42+107)].

result:



So, in the raw transaction, the scriptSig appears here:




I'll leave the scriptSig for now.


Next: sequence.

In Ken Shirriff's transaction, this was: ff ff ff ff

In this case, it is: fd ff ff ff

I wonder why it's set to "fd ff ff ff", rather than 0.


That's the end of the input item.


Next: The output count

output count == the number of output items

According to
en.bitcoin.it/wiki/Protocol_specification#tx
the output count is a var_int.

The next byte is 02, which is less than FD, so this byte is the value of the output count number. 0*16 + 2 = 2.

There are two outputs, as seen previously in the blockchain.info output earlier.


Next: value (of the first output)

In Ken Shirriff's transaction, this is: 62 64 01 00 00 00 00 00

In the excerpt above, he notes that this is a little-endian value.

So, eight bytes.

In my transaction, the next eight bytes are: e8 d9 41 00 00 00 00 00

In decimal, the value is (14*16+8) + (13*16+9)*256 + (4*16+1)*(256^2) = 4315624 satoshi == 0.04315624 bitcoin.


Next: script length

According to
en.bitcoin.it/wiki/Protocol_specification#tx
the script length is a var_int.

The next byte is 19, which is less than FD, so this byte is the value of the script length number. 1*16 + 9 = 25.

The next 25 bytes are the scriptPubKey.


Our current position in the transaction is: 4 + 1 + 32 + 4 + 1 + 107 + 4 + 1 + 8 + 1 = 163. We have just looked at byte 163.
Starting from index 0, we are at index 162.

In python, print transaction[2*163:2*(163+25)].

result:
76a914338cdde52f708236affa5675f969606ff846ee6f88ac


So, in the raw transaction, the scriptPubKey appears here:




I'll leave the scriptPubKey for now.


That's the end of the first output item.


Next: another output item.


Next: value (of the second output)

In my transaction, the next eight bytes are: c4 71 6e 01 00 00 00 00

In decimal, the value is (12*16+4) + (7*16+1)*256 + (6*16+14)*(256^2) + (0*16+1)*(256^3) = 24015300 satoshi == 0.24015300 bitcoin.


Next: script length (of the second output)

The next byte is 19, which is less than FD, so this byte is the value of the script length number. 1*16 + 9 = 25.

The next 25 bytes are the scriptPubKey (of the second output).


Our current position in the transaction is: 4 + 1 + 32 + 4 + 1 + 107 + 4 + 1 + 8 + 1 + 25 + 8 + 1 = 197. We have just looked at byte 197.
Starting from index 0, we are at index 196.

In python, print transaction[2*197:2*(197+25)].

result:
76a9143496950f1a01285a1605ac9337c06a5596b9fcd888ac


So, in the raw transaction, the scriptPubKey of the second output appears here:




I'll leave the scriptPubKey for now.


That's the end of the second output item.


The last four bytes of the raw transaction are the block lock time.

In Ken Shirriff's transaction, these are: 00 00 00 00

In mine, they are: ca ee 07 00

I'm not sure whether this is little-endian or big-endian.



Let's write my selected raw transaction in a more readable, subdivided form:


Ken Shirriff's signed transaction:




The selected raw transaction, in single bytes:




The selected raw transaction, in sections:




I wonder why the scriptSig in Ken Shirriff's transaction is longer than the scriptSig in my selected transaction.




Next: Find out how to verify the signature on Ken Shirriff's transaction. Later, I will use what I have learned to attempt to verify the signature on my selected transaction.



Excerpts from Ken Shirriff's article:

You might expect that a Bitcoin transaction is signed simply by including the signature in the transaction, but the process is much more complicated. In fact, there is a small program inside each transaction that gets executed to decide if a transaction is valid. This program is written in Script, the stack-based Bitcoin scripting language.

[...]

The Script language is surprisingly complex, with about 80 different opcodes. It includes arithmetic, bitwise operations, string operations, conditionals, and stack manipulation. The language also includes the necessary cryptographic operations (SHA-256, RIPEMD, etc.) as primitives. In order to ensure that scripts terminate, the language does not contain any looping operations. (As a consequence, it is not Turing-complete.) [...]

In order for a Bitcoin transaction to be valid, the two parts of the redemption script must run successfully. The script in the old transaction is called scriptPubKey and the script in the new transaction is called scriptSig. To verify a transaction, the scriptSig executed followed by the scriptPubKey. If the script completes successfully, the transaction is valid and the Bitcoin can be spent. Otherwise, the transaction is invalid. The point of this is that the scriptPubKey in the old transaction defines the conditions for spending the bitcoins. The scriptSig in the new transaction must provide the data to satisfy the conditions.

In a standard transaction, the scriptSig pushes the signature (generated from the private key) to the stack, followed by the public key. Next, the scriptPubKey (from the source transaction) is executed to verify the public key and then verify the signature.

As expressed in Script, the scriptSig is:

PUSHDATA
signature data and SIGHASH_ALL
PUSHDATA
public key data

The scriptPubKey is:

OP_DUP
OP_HASH160
PUSHDATA
Bitcoin address (public key hash)
OP_EQUALVERIFY
OP_CHECKSIG

When this code executes, PUSHDATA first pushes the signature to the stack. The next PUSHDATA pushes the public key to the stack. Next, OP_DUP duplicates the public key on the stack. OP_HASH160 computes the 160-bit hash of the public key. PUSHDATA pushes the required Bitcoin address. Then OP_EQUALVERIFY verifies the top two stack values are equal - that the public key hash from the new transaction matches the address in the old address. This proves that the public key is valid. Next, OP_CHECKSIG checks that the signature of the transaction matches the public key and signature on the stack. This proves that the signature is valid.

Hm. Ok.
Notes:
- The previous/source transaction that contains the unspent output (which is used as an input in the current transaction) also holds the scriptPubKey, which roughly means "when this unspent output is used as an input for a new transaction (i.e. 'spent'), the transaction must be signed by the private key corresponding to the bitcoin address that holds this unspent output".
- The new/current transaction contains a scriptSig, which contains the signature that satisfies the condition set by the scriptPubKey.
- The scriptSig contains the bitcoin public key. This public key corresponds to the private key of the bitcoin address that "holds" the unspent output that the new transaction will spend. (It "holds" the unspent output in the sense that, according to the bitcoin distributed ledger, this unspent output is associated with this bitcoin address.)
-- Note: The bitcoin public key, when reformatted in a particular way, becomes the bitcoin address.
- The scriptPubKey contains the hash of the bitcoin public key. The scriptSig of a new transaction must contain the bitcoin public key that hashes to this hash value.



So, I need to learn how to execute the various operations in the signature verification. I also need to learn exactly which data is required as input for these operations and which format(s) this data must be in before the operations are performed.


There is one scriptPubKey per output in the selected transaction. If they are used in a new transaction, each will probably require a separate signature. Therefore, when making a new transaction, each input must be signed, presumably separately. I think that each signature will apply to the raw unsigned form of the transaction, and perhaps only to the section of the transaction that deals with a specific input. Some manipulation will therefore be required to get the transaction data into the signed form, in order to verify a signature.


The scriptSig signature does several things:
- It proves that the transaction has not been changed since it was created.
- It proves that the transaction was created by someone who had a specific public key (which is contained in the scriptSig)
- It proves that the transaction was created by someone who had the private key that corresponds to the specific public key required by the scriptPubKey of the relevant input.


Hm. In order to properly verify Ken Shirriff's transaction (i.e. in the way that the bitcoin client would verify it), I need the scriptPubKey of the input, which will be in the previous/source transaction. I will then verify that the scriptSig of Ken Shirriff's transaction satisfies this scriptPubKey.


From an earlier excerpt from Ken Shirriff's article:
"I started by bying bitcoins from Coinbase and putting 0.00101234 bitcoins into address 1MMMMSUb1piy2ufrSguNUdFmAcvqrQF8M5, which was transaction 81b4c832...."
In the article, "81b4c832...." is linked to:
blockchain.info/tx/81b4c832d70cb56ff957589752eb4125a4cab78a25a8fc52d6a09e5bd4404d48

This transaction contains 3 inputs and 2 outputs. The first output is to address 1MMMMSUb1piy2ufrSguNUdFmAcvqrQF8M5.


All the input and output addresses begin with "1", so none of them are multisig. (I think that multisig addresses may affect the transaction format.)



I'll begin writing a transaction parser.


I'll get the raw transaction by appending "?format=hex" to the hyperlink reference.

Browse to:
http://blockchain.info/tx/81b4c832d70cb56ff957589752eb4125a4cab78a25a8fc52d6a09e5bd4404d48?format=hex

Result:




I'll refer to this transaction as "tr_ken1".

Ken Shirriff's transaction is "tr_ken2".

My selected transaction is "tr_s2". Whichever transaction provides the single input to my selected transaction will be "tr_s1".



First goal for a transaction parser: Read the raw transaction and output it in readable sections.



Make a new directory in which to work.

Save the raw transaction above as "tr_ken1.txt" in the work directory.

In TextWrangler, create a new file "parser1.py" and save it in the work directory.


Let's develop.



































































Add as the first line of .




Edit last line of to be:







Hm.


Ah.


should have been


Edit this line.






Let's just look at the first input for now.

Note: This

is an error. Need to explicitly make a copy of the dictionary for each entry in the list.













Ok. Looks good.
previous_output_index (01 00 00 00) and sequence (ff ff ff ff) hold reasonable values.

Let's do all the inputs.










Ok.
The previous_output_index and the sequence for each input hold reasonable values.


Next: the outputs.















Just the first output for now.



Error:

in the "print data" section was not updating script_length with each input.














Looks good.
Output #0's value and script_length are reasonable.



Let's try with both outputs.












Good. Finally, get the block lock time. Also, add a check to confirm that we have reached the end of the raw transaction i.e. that the index has the exact expected value.










I'd like to see the output values in bitcoin rather than little-endian hex.












Hm. Good.

Remove from , as it is now unnecessary.



For comparison, I'll get the result of pasting in the raw transaction tr_ken1 into:
blockchain.info/decode-tx

Result:




Let's compare results.


These two results agree on:
- size (617 bytes)
- block lock time (0 or 00 00 00 00)
- version (1 or 01 00 00 00 (little-endian))
- input_count (3 or 03)
- output_count (2 or 02)
-- Note: some reading indicates that vin_sz == input_count and vout_sz == output_count.

Differences:
- blockchain.info: The 'hash' on the first level of the tree
(81b4c832d70cb56ff957589752eb4125a4cab78a25a8fc52d6a09e5bd4404d48)
is not present in my parsing result. Some reading indicates that this is the transaction id of the transaction, calculated by hashing the transaction. I'm not sure what format the transaction has to be in before this hashing operation.


The previous output hash values in the inputs appear to be reversed in the blockchain.info result.

Let's confirm equality.

Example of checking the equality of a hash from blockchain.info and from my result:



The "_b1" suffix stands for "blockchain.info 1". The "_s1" suffix stands for "StJohn 1".

Repeat this process for the other two input previous_output_hash values.

They're all equal.


More agreements:
- The inputs appear in the same order.
- The inputs have the same previous_output_index values (1, 0, 1 or 01 00 00 00, 00 00 00 00, 01 00 00 00)



The scriptSig values in my result output do not appear to be reversed.


Let's confirm equality of the scriptSig values.

Example of checking the equality of a scriptSig from blockchain.info and from my result:




Repeat this process for the other two input scriptSig values.

They're all equal.


In the blockchain.info result, the "script" item within each output would appear to be the scriptPubKey in my result.

The scripPubKey values in my result do not appear to be reversed.

Confirm equality of the scriptPubKey values, using the same process for checking the scriptSig values shown above.

They're both equal.

More agreements:
- The outputs are in the same order.
- Output #0 has the same value in each result (101234 or 0.00101234).
- Output #1 has the same value in each result (1738645 or 0.01738645).


Notes:
- The "script_string" value appears to be decoded from the "script" value.
- It's strange that the "address" for an output is returned in the blockchain.info result, as this information is not part of a raw transaction. Only the hash of the public key is stored in the transaction, not the public key itself. The public key becomes known only when the output is spent in a new transaction (the public key is included within the scriptSig). The "address" must therefore be retrieved from the next transaction that spends this output, stored in the data system of blockchain.info.
- Sequence numbers are included in my result but not in the blockchain.info result.












Ok. Let's continue.



In Ken Shirriff's signed transaction (tr_ken2), the previous output index of the single input was: 00 00 00 00
This equals 0.

So, the first output from the previous transaction (tr_ken1) is used as the input in tr_ken2. (Outputs in a transaction are implicitly 0-indexed.)

From the output of parser1.py, I see that the scriptPubKey of output #0 is:
76 a9 14 df 3b d3 01 60 e6 c6 14 5b aa f2 c8 8a 88 44 c1 3a 00 d1 d5 88 ac


Hm.

Next: Look at the scriptPubKey format for basic transactions (i.e. where outputs are Pay-To-Public-Key-Hash (P2PKH)).



In this sentence from an earlier excerpt from Ken Shirriff's article,
"The Script language is surprisingly complex, with about 80 different opcodes."
The phrase "80 different opcodes" links to
en.bitcoin.it/wiki/Script



Excerpts from:
en.bitcoin.it/wiki/Script

Bitcoin uses a scripting system for transactions. Forth-like, Script is simple, stack-based, and processed from left to right. It is intentionally not Turing-complete, with no loops.

A script is essentially a list of instructions recorded with each transaction that describe how the next person wanting to spend the Bitcoins being transferred can gain access to them. The script for a typical Bitcoin transfer to destination Bitcoin address D simply encumbers future spending of the bitcoins with two things: the spender must provide

1) a public key that, when hashed, yields destination address D embedded in the script, and
2) a signature to prove ownership of the private key corresponding to the public key just provided.

[...]

A transaction is valid if nothing in the combined script triggers failure and the top stack item is True (non-zero) when the script exits. [...]

This document is for information purposes only. Officially, Bitcoin script is defined by its reference implementation
[ http://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp ].

The stacks hold byte vectors. When used as numbers, byte vectors are interpreted as little-endian variable-length integers with the most significant bit determining the sign of the integer. Thus 0x81 represents -1. 0x80 is another representation of zero (so called negative 0). Positive 0 is represented by a null-length vector. Byte vectors are interpreted as Booleans where False is represented by any representation of zero and True is represented by any representation of non-zero.

Leading zeros in an integer and negative zero are allowed in blocks but get rejected by the stricter requirements which standard full nodes put on transactions before retransmitting them. Byte vectors on the stack are not allowed to be more than 520 bytes long. Opcodes which take integers and bools off the stack require that they be no more than 4 bytes long, but addition and subtraction can overflow and result in a 5 byte integer being put on the stack.

Hm.

0x81 in binary is: 1000 0001
0x80 in binary is: 1000 0000

Ok. So in Script, any byte that starts with a "1" bit is negative. The first one to do so, 0x80 or 1000 0000, is "negative 0".

0x81 is -1 in decimal.

Normal ("positive") 0 is 0x00 or 0000 0000.

Booleans:
- 0x00 or 0x80 are False
- Any other value is True.

Key points:
- Byte vectors are little-endian variable-length integers.
- Don't use negative 0 (0x80) bytes. Don't use leading zero bytes in the integer values. Both of these cause problems with transaction retransmission.
- Maximum length of byte vector is 520 bytes.
- Don't use integers and boolean values that are longer than 4 bytes.


Further reading indicates that a "stack" is the abstract idea of a sequential collection of objects on which certain operations are defined. Implementations may vary across platforms but must behave in the same way in order to be considered to be the same stack item. This means that a stack can be implemented in Python on one computer and in C++ on another computer, but as long as the two stack implementations can perform the same operations on the same domain, they can pass data between themselves without any trouble.

The stack itself does not implement a SHA256 hash function, it simply indicates when and on what data a SHA256 function should operate. The details of implementing SHA256 are left to the stack implementation.



From reading the list of opcodes shown at:
en.bitcoin.it/wiki/Script
it appears that all opcodes are exactly one byte.


Let's re-quote an excerpt from Ken Shirriff's article:

In a standard transaction, the scriptSig pushes the signature (generated from the private key) to the stack, followed by the public key. Next, the scriptPubKey (from the source transaction) is executed to verify the public key and then verify the signature.

As expressed in Script, the scriptSig is:

PUSHDATA
signature data and SIGHASH_ALL
PUSHDATA
public key data

The scriptPubKey is:

OP_DUP
OP_HASH160
PUSHDATA
Bitcoin address (public key hash)
OP_EQUALVERIFY
OP_CHECKSIG

When this code executes, PUSHDATA first pushes the signature to the stack. The next PUSHDATA pushes the public key to the stack. Next, OP_DUP duplicates the public key on the stack. OP_HASH160 computes the 160-bit hash of the public key. PUSHDATA pushes the required Bitcoin address. Then OP_EQUALVERIFY verifies the top two stack values are equal - that the public key hash from the new transaction matches the address in the old address. This proves that the public key is valid. Next, OP_CHECKSIG checks that the signature of the transaction matches the public key and signature on the stack. This proves that the signature is valid.

So, it looks as though each of these opcodes:
PUSHDATA, OP_DUP, OP_HASH160, OP_EQUALVERIFY, OP_CHECKSIG
is a single byte in a script byte sequence in the raw transaction. The stack implementation knows how to interpret these opcodes and perform the indicated operations.

Exceptions: OP_PUSHDATA1 is two bytes long, OP_PUSHDATA2 is three bytes long, and OP_PUSHDATA4 is five bytes long. There may be other multi-byte opcodes.



Excerpt from:
en.bitcoin.it/wiki/Script

Standard Transaction to Bitcoin address (pay-to-pubkey-hash)

scriptPubKey: OP_DUP OP_HASH160 {pubKeyHash} OP_EQUALVERIFY OP_CHECKSIG
scriptSig: {sig} {pubKey}

To demonstrate how scripts look on the wire, here is a raw scriptPubKey:

OP_DUP: 76
OP_HASH160: A9
Bytes to push: 14
Data to push: 89 AB CD EF AB BA AB BA AB BA AB BA AB BA AB BA AB BA AB BA
OP_EQUALVERIFY: 88
OP_CHECKSIG: AC

Note: scriptSig is in the input of the spending transaction and scriptPubKey is in the output of the previously unspent i.e. "available" transaction.

Here is how each word is processed:

[Begin Stack Processing]

[Stage 1]
- Stack: Empty
- Script: {sig} {pubKey} OP_DUP OP_HASH160 {pubKeyHash} OP_EQUALVERIFY OP_CHECKSIG
- Description: scriptSig and scriptPubKey are combined.

[Stage 2]
- Stack: {sig} {pubKey}
- Script: OP_DUP OP_HASH160 {pubKeyHash} OP_EQUALVERIFY OP_CHECKSIG
- Description: Constants are added to the stack.

[Stage 3]
- Stack: {sig} {pubKey} {pubKey}
- Script: OP_HASH160 {pubKeyHash} OP_EQUALVERIFY OP_CHECKSIG
- Description: Top stack item is duplicated.

[Stage 4]
- Stack: {sig} {pubKey} {pubHashA}
- Script: {pubKeyHash} OP_EQUALVERIFY OP_CHECKSIG
- Description: Top stack item is hashed.

[Stage 5]
- Stack: {sig} {pubKey} {pubHashA} {pubKeyHash}
- Script: OP_EQUALVERIFY OP_CHECKSIG
- Description: Constant added.

[Stage 6]
- Stack: {sig} {pubKey}
- Script: OP_CHECKSIG
- Description: Equality is checked between the top two stack items.

[Stage 7]
- Stack: true
- Script: Empty.
- Description: Signature is checked for top two stack items.

[End Stack Processing]

Ok. Let's look up the relevant opcodes.


From:
en.bitcoin.it/wiki/Script

I find that:




Notes:
- The "opcode" is the decimal value of the hex byte.
- "Input: x1 x2" presumably means that the inputs to the operation are the first two items on the stack (judging by the example stack process shown above), which indicates that the stack is 1-indexed.
- For OP_HASH160, "Input: in" presumably means the top item on the stack.



I think those are all the opcodes I need for reading a standard scriptPubKey.


This is the scriptPubKey under consideration (from tr_ken1):
76 a9 14 df 3b d3 01 60 e6 c6 14 5b aa f2 c8 8a 88 44 c1 3a 00 d1 d5 88 ac

Hm.

First byte is 76, or rather 0x76, which is OP_DUP.

Second byte is a9, which is OP_HASH160.

Next: 0x14, which in decimal is 1*16+4 = 20, which is between 1 and 75, so it means PUSHDATA(20), i.e. push the next 20 bytes of data onto the stack, presumably as a single stack item.

Next 20 bytes: df 3b d3 01 60 e6 c6 14 5b aa f2 c8 8a 88 44 c1 3a 00 d1 d5

These 20 bytes are presumably the public key hash i.e. if someone's bitcoin public key hashes to this value, they can use the corresponding private key to spend this output.

Next byte: 88, which is OP_EQUALVERIFY.

Last byte: ac, which is OP_CHECKSIG.


So, in readable form, the scriptPubKey is:





Now let's look at the scriptSig in tr_ken2, which should satisfy the cryptographic condition set by scriptPubKey in tr_ken1.


scriptSig:



The first byte, 47, which in decimal is 4*16+7 = 71, which is within the inclusive range 1-75, is a PUSHDATA command, in this case PUSHDATA(71).

I'm using PUSHDATA(n) to mean that:
- the hex byte in question indicates that the next n bytes are data that should be pushed onto the stack as a single new stack item.

I'll use python to select the next 71 bytes.






So, within scriptSig, the next 71 bytes, which should be the transaction signature, are located here:

scriptSig:



Note: To find the end of the 71-byte sequence, choose the last three bytes from the final string shown in the python output above, which are "3e 82 01", copy the scriptSig to the bottom of the document, position the cursor before scriptSig, and use the text editor (TextWrangler in this case) to search for the byte string "3e 82 01". It's unlikely that e.g. three bytes will repeat exactly within scriptSig. You can search again from the end of the first instance of the byte string in order to make sure.


The next byte is 41, which in decimal is 4*16+1 = 65, which is within the inclusive range 1-75, is a PUSHDATA command, in this case PUSHDATA(65).


Use python as shown above to select the next 65 bytes. Check that the number of hex bytes selected is actually 65 (Python slicing is elastic/forgiving) using: len(s2[73:73+65])


So, within scriptSig, the last 65 bytes, which should be the bitcoin public key, are located here:

scriptSig:



So, in readable form, the scriptSig is:




Next: I can actually just crank the stack machine by hand, by performing the required operations in the specified order on the correctly selected data.







Here is a manual stack machine:

[Begin Stack Processing]

[Stage 1]
- Stack: Empty
- Script: PUSHDATA(71) [sequence of 71 bytes] PUSHDATA(65) [sequence of 65 bytes] OP_DUP OP_HASH160 PUSHDATA(20) [sequence of 20 bytes] OP_EQUALVERIFY OP_CHECKSIG
- Description: scriptSig and scriptPubKey are combined.

Let's begin executing the stack commands.

The first command is to "push next 71 bytes onto the stack as a new stack item". For convenience, I will refer to the next 71 bytes (value: 30 44 02 20 2c b2 65 bf 10 70 7b f4 93 46 c3 51 5d d3 d1 6f c4 54 61 8c 58 ec 0a 0f f4 48 a6 76 c5 4f f7 13 02 20 6c 66 24 d7 62 a1 fc ef 46 18 28 4e ad 8f 08 67 8a c0 5b 13 c8 42 35 f1 65 4e 6a d1 68 23 3e 82 01) as {sig}.

I will refer to the sequence of 65 bytes as {pubKey} and the sequence of 20 bytes as {pubKeyHash}.

[Stage 2]
- Stack: {sig}
- Script: PUSHDATA(65) [sequence of 65 bytes] OP_DUP OP_HASH160 PUSHDATA(20) [sequence of 20 bytes] OP_EQUALVERIFY OP_CHECKSIG
- Description: First command (PUSHDATA(71)) has been executed.

[Stage 3]
- Stack: {sig} {pubKey}
- Script: OP_DUP OP_HASH160 PUSHDATA(20) [sequence of 20 bytes] OP_EQUALVERIFY OP_CHECKSIG
- Description: Second command (PUSHDATA(65)) has been executed.

[Stage 4]
- Stack: {sig} {pubKey} {pubKey}
- Script: OP_HASH160 PUSHDATA(20) [sequence of 20 bytes] OP_EQUALVERIFY OP_CHECKSIG
- Description: Third command (OP_DUP) has been executed.


Hm. Ok, next stage requires some work. I have to take the top item on the stack and hash it twice, first with SHA-256 and then with RIPEMD-160.


In my archives, I have a Python implementation of SHA256, originally copied from the PyPy source code.

I downloaded it from:
bitbucket.org/pypy/pypy/src/tip/lib_pypy/_sha256.py
on 2017-05-12 and saved it as pypy_sha256.py.

I've saved my copy as an asset of this article. [link]

Save a copy of this file in the work directory.


Note: The sha256(object) class constructor requires its input to be a byte sequence in raw bytes, not hex bytes. The output is also a raw byte sequence. Both of these byte sequences are big-endian (i.e. the highest value byte is first in the sequence).


Let's test.


Create a new file in the work directory: op_hash160.py

The goal is to hash {pubKey}, which is:










Ok. The SHA256 digest of the {pubKey} data is:
acd518cad5449a573db372ff7e3330c4ffb40de59d662fcdc4090c4e021b850b




Next: RIPEMD-160.


In my archives, I have a Python implementation of RIPEMD160. I originally found it in Vitalik Buterin's pybitcointools repository at:
github.com/vbuterin/pybitcointools

The first two lines of the code are:


The original author, Björn Edström, has a website:
www.bjrn.se

After some searching, I found the code stored at:
www.bjrn.se/code/ripemdpy.txt
I downloaded a copy on 2017-08-04 and saved it as bjorn_edstrom_ripemd160.py.

I've saved my copy as an asset of this article. [link]

Save a copy of this file in the work directory.


Note: I think the RIPEMD160(arg) class constructor handles a raw byte sequence as input without any trouble. The author used the phrase "string argument" but I think that he meant "string of bytes" rather than "string of bytes that are valid ASCII characters".


Let's test.










Ok. The result of OP_HASH160 is:
df3bd30160e6c6145baaf2c88a8844c13a00d1d5

Let's split this into individual hex bytes:





Result:





This stage of the stack machine is:

[Stage 5]
- Stack: {sig} {pubKey} {pubKeyHash}
- Script: PUSHDATA(20) [sequence of 20 bytes] OP_EQUALVERIFY OP_CHECKSIG
- Description: Top stack item has been hashed.


Let's continue.


[Stage 6]
- Stack: {sig} {pubKey} {pubKeyHash} {pubKeyHashB}
- Script: OP_EQUALVERIFY OP_CHECKSIG
- Description: Command (PUSHDATA(65)) has been executed.

I've renamed the sequence of 65 bytes to pubKeyHashB, in order to differentiate it from the hash of the public key that was just calculated.


Next stage:

OP_EQUALVERIFY == run OP_EQUAL, then run OP_VERIFY.

OP_EQUAL returns 1 if the two top stack items are exactly equal, 0 otherwise.

Ok.

The current top two stack items are:
- {pubKeyHashB} = df 3b d3 01 60 e6 c6 14 5b aa f2 c8 8a 88 44 c1 3a 00 d1 d5
- {pubKeyHash} = df 3b d3 01 60 e6 c6 14 5b aa f2 c8 8a 88 44 c1 3a 00 d1 d5


Let's check whether they are equal.





They're equal. This means that OP_EQUAL returns 1.

Now run OP_VERIFY.

OP_VERIFY marks the transaction as invalid if top stack value is not true. The top stack value is removed.

For this stack machine, any value other than positive 0 (0x00) or negative 0 (0x80) is "true". OP_EQUAL returned "1", which in hex is 0x01, so OP_VERIFY does not mark the transaction as invalid. It then removes the top stack item.

From an earlier excerpt:

OP_EQUAL pops (removes from the top of the stack) the two values it compared, and replaces them with the result of that comparison: zero (false) or one (true).

So, in this case: OP_EQUAL removes the two top items ({pubKeyHash} and {pubKeyHashB}) and adds a new one ("1"). Then OP_VERIFY removes the "1" item.


So:

[Stage 7]
- Stack: {sig} {pubKey}
- Script: OP_CHECKSIG
- Description: Command OP_EQUALVERIFY has been executed. Transaction has not been marked invalid.



OP_CHECKSIG: The entire transaction's outputs, inputs, and script (from the most recently-executed OP_CODESEPARATOR to the end) are hashed. The signature used by OP_CHECKSIG must be a valid signature for this hash and public key. If it is, 1 is returned, 0 otherwise.




Hm.





I need the hash (which algorithm?) of the transaction (in what format?). Then I need to verify the signature, which (I think) means to check that the scriptSig's signature is the signed-by-the-public-key form of the hash-of-the-formatted-transaction.


Earlier, I found that the txid ("previous output hash") used in a transaction input is 256 bits long, and therefore probably the result of running the SHA256 algorithm. Perhaps SHA256 is also used to hash the raw transaction for signing.

However, the {pubKey} [bitcoin public key] above is 65 bytes == 520 bits long (not 256 bits).

From an earlier excerpt:

The Elliptic Curve DSA algorithm generates a 512-bit public key from the private key. (Elliptic curve cryptography will be discussed later.) This public key is used to verify the signature on a transaction. Inconveniently, the Bitcoin protocol adds a prefix of 04 to the public key.

512 bits + a single hex byte "04" is 520 bits. The first byte of {pubKey} is indeed 04.





Some earlier excerpts from:
bitcoin.org/en/developer-guide

All transactions, including the coinbase transaction, are encoded into blocks in binary rawtransaction format.

The rawtransaction format is hashed to create the transaction identifier (txid).

[...]

For a P2PKH-style output, Bob's signature script will contain the following two pieces of data:

1) His full (unhashed) public key, so the pubkey script can check that it hashes to the same value as the pubkey hash provided by Alice.

2) An secp256k1 signature made by using the ECDSA cryptographic formula to combine certain transaction data (described below) with Bob's private key. This lets the pubkey script verify that Bob owns the private key which created the public key.

Bob's secp256k1 signature doesn't just prove Bob controls his private key; it also makes the non-signature-script parts of his transaction tamper-proof so Bob can safely broadcast them over the peer-to-peer network.

[...]

The data Bob signs includes the txid and output index of the previous transaction, the previous output's pubkey script, the pubkey script Bob creates which will let the next recipient spend this transaction's output, and the amount of satoshis to spend to the next recipient. In essence, the entire transaction is signed except for any signature scripts, which hold the full public keys and secp256k1 signatures.

Hm.


More excerpts from Ken Shirriff's article:

Signing the transaction

I found signing the transaction to be the hardest part of using Bitcoin manually, with a process that is surprisingly difficult and error-prone. The basic idea is to use the ECDSA elliptic curve algorithm and the private key to generate a digital signature of the transaction, but the details are tricky. The signing process has been described through a 19-step process
[ http://bitcoin.stackexchange.com/questions/3374/how-to-redeem-a-basic-tx ]
(more info)
[ http://en.bitcoin.it/wiki/OP_CHECKSIG ].

[...]

The biggest complication is the signature appears in the middle of the transaction, which raises the question of how to sign the transaction before you have the signature. To avoid this problem, the scriptPubKey script is copied from the source transaction into the spending transaction (i.e. the transaction that is being signed) before computing the signature. Then the signature is turned into code in the Script language, creating the scriptSig script that is embedded in the transaction. It appears that using the previous transaction's scriptPubKey during signing is for historical reasons rather than any logical reason. For transactions with multiple inputs, signing is even more complicated since each input requires a separate signature, but I won't go into the details.

One step that tripped me up is the hash type. Before signing, the transaction has a hash type constant temporarily appended. For a regular transaction, this is SIGHASH_ALL (0x00000001). After signing, this hash type is removed from the end of the transaction and appended to the scriptSig.

Another annoying thing about the Bitcoin protocol is that the signature and public key are both 512-bit elliptic curve values, but they are represented in totally different ways: the signature is encoded with DER encoding but the public key is represented as plain bytes. In addition, both values have an extra byte, but positioned inconsistently: SIGHASH_ALL is put after the signature, and type 04 is put before the public key.

Debugging the signature was made more difficult because the ECDSA algorithm uses a random number. Thus, the signature is different every time you compute it, so it can't be compared with a known-good signature.

Update (Feb 2014): An important side-effect of the signature changing every time is that if you re-sign a transaction, the transaction's hash will change. This is known as Transaction Malleability. There are also ways that third parties can modify transactions in trivial ways that change the hash but not the meaning of the transaction. [...]

With these complications it took me a long time to get the signature to work. Eventually, though, I got all the bugs out of my signing code and succesfully signed a transaction. Here's the code snippet I used.

def makeSignedTransaction(privateKey, outputTransactionHash, sourceIndex, scriptPubKey, outputs):

myTxn_forSig = (makeRawTransaction(outputTransactionHash, sourceIndex, scriptPubKey, outputs)

+ "01000000") # hash code

s256 = hashlib.sha256(hashlib.sha256(myTxn_forSig.decode('hex')).digest()).digest()

sk = ecdsa.SigningKey.from_string(privateKey.decode('hex'), curve=ecdsa.SECP256k1)

sig = sk.sign_digest(s256, sigencode=ecdsa.util.sigencode_der) + '\01' # 01 is hashtype

pubKey = keyUtils.privateKeyToPublicKey(privateKey)

scriptSig = utils.varstr(sig).encode('hex') + utils.varstr(pubKey.decode('hex')).encode('hex')

signed_txn = makeRawTransaction(outputTransactionHash, sourceIndex, scriptSig, outputs)

verifyTxnSignature(signed_txn)

return signed_txn

Hm.

Ok. From the code, I see that the first step is to create a transaction to be signed and append a hash_type ("01000000") to it.

In a transaction, there is one scriptSig per input. In a transaction-to-be-signed, the scriptSig is replaced with the scriptPubKey of the unspent output. The signature will be created using the private key that corresponds to this scriptPubKey.

Question: If there are multiple inputs, a signature is needed for each one. Are all scriptSigs in a multiple-input-transaction replaced with the same scriptPubKey in the corresponding transaction-to-be-signed?

Ken Shirriff's code and article solves his problem (creating a valid 1-input-to-1-output transaction) and didn't tackle this question.

Alternative possibility: Only the scriptSig for 1 input is replaced with the scriptPubKey of the unspent-output-being-used-here-as-an-input. The other input scriptSigs are left blank during the signing.

Some reading indicates that the other scriptSigs are in fact replaced with a zero byte (0x00) within the transaction-to-be-signed.

Future: Test this by verifying a multiple-input transaction.




In Ken Shirriff's repository linked from this article, I find the code for the function makeRawTransaction() in txnUtils.py.




When this function was called earlier, scriptPubKey was passed in as the scriptSig argument.

I note that the length var_int of scriptSig is calculated in this function.



I'll create the transaction-to-be-signed manually.



Ken Shirriff's signed transaction (tr_ken2):




Note: tr_ken2 already has the necessary outputTransactionHash (previous_output_hash) and sourceIndex (previous_output_index).

The previous_output_hash is already reversed.


This is the relevant scriptPubKey from tr_ken1:


I need to construct a var_int with length of this scriptPubKey. It's included in the substitution.





So there are 25 bytes in scriptPubKey, which is 19 in hex.

So, now I substitute the relevant scriptPubKey from tr_ken1 into tr_ken2, and I append the hash_type (4 hex bytes) "01 00 00 00", creating tr_ken2_to_be_signed.




This line from earlier indicates that I now have to hash tr_ken2_to_be_signed twice using SHA256.



The result of this operation is the item that is actually signed.


Ok. Let's hash it twice.

First, get the hex bytes of tr_ken2_to_be_signed into a single string.

Copy the transaction above. Use TextWrangler's Find-and-Replace with grep enabled to replace "^-.*: " with "".




I entered the Python interpreter within my work directory, so the sha256 class can be imported from pypy_sha256.py.





The result of this operation is:
5fda68729a6312e17e641e9a49fac2a4a6a680126610af573caab270d232f850




In space-separated hex bytes, the result is:


This result is the double SHA256 hash of the transaction-to-be-signed.



Let's look at Ken Shirriff's verifyTxnSignature(signed_txn) function.

Its code is in txnUtils.py, along with the code for some of the functions it calls.





parseTxn(txn) and getSignableTxn(parsed) approximately do the same process that I have just done manually.

This line:

is a check for the hash type that was appended to the scriptSig.

From an earlier excerpt:

One step that tripped me up is the hash type. Before signing, the transaction has a hash type constant temporarily appended. For a regular transaction, this is SIGHASH_ALL (0x00000001). After signing, this hash type is removed from the end of the transaction and appended to the scriptSig.

Ken Shirriff's code appends this SIGHASH_ALL hash type in little-endian form "01 00 00 00" prior to signing, but the verification check looks at the last hex byte, which suggests that it was appended to scriptSig in big-endian form.

The tr_ken2 scriptSig in question is:



It does not end in "01".

However, the subdivided readable form of the scriptSig is:


This fits with the fact that the parsed() function returns "sig" and "pub" as separate items.

The transaction signature section, or {sig}, does end in 01, indicating that the hash type is appended to the {sig} section of the scriptSig, rather than to the entire scriptSig item itself.

The three bytes that preceed the "01" byte at the end of {sig} are not "00 00 00", suggesting that although a four byte version of the idea {hash_type==1} is appended to the transaction prior to signing, only a one byte version is appended to the signature in the final transaction.



I'll run parseTxn on tr_ken2 and take a look at its outputs.


First, get tr_ken2 as a hex byte string.


Ken Shirriff's signed transaction:




Following the same process as that applied earlier to get tr_ken2_to_be_signed into a single hex byte string, I get:













Ok. The last byte of "sig", as returned by the parsed() function, is "01" as expected. The first byte of "sig" is the same as the first byte of {sig} ("30").


The next line in verifyTxnSignature(txn) is:


So, we take the "sig" result from parsed(), which I think is the same as {sig}, without the last hash_type byte, and without the sig_length var_int at the beginning.

Then, we convert it from DER encoding to a hex byte string.

Here is tr_ken2 {sig} again (without the final 01 hash_type byte):




Let's look at keyUtils.py.


I find:






I have downloaded a copy of the ecdsa library available at
pypi.python.org/pypi/ecdsa/0.10
It came with this filename: ecdsa-0.10.tar.gz

I've saved my copy as an asset of this article. [link]


Let's uncompress the archive.




From within the resulting directory ecdsa-0.10, copy the directory ecdsa to the work directory.

The ecdsa directory contains an __init__.py file and a ecdsa.py file, so (I think) I should be able to use "import ecdsa" within a python script in the work directory. I don't know the exact details of how python importing works.













Result:
2cb265bf10707bf49346c3515dd3d16fc454618c58ec0a0ff448a676c54ff7136c6624d762a1fcef4618284ead8f08678ac05b13c84235f1654e6ad168233e82

Result in space-separated bytes:



Is the output 64 bytes?



128/2 = 64, so yes. (two hex characters are one byte.)


Let's look at the last three lines of verifyTxnSignature(txn).




So, the first line shows me that I need the public key from scriptSig in tr_ken2, which is:


Note: The result of running parser_ken.py shows that the length var_int at the start is not included.


The second of the three lines shows me that I should remove the first byte from the public key, convert it from hex into raw bytes, and then use the ecdsa library to create a key object from these raw bytes.

The first byte is "04".

Excerpt from earlier:

Inconveniently, the Bitcoin protocol adds a prefix of 04 to the public key.

So this first byte is a prefix, and is not part of the actual public key value.


Finally, the last line is an assertion that the signature is the result of signing the double-sha256-hash of the transaction-to-be-signed.


Ok.


Let's extend the capabilities of check_signature.py.









The ECDSA implementation in this library reports that the signature is valid.


32 bytes is 32*8 = 256 bits, which is the expected length for the result of running SHA256.

64 bytes is 64*8 = 512 bits, which is the expected length of a ECDSA public key.

A signature should be the same length as the key that was used to produce it, and indeed it is (64 bytes).




Excellent.




Next: Let's change a bit in the hash to see if the library correctly reports a verification failure.


I'll change
tr_ken2_hash_hex_bytes = "5f da 68 72 9a 63 12 e1 7e 64 1e 9a 49 fa c2 a4 a6 a6 80 12 66 10 af 57 3c aa b2 70 d2 32 f8 50"
to
tr_ken2_hash_hex_bytes = "5f da 68 72 9a 63 12 e1 7e 64 1e 9a 49 fa c2 a4 a6 a6 80 12 66 10 af 57 3c aa b2 70 d2 32 f8 51"

I've changed the last byte from 50 to 51. In hex byte, a single character represents 4 bits. The last 4 bits of the hash have been changed from 0000 to 0001, so the change is just a single bit.





Good.





Next: Attempt to verify the signature on my selected transaction (tr_s2). Streamline the process of verification if possible.



raw transaction tr_s2 as a hex byte string:




tr_s2 in space-separated hex bytes:




The result of manually reading tr_s2:





Let's parse tr_s2 with parser1.py and check that the results match those that were found manually.

Save tr_s2 into a new file called tr_s2.txt within the work directory. Edit parser1.py so that
file_path_1 = "tr_s2.txt"







Results match.



I'll write a second parser, using parser1.py as a guide.

This new parser should construct a Transaction object to store all the results.










[development occurs here]












Ok.

These two output lines within an input of the parsed transaction:

provide me with the information necessary to:
- look up the previous transaction that supplied this input (which will be tr_s1), then download it in raw form and parse it.
- select the scriptPubKey from the correct output from the parsed form of this previous transaction.



Construct query for getting raw transaction tr_s1 from blockchain.info:
http://blockchain.info/tx/36b325b30a8bdf60d835e65cbb97dd172cb2910d30c4060e7502b6a32cad8c4f?format=hex

Result:


Save this as tr_s1.txt in the work directory.

Edit parser2.py so that
raw_transaction_file_path = "tr_s1.txt"






The scriptPubKey of output #1 is:



This is the scriptPubKey challenge that the single scriptSig of tr_s2 satisfies.



Next: Write a script that can process a subset of Script and display it in a readable form.



Create a file script_processor1.py in the work directory. Run to change its permissions so that it can be run with the command .



[development occurs here]








Hm.

In the output, I can see that the first byte of the public_key_data in scriptSig is not actually 0x04. It's 0x02.


An earlier excerpt from:
bitcoin.org/en/developer-guide

Bitcoin ECDSA public keys represent a point on a particular Elliptic Curve (EC) defined in secp256k1. In their traditional uncompressed form, public keys contain an identification byte, a 32-byte X coordinate, and a 32-byte Y coordinate. The extremely simplified illustration below shows such a point on the elliptic curve used by Bitcoin, y^2 = x^3 + 7, over a field of contiguous numbers.

[illustration not included]

An almost 50% reduction in public key size can be realized without changing any fundamentals by dropping the Y coordinate. This is possible because only two points along the curve share any particular X coordinate, so the 32-byte Y coordinate can be replaced with a single bit indicating whether the point is on what appears in the illustration as the "top" side or the "bottom" side.

No data is lost by creating these compressed public keys - only a small amount of CPU is necessary to reconstruct the Y coordinate and access the uncompressed public key. Both uncompressed and compressed public keys are described in official secp256k1 documentation and supported by default in the widely-used OpenSSL library.

Because they're easy to use, and because they reduce almost by half the block chain space used to store public keys for every spent output, compressed public keys are the default in Bitcoin Core and are the recommended default for all Bitcoin software.

However, Bitcoin Core prior to 0.6 used uncompressed keys. This creates a few complications, as the hashed form of an uncompressed key is different than the hashed form of a compressed key, so the same key works with two different P2PKH addresses. This also means that the key must be submitted in the correct format in the signature script so it matches the hash in the previous output's pubkey script.

For this reason, Bitcoin Core uses several different identifier bytes to help programs identify how keys should be used:

1) Private keys meant to be used with compressed public keys have 0x01 appended to them before being Base-58 encoded. (See the private key encoding section above.)

2) Uncompressed public keys start with 0x04; compressed public keys begin with 0x03 or 0x02 depending on whether they're greater or less than the midpoint of the curve. These prefix bytes are all used in official secp256k1 documentation.

Excerpt from:
en.bitcoin.it/wiki/Protocol_documentation#Signatures

Public keys (in scripts) are given as 04 [x] [y] where x and y are 32 byte big-endian integers representing the coordinates of a point on the curve or in compressed form given as [sign] [x] where [sign] is 0x02 if y is even and 0x03 if y is odd.

So, the public data in this case is:
public key:
- type: 02
- X: a5 34 d6 52 73 f8 52 0e 1e 84 1c cb b7 82 b7 1e 06 b4 11 7a 90 bb 92 c6 55 f8 13 1c f6 ae 22 61


Key point:
- "The hashed form of an uncompressed key is different than the hashed form of a compressed key, so the same key works with two different P2PKH addresses. This also means that the key must be submitted in the correct format in the signature script so it matches the hash in the previous output's pubkey script."


Hm. I think that this means that the compressed public key has a corresponding bitcoin address that uses the hash of the compressed public key.


So: The scriptPubKey in tr_s1 probably stores the hash of the compressed form of the public key.


Edit script_processor1.py:
- Change this comment:
# - The first byte of the public key, 04, is not part of the public key itself. I don't know what it's meant to indicate.
to:
# - The first byte of the public key indicates the type of public key. 0x04 == uncompressed form (32-byte X coordinate, 32-byte Y coordinate on the elliptic curve). 0x02 == compressed form (32-byte X, Y is even). 0x03 == compressed form (32-byte X, Y is odd). Source: http://en.bitcoin.it/wiki/Protocol_documentation#Signatures
- Change this line:
# public key, with 04 prefix.
to:
# public key, with 1-byte type prefix in [0x04, 0x02, 0x03].
- Change these two lines:
# confirm that first byte (prefix) is 0x04.
assert(public_key_data[0] == "04")
to:
# confirm that first byte (prefix) is in list [0x04, 0x02, 0x03].
assert(public_key_data[0] in ["04", "02", "03"])


Run it again.






Note: The signature data in scriptSig of tr_s2 is:




Rename check_signature.py to check_signature1.py.

Write check_hash_and_signature1.py, which should:
- hash the public key data from tr_s1 (use code from op_hash160.py)
- confirm that the resulting hash matches the hash in the scriptPubKey in tr_s1.
- parse tr_s2 and generate the transaction-in-signable-form (copy the Transaction class and accompanying functions from parser2.py and add a method for building the transaction-in-signable-form).
- hash the transaction-in-signable-form (double sha256)
- tackle the problem of getting an ECDSA VerifyingKey object from just the X coordinate and the Y sign.


Then, for the moment, check the validity of the signature using check_signature1.py.













Aha. Experimental confirmation that if the public key is supplied in compressed form within the scriptSig of a new transaction, then the compressed form (not the uncompressed form) should be hashed for comparison to the public key hash in the scriptPubKey of the relevant previous transaction.


[some development occurs here]


I'm currently working on this:
- tackle the problem of getting an ECDSA VerifyingKey object from just the X coordinate and the Y sign.


I've read through the ecdsa library. I can't find a function for calculating the Y coordinate from a known X coordinate.

I note that:
- the ecdsa library imports its sha1 hash function from hashlib (which, I think, is a wrapper for openssl). Also sha256, sha512. However, it looks like it's possible to provide an already-calculated hash to a signing function.
- in ecdsa.py, I find: "It is absolutely vital that random_k be an unpredictable number in the range [1, self.public_key.point.order()-1]. If an attacker can guess random_k, he can compute our private key from a single signature. Also, if an attacker knows a few high-order bits (or a few low-order bits) of random_k, he can compute our private key from many signatures. The generation of nonces with adequate cryptographic strength is very difficult and far beyond the scope of this comment."
-- random_k is an argument to class Private_key, method sign( self, hash, random_k ).
-- Summary: A different random number is needed for every signature. If an insufficiently random number is used, an attacker can derive the private key from a sufficient number of signatures.
- The code claims that it was written in 2005 and 2006 by Peter Pearson. Some changes made in 2008 and 2009.


From an earlier excerpt: "a point on the elliptic curve used by Bitcoin, y^2 = x^3 + 7"

So, to get Y from X, calculate y = sqrt(x^3 + 7).

Need to convert 32-byte X into an integer. Then convert resulting integer Y into 32-byte string.

Because y is calculated from a square root, there will be two y values for every x value. One positive, one negative.

This indicates that this source
en.bitcoin.it/wiki/Protocol_documentation#Signatures
incorrectly stated that the difference between the two y values is that one is odd and the other is even.

Here is X:


By using

I find that X_decimal is:
74724975260254336635725088600963580058846919575436399405146825925206718947937

By using

I find that Y_decimal is:
20426721601886702285677856159981430109269012723278278952324010893280738091637119207319161997770778320257157001379840
- Note: To display full number of Y (i.e. not in scientific notation), use:


Hm.


Python code excerpt:



This produces a result of 48 (bytes), but it should be 32.


Google "bitcoin uncompress public key".


First result:
bitcoin.stackexchange.com/questions/28398/how-can-i-get-the-uncompressed-public-key-from-the-compressed-public-key-in-open

A comment there by Tim S leads to:
bitcointalk.org/index.php?topic=644919.msg7205689#msg7205689
Author: TimS
Date: June 09, 2014, 12:53:21 AM

Excerpt:

Re: How to get uncompressed public key from compressed one ?

From http://en.wikipedia.org/wiki/Quadratic_residue and http://mersennewiki.org/index.php/Modular_Square_Root, if

r^2 = a mod m where m = 3 mod 4 (as secp256k1's p does)
then
r = +-a^((m+1)/4) mod m

So:

y^2 mod p = (x^3 + 7) mod p
y mod p = +-(x^3 + 7)^((p+1)/4) mod p

So calculate (x^3 + 7)^((p+1)/4) mod p, and if the parity of the first answer you get is wrong, then take the negative of that answer (since we're working modulo an odd number, taking the negative will flip the even/odd parity).

Just for fun, here's some Python code that'll do the calculation in the blink of an eye, preset to work on the public key of (the random) private key 55255657523dd1c65a77d3cb53fcd050bf7fc2c11bb0bb6edabdbd41ea51f641

Code:

def pow_mod(x, y, z):

"Calculate (x ** y) % z efficiently."

number = 1

while y:

if y & 1:

number = number * x % z

y >>= 1

x = x * x % z

return number

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

compressed_key = '0314fc03b8df87cd7b872996810db8458d61da8448e531569c8517b469a119d267'

y_parity = int(compressed_key[:2]) - 2

x = int(compressed_key[2:], 16)

a = (pow_mod(x, 3, p) + 7) % p

y = pow_mod(a, (p+1)//4, p)

if y % 2 != y_parity:

y = -y % p

uncompressed_key = '04{:x}{:x}'.format(x, y)

print(uncompressed_key)

Ok. The calculation has to be done using modular arithmetic. I don't fully understand the mathematics code, but I'll see if it works.










This line:

suggests that the correct way to distinguish between the two possible Y results really is "even" vs "odd".



Hm. I get a 65-byte result for the uncompressed public key:
04a534d65273f8520e1e841ccbb782b71e06b4117a90bb92c655f8131cf6ae226150b222cdcd631b144cfe6ff8df86a5c02e416eb6d10ee9168bda056fc4f855ee

A "04" prefix and two 32-byte values for X and Y.

X: a534d65273f8520e1e841ccbb782b71e06b4117a90bb92c655f8131cf6ae2261
Y: 50b222cdcd631b144cfe6ff8df86a5c02e416eb6d10ee9168bda056fc4f855ee

Now let's see if that actually works.


I can use parts of the ecdsa library to check the validity of a point.









Ok. It's a valid point.




check_hash_and_signature1.py can currently:
- confirm that the public key in a new transaction hashes to the hash stored in the scriptPubKey of the relevant previous transaction.
- get the signable form of a transaction.
- apply sha256 twice to the transaction-in-signable-form.


Let's store a checkpoint:











Inputs for check_signature1.py:

All of these come from tr_s2.


Remove the last byte (hash_type == 01) from the signature and add spaces to the other data items.

Inputs for check_signature1.py:





Rewrite check_signature1.py a bit.













Excellent.


Digital signature for tr_s2 found to be valid.

Earlier the public key for tr_s2 was found to be valid (its hash was the expected value).


Next: Move the functionality of uncompress.py, check_validity_of_point.py, and check_signature1.py into check_hash_and_signature1.py.



Hm. Actually, I think I'll keep everything as separate files for the moment.


Actually, I should split the public key hash check and the double sha256 calculation into separate files. I'll verify the transaction again and, as I do so, I'll perform the split and record the sequence of operations in the verification process.







### START VERIFICATION PROCESS

selected raw transaction, tr_s2:



it's stored in file tr_s2.txt.


use parser2.py, targeted at tr_s2.txt, to parse the raw transaction format.




Note that the previous_output_index is "1".


From the single input, get the value of "[derived property] previous_output_hash (no spaces, big-endian)":
36b325b30a8bdf60d835e65cbb97dd172cb2910d30c4060e7502b6a32cad8c4f


Construct a query with which to retrieve this previous transaction in raw form:

http://blockchain.info/tx/36b325b30a8bdf60d835e65cbb97dd172cb2910d30c4060e7502b6a32cad8c4f?format=hex

Save the resulting raw transaction in the file tr_s1.txt (it's the same as before - no change).


use parser2.py, targeted at tr_s1.txt, to parse the raw transaction format.






Get the tr_s2_scriptSig:


From the second output (output index 1) of tr_s1, get the scriptPubKey:



tr_s2_scriptSig satisfies the cryptographic condition set by tr_s1_output1_scriptPubKey, which allows tr_s2 to use tr_s1_output1 as an input.


Take this scriptSig and scriptPubKey and use them as inputs to script_processor1.py.





script_processor1.py didn't raise any errors, which means that the combined script is in the expected format (the standard P2PKH format).


Now, write check_hash1.py, drawing material from check_hash_and_signature1.py.
check_hash1.py will use these results from script_processor1.py as input:










tr_s2_public_key hashes to tr_s1_public_key_hash.


Write check_signature2.py, which will import the Transaction class from parser2.py.

Copy the new material in the Transaction class from check_hash_and_signature1.py to the Transaction class in parser2.py.
These are:
- the function get_var_int_prefix (place this in parser2.py).
- the methods get_signable_hex_bytes and get_hex_bytes.


check_signature2.py inputs:



Don't remove the "01" final hash_type byte from signature_data manually. I'll do this in check_signature2.py.


Add a check in check_signature2.py that stops the script if the public key is in compressed form and instructs the user to:
- uncompress the public key
- run the script again

Done.

In this case, the public key starts with "02", so check_signature reports this as a problem. Use uncompress.py to produce an uncompressed public key and use check_validity_of_point.py to confirm that the uncompressed public key is a valid point on the secp256k1 curve.

Adjust uncompress.py so that it prints the X and Y values that can be used as inputs for check_validity_of_point.py.














Use the uncompressed public key produced by uncompress.py as new input into check_signature2.py.


First, run check_signature2.py with the original compressed public key data:




Error is reported as expected.


Now, use the uncompressed public key.






Cool. Validity of signature confirmed.



Here's the final code for check_signature2.py.






And the final code for parser2.py (with the new material from check_hash_and_signature1.py):











### END VERIFICATION PROCESS






As a sanity check, I'll do this again with Ken Shirriff's transaction, tr_ken2.


Earlier, I found that tr_ken1 can be accessed at:
blockchain.info/tx/81b4c832d70cb56ff957589752eb4125a4cab78a25a8fc52d6a09e5bd4404d48

From Ken Shirriff's article, I see that tr_ken1 transferred bitcoin to this address generated by Ken Shirriff: 1MMMMSUb1piy2ufrSguNUdFmAcvqrQF8M5

The transaction tr_ken2 transferred bitcoin from
1MMMMSUb1piy2ufrSguNUdFmAcvqrQF8M5
to
1KKKK6N21XKo48zWKuQKXdvSsCf95ibHFa.

At
blockchain.info/tx/81b4c832d70cb56ff957589752eb4125a4cab78a25a8fc52d6a09e5bd4404d48
click the output address
1MMMMSUb1piy2ufrSguNUdFmAcvqrQF8M5,
which links to:
blockchain.info/address/1MMMMSUb1piy2ufrSguNUdFmAcvqrQF8M5

Two transactions are listed for this address.

The top transaction has the output address
1KKKK6N21XKo48zWKuQKXdvSsCf95ibHFa
so it's tr_ken2.

tr_ken2's transaction hash is
3f285f083de7c0acabd9f106a43ec42687ab0bebe2e6f0d529db696794540fea
On the page, this transaction hash links to
blockchain.info/tx/3f285f083de7c0acabd9f106a43ec42687ab0bebe2e6f0d529db696794540fea

Append ?format=hex to this transaction hash link to get the link to the raw form of the transaction.
http://blockchain.info/tx/3f285f083de7c0acabd9f106a43ec42687ab0bebe2e6f0d529db696794540fea?format=hex

transaction tr_ken2 in raw form:



This is the input to the verification process.






### START VERIFICATION PROCESS


transaction tr_ken2 in raw form:




Save this raw transaction in tr_ken2.txt in the work directory (this is a new file).


Run parser2.py, targeted at tr_ken2.txt.






Note that the previous_output_index of the single input is "0".


From the single input, get the value of "[derived property] previous_output_hash (no spaces, big-endian)":
81b4c832d70cb56ff957589752eb4125a4cab78a25a8fc52d6a09e5bd4404d48


Construct a query with which to retrieve this previous transaction in raw form:

http://blockchain.info/tx/81b4c832d70cb56ff957589752eb4125a4cab78a25a8fc52d6a09e5bd4404d48?format=hex

Save the resulting raw transaction in the file tr_ken1.txt (it's the same as before - no change).


use parser2.py, targeted at tr_ken1.txt, to parse the raw transaction format.





Get the tr_ken2_scriptSig:



From the first output (output index 0) of tr_ken1, get the scriptPubKey:



tr_ken2_scriptSig satisfies the cryptographic condition set by tr_ken1_output0_scriptPubKey, which allows tr_ken2 to use tr_ken1_output0 as an input.



Take this scriptSig and scriptPubKey and use them as inputs to script_processor1.py.





script_processor1.py didn't raise any errors, which means that the combined script is in the expected format (the standard P2PKH format).


Run check_hash1.py, which uses these results from script_processor1.py as input:







tr_ken2_input_public_key hashes to tr_ken1_output0_public_key_hash.



Now run check_signature2.py, with these inputs:



The public key starts with "04", so for this transaction (tr_ken2) it will not be necessary to use uncompress.py and check_validity_of_point.py.





Validity of signature in tr_ken2 confirmed.


### END VERIFICATION PROCESS




Let's summarise the verification process as it currently stands.



### TRANSACTION VERIFICATION PROCESS (version 1)


Select a transaction to verify. It must have exactly one input. It can have multiple outputs. The input and the outputs must all be single-signature Pay-To-Public-Key-Hash (P2PKH). The public key in the input scriptSig may be compressed.

Get the raw form of the selected transaction. Save this in a file in the work directory.

Run parser2.py, targeted at this file.
- In the single input, get these values:
-- [derived property] previous_output_hash (no spaces, big-endian)
-- previous_output_index
-- scriptSig

Use the "previous_output_hash (no spaces, big-endian)" value to look up the transaction that supplied an output for use as the input to the selected transaction. Get the raw form of this previous transaction. Save it in a file in the work directory.

Run parser2.py, targeted at this file.
Use the previous_output_index found earlier to select the appropriate output in the result.
- In this output, get this value:
-- scriptPubKey

The selected transaction's scriptSig should satisfy the cryptographic condition set by the previous transaction's scriptPubKey.

Use the scriptPubKey and the scriptSig as inputs to script_processor1.py.
From the output, get these values:
- signature_data
- public_key_data
- public_key_hash

Use public_key_data and public_key_hash as inputs to check_hash1.py. This script will check that the public_key_data in the selected transaction's scriptSig hashes to the public_key_hash in the previous transaction's scriptPubKey.

Use these items produced by script_processor1.py:
- signature_data
- public_key_data
this item produced by parser2.py when parser2.py was targeting the previous transaction:
- scriptPubKey
and the file containing the selected transaction
as inputs to check_signature2.py

If the public_key_data is compressed, uncompress it using uncompress.py and check_validity_of_point.py, then use the uncompressed form as input to check_signature2.py.

check_signature2.py will use the public key to check the validity of the signature of the selected transaction in signable form. The public key and the signature are stored in the selected transaction's scriptSig. The scriptPubKey of the previous transaction is part of the transaction-in-signable-form.

If both check_hash1.py and check_signature2.py return successful results, then the selected transaction has been verified.


### END TRANSACTION VERIFICATION PROCESS (version 1)













Changes from the original text:

- I have not always preserved the format of any excerpts from webpages on other sites (e.g. not preserving the original bold/italic styles, changing the list structures, not preserving hyperlinks).

- I have not always preserved the format of any computer output (e.g. from running bash commands). Examples: Setting input lines in bold text, adding/removing newlines in order to make a sequence of commands easier to read, using hyphens for lists and sublists instead of indentation, breaking wide tables into consecutive sections.