Safe Haskell | None |
---|---|
Language | Haskell98 |
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...
- toWord# :: Int -> Word#
- fromWord# :: Word# -> Int
- data CompactList
- toCompactList :: [Int] -> CompactList
- fromCompactList :: CompactList -> [Int]
- consCompactList :: Int -> CompactList -> CompactList
- data IndexList = IndexList !Word# IndexList
- intToBool# :: Int# -> Bool
- nullIndexList :: IndexList
- isNullIndexList :: IndexList -> Bool
- isSingletonIndexList :: IndexList -> Bool
- consIndexList :: Int -> IndexList -> IndexList
- toIndexList :: [Int] -> IndexList
- fromIndexList :: IndexList -> [Int]
- newtype TxLookup = TxLookup (IOArray Word32 CompactList)
- newEmptyTxLookup :: IO TxLookup
- insertIntoTxLookup' :: Word32 -> Int -> TxLookup -> IO ()
- txLookupList' :: Word32 -> TxLookup -> IO [Int]
- first24Bits :: Hash256 -> Word32
- insertIntoTxLookup :: Hash256 -> Int -> TxLookup -> IO ()
- txLookupList :: Hash256 -> TxLookup -> IO [Int]
- buildTxLookupTable :: ChainTable -> IO TxLookup
- txLookup :: ChainTable -> TxLookup -> Hash256 -> IO (Maybe (Int, Tx RawScript RawScript))
- txLookup_ :: ChainTable -> TxLookup -> Hash256 -> IO (Maybe (Tx RawScript RawScript))
- loadPrevTxs :: ChainTable -> TxLookup -> Tx a b -> IO (Tx (Tx RawScript RawScript, a) b)
- checkTx :: ChainTable -> TxLookup -> Tx RawScript RawScript -> IO (Either String Bool)
- checkTxByHash :: ChainTable -> TxLookup -> Hash256 -> IO (Either String Bool)
interal stuff
data CompactList Source #
A list which is more compact for a small number of elements
toCompactList :: [Int] -> CompactList Source #
fromCompactList :: CompactList -> [Int] Source #
consCompactList :: Int -> CompactList -> CompactList 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 ?!?!
intToBool# :: Int# -> Bool Source #
isNullIndexList :: IndexList -> Bool Source #
isSingletonIndexList :: IndexList -> Bool Source #
toIndexList :: [Int] -> IndexList Source #
fromIndexList :: IndexList -> [Int] Source #
first24Bits :: Hash256 -> Word32 Source #
Build and use the TxLookup
table
buildTxLookupTable :: ChainTable -> IO TxLookup Source #
Builds a 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