Launching the beta version of a Blockchain proof of existence service

The Blockchain timestamping software I’ve been working on for the past couple of months (blog post part 1 and part 2) is finally ready for beta-testing at http://BlkProof.com

The site calculates fingerprints (SHA256 checksums) of user’s files and write these to the Bitcoin Blockchain. The actually calculation happens in the user’s browser, thus the file itself is never shared or even transferred over the internet, making it suitable files with sensitive or private content. If ownership of something included in the file is later contested, the user can refer to the timestamped fingerprint in the Bitcoin Blockchain as proof that they had access to the file at this earlier point in time (with the caveat that only existence is proven, more on this below).

Components of the website

The BlkProof website consists of 3 layers:

• the HTML and Javascript front-end loaded in the user’s browser. This is includes everything the user sees, as well as the functionality needed to compute the SHA256 fingerprints of files.
• a mid-tier written in Go and hosted on Google App Engine. This code verifies payment/vouchers and sends the confirmation email when the fingerprint is written to a block.
• a backend written in Go and hosted on Google Compute Engine. This is where the heavy lifting is done. It’s basically a SPV Bitcoin Wallet, with persistent connections to multiple other nodes in the Bitcoin network. Verified requests are received from the mid-tier, and corresponding Bitcoin transactions are built and broadcast to the network with the appropriate fees to miners. It watches the Bitcoin network and alerts the mid-tier when a relevant transaction is confirmed by a miner.

Each of these layers are currently in beta, with several parts still lacking. If you want to help test the site, try using it in various ways and let me know if you perform an operation that doesn’t work as expected. For some free trial runs, use voucher blkproofZfUXa4Q1ZEfcCLNmVJCC9ExbWipvfJjP5kNEXq5QcpJbKRg (copy-paste it into the voucher-field when ready to write a fingerprint to the Blockchain)

From proof of existence to proof of creation

A timestamped fingerprint in the Bitcoin Blockchain proves that a certain file existed at a point in time. Neither BlkProof or the Blockchain tracks where the fingerprint came from, so anyone could have put it there.

To get from this to proof that you created the file, your name needs to be in the file itself. For documents this can be achieved by simply writing you name in it, for things like audio and images, various tags can be used (eg. ID3). If neither of these options are viable, you can simply bundle the file(s) you want to have timestamped with a text file in something like a zip-archive, then timestamp the fingerprint of the archive (note that in this situation you need to keep a copy of that exact zip-file around for when you need to prove that exactly that file (and its content) is the one that has that fingerprint).

Will this actually be accepted as proof of creation? I am not a lawyer, but proving that you had access to a file at an earlier point in time than anyone else claiming to have created it should be pretty convincing evidence.

Blockchain proof of existence, part 2

This is the second part of a series on developing a Bitcoin application able to record document checksums in the Blockchain. The first part covered development of the software needed to take control over some addresses and create valid transactions, which itself was built on top of software handling discovering and connecting to the Bitcoin peer-to-peer network (covered in this post).

The actual additions needed to the Bitcoin wallet in order to write arbitrary data to the Blockchain turned out to be quite trivial; replacing the pay-to-pubkey-hash script with OP_RETURN followed by the data payload and broadcast it as normal:

Transaction: e4a325b4b54ca05bd58655a1c535c86fb7648e5392e83c72b428aee07ed19547

Input: tx aa37ea6c35e6688b52f71908bd3fb7700b83d6e88e32349914a7be964e5d69a8 (output index 1) => 1LivLKSyh9hU9enjptHveRqxp1uJ8NfDYd

Signature: 3046022100c22c7f8b3e49718fa8cb6db530c4d0607feb5cabe649a4070713e922d523058a022100d08292daabf847e6968572a9c6ec0a723b49ee85f11104de24e43510ce1e623f01

Output: 0 satoshis (0.000000 mBTC) to script: OP_RETURN 636861696e206f662074686f75676874

Output: 30000 satoshis (0.300000 mBTC) to script: OP_DUP OP_HASH160 1dhBEoKc1soKqVLfrgs8SPAn3hyVBRoWC OP_EQUALVERIFY OP_CHECKSIG

Where the payload 636861696e206f662074686f75676874 is, narcissistically, the hex encoded "chain of though". How well Blockchain trackers displays the payload data varies, but at least one (coinsecrets.org) does a good job at it.

From here the next step will be to expose this functionality online, giving everyone the power to record checksums, or other data, on the blockchain.

Working around transaction malleability

In my last post I wrote about how someone is exploiting transaction malleability to produce duplicate transactions that are seen as valid by the Bitcoin network. This is causing a few different issues, where the most important for my use-case is the inability to safely spend unconfirmed change from previous transactions.

Normally one would be able to spend the outputs of a transaction without waiting for it to be confirmed by a miner. When the subsequent transactions are broadcast, the other nodes, miners included, will know that the previous transaction with the outputs now being spent is pending confirmation. Miners can chose to include a chain of transactions spending each others' outputs in the same block, effectively confirming them all at once.

With duplicate valid transactions being broadcast by a third-party, it's not clear which one will end up getting confirmed, rendering both the unconfirmed transactions and their outputs potentially invalid, precluding reliable spending of them. Thus the change (and other outputs) become locked up until the previous transaction is confirmed in at least one block (or more if one wants to be safe from orphaned blocks).

Malleability strikes

I'll use a set of transactions made last night as an example. I'm sending 1.2 mBTC (which happens to be most of the funds in this wallet) to a couple of my own addresses:

Transaction: c83daec40c929b93bcc74b2cf1e434df6dd683e03f0734d659eb598fd6be859f

Input: tx 3d9ae35ec8e5b4c9b9cdad8c1fe7bd9afc465646485a9d5932fb71cbff586294 (output index 0) => 13ZsFbiWrDeyyBwwtFpmssA47Tv7v7tZNX
Signature: 304402205e60723c766054f37de49e312e5ca30458d80b2998319acdd6b9987c9b585f7c02206b282675dee89634b4470ea314ccfd18171732d35473517cd49b2889c9d1b46901

Input: tx f2312492b3383adc7d3aa68762e3988eba21b0787810eaf5504b7382247c814c (output index 0) => 191SwwonaRnUxDREcFVKgaRyUn6RuKPGjj
Signature: 30440220015dceb8395f0e5f52c47739659306e6ed552bd5f3fca2a6730587f4c82e2a6e022064a9bc869b35d6c773c7bf5423f40bd057666f14b2e6ef6dca5de1394d39a04501

Input: tx f2312492b3383adc7d3aa68762e3988eba21b0787810eaf5504b7382247c814c (output index 1) => 1Ky3S6nfazgAzGJB9UoS7Djn2mh3tSrMT
Signature: 30440220581b87bb9c49bcaa834081a1454bc68ee5c4541bbe98622f8cc4518e551b756302206cf4c02c961866913d11dd0f69d03d9c38a7874a17e68706af1399d11ec2e9a801

Output: 100000 satoshis (1.000000 mBTC) to script: OP_DUP OP_HASH160 1K1RhsKXz3amFrpoWB8H4B3bgYTafBsU9L OP_EQUALVERIFY OP_CHECKSIG
Output: 20000 satoshis (0.200000 mBTC) to script: OP_DUP OP_HASH160 1LwuLQK93PDTB1fR4CJ5DgpnsgrUXJiaTb OP_EQUALVERIFY OP_CHECKSIG 

Within seconds of me broadcasting the above transaction, the following equivalent transaction is produced by an unknown third-party:

Transaction: fe99ee388fca957b324039b8cc2c3938b2a0e3bfff9cb98bec0c7a422b4242b2

Input: tx 3d9ae35ec8e5b4c9b9cdad8c1fe7bd9afc465646485a9d5932fb71cbff586294 (output index 0) => 13ZsFbiWrDeyyBwwtFpmssA47Tv7v7tZNX
Signature: 304502205e60723c766054f37de49e312e5ca30458d80b2998319acdd6b9987c9b585f7c02210094d7d98a211769cb4bb8f15ceb3302e6a397aa135ad54ebeeb37360306648cd801

Input: tx f2312492b3383adc7d3aa68762e3988eba21b0787810eaf5504b7382247c814c (output index 0) => 191SwwonaRnUxDREcFVKgaRyUn6RuKPGjj
Signature: 30450220015dceb8395f0e5f52c47739659306e6ed552bd5f3fca2a6730587f4c82e2a6e0221009b56437964ca29388c3840abdc0bf42e63486dd1fc61b0cdf5747d5382fca0fc01

Input: tx f2312492b3383adc7d3aa68762e3988eba21b0787810eaf5504b7382247c814c (output index 1) => 1Ky3S6nfazgAzGJB9UoS7Djn2mh3tSrMT
Signature: 30450220581b87bb9c49bcaa834081a1454bc68ee5c4541bbe98622f8cc4518e551b7563022100930b3fd369e7996ec2ee22f0962fc2628207559c9762193510bec4bbb173579901

Output: 100000 satoshis (1.000000 mBTC) to script: OP_DUP OP_HASH160 1K1RhsKXz3amFrpoWB8H4B3bgYTafBsU9L OP_EQUALVERIFY OP_CHECKSIG
Output: 20000 satoshis (0.200000 mBTC) to script: OP_DUP OP_HASH160 1LwuLQK93PDTB1fR4CJ5DgpnsgrUXJiaTb OP_EQUALVERIFY OP_CHECKSIG


I won't go into how it's different from my original (read my previous post on the topic for that); suffice to say it is a valid, but conflicting transaction, and nodes and miners have no way to tell which is the original of the two.

If I want to spend the outputs of that transaction before it is confirmed, the dilemma is the following: the two conflicting transactions have different hashes, producing unique and different outputs:

• c83daec40c929b93bcc74b2cf1e434df6dd683e03f0734d659eb598fd6be859f, index 0 has 1 mBTC and index 1 has 0.2 mBTC
• fe99ee388fca957b324039b8cc2c3938b2a0e3bfff9cb98bec0c7a422b4242b2, index 0 has 1 mBTC and index 1 has 0.2 mBTC

Eventually one of those will be confirmed and the other one will be thrown away as invalid. If we use the wrong one in our next transaction, parts of the network will accept it as a valid transaction for a while (essentially whatever nodes saw its predecessor first are going to see this one as valid too), but it will never end up getting confirmed by a miner. This is frustrating, and can result in us believing we sent a payment (or recorded a document checksum on the blockchain) when in reality the transaction ended up getting dropped by the whole network.

Living with uncertainty

Using a transaction fingerprint that isn't affected by signature modifications, it is easy to recognize two or more transactions as originating from a malleability attack. This information can be used to postpone spending the change until one is confirmed and the situation is cleared up.

Another option when this is encountered is to accept that out of this set of transactions, only one will eventually get confirmed, and new transactions created spending the outputs of the others are certain to get dropped. What I did was to modify my wallet software to create its own duplicate transactions when a situation like this is encountered. The following are the suggested transactions for splitting the still unconfirmed 1 mBTC I just sent to 1K1RhsKXz3amFrpoWB8H4B3bgYTafBsU9L into payments of 0.5 and 0.4 mBTC to two new addresses (paying a 0.1 mBTC fee):

Transaction 0: 4ebe551a5830a9a17b149fa75ae037e0511a730ae9919183a9c03045bed043b1

Input: tx c83daec40c929b93bcc74b2cf1e434df6dd683e03f0734d659eb598fd6be859f (output index 0) => 1K1RhsKXz3amFrpoWB8H4B3bgYTafBsU9L
Signature: 30430220197d47182020132ac30fb0ef5d0a86913adc4aaf756a806e2997fe2e4ea79eaf021f60ba102e4400538f286bf877250d72708cead8561f1c21be4eba83221c314c01

Output: 50000 satoshis (0.500000 mBTC) to script: OP_DUP OP_HASH160 1NK66CAL8CajEZBFLXke3VtckxnML3PYpv OP_EQUALVERIFY OP_CHECKSIG
Output: 40000 satoshis (0.400000 mBTC) to script: OP_DUP OP_HASH160 1LivLKSyh9hU9enjptHveRqxp1uJ8NfDYd OP_EQUALVERIFY OP_CHECKSIG 

Transaction 1: aa37ea6c35e6688b52f71908bd3fb7700b83d6e88e32349914a7be964e5d69a8

Input: tx fe99ee388fca957b324039b8cc2c3938b2a0e3bfff9cb98bec0c7a422b4242b2 (output index 0) => 1K1RhsKXz3amFrpoWB8H4B3bgYTafBsU9L
Signature: 304402202dc4cb51339bd2b434df13e3a9bbe65d845750ff03f2622a38e58dd47418c92c0220422e8389316d3dd5fff3a1ad66bb186460303a7616d52fb9f89ee5170740981a01

Output: 50000 satoshis (0.500000 mBTC) to script: OP_DUP OP_HASH160 1NK66CAL8CajEZBFLXke3VtckxnML3PYpv OP_EQUALVERIFY OP_CHECKSIG
Output: 40000 satoshis (0.400000 mBTC) to script: OP_DUP OP_HASH160 1LivLKSyh9hU9enjptHveRqxp1uJ8NfDYd OP_EQUALVERIFY OP_CHECKSIG

As you can see, two basically equivalent transactions are generated, one for each of the potentially valid outputs to 1K1RhsKXz3amFrpoWB8H4B3bgYTafBsU9L. These would then, ideally, each be sent to the nodes of the network that see their respective predecessors as valid transactions as these would readily accept this next one as well. For simplicity we do the slightly abusive alternative of just broadcasting both of them, and letting our connected nodes (based on which predecessor they saw first) filter out the "good" one.

In this particular example, fe99ee388fca957b324039b8cc2c3938b2a0e3bfff9cb98bec0c7a422b4242b2, the conflicting transaction broadcast by the unknown third-party, ended up becoming the confirmed one, mined in block 379791. As it turns out, our second follow-up transaction (aa37ea6c35e6688b52f71908bd3fb7700b83d6e88e32349914a7be964e5d69a8) got confirmed in the same block. The first follow-up gets dropped by the network along with its predecessor, as intended.

Limitations

This approach relies on creating a potentially high number of redundant transactions to be able to spend unconfirmed change. In the case above, it's only two transaction, but the nature of transaction malleability allows third-parties to create a lot more duplicates than that if they are so inclined. Furthermore, you'd now have a number of actually distinct duplicate transactions (the change-spending transactions above have different inputs, which is a new level of duplication than what malleability allows for). If a third-party decided to create duplicates of the new change-spending transactions and we were to try to spend the unconfirmed outputs of these too, we'd have a veritable explosion of duplicate transactions.

With the current magnitude of the malleability attacks, where a single duplicate transaction is broadcast for each original transaction, creating duplicate spending transactions for the respective outputs will enable several levels of chained transaction between block -- without requiring excessive numbers of speculative transactions to be broadcast. That might not be the case if the malleability attacks intensified in the future. For now though, the workaround outlined above seems like an appropriate and sufficient remedy.

Transaction malleability

Transaction malleability is an artifact of how Bitcoin transactions are signed. As I mentioned in my last post, the input signatures are there to, in part, protect your transaction from being modified by third parties. Without access to the private key used to sign a transaction, there's no way for an attacker to change where that transaction sends its satoshis without invalidating the signature. However, the signature itself is not protected from change, and herein lies the rub; changing the signature will change the hash of a transaction, essentially creating a new equivalent transaction, that is still valid. This has a number of issues, and due to, apparently, a bored Russian hacker, malleability has recently gone from a theoretical problem to something pretty much all Bitcoin software has to deal with all the time, my wallet software being no exception.

What does it look like?

I recently broadcast a simple transaction that can serve as an example of what exactly malleability looks like. The transaction sends two unspent outputs to a new address and hashes to 3d9ae35ec8e5b4c9b9cdad8c1fe7bd9afc465646485a9d5932fb71cbff586294. It has already gotten a few confirmations and can be viewed in detail on blockchain.info.

 This is how it looked on my wallet just before I broadcast it, let call this transaction A:

Transaction: 3d9ae35ec8e5b4c9b9cdad8c1fe7bd9afc465646485a9d5932fb71cbff586294, version 1

Input: tx 389a80eaccc69ce8504de8f60cbbb5ecb0c975be6197e77d91326417ab8166ff (output index 1) => 17pZuDHfXNLKxyA7hsd1cGrSSPtUrhnxTq
Signature: 3044022035e0595694e040591bd9ca90015a889318ce1e5eb247c547672ea3974eecd7fb02205004cd171a1b282cb75ab7e285d840a6ec1facffbc50aa6e651e969e6103bc6201

Input: tx e4231428afe4a2fd1574a2e7d9eaec392db6c6b75ee53c99e34ed1c141b01aa0 (output index 0) => 18WPbS5dxLUjE16DymRpv1q7W9JmPz8u9u
Signature: 30460221008a162fbaf43f2f10db622d9443f89a50574f83d9c57b66dd14ec276130dafeec022100a013b18159b5737f0d7dec9f0e95815cd3cfd82e461baad6c42d37e93d55bb4001

Output: 30000 satoshis (0.300000 mBTC) to script: OP_DUP OP_HASH160 13ZsFbiWrDeyyBwwtFpmssA47Tv7v7tZNX OP_EQUALVERIFY OP_CHECKSIG 

Within seconds, the connected nodes indicated that transaction A had been added to their mempools and regarded as a valid transaction. Then, roughly 8 seconds after the broadcast, one node notifies my wallet that it has a transaction with hash b4f3c62159a222ea9eccf5d0f9057c555d0d519cfe580412c4c185c244d8bb30 paying one of its addresses. The wallet software promptly fetches the transaction, and this is how it looks (lets call this transaction B):

Transaction: b4f3c62159a222ea9eccf5d0f9057c555d0d519cfe580412c4c185c244d8bb30, version 1

Input: tx 389a80eaccc69ce8504de8f60cbbb5ecb0c975be6197e77d91326417ab8166ff (output index 1) => 17pZuDHfXNLKxyA7hsd1cGrSSPtUrhnxTq
Signature: 3044022035e0595694e040591bd9ca90015a889318ce1e5eb247c547672ea3974eecd7fb02205004cd171a1b282cb75ab7e285d840a6ec1facffbc50aa6e651e969e6103bc6201

Input: tx e4231428afe4a2fd1574a2e7d9eaec392db6c6b75ee53c99e34ed1c141b01aa0 (output index 0) => 18WPbS5dxLUjE16DymRpv1q7W9JmPz8u9u
Signature: 30450221008a162fbaf43f2f10db622d9443f89a50574f83d9c57b66dd14ec276130dafeec02205fec4e7ea64a8c80f2821360f16a7ea1e6df04b8692cf564fba526a392e0860101
The 
Output: 30000 satoshis (0.300000 mBTC) to script: OP_DUP OP_HASH160 13ZsFbiWrDeyyBwwtFpmssA47Tv7v7tZNX OP_EQUALVERIFY OP_CHECKSIG 

At first glance it looks like the same transaction. In fact, transaction A and B both uses the same inputs to pay the same output the same amount. The only reason they have different hashes, and thus show up as two unique transactions, is a change to the signature on the second input.

Input signatures

Every transaction input has a signature field, and for standard transactions it contains two objects; a DER-encoded signature of the transaction, and the unhashed version of the public key the consumed output was originally sent to (only the actual signature is shown in the transactions above).

So what has changed between transaction A and transaction B.

• Second input to A:
  30460221008a162fbaf43f2f10db622d9443f89a50574f83d9c57b66dd14ec276130dafeec022100a013b18159b5737f0d7dec9f0e95815cd3cfd82e461baad6c42d37e93d55bb4001
• Second input to B:30450221008a162fbaf43f2f10db622d9443f89a50574f83d9c57b66dd14ec276130dafeec02205fec4e7ea64a8c80f2821360f16a7ea1e6df04b8692cf564fba526a392e0860101

The signature actually consists of two numbers, R and S, and they are encode as follows

• Signature: 0x30 <total length (one byte)> R(encoded) S(encoded) 0x01
• where the last byte is a signature hash code that isn't really part of the signature.
• R and S (encoded): 0x02 <length (one byte)> <actual number>

As we can see, R is unchanged whereas S has changed. Although there's a large number of valid ECDSA signatures for any given data (this helps avoid leaking information if you were to, say, sign the same data twice), you'd think creating a new signature required knowing the private key. There is however a quirk in how an ECDSA signature works allowing for two valid values of S in any signature, and crucially for this attack, the relationship between the two Ses is really simple. It turns out that for any valid ECDSA signature (with the particular parameters used in Bitcoin), the signature will still be valid if S is replaced with S' = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 - S.

In our case transaction A has Sa = 00a013b18159b5737f0d7dec9f0e95815cd3cfd82e461baad6c42d37e93d55bb40 and transaction B has Sb = fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 - Sa = 5fec4e7ea64a8c80f2821360f16a7ea1e6df04b8692cf564fba526a392e08601.

This is simple math, and basically something anyone can do. In fact, the way the signature is encoded is loosely enough defined to open up for countless modification that don't involve any math at all. For this particular transaction, it would for instance be possible to just strip the leading 0x00 from Sa, yielding the signature 30450221008a162fbaf43f2f10db622d9443f89a50574f83d9c57b66dd14ec276130dafeec0220..a013b18159b5737f0d7dec9f0e95815cd3cfd82e461baad6c42d37e93d55bb4001 and the transaction hash b5514b39d578be2c0889382930780ac33997571b4bb1611990f8e897380dcefb; a third unique but equivalent transaction. For a list all known ways to modify signatures without invalidating them, as well as the proposed fixes to the Bitcoin protocol, see BIP-0062.

Consequences and short term solutions

Even though transaction malleability doesn't change the essence of a transaction, and once one is confirmed by a miner, the other one(s) will be clearly invalid, the period of uncertainty before that happens can be quite a nuisance (essentially all versions of a transaction must be treated as equally valid/invalid as there's no way to tell which one was the original one, or which one will end up sticking). Naively implemented wallets (including mine at this point) can double count incoming transfers, messing up the account balance. Worse though, transactions made using the change output from a recent, not-yet-confirmed transaction, may turn out to be invalid if a miner confirms the modified transaction rather than the original.

Take for instance the following transaction proposed my wallet before the malleability issue above was settled (let's call this transaction C):

Transaction: 3e90b646873675f6728f7878484dda5f7693f66ccc0b0b30a0145f02d9d4797a, version 1

Input: tx b4f3c62159a222ea9eccf5d0f9057c555d0d519cfe580412c4c185c244d8bb30 (output index 0) => 13ZsFbiWrDeyyBwwtFpmssA47Tv7v7tZNX
Signature: 3046022100f5622225b11cd4ecc35625f9ebedfb4b10059941d41ab20f68b1bc60bd9a7c91022100ad99b6e367e830916abc20e71eb4dbfbe25251d6dd5c0724099c4db0f1a453f201

Output: 20000 satoshis (0.200000 mBTC) to script: OP_DUP OP_HASH160 1L9SmY5i3bQ17RJreX4CoJJJBrWK6oN5HF OP_EQUALVERIFY OP_CHECKSIG 

 

It's trying to use an output from transaction B to form a new transaction, something that would be considered valid by a significant fraction of the network (any node that saw transaction B before A), before eventually ending up being an invalid transaction once transaction A was mined, rendering transaction B invalid.

I could program the wallet to disregard outputs from transaction B, after all it knows which one was the original one, but that wouldn't stop miners from confirming transaction B if they happened to see that before A.

A better solution would probably be to keep track of all the modified versions of the original transaction, and create corresponding versions of any new transaction spending the outputs. Ideally these should then be forwarded to miners with compatible views of the world for inclusion in their next block, so miners who believe transaction B is the valid one are sent C as it stand above, while miners who think transaction A is the valid one are sent C(a), where the corresponding output of A is used instead of the one from B. This process might be hard to get accurate, but sending C(a) back to nodes that sent us A, while sending C(b) back to nodes that sent us B, will probably not be too far off. In any case, putting both versions of C out there will ensure that one is still valid once the network has decided on the A vs B situation.

With this solution implemented, the wallet should be able to function as normal even during malleability attacks like the one that's currently ongoing, without having to wait for protocol level improvements (like those proposed in BIP-0062). I'll write a new post on this topic once I have this functionality implemented and ready for testing.

Blockchain proof of existence, part 1

Despite the blockchain originally being designed as a ledger for a payment system, it is turning into much more. TØ, the Overstock subsidiary, has developed a way to represent financial assets as colored coins and recently reached a milestone when a hedge fund borrowed 10 million USD worth of stocks using their system. Others are using the fact that data written to the blockchain is all but impossible to modify once it's written. Small amounts of data can be written and, unless the blockchain at some point ceases to exist, it can always be read back exactly as it was written (there are potential attacks that can rewrite history, but they get harder fast as the data we care about gets older. For my use-case is, which is really long-term, I don't think these attacks are of any concern).

My current project is taking advantage of this fact, in combination with the fact that every block has a timestamp that is guaranteed to be within certain bounds and, like the data in the block, can't be changed once written. Thus, data included in a block can not only be read back correctly later, it can also be accurately (within a couple of hours) dated. In other words, if you write a piece of information to the blockchain, you can later prove to anyone that you knew that info at that time in the past.

Of course, once the information is written, anyone can read it. If that's not what you want, you're better of writing a cryptographic checksum of the information to the blockchain, keeping the raw data secret. When the time comes when you need to prove that the data existed at that point in the past, you share the original data, the method used to generate the checksum and the block where the checksum can be found, thereby proving that the data in question existed when that block was finalized (with the usual caveat that the algorithm used to generate the checksum must still be considered strong).

Bitcoin transactions

The blocks in the blockchain are made up by bitcoin transactions of various kinds. Most are transferring ownership of bitcoins between two or more parties. With the exception of the special coinbase transaction, every transaction has one or more inputs. A transaction doesn't need to have an output, but even transactions made with the purpose to put data in the block chain probably should have at least one. The reason for this is that the nature of the Bitcoin protocol is that every transactions spends all its inputs in full and any funds not going to an output can be collected by the miner of the block; unless you have an input containing the exact fee amount, you'll need a change output in the transaction.

Example bitcoin transactions

Even though payments are made to familiar looking bitcoin addresses (eg. 1QAsw4fsfq3MJdgiEGod3MxY9BY2EnTWEU), the inputs to a transaction don't technically come from an address, they come from previous transactions. Likewise, an address does not technically have any bitcoins in it, it has transaction outputs that are spendable with the private key corresponding to the address. Each output contains a script field that describes how the output can be spent, eg:

OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG

Bitcoin's scripting language can be used to program countless different behaviours, but most nodes will only forward a small subset of standard transactions. The script above is an example of a pay-to-pubkey-hash output, which is the most common type.

Alternative outputs and OP_RETURN  

There has been a lot discussion and controversy around how the Bitcoin protocol and the underlying blockchain should be used. The community is basically divided into two camps; those who want the protocol to be expanded and generalized to facilitate as many different use-cases as possible, likening it to the TCP and IP protocols that underpins the whole internet; and those who want to keep the protocol simple and reserve the blockchain for the Bitcoin currency it was originally intended for.

The Bitcoin Core implementation has tried to resolve the controversy by introducing a short list of standard transactions, including one intended for non-currency operations: the provably unspendable OP_RETURN output. This script allows for up to 40 bytes of arbitrary payload, opening up for alternative uses of the protocol without bloating the blockchain too much. The fact that the output is provably unspendable allows full nodes to prune it from their list of spendable outputs (which is usually kept in memory). At just 40 bytes, we won't be able to store much data in these outputs, but it's the perfect size to store a cryptographic checksum.

Wallets

When first starting out on this project, I imagined writing a small program able to send simple transactions with a little bit of payload would be almost trivial, especially considering that I had already implemented the whole network layer (of course, this whole exercise could have been completely trivial if I wasn't set on writing everything from scratch). As it turns out, forming valid Bitcoin transactions is a little more involved and doing it right requires the following:

1. A list of keys pairs, or better, a way to generate them on demand. It is considered bad practice to reuse keys so, at a minimum, a new change key is needed for every transaction.
2. Knowledge of transaction outputs spendable by those keys.
3. Being able to form valid and signed transactions, taking care to send the change to an address you're in control of.

Modern wallets tend to rely on hierarchical deterministic key derivation for the keys (BIP-0032, BIP-0043, BIP-0044), thus doing away with the hassle of keeping track of and backing up large amounts of unrelated keys. It's pretty straight forward to implement, and provided with a single seed it gives you an endless supply of fresh key pairs.

Part 2 turned out to be quite a bit of work, and essentially amounts to scanning through the whole blockchain and thus the entire history of Bitcoin. Conveniently the Bitcoin protocol provides something called Simplified Payment Verification that makes this achievable. I won't cover the details of this part of the protocol right now, but rather dedicate a separate blog post to that. The summary is that SPV makes it possible to cryptographically verify that the transactions you care about are recorded in the blockchain, while only downloading and verifying a tiny fraction of it.

First transaction

Once you have some spendable transaction outputs and addresses to send change to. Using the Hierarchical Deterministic Keys library I generated a BIP-0044 style Bitcoin account with a couple of external addresses

• Chain m/44'/0'/0'/0/0:
• Public key (compressed format):
  032d9850b19296fe1077f28a3c64d957f5242367dc6d42595b7ca7ca1aaed3dd1d
• Double hashed public key (first SHA256, then RIPEMD-160):
  66fb2649c17e60c4cd16a05c903a161a24aa11a6
• Base58 encoded public key hash (this is what's usually thought of as the address):
  1APWnkAgU5iaiJtz7Ga7i3pGA127oQnnTG
• Chain m/44'/0'/0'/0/1:
• Public key (compressed format): 02abab53af3804c090db8255cc4a6f2c8d3783a8d873db93d689135e39db358df0
• Double hashed public key (first SHA256, then RIPEMD-160):
  fe2927160e030613c119fbc68bc9ab0576f59118
• Base58 encoded public key hash (address):
  1QAsw4fsfq3MJdgiEGod3MxY9BY2EnTWEU

And a change address (this address is not in any way different the other two from a protocol perspective, it's just a BIP-0044 method of accounting) 

• Chain m/44'/0'/0'/1/0:
• Public key (compressed format): 02e4531becbd0b5f86b611fabe85a63f00cf8a2a1f9ff324f0afb084e192d4da56
• Double hashed public key (first SHA256, then RIPEMD-160):
  5ee70c467c5b2c35d2d08ef0d6d202b9c917b261
• Base58 encoded public key hash (address):
  19eoJXTS4gWk1ZAuaQji73JnBNZBhgkpGJ

I then funded my new wallet with 2 mBTC (milli-bitcoins -- about 50 US cents at current rates) by sending them to the first external address. This transaction (dfea6c60cdd3630965d8fc4d9a3090d6dc2b6a802492f7ef02d8b55ac4669bca) has two output, the first of which has

• Value: 200000 (satoshis)
• PkScript: OP_DUP OP_HASH160 66fb2649c17e60c4cd16a05c903a161a24aa11a6 OP_EQUALVERIFY OP_CHECKSIG

The script is a standard pay-to-pubkey-hash script, and the double hash of the first public key that was just generated (if you inspect the transaction on blockchain.info, you'll see the m/44'/0'/0'/0/0 key show up both in the base58 address format, and as a the hex encode hash). That key corresponds to the following private key that was generated as part of the same key pair, and as such, controlled by my wallet:

• private key (compressed Wallet Export Format):
  80107c9829b61c25851f5d5aa4e1e642eef64d1d995a1df1d46f632360a6dc0cb001 

 The new wallet is funded and ready to send a transaction of its own. 

This transaction will have two outputs, one sending 0.5 mBTC to fe2927160e030613c119fbc68bc9ab0576f59118, and one sending 1.4 mBTC to the change address 5ee70c467c5b2c35d2d08ef0d6d202b9c917b261. The remaining 0.1 mBTC of the input is not sent anywhere and is a fee that will be collected by whoever mines a block with our transaction in it (this is the incentive we give miners to actually include our transaction in a block).

With outputs added to the transaction we ready to include the input and prove that we own it:

• Previous output hash:
  dfea6c60cdd3630965d8fc4d9a3090d6dc2b6a802492f7ef02d8b55ac4669bca
• Previous output index: 0
• Signature: 30450220324de09f8f7c8908d4a4b99c13aa28d1a5b3b680a196e6e6d39255e2b4d126c802210089fed6635be470c33f717db1a44f89150ebad18ab511fcf176c959cef7a9c94201 
  032d9850b19296fe1077f28a3c64d957f5242367dc6d42595b7ca7ca1aaed3dd1d

The signature is the proof that this is an input we control as well as an insurance that our transaction is broadcast and recorded unmodified. The second part can be recognized as the (compressed, unhashed) public key of the address the previous transaction was sent to. The first part is the result of signing our transaction (a double SHA256 hash of a serialized version of it) with the the corresponding private key, using an Elliptic Curve Digital Signature Algorithm (ECDSA). The signature proves that we're in control of the relevant private key and, as the whole transaction, including the outputs, is signed, it prevents tampering with our transaction after it's sent.

And that's it. After broadcasting the transaction to a few connected nodes, it was quickly forwarded to the rest of the network, and can now be seen in places like blockchain.info. A few minutes later it was included in block 378726 mined by AntPool. Alongside the 735 other transactions in that block it's now forever recorded in the blockchain.

Next step and source code

The next step will be to send a transaction with a payload and have this data recorded in the blockchain.

If interested in the source code written so far, it can be found here.

Go synchronization primitives

Go comes with two categories of synchronization primitives, traditional locking mechanisms like mutexes, and channels. When implementing bitcoin-network I decided to, as an experiment, go solely with channels and not utilize any of the traditional synchronization primitives. This was somewhat elegant in some situations, but really painful in others. One of the better ones were a straightforward module that already relied heavily on channels, the message dispatcher (essentially a demux). This is a module that reads messages from a single input channel and based on their type, forwards them to a channel to that type's subscriber. The (simplified) main loop looks something like this:

for {

	msg, ok := <-d.input
	if !ok {
		break
	}
	ch, found := d.subscribers[msg.Type]
	if found {
		ch <- msg
	}
}

With d being the dispatcher object:
type Dispatcher struct {
	subscribers map[string]chan<- Message
	input       <-chan Message
}


As long as all the subscribers are added to the map before the main loop is started, this module doesn't seem to need any form of synchronization. The issues start surfacing when looking at the shut down process. As it stands above, the dispatcher module can be shut down cleanly by closing the input channel. However, we have no feedback on this shut down, making it impossible to know how to handle the outgoing channels after the input has been closed.

Closing a channel from the reader side has the risk of crashing if the writer is still active. Shutting down the reader without closing the channel runs the risk of blocking the writer, causing us to leak memory and threads. Unless we let the dispatcher take ownership of the outgoing channels (ie. close them when shutting down), we can only solve this by adding a "shut down" method that blocks (or otherwise signals completion). As it greatly simplifies the downstream code to allow reuse of channels, I chose to go with the second option.

A more flexible approach than a shut down method is an Unsubscribe() method that removes one type from the subscribe map. Since a map structure is not thread safe, and we're not using any locks, the removal needs to happen in the main loop. We can achieve this by introducing a new structure and couple of new internal channels:
type unsubscription struct {
	key  string
	done chan<- bool
}

func (d *Dispatcher) Unsubscribe(key string) {
	done := make(chan bool)
	d.unsub <- unsubscription{
		key:  key,
		done: done,
	}
	<-done
}

New main loop:
for {
	select {
	case s := <- d.unsub:
		delete(d.subscribers, s.key)
		s.done <- true

	case msg, ok := <-d.input:
		if !ok {
			break
		}
		ch, found := d.subscribers[msg.Type]
		if found {
			ch <- msg
		}
	}
}

A call of Unsubscribe() will now block until the operation has completed, and as all the work is being done in the main loop, we don't have to worry about races. After unsubscribing all the subscribed keywords, it will be safe to close the subscription channels or just shut down the readers on those channels. This technique works, but we can already tell that more complex modules are going to need a lot of plumbing to get it right (look at the main loops here or here for examples). Even in the relatively simple dispatcher module we can already get simpler and more efficient code by utilizing a sync.Mutex to protect the subscribers map.

Obviously, this was all sort of a contrived example and the learnings don't transfer to channels in general, which certainly have their place alongside the traditional locking mechanisms (https://github.com/golang/go/wiki/MutexOrChannel provides some advice on when to use either mechanism). It does however show that the traditional locks still have a place in Go and that channel shut-down can get complicated quickly.

Bitcoin peer to peer network

Bitcoin is based on a peer to peer network, where each peer, or node, verifies, stores and forwards the transactions taking place on the network. Some nodes, the miners, collect valid transactions into blocks and publish these. Each block references the previous block, thus creating a chain of them, the Blockchain. Although creating blocks is hard work and requires specialized hardware, anyone can subscribe to these blocks, then inspect and verify them.

By connecting to a node on the network, we can receive a stream of real-time transactions as well as the blocks being published as miners create them. For robustness and security, we should probably connect to several independent nodes, thus reducing the chance that transactions are being censored by malicious nodes, or dropped by a faulty one. Ensuring that we're well connected is far from trivial, so in this first pass we'll just connect to a handful of nodes and hope that they're not all colluding against us. Unresponsive or otherwise broken connections will be dropped and new ones created to replace them.

Implementation

I've written a simple implementation of this network layer based on the protocol documentation (refer to this for details on the various messages mentioned below, or terms that are unfamiliar). I chose Go as the implementation language, and as an experiment the code relies solely on channels for synchronization, which is elegant at times, but far from perfect. I'll write a separate blog post about interesting problems arising from these choices.

The code consist of two layers, the connection and the network. The former focuses on a setting up and maintaining a single connection, including sending and responding to pings. The latter will acquire the addresses of as many peers as possible, score the quality of them by various metrics and create and set up connections to a number of the best scoring ones. New peers' addresses are found by performing DNS look-ups, asking already connected peers by sending a getaddr message, or loading previously known peers from local storage. Usually this will quickly result in a pretty good overview of the network, with hundreds of nodes to chose between for connections.

Users of the library will get a channel to send messages on (either addressed messages or broadcasts) and the ability to subscribe to received messages by type. They don't have to worry about managing the connections and won't even be aware of the low level messages, with the exception of received version messages, that can be subscribed to by users who need to be aware of new peers being connected to (eg. because they want to address messages to them -- the example application included with the library will listen for version messages and send a mempool message to each new peer, thus initiating one or more inv messages containing transactions in the respective peer's mempool to be sent our way). This is a good starting point for beginning to write software interacting with the Bitcoin network.

Inspecting current connectivity

The example application contains a simple web server that can be used to see current connections as well as the applications view of the network. The page /peers on localhost:8080 list all known peers, with their connection status, address, time of last activity and a quality score.

Example peer list as seen on http://localhost:8080/peers:

(connected) 75.189.201.141:8333   2015-09-17 13:10:48.073832944 -0500 CDT Q(1000)
(connected) 73.162.143.196:8333   2015-09-17 13:10:42.964351941 -0500 CDT Q(1000)
(connected) 79.98.137.63:8333   2015-09-17 13:10:47.438899944 -0500 CDT Q(1000)
(spare)     52.11.33.24:8333   2015-09-17 13:10:32.825600001 -0500 CDT Q(800)
(pending)   50.147.76.86:8333   2015-09-17 13:10:32.825595045 -0500 CDT Q(800)
(spare)     69.143.149.38:8333   2015-09-17 13:10:32.825507889 -0500 CDT Q(800)
(pending)   24.52.35.44:8333   2015-09-17 13:10:32.695354838 -0500 CDT Q(800)
(spare)     54.153.97.109:8333   2015-09-17 13:10:32.825616717 -0500 CDT Q(800)
(spare)     25.96.107.191:8333   2015-09-17 11:08:03 -0500 CDT Q(678)

[...]
(spare)     71.93.135.167:8333   2015-09-17 05:02:53 -0500 CDT Q(313)
(spare)     155.133.19.109:8333   2015-09-17 05:00:28 -0500 CDT Q(310)
(failed)    50.177.196.160:8333, failed at 2015-09-17 13:10:43.100961354 -0500 CDT Q(300)
(failed)    173.69.49.106:8333, failed at 2015-09-17 13:10:42.699932334 -0500 CDT Q(300)
(failed)    198.38.93.227:8333, failed at 2015-09-17 13:10:42.700074666 -0500 CDT Q(300)
(spare)     68.238.62.169:8333   2015-09-17 04:49:01 -0500 CDT Q(299)
(spare)     72.241.129.31:8333   2015-09-15 16:09:59 -0500 CDT Q(0)
(spare)     84.104.142.12:8333   2015-09-09 23:23:42 -0500 CDT Q(0)
(spare)     87.220.72.124:8333   2015-08-20 08:24:59 -0500 CDT Q(0)

The application contains a simple In the example above there are 3 established connections, with 2 more pending. 3 nodes have had recent failures and are ranked lower because of this, while the rest are spares, ranked by the time of the last known activity from them (as seen by us, or as communicated by a peer in an addr message).