Difference between revisions of "Transaction Construction Algorithm (voting pools)"

From Open Transactions
Jump to navigation Jump to search
(Procedure: Add output list initialization section)
m (Sequence)
Line 65: Line 65:
 
====Sequence====
 
====Sequence====
  
# Pass the <code>inputstart</code>, <code>inputstop</code>, and <code>dustthreshold</code> parameters to the [[input selection algorithm]] to obtain an ordered list of eligible inputs.
+
# Pass the <code>inputstart</code>, <code>inputstop</code>, and <code>dustthreshold</code> parameters to the [[Input Selection Algorithm (voting pools)|input selection algorithm]] to obtain an ordered list of eligible inputs.
 
# Perform a first pass check to determine if the requested outputs exceed the size of the eligible inputs. Note that this check is only definitive in the case where the output sum is greater than the input sum. At this stage of the algorithm, the input sum exceeding the output sum does not prove that all outputs will be successfully created.
 
# Perform a first pass check to determine if the requested outputs exceed the size of the eligible inputs. Note that this check is only definitive in the case where the output sum is greater than the input sum. At this stage of the algorithm, the input sum exceeding the output sum does not prove that all outputs will be successfully created.
 
## Take the sum of both lists.
 
## Take the sum of both lists.

Revision as of 12:22, 17 September 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.

Procedure

Overview

Transaction Construction Algorithm - Overview.png

Initial Conditions

The getdepositscript API call has been received by the wallet, and all the arguments have been checked for errors.

Sequence

The basic flow of the procedure is:

  1. Gather accounting information from the API call arguments
  2. Validate and sort the output list
  3. Start a new transactions
  4. Add outputs to the transaction until either all outputs are added or all inputs are used.
  5. Make sure all generated transactions are ready for signing.
  6. Create a list of all signatures which the wallet is capable of generating.
  7. Create a status list containing the deposition of every output the caller specified.
  8. Return the status list and signature list to the caller.

Each step in this chart is more fully described below.


Preparation

Transaction Construction Algorithm - Preparation.png

Initial Conditions

The getdepositscript API call has been received by the wallet, and all the arguments have been checked for errors.

Sequence

  1. The algorithm must keep track of the next change address to be used. The initial value is supplied as the changestart argument. Any time a change output is allocated, the index value of the address identifier is incremented, and if a change output is remove from a transaction the index value is decremented. The final value will be returned to the caller as the nextchangestart value in the withdrawal status list.
  2. Prepare an empty list for holding transactions as they are constructed and before they are signed.
  3. Prepare an empty array to hold the transaction signatures which will be returned to the caller as the signatures value.
  4. Prepare an withdrawal status object.
    1. roundID: copied from roundID argument
    2. nextinputstart: nil
    3. nextchangestart: nil
    4. fees: 0
    5. outputs: should contain an entry for every output passed:
      1. outBailmentID: copied from outBailmentID entry in outputs argument
      2. status: empty string
      3. transactions: nil

Output List Initialization

Transaction Construction Algorithm - Output List Initialization.png

Initial Conditions

The getdepositscript API call has been received by the wallet, and all the arguments have been checked for errors.

Sequence

  1. Pass the inputstart, inputstop, and dustthreshold parameters to the input selection algorithm to obtain an ordered list of eligible inputs.
  2. Perform a first pass check to determine if the requested outputs exceed the size of the eligible inputs. Note that this check is only definitive in the case where the output sum is greater than the input sum. At this stage of the algorithm, the input sum exceeding the output sum does not prove that all outputs will be successfully created.
    1. Take the sum of both lists.
    2. If the sum of the outputs exceeds the sum of the inputs, remove outputs in descending size order until this is no longer true. Note this may result in the output list being an empty set.
  3. If the output list is non-empty, sort it by outBailmentID
  4. Move both the input lists and outputs lists into separate stacks by pushing them in reverse list order. The first input and first output should be on the top of their respective stacks.