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

Bitcoin.BlockChain.TxLookup

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

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

Constructors

 NilList OneList !Word# TwoList !Word# !Word# ThrList !Word# !Word# !Word# FouList !Word# !Word# !Word# !Word# GenList !IndexList

Instances

 Source # Methodsrnf :: CompactList -> () #

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

 Source # Methodsrnf :: IndexList -> () #

newtype TxLookup Source #

Constructors

 TxLookup (IOArray Word32 CompactList)

# Build and use the TxLookup table

Builds a TxLookup table

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.

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.

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)

Checks a transaction given by its hash