bitcoin-hs-0.0.1: Partial implementation of the Bitcoin protocol (as of 2013)

Safe HaskellNone
LanguageHaskell98

Bitcoin.BlockChain.TxLookup

Contents

Description

An simple but relatively compact data structure for looking up transactions in the blockchain (TODO: replace these data structures by a better one...)

Blockchain stats (as of 2013):

  • block heigh currently ~270,000, so 20 bits for that is enough for a while, 23 enough for ever basically.
  • number of transaction is currently ~27,000,000 (2016 data: ~162 million)
  • average number of transactions per block is currently ~300-350 (2016: ~2000)

Idea: index into a large dense array by the first few (say 24 or 26) bits of the hash, then store a list (vector) of the possible block indices there. With 24 bit index there will be in average 2 blocks per tx, of course sometimes more sometimes less.

An IOArray -> 16M pointers, on 32 bit that is 64M 30 million entries tx-s => 30 million entries, for short lists approx 1 word/entry, so let's say 150-200M on 32 bit.

On 64 bit we have more memory so it's ok :)

2016 update: you will need more memory to store even 32 bits per transaction... The most compact estimation already gives 1+ gigs...

Synopsis

interal stuff

data CompactList Source #

A list which is more compact for a small number of elements

Instances

data IndexList Source #

Hack for a more compact list structure. Last element of the list has the highest bit set to 1. Empty list has all bits set to 1. Space consumption is 3 words per list entry instead of 5 for normal lists.

Note: compiling with -O1 seeems to create larger memory consumption than -O0 and -O2 ?!?!

Constructors

IndexList !Word# IndexList 

Instances

NFData IndexList Source # 

Methods

rnf :: IndexList -> () #

Build and use the TxLookup table

txLookup :: ChainTable -> TxLookup -> Hash256 -> IO (Maybe (Int, Tx RawScript RawScript)) Source #

Looks up a transaction by hash. First we check the TxLookup table, then we load the possible blocks (if any), parse them and check them for the given transaction. We also return the block height.

txLookup_ :: ChainTable -> TxLookup -> Hash256 -> IO (Maybe (Tx RawScript RawScript)) Source #

does not return the block height

loadPrevTxs :: ChainTable -> TxLookup -> Tx a b -> IO (Tx (Tx RawScript RawScript, a) b) Source #

Given a transaction, we load all the previous transactions from the disk (using the cache), and add them the Tx structure (abusing the parametrized script field). The result can then be fed to checkTransaction.

checkTx :: ChainTable -> TxLookup -> Tx RawScript RawScript -> IO (Either String Bool) Source #

Checks a transaction. Note: this automatically accepts coinbase transactions (does not check that that sum of reward and fees is the amount, since it has no access to the fees)

checkTxByHash :: ChainTable -> TxLookup -> Hash256 -> IO (Either String Bool) Source #

Checks a transaction given by its hash