Iterative Channel Package Computation

Motivation

Nodes set fee rate restrictions as a mechanism to limit the size of their memory pools. The variability of these restrictions may prevent the propagation of transactions to miners which would accept these lesser fees. Packaging related transactions which together satisfy the restriction would allow the potential to overcome network bottlenecks. However, redundant signaling of transactions may lead to a waste of bandwidth. It is thus desirable to customize packages between peers to minimize such waste. The following proposes a mechanism of dynamically packaging related transactions in such a way that the fee rate would be acceptable to a receiving node and thus further the propagation of transactions with minimal data redundancy.

Computation from Canonical Transaction

Let $Bytes(t)$ be the byte count of transaction $t$. Let $Sigops(t)$ be the sigop count of transaction $t$. Let $Fee(t)$ be the fee available from transaction $t$. Let $b_{max}$ be the maximum bytes allowed in a package. Let $s_{max}$ be the maximum sigops allowed in a package.

Let $c$ be a channel. Let $R(c)$ be the feerate required by channel $c$. Let $Known_{c}(t)$ denote inclusion of transaction $t$ in the set of known transactions to channel $c$. Let $Confirmed(t)$ denote inclusion of transaction $t$ in the blockchain.

For each known channel $c \in C$ the following computation can be performed on notification of a new transaction $t$ to the memory pool.

Package(t, c):
    Let P_{t,c} be the potential canonical package of t to c, initially empty.
    Let f be the cumulative fee, initially zero.
    Let b be the cumulative bytes, initially zero.
    Let s be the cumulative sigops, initially zero.
    Let Visited_{t,c}(t_{v}) provide an indicator that a transaction has been
        traversed, initially all false.
    try
        Visit(t, t, c, &f, &b, &s, &P_{t,c})
    catch IMPOSSIBLE_PACKAGE
        return {}
    if (f / b >= R(c))
        return P_(t,c)

Visit(t_{origin}, t_{current}, c, f, b, s, P_{t_{origin},c}):
    if ((b_{max} < Bytes(t_{current}) + b) || (s_{max} < Sigops(t_{current}) + s))
        throw IMPOSSIBLE_PACKAGE

    b += Bytes(t_{current})
    s += Sigops(t_{current})
    f += Fee(t_{current})
    prepend t_{current} to the list P_{t_{origin},c}
    Visited_{t_{origin},c}(t_{current}) = true

    for each transaction input t_{input} of t_{current}
        if (!Visited_{t_{origin},c}(t_{input}) && !Known_{c}(t_{input}) &&
            !Confirmed(t_{input}))
            Visit(t_{origin}, t_{input}, c, f, b, s, P_{t_{origin},c})

The above provides a depth-first walk through the graph of transactions. By holding in a graph only those transactions in the memory pool, checking for confirmedness would be unnecessary.

Analysis

Assume $Known_{c}(t)$ is provided as a constant time lookup. For each channel, the cost of detecting a minimal canonical package for transaction $t$ is at most linear in the size of the subgraph of transactions not known to channel $c$ but known to the generating node within the bounds of its memory pool. Thus, for $n$ the number of transactions in the memory pool and $c$ the number of channels, $O(n * c)$ is a worst case time bound. Additionally, $O(n * c)$ size is required to contain $Known_{c}(t)$.

The above depends on $Known_{c}$ to minimally package for channel $c$. Initialization of $Known_{c}$ can be accomplished in the following ways:

1. Assume on connection that a peer is long running and contains our memory pool.
2. Rely upon memory pool synchronization to populate.
3. Upon channel creation, iterate the above algorithm for each transaction, starting with transactions whose parents are confirmed.

State Management

Upon reception of a transaction $t$ meeting our feerate from a channel $c$, the set of known transactions of the channel $Known_{c}$ shall be updated to reflect the knowledge of $t$ by $c$.