|
|
| (29 intermediate revisions by 3 users not shown) |
| Line 1: |
Line 1: |
| − | ==Introduction==
| + | #REDIRECT [[:Category:Transaction Construction 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.
| |
| − | | |
| − | ==Procedure==
| |
| − | | |
| − | ===Overview===
| |
| − | | |
| − | [[File:Transaction_Construction_Algorithm_-_Overview.png|500px|right|thumb]]
| |
| − | | |
| − | ====Initial Conditions====
| |
| − | | |
| − | The [[startwithdrawal]] 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:
| |
| − | | |
| − | # Gather accounting information from the API call arguments
| |
| − | # Validate and sort the output list
| |
| − | # Start a new transactions
| |
| − | # Add outputs to the transaction until either all outputs are added or all inputs are used.
| |
| − | # Make sure all generated transactions are ready for signing.
| |
| − | # Create a list of all signatures which the wallet is capable of generating.
| |
| − | # Create a status list containing the deposition of every output the caller specified.
| |
| − | # Return the status list and signature list to the caller. | |
| − | | |
| − | Each step in this chart is more fully described below.
| |
| − | | |
| − | {{clear}}
| |
| − | <hr>
| |
| − | | |
| − | ===Preparation===
| |
| − | | |
| − | [[File:Transaction_Construction_Algorithm_-_Preparation.png|175px|right|thumb]] | |
| − | | |
| − | ====Initial Conditions====
| |
| − | | |
| − | The [[startwithdrawal]] API call has been received by the wallet, and all the arguments have been checked for errors.
| |
| − | | |
| − | ====Sequence====
| |
| − | | |
| − | # The algorithm must keep track of the next change address to be used. The initial value is supplied as the <code>[[Startwithdrawal#Arguments|changestart]]</code> 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 <code>[[Withdrawal status|nextchangestart]]</code> value in the [[Withdrawal status| withdrawal status list]].
| |
| − | # Prepare an empty list for holding transactions as they are constructed and before they are signed.
| |
| − | # Prepare an empty array to hold the transaction signatures which will be returned to the caller as the <code>[[siglist| signatures]]</code> value.
| |
| − | # Prepare an <code>withdrawal status</code> object.
| |
| − | ## <code>roundID</code>: copied from <code>roundID</code> argument
| |
| − | ## <code>nextinputstart</code>: nil
| |
| − | ## <code>nextchangestart</code>: nil
| |
| − | ## <code>fees</code>: 0
| |
| − | ## <code>outputs</code>: should contain an entry for every output passed:
| |
| − | ### <code>outBailmentID</code>: copied from <code>outBailmentID</code> entry in <code>outputs</code> argument
| |
| − | ### <code>status</code>: empty string
| |
| − | ### <code>transactions</code>: nil
| |
| − | | |
| − | {{clear}}
| |
| − | <hr>
| |
| − | ===Output List Initialization===
| |
| − | | |
| − | [[File:Transaction_Construction_Algorithm_-_Output List Initialization.png|350px|right|thumb]]
| |
| − | | |
| − | ====Initial Conditions====
| |
| − | | |
| − | The [[startwithdrawal]] API call has been received by the wallet, and all the arguments have been checked for errors.
| |
| − | | |
| − | ====Sequence====
| |
| − | | |
| − | # 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.
| |
| − | ## Take the sum of both lists.
| |
| − | ## 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.
| |
| − | # If the output list is non-empty, sort it by <code>outBailmentID</code>
| |
| − | # 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.
| |
| − | | |
| − | {{clear}}
| |
| − | <hr>
| |
| − | ===Initialize New Transaction===
| |
| − | | |
| − | [[File:Transaction_Construction_Algorithm_-_Initialize New Transaction.png|175px|right|thumb]]
| |
| − | | |
| − | ====Initial Conditions====
| |
| − | | |
| − | There are no pending transactions to in the process of being constructed, either because this is the first transaction of the algorithm or because a previous pending transaction has been moved to the finished transaction list.
| |
| − | | |
| − | The input stack contains at least one input.
| |
| − | | |
| − | The output stack contains at least one output.
| |
| − | | |
| − | ====Sequence====
| |
| − | | |
| − | # Create a minimal transaction skeleton with a header and one change output.
| |
| − | ## The change output will be the last output of the transaction, but the number of other outputs in this transaction is not yet known.
| |
| − | ## The change output must be included in the skeleton for transaction size calculations.
| |
| − | ## The position index for the change output is nil.
| |
| − | ## The first non-change output for the transaction will be placed at position index 0.
| |
| − | | |
| − | After creating the transaction skeleton, and after any action which alters it, the new transaction size (bytes) and minimum required transaction fee must be recalculated.
| |
| − | | |
| − | {{clear}}
| |
| − | <hr>
| |
| − | | |
| − | ===Add Next Output===
| |
| − | | |
| − | [[File:Transaction_Construction_Algorithm_-_Add Next Output.png|500px|right|thumb]]
| |
| − | | |
| − | ====Initial Conditions====
| |
| − | | |
| − | The output stack contains at least one output.
| |
| − | | |
| − | There is a transaction in progress which is ready to accept new outputs. This transaction is either empty or it contains 1 or more outputs.
| |
| − | | |
| − | If the transaction already contains outputs, then it also contains sufficient inputs to cover those outputs and any required transaction fees without exceeding size limits. This is because it must have already successfully passed through this procedure before.
| |
| − | | |
| − | ====Sequence====
| |
| − | | |
| − | # Locate the entry for this output in the [[Withdrawal status|withdrawal status]] object by finding the corresponding outBailmentID.
| |
| − | # Validate the output address.
| |
| − | ## If it is invalid, update <code>status</code> entry for this output to "invalid" and exit from this procedure.
| |
| − | ## If it is valid, add it to the transaction.
| |
| − | ### Add a new entry to the <code>transaction</code> array for this output:
| |
| − | ###* <code>nxid</code>: nil
| |
| − | ###* <code>index</code>: next unused
| |
| − | ###* <code>amount</code>: copied from [[Outputs (Voting Pool Wallet API)|outputs]] list.
| |
| − | # Check that the transaction does not exceed size limits. If it does, follow the [[Transaction Construction Algorithm (voting pools)#Oversize Transaction|Oversize Transaction]] procedure.
| |
| − | # Compare the sum of the inputs to the sum of the inputs and required transaction fee to determine if more inputs are required.
| |
| − | ## If no more inputs are required, then update the <code>status</code> for this output to "success".
| |
| − | # If more inputs are required, then check to see if any more are available.
| |
| − | ## According to the initial conditions, the input stack can not be empty on the first run through this loop.
| |
| − | ## If the input stack is empty at this point, then the output has added at least one input beyond what was needed to satisfy the prior output (if there was a prior output)
| |
| − | ## If the input stack is empty, then the output can only be partially fulfilled. Follow the [[Transaction Construction Algorithm (voting pools)#Split Output|Split Output]] procedure.
| |
| − | # Add the next input from the stack, and continue the loop at step 2.
| |
| − | | |
| − | The loop will continue until either:
| |
| − | | |
| − | * The transaction contains sufficient input value to satisfy the output plus transaction fees
| |
| − | * The transaction exceeds size limits
| |
| − | * There is not enough input value, but no more inputs are available
| |
| − | | |
| − | {{clear}}
| |
| − | <hr>
| |
| − | | |
| − | ===Finalize Transaction===
| |
| − | | |
| − | [[File:Transaction Construction Algorithm - Finalize Transaction.png|500px|right|thumb]]
| |
| − | | |
| − | ====Initial Conditions====
| |
| − | | |
| − | * An unfinished transaction is ready for processing.
| |
| − | ** The transaction may or may not have have a useful (non-change) output
| |
| − | ** The transaction is valid
| |
| − | *** Not too big
| |
| − | *** Inputs are sufficient to cover outputs and required fees
| |
| − | ** A change output may exist in the transaction
| |
| − | *** If a change output exists, it is located in position 0 and has a nil value.
| |
| − | | |
| − | ====Sequence====
| |
| − | | |
| − | # If the transaction only contains a change output and no inputs, then it may be discarded.
| |
| − | # The change amount is calculated by: Σ(txin) - ( Σ(txout) + fees )
| |
| − | ## If the change amount is greater than zero:
| |
| − | ### Set the value of the output
| |
| − | ### Set the position of the output to the next unused value after the last non-change output.
| |
| − | ## If the change amount is zero, then the change output is removed from the transaction.
| |
| − | # Calculate an [[ntxid]] for the transaction for tracking purposes.
| |
| − | # Loop through every (non-change) output in the transaction and update the [[withdrawal status]] object for the corresponding output.
| |
| − | ## The withdrawal status object contain an entry for every output in the transaction, where each entry has an <code>transactions</code> object containing a nil <code>ntxid</code>, an <code>index</code> matching the output position index, and a matching <code>amount</code>.
| |
| − | ## Update the <code>nxid</code> value from nil to the ntxid for the transaction.
| |
| − | # Add the fees from this transaction to the <code>fees</code> property of the withdrawal status object.
| |
| − | # Move the transaction to the finished transaction list.
| |
| − | | |
| − | {{clear}}
| |
| − | <hr>
| |
| − | ===Update Signatures===
| |
| − | | |
| − | [[File:Transaction Construction Algorithm - Update Signatures.png|500px|right|thumb]]
| |
| − | | |
| − | {{clear}}
| |
| − | <hr>
| |
| − | ===Update Status===
| |
| − | | |
| − | [[File:Transaction Construction Algorithm - Update Status.png|500px|right|thumb]]
| |
| − | | |
| − | {{clear}}
| |
| − | <hr>
| |
| − | ===Oversize Transaction===
| |
| − | | |
| − | [[File:Transaction Construction Algorithm - Oversize Transaction.png|500px|right|thumb]]
| |
| − | | |
| − | {{clear}}
| |
| − | <hr>
| |
| − | ===Rollback Last Output===
| |
| − | | |
| − | [[File:Transaction Construction Algorithm - Rollback Last Output.png|500px|right|thumb]]
| |
| − | | |
| − | {{clear}}
| |
| − | <hr>
| |
| − | ===Split Output===
| |
| − | | |
| − | [[File:Transaction Construction Algorithm - Split Output.png|500px|right|thumb]]
| |
| − | | |
| − | {{clear}}
| |
| − | <hr>
| |
| − | ===Insufficient Inputs===
| |
| − | | |
| − | [[File:Transaction Construction Algorithm - Insufficient Inputs.png|500px|right|thumb]]
| |
| − | | |
| − | [[Category:Voting Pool Technical Specifications]]
| |
