Input Selection Algorithm (voting pools)
In order to avoid an expensive and error-prone consensus process, it is mandatory for wallets to be able to construct withdrawal transactions in a deterministic manner, assuming they are given the withdrawal requests in a deterministic order. Once this is accomplished, then it only becomes necessary for wallets to share signatures among themselves because they know they all signed the exact same bitcoin transaction.
One requirement to achieving this determinism is that the inputs used by the transaction construction algorithm are selected in a deterministic order.
The input selection algorithm generates an ordered list of eligible inputs for a withdrawal transaction. It is called from startwithdrawal with a set of three parameters:
- The first address identifier to be considered.
- The last series from which to select inputs.
- The minimum allowed input size.
The algorithm returns all inputs associated with the inclusive range given by inputstart and inputstop which are considered eligable, in a specific order.
An unspent output is considered eligible if it meets the following criteria:
- Its size is larger than dustthreshold
- The transaction in which it was created has more than 100 confirmations
The first criteria ensures the input will add more value to the transaction than the cost spend it in terms of fees.
The second ensures determinism.
Withdrawals are processed from the oldest deposits, in FIFO order and reuse of deposit addresses is not encouraged. However, it's not possible to prevent anyone from sending duplicate or unsolicited deposits to an address. The Duplicate Deposit procedure sweeps unsolicited deposits to their correct location, however at any given time it's not possible to ensure all nodes have performed this procedure at the exact same moment.
If the recommended values of weekly key rotation and 95% cold storage are followed, then the inputs being selected should have about 20000 confirmations (two orders of magnitude higher than the limit.)
By rejecting all inputs with less than 100 confirmations, the pool effectively has a 16 hour window in which to detect duplicate deposits and perform the duplicate deposit procedure before there is a risk of non-deterministic transaction construction.
When searching for addresses with eligible utxos to be used as inputs, the various parameters of the address identifier are incremented in the following order:
- branch (0 to n+1)
- index (0 to highest used for series)
- series (oldest to newest)
The returned inputs are sorted and returned in the same order: increasing by branch, index and series. If an address references more than one eligible inputs, they are all selected and are sorted by txid, then by output index.
If an address contains no eligible inputs, it is skipped.
In order for transaction signing to be successful, every wallet must create the exact same transactions, under all conditions. To achieve this, each wallet must create the transaction from the exact same set of inputs.
An individual wallet knows which series it has thawed, but it does not know what the rest of the wallets in the pool have thawed. The caller of the startwithdrawal API call is responsible for coordinating with other pool members to determine which series have been thawed by at least
m members of the pool, and then passing this series identifier explicitly.
The input selection algorithm must honor the provided
inputstop regardless of the state of a series (cold or thawed).
If this algorithm provides inputs from a series which this wallet has not yet thawed (but
n members of the pool have), then the transaction construction algorithm will use those inputs but will not be able to sign them. This is not a problem for the withdrawal because the pool does have enough signatures to make the affected transactions valid.