andrewdroll.com

You've found your way to...

...Andrew Droll's personal website, where I host professional information about myself, and blog about science, technology, mathematics, education, philosophy, and other topics.

The latest blog post will always appear below.

Moving Bitcoins

Link to the previous entry.

I was having some difficulty deciding on the topic for this blog when I started writing. I haven't yet done enough research to talk about abuse possible by sub-50% miners in detail, nor have I delved too far into the network synchronization protocol. I'm also not yet prepared to delve into a blog about Bitcoin source, though that may be coming soon. Another idea I had was to give a review of Bitcoin fraud, losses, security problems that have occurred previously as context for security discussions today. Indeed, that is something I plan to do soon as well. However, it's not the choice I've made for this blog.

Today we change gears for today to talk about transactions themselves. Necessarily, I've mentioned transactions a lot already. They are the mechanism by which Bitcoins are tracked and transferred, and they are the information that mining is designed to preserve permanently in the form of blocks and the permanent block chain record.

However, I still haven't talked about what transactions actually are or how they work at a protocol level.

So in this blog I will go over the mechanism by which transactions occur, the information they contain, how they track bitcoins, how they are secured, and the actual format of data broadcasted to the Bitcoin network when a transaction is made.

What is a Bitcoin?

Throughout my blog series, I have often referred to Bitcoins as if they were virtual "objects" - things to be exchanged, akin to giving somebody a five dollar bill in an everyday transaction. Of course, a large proportion of everyday transactions in today's world are not of five dollar bills (or any other denomination of currency), but instead are made digitally, transferring funds via intermediaries like Visa, MasterCard, or your personal banking institution, either on credit or via a direct debit scheme. The actual exchange of physical currency does not occur in any obvious way - however the idea of that exchange of money, backed by a central government bank, is still there.

The fact is that Bitcoins do not exist at all, though. Nowhere in the block chain is there stored a record of how many Bitcoins any given user posesses. Nor is it necessary for a personal Bitcoin wallet, that might run on your own desktop computer, to store that information - though it might be useful. In terms of the Bitcoin protocol, there is no such thing as a file or an address representing a given Bitcoin (or subdivision of a Bitcoin).

So how does Bitcoin work as a currency then? How can you exchange objects that don't exist at all?

The answer is simple: You keep track of the transactions.

When Bitcoins are created as a result of successful block mining, a transaction is created by the miner and added to the block, with their own Bitcoin address set as the recipient and a value currently equal to 25.00000000 (reducing by half approximately every four years). This transaction has a null sender address. This transaction represents currency showing up out of thin air, and it's generated by the miner itself. Don't worry too much though - if they tried to cheat by giving themselves extra coins (i.e. by recording the "value" higher than 25.00000000, for example, then the rest of the Bitcoin would reject the block as invalid).

This represents process gives the miner permission to spend 25 new Bitcoins. The Bitcoins themselves are a mirage though - there aren't a bunch of new addresses or files that pop up to represent them. Instead, to spend these Bitcoins, the miner simply references the transaction that created them. The transaction grants him the right to spend the new coins. The coins themselves don't need to exist at all - the only thing you need is a consistent transaction record.

This applies to all Bitcoin transactions, not just ones that involve miners creating new coins. When Jasper wants to send Bitcoin currency to Daniel, it doesn't involve sending him a bunch of keys or files containing Bitcoins. Instead, it only involves comprehensive transaction record-keeping. The way it works is this:

The block chain has a number of transactions with Jasper as the recipient in its records. He's also sent some Bitcoins, so he is the sender on a number of other transactions.

When Jasper wants to send coins to Daniel, he does so by referencing previous transactions of which he was the recipient. Each of these has a value, representing the number of Bitcoins Jasper received in that transaction. When sending Bitcoins to Daniel, Jasper needs to collect a number of transactions, where he was the recipient, and where the value of coins he received cumulatively in those transactions was at least as large as the value he wants to send to Daniel.

If the cumulative value of the transactions Jasper has collected and combined to send Bitcoin to Daniel exceeds the value he wants to send to Daniel, then the extra balance is added to the transaction as change - a second output, directed back at Jasper. Jasper really pays himself this change. He's generating the transaction after all. However, it's set up so that Daniel receives the correct value, and Jasper doesn't lose coins.

This all sounds pretty complicated. The idea is simple though: A virtual currency doesn't actually need to keep objects identifying currency; It only needs to keep track of every exchange of currency.

The fact that a user has some Bitcoins is known by virtue of the fact the user has been the recipient of transactions with some nonzero values. She has the permission to spend that value of coins by generating a new transaction, referencing the prior one, and identifying another user as the receiver of the new transaction. She verifies her identity by a cryptographic signature so that nobody else can spend coins from transactions where she was the recipient.

So the point here is that there are no Bitcoins - there are only Bitcoin transactions.

What makes a transaction?

In a moment, we will break down an actual transaction into its component information and analyze how it communicates a transfer of Bitcoins effectively. First, though, let us examine what types of information we should expect a transaction to include. Qualitatively, these might be:

  • The sender of the transaction.
  • The receiver (or receivers) of the transaction. Multiple receivers ARE allowed in Bitcoin!
  • A record of where the coins used by the sender in the transaction came from - that is, identifiers for their precedent transactions. Bitcoins don't exist themselves, so this is necessary for record-keeping and to verify that the sender has the right to transfer the Bitcoin funds in question.
  • How much currency is to be sent to each recipient.
  • How much change is to be returned to the sender.
  • A security mechanism ensuring that the claimed sender was the one who generated the transaction. Otherwise, miners (or anyone else) could spend anyone's Bitcoins at any time.


These are exactly the pieces of information that a Bitcoin client broadcasts to the network when it wishes to initiate a transaction, modulo a few details. In practice, transactions are generated automatically by client Bitcoin wallet software. The user needs only to specify the address of the recipient, the amount of coins to be transferred, and perhaps to provide a password or some other type of authentication to verify his or her identity.

The process of figuring out the most efficient precedent transactions to reference when compiling the funds required by the sender in the transaction is done automatically by the software referencing the block chain. If the sender has received many small transactions - say, all of 0.01 Bitcoins (we may sometimes refer to units of Bitcoins by the standard acronym BTC from now on) - and they want to send 1 Bitcoin in the transaction, then the transaction will have to contain 100 precedent transaction identifiers in order for enough currency to be available to transfer.

Bitcoin client software does this type of calculation automatically, then formats the information correctly and broadcasts it to the wider Bitcoin network so that its validity may be confirmed, and miners may add it to the queue for the next block.

Real transactions

With qualitative discussion behind us, let us look at some actual transactions recently broadcast over the Bitcoin network. We will look at the actual information broadcast in a real Bitcoin transaction. Examples are easy to find: Every valid transaction ever made via Bitcoin is recorded in the block chain, and the block chain is stored openly on every Bitcoin node. There are various web APIs designed for convenient transaction and block viewing - blockchain.info, blockexplorer.com, and blockr.io are a few examples.

Here is an example of transaction raw data from block 308635 (earlier today), obtained from blockexplorer.com (note that I am truncating long cryptographic elements to avoid line overflow!):


{
"hash":"b99a194...",
"ver":1,
"vin_sz":2,
"vout_sz":1,
"lock_time":0,
"size":405,
"in":[
{
"prev_out":{
"hash":"8df247...",
"n":0
},
"scriptSig":"304602210... 04d010878..."
},
{
"prev_out":{
"hash":"85b8d0530...",
"n":0
},
"scriptSig":"304502202... 04d010878..."
}
],
"out":[
{
"value":"20.00990000",
"scriptPubKey":"OP_DUP OP_HASH160 bb89104f... OP_EQUALVERIFY OP_CHECKSIG"
}
]
}

We'll examine this transaction data in a moment, but first I will note that this particular transaction actually has some atypical elements. An experienced user would notice this instantly, even if the data seems obtuse. We will pick a more typical example next, but this one will serve to illustrate some ideas about the data in transactions more fully than otherwise.

So, let us examine this transaction line-by-line and figure out what it says:

"hash":"b99a1946d98..."

This line is a unique hash SHA-256 hash of most of the transaction in question. It serves as an identifier, and along with the file size, also serves as verification that the transaction has not been modified after being signed by the sender. Unfortunately there is a wrinkle here. Included in transactions are references to scripts run client-side to verify its authentication. It is impossible to include the full code of these scripts in the transaction hash, and they can be customized on a per-transaction basis (the purpose of customization of scripts is to allow more complicated transactions - for example, transactions with multiple senders or with a contractual nature).

The fact that not the entire script is included in the hash allows some potential modifications to transactions after the fact. This is called transaction malleability, and it has caused problems in the past - in particular, transaction malleability was cited as a major problem in the Mt.Gox fiasco earlier this year (a crisis we have not yet addressed in these blogs, but which we will arrive at eventually - the link is to Reuters coverage). Most of the information is hashed securely - receivers, precedent transactions, values, and so on. Bitcoin wallets can also be designed to work around this issue in practice. Moreover, once a transaction is confirmed by being included in a block by a miner, malleability is no longer a real concern. However the malleability problem is certainly worth noting. It has been a major cause cited for losses of millions of dollars' worth of Bitcoin value in the past.

"ver":1,

This line is representative of the Bitcoin software version being used. However, there are technical caveats involved. Insofar as transactions and block headers are confirmed, this field must be equal to 1 for the network to accept the broadcast.


"vin_sz":2,
"vout_sz":1


These fields indicate, respectively, the number of precedent transactions used to source the Bitcoins for the current transaction, and the number of receiver addresses that will receive Bitcoins in the current transaction. Thus, the transaction we are looking at sources Bitcoins from two precedent transactions, and has only one receiver.

This is the first atypical aspect of the transaction we are looking at. It is unusual for a transaction to have only one receiver, because typically, the sender of the transaction will receive change. This means two receivers - the actual receiver of the Bitcoins to be transacted, and the original sender, receiving the surplus currency as change.

Thus, in our current transaction, there is no change to the sender. The two precedent transaction values must add exactly to the amount intended to be sent to the receiver (modulo a small transaction fee). A "vout_sz" field equal to 1, as in this transaction, is not the typical case.

"lock_time":0

This is a field where nonzero values are reserved for more complicated transactions. The "lock_time" field may identify a block number or timestamp after which the transaction may no longer be modified - meaning that until this timestamp or block number, the transaction may be modified by the sender (or in even more complicated transactions, by one of multiple senders). In typical client-to-client purchase transactions, "lock_time" is set to 0 - the transaction is locked immediately and is not intended for modification. In transactions with nonzero "lock_time," a new field is added, called "sequence," which identifies the version of the transaction. The version with the highest sequence number when the "lock_time" field is satisfied will be processed by miners into the next block. Miners cannot validly include a transaction in a block until its "lock_time" field is satisfied.

"size":405

This field stores the size of the transaction (in bytes). This may be used for verification purposes along with the transaction hash.

"in":[
{
"prev_out":{
"hash":"8df2472b31...",
"n":0
},
"scriptSig":"304602210... 04d010878e..."
},
{
"prev_out":{
"hash":"85b8d05306c...",
"n":0
},
"scriptSig":"304502202 04d010878e..."
}
],


The "in:" field indicates the start of the list of precedent transactions, whose combined values will be used to pay the outputs of this transaction. Here there are two precedent transactions. The lines

"prev_out":{
"hash":"8df2472b31...",
"n":0
},


identify the first precedent transaction. The "hash" line is its hash. The line '"n": 0' identifies which output of the precedent transaction is to be used in the current transaction - remember, transactions may have multiple receivers, and the sender of our current transaction may have been just one of many receivers in the precedent transaction. In this case, he was the first receiver listed in the precedent transaction, identified by the "0" value in the "n" field.

Remark that the values of precedent transactions are not listed in the current transaction's data - from the hash and the output number, one may check the block chain record to determine its value. The entire value will be applied to payments to receivers of the present transaction. This is why change is typically required - it is not usually possible for Bitcoin software to find precedent transactions whose values add exactly to the output value of the current transaction, so there is normally excess to be returned to the sender as change.

Moreover, remark that the precedent transaction hashes and output indices provide the sender's Bitcoin address - he was the receiver of that precedent transaction's indicated output, which means his address can be found by looking up that transaction and looking at the receiver's address listed there.

Note that the parentheses "{..}" separate distinct precedent transactions. In our present case, as the "vin_sz" field discussed earlier indicated, there are two precedent transactions to consider.

The line

"scriptSig":"3046022100b9b... 04d010878e40..."

contains the cryptographic authentication confirming that the sender of the current transaction has the right to spend the coins from the specified output of the first precedent transaction. This line really contains two pieces of information: The signature, "30460221...", and the sender's public cryptographic key, "04d010878e..."

The cryptographic verification here relies on the principles of public-key cryptography, and is implemented here via ECDSA (elliptic curve digital signal algorithm). We will discuss the details in a small supplementary blog entry to follow.

A high-level explanation sounds like this: The sender has both a private key, only known to them, and a public key, broadcasted in the transaction as indicated, which is known to the entire network. The sender uses a cryptographic algorithm to encrypt the transaction's data (without the hash) using his or her private key. This encrypted data is the signature. The public key may be used to verify that the signature decrypts to the valid transaction data. However, the public key and the signature together still do not allow easy computation of the private key. Thus nobody except the valid sender can fake the signature.

Suffice it to say that the signature plus public key combination allow any receiver to verify that the message originated from the claimed sender (or someone possessing their private key, at least), without allowing anyone else to fake transactions from that sender. The format of the public key and the resulting signature are determined by the specific algorithm being used - in this case, the ECDSA algorithm.

We will note a potential protocol problem associated with ECDSA public keys. In particular, there is some wiggle room in ECDSA public keys - there are slight variants on a given ECDSA key that can generate the same digital signature. These are recognizable and take known formats. A solution is for wallets and Bitcoin clients to only accept transactions with signatures in the correct format. However, this is a second transaction malleability concern within the protocol.

"prev_out":{
"hash":"85b8d05306c...",
"n":0
},
"scriptSig":"304502202c9e... 04d010878e4..."
}


These are the identical lines for the second precedent transaction. The hash is different, because this is a different precedent transaction. The signature is also different, because now the sender is authenticating his right to relay coins from a different transaction - this point will be addressed more fully when we blog about ESDSA and public key cryptography. The input field is still equal to 0, so we are taking the value of the first input of the second precedent transaction. The public key also has not changed. This is a unique identified of the sender of the current transaction, and does not need to change in order for unique signatures to be generated and validated.

The last lines in the transaction are:

"out":[
{
"value":"20.00990000",
"scriptPubKey":"OP_DUP OP_HASH160 bb89104fea... OP_EQUALVERIFY OP_CHECKSIG"
}


As the "out:" field might suggest, these lines specify the receiver's parameters. The "value:" line does exactly what it sounds like - it specifies how many Bitcoins the given receiver is to be sent.

In general, if the total cumulative "value" in all of the output fields of a Bitcoin transaction is less than the cumulative values of all the indicated outputs of the precedent (input) transactions - resulting in a surplus of input coins - then the excess coins are taken as a "transaction fee." Transaction fees are paid to the miner who completes the block in which the transaction is recorded. Thus, transaction fees provide a reward to miners beyond the simple mining of new Bitcoins. Many Bitcoin transactions have small transaction fees mandated in order to be accepted by miners. This has a motivation in the protocol - small, fixed transaction fees provide a disincentive for anyone trying to overload the Bitcoin network with a large number of small-value transactions.

The "value" field contains 8 decimal places. This is because the smallest unit of Bitcoin possible in the protocol is 10-8 - one one-hundreth millionth. A unit of 10-8 = 0.00000001 BTC is called a "Satoshi," eponymous of Satoshi Nakamoto, the originator of Bitcoin (which may itself be a pseudonym).

The last relevant line of the transaction is "scriptPubKey":"OP_DUP OP_HASH160 bb89104fea7bc7394c378811917fc83c8b59042c OP_EQUALVERIFY OP_CHECKSIG." The most important thing to note here for now is the hexadecimal string in the middle of the field: This string, "bb89104fea...," is the Bitcoin address of the receiver of this output of the transaction.

The rest of the line specifies instructions on how the transaction's signatures are to be verified. These instructions are written in Bitcoin's scripting language, and refer to functions built-in to Bitcoin software. Typically these instructions are exactly as given here: "OP_DUP OP_HASH160 ... OP_EQUALVERIFY OP_CHECKSIG." However, in some more complicated transactions, involving multiple senders or delayed contracts, more complicated processing scripts may also be required.

The nature of these scripts actually presents a potential problem for the protocol, which we already mentioned earlier: Transaction malleability. Not all of these script instructions can be incorporated into the transaction's hash, since part of their execution generates the hash itself. Thus in some cases it may be possible to insert additional instructions, or change instructions, after the hash has been generated. Again, there are solutions for this problem at the wallet level, but this malleability problem is a concern and has allowed fraud in the past (as mentioned previously, cited earlier in the Mt.Gox crisis earlier this year).

We will leave a detailed analysis of Bitcoin scripting to a future blog. It is interesting to note these concerns now, though.

We mentioned earlier that this transaction is not quite typical. Why?

As noted previously, this transaction has two inputs but only one output. This is not the typical case for a Bitcoin transaction. We normally expect at least two outputs - the intended recipient being one of them, and the sender himself being the other, receiving change. In the case we have just looked at, a closer look at the precedent transactions (incorporated automatically if we look at blockexplorer.com's detailed transaction listing) shows that the first precedent input of our current transaction had value of 0.01 BTC, and the second had value of 20.00 BTC.

Thus the total value of the precedent transactions was 20.01 BTC, with 20.0099 BTC to be paid to the single recipient. The left-over 0.0001 BTC was left out to be paid as a transaction fee to the miner who validated the transaction. There is no change to the sender because the two precedent transactions' values add exactly to the amount meant to be sent to the receiver. A Bitcoin wallet will always try to calculate the most efficient way to combine precedent transactions to pay the required amount to the receiver of a new transaction - however, typically, it will not be able to do so as exactly as in the present case. The exactness makes this particular transaction slightly outside the typical case.

Another interesting aspect of this transaction is the value. Bitcoins are worth a lot of money. At the time of writing, 1 BTC is valued at $650.28 USD, according to coindesk.com. Thus value of 20.01 BTC paid in our example is worth over $13,000 USD. As we can see, users of Bitcoin are making substantial transactions with the currency.

For an example of a more typical transaction, with many input transactions and including change to the sender, one may freely look at the database at blockexplorer.com. Here is one example: Detailed info ; Raw data.

All for now

That will do it for this blog. More to come.

Change the world.
Join the #SolveMIT community.

Keep informed, the Gnowit way.

Andrew Droll

Ottawa, Canada

About

I am the Lead Data Scientist for Gnowit Inc. in Ottawa, Canada. Recently I joined the Massachusetts Institute of Technology (MIT)'s Solve movement as an invited participant to its inaugural event. I hold a Ph.D. in Mathematics from Queen's University in Kingston, Ontario. If you'd like to contact me, then get in touch by e-mail, via social media, or call/text me at 613.864.0442.

Interactive CV

Bio