The Memory Pool

Where unconfirmed transactions go

1: 

module Mempool

A UTXO accessor that stores UTXO operations in memory. Deletes are stored as tombstones and adds are stored as key value pairs. The accessor methods first checks the in-memory table (a dictionary) for a match before going to the base/lower UTXO accessor. Basically, this is an addendum to the base UTXO set. Instead of modifying the base set, it keeps track of the recent differences.

If they become permanent, Commit writes them to the base UTXO set otherwise the accessor is simply discarded.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 

type MempoolUTXOAccessor(baseUTXO: IUTXOAccessor) =
    let table = new Dictionary<OutPoint, UTXO>(new OutpointCompare())
    // With LevelDB, I had iterators. A dictionary does not have a sorted iterator so I need to keep track
    // of the counts separately
    let counts = new Dictionary<byte[], int>(new HashCompare()) 

    let getOrDefault (hash: byte[]) = 
        let (f, count) = counts.TryGetValue(hash) // I wish there was a GetOrDefault instead of a TryGetValue
        if f then count else 0
    let deleteUTXO (outpoint: OutPoint) = 
        table.[outpoint] <- null
        let count = getOrDefault outpoint.Hash
        counts.[outpoint.Hash] <- count-1
    let addUTXO (outpoint: OutPoint) (utxo: UTXO) = 
        table.[outpoint] <- utxo
        let count = getOrDefault outpoint.Hash
        counts.[outpoint.Hash] <- count+1
        
    let getUTXO (outpoint: OutPoint) =
        let (f, utxo) = table.TryGetValue(outpoint)
        if f
        then 
            if utxo <> null 
            then Some(utxo)
            else 
                logger.DebugF "Cannot find outpoint %A" outpoint
                None
        else
            baseUTXO.GetUTXO outpoint
    let getCount (txHash: byte[]) =
        let (f, count) = counts.TryGetValue(txHash)
        if f 
        then count + baseUTXO.GetCount(txHash)
        else baseUTXO.GetCount(txHash)

    let commit() = // Write them for good
        table |> Seq.iter(fun kv ->
            let outpoint = kv.Key
            let utxo = kv.Value
            if utxo <> null 
            then baseUTXO.AddUTXO(outpoint, utxo)
            else baseUTXO.DeleteUTXO(outpoint)
        )
        table.Clear()
        counts.Clear()

    member x.Clear() = table.Clear()
    member x.Commit() = commit()

    interface IUTXOAccessor with
        member x.DeleteUTXO(outpoint) = deleteUTXO outpoint
        member x.AddUTXO(outpoint, txOut) = addUTXO outpoint txOut
        member x.GetUTXO(outpoint) = getUTXO outpoint
        member x.GetCount(txHash) = getCount txHash
        member x.Dispose() = table.Clear()

The memory pool receives transactions from the all the connected nodes. Many of them turn out to be invalid, most of the time because the output is already spent (double-spend). Sometimes though, the signatures are invalid altogether. In any case, it's important to check the transactions before they are accepted into the pool. When the application receives a new block, the memory pool gets revalidated and every invalid transaction gets booted out. In this case, it is because of a double-spend between the transactions in the block and the same one from the pool.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 

let txHash = hashFromHex "d4c7e1458bc7d7c54e90cc95117afd95a7498931cc2aa11e18ab0c52fc4cc512"
let checkScript (utxoAccessor: IUTXOAccessor) (tx: Tx): Option<unit> = 
    let x = 
        tx.TxIns 
            |> Seq.mapi (fun i txIn ->
                let scriptEval = new Script.ScriptRuntime(Script.computeTxHash tx i)
                let outpoint = txIn.PrevOutPoint
                let utxo = utxoAccessor.GetUTXO outpoint
                utxo |> Option.map (fun utxo -> scriptEval.Verify(txIn.Script, utxo.TxOut.Script))
                ) 
            |> Seq.toList |> Option.sequence 
            |> Option.map(fun x -> x.All(fun x -> x)) // tx succeeds if all scripts succeed
    (x.IsSome && x.Value) |> errorIfFalse "script failure"

let mempoolAccessor = new MempoolUTXOAccessor(utxoAccessor)
let nopWriter = new NopUndoWriter()

Validating a tx in the pool will update the mempool UTXO set that is built on top of the confirmed UTXO. But for the mempool, there is nothing to undo and therefore no need for an undo writer.

1: 
2: 
3: 
4: 
5: 
6: 

let validate (tx: Tx) =
    maybe {
        do! checkScript mempoolAccessor tx
        processUTXO mempoolAccessor nopWriter false mempoolHeight tx |> ignore
        return ()
    }

Revalidate builds a new pool and then flips the old one with the new one.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 

let revalidate () =
    mempoolAccessor.Clear()
    let newListTx = new List<byte[]>()
    let newMempool = new Dictionary<byte[], Tx>(new HashCompare())
    listTx <- listTx.Where(fun hash ->
        let tx = mempool.[hash]
        (validate tx).IsSome
        ).ToList()
    mempool <- listTx.Select(fun hash -> mempool.[hash]).ToDictionary(fun tx -> tx.Hash)
    logger.InfoF "Mempool has %d transactions" mempool.Count

let addTx tx = 
    try
        validate tx |> Option.iter(fun () ->
            listTx.Add(tx.Hash)
            mempool.Item(tx.Hash) <- tx
            broadcastToPeers.OnNext(new BitcoinMessage("tx", tx.ToByteArray()))
            logger.DebugF "Unconfirmed TX -> %s" (hashToHex tx.Hash)
            )
    with
    | ValidationException e -> ignore() // printfn "Invalid tx: %s" (hashToHex tx.Hash)

Message loop

The main message loop picks up

  • new inv messages. If the mempool doesn't have it, it will request for the tx data using getdata
  • tx data. It gets validated and then put into the pool
  • getdata. When another node ask for the details of a tx it doesn't have
  • mempool. The mempool message that triggers a full dump of the mempool as inv messages
  • revalidate
 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 

let processCommand (command: MempoolCommand) = 
    match command with
    | Revalidate (currentHeight, undoTxs) ->
        mempoolHeight <- currentHeight
        for txBlock in undoTxs do
        for tx in txBlock do
            listTx.Add(tx.Hash)
            mempool.Item(tx.Hash) <- tx
        revalidate()
    | Tx tx -> addTx tx
    | Inv (invVector, peer) -> 
        let newInvs = invVector.Invs |> List.filter(fun inv -> not (mempool.ContainsKey inv.Hash))
        newInvs |> List.iter (fun inv -> mempool.Add(inv.Hash, null))
        let gd = new GetData(newInvs)
        if not gd.Invs.IsEmpty then
            peer.Receive(GetData gd)
    | GetTx (invs, peer) ->
        for inv in invs do
            let (f, tx) = mempool.TryGetValue(inv.Hash)
            if f && tx <> null then
                peer.Send(new BitcoinMessage("tx", tx.ToByteArray()))
    | Mempool peer -> 
        let inv = mempool.Keys |> Seq.map (fun txHash -> InvEntry(txInvType, txHash)) |> Seq.toList
        logger.DebugF "MemoryPool %A" inv
        if not inv.IsEmpty then
            let invVec = InvVector(inv)
            peer.Send(new BitcoinMessage("inv", invVec.ToByteArray()))

let startMempool() =
    mempoolIncoming.ObserveOn(NewThreadScheduler.Default).Subscribe(processCommand) |> ignore
module Mempool
namespace System
namespace System.Linq
namespace System.Collections
namespace System.Collections.Generic
Multiple items
namespace System.Linq

--------------------
namespace Microsoft.FSharp.Linq
Multiple items
namespace System.Collections

--------------------
namespace Microsoft.FSharp.Collections
Multiple items
type Choice<'T1,'T2> =
  | Choice1Of2 of 'T1
  | Choice2Of2 of 'T2

Full name: Microsoft.FSharp.Core.Choice<_,_>

--------------------
type Choice<'T1,'T2,'T3> =
  | Choice1Of3 of 'T1
  | Choice2Of3 of 'T2
  | Choice3Of3 of 'T3

Full name: Microsoft.FSharp.Core.Choice<_,_,_>

--------------------
type Choice<'T1,'T2,'T3,'T4> =
  | Choice1Of4 of 'T1
  | Choice2Of4 of 'T2
  | Choice3Of4 of 'T3
  | Choice4Of4 of 'T4

Full name: Microsoft.FSharp.Core.Choice<_,_,_,_>

--------------------
type Choice<'T1,'T2,'T3,'T4,'T5> =
  | Choice1Of5 of 'T1
  | Choice2Of5 of 'T2
  | Choice3Of5 of 'T3
  | Choice4Of5 of 'T4
  | Choice5Of5 of 'T5

Full name: Microsoft.FSharp.Core.Choice<_,_,_,_,_>

--------------------
type Choice<'T1,'T2,'T3,'T4,'T5,'T6> =
  | Choice1Of6 of 'T1
  | Choice2Of6 of 'T2
  | Choice3Of6 of 'T3
  | Choice4Of6 of 'T4
  | Choice5Of6 of 'T5
  | Choice6Of6 of 'T6

Full name: Microsoft.FSharp.Core.Choice<_,_,_,_,_,_>

--------------------
type Choice<'T1,'T2,'T3,'T4,'T5,'T6,'T7> =
  | Choice1Of7 of 'T1
  | Choice2Of7 of 'T2
  | Choice3Of7 of 'T3
  | Choice4Of7 of 'T4
  | Choice5Of7 of 'T5
  | Choice6Of7 of 'T6
  | Choice7Of7 of 'T7

Full name: Microsoft.FSharp.Core.Choice<_,_,_,_,_,_,_>
val mutable listTx : List<byte []>

Full name: Mempool.listTx
Multiple items
type List<'T> =
  new : unit -> List<'T> + 2 overloads
  member Add : item:'T -> unit
  member AddRange : collection:IEnumerable<'T> -> unit
  member AsReadOnly : unit -> ReadOnlyCollection<'T>
  member BinarySearch : item:'T -> int + 2 overloads
  member Capacity : int with get, set
  member Clear : unit -> unit
  member Contains : item:'T -> bool
  member ConvertAll<'TOutput> : converter:Converter<'T, 'TOutput> -> List<'TOutput>
  member CopyTo : array:'T[] -> unit + 2 overloads
  ...
  nested type Enumerator

Full name: System.Collections.Generic.List<_>

--------------------
List() : unit
List(capacity: int) : unit
List(collection: IEnumerable<'T>) : unit
Multiple items
val byte : value:'T -> byte (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.byte

--------------------
type byte = Byte

Full name: Microsoft.FSharp.Core.byte
val mutable mempool : Dictionary<obj,obj>

Full name: Mempool.mempool
Multiple items
type Dictionary<'TKey,'TValue> =
  new : unit -> Dictionary<'TKey, 'TValue> + 5 overloads
  member Add : key:'TKey * value:'TValue -> unit
  member Clear : unit -> unit
  member Comparer : IEqualityComparer<'TKey>
  member ContainsKey : key:'TKey -> bool
  member ContainsValue : value:'TValue -> bool
  member Count : int
  member GetEnumerator : unit -> Enumerator<'TKey, 'TValue>
  member GetObjectData : info:SerializationInfo * context:StreamingContext -> unit
  member Item : 'TKey -> 'TValue with get, set
  ...
  nested type Enumerator
  nested type KeyCollection
  nested type ValueCollection

Full name: System.Collections.Generic.Dictionary<_,_>

--------------------
Dictionary() : unit
Dictionary(capacity: int) : unit
Dictionary(comparer: IEqualityComparer<'TKey>) : unit
Dictionary(dictionary: IDictionary<'TKey,'TValue>) : unit
Dictionary(capacity: int, comparer: IEqualityComparer<'TKey>) : unit
Dictionary(dictionary: IDictionary<'TKey,'TValue>, comparer: IEqualityComparer<'TKey>) : unit
val mutable mempoolHeight : int

Full name: Mempool.mempoolHeight
Multiple items
type NopUndoWriter =
  interface obj
  new : unit -> NopUndoWriter
  override Write : 'a * 'b * 'c -> unit

Full name: Mempool.NopUndoWriter

--------------------
new : unit -> NopUndoWriter
val x : NopUndoWriter
override NopUndoWriter.Write : 'a * 'b * 'c -> unit

Full name: Mempool.NopUndoWriter.Write
val ignore : value:'T -> unit

Full name: Microsoft.FSharp.Core.Operators.ignore
Multiple items
type OutpointCompare =
  interface obj
  new : unit -> OutpointCompare
  override Equals : left:'c * right:'d -> bool
  override GetHashCode : outpoint:'a -> 'b

Full name: Mempool.OutpointCompare

--------------------
new : unit -> OutpointCompare
type IEqualityComparer<'T> =
  member Equals : x:'T * y:'T -> bool
  member GetHashCode : obj:'T -> int

Full name: System.Collections.Generic.IEqualityComparer<_>
val x : OutpointCompare
override OutpointCompare.Equals : left:'c * right:'d -> bool

Full name: Mempool.OutpointCompare.Equals
val left : 'c
val right : 'd
type obj = Object

Full name: Microsoft.FSharp.Core.obj
Object.ReferenceEquals(objA: obj, objB: obj) : bool
override OutpointCompare.GetHashCode : outpoint:'a -> 'b

Full name: Mempool.OutpointCompare.GetHashCode
val outpoint : 'a
Multiple items
type MempoolUTXOAccessor =
  interface obj
  new : baseUTXO:obj -> MempoolUTXOAccessor
  override AddUTXO : outpoint:'d * txOut:'e -> unit
  member Clear : unit -> 'g
  member Commit : unit -> unit
  override DeleteUTXO : outpoint:'f -> unit
  override Dispose : unit -> 'a
  override GetCount : txHash:byte [] -> int
  override GetUTXO : outpoint:'b -> 'c option (requires equality and 'c : null)

Full name: Mempool.MempoolUTXOAccessor

--------------------
new : baseUTXO:obj -> MempoolUTXOAccessor
val baseUTXO : obj
val table : seq<obj>
val counts : Dictionary<byte [],int>
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
val getOrDefault : (byte [] -> int)
val hash : byte []
val f : bool
val count : int
Dictionary.TryGetValue(key: byte [], value: byref<int>) : bool
val deleteUTXO : ('a -> unit)
val addUTXO : ('a -> 'b -> unit)
val utxo : 'b
val getUTXO : ('a -> 'b option) (requires equality and 'b : null)
val utxo : 'b (requires equality and 'b : null)
union case Option.Some: Value: 'T -> Option<'T>
union case Option.None: Option<'T>
val getCount : (byte [] -> int)
val txHash : byte []
val commit : (unit -> unit)
module Seq

from Microsoft.FSharp.Collections
val iter : action:('T -> unit) -> source:seq<'T> -> unit

Full name: Microsoft.FSharp.Collections.Seq.iter
val kv : obj
val outpoint : obj
val utxo : obj
Dictionary.Clear() : unit
val x : MempoolUTXOAccessor
member MempoolUTXOAccessor.Clear : unit -> 'g

Full name: Mempool.MempoolUTXOAccessor.Clear
member MempoolUTXOAccessor.Commit : unit -> unit

Full name: Mempool.MempoolUTXOAccessor.Commit
override MempoolUTXOAccessor.DeleteUTXO : outpoint:'f -> unit

Full name: Mempool.MempoolUTXOAccessor.DeleteUTXO
val outpoint : 'f
override MempoolUTXOAccessor.AddUTXO : outpoint:'d * txOut:'e -> unit

Full name: Mempool.MempoolUTXOAccessor.AddUTXO
val outpoint : 'd
val txOut : 'e
override MempoolUTXOAccessor.GetUTXO : outpoint:'b -> 'c option (requires equality and 'c : null)

Full name: Mempool.MempoolUTXOAccessor.GetUTXO
val outpoint : 'b
override MempoolUTXOAccessor.GetCount : txHash:byte [] -> int

Full name: Mempool.MempoolUTXOAccessor.GetCount
override MempoolUTXOAccessor.Dispose : unit -> 'a

Full name: Mempool.MempoolUTXOAccessor.Dispose
val txHash : obj

Full name: Mempool.txHash
val checkScript : utxoAccessor:'a -> tx:'b -> Option<unit>

Full name: Mempool.checkScript
val utxoAccessor : 'a
val tx : 'b
module Option

from Microsoft.FSharp.Core
type unit = Unit

Full name: Microsoft.FSharp.Core.unit
val x : bool option
val mapi : mapping:(int -> 'T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.mapi
val i : int
val txIn : obj
val scriptEval : obj
val utxo : obj option
val map : mapping:('T -> 'U) -> option:'T option -> 'U option

Full name: Microsoft.FSharp.Core.Option.map
val toList : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.Seq.toList
val x : obj
property Option.IsSome: bool
property Option.Value: bool
val mempoolAccessor : MempoolUTXOAccessor

Full name: Mempool.mempoolAccessor
val nopWriter : NopUndoWriter

Full name: Mempool.nopWriter
val validate : tx:'a -> 'b

Full name: Mempool.validate
val tx : 'a
val revalidate : unit -> 'a

Full name: Mempool.revalidate
member MempoolUTXOAccessor.Clear : unit -> 'g
val newListTx : List<byte []>
val newMempool : obj
(extension) IEnumerable.Where<'TSource>(predicate: Func<'TSource,bool>) : IEnumerable<'TSource>
(extension) IEnumerable.Where<'TSource>(predicate: Func<'TSource,int,bool>) : IEnumerable<'TSource>
val tx : obj
(extension) IEnumerable.Select<'TSource,'TResult>(selector: Func<'TSource,'TResult>) : IEnumerable<'TResult>
(extension) IEnumerable.Select<'TSource,'TResult>(selector: Func<'TSource,int,'TResult>) : IEnumerable<'TResult>
Multiple items
property Dictionary.Count: int

--------------------
(extension) IEnumerable.Count<'TSource>() : int
(extension) IEnumerable.Count<'TSource>(predicate: Func<'TSource,bool>) : int
val addTx : tx:obj -> unit

Full name: Mempool.addTx
val iter : action:('T -> unit) -> option:'T option -> unit

Full name: Microsoft.FSharp.Core.Option.iter
List.Add(item: byte []) : unit
property Dictionary.Item: obj -> obj
val processCommand : command:'a -> 'b

Full name: Mempool.processCommand
val command : 'a
val filter : predicate:('T -> bool) -> list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.filter
val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not
Dictionary.ContainsKey(key: obj) : bool
val iter : action:('T -> unit) -> list:'T list -> unit

Full name: Microsoft.FSharp.Collections.List.iter
Dictionary.Add(key: obj, value: obj) : unit
Dictionary.TryGetValue(key: obj, value: byref<obj>) : bool
property Dictionary.Keys: Dictionary`2.KeyCollection<obj,obj>
val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map
val startMempool : unit -> unit

Full name: Mempool.startMempool