Difference between revisions of "Input Selection Algorithm (voting pools)"

From Open Transactions
Jump to navigation Jump to search
(Example)
(Eligibility criteria: add flowchart)
 
(2 intermediate revisions by 2 users not shown)
Line 13: Line 13:
 
# The minimum allowed input size.
 
# 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.
+
The algorithm returns all inputs associated with the inclusive range given by inputstart and inputstop which are considered eligible, in a specific order.
 +
 
 +
<hr>
 +
 
 +
===Scanning Order===
 +
 
 +
<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/fc0c88a9-5769-4778-bb1c-fa7e7b3ab24f" width="350" height="1200" frameborder="0" scrolling="no" /></div>
 +
 
 +
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)
 +
# index (0 to highest used for series)
 +
# series (oldest to newest)
 +
 
 +
Note that the number of branches may vary from series to series because voting pool members may be added or removed when moving between series.
 +
 
 +
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.
 +
 
 +
{{clear}}
 +
<hr>
  
 
===Eligibility criteria===
 
===Eligibility criteria===
 +
 +
<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/929967ce-f5fb-4be7-ac08-eddc0500af35" width="200" height="1000" frameborder="0" scrolling="yes" /></div>
  
 
An unspent output is considered eligible if it meets the following criteria:
 
An unspent output is considered eligible if it meets the following criteria:
Line 21: Line 44:
 
* Its size is larger than dustthreshold
 
* Its size is larger than dustthreshold
 
* The transaction in which it was created has more than 100 confirmations
 
* The transaction in which it was created has more than 100 confirmations
 +
* The unspent output is not the [[charter output]]
  
 
The first criteria ensures the input will add more value to the transaction than the cost spend it in terms of fees.
 
The first criteria ensures the input will add more value to the transaction than the cost spend it in terms of fees.
Line 32: Line 56:
 
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.
 
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.
  
===Input Ordering===
+
{{clear}}
 
 
When moving from address to address, 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)
 
 
 
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.
 
  
 
==Determinism==
 
==Determinism==

Latest revision as of 17:09, 7 October 2014

Introduction

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.

Procedure

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:

  1. The first address identifier to be considered.
  2. The last series from which to select inputs.
  3. The minimum allowed input size.

The algorithm returns all inputs associated with the inclusive range given by inputstart and inputstop which are considered eligible, in a specific order.


Scanning Order

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:

  1. branch (0 to n)
  2. index (0 to highest used for series)
  3. series (oldest to newest)

Note that the number of branches may vary from series to series because voting pool members may be added or removed when moving between series.

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.


Eligibility criteria

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 unspent output is not the charter output

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.

Determinism

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 inputstart and 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 m-of-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.

Example