Create and sign a standard raw Bitcoin transaction.


This will involve:
- Creating a standard raw Bitcoin transaction.
- Signing the transaction using ECDSA cryptography.
- Broadcasting the transaction so that it can be mined, which will confirm its validity.


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 an input scriptSig is uncompressed.


Note: The form of the transaction that is actually signed differs slightly for each input address.







- Goal
- Contents
- Brief Summary
- Summary
- Recipe For Managing The Fee And Broadcast Of A Bitcoin Transaction
- Downloadable Digital Assets
- Recipes For Using Various Downloadable Assets
- Representative Sample Of Bash Commands Used
- Notes / Discoveries
- Further Work
- Project Log










I generated two standard* addresses, a "source address" and a "target address". I transferred some bitcoin from my LocalBitcoins account to the source address. I constructed and signed a transaction (tx1) that moved the available bitcoin from the source address to the target address. I studied various aspects of ECDSA signatures, particularly S values, in order to accomplish this. The transaction was broadcast and added to the Bitcoin blockchain.

My then-current LocalBitcoins receiving address was a Pay-To-Script-Hash (P2SH) address. I constructed and signed a second transaction (tx2) that moved the available bitcoin from the target address to my LocalBitcoins account. I studied P2SH addresses in order to accomplish this. The transaction was broadcast and added to the Bitcoin blockchain.

Total bitcoin spent during this project: 0.00020450

Please see the Summary section for further information.

* I define a standard address to be a Pay-To-Public-Key-Hash (P2PKH) address where the public key was not compressed before it was hashed.














Original plan of action for this project:
- Generate an address and move some bitcoin into it (the "source address").
- Obtain a second address (the "target address").
- Find out the recent average mining fee.
- Create a raw Bitcoin transaction that specifies the transfer of the bitcoin from the source address to the target address. Be careful to include a mining fee.
- Sign the transaction using the private key of the source address and ECDSA cryptography. Before signing, the transaction must be altered slightly to get the transaction-in-signable-form.
- Embed the transaction signature into the transaction.
- Broadcast the transaction to the Bitcoin network.
- Confirm that the transaction has been mined (included in a block in the Bitcoin blockchain). This verifies that the transaction was valid (i.e. in the correct format, with a mathematically valid signature).



What I actually ended up doing during the project:
- Generated an address (the "source address"). This was a standard address: uncompressed Pay-To-Public-Key-Hash (P2PKH).
- Confirmed that the source address had not already appeared on the Bitcoin blockchain.
- Decided not to use my then-current LocalBitcoins receiving address as the target address because it started with a '3' and was therefore a Pay-To-Script-Hash (P2SH) address, not a standard P2PKH address. Generated a second address (the "target address"). This was a standard address: uncompressed Pay-To-Public-Key-Hash (P2PKH).
- Confirmed that the target address had not already appeared on the Bitcoin blockchain.
- Decided to later create and sign a second transaction that would move the available bitcoin from the target address to my then-current LocalBitcoins receiving address. This would mean that during this project, the bitcoin would complete a round-trip back to my LocalBitcoins account.
- Used a web service to look up estimated mining delays for different transaction fee ranges. Fees were measured in satoshis / byte.
- Transferred some bitcoin from my LocalBitcoins account to the source address (enough to cover two high-end Bitcoin network transaction fees and the LocalBitcoins deposit fee). This was transaction 0 (tx0).
- Used a web service to look up information about this transaction for use in a second transaction.
- Assembled a raw transaction that moved the available bitcoin from the source address to the target address. Used a small fee (approximately 1 satoshi / byte). This was transaction 1 (tx1).
- Learned how to use the Python ECDSA library to sign the transaction.
- Tried to use a web service to broadcast the transaction. The transaction was rejected because it had a high S value in its signature.
- Studied various sources in order to learn about high and low S values in transaction signatures.
- Studied and thought about Transaction Malleability (which is the reason for the Bitcoin network having converged on only mining transactions with low S values in their signatures).
- Learned how to convert a high S value into a low S value, which means that a high-S signature can be converted into a low-S signature.
- Studied the ECDSA signing process and signature verification process. Only understood some of it. Did not learn why the low-S-to-high-S conversion process works or why a signature with a low S value is mathematically equivalent to a signature with a high S value. Learned where and how a random integer is used in the signature process, and its value domain.
- Dug down into the Python ECDSA library and worked out how, when signing a transaction, to:
a) Supply my own random integer K value to the signing process.
b) See the values of S and R in the signature before they are encoded in DER format.
c) Check if the S value is high, and, if it is, replace it with the corresponding low S value.
- Signed tx1 again. Signature contained a low S value.
- Used a web service to broadcast the transaction. It was mined within a few minutes. Goal attained: Test a transaction that sends bitcoin from one standard address to another.
- Began to work on assembling a second transaction that would move the available bitcoin from the target address to my then-current LocalBitcoins receiving address. This was transaction 2 (tx2).
- Studied P2SH addresses in order to discover how to send a transaction output to a P2SH address (in this case, my then-current LocalBitcoins receiving address). Learned that P2SH were a soft fork that specified a new convention for how to use the components of a P2PKH address. Learned that the most common use for P2SH is to implement multi-signature addresses. Decided that P2SH addresses replaced the cryptographic guarantee of P2PKH addresses with a promise made by the Bitcoin miners to observe a different cryptographic guarantee. Concluded that breaking the guarantee of P2PKH addresses requires a hard fork, whereas breaking the guarantee of P2SH address only requires another soft fork, and that therefore P2SH addresses are not as secure as P2PKH addresses.
- Learned the P2SH address format and how to reverse it to obtain the hash value inside it. Learned how to construct a P2SH transaction output (scriptPubKey) so that I could send bitcoin to a P2SH address.
- Confirmed that all P2SH addresses start with '3'.
- Assembled tx2. Used a small fee (approximately 1 satoshi / byte).
- Signed tx2.
- Tried to use a web service to broadcast the transaction. The transaction was rejected because its signature was invalid.
- Examined my work and found that I had not included values for "script_length: (var_int)" for both {scriptPubKey of unspent output from previous transaction} and scriptPubKey in tx2-in-signable-form.
- Signed tx2 again.
- Used a web service to broadcast the transaction. It was mined within approximately 5 minutes. LocalBitcoins processed the transaction, deducted its deposit fee, and deposited the remaining amount in my account.
- Confirmed that a transaction id (txid) is constructed by hashing a signed transaction with SHA256 twice.
- Discovered that SHA256 produces a big-endian result and that any txids used within a transaction (to identify previous transactions that supply unspent outputs for use as inputs in this new transaction) are encoded in big-endian format. I had previously thought that they were in little-endian format in the raw transaction data. I also learned that the original Bitcoin client's RPC calls used little-endian format for txids, and that as a result web services and wallet programs generally use txids in little-endian format. I had previously thought that web services were using big-endian format for txids.
- Learned that if endianness is important within an algorithm (e.g. SHA256), then implementations for that algorithm must be written separately for CPU architectures with different endiannesses.
- Wrote a proposal for a unique transaction identifier. See Notes / Discoveries section: Proposal for a unique transaction identifier (utxid).
- Thought carefully about how to rebroadcast a new version of a transaction if the previous version was not mined. See this section: Recipe For Managing The Fee And Broadcast Of A Bitcoin Transaction.
- Wrote an explanation of endianness. See Notes / Discoveries section: Endianness.



Notes:

- When constructing transactions, I used block explorers and various calculations to obtain raw data for use in a new transaction. I did not process and read previous raw transactions, but it would be preferable to do so in a production process.

- The Notes / Discoveries section contains the following parts, which cover the items in this summary in more detail:
-- Transaction web services
-- Standard transaction - raw format
-- Standard transaction-in-signable-form - raw format
-- Gathering data in order to construct a new transaction
-- Addresses generated in this project
-- Algorithm for deriving the public key hash from a standard Bitcoin address
-- Algorithm for signing a standard transaction
-- Transaction Malleability
-- BIP 62 - Dealing with malleability
-- High and low S values in Bitcoin transaction signatures
-- Further information concerning ECDSA signatures and S values
-- P2SH multi-signature addresses - security
-- P2SH multi-signature addresses - results from this project
-- Transactions constructed and signed in this project
-- Transaction identifier (txid) construction and endianness
-- Endianness
-- Proposal for a unique transaction identifier (utxid)



Financial Information:
- I calculated an amount of bitcoin that was large enough to ensure that I would be able to pay two Bitcoin transaction fees + the LocalBitcoins deposit fee, with extra so as to have room to manoeuver. This was 0.002 bitcoin, or about $12 at then-current prices.
- I transferred 0.002 bitcoin in tx0.
- LocalBitcoins charged a transaction fee of 0.00005 bitcoin for tx0. This was subtracted from my LocalBitcoins wallet balance, not from the amount that was actually sent.
- For tx1, I used a transaction fee of 225 satoshis (0.00000225 bitcoin).
- For tx2, I used a transaction fee of 225 satoshis (0.00000225 bitcoin).
- When it accepted and processed tx2, LocalBitcoins charged a deposit fee of 0.00015000 bitcoin.
- Total bitcoin spent: LocalBitcoins transaction fee for tx0 + tx1 transaction fee + tx2 transaction fee + LocalBitcoins deposit fee for tx2 = 0.00005000 + 0.00000225 + 0.00000225 + 0.00015000 = 0.00020450 bitcoin.


My new working definition of a standard transaction:
- It has at least one input and at least one output.
- All input and output addresses are Pay-To-Public-Key-Hash (P2PKH).
- All input scriptSigs contain uncompressed public keys.














Objectives:
- Fine control of the transaction fee.
- Ability to rebroadcast a new transaction with a higher fee if the previous transaction is not mined within a reasonable time period. This new transaction, if mined, should invalidate the previous transaction.

Note: This recipe is derived from work in this project but has not been tested.

1) Gather the required data for a new transaction (this process is not specified in this recipe). Include at least one "change address" output. Inputs should be added as necessary to achieve the desired output values. The sum of the inputs may be greater than the sum of the desired output values, i.e. some bitcoin may be left over. Send this left-over bitcoin to the change address output. Include an additional input that is specifically for paying the as-yet-unknown transaction fee. Send the bitcoin from this input to the change address output.

2) Construct the transaction, without including signatures (this process is not specified in this recipe).

3) Calculate the byte length of the result of step (2). Let this result be A.

4) Let the estimated byte length of the final transaction be N. Let the approximate byte length of a single input signature be B. Let the number of inputs be C. Calculate N = A + B x C.

5) Using a fee estimation service, look at fee ranges (in satoshis / byte) and the estimated delays for each range. Choose an acceptable delay. Let the corresponding fee (in satoshis / byte) be D. Let the final transaction fee (in satoshis) be E. Calculate E = D x N.

6) Copy the result of step (2). Subtract E from the value in the change address output. The transaction fee is stored implicitly in the transaction as the difference between the sum of the input values and the sum of the output values.

7) Sign the transaction (this process is not specified in this recipe). Insert the input signatures into the transaction.

8) Let the final byte length of the transaction be M. Calculate M by finding the byte length of the result of step (7).

9) Let the final transaction fee (in satoshis / byte) be F. Calculate F = E / M. Confirm that F is within the original desired fee range.

10) Record the time, date, and blockheight. Broadcast the transaction to the Bitcoin network or upload the transaction to a service that can do this for you.

11) A node will store unconfirmed transactions in its memory pools for a particular time period. If the transaction is not mined (confirmed) within this period, the node will delete it from its memory pool. This period will vary depending on the node. Some reading indicates that the default period is 72 hours (three days). After broadcasting the transaction, wait three days + a small delay. If the transaction is mined during this period, stop here. Otherwise, continue to step (12).

12) Using a fee estimation service, look at fee ranges (in satoshis / byte) and the estimated delays for each range. Choose a higher fee range than was used previously.

13) Repeat steps (5)-(12) until the transaction is mined.


Note: If a transaction disappears from the network (i.e. the memory pools of all public nodes), this doesn't mean that it has vanished permanently. Anyone who stored it can rebroadcast it later - it will still be valid. In order to make it invalid, create a new transaction that uses at least one of the same inputs.

Note: An input in a transaction is an as-yet-unspent output of a previous transaction. Each unspent output can only ever be spent once. If a transaction is broadcast that uses at least one input that has already been spent, this transaction is invalid and will not be mined.


















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



The following assets were developed during this project and were run using Python 2.7.13 on Aineko.


Description: Change the endianness of a hex string.
change_hex_endianness.py

Description: Derive the public key hash from a standard Bitcoin address. A standard address begins with a '1' and is an uncompressed Pay-To-Public-Key-Hash (P2PKH) address.
get_public_key_hash_from_bitcoin_address.py

Description: Derive the script hash from a P2SH Bitcoin address (which begins with '3').
get_script_hash_from_p2sh_address.py

Description: This script uses the Python ECDSA library to sign a transaction-in-signable-form.
sign_transaction_in_signable_form.py



The following assets are associated with the article Reading and verifying a standard raw bitcoin transaction. Please read the article for information and advice on these assets.

Description: An implementation of RIPEMD-160, written by Björn Edström.
bjorn_edstrom_ripemd160.py [paywalled]

Description: A Python implementation of ECDSA cryptography, written by Peter Pearson.
ecdsa-0.10.tar.gz [paywalled]

Description: A Python implementation of SHA256.
pypy_sha256.py [paywalled]



The following assets are associated with the article Generating a standard Bitcoin address. Please read the article for information and advice on these assets.

Description: This script generates a standard Bitcoin address from a private key in raw byte form (e.g. "hello_world").
generate_bitcoin_address.py [paywalled]

Description:
Title: Working Draft, American National Standard, X9.62-1998, Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)
Author: Accredited Standards Committee X9, American Bankers Association
Date: September 20, 1998
x9_62_draft_ecdsa.pdf [paywalled]











Recipe 1: change_hex_endianness.py

1) Set the variable to contain the hex value whose endianness you want to reverse.

2) Run the script.



3) You can also import the function into other scripts or while working in the Python REPL.

Example:




Recipe 2: get_public_key_hash_from_bitcoin_address.py

1) Set the variable to contain the standard Bitcoin address whose public key hash you wish to extract.

2) Run the script.





Recipe 3: get_script_hash_from_p2sh_address.py

1) Set the variable to contain the P2SH Bitcoin address whose script hash you wish to extract.

2) Run the script.



Future: Check the validity of the checksum in the P2SH address, rather than just removing it.



Recipe 4: sign_transaction_in_signable_form.py

Note: For a description of the signable form of a transaction, see the "Standard transaction-in-signable-form - raw format" part of the Notes / Discoveries section.

1) Set the variable to contain the hex value of the particular transaction-in-signable-form that you wish to sign and thereby create a signature for one input to the transaction. For each input, the transaction-in-signable-form will be slightly different.

2) Set the variable to contain the hex value of the private key for this particular input.

3) Set the variable to contain a random ASCII byte string. To preserve the security of the private key, the value of k must be different for each published signature. Alternatively, comment out the line and add a line that sets the variable to be a random hex value. The domain of k is the inclusive interval [1, n-1], where n is the order of the base point G of the elliptic curve secp256k1 and is equal to FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141.

4) This script uses the Python ECDSA library. Download ecdsa-0.10.tar.gz from the Downloadable Assets section. Place it into the "work directory" that contains sign_transaction_in_signable_form.py. Unpack the zipped tape archive file ecdsa-0.10.tar.gz. The following command can be used to do this:


5) The unpacking in step (4) should produce a new directory named ecdsa-0.10. ecdsa-0.10 should contain a directory named ecdsa. Copy the ecdsa directory to the work directory. The ecdsa library can now be imported by the sign_transaction_in_signable_form.py script.

Future: Investigate how the sign_transaction_in_signable_form.py script could import the ecdsa library directly, so that the copy operation above is not necessary.

6) This script uses the PyPy Python implementation of SHA256. Download pypy_sha256.py from the Downloadable Assets section. Place it into the work directory.

7) Run the script sign_transaction_in_signable_form.py.



Note: This script checks if the S value in the signature is high, and, if it is, replaces it with the corresponding low S value.
















Note: The output is not always included for every command.

























Parts:
- Transaction web services
- Standard transaction - raw format
- Standard transaction-in-signable-form - raw format
- Gathering data in order to construct a new transaction
- Addresses generated in this project
- Algorithm for deriving the public key hash from a standard Bitcoin address
- Algorithm for signing a standard transaction
- Transaction Malleability
- BIP 62 - Dealing with malleability
- High and low S values in Bitcoin transaction signatures
- Further information concerning ECDSA signatures and S values
- P2SH multi-signature addresses - security
- P2SH multi-signature addresses - results from this project
- Transactions constructed and signed in this project
- Transaction identifier (txid) construction and endianness
- Endianness
- Proposal for a unique transaction identifier (utxid)





Transaction web services



Note: It is convenient to measure transaction fees in satoshis / byte.

I used
bitcoinfees.earn.com
to choose fees for my transactions. It displays the estimated delay (in blocks and in minutes) for ranges of fee values (in satoshis / byte).
[Hearsay] The site's predictions are based on blockchain data of the last 3 hours, as well as the current pool of unconfirmed transactions (mempool).

I was able to use
live.blockcypher.com/btc/decodetx
to parse a signed transaction.

I was able to use
live.blockcypher.com/btc/pushtx
to upload a signed transaction for broadcasting to the network.

I was able to use
blockchain.info/decode-tx
to parse a signed transaction, although it did not provide as much detail as did
live.blockcypher.com/btc/decodetx

At some point during the project, I found that
blockchain.info/decode-tx
now led to:
www.blockchain.com/en/btc/decode-tx
which, when I tried to submit a transaction for parsing, simply reloaded the page, wiping the transaction hex data.

I was able to use
blockchain.info/pushtx
to find errors with a signed transaction, but I switched to using the blockcypher pushtx service and never used this one to successfully broadcast a transaction.





Standard transaction - raw format



This is my current working definition of the raw format of a standard Bitcoin transaction.


Standard transaction:


scriptSig:


scriptPubKey:



Notes:

- Previously, I had thought that previous_output_hash was little-endian, and that block explorers used a big-endian form of previous_output_hash.

- [Hearsay] The original client uses big-endian hashes in the raw data, but little-endian for all values in RPC calls. Therefore, txids are big-endian in the raw transaction, but little-endian when used in an RPC call to look up a transaction. For this reason, block explorers mostly use and display txids in little-endian format.
-- So far, I am persuaded by my results that txids are big-endian in the raw transaction and little-endian in block explorers.

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

- txid == "transaction id".

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

- The transaction fee is stored implicitly in a transaction as the difference between the sum of the input values and the sum of the output values.

- My new working definition of a standard transaction:
-- It has at least one input and at least one output.
-- All input and output addresses are Pay-To-Public-Key-Hash (P2PKH).
-- All input scriptSigs contain uncompressed public keys.

- My working definition of a standard address is: Pay-To-Public-Key-Hash (P2PKH) where the public key was not compressed before being hashed.

- My working definition of a standard input is: an unspent output stored in a standard address.

- The inputs for a new transaction are a set of as-yet-unspent outputs from previous transactions. An input transfers value out of a previous address and an output transfers 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.

- scriptPubKey is the "destination" of the bitcoin in a transaction and contains the hash of a public key. The corresponding private key is required in order to spend this bitcoin later.

- The previous_output_hash is:
-- the hash of the previous transaction that:
--- contains the unspent output that:
---- will be used as an input in this new transaction

- The previous_output_index is the implicit index (starting at 0) of the unspent output in the list of unspent outputs in the previous block.

- The domain of the opcode PUSHDATA is 1-75 in decimal (0x01-0x4b in hex).





Standard transaction-in-signable-form - raw format



This is my current working definition of the raw format of a standard Bitcoin transaction-in-signable-form.




scriptPubKey (standard form):


Note: In the {scriptPubKey of relevant unspent output from previous transaction}, the unspent output is associated with a particular address, the private key of which is to be used to sign this particular transaction-in-signable-form in order to create a single scriptSig.

Note: The hash type (SIGHASH_ALL) is 1. As 1 byte, this is 0x01. As 4 bytes (little-endian), this is 0x01 00 00 00. The 4-byte version is appended to the transaction-in-signable-form before signing. The 1-byte version is appended to the signature_data after signing.





Gathering data in order to construct a new transaction



Transaction data that should be originally chosen when the transaction is being planned:

Notes:
- Include at least one "change address" output. Inputs should be added as necessary to achieve the desired output values. The sum of the inputs may be greater than the sum of the desired output values, i.e. some bitcoin may be left over. Send this left-over bitcoin to the change address output. Include an additional input that is specifically for paying the as-yet-unknown transaction fee. Send the bitcoin from this input to the change address output.


Transaction data that can be known immediately:

Notes:
- I think that the version is always hardcoded as '1' for the main Bitcoin network. In 4 little-endian hex bytes, this is 01 00 00 00.
- [Hearsay] Sequence can always be set to 0xffffffff. It is a nonfunctional legacy feature that was designed to allow multiple signers to agree to update a transaction.
- [Hearsay] Block lock time can always be set to 0x00000000. It was designed to ask miners not to mine a transaction until a specified block height is reached. A block lock time of 0x00000000 specifies that the transaction can be mined at any block height after 0.
- The 4-byte hash_type is appended to the transaction before signing.
- The 1-byte hash_type is appended to the transaction signature.


Transaction data that can be derived from the destination addresses:

Notes:
- The destination addresses must be standard addresses (i.e. single-signature Pay-To-Public-Key-Hash (P2PKH)). For other destination addresses (e.g. P2SH multi-signature), the scriptPubKey format below will be different.

scriptPubKey:



Transaction data that can be acquired by analysing previous transactions on the blockchain:

Notes:
- "scriptPubKey of relevant unspent output from previous transaction" is used when signing a transaction to make a signature for a particular input. It can be derived from the input address. However, it should also be found within the relevant unspent output in a previous transaction, and then compared against the version derived from the input address as a sanity check.


Transaction data that must be calculated after all other data has been assembled:

scriptSig:

Notes:
- public_key_data in the scriptSig can be derived from the private key of the input address.
- signature_data in the scriptSig is the signature created by signing the entire transaction using the private key of one particular input address.






Addresses generated in this project



Sequence of actions:
- Have a LocalBitcoins account that holds some bitcoin.
- Generate an address (the "source address").
- Generate a second address (the "target address").
- Use LocalBitcoins system to transfer some bitcoin from the LocalBitcoins account to the source address.
- Construct and sign a transaction to move the available bitcoin from the source address to the target address. Upload this transaction to a web service for broadcast to the network.
- Construct and sign a transaction to move the available bitcoin from the target address to my then-current LocalBitcoins receiving address. Upload this transaction to a web service for broadcast to the network.



Source address:




Target address:




Source address:
1CTumCMjzBfccCJBTkHoPQmAwEqU9Uj2sQ

Target address:
12RbVkKwHcwHbMZmnSVAyR4g88ZChpQD6f

Then-current LocalBitcoins receiving address:
36CQfj2Yt54sZttJYTb5ywuS7YGEQLfzCE


Before using them, I confirmed that neither the source nor the target address had been used already on the Bitcoin blockchain.









Algorithm for deriving the public key hash from a standard Bitcoin address



1) Count the number of leading '1' characters in the address, then remove them.

2) Convert the result of step (1) from the Bitcoin base-58 encoding to a base-10 integer.

3) Convert the result of step (2) from a base-10 integer to a hex byte string.

4) The last four bytes in the result of step (3) are the checksum. Remove them.

5) Let the result of step (1) be N. Add N leading zero bytes to the result of step (4).

6) The first byte in the result of step (5) is the version byte. For the main Bitcoin network, the version byte is 0x00. Remove it.

7) The final result of step (6) should be the public key hash in hex bytes, i.e. RIPEMD-160(SHA256(public_key)). Confirm that it is 160 bits or 160 / 8 = 20 bytes long.


Steps 1-5 comprise the reverse Base58Check algorithm.


Algorithm for step (2):
- This is the Bitcoin base-58 symbol list, in order of value, starting from decimal 0 and ending at decimal 57:

- Here, a base-58 string is a standard Bitcoin address without any leading '1' characters.
- Let the length of the base-58 string be N. Let M = N - 1.
- Treat the base-58 string as an array of characters. Set the index i = 0 i.e. the first index in the array, starting from the left.
- Let the running total x = 0.
- Perform the following loop until all characters in the base-58 string have been processed:
-- Use the index i to select a character from the base-58 string.
-- Look up this character's decimal value in the base-58 symbol list.
-- Multiply this value by 58 ^ (M - i).
-- Add the result of this multiplication to x.
-- Increment i by 1.
- When the entire base-58 string has been processed, the running total x should now contain the decimal value of the base-58 string.

Note: As we proceed from left to right to the low end of the base-58 string, the power of 58 decreases, exactly the same as in a decimal number.
Example:
For 156, N = 3 and M = 2.
156 = 1*(10^2) + 5*(10^1) + 6*(10^0)


For an example implementation, see this asset in the Downloadable Assets section:
get_public_key_hash_from_bitcoin_address.py






Algorithm for signing a standard transaction



Perform the following steps for each input.

1) A transaction's inputs are "unspent outputs" of previous transactions. For this input, look up the previous transaction that supplies this unspent output. Extract the scriptPubKey of this output from the previous transaction. Let this scriptPubKey be "previous_scriptPubKey".

2) In order to use this input within a new transaction, you must have the private key that controls it. Retrieve the private key from storage. Retrieve the corresponding public key from storage. Alternatively, derive it from the private key.

3) Substitute the previous_scriptPubKey for the scriptSig of this input. Calculate the previous_scriptPubKey's length var_int and substitute it for the scriptSig's length var_int.

4) Remove the scriptSigs of other inputs. I haven't tested this myself yet. Some reading indicates that a single 0x00 byte is substituted for each length var_int of other scriptSigs (thus indicating that the scriptSig contains no data).

5) Append a four-byte, little-endian form of the hash_type to the entire transaction. For hash type 1, SIGHASH_ALL, this is 0x01 00 00 00. The transaction is now the transaction-in-signable-form. Note that the transaction-in-signable-form differs for each input.

6) Sign the transaction-in-signable-form with the private key.

7) Convert the signature into DER encoding.

8) Construct the scriptSig, using this new signature and the public key. Calculate and include the length var_ints for each. Calculate and include the length var_int of the entire scriptSig.

9) Append a one-byte version of the hash_type to the scriptSig signature data. For hash type 1, SIGHASH_ALL, this is 0x01.

10) Save the result of step (9) as the scriptSig for this input.

After all scriptSigs have been constructed, place them in the appropriate locations within the original transaction. The transaction has now been signed.






Transaction Malleability



Transaction Malleability: A third party can receive a broadcast transaction, alter it, and rebroadcast it. Any alteration to the signed section of the transaction can be mechanically detected (the transaction signature(s) will be invalid) and rejected. However, a signature itself, and the scriptSig that contains it, is not signed. Alterations to the signature and/or the scriptSig can be harder to detect and reject.


Examples of possible alterations to the signature or scriptSig:
- [Untested] Signatures may not be encoded in strict DER format.
- The S value in a signature can be changed from high to low or vice versa. In the ECDSA cryptosystem, a high S value is mathematically identical to the corresponding low S value.
- [Untested] Changing an opcode to a different opcode (or sequence of opcodes) that performs the same overall function.
- [Untested] Adding leading zero bytes to the X or Y value in the public key data in the scriptSig.
Each of these changes alters the transaction's byte sequence but not its validity.


Why does Transaction Malleability matter?
- Nodes store unmined transactions in their memory pools and transmit them to other nodes. This requires storage and processing. If an attacker can alter many transactions and rebroadcast them, and the altered versions cannot be easily detected and rejected, this imposes additional running costs on each node. If this attack is performed on a large enough scale, the speed of transmission of new transactions through the Bitcoin network may diminish considerably.
- The transaction identifier (txid) is created by hashing the transaction twice with the SHA256 algorithm. Altered versions of the transaction will have different txids. If an altered version of the transaction is mined, the desired transfer of bitcoin will still take place, but if the original sender and/or receiver are using the original txid to track the status of the transaction (whether manually or with software), they won't detect that the transaction has been successfully mined. In order to confirm the transfer, they will have to check the balances of the various addresses involved in the transaction. This can make tracking the status of transactions (for e.g. bookkeeping) more difficult and time-consuming.
- It is possible to create and broadcast a transaction that spends the outputs of another transaction that has not yet been mined. Transactions include the txid of each of their predecessors. If an altered version of the transaction is mined, any later transactions that tried to spend its outputs will now be invalid and will never be mined.






BIP 62 - Dealing with malleability



Note: BIP = Bitcoin Improvement Proposal


Source:
github.com/bitcoin/bips/blob/master/bip-0062.mediawiki
Author: Pieter Wuille

NOTICE: This document is a work in progress and is not complete, implemented, or otherwise suitable for deployment.

BIP: 62 Layer: Consensus (soft fork) Title: Dealing with malleability Author: Pieter Wuille <pieter.wuille@gmail.com> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0062 Status: Withdrawn Type: Standards Track Created: 2014-03-12 License: BSD-2-Clause

Table of Contents

- Abstract
- Copyright
- Motivation
- Specification
-- New rules
-- Block validity
-- References
--- Low S values in signatures
--- DER encoding
--- Push operators
--- Numbers
- Compatibility


Abstract

This document specifies proposed changes to the Bitcoin transaction validity rules in order to make malleability of transactions impossible (at least when the sender doesn't choose to avoid it).


Copyright

This BIP is licensed under the 2-clause BSD license.


Motivation

As of february 2014, Bitcoin transactions are malleable in multiple ways. This means a (valid) transaction can be modified in-flight, without invalidating it, but without access to the relevant private keys.

This is a problem for multiple reasons:

- The sender may not recognize his own transaction after being modified.
- The sender may create transactions that spend change created by the original transaction. In case the modified transaction gets mined, this becomes invalid.
- Modified transactions are effectively double-spends which can be created without malicious intent (of the sender), but can be used to make other attacks easier.

Several sources of malleability are known:

1) Non-DER encoded ECDSA signatures
Right now, the Bitcoin reference client uses OpenSSL to validate signatures. As OpenSSL accepts more than serializations that strictly adhere to the DER standard, this is a source of malleability. Since v0.8.0, non-DER signatures are no longer relayed already.

2) Non-push operations in scriptSig
Any sequence of script operations in scriptSig that results in the intended data pushes, but is not just a push of that data, results in an alternative transaction with the same validity.

3) Push operations in scriptSig of non-standard size type
The Bitcoin scripting language has several push operators (OP_0, single-byte pushes, data pushes of up to 75 bytes, OP_PUSHDATA1, OP_PUSHDATA2, OP_PUSHDATA4). As the later ones have the same result as the former ones, they result in additional possibilities.

4) Zero-padded number pushes:
In cases where scriptPubKey opcodes use inputs that are interpreted as numbers, they can be zero padded.

5) Inherent ECDSA signature malleability
ECDSA signatures themselves are already malleable: taking the negative of the number S inside (modulo the curve order) does not invalidate it.

6) Superfluous scriptSig operations
Adding extra data pushes at the start of scripts, which are not consumed by the corresponding scriptPubKey, is also a source of malleability.

7) Inputs ignored by scripts
If a scriptPubKey starts with an OP_DROP, for example, the last data push of the corresponding scriptSig will always be ignored.

8) Sighash flags based masking
Sighash flags can be used to ignore certain parts of a script when signing.

9) New signatures by the sender
The sender (or anyone with access to the relevant private keys) is always able to create new signatures that spend the same inputs to the same outputs.

The first six and part of the seventh can be fixed by extra consensus rules, but the last two can't. Not being able to fix #7 means that even with these new consensus rules, it will always be possible to create outputs whose spending transactions will all be malleable. However, when restricted to using a safe set of output scripts, extra consensus rules can make spending transactions optionally non-malleable (if the spender chooses to; as he can always bypass #8 and #9 himself).


Specification

New rules

Seven extra rules are introduced, to combat exactly the seven first sources of malleability listed above:

1) Canonically encoded ECDSA signatures
An ECDSA signature passed to OP_CHECKSIG, OP_CHECKSIGVERIFY, OP_CHECKMULTISIG or OP_CHECKMULTISIGVERIFY must be encoded using strict DER encoding. To provide a compact way to deliberately create an invalid signature for OP_CHECKSIG and OP_CHECKMULTISIG, an empty byte array (i.e., the result of OP_0) is also allowed. Doing a verification with a non-DER signature makes the entire script evaluate to False (not just the signature verification). See reference: DER encoding.

2) Non-push operations in scriptSig
Only data pushes are allowed in scriptSig. Evaluating any other operation makes the script evaluate to false. See reference: Push operators.

3) Push operations in scriptSig of non-standard size type
The smallest possible push operation must be used when possible. Pushing data using an operation that could be encoded in a shorter way makes the script evaluate to false. See reference: Push operators.

4) Zero-padded number pushes
Any time a script opcode consumes a stack value that is interpreted as a number, it must be encoded in its shortest possible form. 'Negative zero' is not allowed. See reference: Numbers.

5) Inherent ECDSA signature malleability
We require that the S value inside ECDSA signatures is at most the curve order divided by 2 (essentially restricting this value to its lower half range). See reference: Low S values in signatures.

6) Superfluous scriptSig operations
scriptPubKey evaluation will be required to result in a single non-zero value. If any extra data elements remain on the stack, the script evaluates to false.

7) Inputs ignored by scripts
The (unnecessary) extra stack element consumed by OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY must be the empty byte array (the result of OP_0). Anything else makes the script evaluate to false.


Block validity

To introduce these new rules in the network, we add both v3 blocks and v3 transactions. v2 is skipped for transactions to keep the version numbers between transaction and block rules in sync. v2 transactions are treated identically to v1 transactions. The same mechanism as in BIP 0034 is used to introduce v3 blocks. When 75% of the past 1000 blocks are v3, a new consensus rule is activated:

- All transactions in v3 blocks are required to follow rules #1-#2.
- v3 (and higher) transactions in v3 blocks are required to follow rules #3-#7 as well.

When 95% of the past 1000 blocks are v3 or higher, v2 blocks become invalid entirely. Note however that v1 (and v2) transactions remain valid forever.


References

Below is a summary of the effects on signatures, their encoding and data pushes.

Low S values in signatures

The value S in signatures must be between 0x1 and 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0 (inclusive). If S is too high, simply replace it by S' = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 - S.

Signatures produced by the OpenSSL library are not guaranteed to be consistent with this constraint. Version 0.9.3 of the reference client provides an example [ http://github.com/bitcoin/bitcoin/blob/v0.9.3/src/key.cpp#L202-L227 ] for detection and correction.

The constraints on the value R are unchanged w.r.t. ECDSA, and values can be between 0x1 and 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364140 (inclusive).


DER encoding

For reference, here is how to encode signatures correctly in DER format.

0x30 [total-length] 0x02 [R-length] [R] 0x02 [S-length] [S] [sighash-type]

- total-length: 1-byte length descriptor of everything that follows, excluding the sighash byte.
- R-length: 1-byte length descriptor of the R value that follows.
- R: arbitrary-length big-endian encoded R value. It cannot start with any 0x00 bytes, unless the first byte that follows is 0x80 or higher, in which case a single 0x00 is required.
- S-length: 1-byte length descriptor of the S value that follows.
- S: arbitrary-length big-endian encoded S value. The same rules apply as for R.
- sighash-type: 1-byte hashtype flag (only 0x01, 0x02, 0x03, 0x81, 0x82 and 0x83 are allowed).

This is already enforced by the reference client as of version 0.8.0 (only as relay policy, not as a consensus rule).
This rule, combined with the low S requirement above, results in S-length being at most 32 (and R-length at most 33), and the total signature size being at most 72 bytes (and on average 71.494 bytes).


Push operators

- Pushing an empty byte sequence must use OP_0.
- Pushing a 1-byte sequence of byte 0x01 through 0x10 must use OP_n.
- Pushing the byte 0x81 must use OP_1NEGATE.
- Pushing any other byte sequence up to 75 bytes must use the normal data push (opcode byte n, with n the number of bytes, followed n bytes of data being pushed).
- Pushing 76 to 255 bytes must use OP_PUSHDATA1.
- Pushing 256 to 520 bytes must use OP_PUSHDATA2.
- OP_PUSHDATA4 can never be used, as pushes over 520 bytes are not allowed, and those below can be done using other operators.
- Any other operation is not considered to be a push.


Numbers

The native data type of stack elements is byte arrays, but some operations interpret arguments as integers. The used encoding is little endian with an explicit sign bit (the highest bit of the last byte). The shortest encodings for numbers are (with the range boundaries encodings given in hex between ()).

0: OP_0; (00)

1..16: OP_1..OP_16; (51)..(60)

-1: OP_1NEGATE; (79)

-127..-2 and 17..127: normal 1-byte data push; (01 FF)..(01 82) and (01 11)..(01 7F)

-32767..-128 and 128..32767: normal 2-byte data push; (02 FF FF)..(02 80 80) and (02 80 00)..(02 FF 7F)

-8388607..-32768 and 32768..8388607: normal 3-byte data push; (03 FF FF FF)..(03 00 80 80) and (03 00 80 00)..(03 FF FF 7F)

-2147483647..-8388608 and 8388608..2147483647: normal 4-byte data push; (04 FF FF FF FF)..(04 00 00 80 80) and (04 00 00 80 00)..(04 FF FF FF 7F)

Any other numbers cannot be encoded.

In particular, note that zero could be encoded as (01 80) (negative zero) if using the non-shortest form is allowed.


Compatibility

- Relay of transactions
A new node software version is released which makes v3 transactions standard, and relays them when their scriptSigs satisfy the above rules. Relaying of v1 transactions is unaffected. A v1 transaction spending an output created by a v3 transaction is also unaffected.

- Wallet updates
As v3 transactions are non-standard currently, it is not possible to start creating them immediately. Software can be checked to confirm to the new rules of course, but using v3 should only start when a significant part of the network's nodes has upgraded to compatible code. Its intended meaning is "I want this transaction protected from malleability", and remains a choice of the wallet software.

High and low S values in Bitcoin transaction signatures



Let N be the order of the base point G of the elliptic curve secp256k1. N is also known as the "curve order".

N = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

An ECDSA signature is comprised of an R value and an S value.

The domain of both S and R is the inclusive interval [1, N-1].

Converting the S value to its negative (modulo the curve order) does not change the mathematical validity of the signature.

To put this another way:
(R, S) is mathematically equivalent to (R, S'), where S' = N - S, where N is the curve order and S can be either a low S value or a high S value.

It's possible to choose to only consider low S values to be acceptable. The maximum permissible S value is then the curve order divided by 2. This removes one avenue of transaction malleability (the ability to change an S value in a signed transaction from low to high or vice versa).

Let M = floor(N/2).

M = 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0

The domain of low S values is the inclusive interval [1, M].

The domain of high S values is the inclusive interval [M+1, N-1].

Note: The highest S value is N-1. When N is odd, N - floor(N/2) = floor(N/2)+1. Therefore, the high-S domain is the inclusive interval [floor(N/2)+1, N-1].

If an ECDSA implementation produces a signature with a high S value, this high S value can be converted to a low S value by the following operation:
S' = N - S

When encoded in DER format, R and S are stored in big-endian form.

Proving that the two ECDSA digital signatures
1) (R, S)
2) (R, S') where S' = N - S
are mathematically equivalent (or even understanding a proof done by someone else) is beyond my current capabilities. I would have to study modular arithmetic for a while.

Currently, many Bitcoin mining nodes on the main Bitcoin network have decided to accept only transactions with low S values in their signatures. They will accept transactions with high S values, but will then change them to low S before attempting to mine them. This is a soft fork (a convention that limits the use of the original ruleset).

It is unlikely that Bitcoin nodes owned by miners would reject a new block containing a transaction with a signature with a high S value. This would be a hard fork, as this block would be valid under the original ruleset. Hard forks are dangerous from a financial and game-theoretical point of view.

This replacement is an acceptable simplification of the transaction format that:
- removes a aspect of transaction malleability.
- is unlikely to decrease the security of transactions.
- does not break compatibility with nodes that accept high-S-value transactions.






Further information concerning ECDSA signatures and S values



Pieter Wuille is one of the main advocates of the Segregated Witness project, so I don't trust him. I looked for further information from more trustworthy sources concerning the ideas in BIP 62.


Sources:
- X9.62-1998 The Elliptic Curve Digital Signature Algorithm (ECDSA)
- Opinions from Mircea Popescu, asciilifeform, and mod6, found in the logs of the #trilema chat channel.




I read various sections of x9_62_draft_ecdsa.pdf, which is included in the Downloadable Assets section.

Document details:
Title: Working Draft, American National Standard, X9.62-1998, Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)
Author: Accredited Standards Committee X9, American Bankers Association.
Date: September 20, 1998

I eventually skim-read the whole document, but found nothing explicit about low and high S values.

Relevant excerpts concerning ECDSA signatures are quoted below, along with some of my notes on them.



Page 4: Excerpt from section 2.2 (Symbols and Notation)

x mod n
The unique remainder r, 0 <= r <= n-1, when integer x is divided by n. For example, 23 mod 7 = 2.

x triple_bar y (mod n)
x is congruent to y modulo n. That is, (x mod n) = (y mod n).

x^-1 mod n
Definition: If gcd(x, n) = 1, then x^-1 mod n is the unique integer y, 1 <= y <= n-1, such that x*y triple_bar 1 (mod n).

Pages 16-17: Section 5.3 (Signature Generation)

5.3 Signature Generation

This section describes the ECDSA signature generation process. The signature generation process consists of:

1) Message digesting.
2) Elliptic curve computations.
3) Modular computations.

The inputs to the signature process are:

1) The message, M, of an arbitrary length, which is represented by a bit string.
2) A valid set of elliptic curve domain parameters.
3) An elliptic curve private key, d, associated with the elliptic curve domain parameters.

The output of the signature process are two integers r and s (the digital signature), where 1 <= r <= n-1, 1 <= s <= n-1.


5.3.1 Message Digesting

Compute the hash value e = H(M) using the hash function SHA-1 as specified in ANSI X9.30 Part 2 [4]. e is represented as an integer with a length of 160 bits.


5.3.2 Elliptic Curve Computations

1) Select a statistically unique and unpredictable integer k in the interval [1,n-1].

It is acceptable to use a random or pseudorandom number. If a pseudorandom number is used, it shall be generated using one of the procedures of Annex A.4 or in an ANSI X9 approved standard. If a pseudorandom generation method is used, the seed values used in the generation of k may either be determined by internal means, be supplied by the caller, or both - this is an implementation choice. In all cases, the seed values have the same security requirements as the private key value. That is, they must be protected from unauthorized disclosure and be unpredictable.

If the implementation allows a seed supplied by the caller, then the physical security of the device is of utmost importance. This is because if an adversary gained access to the signature generation device and were able to generate a signature with a seed of its choice for the per-message secret k, then the adversary could easily recover the private key.

2) Compute the elliptic curve point (x_1, y_1) = k*G. (See Annex D.3.2.)


5.3.3 Modular Computations

1) Convert the field element x_1 to an integer x_macron_1, as described in Section 4.3.5.
2) Set r = x_macron_1 mod n.
3) If r = 0, then go to step 1 of Section 5.3.2.
4) Compute s = k^-1 (e + d*r) mod n. (See Annex D.1.2. for one method to compute k^-1 mod n.)
5) If s = 0, then go to step 1 of Section 5.3.2.


5.3.4 The Signature

The signature for M shall be the two integers, r and s, as computed in Section 5.3.3.

NOTES:
1) In step 3 of Section 5.3.3, the probability that r = 0 is approximately 1/n.
2) In step 5 of Section 5.3.3, the probability that s = 0 is approximately 1/n.
3) As an optional security check (to guard against malicious or non-malicious errors in the signature generation process), the signer may verify that (r, s) is indeed a valid signature for message M using the signature verification process described in Section 5.4.

Key points:

- The ECDSA signature is composed of two numbers, r and s, that both lie in the inclusive interval [1, n-1], where n is the curve order.

- The pieces needed to create the signature are:
-- The message M to be signed. In my case, the double SHA256 hash digest of the transaction-in-signable-form.
-- A valid set of parameters describing an elliptic curve. In my case, this is the curve secp256k1.
-- The elliptic curve private key d. In my case, this is the private key of the Bitcoin address.
-- A integer k chosen randomly from within the inclusive interval [1, n-1].

- "If a pseudorandom generation method is used, the seed values used in the generation of k may either be determined by internal means, be supplied by the caller, or both - this is an implementation choice. In all cases, the seed values have the same security requirements as the private key value. That is, they must be protected from unauthorized disclosure and be unpredictable."
-- Note: The random number k (or a seed used to generate k values via a pseudo-random algorithm) is of the same importance as the private key.

- "If the implementation allows a seed supplied by the caller, then the physical security of the device is of utmost importance. This is because if an adversary gained access to the signature generation device and were able to generate a signature with a seed of its choice for the per-message secret k, then the adversary could easily recover the private key."
-- Note: k is "per-message" i.e. it should be used for only one message.
-- Note: If an adversary knows k and the resulting signature, and presumably the message M and the elliptic curve parameters, it is able to calculate the private key.

- When the signature has been calculated, r and/or s might be 0. In this case, the signature should be rejected and recalculated using a different value of k.

- k is used in the calculation of s.

- k is used in the calculation of r, because x_macron_1 is derived from x_1, which is derived from k*G.





Pages 17-18: Section 5.4 (Signature Verification)

5.4 Signature Verification

This section describes the ECDSA signature verification process.

The signature verification process consists of:

1) Message digesting.
2) Modular computations.
3) Elliptic curve computations.
4) Signature checking.

The input to the signature verification process is:

1) The received message, M', represented as a bit string.
2) The received signature for M', represented as the two integers, r' and s'.
3) A valid set of elliptic curve domain parameters.
4) A valid public key, Q, associated with the elliptic curve domain parameters.

The output of the signature verification process is an indication of signature verification success or failure.


5.4.1 Message Digesting

Compute the hash value e' = H(M') using the hash function SHA-1 as specified in ANSI X9.30 Part 2 [4]. e' is represented as an integer with a length of 160 bits.


5.4.2 Modular Computations

1) If r' is not an integer in the interval [1, n-1], then reject the signature.
2) If s' is not an integer in the interval [1, n-1], then reject the signature.
3) Compute c = (s')^-1 mod n. (See Annex D.1.2.)
4) Compute u_1 = e'*c mod n and u_2 = r'*c mod n.


5.4.3 Elliptic Curve Computations

1) Compute the elliptic curve point (x_1, y_1) = u_1*G + u_2*Q (see Annex D.3.2). (If u_1*G + u_2*Q is the point at infinity, then reject the signature.)


5.4.4 Signature Checking

1) Convert the field element x_1 to an integer x_macron_1, as described in Section 4.3.5.

2) Compute v = x_macron_1 mod n.

3) If r' = v, then the signature is verified, and the verifier has a high level of confidence that the received message was sent by the party holding the secret key d corresponding to Q. If r' does not equal v, then the message may have been modified, the message may have been incorrectly signed by the signatory, or the message may have been signed by an impostor. The message shall be considered invalid.

Key points:
- The signature is valid if r' = v.
- The calculation of v depends on x_macron_1, which depends on x_1, which depends on u_1 and u_2, which both depend on c.
- c = (s')^-1 mod n



Page 65: Annex D.1.2 (Inversion in a Finite Field)

D.1.2 Inversion in a Finite Field

If g != 0 is an element of the field F_q, then the inverse g^-1 is the field element c such that g*c = 1. The inverse can be found efficiently by exponentiation since c = g^(q-2). Note that if q is prime and g is an integer satisfying 1 <= g <= q-1, then g^-1 is the integer c, 1 <= c <= q-1, such that g*c triple_bar 1 (mod q). The algorithm is used in Sections 5.3.3 and 5.4.2.

Input: A field F_q, and a non-zero element g element_of F_q.

Output: The inverse g^-1.
1) Compute c = g^(q-2) (see Annex D.1.1).
2) Output c.

An even more efficient method is the extended Euclidean Algorithm [22, p. 325].

c = (s')^-1 mod n is the "modular inverse" of s'.


s' * (modular inverse of s) triple_bar 1 mod n, where triple_bar means "is congruent to".








I looked for discussion of S values in the logs of the #trilema chat channel.

Browse to:
btcbase.org/log

Note: This log site is maintained by phf.

Log excerpts and mod6's patch are in the Project Log section.



Notes:
- The curve order N is 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141.
- From x9_62_draft_ecdsa.pdf: The ECDSA signature is composed of two numbers, R and S, that both lie in the inclusive interval [1, N-1], where N is the curve order.
- From BIP 62: Low-S values lie in the inclusive interval [1, M], where M = floor(N/2) = 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0.


I trust opinions from Mircea Popescu, asciilifeform, and mod6 on this matter. I'll summarise the relevant key points from reading their discussions (and mod6's patch).


Key points from studying the logs:

- Signatures contain S values.

- S values can be low or high.

- A high S value can be changed to a low S value. This change occurs after the signature has been created. It is a small numerical change and won't affect transaction security.

- BIP 62 includes several points about S values and changing high S values to low S values. BIP 62 is broadly acceptable, even though it was written by Pieter Wuille

- To convert a high S value to a low S value, use the equation low_S_value = N - high_S_value.

- A signature that includes a high S value is a legitimate signature.

- The high/low S value ambiguity is built in at the protocol level. There are two mathematically valid outputs of the signing process, even if, when run once, it only produces one of them.

- It's not clear why a high-S-changed-to-low-S signature is still mathematically valid.

- The Bitcoin miners accept high-S transactions but change them to low-S before attempting to mine them.

- Choosing low-S values is a convention. It was technically possible for the network to have converged on using only high-S values in transaction signatures.

- Mircea Popescu: "when there's ambiguity in design, this is to be exposed to user.". A transaction-creation program should present the user with a choice, but not the obligation, to enforce low S values or high S values.

- A soft fork is a narrowing of the protocol. It is a convention for the use of an item, but does not actually change the overall behaviour of the item.

- A hard fork changes the overall behaviour of an item in some way.

- Miners choosing to mine only low-S transactions is a soft fork.

- Blocks containing high-S transactions, once mined, are unlikely to be rejected by nodes in the Bitcoin network. Making such a change is a hard fork, and miners are wary of implementing a hard fork in their code for good game-theoretic reasons.




Further notes:

- If a miner does not make this switch to only mining low-S transactions, his mempool management is more difficult. When a new block arrives with a high-S-changed-to-low-S transaction, any unconfirmed transactions that spend the outputs of this transaction will be invalid, since they will include the original txid of the changed transaction. They will have to be pruned from the mempool, because if the miner produces a block containing one of them, the entire block will be invalid. Ideally, this pruning should occur as soon as possible, so as to have maximum available time for mining. By switching to change-high-S-to-low-S, this pruning can occur before the arrival of a new block.

- Mircea Popescu points out that miners may be changing all high-S transactions to low-S transactions, but strategically they are obliged to not reject blocks containing high-S transactions, lest someone eventually mine such a block, causing a fork in which two mining chains emerge. Miners can't easily know which fork would win, and mining on the eventual loser chain means that all mining rewards from that chain would be lost, so they are highly incentivised to never change the new block acceptance ruleset, as they can't be sure that the majority of other miners would also make the exact same change. It's a prisoner's dilemma situation.

- Any one who maintains a Bitcoin node is also obliged to stick to the same new block acceptance ruleset, for the same game-theoretic reason.

- If a miner cartel exists that controls 51% of the hash power and can effectively coordinate its internal activity, then it could perhaps enforce a change in the block acceptance ruleset.






P2SH multi-signature addresses - security



Note: The following section is conjecture based on hearsay. It has not been tested.

Summary: Soft forks can be unmade as easily as they were made. They are necessarily easier to make or unmake than a hard fork. P2SH addresses, including P2SH multi-signature addresses, are only protected by a soft fork, not by the original protocol, and are therefore a less secure store of value than are P2PKH addresses.


[Hearsay] Pay-to-script-hash (P2SH) transactions were created in 2012 to let a spender create a pubkey script containing a hash of a second script, the redeem script.

[Hearsay] P2SH multi-signature is a subtype of P2SH.

[Hearsay] There was an earlier multi-signature transaction type, in which the entire redemption script was stored in the address. P2SH multi-signature has replaced it in actual use - in this case only the hash of the redemption script is stored in the address.

[Hearsay] P2SH multi-signature script format:


Note: In code, outputScript might be called "scriptPubKey", as it occupies the same position and role as the scriptPubKey for P2PKH outputs.

Let "nodes using the original ruleset" be "nodes".

Let "nodes using a soft-fork ruleset" be "soft-fork nodes".

P2SH is a soft fork, i.e. a narrowing of the original protocol, with something extra added on (the promise to only mine a transaction if the signatures in the scriptSig meet the conditions of the redeemScript). P2SH transactions are a convention that the miners promise to enforce.

The soft fork is a convention on how to use the items scriptPubKey and scriptSig from the original ruleset / protocol.

When a new transaction appears that spends from a P2SH multi-signature address, nodes will verify that the redeemScript in the scriptSig hashes to the hash value in the outputScript. Soft-fork nodes will additionally verify that the conditions in the redeemScript (i.e. M of N signatures by specified public keys) are satisfied by the [signature]s.

To nodes, the scriptSig looks like an invalid signature. They expect that the scriptSig contains a signature and a public key, that the public key verifies the signature, and that the signature was made by the private key corresponding to the public key. The redeemScript fulfills none of these conditions. Nodes won't accept the transaction and will not mine it or re-broadcast it. However, they won't reject blocks that contain it.

The soft fork (and, in fact, any soft fork) is only enforced because 51% of the mining hash power agrees to enforce it. If the majority of the hash power were to stop enforcing the extra conditions in the scriptSig redeemScript, anyone could create a new transaction that transferred bitcoin from a P2SH address to an original P2PKH address that they controlled.

Note: This transaction would not be valid under the original ruleset, because the hypothetical private key corresponding to the redeemScript hash would be unknown, so this transaction could not be validly signed. This seizure would therefore have to be done with the cooperation of 51% of the mining power, who would have to accept (or at least not reject) this new transaction. This would essentially be another, different, soft fork.

The people with the incentive to eventually try to do this "soft fork rollback" would be some emergent miner conglomerate / alignment, whenever it became worthwhile to do so without too much risk. This rollback would not affect those who use P2PKH addresses - it would therefore be a limited seizure of funds that would probably not greatly affect the market value of the Bitcoin ecosystem in the long term. The P2PKH addresses would continue to be a reasonably safe store of value, regardless of whether the soft-fork P2SH addresses are enforced or not.

Note: Any change of the ruleset that allowed a miner conglomerate to seize funds stored in P2PKH addresses would be a hard fork. In the event of a hard fork, it is likely that the original ruleset would be preserved by a subsection of the mining hash power, and that there would be a fork in the chain. The hard-fork chain would likely see a steady decrease in its market price (due to being an unsafe store of value). The original-ruleset chain would continue as normal.

Conclusion: Soft forks can be unmade as easily as they were made. They are necessarily easier to make or unmake than a hard fork. P2SH addresses, including P2SH multi-signature addresses, are only protected by a soft fork, not by the original protocol, and are therefore a less secure store of value than are P2PKH addresses.






P2SH multi-signature addresses - results from this project



To send to a P2SH multi-signature address, I don't need to worry about how to spend from it. I just need to construct an outputScript from the P2SH address and use it in the transaction output.

The P2SH outputScript is:

- 20 in hex is 0x14.

The address format of P2SH addresses is:


On the main network, the version byte is 0x05.

Note: Because the '05' byte is always added at the front of the script hash, a P2SH address will never start with a leading zero byte, so the count-leading-zeros section of the base58check algorithm will never have an effect on the address during conversion.

Version byte + 20-byte hash with the minimum possible integer value:
"05"+"00"*20 =
050000000000000000000000000000000000000000
- in base58check_encoding (in which the 4-byte checksum is added), this is:
31h1vYVSYuKP6AhS86fbRdMw9XHieotbST
- minimum value as a decimal integer:
7307508186654514591018424163581415098279662714880

Version byte + 20-byte hash with the maximum possible integer value:
"05"+"FF"*20 =
05FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
- in base58check_encoding (in which the 4-byte checksum is added), this is:
3R2cuenjG5nFubqX9Wzuukdin2YfBbQ6Kw
- maximum value as a decimal integer:
8769009823985417509222108996297698117935595257855

So: A string of 21 bytes that starts with the '05' byte, once converted into base58check encoding (with a 4-byte checksum added by the encoding function), always starts with the base58 symbol '3'.


I decoded my then-current LocalBitcoins receiving address
36CQfj2Yt54sZttJYTb5ywuS7YGEQLfzCE
and found that the redeemScript hash inside it was:
316f8d5c41d88d3a0df179fc5ad765d57f7f4667

I then constructed an outputScript from the redeemScript hash.

outputScript:


I was able to construct and sign a valid transaction that transferred bitcoin from the P2PKH target address to the P2SH multi-signature LocalBitcoins receiving address. This was transaction 2.









Transactions constructed and signed in this project



Sequence of actions:
- Have a LocalBitcoins account that holds some bitcoin.
- Generate an address (the "source address").
- Generate a second address (the "target address").
- Use LocalBitcoins system to transfer some bitcoin from the LocalBitcoins account to the source address.
- Construct and sign a transaction to move the available bitcoin from the source address to the target address. Upload this transaction to a web service for broadcast to the network.
- Construct and sign a transaction to move the available bitcoin from the target address to my then-current LocalBitcoins receiving address. Upload this transaction to a web service for broadcast to the network.

Note: My then-current LocalBitcoins receiving address was a P2SH multi-signature address. I had to learn how to construct a transaction that transferred bitcoin to a multi-signature address.


Let tx0 be the transaction that moved bitcoin from my LocalBitcoins account to the source address.

Let tx1 be the transaction that moved bitcoin from the source address to the target address.

Let tx2 be the transaction that moved bitcoin from the target address to my then-current LocalBitcoin receiving address.


Let txid0 be the transaction id of tx0.

Let txid1 be the transaction id of tx1.

Let txid2 be the transaction id of tx2.



For tx0:
- It was mined in block 529181.

For tx1 and tx2:
- There was one input and one output.
- I chose a fee of 1 satoshi / byte.
- I assumed a transaction size of 225 bytes.
- The final fee amount was (1 satoshi / byte) x 225 bytes = 225 satoshis.
- I subtracted this fee amount from the output value.

For tx1:
- Transaction fee was 225 satoshis.
- Transaction size was 223 bytes.
- Fee was therefore 225/223 satoshis/byte, which is slightly more than 1 satoshi/byte.
- Estimated delay for 1-2 satoshis / byte was 3-21 blocks or 20-300 minutes. Later, at time of broadcast, it was 2-7 blocks or 5-180 minutes.
- It was mined in block 529790 within a few minutes.

For tx2:
- Transaction fee was 225 satoshis.
- Transaction size was 221 bytes.
- Fee was therefore 225/221 satoshis/byte, which is slightly more than 1 satoshi/byte.
- At time of broadcast, estimated delay for 1-2 satoshis / byte was 0-7 blocks or 0-120 minutes.
- It was mined in block 530582 within approximately 5 minutes.



txid0 (little-endian, used in block explorers):


txid0 (big-endian form, produced by the double SHA256 hash of the signed transaction):



txid1 (big-endian form, produced by the double SHA256 hash of the signed transaction):


txid1 (little-endian, used in block explorers):



txid2 (big-endian form, produced by the double SHA256 hash of the signed transaction):


txid2 (little-endian, used in block explorers):




The little-endian forms of the txids can be used to look up the transactions on a block explorer web service.

Examples:

tx0:
blockchain.info/tx/8482e48391425d88fe30bd4066957000335f58e83f854f997146f41b9493b4ce

tx1:
live.blockcypher.com/btc/tx/4bdd5f653d0100ea4735953e8e22e92321af9074926b3bd33c279c289f2d975a

tx2:
live.blockcypher.com/btc/tx/87d230cad8ae3cc065ce9b52fbbd81140948e3e95b250c9015faa8048e1dee40





tx1 (signed):




scriptSig:



scriptPubKey:




Insert the scriptSig and scriptPubKey byte sequences into transaction 1. Also calculate and insert their byte length var_ints.



tx1 (signed):




tx1 (signed):




tx1 (signed):


It is 223 bytes long.



When I first constructed tx1, its signature contained a high S value.

I browsed to:
blockchain.info/decode-tx
pasted in the signed transaction hex, and clicked "Submit Transaction".

The transaction was parsed successfully.

I browsed to:
blockchain.info/pushtx
pasted in the signed transaction hex, and clicked "Submit Transaction".

I got this error:


I then studied the meaning of "high S value" in transaction signatures and learned how to create transactions that always had low S values.

I made a new low-S signature for the transaction and was able to upload it for broadcast and mining.






tx2 (signed):




scriptSig:



outputScript:



Insert the scriptSig and outputScript byte sequences into transaction 2. Also calculate and insert their byte length var_ints.


tx2 (signed):




tx2 (signed):




tx2 (signed):


It is 221 bytes long.



The first time that I constructed transaction-2-in-signable-form, I forgot to include values for "script_length: (var_int)" for both {scriptPubKey of unspent output from previous transaction} and the output outputScript. The signature was therefore invalid.

I browsed to:
live.blockcypher.com/btc/decodetx
Network = "Bitcoin".
pasted in the signed transaction hex, and clicked "Decode Transaction".

The transaction was parsed successfully.

I browsed to:
blockchain.info/pushtx
pasted in the signed transaction hex, and clicked "Submit Transaction".

I got this error:



I inserted the missing values into the transaction, re-signed it, and was able to upload it for broadcast and mining.







Transaction identifier (txid) construction and endianness



Excerpt from:
bitcoin.org/en/developer-reference#hash-byte-order

Bitcoin Core RPCs accept and return the byte-wise reverse of computed SHA-256 hash values. For example, the Unix sha256sum command displays the SHA256(SHA256()) hash of mainnet block 300,000's header as:

> /bin/echo -n '020000007ef055e1674d2e6551dba41cd214debbee34aeb544c7ec670000000000000000d3998963f80c5bab43fe8c26228e98d030edf4dcbe48a666f5c39e2d7a885c9102c86d536c890019593a470d' | xxd -r -p | sha256sum -b | xxd -r -p | sha256sum -b
5472ac8b1187bfcf91d6d218bbda1eb2405d7c55f1f8cc820000000000000000

The result above is also how the hash appears in the previous-header-hash part of block 300,001's header:

020000005472ac8b1187bfcf91d6d218bbda1eb2405d7c55f1f8cc82000\
0000000000000ab0aaa377ca3f49b1545e2ae6b0667a08f42e72d8c24ae\
237140e28f14f3bb7c6bcc6d536c890019edd83ccf

However, Bitcoin Core's RPCs use the byte-wise reverse for hashes, so if you want to get information about block 300,000 using the

getblock

RPC, you need to reverse the requested hash:

> bitcoin-cli getblock \
000000000000000082ccf8f1557c5d40b21edabb18d2d691cfbf87118bac7254

(Note: hex representation uses two characters to display each byte of data, which is why the reversed string looks somewhat mangled.)

The rationale for the reversal is unknown, but it likely stems from Bitcoin Core's use of hashes (which are byte arrays in C++) as integers for the purpose of determining whether the hash is below the network target. Whatever the reason for reversing header hashes, the reversal also extends to other hashes used in RPCs, such as TXIDs and merkle roots.

As header hashes and TXIDs are widely used as global identifiers in other Bitcoin software, this reversal of hashes has become the standard way to refer to certain objects. The table below should make clear where each byte order is used.

[Note: table converted to list]


List of data types and their byte orders in different situations:
[Note: Presumably, Internal Byte Order is always big-endian and RPC Byte Order is always little-endian.]

- Data = SHA256(SHA256(0x00))
-- Internal Byte Order = Hash: 1406...539a
-- RPC Byte Order = Hash 9a53...0614

- Data = Header Hashes: SHA256(SHA256(block header))
-- Internal Byte Order = Used when constructing block headers
-- RPC Byte Order = Used by RPCs such as

getblock

; widely used in block explorers

- Data = Merkle Roots: SHA256(SHA256(TXIDs and merkle rows))
-- Internal Byte Order = Used when constructing block headers
-- RPC Byte Order = Returned by RPCs such as

getblock

- Data = TXIDs: SHA256(SHA256(transaction))
-- Internal Byte Order = Used in transaction inputs
-- RPC Byte Order = Used by RPCs such as

gettransaction

and transaction data parts of

getblock

; widely used in wallet programs

- Data = P2PKH Hashes: RIPEMD160(SHA256(pubkey))
-- Internal Byte Order = Used in both addresses and pubkey scripts
-- RPC Byte Order = N/A: RPCs use addresses which use internal byte order

- Data = P2SH Hashes: RIPEMD160(SHA256(redeem script))
-- Internal Byte Order = Used in both addresses and pubkey scripts
-- RPC Byte Order = N/A: RPCs use addresses which use internal byte order


Note: RPCs which return raw results, such as

getrawtransaction

or the raw mode of

getblock

, always display hashes as they appear in blocks (internal byte order).

Notes:
- RPC = Remote Procedure Call
-- RPC commands are the main way to use the original Bitcoin client from the command line.


Key points:
- In raw Bitcoin data, hashes are stored in big-endian format.
-- Possible reason: The original Bitcoin client needs to check that the header hash of a new bitcoin block is below the current network target value. This comparison is easier if the hash is stored in big-endian format.
- Hashes in Bitcoin: block headers, transaction ids (txids), and merkle roots.
- When used as identifiers in the original client's RPC calls (for e.g. getting data about a block or transaction), hashes are in little-endian format.
- Little-endian is the de facto standard for Bitcoin hash identifiers, but hashes (e.g. txids) are in big-endian form within raw Bitcoin data.









Endianness



A byte is (usually) a sequence of 8 bits. Example (binary): 0011 0001. In hex, this example is 31.

A byte can be interpreted as a number or as a character. A useful default is to interpret byte sequences as characters. Example: A text editor is directed to open a file whose format is unknown.

An 8-bit byte can have any value in the binary inclusive interval 0000 0000 - 1111 1111.

When interpreted as a number, a byte can have any value in the inclusive (decimal) interval 0-255.

When a byte is interpreted as a character, a text encoding (often ASCII by default) is used to look up a character for that particular byte's value. A text encoding is an alphabet i.e. a convention for a set of symbols arranged in a particular order. The numerical value of the byte is used to select a position in the alphabet and thereby choose the symbol / letter / character in that position.

Notes:
- Not all byte values in the ASCII encoding correspond to a printable character.
- Encodings other than ASCII could be used to interpret a byte as a character. However, ASCII emerged as a Schelling point during the development of computers and is therefore the best default choice.

A data item is a sequence of one or more bytes. Examples (hex): "31", "31 30".

A data item can contain another data item. Example (hex): "68 65 6c 6c 6f 5f 31". Here, the item "31" is contained within the larger item "68 65 6c 6c 6f 5f 31".

Let i1 be "31".

Let i2 be "68 65 6c 6c 6f 5f 31".

When i1 and i2 are interpreted as ASCII text (i.e. sequential single byte values), then:
i1 = "1"
i2 = "hello_1"

If a data item is multi-byte and is intended to represent a particular (often numerical) value, then the order of the bytes in this data item is important. Let's define this type of data item to be a "multi-byte data value".

Example (hex): "31 30".

Note: An example of a non-numerical multi-byte value would be the à character in the UTF-8 encoding, which in hex bytes is "C3 A0".

In big-endian format, the first byte is the most significant byte (MSB) and the last byte is the least significant byte (LSB). The hex byte sequence 31 30 would then represent the decimal value 12592. The MSB would be 31 and the LSB would be 30.

In little-endian format, the first byte is the least significant byte (LSB) and the last byte is the most significant byte (MSB). The hex byte sequence 31 30 would then represent the decimal value 12337. The MSB would be 30 and the LSB would be 31.

A data item format should specify where multi-byte data values can occur internally and how many bytes they will contain.

Example data item format "value":
- [6-byte string "value="] + [1-byte length number N] + [big-endian multi-byte integer value consisting of N bytes]

Example data item in this format:
76 61 6c 75 65 3d 02 31 30

The first 6 bytes "76 61 6c 75 65 3d" are "value=" when interpreted as ASCII characters.

"02" is a single byte of numerical value 2 indicating that the following 2 bytes are the big-endian multi-byte integer value.

"31 30" is the big-endian multi-byte integer value. In decimal, its value is 12592.

Note: It is important to specify the length of a multi-byte data value, otherwise a parser (human or software) will not know when it has reached the end of the multi-byte data value. It is important to specify whether a multi-byte data value is big-endian or little-endian, else the parser will interpret the value incorrectly.

Let's define a data item that contains several multi-byte data values to be a "container".

A container can be very difficult to parse if the byte lengths of multi-byte data values within it are not specified.

Note that the order of bytes within a container is (in my experience) almost always "first byte to be read by the parser comes first". This is similar to MSB-first big-endian format.

Example container format "Book":
- Book_name: [1-byte length number N] + [multi-byte string value]
- Pages: value
- Words: value
Note: This container uses the "value" data item above as a component.

Example container in this format:
05 42 6f 6f 6b 31 76 61 6c 75 65 3d 01 32 76 61 6c 75 65 3d 02 31 30

This container contains 3 data items, to be read in consecutive order, in accordance with the Book format, starting at the first byte in the sequence and ending at the last byte in the sequence.

Zen exercise for student: If you didn't know that this byte sequence was a Book container, how would you find out which format you should use to interpret it?

Let's parse this Book container.

The first byte should be a 1-byte length number. The first byte is "05". This byte, interpreted as has a numerical value of 5. This means that the next 5 bytes should be the Book_name.

The next 5 bytes are "42 6f 6f 6b 31". When interpreted as ASCII characters, these bytes are "Book1". We assume that we've reached the end of the Book_name multi-byte data value.

The next data item that we expect, from reading the format, is a Pages "value" item. The next 6 bytes are "76 61 6c 75 65 3d" as expected. When interpreted as ASCII characters, these bytes are "value=".

We then interpret the next byte as a length number. In this case the next byte is 01. In decimal, this is 1.

We look at the next 1 byte, which is 32. In decimal, this is 50. So this Book container indicates that Book1 has 50 pages. We assume that we've reached the end of the Pages "value" data item.

The next data item that we expect, from reading the format, is a Words "value" item. The next 6 bytes are "76 61 6c 75 65 3d" as expected. When interpreted as ASCII characters, these bytes are "value=".

We then interpret the next byte as a length number. In this case the next byte is 02. In decimal, this is 2.

We look at the next 2 bytes, which are 31 30. When interpreted as a big-endian multi-byte data value, this is 12592 in decimal. So this Book container indicates that Book1 has 12592 words. We assume that we've reached the end of the Words "value" data item.

Note: In this text, I've generally used e.g. "05" to write a single hex byte and e.g. "42 6f 6f 6b 31" to write a hex byte sequence. The "0x" prefix is also used to write hex bytes e.g. 0x05 and 0x42 6f 6f 6b 31.


Key points:
- Endianness doesn't matter for storing ASCII string data (i.e. raw bytes) e.g. "hello world". The default approach when trying to read a data item in an unknown data format is to interpret its bytes as ASCII characters.
- Endianness matters when working with multi-byte data items e.g. 4-byte integers.
- Big-endian: Most significant byte (MSB) comes first.
- Little-endian: Least significant byte (LSB) comes first.



Further notes on endianness:

- CPUs can be designed to operate on big-endian or on little-endian multi-byte data values.

- Some reading indicates that:
-- Filesystems and operating systems generally, but not always, store multi-byte data values in the same endianness as that used by the CPU architecture that they run on.
--- Example: [Hearsay] The FAT filesystem is written to always use the same endianness, regardless of the CPU architecture. Therefore, on some systems it must use a different endianness to that of the CPU.
-- If they do not, byte-swapping steps must occur that change the endianness of multi-byte data values before the CPU performs any operations on them.

- Endianness parsing problems occur when trying to read a binary file that was originally created on another system that used a different endianness.

- Data container formats, which may contain multi-byte data values (of either endianness), are usually "first-byte-first" for easier reading and debugging, regardless of CPU architecture.

- Some reading indicates that a similar endianness problem exists for the order of bits within a byte. This is called "bit numbering" or "bit endianness". The equivalent of little-endian is "Least Significant Bit (LSB) first" and the equivalent of big-endian is "Most Significant Bit (MSB) first". The terms MSbit, MSbyte, LSbit, and LSbyte can be used to differentiate the abbreviations MSB and LSB when dealing with both contexts at the same time. This bit endianness is usually transparent to the software (i.e. implemented invisibly at a very low level), so unless you are writing in very precise languages (I think Ada allows you to specify bit endianness) or working at the hardware level (e.g. computer network data transmission systems), this isn't something that you are likely to encounter.



Key points concerning endianness and numerical algorithms derived from an answer written by Thomas Pornin:
Source:
security.stackexchange.com/questions/13553/does-the-endianness-used-with-an-encryption-algorithm-affect-its-security

- When an algorithm, e.g. a hash algorithm, relies on a particular endianness for certain data, this is included in the algorithm specification.

- The implementation is responsible for following the algorithm specification, regardless of the CPU endian convention.
-- If an implementation is written for a CPU architecture with a different endianness than that required by the algorithm, the implementation must include the necessary byte-swapping steps.

- C code can be written in an endian-neutral way.
-- Note: I think that Thomas Pornin is referring specifically to C code where there is no interpretation of a byte sequence as an integer. This operation must carefully manage the endianness of the byte sequence, or the result will be not be the same on different systems.
-- Example: The AES algorithm does not interpret any byte sequences as integers, so the code for it can be written in an endian-neutral way. The same C code can be compiled and run on systems that use different endianness.

- The specifications for the SHA-1 / SHA-256 hash functions include a big-endian convention.



Principle: Code must be written separately for each CPU architecture if a specific endianness is to be used within an algorithm across a set of architectures. Example: SHA256 algorithm.


I have read through the PyPy SHA256 code but I don't understand it. I've been getting usable results so far by assuming that this SHA256 code returns big-endian results. My system (Mac OS X 10.6.8) is little-endian.

Two possibilities:
- The Python engine always uses a particular endianness internally, and all its implementations support this, regardless of system endianness. This Python SHA256 code will work on any system on which a Python implementation has been installed.
- The Python engine uses the system endianness. This Python SHA256 code was written on / for a little-endian CPU architecture. If I were to run this Python SHA256 code on a Python engine installed on a big-endian system, it might not work properly. A new Python SHA256 implementation would have to be written for this hypothetical big-endian system.









Proposal for a unique transaction identifier (utxid)



Transaction Malleability: A valid transaction scriptSig can be altered in ways that change its raw byte sequence but not its mathematical validity. The rest of the transaction cannot be altered without making the signature(s) mathematically invalid. The transaction identifier (txid) is created by hashing the transaction twice with the SHA256 algorithm. If there are multiple versions of a transaction (each with different alterations to one or more scriptSigs), then each version will have a different transaction identifier (txid).

Transaction tracking problem: The original parties to a transaction will use the txid derived from the original transaction, but a different version, altered and rebroadcast by a malicious third party, might be mined. This would make tracking the status of the transaction more difficult. If you scan each new block for the txid you are expecting, you won't register the altered version's txid and won't know that the transaction has been entered into the blockchain. Instead, you must track relevant address balances, wait for them to register an increase / decrease, and then check the accounts of each address to confirm that all the amounts are correct (multiple transactions might be moving bitcoin into or out of the same address(es) during the same time period).

Given the problem of Transaction Malleability, how could a transaction be given a unique transaction identifier (utxid), perhaps only for use within an internal transaction tracking system?

Possible approach:

0) Run at least one Bitcoin node. Perform the following steps for each new transaction received.

1) Receive a new transaction.

2) Confirm the mathematical validity of its signature(s).

3) Strip all scriptSigs from the transaction.

4) Hash the stripped transaction with double SHA256.

5) Use the resulting hash digest as a utxid. If multiple versions of the transaction are received, with different but valid scriptSigs, processing them in this way will produce the same unique identifier.

6) Store all received versions of a transaction and group them under the same utxid. Hash each one with double SHA256 to produce a normal transaction identifier (txid).

7) When processing new blocks, watch for normal txids. For each one, look up its unique identifier and check if there are multiple transaction versions. Discard all versions except for the one that was mined. Optionally, perform this alternate-version-cleanup only once N further blocks have been mined. A common value of N in practice is 6.

8) For an internal transaction tracking system (i.e. "which transactions are still waiting to be confirmed?"), use the unique identifier. When any version of the transaction is mined, it can be mapped to this unique identifier and the tracking system can change the transaction's status to "mined".

9) For communication with the external world, use the normal txid of the mined version of the transaction.

Using this approach, alternate transaction versions can be discarded, rather than taking up storage space and / or requiring further processing to determine their status.
- Note: All that is required to confirm a transaction as valid is a single mined version in which all signatures are mathematically valid.
- Note: This unique identifier will not be usable on other systems that haven't implemented it.

If a transaction disappears from the network (i.e. the memory pools of all public nodes), this doesn't mean that it has vanished permanently. Anyone who stored it can rebroadcast it later - it will still be valid. This means that if you want to try to make the same payment again, it is best to create a new transaction that uses the same UXTO set but has a higher mining fee. If this transaction is mined, the previous one will be invalid, as each UXTO can only be spent once.
- Note: If the original transaction only involved outgoing payments to other people, and it did not send any change back to one of your addresses, then the mining fee cannot be increased by decreasing the change amount. One solution: Add a new input UXTO, and perhaps also use a change address so as not to spend the entire new input UXTO. The previous transaction will be invalidated as long as at least one of its UXTOs is spent in the new transaction.
















Is the use of compressed public keys in Bitcoin addresses a soft fork, or is this capability a part of the basic protocol?
- Related: Is there any way to know that a particular address is derived from the hash of a compressed public key? I doubt it, but it would be useful to know for sure.



In the two transactions in this project, the byte length of the signature_data item within a scriptSig was 71 bytes long, both times. In the Notes / Discoveries section, in part "Standard transaction - raw format", I specified that signature_data byte length was "71 bytes (approximately)". What are the high and low limits of the signature_data byte length?
- In a previous project, Reading and verifying a standard raw bitcoin transaction, the transaction that I verified had a signature_data byte length of 72. Ken Shirriff's transaction, also investigated in this project, had a signature_data byte length of 71.
- From BIP 62: "This rule [strict DER encoding for signatures], combined with the low S requirement above, results in S-length being at most 32 (and R-length at most 33), and the total signature size being at most 72 bytes (and on average 71.494 bytes)."
-- BIP 62 doesn't mention a lower limit on the signature byte length, but from the information supplied I suspect that it might be 71 bytes.



Find out which of the following possibilities is true:
1) The Python engine always uses a particular endianness internally, and all its implementations support this, regardless of system endianness. The Python SHA256 code will work on any system on which a Python implementation has been installed.
2) The Python engine uses the system endianness. The Python SHA256 code was written on / for a little-endian CPU architecture. If I were to run the Python SHA256 code on a Python engine installed on a big-endian system, it might not work properly. A new Python SHA256 implementation would have to be written for this hypothetical big-endian system.



Is the following statement true?
"The FAT filesystem is written to always use the same endianness, regardless of the CPU architecture."



Work through and test the recipe in the section Recipe For Managing The Fee And Broadcast Of A Bitcoin Transaction.



Read the original Bitcoin code to see if the following section is accurate:
- [Hearsay] The original client uses big-endian hashes in the raw data, but little-endian for all values in RPC calls. Therefore, txids are big-endian in the raw transaction, but little-endian when used in an RPC call to look up a transaction. For this reason, block explorers mostly use and display txids in little-endian format.



Work on acquiring the following data from the raw forms of the relevant previous transactions for use when creating a new transaction, rather than by looking it up on a block explorer service.

Transaction data that can be acquired by analysing previous transactions on the blockchain:

Notes:
- "scriptPubKey of relevant unspent output from previous transaction" is used when signing a transaction to make a signature for a particular input. It can be derived from the input address. However, it should also be found within the relevant unspent output in a previous transaction, and then compared against the version derived from the input address as a sanity check.



Work through the "Algorithm for signing a standard transaction" (a part of the Notes / Discoveries section) with a transaction that contains two inputs. This will test the unknown part of step (4), included again here:

4) Remove the scriptSigs of other inputs. I haven't tested this myself yet. Some reading indicates that a single 0x00 byte is substituted for each length var_int of other scriptSigs (thus indicating that the scriptSig contains no data).



Investigate the [untested] ideas in the following section of the Transaction Malleability part of the Notes / Discoveries section.

Examples of possible alterations to the signature or scriptSig:
- [Untested] Signatures may not be encoded in strict DER format.
- The S value in a signature can be changed from high to low or vice versa. In the ECDSA cryptosystem, a high S value is mathematically identical to the corresponding low S value.
- [Untested] Changing an opcode to a different opcode (or sequence of opcodes) that performs the same overall function.
- [Untested] Adding leading zero bytes to the X or Y value in the public key data in the scriptSig.
Each of these changes alters the transaction's byte sequence but not its validity.



Prove that the two ECDSA digital signatures
1) (R, S)
2) (R, S') where S' = N - S
are mathematically equivalent.
This will probably require studying modular arithmetic.



Investigate the mathematics behind the ECDSA signing and signature verification processes. Why do these processes work?



























Plan of action:
- Generate an address and move some bitcoin into it (the "source address").
- Obtain a second address (the "target address").
- Find out the recent average mining fee.
- Create a raw Bitcoin transaction that specifies the transfer of the bitcoin from the source address to the target address. Be careful to include a mining fee.
- Sign the transaction using the private key of the source address and ECDSA cryptography. Before signing, the transaction must be altered slightly to get the transaction-in-signable-form.
- Embed the transaction signature into the transaction.
- Broadcast the transaction to the Bitcoin network.
- Confirm that the transaction has been mined (included in a block in the Bitcoin blockchain). This verifies that the transaction was valid (i.e. in the correct format, with a mathematically valid signature).





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





Create a project directory
("creating_and_signing_a_standard_raw_Bitcoin_transaction").
Inside the project directory, create a work directory ("work").


Browse to the earlier article
Generating a standard Bitcoin address
and download these four assets:

- bjorn_edstrom_ripemd160.py
- ecdsa-0.10.tar.gz
- pypy_sha256.py
- generate_bitcoin_address.py


Put these assets in the work directory.


Follow the steps in the Bitcoin Address Generation Recipe section of this earlier article.


1) Create or generate a private key in raw byte form.

I'll choose: the_library_of_babel
as my ASCII private key.

Normally, I would use dice and a word table to generate a longer, more secure passphrase.


2) Unpack the zipped tape archive file ecdsa-0.10.tar.gz file.

Open a terminal and change to the work directory.




3) The unpacking produced a new directory: ecdsa-0.10. ecdsa-0.10 contains a directory named: ecdsa. Copy the ecdsa directory to the work directory. The ecdsa library can now be imported by the generate_bitcoin_address.py script.


4) Open the generate_bitcoin_address.py file in a text editor. Set the value of the variable private_key_bytes to be the private key in raw byte form that was generated earlier ("the_library_of_babel").


5) Run the script generate_bitcoin_address.py.





Looks good.


I'll check that if this address has already been used on the Bitcoin blockchain.

Browse to:
blockchain.info

In the search box, enter:
1CTumCMjzBfccCJBTkHoPQmAwEqU9Uj2sQ

Result:
"No transactions found for this address, it has probably not been used on the network yet."


When I broadcast the transaction, there must be some bitcoin in the source address in order for the transaction to be valid. However, I don't have to send the bitcoin right now. I can first learn how to construct the transaction.


The target address can be my LocalBitcoins receiving address. This is currently:
36CQfj2Yt54sZttJYTb5ywuS7YGEQLfzCE


Hm. It starts with a '3', so this is a multi-signature address, which I consider to be non-standard. I want to test a transaction that sends bitcoin from one standard address to another.

I'll create another address using generate_bitcoin_address.py.


private key: the_eye_of_argon





In the search box on blockchain.info, enter:
12RbVkKwHcwHbMZmnSVAyR4g88ZChpQD6f

Result:
"No transactions found for this address, it has probably not been used on the network yet."



I'll need to send enough bitcoin to the source address to pay for two transaction fees. The first transaction will transfer bitcoin from the source address to the target address. The second transaction will transfer bitcoin from the target address to my LocalBitcoins receiving address. Making this second transaction will allow me to see if there are any peculiarities when transfering bitcoin from a standard address to a multi-signature address.



After some searching, I found:
bitcoinfees.earn.com
which displays fees in satoshis/byte, along with the estimated delay (in blocks and in minutes) for each fee value range.


Excerpts:

Which fee should I use?

The fastest and cheapest transaction fee is currently 208 satoshis/byte, shown in green at the top.
For the median transaction size of 225 bytes, this results in a fee of 46,800 satoshis.

Please note that many wallets use satoshis-per-kilobyte or bitcoins-per-kilobyte, so you may need to convert units. See our instructions for more details.

[...]

What are the fees shown here?

The fees displayed here are Satoshis (0.00000001 BTC) per byte of transaction data. Miners usually include transactions with the highest fee/byte first.


What does the delay mean?

The delay shown here is the predicted number of blocks the transactions will take to confirm. If a transactions are predicted to have a delay between 1-3 blocks, there is a 90% chance that they will be confirmed within that range (around 10 to 30 minutes).
Transactions with higher fees will often have 0 delay, which means they will likely be confirmed with the next block (usually around 5-15 minutes).


How is the delay predicted?

The predictions are based on blockchain data of the last 3 hours, as well as the current pool of unconfirmed transactions (mempool).
First, a likely future mempool and miner behavior is predicted using Monte Carlo simulation. From the simulations, it can be seen how fast transactions with different fees are likely to be included in the upcoming blocks.
The predicted delay shown here is chosen to represent a 90% confidence interval.

Notes:
- The fee value range of 207-208 satoshis/byte is coloured green. The chart is in reverse order (lowest fees shown at the top) so this fee range actually appears at the bottom.
- The delay for this range is 0 blocks or 0-30 minutes.
- Every fee value range higher than 208 satoshis/byte is also coloured green, and also has a delay of 0 blocks or 0-30 minutes.
- "fastest and cheapest transaction fee" means "the cheapest of the fastest possible transaction fees".


I'm not bothered by tests taking a long time, if this time is somewhat predictable. I'll have a look at the low end.

For 0 satoshis/byte, delay is 61-Inf blocks or 480-Inf minutes.

Unpredictable. I assume that "inf" means infinity.

For 1-2 satoshis/byte, delay is 3-21 blocks or 20-300 minutes.

For 3-4 satoshis/byte, delay is 3-19 blocks or 20-300 minutes.


What delay does 0.5 * (the value of the cheapest of the fastest fees) buy?

208/2 = 104

For 103-104 satoshis/byte, delay is 2-4 blocks or 5-80 minutes.


I'll use 1-2 satoshis/byte. A 5 hour delay is acceptable. I'll check this again though before I broadcast the transaction.


What can I do if my transaction is rejected by every miner and never mined, due to having a very low fee?



Excerpts from:
support.earn.com/digital-currency/bitcoin-mempools/how-to-figure-out-how-long-your-transaction-has-been-in-other-nodes-mempools
Author: Zach

How to figure out how long your transaction has been in other node's mempools

Most miners use Bitcoin Core which, by default, removes transactions over 72 hours old from its mempool. This is a very useful feature if your transaction gets stuck because it allows you to re-send a similar transaction that pays a higher fee.

If you know about when you sent your transaction, then you can just wait three days from then to try to resend. If you're the recipient of the transaction or you just don't remember when the transaction was sent, some blockchain explorers will tell you when they added the transaction to their mempool.

[...]

Most nodes receive new transactions within a minute of each other, so you can simply add three days to the time listed for when the transaction was received.

Ok.
- When broadcasting, record the time and blockheight.
- If the transaction is not mined within e.g. 2 * expected_delay_blocks (in my case, 2 * 5 = 10 blocks), then:
-- wait three days (measured from time of broadcast) + a small delay (to ensure that transaction has been deleted from all nodes' mempools)
-- check estimated delays for fee ranges again and choose a higher fee range relative to the lowest non-infinite-delay fee range.
-- re-sign the transaction with this new higher fee and rebroadcast it (again remembering to record the time and blockheight, in case this new transaction is also not mined).



Next: Create a raw Bitcoin transaction that specifies the transfer of the bitcoin from the source address to the target address. Be careful to include a mining fee.



Excerpts from an earlier article:
Reading and verifying a standard raw bitcoin transaction

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

Expected format (raw hex bytes):
- version: 4 bytes (little-endian)
- input_count: (var_int)
- inputs:
-- previous_output_hash: 32 bytes (little-endian)
-- previous_output_index: 4 bytes (little-endian)
-- script_length: (var_int)
-- scriptSig
-- sequence: 4 bytes (little-endian)
- output_count: (var_int)
- outputs:
-- value: 8 bytes (little-endian)
-- script_length: (var_int)
-- scriptPubKey
- block lock time: 4 bytes

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).


[...]


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:

01000000014f8cad2ca3b602750e06c4300d91b22c17dd97bb5ce635d860df8b0ab325b336010000006b483045022100d8321c3c4b3fc3a34e30547d1cb6aea6855cad330b590b53e824f647dd49239902201e9056e82297a2108b1969cc497150734ab78f51cbf979885afc104f70a65150012102a534d65273f8520e1e841ccbb782b71e06b4117a90bb92c655f8131cf6ae2261fdffffff02e8d94100000000001976a914338cdde52f708236affa5675f969606ff846ee6f88acc4716e01000000001976a9143496950f1a01285a1605ac9337c06a5596b9fcd888accaee0700

In space-separated hex bytes, this transaction is:

01 00 00 00 01 4f 8c ad 2c a3 b6 02 75 0e 06 c4 30 0d 91 b2 2c 17 dd 97 bb 5c e6 35 d8 60 df 8b 0a b3 25 b3 36 01 00 00 00 6b 48 30 45 02 21 00 d8 32 1c 3c 4b 3f c3 a3 4e 30 54 7d 1c b6 ae a6 85 5c ad 33 0b 59 0b 53 e8 24 f6 47 dd 49 23 99 02 20 1e 90 56 e8 22 97 a2 10 8b 19 69 cc 49 71 50 73 4a b7 8f 51 cb f9 79 88 5a fc 10 4f 70 a6 51 50 01 21 02 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 fd ff ff ff 02 e8 d9 41 00 00 00 00 00 19 76 a9 14 33 8c dd e5 2f 70 82 36 af fa 56 75 f9 69 60 6f f8 46 ee 6f 88 ac c4 71 6e 01 00 00 00 00 19 76 a9 14 34 96 95 0f 1a 01 28 5a 16 05 ac 93 37 c0 6a 55 96 b9 fc d8 88 ac ca ee 07 00

In subdivided readable form, this transaction is:

- [derived property] byte length: 226
- version: 01 00 00 00
- input_count: 01
- [derived property] input_count_decimal: 1
- input #0:
-- previous_output_hash: 4f 8c ad 2c a3 b6 02 75 0e 06 c4 30 0d 91 b2 2c 17 dd 97 bb 5c e6 35 d8 60 df 8b 0a b3 25 b3 36
-- [derived property] previous_output_hash (no spaces, big-endian): 36b325b30a8bdf60d835e65cbb97dd172cb2910d30c4060e7502b6a32cad8c4f
-- previous_output_index: 01 00 00 00
-- [derived property] previous_output_index_decimal: 1
-- script_length: 6b
-- [derived property] script_length_decimal: 107
-- scriptSig: 48 30 45 02 21 00 d8 32 1c 3c 4b 3f c3 a3 4e 30 54 7d 1c b6 ae a6 85 5c ad 33 0b 59 0b 53 e8 24 f6 47 dd 49 23 99 02 20 1e 90 56 e8 22 97 a2 10 8b 19 69 cc 49 71 50 73 4a b7 8f 51 cb f9 79 88 5a fc 10 4f 70 a6 51 50 01 21 02 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
-- sequence: fd ff ff ff
- output_count: 02
- [derived property] output_count_decimal: 2
- output #0:
-- value: e8 d9 41 00 00 00 00 00
-- [derived property] output value in bitcoin: 0.04315624
-- script_length: 19
-- [derived property] script_length_decimal: 25
-- scriptPubKey: 76 a9 14 33 8c dd e5 2f 70 82 36 af fa 56 75 f9 69 60 6f f8 46 ee 6f 88 ac
- output #1:
-- value: c4 71 6e 01 00 00 00 00
-- [derived property] output value in bitcoin: 0.24015300
-- script_length: 19
-- [derived property] script_length_decimal: 25
-- scriptPubKey: 76 a9 14 34 96 95 0f 1a 01 28 5a 16 05 ac 93 37 c0 6a 55 96 b9 fc d8 88 ac

In subdivided readable form, the scriptSig is:

- PUSHDATA: 48
- [derived property] PUSHDATA decimal value: 72
- signature_data: 30 45 02 21 00 d8 32 1c 3c 4b 3f c3 a3 4e 30 54 7d 1c b6 ae a6 85 5c ad 33 0b 59 0b 53 e8 24 f6 47 dd 49 23 99 02 20 1e 90 56 e8 22 97 a2 10 8b 19 69 cc 49 71 50 73 4a b7 8f 51 cb f9 79 88 5a fc 10 4f 70 a6 51 50 01
- PUSHDATA: 21
- [derived property] PUSHDATA decimal value: 33
- public_key_data: 02 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

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

- OP_DUP: 76
- OP_HASH160: a9
- PUSHDATA: 14
- [derived property] PUSHDATA decimal value: 20
- public_key_hash: 7e 76 71 29 b1 5e e6 d7 e6 be 8a c3 a1 00 dd 29 c4 c6 7e 63
- OP_EQUALVERIFY: 88
- OP_CHECKSIG: ac

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.)


[...]


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.


[...]


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.

expected script for a standard transaction:
- [scriptSig]
-- PUSHDATA: 1 byte
-- signature data + SIGHASH_ALL
-- PUSHDATA: 1 byte
-- public key data
- [scriptPubKey]
-- OP_DUP / 0x76: 1 byte
-- OP_HASH160 / 0xa9: 1 byte
-- PUSHDATA: 1 byte
-- public key hash: 20 bytes (== 160 bits)
-- OP_EQUALVERIFY / 0x88: 1 byte
-- OP_CHECKSIG / 0xac: 1 byte

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. The public key data in Ken Shirriff's signed transaction begins with 04 and is uncompressed.

Opcode descriptions:

- byte value: 0x01-0x4b
-- Word: PUSHDATA
-- Opcodes 1-75 (e.g. OP_1).
-- Input: [Special]
-- Output: a single stack item
-- Description: Let N be the byte value of the opcode. The next N bytes are data to be pushed onto the stack as a new stack item.

- byte value: 0x69
-- Word: OP_VERIFY
-- Opcode: 105
-- Input: True / false
-- Output: Nothing / fail
-- Description: Marks transaction as invalid if top stack value is not true. The top stack item is removed.

- byte value: 0x76
-- Word: OP_DUP
-- Opcode: 118
-- Input: top_item
-- Output: top_item, top_item
-- Description: Duplicates the top stack item.

- byte value: 0x87
-- Word: OP_EQUAL
-- Opcode: 135
-- Input: top_item, item_below_top_item
-- Output: True / false.
-- Description: Returns 1 if the inputs are exactly equal, 0 otherwise.

- byte value: 0x88
-- Word: OP_EQUALVERIFY
-- Opcode: 136
-- Input: top_item, item_below_top_item
-- Output: Nothing / fail.
-- Description: Same as OP_EQUAL, but runs OP_VERIFY afterward.

- byte value: 0xa9
-- Word: OP_HASH160
-- Opcode: 169
-- Input: top_item
-- Output: hash
-- Description: The top item on the stack is hashed twice: first with SHA-256 and then with RIPEMD-160.

- byte value: 0xac
-- Word: OP_CHECKSIG
-- Opcode: 172
-- Input: top_item, item_below_top_item (signature, public key). Also hash of entire transaction-in-signable-form.
-- Output: True / false
-- Description: The entire transaction (in an altered form) is hashed. The signature must be a valid signature for this hash and public key. If it is, 1 is returned, otherwise 0 is returned.

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

- For each input:
-- Acquire the relevant scriptPubKey of the previous transaction (that supplies the unspent output used as an input in the new transaction).
-- Substitute this scriptPubKey for the scriptSig of this input. Also substitute the scriptPubKey's length var_int for the scriptSig's length var_int.
-- Remove the scriptSigs of other inputs. I haven't tested this myself. Some reading indicates that a single 0x00 byte is substituted for each length var_int of other scriptSigs (thus indicating that the scriptSig contains no data).
-- Append a four-byte form of the hash_type. For hash type 1, SIGHASH_ALL, this is 0x01 00 00 00 (The value "1" in little-endian form).
-- The transaction is currently the transaction-in-signable-form.
-- Sign this form of the transaction with the private key corresponding to the public key to which the unspent output was originally sent.
-- Remove the four-byte hash_type from the end of the transaction.
-- Append a one-byte version of the hash_type (e.g. SIGHASH_ALL == 0x01) to the scriptSig signature data.
-- Save the scriptSig for this input.

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.

Ok.

Transaction format:




Let's see how much of this can be constructed without a previous transaction on the blockchain.


More notes from reading Reading and verifying a standard raw bitcoin transaction:

- I think that the version is hardcoded as '1'. In 4 hex bytes, this is 01 00 00 00.

- The previous_output_hash is:
-- the hash of the previous transaction that:
--- contains the unspent output that:
---- will be used as an input in this new transaction

- The previous_output_hash is in little-endian format within a raw transaction, but in the block explorer I have used (blockchain.info), it is in big-endian format. It is also known as the transaction id or "txid".

- The previous_output_index is the implicit index (starting at 0) of the unspent output in the list of unspent outputs in the previous block.

- The domain of the opcode PUSHDATA is 1-75 in decimal (0x01-0x4b in hex).

- Sequence can always be set to 0xffffffff. It is a nonfunctional legacy feature that was designed to allow multiple signers to agree to update a transaction.

- Block lock time can always be set to 0x00000000. It was designed to ask miners not to mine a transaction until a specified block height is reached. In this case, it can be mined at any block height after 0.


I won't have the following information until I have made a transaction that transfers some bitcoin to the source address:
- previous_output_hash
- previous_output_index
- value


The input_count is a var_int. I will only use 1 input, so it's 0x01.

Note: 0x is a prefix that means 'hex'.


I won't know the var_int script_length of scriptSig until I have constructed scriptSig.


The scriptSig of the previous analysed transaction is:



Note that in this case the public_key_data is compressed.

The signature_data will be produced during the transaction signing process.

The rest of the scriptSig can however be assembled now. The public_key_data will be the public key of the source address. It won't be compressed.

- public_key_hex:



I need to know how many bytes there are in this value.



The previous command counted the number of characters in the value. Each hex byte is two characters, so I need to divide the result by two in order to know the number of bytes in the value.

130 / 2 = 65. This is within the 1-75 domain of the PUSHDATA opcode.


65 is a decimal value. What's 130 in hex?



It's 41.


For legibility, I'll separate each hex byte with a space.




Now let's insert this data into the new scriptSig.

new scriptSig:




The output_count is a var_int. I will only use 1 output, so it's 0x01.


The target address contains the hash of the target public key. This public key hash is needed for constructing scriptPubKey.

target address:
12RbVkKwHcwHbMZmnSVAyR4g88ZChpQD6f



In the earlier article Generating a standard Bitcoin address, I described an algorithm for generating a Bitcoin address. I'll copy the relevant excerpt below. I will then construct an algorithm that partially reverses the process and derives the public key hash from the address.

Algorithm for generating a Bitcoin address:

1) Create an ECDSA private key. Add leading zero bytes until it is 256 bits (32 bytes) long.

This private key must be in the closed interval [1, n-1] where n is the order of the base point G of the elliptic curve secp256k1. In hex, n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141. n is 32 bytes (256 bits) long. Most, but not all, 256-bit sequences are valid Bitcoin private keys.

2) Generate the corresponding ECDSA public key.

3) Hash the public key using the SHA256 algorithm.

4) Hash the result of step (3) using the RIPEMD-160 algorithm.

5) Add the version byte in front of the result of step (4). For the main Bitcoin network, the version byte is 0x00. Another way to describe this step is: Bytewise concatenate the version byte and the result of step (4).

6) Hash the result of step (5) using the SHA256 algorithm.

7) Hash the result of step (6) using the SHA256 algorithm.

8) Select the first four bytes of step (7).

9) Bytewise concatenate the result of step (5) and step (8).

10) Treating the result of step (9) as a single big-endian bignumber, convert it to base-58 using bignumber division. This result should not have any leading zeros.

11) Count the number of leading zeros in the result of step (5).

12) Let the result of step (11) be N. Add N '1' characters in front of the result of step (10). Each of these represents a leading zero byte that was not preserved in step (10).


Steps 6-12 comprise the Base58Check algorithm.


Algorithm for step (10):
- Convert the byte sequence to a big integer. How this is done will depend on the programming language. The result must be stored in a big integer data type upon which a division operation can be performed.
- Set a result string R to be an empty string.
- Repeatedly divide the big integer by 58. Using the base-58 conversion table (below), convert the remainder of each division into a base-58 symbol. Append this symbol to the end of R. Stop when the result is 0.
- Reverse the result string R.
- Note: It would be possible to prepend to the beginning of R instead of appending, and thus have no need to reverse R at the end, but prepending is usually a slower operation than appending.



Base-58 conversion table:

Remainder Value => Base-58 Symbol

0 => 1
1 => 2
2 => 3
3 => 4
4 => 5
5 => 6
6 => 7
7 => 8
8 => 9
9 => A
10 => B
11 => C
12 => D
13 => E
14 => F
15 => G
16 => H
17 => J
18 => K
19 => L
20 => M
21 => N
22 => P
23 => Q
24 => R
25 => S
26 => T
27 => U
28 => V
29 => W
30 => X
31 => Y
32 => Z
33 => a
34 => b
35 => c
36 => d
37 => e
38 => f
39 => g
40 => h
41 => i
42 => j
43 => k
44 => m
45 => n
46 => o
47 => p
48 => q
49 => r
50 => s
51 => t
52 => u
53 => v
54 => w
55 => x
56 => y
57 => z

Algorithm for deriving the public key hash from a Bitcoin address:

1) Count the number of leading '1' characters in the address, then remove them.

2) Convert the result of step (1) from the Bitcoin base-58 encoding to a base-10 integer.

3) Convert the result of step (2) from a base-10 integer to a hex byte string.

4) The last four bytes in the result of step (3) are the checksum. Remove them.

5) Let the result of step (1) be N. Add N leading zero bytes to the result of step (4).

6) The first byte in the result of step (5) is the version byte. For the main Bitcoin network, the version byte is 0x00. Remove it.

7) The final result of step (6) should be the public key hash in hex bytes, i.e. RIPEMD-160(SHA256(public_key)). It should be 160 bits or 160 / 8 = 20 bytes long.


Steps 1-5 comprise the reverse Base58Check algorithm.


Algorithm for step (2):
- Let the length of the base-58 string be N. Let M = N - 1.
- Treat the base-58 string as an array of characters. Set the index i = 0 i.e. the first index in the array, starting from the left.
- Let the running total x = 0.
- Perform the following loop until all characters in the base-58 string have been processed:
-- Use the index i to select a character from the base-58 string.
-- Look up this character's decimal value in the base-58 symbol conversion table.
-- Multiply this value by 58 ^ (M - i).
-- Add the result of this multiplication to x.
-- Increment i by 1.
- When the entire base-58 string has been processed, the running total x should now contain the decimal value of the base-58 string.

Note: As we proceed to the low end of the base-58 string, the power of 58 decreases, exactly the same as in a decimal number.
Example:
For 156, N = 3 and M = 2.
156 = 1*(10^2) + 5*(10^1) + 6*(10^0)






Ok. Let's test.


Target Bitcoin address:
12RbVkKwHcwHbMZmnSVAyR4g88ZChpQD6f


1) There is one leading '1' character. After it is removed, the result is:
2RbVkKwHcwHbMZmnSVAyR4g88ZChpQD6f

2)



N = 33. M = 33 - 1 = 32.

Let i = 0. Let x = 0.

The first character is 2. The symbol 2 is 1 in decimal.

1 * (58 ^ (32 - 0)) = 1 * 58^32



x = x +
268965015114358137726910587140455987105619365599731777536
= 268965015114358137726910587140455987105619365599731777536

i = i + 1 = 0 + 1 = 1

I'll write some code to automate this process.


[development occurs here]







Result:



Next:
3) Convert the result of step (2) from a base-10 integer to a hex byte string.




The final 'L' in a Python string indicates a "long" type. Remove it.

Result:
0xf9ee78522f6cc8a88784ae02b0408e452d80259ccc52540



Hm. In order to be a byte string, the length needs to be divisible by 2 (every 2 hex characters represents an 8-bit byte).

Add a '0' at the front.

Result:



4) The last four bytes in the result of step (3) are the checksum. Remove them.

Result:



5) Let the result of step (1) be N. Add N leading zero bytes to the result of step (4).

N = 1.

Result:



6) The first byte in the result of step (5) is the version byte. For the main Bitcoin network, the version byte is 0x00. Remove it.

Result:



7) The final result of step (6) should be the public key hash in hex bytes, i.e. RIPEMD-160(SHA256(public_key)). It should be 160 bits or 160 / 8 = 20 bytes long.



Divide length by 2 to get the number of bytes.
40 / 2 = 20.
This is the expected length.




Let's check if this is the correct public key hash value by taking the public key value (found earlier during address generation) and hashing it.

public_key_hex for target address:





Result of hashing the public key:


Result derived earlier from the target Bitcoin address:



Let's test equality mechanically.




Good. The hash values are equal. The algorithm and code for deriving the public key hash from a Bitcoin address works correctly for at least one case.



Let's construct the scriptPubKey for the target address.

Note: A later transaction, that moves bitcoin from the target address to some other address, must be signed by the private key corresponding to the public key that hashes to the hash value in this scriptPubKey.


The scriptPubKey of the previous analysed transaction is:



For legibility, I'll separate each hex byte in the public key hash with a space.




The scriptPubKey for the target address is:



The script_length var_int for this scriptPubKey will be the same as in the previously analysed transaction, because the public_key_hash was 20 bytes long in both cases.

So, script_length (in hex) = 19



Ok. Let's assemble the transaction (as much as possible) from all these calculated values.


Transaction format:






New transaction:




scriptSig:



scriptPubKey:




Next: Transfer some bitcoin to the source address. Once the transaction that performs this transfer has been mined, I can look it up on the blockchain in order to acquire these values:
- previous_output_hash
- previous_output_index
- value

Note: Wait for 5 more blocks to be mined after the block containing my transaction.


How much to transfer?

I'll assume the median transaction size of 225 bytes.

The cheapest of the fastest fee ranges is 207-208 satoshis/byte.

At 208 satoshis/byte, a 225-byte transaction will cost 225 * 208 = 46800 satoshis.

I plan to use much lower fees, but I should transfer enough to be absolutely sure I can afford the fees during this project, so I'm using the high end of the fee range in my calculations.


I'll eventually make a second transaction to move the remaining bitcoin from the target address back to my LocalBitcoins account, so I need to double the fee.

46800 * 2 = 93600 satoshis.


During the earlier project Generating a standard Bitcoin address, LocalBitcoins charged a deposit fee of 0.00015000 bitcoin.


Excerpt from:
localbitcoins.com/fees

When sending to LocalBitcoins wallet, a bitcoin network fee is deducted from the deposit. The fee varies on how congested the Bitcoin Network is. If your deposit amount is smaller than the bitcoin deposit fee, the deposit will not be processed.

So, the amount sent back to the LocalBitcoins wallet needs to be greater than the LocalBitcoins deposit fee.

0.00015000 btc is 15000 satoshis.

Add the deposit fee:

93600 + 15000 = 108600 satoshis


In bitcoin, this is 0.00108600.

I'll add some slack and send 0.002 bitcoin. At current prices, this is about $12.


Log on to LocalBitcoins.

Send 0.002 bitcoin to source address:
1CTumCMjzBfccCJBTkHoPQmAwEqU9Uj2sQ

LocalBitcoins charged a transaction fee of 0.00005 bitcoin. This was subtracted from my LocalBitcoins wallet balance, not from the amount that was actually sent.

Browse to LocalBitcoins / Wallet / Transactions.
Refresh the page after a minute or so.
A txid is now shown:


Browse to blockchain.info.
Copy the txid in the search box and press enter.
blockchain.info/tx/8482e48391425d88fe30bd4066957000335f58e83f854f997146f41b9493b4ce
Transaction is unconfirmed.

Set timer for 10 minutes.

Timer has gone off.
Refresh blockchain.info transaction info page.
3 confirmations.

I'll wait for 6 total confirmations.

Set timer for 30 minutes.

Timer has gone off.
Refresh blockchain.info transaction info page.
7 confirmations.


Ok. Let's proceed.



This transaction transferred bitcoin from my LocalBitcoins account to the source address. Treating this transaction as the new "previous transaction", I can now look up the following information:
- previous_output_hash
- previous_output_index
- value
for use in a new transaction.




The txid is:


The previous_output_hash, as used in the raw transaction, is the txid in little-endian format. (If I recall correctly, txids are in big-endian format.) So, I need to reverse the byte order.




So, previous_output_hash is:



Next: previous_output_index

Manually count the outputs of this transaction on the transaction info page.
blockchain.info/tx/8482e48391425d88fe30bd4066957000335f58e83f854f997146f41b9493b4ce
Result = 20
Outputs are implicitly 0-indexed.

My source address is the 10th from the top, so it has an index of 9. I am assuming that blockchain.info displays the output addresses in the same order in which they are stored within the raw transaction and that index=0 is at the top of the list.

So: previous_output_index = 9

In hex, this is 09. It needs to be 4 bytes (little-endian), so add 3 leading zero bytes and reverse it.

So:

previous_output_index = 09 00 00 00


Finally: value

Currently, the source address contains 0.002 bitcoin or 200000 satoshis.

I'll assume the median transaction size of 225 bytes.

At 1 satoshi/byte, a 225-byte transaction will include a transaction fee of 225 satoshis.

The value will be the current amount minus the fee.

200000 - 225 = 199775

value = 199775

I might adjust this a bit depending on how big the actual new transaction turns out to be.

The value needs to be 8 bytes (little-endian).



Result: 30c5f
Add a 0 at the front to make this hex value to be of even length (i.e. full bytes).
030c5f
03 0c 5f

Add 5 leading zero bytes to make this value 8 bytes long.
00 00 00 00 00 03 0c 5f

Now reverse it to make it little-endian.
5f 0c 03 00 00 00 00 00


So, value = 5f 0c 03 00 00 00 00 00








Next: Insert these values into the new transaction:



Transaction format:






New transaction:




scriptSig:



scriptPubKey:







Ok. Transaction has been assembled.

Next: Get the signable form of this transaction for the relevant input. In this case, there is only one input.


From an earlier excerpt:

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

- For each input:
-- Acquire the relevant scriptPubKey of the previous transaction (that supplies the unspent output used as an input in the new transaction).
-- Substitute this scriptPubKey for the scriptSig of this input. Also substitute the scriptPubKey's length var_int for the scriptSig's length var_int.
-- Remove the scriptSigs of other inputs. I haven't tested this myself. Some reading indicates that a single 0x00 byte is substituted for each length var_int of other scriptSigs (thus indicating that the scriptSig contains no data).
-- Append a four-byte form of the hash_type. For hash type 1, SIGHASH_ALL, this is 0x01 00 00 00 (The value "1" in little-endian form).
-- The transaction is currently the transaction-in-signable-form.
-- Sign this form of the transaction with the private key corresponding to the public key to which the unspent output was originally sent.
-- Remove the four-byte hash_type from the end of the transaction.
-- Append a one-byte version of the hash_type (e.g. SIGHASH_ALL == 0x01) to the scriptSig signature data.
-- Save the scriptSig for this input.

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.

Hm. I need the scriptPubKey of the source address used in the recently mined transaction. I can then substitute it for the scriptSig in the new transaction.

I can derive it from the source address using the process I developed earlier to derive a scriptPubKey from the target address. I'm using standard opcodes that won't change.

Source address:
1CTumCMjzBfccCJBTkHoPQmAwEqU9Uj2sQ

This time, I'll automate the process a little more. I'll test with the target address first in order to double-check the code.


[development occurs here]







Result:


From earlier, the result of hashing the public key of the target address:


Let's test equality mechanically.



Good.


Now, uncomment the second line containing the variable "address" and run the script again in order to process the source address.




Result:



For legibility, I'll separate each hex byte with a space.





Hm. A piece of information that I hadn't consciously realised before, but had just picked up without any consideration:
- The public_key_hash in scriptPubKey is stored in big-endian form.


Note:
- On the transaction info page
blockchain.info/tx/8482e48391425d88fe30bd4066957000335f58e83f854f997146f41b9493b4ce
the 10th Output Script from the top is:

- Note: Click "Show scripts & coinbase" to display the Output Scripts.
- The public key hash shown in this scriptPubKey is the same as the value I have just derived. This is a confirmation that the derivation process works correctly.



The scriptPubKey for the source address:



In a single byte sequence, this is:


Counting manually, its length in bytes is:
1 + 1 + 1 + 20 + 1 + 1 = 25

In hex, this length is: 19


Now, substitute this scriptPubKey from the previous transaction for the scriptSig of the new transaction. Also substitute its script_length.

No changes need to be made to other inputs or scriptSigs, since for the new transaction there is only one input.

Also, append a four-byte form of the SIGHASH_ALL hash_type to the transaction. For hash type 1, SIGHASH_ALL, this is 0x01 00 00 00 (The value "1" in little-endian form).





Transaction-in-signable-form format:






New transaction-in-signable-form:




scriptPubKey:





Let's compress the scriptPubKey for the target address into a single byte sequence, then place it into the transaction object.




New transaction-in-signable-form:






Let's compress the new transaction-in-signable-form into a single byte sequence.




New transaction-in-signable-form:



Remove spaces:




New transaction-in-signable-form:




Next: Sign the new transaction-in-signable-form.


I recall that Ken Shirriff used the Python ECDSA library to do this.


Excerpt from Reading and verifying a standard raw bitcoin transaction.
Original source: Ken Shirriff's article Bitcoins the hard way: Using the raw Bitcoin protocol.

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

I've already appended the hash type ("01000000").

Steps:
- SHA256(SHA256(transaction-in-signable-form))
- Create a SigningKey object from the private key of the source Bitcoin address (that supplies its unspent output as the input to the new transaction).
- Use the sign_digest() method of the SigningKey to sign the double SHA256 hash digest of the transaction-in-signable-form. Use the sigencode argument to specify that the signature should be returned in DER encoding.
- Append hash_type (as a single byte) "01" to DER-encoded signature.
- Get the public key corresponding to the private key of the source Bitcoin address.
- Construct the scriptSig using the signature and the public key. I suspect that the utils.varstr() function adds a length var_int to the beginning of its input data.
- It's a good idea to call the transaction verification function at the end, as a sanity check.


Information from earlier about the source address private key:






The double SHA256 hash digest of the transaction-in-signable-form is:


The DER-encoded signature of the double SHA256 hash digest (with hash type byte appended) is:

- this is 73 bytes long. 73 in hex is 49.


For legibility, I'll add spaces in between the hex bytes in the signature.





Signature:




I can now finish constructing the scriptSig of the new transaction. I added the public key data (and its var_int length) earlier.

new scriptSig:




Now, I can take the new transaction (not in signable form) and insert this scriptSig, which will prove its validity.





Transaction format:






New transaction:




scriptSig:



scriptPubKey:




Convert the scriptSig into a byte sequence.




Need the script_length var_int for scriptSig.



The script_length var_int for scriptSig, in hex, is: 8c


Convert the scriptPubKey into a byte sequence.




Insert the scriptSig and scriptPubKey byte sequences into the transaction.


New transaction:





Convert the final form of the new transaction into a byte sequence.




New transaction:




Remove spaces:




Signed transaction:



Next: Broadcast transaction and see if it is mined (or rejected).


Let's double-check the current fees before broadcasting.

Browse to:
bitcoinfees.earn.com
- For 0 satoshis/byte, estimated delay is Inf blocks or 9960-Inf minutes.
- For 1-2 satoshis/byte, estimated delay is 2-11 blocks or 5-180 minutes.
- For 3-4 satoshis/byte, estimated delay is 2-9 blocks or 5-180 minutes.



While reading and verifying a standard raw bitcoin transaction, I noted the existence of a "pushtx" option on blockchain.info.


Browse to:
blockchain.info/pushtx

Excerpt:

Broadcast Transaction

Tip: Check your transaction before broadcasting using the decode transaction tool [ http://blockchain.info/decode-tx ]

This page allows you to paste a raw transaction in hex format (i.e. characters 0-9, a-f) and broadcast it over the bitcoin network.

Browse to:
blockchain.info/decode-tx

Paste in signed transaction.
Result:




Transaction parsed successfully. Various values are as expected.

Note: At first, I had forgotten to add the script_length var_int for the scriptSig. This page returned "Parse: Error Parsing Transaction". I read back over my work and found and fixed the problem, so this parsing step to check the format was useful.

The size of the transaction is 225 bytes. I forgot to check for this earlier.

Let's double-check.



Good.


The "hash" value for the previous output is:


This is the txid of the transaction that transferred bitcoin to the source address. Notably, it's in big-endian format.

The "hash" value for the signed transaction is:


Presumably, this is the txid for this new signed transaction, in big-endian format.


Browse to:
blockchain.info/pushtx

Paste in the signed transaction and click "Submit transaction".

Result:



Hm.




I've read about high and low S values in Bitcoin before, but I never understood what it meant, and I didn't dig far enough to find out.


Google "bitcoin high and low s value".
Nothing looks useful. Lots of results concerning the price of bitcoin.

I recall that this was related to transaction malleability in some way.

Google "bitcoin high and low s value malleability".


First result:
github.com/bitcoin/bips/blob/master/bip-0062.mediawiki
Author: Pieter Wuille

Note: BIP = Bitcoin Improvement Proposal


Entire text of this result follows. I've included it all here because it contains further information about transaction malleability that might be useful in future.

NOTICE: This document is a work in progress and is not complete, implemented, or otherwise suitable for deployment.

BIP: 62 Layer: Consensus (soft fork) Title: Dealing with malleability Author: Pieter Wuille <pieter.wuille@gmail.com> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0062 Status: Withdrawn Type: Standards Track Created: 2014-03-12 License: BSD-2-Clause

Table of Contents

- Abstract
- Copyright
- Motivation
- Specification
-- New rules
-- Block validity
-- References
--- Low S values in signatures
--- DER encoding
--- Push operators
--- Numbers
- Compatibility


Abstract

This document specifies proposed changes to the Bitcoin transaction validity rules in order to make malleability of transactions impossible (at least when the sender doesn't choose to avoid it).


Copyright

This BIP is licensed under the 2-clause BSD license.


Motivation

As of february 2014, Bitcoin transactions are malleable in multiple ways. This means a (valid) transaction can be modified in-flight, without invalidating it, but without access to the relevant private keys.

This is a problem for multiple reasons:

- The sender may not recognize his own transaction after being modified.
- The sender may create transactions that spend change created by the original transaction. In case the modified transaction gets mined, this becomes invalid.
- Modified transactions are effectively double-spends which can be created without malicious intent (of the sender), but can be used to make other attacks easier.

Several sources of malleability are known:

1) Non-DER encoded ECDSA signatures
Right now, the Bitcoin reference client uses OpenSSL to validate signatures. As OpenSSL accepts more than serializations that strictly adhere to the DER standard, this is a source of malleability. Since v0.8.0, non-DER signatures are no longer relayed already.

2) Non-push operations in scriptSig
Any sequence of script operations in scriptSig that results in the intended data pushes, but is not just a push of that data, results in an alternative transaction with the same validity.

3) Push operations in scriptSig of non-standard size type
The Bitcoin scripting language has several push operators (OP_0, single-byte pushes, data pushes of up to 75 bytes, OP_PUSHDATA1, OP_PUSHDATA2, OP_PUSHDATA4). As the later ones have the same result as the former ones, they result in additional possibilities.

4) Zero-padded number pushes:
In cases where scriptPubKey opcodes use inputs that are interpreted as numbers, they can be zero padded.

5) Inherent ECDSA signature malleability
ECDSA signatures themselves are already malleable: taking the negative of the number S inside (modulo the curve order) does not invalidate it.

6) Superfluous scriptSig operations
Adding extra data pushes at the start of scripts, which are not consumed by the corresponding scriptPubKey, is also a source of malleability.

7) Inputs ignored by scripts
If a scriptPubKey starts with an OP_DROP, for example, the last data push of the corresponding scriptSig will always be ignored.

8) Sighash flags based masking
Sighash flags can be used to ignore certain parts of a script when signing.

9) New signatures by the sender
The sender (or anyone with access to the relevant private keys) is always able to create new signatures that spend the same inputs to the same outputs.

The first six and part of the seventh can be fixed by extra consensus rules, but the last two can't. Not being able to fix #7 means that even with these new consensus rules, it will always be possible to create outputs whose spending transactions will all be malleable. However, when restricted to using a safe set of output scripts, extra consensus rules can make spending transactions optionally non-malleable (if the spender chooses to; as he can always bypass #8 and #9 himself).


Specification

New rules

Seven extra rules are introduced, to combat exactly the seven first sources of malleability listed above:

1) Canonically encoded ECDSA signatures
An ECDSA signature passed to OP_CHECKSIG, OP_CHECKSIGVERIFY, OP_CHECKMULTISIG or OP_CHECKMULTISIGVERIFY must be encoded using strict DER encoding. To provide a compact way to deliberately create an invalid signature for OP_CHECKSIG and OP_CHECKMULTISIG, an empty byte array (i.e., the result of OP_0) is also allowed. Doing a verification with a non-DER signature makes the entire script evaluate to False (not just the signature verification). See reference: DER encoding.

2) Non-push operations in scriptSig
Only data pushes are allowed in scriptSig. Evaluating any other operation makes the script evaluate to false. See reference: Push operators.

3) Push operations in scriptSig of non-standard size type
The smallest possible push operation must be used when possible. Pushing data using an operation that could be encoded in a shorter way makes the script evaluate to false. See reference: Push operators.

4) Zero-padded number pushes
Any time a script opcode consumes a stack value that is interpreted as a number, it must be encoded in its shortest possible form. 'Negative zero' is not allowed. See reference: Numbers.

5) Inherent ECDSA signature malleability
We require that the S value inside ECDSA signatures is at most the curve order divided by 2 (essentially restricting this value to its lower half range). See reference: Low S values in signatures.

6) Superfluous scriptSig operations
scriptPubKey evaluation will be required to result in a single non-zero value. If any extra data elements remain on the stack, the script evaluates to false.

7) Inputs ignored by scripts
The (unnecessary) extra stack element consumed by OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY must be the empty byte array (the result of OP_0). Anything else makes the script evaluate to false.


Block validity

To introduce these new rules in the network, we add both v3 blocks and v3 transactions. v2 is skipped for transactions to keep the version numbers between transaction and block rules in sync. v2 transactions are treated identically to v1 transactions. The same mechanism as in BIP 0034 is used to introduce v3 blocks. When 75% of the past 1000 blocks are v3, a new consensus rule is activated:

- All transactions in v3 blocks are required to follow rules #1-#2.
- v3 (and higher) transactions in v3 blocks are required to follow rules #3-#7 as well.

When 95% of the past 1000 blocks are v3 or higher, v2 blocks become invalid entirely. Note however that v1 (and v2) transactions remain valid forever.


References

Below is a summary of the effects on signatures, their encoding and data pushes.

Low S values in signatures

The value S in signatures must be between 0x1 and 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0 (inclusive). If S is too high, simply replace it by S' = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 - S.

Signatures produced by the OpenSSL library are not guaranteed to be consistent with this constraint. Version 0.9.3 of the reference client provides an example [ http://github.com/bitcoin/bitcoin/blob/v0.9.3/src/key.cpp#L202-L227 ] for detection and correction.

The constraints on the value R are unchanged w.r.t. ECDSA, and values can be between 0x1 and 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364140 (inclusive).


DER encoding

For reference, here is how to encode signatures correctly in DER format.

0x30 [total-length] 0x02 [R-length] [R] 0x02 [S-length] [S] [sighash-type]

- total-length: 1-byte length descriptor of everything that follows, excluding the sighash byte.
- R-length: 1-byte length descriptor of the R value that follows.
- R: arbitrary-length big-endian encoded R value. It cannot start with any 0x00 bytes, unless the first byte that follows is 0x80 or higher, in which case a single 0x00 is required.
- S-length: 1-byte length descriptor of the S value that follows.
- S: arbitrary-length big-endian encoded S value. The same rules apply as for R.
- sighash-type: 1-byte hashtype flag (only 0x01, 0x02, 0x03, 0x81, 0x82 and 0x83 are allowed).

This is already enforced by the reference client as of version 0.8.0 (only as relay policy, not as a consensus rule).
This rule, combined with the low S requirement above, results in S-length being at most 32 (and R-length at most 33), and the total signature size being at most 72 bytes (and on average 71.494 bytes).


Push operators

- Pushing an empty byte sequence must use OP_0.
- Pushing a 1-byte sequence of byte 0x01 through 0x10 must use OP_n.
- Pushing the byte 0x81 must use OP_1NEGATE.
- Pushing any other byte sequence up to 75 bytes must use the normal data push (opcode byte n, with n the number of bytes, followed n bytes of data being pushed).
- Pushing 76 to 255 bytes must use OP_PUSHDATA1.
- Pushing 256 to 520 bytes must use OP_PUSHDATA2.
- OP_PUSHDATA4 can never be used, as pushes over 520 bytes are not allowed, and those below can be done using other operators.
- Any other operation is not considered to be a push.


Numbers

The native data type of stack elements is byte arrays, but some operations interpret arguments as integers. The used encoding is little endian with an explicit sign bit (the highest bit of the last byte). The shortest encodings for numbers are (with the range boundaries encodings given in hex between ()).

0: OP_0; (00)

1..16: OP_1..OP_16; (51)..(60)

-1: OP_1NEGATE; (79)

-127..-2 and 17..127: normal 1-byte data push; (01 FF)..(01 82) and (01 11)..(01 7F)

-32767..-128 and 128..32767: normal 2-byte data push; (02 FF FF)..(02 80 80) and (02 80 00)..(02 FF 7F)

-8388607..-32768 and 32768..8388607: normal 3-byte data push; (03 FF FF FF)..(03 00 80 80) and (03 00 80 00)..(03 FF FF 7F)

-2147483647..-8388608 and 8388608..2147483647: normal 4-byte data push; (04 FF FF FF FF)..(04 00 00 80 80) and (04 00 00 80 00)..(04 FF FF FF 7F)

Any other numbers cannot be encoded.

In particular, note that zero could be encoded as (01 80) (negative zero) if using the non-shortest form is allowed.


Compatibility

- Relay of transactions
A new node software version is released which makes v3 transactions standard, and relays them when their scriptSigs satisfy the above rules. Relaying of v1 transactions is unaffected. A v1 transaction spending an output created by a v3 transaction is also unaffected.

- Wallet updates
As v3 transactions are non-standard currently, it is not possible to start creating them immediately. Software can be checked to confirm to the new rules of course, but using v3 should only start when a significant part of the network's nodes has upgraded to compatible code. Its intended meaning is "I want this transaction protected from malleability", and remains a choice of the wallet software.

Pieter Wuille is one of the main advocates of the Segregated Witness project, so I don't trust him. I will use the information above as a starting point, but before using it for anything I'll search for confirmation of these items from sources that I trust more.



Let's take_notes / think / rewrite.


I don't know to what degree these proposed changes have been implemented by those who run nodes on the Bitcoin network. I do know that at least blockchain.info has decided to reject transaction signatures with high S values.


Transaction Malleability: A third party can receive a broadcast transaction, alter it, and rebroadcast. Any alteration to the signed section of the transaction can be mechanically detected (the transaction signature(s) will be invalid) and rejected. However, a signature itself, and the scriptSig that contains it, is not signed. Alterations to the signature and/or the scriptSig can be harder to detect and reject.

Examples of possible alterations to the signature:
- Signatures may not be encoded in strict DER format.
- Changing its S value from high to low or vice versa. In the ECDSA cryptosystem, a high S value is mathematically identical to the corresponding low S value. Changing the S value does not affect the validity of the signature, but results in a transaction with a different byte sequence.

Examples of possible alterations to the scriptSig:
- Changing an opcode to a different opcode (or sequence of opcodes) that performs the same overall function. This change results in a valid transaction with a different byte sequence.
- Adding leading zero bytes to an input value in the scriptSig (e.g. the public key). This does not change the value but does change the transaction's byte sequence.

Why does Transaction Malleability matter?
- Nodes store unmined transactions in their memory pools and transmit them to other nodes. This carries costs in storage and processing. If an attacker can alter many transactions and rebroadcast them, and the altered versions cannot be easily detected and rejected, this imposes additional running costs on each node. If this attack is performed on a large enough scale, the speed of transmission of new transactions through the Bitcoin network may diminish considerably.
- From some reading, it appears that the transaction identifier (txid) is created by hashing the transaction twice with the SHA256 algorithm. Altered versions of the transaction will have different txids. If an altered version of the transaction is mined, the desired transfer will still take place, but if the original sender and receiver are using the wrong txid to track the status of the transaction (whether manually or with software), they won't detect that the transaction has been successfully mined. In order to confirm the transfer, they will have to check the balances of the various addresses involved in the transaction. This can make tracking the status of transactions (for e.g. bookkeeping) more difficult and time-consuming.
- It is possible to create and broadcast a transaction that spends the outputs of another transaction that has not yet been mined. Transactions include the txid of each of their predecessors. If an altered version of the transaction is mined, any later transactions that tried to spend its outputs will now be invalid and will never be mined.


Focusing on ECDSA S values, here are the key points:
- An ECDSA signature includes an S value.
- Converting the S value to its negative (modulo the curve order) does not change the mathematical validity of the signature.
- It's possible to choose to only consider low S values to be acceptable. The maximum value is then the curve order divided by 2. This removes one avenue of transaction malleability.
- More specifically, the domain of low S values is:
The range of values between 0x1 and 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0 (inclusive).
- If an ECDSA implementation produces a signature with a high S value, this high S value can be converted to a low S value by the following operation:
S' = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 - S
-- Note: From earlier research, I know that 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 is n, where n is the order of the base point G of the elliptic curve secp256k1.
- ECDSA signatures also contain another value called R, and that its domain is the range of values between 0x1 and 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364140 (inclusive).
-- Note: The upper limit value is n-1.
- In DER format, R and S are stored in big-endian form.


I'll investigate the accuracy of the upper limit value of the low S value domain.




x2 is my calculated value for n/2. y is the value for n/2 from BIP 62 above. They are equal.

n_int is odd. n/2 is therefore not a whole integer. Python's integer division will round down (floor) the result if the result is not an integer.

I will take floor(n/2) = 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0 as the maximum permissible low S value.


Subtracting floor(n/2) from n, where n is odd, will result in floor(n/2)+1. I think that high S values probably lie in the inclusive interval [floor(n/2)+1, n], although (by similarity to the domain of R) perhaps the maximum permissible high S value is n-1, rather than n.

Hm. A low_S high_S value pair is related by n = low_S + high_S. If high_S == n, then low_S == 0, which is not within the permitted range of low_S values. So I deduce that the maximum permissible value of high_S is therefore n-1.




Before I write or modify any code, I would like to have confirmation from another source about the low and high S values, their domains of validity, and their mathematical equivalence.


I will consult the document x9_62_draft_ecdsa.pdf, which I stored as an asset of my earlier article Generating a standard Bitcoin address.

Document details:
Title: Working Draft, American National Standard, X9.62-1998, Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)
Author: Accredited Standards Committee X9, American Bankers Association
Date: September 20, 1998
It is referenced in the Python ECDSA library.

Browse to this earlier article and download x9_62_draft_ecdsa.pdf.





In x9_62_draft_ecdsa.pdf, on pages 16-17, I find section 5.3 (Signature Generation):

5.3 Signature Generation

This section describes the ECDSA signature generation process. The signature generation process consists of:

1) Message digesting.
2) Elliptic curve computations.
3) Modular computations.

The inputs to the signature process are:

1) The message, M, of an arbitrary length, which is represented by a bit string.
2) A valid set of elliptic curve domain parameters.
3) An elliptic curve private key, d, associated with the elliptic curve domain parameters.

The output of the signature process are two integers r and s (the digital signature), where 1 <= r <= n-1, 1 <= s <= n-1.


5.3.1 Message Digesting

Compute the hash value e = H(M) using the hash function SHA-1 as specified in ANSI X9.30 Part 2 [4]. e is represented as an integer with a length of 160 bits.


5.3.2 Elliptic Curve Computations

1) Select a statistically unique and unpredictable integer k in the interval [1,n-1].

It is acceptable to use a random or pseudorandom number. If a pseudorandom number is used, it shall be generated using one of the procedures of Annex A.4 or in an ANSI X9 approved standard. If a pseudorandom generation method is used, the seed values used in the generation of k may either be determined by internal means, be supplied by the caller, or both - this is an implementation choice. In all cases, the seed values have the same security requirements as the private key value. That is, they must be protected from unauthorized disclosure and be unpredictable.

If the implementation allows a seed supplied by the caller, then the physical security of the device is of utmost importance. This is because if an adversary gained access to the signature generation device and were able to generate a signature with a seed of its choice for the per-message secret k, then the adversary could easily recover the private key.

2) Compute the elliptic curve point (x_1, y_1) = k*G. (See Annex D.3.2.)


5.3.3 Modular Computations

1) Convert the field element x_1 to an integer x_macron_1, as described in Section 4.3.5.
2) Set r = x_macron_1 mod n.
3) If r = 0, then go to step 1 of Section 5.3.2.
4) Compute s = k^-1 (e + d*r) mod n. (See Annex D.1.2. for one method to compute k^-1 mod n.)
5) If s = 0, then go to step 1 of Section 5.3.2.


5.3.4 The Signature

The signature for M shall be the two integers, r and s, as computed in Section 5.3.3.

NOTES:
1) In step 3 of Section 5.3.3, the probability that r = 0 is approximately 1/n.
2) In step 5 of Section 5.3.3, the probability that s = 0 is approximately 1/n.
3) As an optional security check (to guard against malicious or non-malicious errors in the signature generation process), the signer may verify that (r, s) is indeed a valid signature for message M using the signature verification process described in Section 5.4.

Key points:

- The ECDSA signature is composed of two numbers, r and s, that both lie in the inclusive interval [1, n-1], where n is the curve order.

- The pieces needed to create the signature are:
-- The message M to be signed. In my case, the double SHA256 hash digest of the transaction-in-signable-form.
-- A valid set of parameters describing an elliptic curve. In my case, this is the curve secp256k1.
-- The elliptic curve private key d. In my case, this is the private key of the Bitcoin address.
-- A integer k chosen randomly from within the interval [1, n-1]. I assume this is an inclusive interval, as square brackets usually mean "inclusive". A quick check in section 2.2 (Symbols and Notation) confirms this. In my case, some reading of the Python ECDSA implementation indicates that the sign_digest() method stack eventually uses as its entropy source.
--- Note: The SigningKey class is in keys.py. The SigningKey class method sign_digest() calls the SigningKey class method sign_number(), which calls the function randrange(order, entropy) in order to generate a random k value if k is not None. The function randrange() is imported from util.py. If entropy is None, then randrange() sets entropy = os.urandom.

- "If a pseudorandom generation method is used, the seed values used in the generation of k may either be determined by internal means, be supplied by the caller, or both - this is an implementation choice. In all cases, the seed values have the same security requirements as the private key value. That is, they must be protected from unauthorized disclosure and be unpredictable."
-- Note: This is confirmation that the random number k (or a seed used to generate k values via a pseudo-random algorithm) is of the same importance as the private key.

- "If the implementation allows a seed supplied by the caller, then the physical security of the device is of utmost importance. This is because if an adversary gained access to the signature generation device and were able to generate a signature with a seed of its choice for the per-message secret k, then the adversary could easily recover the private key."
-- Note: k is "per-message" i.e. it should be used for only one message.
-- Note: If an adversary knows k and the resulting signature, and presumably the message M and the elliptic curve parameters, it is able to calculate the private key.

- When the signature has been calculated, r and/or s might be 0. In this case, the signature should be rejected and recalculated using a different value of k.

- k is used in the calculation of s.

- k is used in the calculation of r, because x_macron_1 is derived from x_1, which is derived from k*G.



I've skim-read the whole document. Nothing explicit about low and high S values.


Hm. It might not be mentioned explicitly. Let's think about it. A low-S value (between 1 and floor(n/2)) should produce the same mathematical result when the signature is verified as would the corresponding high-S value (between floor(n/2)+1 and n). A low_S high_S value pair is related by n = low_S + high_S.



Let's look at the signature verification algorithms, paying particular attention to the places where S is used.


In x9_62_draft_ecdsa.pdf, on pages 17-18, I find section 5.4 (Signature Verification):

5.4 Signature Verification

This section describes the ECDSA signature verification process.

The signature verification process consists of:

1) Message digesting.
2) Modular computations.
3) Elliptic curve computations.
4) Signature checking.

The input to the signature verification process is:

1) The received message, M', represented as a bit string.
2) The received signature for M', represented as the two integers, r' and s'.
3) A valid set of elliptic curve domain parameters.
4) A valid public key, Q, associated with the elliptic curve domain parameters.

The output of the signature verification process is an indication of signature verification success or failure.


5.4.1 Message Digesting

Compute the hash value e' = H(M') using the hash function SHA-1 as specified in ANSI X9.30 Part 2 [4]. e' is represented as an integer with a length of 160 bits.


5.4.2 Modular Computations

1) If r' is not an integer in the interval [1, n-1], then reject the signature.
2) If s' is not an integer in the interval [1, n-1], then reject the signature.
3) Compute c = (s')^-1 mod n. (See Annex D.1.2.)
4) Compute u_1 = e'*c mod n and u_2 = r'*c mod n.


5.4.3 Elliptic Curve Computations

1) Compute the elliptic curve point (x_1, y_1) = u_1*G + u_2*Q (see Annex D.3.2). (If u_1*G + u_2*Q is the point at infinity, then reject the signature.)


5.4.4 Signature Checking

1) Convert the field element x_1 to an integer x_macron_1, as described in Section 4.3.5.

2) Compute v = x_macron_1 mod n.

3) If r' = v, then the signature is verified, and the verifier has a high level of confidence that the received message was sent by the party holding the secret key d corresponding to Q. If r' does not equal v, then the message may have been modified, the message may have been incorrectly signed by the signatory, or the message may have been signed by an impostor. The message shall be considered invalid.

Key points:
- The signature is valid if r' = v.
- The calculation of v depends on x_macron_1, which depends on x_1, which depends on u_1 and u_2, which both depend on c.
- c = (s')^-1 mod n


Hm.

Let's define s_l and s_h as a low-S value and high-S value pair, related by the equation n = s_l + s_h, where n is the curve order.

Now, if the signature is to be valid when either s_l or s_h is used, then v = x_macron_1 mod n must produce the same value of v in both cases.

However, I'm not sure that it follows that c = (s')^-1 mod n should produce the same result for both s_l and s_h. I recall that modular arithmetic can be strange, and perhaps the interplay of equations follows two possible paths, one for s_l and one for s_h, which both end in the same v value.



Let's have a look at Annex D.1.2.

Table of Contents, on page iv, shows that Annex D.1.2 (Inversion in a Finite Field) is on page 65.


In x9_62_draft_ecdsa.pdf, on page 65, I find Annex D.1.2 (Inversion in a Finite Field):

D.1.2 Inversion in a Finite Field

If g != 0 is an element of the field F_q, then the inverse g^-1 is the field element c such that g*c = 1. The inverse can be found efficiently by exponentiation since c = g^(q-2). Note that if q is prime and g is an integer satisfying 1 <= g <= q-1, then g^-1 is the integer c, 1 <= c <= q-1, such that g*c triple_bar 1 (mod q). The algorithm is used in Sections 5.3.3 and 5.4.2.

Input: A field F_q, and a non-zero element g element_of F_q.

Output: The inverse g^-1.
1) Compute c = g^(q-2) (see Annex D.1.1).
2) Output c.

An even more efficient method is the extended Euclidean Algorithm [22, p. 325].

Hm.

So c = (s')^-1 mod n is the "modular inverse" of s'.

s' * (modular inverse of s) triple_bar 1 mod n, where triple_bar means "is congruent to".


I don't know if s_l and s_h have the same modular inverse. I suspect that they don't.



In x9_62_draft_ecdsa.pdf, on page 4, I find this excerpt in section 2.2 (Symbols and Notation):

x mod n
The unique remainder r, 0 <= r <= n-1, when integer x is divided by n. For example, 23 mod 7 = 2.

x triple_bar y (mod n)
x is congruent to y modulo n. That is, (x mod n) = (y mod n).

x^-1 mod n
Definition: If gcd(x, n) = 1, then x^-1 mod n is the unique integer y, 1 <= y <= n-1, such that x*y triple_bar 1 (mod n).

Proving that the two ECDSA digital signatures
1) (R, S)
2) (R, S') where S' = n - S
are mathematically equivalent (or even understanding a proof done by someone else) is beyond my current capabilities. I would have to study modular arithmetic for a while.


I can however look for some confirmation from additional sources that:
1) A low-S value lies in the inclusive interval [1, floor(n/2)]. A high-S value lies in the inclusive interval [floor(n/2)+1, n-1].
2) (R, S) is mathematically equivalent to (R, S'), where S' = n - S, where n is the curve order and S can be either a low-S value or a high-S value.
3) A notable proportion of nodes on the main Bitcoin network have decided to accept only low-S values in transaction signatures.
4) If an ECDSA implementation produces a transaction signature with a high-S value, the high-S-value can be replaced with its corresponding low-S value, calculated using S' = n - S.
5) This replacement is an acceptable simplification of the transaction format that:
5a) removes a aspect of transaction malleability.
5b) is unlikely to decrease the security of transactions.
5c) does not break compatibility with nodes that accept high-S-value transactions.



I'll look in the logs of the #trilema chat channel.


Browse to:
btcbase.org/log

Note: This log site is maintained by phf.


Search for various terms e.g. "malleability", "low-s", "bip 62", "bip62", "ecdsa".


I'll include relevant excerpts from the log here.


btcbase.org/log/2015-10-15#1299964




btcbase.org/log/2015-10-15#1300022




btcbase.org/log/2015-10-16#1300058
to
btcbase.org/log/2015-10-16#1300080




btcbase.org/log/2017-07-25#1689882
to
btcbase.org/log/2017-07-25#1689884





Key points so far:
- Enforcing low-s encoding of ecdsa signatures is probably unavoidable, presumably just to remove an avenue of transaction format ambiguity.
- The suggestions in BIP 62 are acceptable.
- Changing a high-S value to the corresponding low-S value is a small change that occurs after the signature has been created.
- It's not clear why the high-S-changed-to-low-S signature is still mathematically valid.
- mod6 has written a patch that changes high-S values to low-S values.
-- Note: This patch will hopefully confirm the low-S and high-S domains and the equation for calculating a low-S value from high-S value.




btcbase.org/log/2016-06-24#1489992
to
btcbase.org/log/2016-06-24#1490052




Key points so far:
- A signature that includes a high-S value is a legitimate signature.
- The high-S / low-S ambiguity is built in at the protocol level.
-- This means that there are two mathematically valid outputs of the signing process, even if, when run, it only produces one of them.
- The Bitcoin miners accept high-S transactions but change them to low-S before attempting to mine them.
-- Note: Mircea Popescu runs his own node(s), and can therefore broadcast a high-S transaction to the Bitcoin network. Earlier, I attempted to upload a high-S transaction to blockchain.info's system, which rejected it. If I were to run my own node and broadcast my high-S transaction from it, the miners would probably accept it, change it, and mine it, because it contains a transaction fee.
- Mircea Popescu: "when there's ambiguity in design, this is to be exposed to user."
-- From mod6's comment at the beginning, his patch(es) presumably follow this plan and allow the user to choose whether to change high-S to low-S when making a transaction.
-- I think this is the right approach.



btcbase.org/log/2016-01-31#1391888
to
btcbase.org/log/2016-01-31#1391916




Key points so far:
- Choosing low-S values is a convention. It was technically possible for the network to have converged on using only high-S in transaction signatures.
- Blocks containing high-S transactions, once mined, are unlikely to be rejected by nodes in the Bitcoin network.





btcbase.org/log/2016-01-14#1369763
to
btcbase.org/log/2016-01-14#1369793




Key points so far:
- There was a 36-hour fork in the blockchain. It seems that:
- 1) Miners voted for only low-S transactions.
- 2) New code was implemented that caused Bitcoin nodes to reject new blocks with high-S transactions.
- 3) At least some of the miners did not immediately implement this change. One of them mined a block that included a high-S transaction.
- 4) The network split into two sections, one that accepted this block and one that did not. This is a "network fork", where two chains emerge. If there are miners that are using different rulesets for accepting new blocks, both chains will continue. If all miners are agreed on one ruleset, but some relay/storage nodes are using a different ruleset, then the relay/storage nodes will halt at a particular block, while the mining chain continues.
- 5) Two possible fork scenarios and their resolutions:
- 5a) There was one mining chain. The nodes that were rejecting new blocks with high-S transactions switched back to accepting them.
- 5b) There were two mining chains. The miners that were mining both low-S and high-S transactions switched to changing all high-S transactions to low-S transactions. They then began mining on the other chain.
- A soft fork is a narrowing of the protocol. It is a convention for the use of an item, but does not actually change the overall behaviour of the item.
- A hard fork changes the overall behaviour of an item in some way.
- Miners choosing to mine only low-S transactions is a soft fork.


After rereading the excerpt above, I think that:
- Scenario (5a) occurred, but afterwards miners switched to changing all high-S transactions to low-S transactions, in order to avoid future syncronisation problems.
-- Note: If a miner does not make this switch, his mempool management is more difficult. When a new block arrives with a high-S-changed-to-low-S transaction, any unconfirmed transactions that spend the outputs of this transaction will be invalid, since they will include the original txid of the changed transaction. They will have to be pruned from the mempool, because if the miner produces a block containing one of them, the entire block will be invalid. Ideally, this pruning should occur as soon as possible, so as to have maximum available time for mining. By switching to change-high-S-to-low-S, this pruning can occur before the arrival of a new block.
- Mircea Popescu points out that miners may be changing all high-S transactions to low-S transactions, but strategically they are obliged to not reject blocks containing high-S transactions, lest someone eventually mine such a block, causing a fork in which two mining chains emerge. Miners can't easily know which fork would win, and mining on the eventual loser chain means that all mining rewards from that chain would be lost, so they are highly incentivised to never change the new block acceptance ruleset, as they can't be sure that the majority of other miners would also make the exact same change. It's a prisoner's dilemma situation.
-- Note: If a miner cartel exists that controls 51% of the hash power and can effectively coordinate its internal activity, then it could perhaps enforce a change in the block acceptance ruleset.
- Any one who maintains a Bitcoin node is also obliged to stick to the same new block acceptance ruleset, for the same game-theoretic reason.




Let's look at mod6's patch.


In a previous project, Compiling bitcoind (trb 0.5.4) on Debian 7.11, at the end of the article, I stored various patches as assets. In that list of patches, I find:
mod6_der_high_low_s.vpatch


Browse to previous project and download the patch.


I'll include it here:






I don't know C++ very well. But, on reading the code, I note this specific section:




I can see that:
- and are control flags that allow the user to enforce all-high-S or all-low-S for transactions. These are created in an earlier section of the patch.
- The order is taken from the EC (elliptic curve) group.
- In , it looks as though the right shift operation divides by 2 and saves the result in .
-- Note: A right shift operation is effectively the same as floor(n/2).
- The signature is compared to .


Let's check how BN_cmp works.

Google "BN_cmp".

First result:
www.openssl.org/docs/man1.0.2/crypto/BN_cmp.html

Excerpts:

NAME

BN_cmp, BN_ucmp, BN_is_zero, BN_is_one, BN_is_word, BN_is_odd - BIGNUM comparison and test functions

[...]

DESCRIPTION

BN_cmp() compares the numbers a and b.

[...]

RETURN VALUES

BN_cmp() returns -1 if a < b, 0 if a == b and 1 if a > b.

Looks like BN_cmp is part of openssl and BN == "BigNum".


Key point:
- BN_cmp() returns -1 if a < b, 0 if a == b and 1 if a > b.


What will the trb Bitcoin code + mod6's patch will do if the S value is exactly equal to floor( (curve order n) / 2)?

Probably it won't make any change (whatever control flag is set), so it looks like S == floor(n/2) is treated as being both low-S and high-S.

x9_62_draft_ecdsa.pdf: The ECDSA signature is composed of two numbers, r and s, that both lie in the inclusive interval [1, n-1], where n is the curve order.
- Note: Since, when n is odd, n - floor(n/2) = floor(n/2)+1, the high-S domain is the inclusive interval [floor(n/2)+1, n-1].

Mod6's code might cause a problem if the user is trying to enforce high-S and the S value is floor(n/2), in which case it should be changed to floor(n/2)+1, but won't be changed. This is a rather unlikely event.

I think that this could be fixed by changing this line:

to:


If the user is trying to enforce low-S, and the S value is floor(n/2), mod6's code won't change it (the BN_cmp() operation will return 0), which is fine.

For current use, while miners are changing high-S to low-S, and a user will probably only want to enforce low-S, this code will solve the problem.









Let's restate here the items that I have been seeking to confirm:

1) A low-S value lies in the inclusive interval [1, floor(n/2)]. A high-S value lies in the inclusive interval [floor(n/2)+1, n-1].
2) (R, S) is mathematically equivalent to (R, S'), where S' = n - S, where n is the curve order and S can be either a low-S value or a high-S value.
3) A notable proportion of nodes on the main Bitcoin network have decided to accept only low-S values in transaction signatures.
4) If an ECDSA implementation produces a transaction signature with a high-S value, the high-S-value can be replaced with its corresponding low-S value, calculated using S' = n - S.
5) This replacement is an acceptable simplification of the transaction format that:
5a) removes a aspect of transaction malleability.
5b) is unlikely to decrease the security of transactions.
5c) does not break compatibility with nodes that accept high-S-value transactions.


I trust opinions from Mircea Popescu, asciilifeform, and mod6 on this matter. I'll summarise the relevant key points from reading their discussions (and mod6's patch), and see if these sufficiently confirm the items listed above.


Key points:
- Note: The curve order n is 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141.
- Signatures contain S values.
- S values can be low or high.
- A high-S value can be changed to a low-S value. This change occurs after the signature has been created. It is a small change and won't affect transaction security.
- BIP 62 includes several points about S values and changing high-S values to low-S values. BIP 62 is broadly acceptable, even though it was written by Pieter Wuille.
- BIP 62: Low-S values lie in the inclusive interval [1, x], where x is the curve order divided by 2 and is equal to 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0.
-- Note: I have calculated that x == floor(n/2).
- To convert a high-S value to a low-S value, use the equation low_S_value = n - high_S_value.
- x9_62_draft_ecdsa.pdf: The ECDSA signature is composed of two numbers, r and s, that both lie in the inclusive interval [1, n-1], where n is the curve order.
-- Note: Since, when n is odd, n - floor(n/2) = floor(n/2)+1, the high-S domain is the inclusive interval [floor(n/2)+1, n-1].
- A signature that includes a high-S value is a legitimate signature.
- The high-S / low-S ambiguity is built in at the protocol level. There are two mathematically valid outputs of the signing process, even if, when run once, it only produces one of them.
- It's not clear why a high-S-changed-to-low-S signature is still mathematically valid.
- The Bitcoin miners accept high-S transactions but change them to low-S before attempting to mine them.
- Choosing low-S values is a convention. It was technically possible for the network to have converged on using only high-S in transaction signatures.
- Mircea Popescu: "when there's ambiguity in design, this is to be exposed to user.". A transaction-creation program should present the user with a choice to enforce low-S or high-S but not the obligation.
- A soft fork is a narrowing of the protocol. It is a convention for the use of an item, but does not actually change the overall behaviour of the item.
- A hard fork changes the overall behaviour of an item in some way.
- Miners choosing to mine only low-S transactions is a soft fork.
- Blocks containing high-S transactions, once mined, are unlikely to be rejected by nodes in the Bitcoin network. Making such a change is a hard fork, and miners are wary of implementing hard fork in their code for good game-theoretic reasons.




Good. I think I have confirmed the various points to my satisfaction.






Next: Sign the transaction again, using the Python ECDSA library in a slightly different way, so that I can:
- supply my own k value
- see the values of s and r before they are encoded in DER
- check if the S value is high, and, if it is, replace it with the corresponding low-S value.



In the Python ECDSA library, in keys.py, in the SigningKey class, I find these two methods:




Note that:
- sign_digest() calls sign_number().
- sign_digest() also uses string_to_number().
-- In keys.py, I find:

--- In util.py, I find


Plan:
- Proceed through the steps of sign_digest() manually and call sign_number() in order to sign the transaction.


New transaction-in-signable-form:



I've already appended the hash type to the transaction-in-signable-form ("01000000").

Steps from earlier:
- SHA256(SHA256(transaction-in-signable-form))
- Create a SigningKey object from the private key of the source Bitcoin address (that supplies its unspent output as the input to the new transaction).
- Use the sign_digest() method of the SigningKey to sign the double SHA256 hash digest of the transaction-in-signable-form. Use the sigencode argument to specify that the signature should be returned in DER encoding.
- Append hash_type (as a single byte) "01" to DER-encoded signature.
- Get the public key corresponding to the private key of the source Bitcoin address.
- Construct the scriptSig using the signature and the public key. I suspect that the utils.varstr() function adds a length var_int to the beginning of its input data.
- It's a good idea to call the transaction verification function at the end, as a sanity check.


Information from earlier about the source address private key:



The private key needs to be exactly 32 bytes long.

I'll use the hex form of the 32-byte private key and convert it to raw bytes.

Note that k must be in the inclusive interval [1, n-1].



Note: Some errors, mis-steps, and retries have not been included in the REPL output below.





The signature was already low-S. I didn't need to convert the S value from high-S to low-S. However, if it is necessary later, I now have a process in which this conversion step can be placed.



The double SHA256 hash digest of the transaction-in-signable-form is:


The DER-encoded signature of the double SHA256 hash digest (with hash type byte appended) is:

- this is 71 bytes long. 71 in hex is 47.


For legibility, I'll add spaces in between the hex bytes in the signature.





Signature:




I can now construct the scriptSig of the new transaction. I added the public key data (and its var_int length) earlier.

new scriptSig:



Now, I can take the new transaction (not in signable form) and insert this scriptSig, which will prove its validity.


Transaction format:




New transaction:





scriptSig:



scriptPubKey:




Convert the scriptSig into a byte sequence.



Need the script_length var_int for scriptSig.



The script_length var_int for scriptSig, in hex, is: 8a


Convert the scriptPubKey into a byte sequence.




Insert the scriptSig and scriptPubKey byte sequences into the transaction.


New transaction:





Convert the final form of the new transaction into a byte sequence.





New transaction:




Remove spaces:





Signed transaction:




Next: Broadcast new signed transaction and see if it is mined (or rejected).


Let's double-check the current fees before broadcasting.

Browse to:
bitcoinfees.earn.com
- For 0 satoshis/byte, estimated delay is 28-107 blocks or 180-1260 minutes.
- For 1-2 satoshis/byte, estimated delay is 2-7 blocks or 5-180 minutes.
- For 3-4 satoshis/byte, estimated delay is 2-7 blocks or 5-120 minutes.


Browse to:
blockchain.info/decode-tx
which leads to:
www.blockchain.com/en/btc/decode-tx

Paste in signed transaction and click "Submit Transaction".

Hm. The page simply reloads, wiping the transaction.


Odd.

Try again.

Same result.


Google "decode tx".


Second result:
live.blockcypher.com/btc/decodetx

Browse to this page.

Network is set to "Bitcoin".

Paste in signed transaction hex and click "Decode Transaction".

Result:




Hm. This application provides more information than blockchain.info/decode-tx did.


Transaction parsed successfully. Various values are as expected.

The size of the transaction is 223 bytes. I forgot to check for this earlier.

Let's double-check.



Good.

The fee is therefore 225/223 satoshis/byte, which is slightly more than 1 satoshi/byte.



The "hash" value for the signed transaction is:


Presumably, this is the txid for this new signed transaction, in big-endian format.


On
live.blockcypher.com/btc/decodetx
there is this text:
"Ready to broadcast? Click here to broadcast a raw transaction hex.",
in which "Click here" links to:
live.blockcypher.com/btc/pushtx/?t=None

Browse to:
live.blockcypher.com/btc/pushtx/?t=None

Network is set to "Bitcoin".


Paste in signed transaction hex and click "Broadcast Transaction".

Result:

New page loaded:
live.blockcypher.com/btc/tx/4bdd5f653d0100ea4735953e8e22e92321af9074926b3bd33c279c289f2d975a

Some of the information on the page:

Bitcoin Transaction
4bdd5f653d0100ea4735953e8e22e92321af9074926b3bd33c279c289f2d975a

AMOUNT TRANSACTED
0.00199775 BTC

FEES
0.00000225 BTC

CONFIRMATIONS
0/6

Confidence
83.12%

Miner Preference
Low

Size
223 bytes

Lock Time

Version
1

Relayed By:
184.73.119.227


1 Input Consumed

0.002 BTC from
1CTumCMjzBfccCJBTkHoPQmAwEqU9Uj2sQ


1 Output Created

0.00199775 BTC to
12RbVkKwHcwHbMZmnSVAyR4g88ZChpQD6f

Looks like the transaction was successfully broadcast. Or rather, at least one system somewhere was happy to accept it for broadcast.




For 1-2 satoshis/byte, estimated delay was 2-7 blocks or 5-180 minutes.


It's been a few minutes.

Refresh the transaction description page.

1 confirmation.


Set timer for 1 hour.

Timer has finished.

4 confirmations.

half an hour later:
6+ confirmations


Browse to blockchain.info

Paste in txid


8 confirmations.


Good.











Next: Create and sign another transaction that moves the bitcoin from the target address to my LocalBitcoins receiving address.


I need the following information in order to create this second transaction:
- previous_output_hash (txid of previous transaction, but in little-endian form)
- previous_output_index (implicit index of unspent output within list of outputs in previous transaction - this unspent output will be used as an input for the new transaction)
- value (value in single unspent output in previous transaction, but after a transaction fee has been subtracted)

I also need:
- The scriptPubKey for my LocalBitcoins receiving address. I will need to decode the address and perhaps choose different opcodes for sending to a multi-signature address.
- The public key of the target address. This will go into the scriptSig.
- The private key in 32-byte hex for the target address. This will used to sign the transaction.



The txid of the previous transaction, in big-endian form, is:



I'll write a function to automate switching hex data between little-endian and big-endian.









previous_output_hash (little-endian):




For legibility, I'll separate each hex byte with a space.



previous_output_hash (little-endian):






The previous_output_index is 0, because there is only 1 unspent output in my first transaction, and the unspent outputs are implicitly 0-indexed.


value will be the value in the unspent output minus a transaction fee.

The value in the unspent output is 199775 satoshis.

Assuming a transaction size of 225 bytes, and a fee of 1 satoshi/byte, the transaction fee is 225 satoshis.

The new value will be 199775 - 225 = 199550 satoshis.

The value needs to be 8 bytes (little-endian).




Result: 30b7e
Add a 0 at the front to make this hex value to be of even length (i.e. full bytes).
030b7e
03 0b 7e

Add 5 leading zero bytes to make this value 8 bytes long.
00 00 00 00 00 03 0b 7e

Now reverse it to make it little-endian.
7e 0b 03 00 00 00 00 00


So, value = 7e 0b 03 00 00 00 00 00







Information from earlier about the target address:




32-byte private_key_hex:


public_key_hex:




Last ingredient:
scriptPubKey of my LocalBitcoins receiving address.

I don't know how multi-signature addresses work.

From some reading, this won't actually be a "scriptPubKey" i.e. Pay-To-Public-Key-Hash (P2PKH).

It will be a "scriptHash" i.e. Pay to Script Hash (P2SH).


My LocalBitcoins receiving address is currently:
36CQfj2Yt54sZttJYTb5ywuS7YGEQLfzCE




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

This page has a pop-up:
"BETA: This documentation has not been extensively reviewed by Bitcoin experts and so likely contains numerous errors."

P2SH Scripts

[...]

pay-to-script-hash (P2SH) transactions were created in 2012 to let a spender create a pubkey script containing a hash of a second script, the redeem script.

The basic P2SH workflow [...] looks almost identical to the P2PKH workflow. Bob creates a redeem script with whatever script he wants, hashes the redeem script, and provides the redeem script hash to Alice. Alice creates a P2SH-style output containing Bob's redeem script hash.

[...]

When Bob wants to spend the output, he provides his signature along with the full (serialized) redeem script in the signature script. The peer-to-peer network ensures the full redeem script hashes to the same value as the script hash Alice put in her output; it then processes the redeem script exactly as it would if it were the primary pubkey script, letting Bob spend the output if the redeem script does not return false.

[...]

The hash of the redeem script has the same properties as a pubkey hash - so it can be transformed into the standard Bitcoin address format with only one small change to differentiate it from a standard address. This makes collecting a P2SH-style address as simple as collecting a P2PKH-style address. The hash also obfuscates any public keys in the redeem script, so P2SH scripts are as secure as P2PKH pubkey hashes.


Standard Transactions


After the discovery of several dangerous bugs in early versions of Bitcoin, a test was added which only accepted transactions from the network if their pubkey scripts and signature scripts matched a small set of believed-to-be-safe templates, and if the rest of the transaction didn't violate another small set of rules enforcing good network behavior. This is the IsStandard() test, and transactions which pass it are called standard transactions.

Non-standard transactions - those that fail the test - may be accepted by nodes not using the default Bitcoin Core settings. If they are included in blocks, they will also avoid the IsStandard test and be processed.

[...]

The most common use of P2SH is the standard multisig pubkey script.

[...]

Pubkey script: OP_HASH160 <Hash160(redeemScript)> OP_EQUAL
Signature script: <sig> [sig] [sig...] <redeemScript>

This script combination looks perfectly fine to old nodes as long as the script hash matches the redeem script. However, after the soft fork is activated, new nodes will perform a further verification for the redeem script. They will extract the redeem script from the signature script, decode it, and execute it with the remaining stack items(<sig> [sig] [sig..]part). Therefore, to redeem a P2SH transaction, the spender must provide the valid signature or answer in addition to the correct redeem script.

Key points:
- To send to a P2SH multi-signature address, I don't need to worry about how to spend from it. I just need to construct a script from the P2SH address and use it in the transaction output.
-- The script is: OP_HASH160 [Hash160(redeemScript)] OP_EQUAL
- P2SH multi-signature works in this way: A multi-signature redeemScript will be included in the scriptSig of a new transaction that spends from a P2SH multi-signature address. The miners will: a) confirm that the redeemScript hashes to the value in the P2SH multi-signature address, and b) execute the script and confirm that the requisite multiple signatures are included in the new scriptSig and are valid.
- Old nodes (running the original ruleset) will only confirm that the redeemScript hashes to the value in the P2SH multi-signature address. I think that this happens because the redeemScript is occupying the position of a public key in a standard P2PKH scriptSig, so they treat it as a public key. From the perspective of old nodes, the redeemScript will simply be a invalid public key for the supplied signature data in the rest of the scriptSig. They won't relay a transaction containing a payment to a P2SH multi-signature address, or mine it, but I think that they will accept blocks containing it. Notably, old nodes would also accept blocks containing later transactions that (now that the redeemScript is publicly known) spend from the P2SH multi-signature address but do not include valid signatures (because they wouldn't actually run and validate the redeemScript according to the new soft-fork ruleset).
- P2SH multi-signature is a soft fork, i.e. a narrowing of the original protocol, with something extra added on (the promise to only mine a transaction if the signatures in the scriptSig meet the conditions of the redeemScript). Essentially, P2SH multi-signature transactions are a convention that the miners promise to enforce.
-- Note: This is true of original P2PKH (Pay-to-Public-Key-Hash) signatures as well. They only have validity because miners promise to only mine transactions that have valid signatures.
--- Bitcoin values stored on the blockchain have a market value because this promise is kept.
--- Hm. A reversal of the soft fork could eventually occur, in which a majority of the miners stop enforcing the redeemScript conditions but continue to enforce the original P2PKH conditions. They could then mine transactions that transfer any bitcoin stored in P2SH multi-signature addresses to their own P2PKH addresses.
---- Why would they do this? Well, a rising Bitcoin price might eventually make it worthwhile to do so. This would be a reversal of a soft fork (a convention), not a hard fork (a fundamental change). A hard fork is dangerous for miners because it might make long-term holders, who are interested primarily in Bitcoin as a store of value, decide to leave the chain, collapsing the price and severely damaging the miners' investment in equipment etc. A soft fork is not as dangerous for miners. Notably, a reversal of a soft fork is also not as dangerous for miners - they simply stop enforcing some additional rules. The people who use only P2PKH addresses would not be threatened and would probably stay on the Bitcoin blockchain, rather than selling or switching to holding value on another blockchain. The market value of Bitcoin would probably remain high.


Note: I encountered this line of reasoning earlier in the #trilema chat channel logs, but about the Segregated Witness project, not about multi-signature addresses. As I thought through it here, I realised that the scenario was similar, and that the principle is that soft forks can always be reversed.

Note: Segregated Witness addresses, in the original ruleset, are "anyone can spend" addresses. Miners promise to enforce a soft-fork convention - they will store and analyse additional "witness" data containing the transaction signatures, and won't mine transactions that aren't valid according to this additional data. This project also specifies that a new additional merkle tree will be built to guarantee the integrity of the transaction signature data and that the additional final merkle root hash will be placed in the coinbase transaction in a new block.



Relevant excerpt from the #trilema logs:

btcbase.org/log/2017-08-11#1697111
to
btcbase.org/log/2017-08-11#1697118




Interesting additional point from the earlier excerpt:
- If non-standard transactions are included in blocks, they will also avoid the IsStandard() test.

Thought: The new ruleset for P2SH multi-signature may not be enforced during validation of transactions in new blocks received from the network. Miners might only be refusing to mine non-valid P2SH multi-signature transactions, but they might accept a block from another miner that had already mined some (i.e. they may not have bothered to implement code that would reject this block). Profitably reversing the soft-fork might not even require 51% consensus among miners.


Some reading suggests that there was an earlier multi-signature transaction type, in which the entire redemption script was stored in the address. P2SH multi-signature has replaced it in actual use - in this case only the hash of the redemption script is stored in the address.



Excerpts from:
github.com/bitcoin/bips/blob/master/bip-0016.mediawiki

BIP: 16
Layer: Consensus (soft fork)
Title: Pay to Script Hash
Author: Gavin Andresen <gavinandresen@gmail.com>
Comments-Summary: No comments yet.
Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0016
Status: Final
Type: Standards Track
Created: 2012-01-03


[...]


Abstract

This BIP describes a new "standard" transaction type for the Bitcoin scripting system, and defines additional validation rules that apply only to the new transactions.


Motivation

The purpose of pay-to-script-hash is to move the responsibility for supplying the conditions to redeem a transaction from the sender of the funds to the redeemer.

The benefit is allowing a sender to fund any arbitrary transaction, no matter how complicated, using a fixed-length 20-byte hash that is short enough to scan from a QR code or easily copied and pasted.


Specification

A new standard transaction type that is relayed and included in mined blocks is defined:

OP_HASH160 [20-byte-hash-value] OP_EQUAL

[20-byte-hash-value] shall be the push-20-bytes-onto-the-stack opcode (0x14) followed by exactly 20 bytes.


[...]

Backwards Compatibility

These transactions are non-standard to old implementations, which will (typically) not relay them or include them in blocks.

Old implementations will validate that the {serialize script}'s hash value matches when they validate blocks created by software that fully support this BIP, but will do no other validation.

Some notes:
- Status == Final. I assume that this BIP was fully implemented.
- "The purpose of pay-to-script-hash is to move the responsibility for supplying the conditions to redeem a transaction from the sender of the funds to the redeemer." I hadn't properly appreciated this motive before.
- Confirmation that old nodes won't relay these transactions or mine them.
- Confirmation that old nodes will verify the hash in the transaction if it is in a new block that they receive, but won't verify the signature.
- The script that I need to construct (after decoding the P2SH multi-signature address) is: OP_HASH160 PUSHDATA(20) [20-byte-hash-value] OP_EQUAL

20 in hex is 0x14.







Excerpts from:
github.com/bitcoin/bips/blob/master/bip-0013.mediawiki

BIP: 13
Layer: Applications
Title: Address Format for pay-to-script-hash
Author: Gavin Andresen <gavinandresen@gmail.com>
Comments-Summary: No comments yet.
Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0013
Status: Final
Type: Standards Track
Created: 2011-10-18


[...]


Abstract

This BIP describes a new type of Bitcoin address to support arbitrarily complex transactions. Complexity in this context is defined as what information is needed by the recipient to respend the received coins, in contrast to needing a single ECDSA private key as in current implementations of Bitcoin.

In essence, an address encoded under this proposal represents the encoded hash of a script, rather than the encoded hash of an ECDSA public key.


[...]


Specification

The new bitcoin address type is constructed in the same manner as existing bitcoin addresses (see Base58Check encoding):

base58-encode: [one-byte version][20-byte hash][4-byte checksum]

Version byte is 5 for a main-network address, 196 for a testnet address. The 20-byte hash is the hash of the script that will be used to redeem the coins. And the 4-byte checksum is the first four bytes of the double SHA256 hash of the version and hash.


[...]


The leading version bytes are chosen so that, after base58 encoding, the leading character is consistent: for the main network, byte 5 becomes the character '3'. For the testnet, byte 196 is encoded into '2'.


[...]

Backwards Compatibility

This proposal is not backwards compatible, but it fails gracefully-- if an older implementation is given one of these new bitcoin addresses, it will report the address as invalid and will refuse to create a transaction.


[...]


See Also

BIP 12: OP_EVAL, the original P2SH design
BIP 16: Pay to Script Hash (aka "/P2SH/")
BIP 17: OP_CHECKHASHVERIFY, another P2SH design

Some notes:
- Status == Final.
- "if an older implementation is given one of these new bitcoin addresses, it will report the address as invalid and will refuse to create a transaction." I didn't realise that old nodes wouldn't even create transaction that spend to P2SH multi-signature addresses, although, thinking about it, it makes sense. Old nodes will see the new address format as invalid.
- The first byte will always be 5.
-- Hm. In Satoshi's Base58 encoding, 0x00 bytes are '1', but 0x05 bytes are '6', not '3'.
--- Ah. The first byte is not exactly byte 0x05. It's really 0x05 with 24 following bytes (the 20-byte script hash and the 4-byte checksum), i.e. it has an positional value in base58 due to its position in the byte string.


Minimum value:
"05"+"00"*20 =
050000000000000000000000000000000000000000
- in base58check_encoding, this is:
31h1vYVSYuKP6AhS86fbRdMw9XHieotbST
- minimum value as a decimal integer:
7307508186654514591018424163581415098279662714880

Maximum value:
"05"+"FF"*20 =
05FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
- in base58check_encoding, this is:
3R2cuenjG5nFubqX9Wzuukdin2YfBbQ6Kw
- maximum value as a decimal integer:
8769009823985417509222108996297698117935595257855



Hm. So: A string of 21 bytes that starts with the '05' byte, once converted into base58check encoding (with a 4-byte checksum added by the encoding function), always starts with the base58 symbol '3'.


Note: Because the '05' byte is always added at the front of the script hash, a P2SH address will never start with a leading zero byte, so the count-leading-zeros section of the base58check algorithm will never have an effect on the address during conversion.



To get the above results, I wrote a short test script in Python that used parts of generate_bitcoin_address.py.


Here is the test script and an example of its use:













Next: Decode the P2SH address and extract the script hash.

I'll use the earlier script
get_public_key_hash_from_bitcoin_address.py
as a starting point.


[development occurs here]








Using the address for the minimum script hash value
31h1vYVSYuKP6AhS86fbRdMw9XHieotbST
produced the expected result for the script hash:



Using the address for the maximum script hash value
31h1vYVSYuKP6AhS86fbRdMw9XHieotbST
produced the expected result for the script hash:



Finally, I ran the script on my current LocalBitcoins receiving address
36CQfj2Yt54sZttJYTb5ywuS7YGEQLfzCE
and found that the script hash was:




I'll separate each hex byte with a space.









Next:
The output script that I need to construct (after decoding the P2SH multi-signature address) is: OP_HASH160 PUSHDATA(20) [20-byte-hash-value] OP_EQUAL

20 in hex is 0x14.

outputScript:





Next:
Create and sign a transaction that sends the bitcoin in the P2PKH target address to the P2SH multi-signature LocalBitcoins receiving address.



The P2SH outputScript will be placed where the P2PKH scriptPubKey normally goes.

"target address" is the previous target address, that I will now use as the source address of this second transaction. I'll still use "target address" as its label though. I'll use "LocalBitcoins address" to indicate the new target address. I'll call this second transaction "transaction 2".


Inputs:

1) previous_output_hash (little-endian):


2) previous_output_index: 0
- in 4 bytes (little-endian), this is: 00 00 00 00

3) value: 7e 0b 03 00 00 00 00 00
- 199550 satoshis (= 0.00199550 bitcoin)
- input address contains 199775 satoshis.
- implicit transaction fee = 225 satoshis (approximately 1 satoshi/byte)

4) outputScript:


5) 32-byte private_key_hex of target address:


6) public_key_hex of target address:



Separate each hex byte in the public key with a space.










Transaction format:





Transaction 2:




scriptSig:



outputScript:






Ok. Transaction 2 has been assembled.


Next:
Get the signable form of this transaction for the single input.


Algorithm for signing a standard transaction:





I need the scriptPubKey of the target address used in the first transaction. I can then substitute it for the scriptSig in this second transaction to make the transaction-in-signable-form.


Open
get_public_key_hash_from_bitcoin_address.py
and set the variable 'address' to contain the target address
12RbVkKwHcwHbMZmnSVAyR4g88ZChpQD6f





Separate each hex byte in the public key hash with a space.




Using the standard opcode sequence, I can construct the scriptPubKey for the target address:



Counting manually, its length in bytes is:
1 + 1 + 1 + 20 + 1 + 1 = 25

In hex, this length is: 19

scriptPubKey as a byte sequence:



Now, substitute this scriptPubKey from the previous transaction for the scriptSig of transaction 2. Also substitute its script_length.

No changes need to be made to any scriptSigs in other inputs, since for transaction 2 there is only one input.

Append a four-byte form of the SIGHASH_ALL hash_type to transaction 2. For hash type 1, SIGHASH_ALL, this is 0x01 00 00 00 (The value "1" in little-endian form).



Transaction-in-signable-form format:




Transaction-2-in-signable-form:




outputScript:




Compress the outputScript for the LocalBitcoins address into a single byte sequence, then place it into the transaction object.

outputScript:




Transaction-2-in-signable-form:







Compress transaction-2-in-signable-form into a single byte sequence.





Transaction-2-in-signable-form:




Remove spaces:





Transaction-2-in-signable-form:




Next: Sign transaction-2-in-signable-form.



I'll look at how I did this before for the first transaction.


Process for using the Python ECDSA library to sign a transaction-in-signable-form:

1) Calculate the hash digest SHA256(SHA256(transaction-in-signable-form)). Calculate the length in bytes of the hash digest.
- Note: The transaction-in-signable-form differs for each input.

2) Create a SigningKey object from the private-key-in-raw-bytes, specifying that the elliptic curve is secp256k1.

3) Check that the hash digest length is not greater than curve.baselen, where curve is secp256k1.

4) Generate a random value k in the inclusive interval [1, n-1].
- Note: n is the order of the base point G of the elliptic curve secp256k1. In hex, n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141. n is 32 bytes (256 bits) long.

5) Use the sign_number() method of the SigningKey object to sign the hash digest. Pass k as an argument for use in the signing process. Retrieve the resulting r and s values, which together constitute the ECDSA signature.
- Note: Every signature requires a new and unique value of k.

6) Check that the S-value in the signature is within the low-S domain [1, floor(n/2)]. If it is within the high-S domain [floor(n/2)+1, n-1], convert the high-S value to a low-S value by using the following equation: S_new = n - S.
- Note: Currently the Bitcoin network has converged on using low-S values in transaction signatures.
- Note: Square brackets [] signify inclusive intervals.
- Note: An ECDSA signature including a low-S value is mathematically equivalent to the same signature that includes the corresponding high-S value. I don't know why this is the case.

7) Convert the signature (r, s) into DER encoding. The Python ECDSA library includes a function for doing this.

8) Append hash_type SIGHASH_ALL (as a single byte) "01" to DER-encoded signature.





Next: Automate this process. Look at the Python code used in the Python interpreter earlier to perform the steps.


Inputs:
- tx-in-signable-form (hex):

- private_key (hex):

- random k value (bytes):





[development occurs here]











Ok. I now have the single signature for transaction 2:



It is 71 bytes long. In hex, 71 is 0x47.


Separate each hex byte in the signature with a space.







I can now finish constructing the scriptSig of transaction 2. I added the public key data (and its byte length for a PUSHDATA opcode) earlier.

scriptSig from before:



Add the signature data.

scriptSig:





Now let's look at the assembled transaction 2 again.

The new scriptSig will prove the validity of this transaction.




Transaction format:





Transaction 2:




scriptSig:



outputScript:





Convert the scriptSig into a byte sequence.




Need the script_length var_int for scriptSig.



The script_length var_int for scriptSig, in hex, is: 8a


Convert the outputScript into a byte sequence.



Need the script_length var_int for outputScript.



The script_length var_int for outputScript, in hex, is: 17



Insert the scriptSig and outputScript byte sequences into transaction 2. Also insert their length var_ints.




Signed transaction 2:





Convert the final form of transaction 2 into a byte sequence.




Signed transaction 2:




Remove spaces and calculate byte length of signed-transaction-2:




Signed transaction 2:


It is 221 bytes long.

The fee is 225 satoshis, so the fee is slightly greater than 1 satoshi/byte.


Next: Use a web tx-decode utility to validate the format of transaction 2.


Browse to:
live.blockcypher.com/btc/decodetx
Network = "Bitcoin".
Paste in signed transaction hex and click "Decode Transaction".


Result:




Transaction parsed successfully. Various values are as expected.

The size of the transaction is 221 bytes, as expected.


The "hash" value for the signed transaction is:


This should be the txid for this new signed transaction, in big-endian format.




Next: Broadcast new signed transaction and see if it is mined (or rejected).


Let's double-check the current fees before broadcasting.

Browse to:
bitcoinfees.earn.com
- For 0 satoshis/byte, estimated delay is 69-Inf blocks or 660-Inf minutes.
- For 1-2 satoshis/byte, estimated delay is 1-10 blocks or 0-180 minutes.
- For 3-4 satoshis/byte, estimated delay is 0-9 blocks or 0-180 minutes.



Log in to LocalBitcoins and confirm that my current receiving address is still:
36CQfj2Yt54sZttJYTb5ywuS7YGEQLfzCE

Yup, it is.

Also check current deposit fee for incoming transactions:
0.00015 BTC

It hasn't changed.

199550 satoshis = 0.00199550 BTC

0.00199550 - 0.00015 = 0.0018455 BTC

I can expect to have 0.00184550 bitcoin (184550 satoshis) deposited into my LocalBitcoins account.




Browse to:
live.blockcypher.com/btc/pushtx
Network = "Bitcoin".
Paste in signed transaction hex and click "Broadcast Transaction".

Result:



Hm.

Hypotheses:

1) "Error running script" -> There is an error in the outputScript.

2) The txid

is the txid of the first transaction, which moved bitcoin from the source address into the target address. "Error running script for input 0 references [txid] at (unspent output?) 0" indicates a problem with the scriptSig (which authorises spending the output 0 from the first transaction).


Possible approach to finding a solution: Review the work I did to create Transaction 2, put it into signable form, and sign it.


First, try broadcasting again.

Browse to:
live.blockcypher.com/btc/pushtx
Network = "Bitcoin".
Paste in signed transaction hex and click "Broadcast Transaction".


Same result.


Browse to:
blockchain.info/pushtx
Paste in signed transaction hex and click "Submit Transaction".

Result:




Earlier, the decode-tx facility correctly converted the outputScript into the P2SH address, so hypothesis (1) is unlikely.


Hypotheses:

3) The DER formatting system implemented in the Python ECDSA library is not strict.

4) One of the specified satoshi amounts is incorrect.

5) There is a missing var_int (to indicate the length of some variable in the transaction).

6) There is a problem with my low-S-to-high-S conversion.




Earlier, when I constructed transaction-2-in-signable-form, I forgot to include values for "script_length: (var_int)" for both scriptPubKey and outputScript.



Excerpt of earlier work:

Transaction-2-in-signable-form:

Expected format (raw hex bytes):
- version: 4 bytes (little-endian) = 01 00 00 00
- input_count: (var_int) = 01
- inputs:
-- previous_output_hash: 32 bytes (little-endian) = 5a 97 2d 9f 28 9c 27 3c d3 3b 6b 92 74 90 af 21 23 e9 22 8e 3e 95 35 47 ea 00 01 3d 65 5f dd 4b
-- previous_output_index: 4 bytes (little-endian) = 00 00 00 00
-- script_length: (var_int)
-- scriptPubKey of unspent output from previous transaction = 76 a9 14 0f 9e e7 85 22 f6 cc 8a 88 78 4a e0 2b 04 08 e4 52 d8 02 59 88 ac
-- sequence: 4 bytes (little-endian) = ff ff ff ff
- output_count: (var_int) = 01
- outputs:
-- value: 8 bytes (little-endian) = 7e 0b 03 00 00 00 00 00
-- script_length: (var_int)
-- outputScript = a9 14 31 6f 8d 5c 41 d8 8d 3a 0d f1 79 fc 5a d7 65 d5 7f 7f 46 67 87
- block lock time: 4 bytes = 00 00 00 00
- hash type: 4 bytes (little-endian) = 01 00 00 00

Slightly before this excerpt, I calculated that the scriptPubKey was 25 bytes long. In hex, 25 is 0x19.

Later, I calculated that the byte length of outputScript was 23. In hex, 23 is 0x17.




Insert these script_length var_ints (as hex values) into transaction-2-in-signable-form.


Transaction-2-in-signable-form:





Compress transaction-2-in-signable-form into a single byte sequence.


Transaction-2-in-signable-form:



Transaction-2-in-signable-form:




Remove spaces:





Transaction-2-in-signable-form:




Next:
Sign transaction-2-in-signable-form.

I've already written
sign_transaction_in_signable_form.py
I just need to change the value for the input tx-in-signable-form.








Ok. I now have the single signature for transaction 2 (again):



It is 71 bytes long. In hex, 71 is 0x47.


Separate each hex byte in the signature with a space.







I can now finish constructing the scriptSig of transaction 2. I added the public key data (and its byte length for a PUSHDATA opcode) earlier.

scriptSig from before:



Add the signature data.

scriptSig:





Now let's look at the assembled transaction 2 again.

The new scriptSig should hopefully prove the validity of this transaction.


Transaction format:





Transaction 2:




scriptSig:



outputScript:



Convert the scriptSig into a byte sequence.




Need the script_length var_int for scriptSig.



The script_length var_int for scriptSig, in hex, is: 8a


Convert the outputScript into a byte sequence.



Earlier I calculated that the byte length of outputScript is 0x17.


Insert the scriptSig and outputScript byte sequences into transaction 2. Also insert their length var_ints.


Signed transaction 2:





Convert the final form of transaction 2 into a byte sequence.





Signed transaction 2:





Remove spaces and calculate byte length of signed-transaction-2:




Signed transaction 2:


It is 221 bytes long.


The fee is 225 satoshis, so the fee is slightly greater than 1 satoshi/byte.


Next: Use a web tx-decode utility to validate the format of transaction 2.

Note: This produced a usable result previously because transaction 2 was formatted correctly, but transaction-2-in-signable-form was not. The signature was invalid (this utility did not validate the scriptSig), but everything was correctly parsed by this utility.

Browse to:
live.blockcypher.com/btc/decodetx
Network = "Bitcoin".
Paste in signed transaction hex and click "Decode Transaction".


Result:




Transaction parsed successfully. Various values are as expected.

The size of the transaction is 221 bytes, as expected.


The "hash" value for the signed transaction is:


This should be the txid for this new signed transaction, in big-endian format.



Next: Broadcast new signed transaction and see if it is mined (or rejected).


Let's double-check the current fees before broadcasting.

Browse to:
bitcoinfees.earn.com
- For 0 satoshis/byte, estimated delay is 47-Inf blocks or 420-Inf minutes.
- For 1-2 satoshis/byte, estimated delay is 0-7 blocks or 0-120 minutes.
- For 3-4 satoshis/byte, estimated delay is 0-6 blocks or 0-110 minutes.






Log in to LocalBitcoins and confirm that my current receiving address is still:
36CQfj2Yt54sZttJYTb5ywuS7YGEQLfzCE

Yup, it is.

Also check current deposit fee for incoming transactions:
0.00015 BTC

It hasn't changed.

199550 satoshis = 0.00199550 BTC

0.00199550 - 0.00015 = 0.0018455 BTC

I can expect to have 0.00184550 bitcoin (184550 satoshis) deposited into my LocalBitcoins account.



Browse to:
live.blockcypher.com/btc/pushtx
Network = "Bitcoin".
Paste in signed transaction hex and click "Broadcast Transaction".


Result:

New page loaded:
live.blockcypher.com/btc/tx/87d230cad8ae3cc065ce9b52fbbd81140948e3e95b250c9015faa8048e1dee40

Note: The above link contains the txid found earlier when decoding the transaction.

Some of the information on the page:

Transaction Successfully Broadcst

Bitcoin Transaction
87d230cad8ae3cc065ce9b52fbbd81140948e3e95b250c9015faa8048e1dee40

AMOUNT TRANSACTED
0.0019955 BTC

FEES
0.00000225 BTC

CONFIRMATIONS
0/6

Confidence
85.54%

Miner Preference
Low

Size
221 bytes

Lock Time

Version
1

Relayed By:
54.211.11.131


1 Input Consumed

0.00199775 BTC from
12RbVkKwHcwHbMZmnSVAyR4g88ZChpQD6f


1 Output Created

0.0019955 BTC to
36CQfj2Yt54sZttJYTb5ywuS7YGEQLfzCE

Looks like the transaction was successfully broadcast. Or rather, at least one system somewhere was happy to accept it for broadcast.


Set timer for 5 mins.


Timer has finished.
Refresh the transaction description page.

1 confirmation.


~7 hours later:
Refresh the transaction description page.

6+ confirmations.


Browse to blockchain.info.
Paste the txid into the search box and press Enter.

Result:
- 43 confirmations.
- All details are as expected.
- Included In Blocks = 530582 ( 2018-07-05 13:39:30 + 9 minutes )


Log in to LocalBitcoins.
Go to Wallet / Transactions.
Latest item:
- Date = 07/05/2018 15:07
- Received BTC = 0.0018455
- Description = Deposit to 36CQfj......
- Deposit Fee BTC = 0.00015000


Excellent.












I'm going to confirm the process of creating a txid. I read (somewhere) that it's the result of applying the SHA256 hash algorithm twice to the signed transation.

Let's test.



Let's define:
- transaction 0 (tx0) = the transaction in which bitcoin was moved from my LocalBitcoins account to the source address.
- transaction 1 (tx1) = the transaction in which bitcoin was moved from the source address to the target address.
- transaction 2 (tx2) = the transaction in which bitcoin was moved from the target address to my LocalBitcoins account.
- transaction id (txid) = big-endian result of double SHA256 hash of signed transaction.
-- Note: The txid can change due to Transaction Malleability: The transaction byte sequence can be changed in several ways that won't affect its validity but will affect its txid.


signed tx1


txid 1:



signed tx2


txid 2:







Result:



I found this string earlier, when I reversed the endianness of txid1. I thought I was reversing it from big-endian to little-endian.
The input was:

The output was:


I had assumed so far that:
- the SHA256(input_bytes).digest() method in pypy_sha256.py
- the RIPEMD160(input_bytes).digest() method in bjorn_edstrom_ripemd160.py
accepted and returned big-endian data.

Originally, when looking at transaction 1 on two block explorer applications:
- blockchain.info
- live.blockcypher.com
I used txid1 =

to look up transaction 1. I had assumed (at some point during my work, not sure where or why) that the block explorers used txids in big-endian format for links to transaction description pages.


What happens if I use

to look up a txid on a block explorer application?


Browse to
blockchain.info
which leads to
www.blockchain.com/en/explorer

Paste in

and press Enter.

Result:



Browse to
live.blockcypher.com

Paste in

and press Enter.

Result:



Hm. Ok.


I think it's reasonable to assume that
- the SHA256(input_bytes).digest() method
- the RIPEMD160(input_bytes).digest() method
return big-endian results.

This means that

is big-endian txid1 and that

is little-endian txid1.

It also means that the block explorer applications are using txids in little-endian format for their transaction page links.


This would additionally mean that:
- I reversed txid0 from little-endian to big-endian format and included it in tx1 (and tx1-in-signable-form) as previous_output_hash.
- I reversed txid1 from little-endian to big-endian format and included it in tx2 (and tx2-in-signable-form) as previous_output_hash.
- Note: I had thought I was doing exactly the opposite operation in each case.
If this is so, why were tx1 and tx2 accepted and mined with big-endian previous_output_hash values?


Possible explanation: Within a raw transaction, the previous_output_hash is actually a big-endian value.
- Note: This is the case for the public key X and Y values in a scriptSig and the public_key_hash in a scriptPubKey. Most other values in a transaction are little-endian.
- Note: Perhaps the block explorers are displaying all data in little-endian, whether or not it is included within the raw transaction in little-endian form.


txid0:


I reversed this into





Let's double-check the txid of tx2.



signed tx2



txid 2:






Hm.

Same result as tx1. The txid2 used by the block explorers is the endian-reversed result of the double SHA256 hash of tx2-signed.



Alternative hypothesis:
- the SHA256(input_bytes).digest() method accepts input data as a big-endian string, processes it in little-endian, and returns data in little-endian.

This would mean that:
- The block explorers use big-endian versions of the txids in their transaction page links.
- A Bitcoin transaction uses little-endian format for previous_output_hash values.
- I correctly reversed the txids from big-endian to little-endian before using them within transactions 1 & 2 as previous_output_hash values.


Hypothesis 3: Bitcoin transactions can have previous_output_hash values as either little-endian or big-endian.
- Note: This seems quite unlikely. The processing of a new block would become much more expensive.



On balance, I think the first hypothesis is most likely.
- Bitcoin transactions use big-endian format for previous_output_hash values (txids).

Notes derived from this hypothesis:
- The two block explorers blockchain.com and live.blockcypher.com use little-endian format for previous_output_hash values (txids).
- While working with txid values taken from the block explorer data, I reversed their endianness from little to big (thinking that I was doing the opposite) and used big-endian previous_output_hash values (txids) in the two signed transactions (tx1 and tx2). These two transactions were accepted by the Bitcoin network and added to the blockchain.
- the SHA256(input_bytes).digest() method in pypy_sha256.py returns big-endian data (because the double SHA256 txid is placed directly into the raw transaction).
- the RIPEMD160(input_bytes).digest() method in bjorn_edstrom_ripemd160.py returns big-endian data (because the public key hash in a scriptPubKey is in big-endian form).


Note: In the previous project Reading and verifying a standard raw bitcoin transaction, on which I drew heavily for this project, I assumed that the previous_output_hash was stored within the transaction in little-endian form. I then reversed its endianness in order to use a block explorer to look up the previous transaction's data. This led me to think that block explorers used txids in big-endian format for lookups.


This previous project drew heavily on Ken Shirriff's work detailed in his article Bitcoins the hard way: Using the raw Bitcoin protocol

Looking at Ken Shirriff's work, I see that he used the label:
previous output hash (reversed)

The other items were little-endian, so he evidently meant "reversed from little-endian to big-endian".



[some searching and reading occurs here]


Excerpt from:
bitcoin.org/en/developer-reference#hash-byte-order

This page has a pop-up:
"BETA: This documentation has not been extensively reviewed by Bitcoin experts and so likely contains numerous errors."

Hash Byte Order

Bitcoin Core RPCs accept and return the byte-wise reverse of computed SHA-256 hash values. For example, the Unix sha256sum command displays the SHA256(SHA256()) hash of mainnet block 300,000's header as:

> /bin/echo -n '020000007ef055e1674d2e6551dba41cd214debbee34aeb544c7ec670000000000000000d3998963f80c5bab43fe8c26228e98d030edf4dcbe48a666f5c39e2d7a885c9102c86d536c890019593a470d' | xxd -r -p | sha256sum -b | xxd -r -p | sha256sum -b
5472ac8b1187bfcf91d6d218bbda1eb2405d7c55f1f8cc820000000000000000

The result above is also how the hash appears in the previous-header-hash part of block 300,001's header:

020000005472ac8b1187bfcf91d6d218bbda1eb2405d7c55f1f8cc82000\
0000000000000ab0aaa377ca3f49b1545e2ae6b0667a08f42e72d8c24ae\
237140e28f14f3bb7c6bcc6d536c890019edd83ccf

However, Bitcoin Core's RPCs use the byte-wise reverse for hashes, so if you want to get information about block 300,000 using the

getblock

RPC, you need to reverse the requested hash:

> bitcoin-cli getblock \
000000000000000082ccf8f1557c5d40b21edabb18d2d691cfbf87118bac7254

(Note: hex representation uses two characters to display each byte of data, which is why the reversed string looks somewhat mangled.)

The rationale for the reversal is unknown, but it likely stems from Bitcoin Core's use of hashes (which are byte arrays in C++) as integers for the purpose of determining whether the hash is below the network target. Whatever the reason for reversing header hashes, the reversal also extends to other hashes used in RPCs, such as TXIDs and merkle roots.

As header hashes and TXIDs are widely used as global identifiers in other Bitcoin software, this reversal of hashes has become the standard way to refer to certain objects. The table below should make clear where each byte order is used.

[Note: table converted to list]


List of data types and their byte orders in different situations:
[Note: Presumably, Internal Byte Order is always big-endian and RPC Byte Order is always little-endian.]

- Data = SHA256(SHA256(0x00))
-- Internal Byte Order = Hash: 1406...539a
-- RPC Byte Order = Hash 9a53...0614

- Data = Header Hashes: SHA256(SHA256(block header))
-- Internal Byte Order = Used when constructing block headers
-- RPC Byte Order = Used by RPCs such as

getblock

; widely used in block explorers

- Data = Merkle Roots: SHA256(SHA256(TXIDs and merkle rows))
-- Internal Byte Order = Used when constructing block headers
-- RPC Byte Order = Returned by RPCs such as

getblock

- Data = TXIDs: SHA256(SHA256(transaction))
-- Internal Byte Order = Used in transaction inputs
-- RPC Byte Order = Used by RPCs such as

gettransaction

and transaction data parts of

getblock

; widely used in wallet programs

- Data = P2PKH Hashes: RIPEMD160(SHA256(pubkey))
-- Internal Byte Order = Used in both addresses and pubkey scripts
-- RPC Byte Order = N/A: RPCs use addresses which use internal byte order

- Data = P2SH Hashes: RIPEMD160(SHA256(redeem script))
-- Internal Byte Order = Used in both addresses and pubkey scripts
-- RPC Byte Order = N/A: RPCs use addresses which use internal byte order


Note: RPCs which return raw results, such as

getrawtransaction

or the raw mode of

getblock

, always display hashes as they appear in blocks (internal byte order).

The code below may help you check byte order by generating hashes from raw hex.

#!/usr/bin/env python

from sys import byteorder

from hashlib import sha256

## You can put in $data an 80-byte block header to get its header hash,

## or a raw transaction to get its txid

data = "00".decode("hex")

hash = sha256(sha256(data).digest()).digest()

print "Warning: this code only tested on a little-endian x86_64 arch"

print

print "System byte order:", byteorder

print "Internal-Byte-Order Hash: ", hash.encode('hex_codec')

print "RPC-Byte-Order Hash: ", hash[::-1].encode('hex_codec')

Notes:
- RPC = Remote Procedure Call
-- RPC commands are the main way to use the original Bitcoin client from the command line.

Key points:
- In raw Bitcoin data, hashes are stored in big-endian format.
-- Possible reason: The original Bitcoin client needs to check that the header hash of a new bitcoin block is below the current network target value. This comparison is easier if the hash is stored in big-endian format.
- Hashes in Bitcoin: block headers, transaction ids (txids), and merkle roots.
- When used as identifiers in the original client's RPC calls (for e.g. getting data about a block or transaction), hashes are in little-endian format.
- Little-endian is the de facto standard for Bitcoin hash identifiers, but hashes (e.g. txids) are in big-endian form within raw Bitcoin data.
- A system (i.e. the CPU architecture) has a particular endianness.


Can code be written in such a way that it always processes and returns data in a particular endianness, regardless of the endianness of the system underneath?
- Possible approach: Processing data one byte at a time, no matter how slow this turns out to be.


Some reading indicates that the FAT filesystem is written to always use the same endianness, regardless of the CPU architecture.


I would like to know whether the Python SHA256 code will produce the same result if it is run on a Python implementation on a different architecture.

Perhaps an entirely different Python engine is designed and/or compiled for each architecture, in order to handle endianness carefully within the engine so that the Python code will run in the same way and produce the same result.


Are there architectures with a little-endian-esque bit order within a byte? I.e. ones in which the highest-order bit is placed at the end of the byte?
- Some reading indicates "yes". This is called "bit numbering" or "bit endianness". The equivalent of little-endian is "Least Significant Bit (LSB) first" and the equivalent of big-endian is "Most Significant Bit (MSB) first".




I'll test out some of the code suggested in the previous excerpt.




Hm.
- My system byte order is little-endian. The CPU expects to see and process little-endian data.
- It's unlikely that the Mac OS X filesystem was written to be system-independent, so it probably uses the same endianness as the CPU. This means that the data created and stored on this computer should usually be in little-endian form.
-- Note: Endianness problems occur when trying to read a binary file that was originally created on a system using a different endianness.



is equivalent to:



is equivalent to:



is a string reverse operation.


Hm. It looks as though:
- The hash data was returned from the sha256 operation as a big-endian byte sequence.
- The string reverse operation is used here to convert the hash data to "RPC-Byte-Order" i.e. little-endian (e.g. a txid as required by a Bitcoin RPC call).
- The system endianness appears to be unrelated to the endianness of the hash result or its reversal into little-endian form.






Excerpts from:
security.stackexchange.com/questions/13553/does-the-endianness-used-with-an-encryption-algorithm-affect-its-security

Q:

Does the endianness used with an encryption algorithm affect its security?

I'm implementing the AES block cipher, which reads/writes data in 16 byte blocks. The implementation I'm working with usually read data in the little endian format. But in my platform the endianness I'm using is "network order" big endian. Can I use BE for the encryption algorithm? Does the endianness usually change the way the algorithm works? Does it matter at all? I assumed it does not, since it could have simply been different data that you are reading.

asked Apr 7 '12 at 12:00
Robinicks


[...]


A:

The AES is defined as operating on 16-byte blocks. Such a block is an ordered sequence of bytes: there is a first byte, a second byte, and so on, until the sixteenth byte. We often say that the first byte is leftmost and the last byte rightmost because we are westerners who use a latin alphabet and write left-to-right, and we just blindly and implicitly assume that people who write right-to-left are just wrong.

Endianness is about interpreting a sequence of bytes as an integer value; for instance, a sequence of four bytes, interpreted as an integer between 0 and 4294967295. To do such an interpretation, we decide than one of the bytes is for the units (we multiply its numerical value by 1), another is to be multiplied by 256, another by 65536 (which is 256*256), and yet another by 16777216 (i.e. 256*256*256). Little-endian convention is when the byte for units comes first, followed by the byte of value 256, then the byte of value 65536, and finally the byte of value 16777216. Big-endian convention is when the bytes are in the opposite order.

Within AES, there is no interpretation of sequences of bytes into larger integers, so endianness does not apply. However, even for algorithms which do involve interpretation of byte sequences into integers, the algorithm specification defines the endianness to use. It is then up to the implementation to follow that defined convention, whether it matches what the CPU does best or not. For instance, in the hash function MD5, the input message (a sequence of bytes), after padding, is split into 64-byte blocks, and each block is split into 16 4-byte sequences, and each sequence is interpreted as an integer with little-endian convention. MD5 is MD5; it is deterministic and its output for a given input file should not depend on whether the computer uses a x86, ARM, PowerPC or Sparc CPU. Therefore, implementations which run on big-endian CPU must include the necessary byte-swapping steps to do the computation correctly.

Three additional points:

- The importance of endianness for performance is overrated. Even for MD5, which is very fast (on my computer, it processes more than 400 megabytes per second), the byteswap for big-endian CPU implies an overhead of no more than 15%. This is why the usual SHA-1 / SHA-256 hash functions can use big-endian convention (that's how they were defined), contrary to what a basic PC does natively, and it still not a big issue.

- If your C code must be made aware of endianness, then it does things wrong. C code which is not endian neutral is C code which accesses the same memory objects as both bunches of bytes and integers. Such code breaks strict aliasing rules, which means that the code may cease to operate properly when compiled with a different compiler version or with different compiler options. This is sloppy programming.

- Besides little-endian and big-endian, other conventions have existed, often called mixed-endian. These have mostly disappeared. However, big-endian and little-endian architectures are still thriving, therefore, for portability alone, code should be endian neutral.

edited May 23 '17 at 12:40
Community

answered Sep 26 '12 at 22:30
Thomas Pornin

Key points:
- Endianness matters when working with multi-byte data items e.g. 4-byte integers.
-- Some reading indicates that endianness doesn't matter for storing ASCII string data (which is raw bytes) e.g. "hello world".
- When an algorithm, e.g. a hash algorithm, relies on a particular endianness for certain data, this is included in the algorithm specification.
- The implementation is responsible for following the algorithm specification, regardless of the CPU endian convention.
-- If an implementation is written for a CPU architecture with a different endianness than that required by the algorithm, the implementation must include the necessary byte-swapping steps.
- C code can be written in an endian-neutral way.
-- Note: I think that Thomas Pornin is referring specifically to C code where there is no interpretation of a byte sequence as an integer. This operation must carefully manage the endianness of the byte sequence, or the result will be not be the same on different systems.
-- Example: The AES algorithm does not interpret any byte sequences as integers, so the code for it can be written in an endian-neutral way. The same C code can be compiled and run on systems that use different endianness.
- The specifications for the SHA-1 / SHA-256 hash functions include a big-endian convention.


Code must be written separately for each architecture if a specific endianness is to be used within an algorithm across a set of architectures. Example: SHA256 algorithm.


I've read through the PyPy SHA256 code. I don't understand it.

Hm. I've been getting usable results so far by assuming that this SHA256 code returns big-endian results. My system is little-endian.

Two possibilities:
- The Python engine always uses a particular endianness internally, and all its implementations support this, regardless of system endianness. This Python SHA256 code will work on any system on which a Python implementation has been installed.
- The Python engine uses the system endianness. If I were to run this Python SHA256 code on a big-endian system, it might not work properly. A new Python SHA256 implementation would have to be written for this hypothetical big-endian system.










Loose-end: Given the problem of Transaction Malleability, in what ways can a transaction be given a unique identifier, perhaps only for use within an internal transaction tracking system?

Transaction Malleability: A valid transaction scriptSig can be altered in ways that change its raw byte sequence but not its mathematical validity.
- Note: The rest of the transaction cannot be altered without making the signature(s) mathematically invalid.

Possible approach 1:
- Receive a new transaction.
- Confirm its mathematical validity.
- Strip all scriptSigs from the transaction.
- Hash the stripped transaction with e.g. double SHA256.
- Use the resulting hash digest as a unique identifier.
- If new versions of the transaction are received, with different but valid scriptSigs, processing them in this way will produce the same unique identifier. This means that these new versions can be discarded, rather than taking up storage space and requiring further processing to track their status.
- Note: All that is required to confirm a transaction as valid is a single version in which all signatures are mathematically valid.
- Note: This unique identifier will not be usable on other systems that haven't implemented it.
-- Possible solution: While a transaction has not been mined and received at least 6 confirmations, store each valid version of the transaction that is received. Hash each version with double SHA256 in order to produce a txid. Store all txids. Within the internal tracking system, group these valid transaction versions and their txids under the single unique transaction identifier described above. Looking only at the 6th block from the front of the chain, watch for the inclusion of a particular txid in a block. Keep only the transaction version and txid for the transaction that was included in the chain and discard the rest. The internal unique transaction identifier can then be mapped to this final txid so that the txid can be used to reference the transaction when communicating with the external world.



Excerpt from previous project Reading and verifying a standard raw bitcoin transaction:
[Original source: bitcoin.org/en/developer-guide]

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.

Possible approach 2:
- UTXO = "unspent transaction output"
- The set of UTXOs that a transaction uses as inputs is unique to that transaction. It will remain unique forever, since a UTXO can only be used as an input once.
- Receive a new transaction.
- Confirm its mathematical validity.
- Extract the UTXO set of the transaction.
- Hash the UTXO set with e.g. double SHA256.
- Use the resulting hash digest as a unique identifier.
- The unique identifier can used in the manner described in approach 1.

I don't like approach 2 very much. It would group transactions that use the same UXTO set but spend to a different output address or addresses. I don't consider these versions to be the same transaction.

It would also group together transaction versions that spend different amounts to the output addresses and/or use a different mining fee. Again, I don't consider these versions to be the same transaction.


I think that approach 1 is best. It limits transaction variability to different valid signatures. If anything else in a transaction changes, it is treated as a different transaction.


Note derived from the excerpt above: If a transaction disappears from the network (i.e. the memory pools of all public nodes), this doesn't mean that it has vanished permanently. Anyone who stored it can rebroadcast it later - it will still be valid. This means that if you want to try to make the same payment again, it is best to create a new transaction that uses the same UXTO set but has a higher mining fee. If this transaction is mined, the previous one will be invalid, as each UXTO can only be spent once.
- Note: If the original transaction only involved outgoing payments to other people, and it did not send any change back to one of your addresses, then the mining fee cannot be increased by decreasing the change amount. One solution: Create a new transaction in which you add a new input UXTO, and perhaps also use a change address so as not to spend the entire new input UXTO. The previous transaction will be invalidated as long as at least one of its UXTOs is spent in the new transaction.





Excellent. That's the end of this project.



















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 excerpts from PDF files (e.g. not preserving superscript or subscript, replacing stylised characters with basic ASCII characters or descriptions (e.g. "triple_bar", "element_of")).

- 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.