Open Transactions - User contributions [en]

Talk:Keyset (voting pools)

2014-11-06T09:15:29Z

Larshesel:

I understand what an xpub is (an extended public key) but it might not be clear for the first time reader, maybe we should write that. Do we have a good reference on extended keys? I guess this might be the best: https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki#Extended_keys

[[User:Larshesel|Larshesel]] ([[User talk:Larshesel|talk]]) 08:36, 6 November 2014 (UTC):

I might just fail to remember. Does the auditors make the decision that a series should become active? Is the wallet supposed to know if a series is active or not? Since I don't see a way that the wallet is explicitly told, I assume the wallet is not to know this. That assumption is also reinforced by the fact that getdepositscript tells the wallet from which series it should create an address.

On the other hand, currently we have some assumptions in the code that we know which series is the active one (for instance, we're saving a bit saying if the series is active or not) and are starting to build further on this assumption, so it would be good to get clarified what the initial design idea was.

I can't tell right now if there are things in the wallet that actually *need* to know if a series is active or not. But if it did, it could enforce certain things, like not allowing getdepositscript to create deposit addresses for an inactive series, or eliminating the series id from the getdepositscript call entirely.

Update: [[User:Larshesel|Larshesel]] ([[User talk:Larshesel|talk]]) 09:15, 6 November 2014 (UTC):

Never mind - this is clearly spelled out elsewhere. The charter output defines the active series, and we can check if a series is active by looking for the charteroutput at the specified address. In that way we can provide relevant error messages etc.

Talk:Keyset (voting pools)

2014-11-06T08:36:02Z

Larshesel:

Talk:Asset contract (voting pools)

2014-10-16T08:01:51Z

Larshesel: Questions about the charter output

[[User:Larshesel|Larshesel]] ([[User talk:Larshesel|talk]]) 08:01, 16 October 2014 (UTC)

From this page:

Additionally, the charter output must be located in the first change output for the current series.

From http://opentransactions.org/wiki/index.php/Startwithdrawal:

The charter output for the pool is not located at the 0th change address for the given series, or the next series.

That seems to be contradictory. Where is the charter output located?

Further - what is the charter output life-cycle? In which series is it living?

Transaction Construction Algorithm (voting pools)

2014-10-03T09:38:13Z

Larshesel: Fix typo

==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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/eb960c32-71d4-4cfc-8f49-63a82b343608/0" width="300" height="1004" frameborder="0" scrolling="yes" /></div>

====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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/0dd5f7d6-8511-4440-a535-32ad8508d146" width="150" height="502" frameborder="0" scrolling="yes" /></div>

====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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/56b10d7d-bbd4-4590-8200-c837c5ad953c" width="450" height="800" frameborder="0" scrolling="yes" /></div>

====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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/506ed019-070c-44d6-b5e4-994169ab0704" width="150" height="450" frameborder="0" scrolling="yes" /></div>

====Initial Conditions====

* There are no pending transactions 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.

====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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/3e9b2758-338e-40f7-8fe2-e036fda68157" width="600" height="800" frameborder="0" scrolling="yes" /></div>

====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>ntxid</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 outputs 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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/79c726f4-9d4e-4a3c-bd20-6556099d24ab" width="300" height="1004" frameborder="0" scrolling="yes" /></div>

====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 has a nil position and 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>ntxid</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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/97025b62-3720-4810-ae85-5ae678031aed" width="600" height="1100" frameborder="0" scrolling="yes" /></div>

====Initial Conditions====

* The finished transaction list contains zero or more finalized transactions
* The transactions are valid in all respects except for missing signatures

====Sequence====

* If the finished transaction list is empty, the rest of the procedure can be skipped.
* Loop through each transaction.
** Within each transaction, loop through every input.
*** Within each input, loop through every pubkey in the [[redeem script]].
**** If the wallet possesses the private key corresponding to the pubkey, create the appropriate signature.
***** Add the signature to the transaction.
***** Add the signature to the [[siglist|signature list]] in the appropriate position.
* Move all transactions in the finished transaction list to the pending transaction database, where they will wait for additional signatures from other voting pool members.

{{clear}}
<hr>

===Update Status===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/b4dcbb56-3b87-4f56-b249-dfd4276c7cc4" width="300" height="800" frameborder="0" scrolling="yes" /></div>
====Initial Conditions====

* Every outBailmentID in the [[Outputs (Voting Pool Wallet API)|output]] list provided has a non-nil <code>status</code> value in the [[withdrawal status]] object.

====Sequence====

# Update the status for any split outBailments which exist:
## Split outBailments have more than one item in their <code>transactions</code> array and have an existing <code>status</code> value of "success".
## Change the <code>status</code> for all split outBailments from "success" to "split".
# Update the status for any partial outBailments which exist:
## Partial outBailments have existing <code>status</code> value of "partial-".
## Calculate the total missing value needed to satisfy the partial outputs.
## The missing value of an outBailment is the originally-requested size of the outBailment minus the sum of all outputs created to satisfy it (if any exist).
### Obtain a list of eligible inputs from the next un-thawed series and calculate their total value.
### If the eligible value of the next un-thawed series is greater than the total missing value, then the next un-thawed series is the target series.
#### If not, repeat the above process while keeping a running total of eligible value until a target series is located.
### Append the number of the target series to the <code>status</code> value for every partial series.
# Update the <code>nextinputstart</code> value.
## If the input stack is empty, <code>nextinputstart</code> is the first [[address identifier]] for the next un-thawed series.
## If the input stack is not empty, <code>nextinputstart</code> is the [[address identifier]] for the next input in the stack.

{{clear}}
<hr>

===Oversize Transaction===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/4abd7b4f-1079-48d7-af9d-d892433cd65a" width="300" height="400" frameborder="0" scrolling="yes" /></div>

An oversize transaction may occur while attempting to add inputs to satisfy an output which has been added to a transaction as part of the [[#Add Next Output|Add Next Output]] step.

Even with the worst case of high <code>m</code> and/or <code>n</code> values, inputs will never be large enough that a transaction can be oversized while attempting to add the first input to a transaction.

Oversize transactions will have one change output, at least one non-change output, and many inputs.

If an oversize has two or more non-change outputs, then Add Next Output was successful for the previous output. In this case, the transaction was valid before attempting to add the current output, so the current output should be removed from the current transaction and moved to the next one.

Otherwise, the transaction has become too large while adding its first non-change output. This can happen due to a series of small inputs, or a large output, or a combination of the two. In this case the [[outBailment]] can not be satisfied with a single transaction and must be split across multiple transactions.

====Initial Conditions====

* The Add Next Output procedure has created a transaction that exceeds size limits, in one of the following circumstances:
** Immediately upon adding an output to the transaction
*** The transaction contains other outputs which were added successfully. All inputs currently in the transaction are required to satisfy the previous output(s) before the output that failed.
** After adding the first input to the transaction to satisfy an output
*** The transaction contains other outputs which were added successfully. All inputs currently in the transaction are required to satisfy the previous output(s) before the output that failed.
** After having added at least one input to the transaction to satisfy an output without causing an oversize condition.
*** At least one of the inputs in this transaction are only required to satisfy the current output, not any previous outputs (if any exist).

====Procedure====

# Count the number of non-change outputs in the transaction.
# If the number exceeds one, follow the [[#Rollback Last Output|Rollback Last Output]] procedure.
# If the number is one, follow the [[#Split Output|Split Output]] procedure.
{{clear}}
<hr>

===Rollback Last Output===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/81fbb6f6-b150-4a06-915e-7633b05da9af" width="300" height="600" frameborder="0" scrolling="yes" /></div>

This procedure is used if a transaction has exceeded the size limit, and can be brought back under the limit by removing the most-recently added output and the inputs needed to support it from the transaction

The removed inputs and outputs will be added to the beginning of a new transaction.

This procedure will remove one more input than is required to bring the transaction below size limits, and then add exactly one more. This will always result in a valid transaction because the only way to reach this procedure is by having successfully completed at least one [[#Add Next Output|Add Next Output]] cycle for the current transaction prior to adding an output or input that pushes the transaction over the size limit.

====Initial Conditions====

* An oversize transaction contains one or more outputs and their supporting inputs which do not exceed transaction size limits, and one output which does not.
* The number of inputs which are solely dedicated to satisfying the most recently-added output (not required for previous outputs) may be zero or more.

====Sequence====

# Remove the most-recently added output from the transaction and return it to the output stack.
#* This will cause the output to be the first one added to the next transaction.
# Remove the most-recently added input from the transaction and return it to the input stack.
# If the sum of input values exceeds the sum of output values by an amount greater than the required transaction fee:
#* Continue removing inputs one at a time until the sum of the input values falls below the needed output + transaction fee value.
# Add the next input from the stack to the transaction.
# Perform the [[#Finalize Transaction|Finalize Transaction]] procedure.
# [[#Initialize Transaction|Initialize]] a new transaction.

{{clear}}
<hr>

===Split Output===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/c72ce59c-65c0-4a90-943a-c669bac5a737" width="300" height="1004" frameborder="0" scrolling="yes" /></div>

This procedure is used when, either due to a large output or small inputs, the inputs required to satisfy a single output can not fit within transaction size limits.

The outBailment will be split across two or more transactions.

====Initial Conditions====

* The transaction being constructed contains one change output, one non-change output, and many inputs.
* The transaction did not exceed any size limits until the most recent input was added.

====Sequence====

# Remove the change output from the transaction.
# Decrement the value of the <code>nextchangestart</code> property of the [[withdrawal status]] object.
# Determine if the transaction still exceeds size limits.
## If yes, then remove the most-recently added input.
# Update the value of the output in the transaction to be the sum of the inputs minus the required transaction fee.
# Make a copy of the [[Outputs (Voting Pool Wallet API)|outputs]] object corresponding to this outBailmentID.
# Update the <code>amount</code> field of the copied output by subtracting the value determined in step 4.
# Push this new output to the output stack.
# Update the <code>status</code> field for this outBailmentID in the [[withdrawal status]] object to "partial-".
# Perform the [[#Finalize Transaction|Finalize Transaction]] Procedure.
# [[#Initialize Transaction|Initialize]] a new transaction.

{{clear}}
<hr>

===Insufficient Inputs===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/9b471e6e-0a62-408a-ad0e-a5d7c491aa43" width="150" height="500" frameborder="0" scrolling="yes" /></div>

This procedure is followed when the [[#Output List Initialization|Output List Initialization]] step estimated that that the input list was sufficient to fulfill the valid outputs but, due to change and/or transaction fees, one or more outputs can not be fulfilled.

====Initial Conditions====

* [[#Add Next Output|Add Next Output]] has been completed successfully at least once.
* An empty transaction skeleton has been created.
* At least one output remains in the stack, but the input stack is empty.

====Sequence====

* Pop all outputs from the output stack and update their <code>status</code> property in the [[withdrawal status]] list to "partial-".

No further action is necessary. After completing this procedure the algorithm moves on to the [[#Finalize Transaction|Finalize Transaction]] procedure which will discard the empty transaction skeleton which would have otherwise contained the outputs which were processed in this procedure.

[[Category:Voting Pool Technical Specifications]]

Talk:Transaction Construction Algorithm (voting pools)

2014-10-03T09:33:04Z

Larshesel: Elaborate ntxid question

[[User:Larshesel|Larshesel]] ([[User talk:Larshesel|talk]]) 14:57, 26 September 2014 (UTC)

In the preparation step it is mentioned that we create a withdrawal status object which is referenced throughout the algorithm.

We add the roundID to this object, but it does not seem to be used anywhere. Is it needed at all?

[[User:Justusranvier|Justusranvier]] ([[User talk:Justusranvier|talk]]) 15:41, 26 September 2014 (UTC)

It's needed to match up withdrawalstatus objects with siglist objects.

[[User:Larshesel|Larshesel]] ([[User talk:Larshesel|talk]]) 08:58, 29 September 2014 (UTC)

In the output list initialization procedure we may return an empty output list if the smallest output is bigger than the sum of the inputs. What should happen if we return an empty output list? The next step (transaction initialization) seems to assume that it is not empty.

As there are no longer any ouputs we cannot make a transaction. I don't seem to find any error code that reflects this situation.

[[User:Justusranvier|Justusranvier]] ([[User talk:Justusranvier|talk]]) 12:49, 29 September 2014 (UTC)

Transaction Initialization does not depend on the size of the output list. If the transaction skeleton ends up not being used, then Finalize Transaction will discard it (first step).

Easiest way to see what happens is to just follow the steps with an empty output list and you'll find all the checks that handle it.

[[User:Larshesel|Larshesel]] ([[User talk:Larshesel|talk]]) 08:32, 3 October 2014 (UTC)

In the 'Output List Initialization' I don't think it's specified how to keep track of the outputs that are removed if sum(inputs) < sum(outputs). I would assume that we need to mark the output status in the withdrawal status object so the caller can take appropriate action?

[[User:Larshesel|Larshesel]] ([[User talk:Larshesel|talk]]) 09:23, 3 October 2014 (UTC)

In the 'Finalize Transaction' we create a ntxid which is used for tracking purposes. What kind of tracking purposes is that? I see it is used later to update the outbailment status to split if the outbailment has more than one ntxid.

What is ntxid an abbreviation for? Does it have other roles?

Transaction Construction Algorithm (voting pools)

2014-10-03T09:24:37Z

Larshesel: fix typing error

==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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/eb960c32-71d4-4cfc-8f49-63a82b343608/0" width="300" height="1004" frameborder="0" scrolling="yes" /></div>

====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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/0dd5f7d6-8511-4440-a535-32ad8508d146" width="150" height="502" frameborder="0" scrolling="yes" /></div>

====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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/56b10d7d-bbd4-4590-8200-c837c5ad953c" width="450" height="800" frameborder="0" scrolling="yes" /></div>

====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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/506ed019-070c-44d6-b5e4-994169ab0704" width="150" height="450" frameborder="0" scrolling="yes" /></div>

====Initial Conditions====

* There are no pending transactions 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.

====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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/3e9b2758-338e-40f7-8fe2-e036fda68157" width="600" height="800" frameborder="0" scrolling="yes" /></div>

====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 outputs 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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/79c726f4-9d4e-4a3c-bd20-6556099d24ab" width="300" height="1004" frameborder="0" scrolling="yes" /></div>

====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 has a nil position and 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>ntxid</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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/97025b62-3720-4810-ae85-5ae678031aed" width="600" height="1100" frameborder="0" scrolling="yes" /></div>

====Initial Conditions====

* The finished transaction list contains zero or more finalized transactions
* The transactions are valid in all respects except for missing signatures

====Sequence====

* If the finished transaction list is empty, the rest of the procedure can be skipped.
* Loop through each transaction.
** Within each transaction, loop through every input.
*** Within each input, loop through every pubkey in the [[redeem script]].
**** If the wallet possesses the private key corresponding to the pubkey, create the appropriate signature.
***** Add the signature to the transaction.
***** Add the signature to the [[siglist|signature list]] in the appropriate position.
* Move all transactions in the finished transaction list to the pending transaction database, where they will wait for additional signatures from other voting pool members.

{{clear}}
<hr>

===Update Status===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/b4dcbb56-3b87-4f56-b249-dfd4276c7cc4" width="300" height="800" frameborder="0" scrolling="yes" /></div>
====Initial Conditions====

* Every outBailmentID in the [[Outputs (Voting Pool Wallet API)|output]] list provided has a non-nil <code>status</code> value in the [[withdrawal status]] object.

====Sequence====

# Update the status for any split outBailments which exist:
## Split outBailments have more than one item in their <code>transactions</code> array and have an existing <code>status</code> value of "success".
## Change the <code>status</code> for all split outBailments from "success" to "split".
# Update the status for any partial outBailments which exist:
## Partial outBailments have existing <code>status</code> value of "partial-".
## Calculate the total missing value needed to satisfy the partial outputs.
## The missing value of an outBailment is the originally-requested size of the outBailment minus the sum of all outputs created to satisfy it (if any exist).
### Obtain a list of eligible inputs from the next un-thawed series and calculate their total value.
### If the eligible value of the next un-thawed series is greater than the total missing value, then the next un-thawed series is the target series.
#### If not, repeat the above process while keeping a running total of eligible value until a target series is located.
### Append the number of the target series to the <code>status</code> value for every partial series.
# Update the <code>nextinputstart</code> value.
## If the input stack is empty, <code>nextinputstart</code> is the first [[address identifier]] for the next un-thawed series.
## If the input stack is not empty, <code>nextinputstart</code> is the [[address identifier]] for the next input in the stack.

{{clear}}
<hr>

===Oversize Transaction===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/4abd7b4f-1079-48d7-af9d-d892433cd65a" width="300" height="400" frameborder="0" scrolling="yes" /></div>

An oversize transaction may occur while attempting to add inputs to satisfy an output which has been added to a transaction as part of the [[#Add Next Output|Add Next Output]] step.

Even with the worst case of high <code>m</code> and/or <code>n</code> values, inputs will never be large enough that a transaction can be oversized while attempting to add the first input to a transaction.

Oversize transactions will have one change output, at least one non-change output, and many inputs.

If an oversize has two or more non-change outputs, then Add Next Output was successful for the previous output. In this case, the transaction was valid before attempting to add the current output, so the current output should be removed from the current transaction and moved to the next one.

Otherwise, the transaction has become too large while adding its first non-change output. This can happen due to a series of small inputs, or a large output, or a combination of the two. In this case the [[outBailment]] can not be satisfied with a single transaction and must be split across multiple transactions.

====Initial Conditions====

* The Add Next Output procedure has created a transaction that exceeds size limits, in one of the following circumstances:
** Immediately upon adding an output to the transaction
*** The transaction contains other outputs which were added successfully. All inputs currently in the transaction are required to satisfy the previous output(s) before the output that failed.
** After adding the first input to the transaction to satisfy an output
*** The transaction contains other outputs which were added successfully. All inputs currently in the transaction are required to satisfy the previous output(s) before the output that failed.
** After having added at least one input to the transaction to satisfy an output without causing an oversize condition.
*** At least one of the inputs in this transaction are only required to satisfy the current output, not any previous outputs (if any exist).

====Procedure====

# Count the number of non-change outputs in the transaction.
# If the number exceeds one, follow the [[#Rollback Last Output|Rollback Last Output]] procedure.
# If the number is one, follow the [[#Split Output|Split Output]] procedure.
{{clear}}
<hr>

===Rollback Last Output===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/81fbb6f6-b150-4a06-915e-7633b05da9af" width="300" height="600" frameborder="0" scrolling="yes" /></div>

This procedure is used if a transaction has exceeded the size limit, and can be brought back under the limit by removing the most-recently added output and the inputs needed to support it from the transaction

The removed inputs and outputs will be added to the beginning of a new transaction.

This procedure will remove one more input than is required to bring the transaction below size limits, and then add exactly one more. This will always result in a valid transaction because the only way to reach this procedure is by having successfully completed at least one [[#Add Next Output|Add Next Output]] cycle for the current transaction prior to adding an output or input that pushes the transaction over the size limit.

====Initial Conditions====

* An oversize transaction contains one or more outputs and their supporting inputs which do not exceed transaction size limits, and one output which does not.
* The number of inputs which are solely dedicated to satisfying the most recently-added output (not required for previous outputs) may be zero or more.

====Sequence====

# Remove the most-recently added output from the transaction and return it to the output stack.
#* This will cause the output to be the first one added to the next transaction.
# Remove the most-recently added input from the transaction and return it to the input stack.
# If the sum of input values exceeds the sum of output values by an amount greater than the required transaction fee:
#* Continue removing inputs one at a time until the sum of the input values falls below the needed output + transaction fee value.
# Add the next input from the stack to the transaction.
# Perform the [[#Finalize Transaction|Finalize Transaction]] procedure.
# [[#Initialize Transaction|Initialize]] a new transaction.

{{clear}}
<hr>

===Split Output===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/c72ce59c-65c0-4a90-943a-c669bac5a737" width="300" height="1004" frameborder="0" scrolling="yes" /></div>

This procedure is used when, either due to a large output or small inputs, the inputs required to satisfy a single output can not fit within transaction size limits.

The outBailment will be split across two or more transactions.

====Initial Conditions====

* The transaction being constructed contains one change output, one non-change output, and many inputs.
* The transaction did not exceed any size limits until the most recent input was added.

====Sequence====

# Remove the change output from the transaction.
# Decrement the value of the <code>nextchangestart</code> property of the [[withdrawal status]] object.
# Determine if the transaction still exceeds size limits.
## If yes, then remove the most-recently added input.
# Update the value of the output in the transaction to be the sum of the inputs minus the required transaction fee.
# Make a copy of the [[Outputs (Voting Pool Wallet API)|outputs]] object corresponding to this outBailmentID.
# Update the <code>amount</code> field of the copied output by subtracting the value determined in step 4.
# Push this new output to the output stack.
# Update the <code>status</code> field for this outBailmentID in the [[withdrawal status]] object to "partial-".
# Perform the [[#Finalize Transaction|Finalize Transaction]] Procedure.
# [[#Initialize Transaction|Initialize]] a new transaction.

{{clear}}
<hr>

===Insufficient Inputs===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/9b471e6e-0a62-408a-ad0e-a5d7c491aa43" width="150" height="500" frameborder="0" scrolling="yes" /></div>

This procedure is followed when the [[#Output List Initialization|Output List Initialization]] step estimated that that the input list was sufficient to fulfill the valid outputs but, due to change and/or transaction fees, one or more outputs can not be fulfilled.

====Initial Conditions====

* [[#Add Next Output|Add Next Output]] has been completed successfully at least once.
* An empty transaction skeleton has been created.
* At least one output remains in the stack, but the input stack is empty.

====Sequence====

* Pop all outputs from the output stack and update their <code>status</code> property in the [[withdrawal status]] list to "partial-".

No further action is necessary. After completing this procedure the algorithm moves on to the [[#Finalize Transaction|Finalize Transaction]] procedure which will discard the empty transaction skeleton which would have otherwise contained the outputs which were processed in this procedure.

[[Category:Voting Pool Technical Specifications]]

Talk:Transaction Construction Algorithm (voting pools)

2014-10-03T09:23:51Z

Larshesel: what is the purpose of ntxid?

Talk:Transaction Construction Algorithm (voting pools)

2014-10-03T08:32:42Z

Larshesel: Output list initialization - what to do with removed outputs

Input Selection Algorithm (voting pools)

2014-10-02T08:22:51Z

Larshesel: /* Input Ordering */

Talk:Input Selection Algorithm (voting pools)

2014-10-01T10:21:55Z

Larshesel: Addendum to bonus question

[[User:Larshesel|Larshesel]] ([[User talk:Larshesel|talk]]) 09:08, 1 October 2014 (UTC)

I don't understand the part about moving from address to address in the 'Input Ordering' section. I suppose it is meant to specify an ordering?

So the entire ordering would be by branch/index/series/txid/outputidx. For the addresses with only one output the last two parts of the ordering scheme are not necessary.

[[User:Larshesel|Larshesel]] ([[User talk:Larshesel|talk]]) 09:38, 1 October 2014 (UTC)

Bonus quesion

I would expect that when I am searching for eligible inputs, the (voting pool), series and branch are fixed and I only ever change the index number. Is that the case?

[[User:Larshesel|Larshesel]] ([[User talk:Larshesel|talk]]) 10:21, 1 October 2014 (UTC)

I think I've started to use this wiki as my rubber duck :-) It at least appears that asking questions here helps me understand.

The bonus question - I somehow had a notion that the series and branch should be fixed. But we want to use any eligible output we can get our hands on. Therefore it makes sense to look for any eligible input in the *hot* series - all branches and all indexes.

But if the moving from address to address part of the 'Input Ordering' sections is supposed to describe how we search the space of eligible inputs, then the 3rd item does not make sense as there is only one series to select addresses from - the hot one, since the other series cannot be used for spending as the private keys are not online yet.

Could we split 'how we search' and 'how the output should be ordered' into two distinct sections? The second can refer to the first, if it's the same ordering, but then it's explicit.

Talk:Input Selection Algorithm (voting pools)

2014-10-01T09:38:31Z

Larshesel: How to search for inputs

Talk:Input Selection Algorithm (voting pools)

2014-10-01T09:08:59Z

Larshesel: Question about input ordering

Transaction Construction Algorithm (voting pools)

2014-10-01T06:53:16Z

Larshesel: /* Initial Conditions */

==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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/eb960c32-71d4-4cfc-8f49-63a82b343608/0" width="300" height="1004" frameborder="0" scrolling="yes" /></div>

====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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/0dd5f7d6-8511-4440-a535-32ad8508d146" width="150" height="502" frameborder="0" scrolling="yes" /></div>

====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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/56b10d7d-bbd4-4590-8200-c837c5ad953c" width="450" height="800" frameborder="0" scrolling="yes" /></div>

====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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/506ed019-070c-44d6-b5e4-994169ab0704" width="150" height="450" frameborder="0" scrolling="yes" /></div>

====Initial Conditions====

* There are no pending transactions 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.

====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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/3e9b2758-338e-40f7-8fe2-e036fda68157" width="600" height="800" frameborder="0" scrolling="yes" /></div>

====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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/79c726f4-9d4e-4a3c-bd20-6556099d24ab" width="300" height="1004" frameborder="0" scrolling="yes" /></div>

====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 has a nil position and 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===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/97025b62-3720-4810-ae85-5ae678031aed" width="600" height="1100" frameborder="0" scrolling="yes" /></div>

====Initial Conditions====

* The finished transaction list contains zero or more finalized transactions
* The transactions are valid in all respects except for missing signatures

====Sequence====

* If the finished transaction list is empty, the rest of the procedure can be skipped.
* Loop through each transaction.
** Within each transaction, loop through every input.
*** Within each input, loop through every pubkey in the [[redeem script]].
**** If the wallet has possesses the private key corresponding to the pubkey, create the appropriate signature.
***** Add the signature to the transaction.
***** Add the signature to the [[siglist|signature list]] in the appropriate position.
* Move all transactions in the finished transaction list to the pending transaction database, where they will wait for additional signatures from other voting pool members.

{{clear}}
<hr>

===Update Status===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/b4dcbb56-3b87-4f56-b249-dfd4276c7cc4" width="300" height="800" frameborder="0" scrolling="yes" /></div>
====Initial Conditions====

* Every outBailmentID in the [[Outputs (Voting Pool Wallet API)|output]] list provided has a non-nil <code>status</code> value in the [[withdrawal status]] object.

====Sequence====

# Update the status for any split outBailments which exist:
## Split outBailments have more than one item in their <code>transactions</code> array and have an existing <code>status</code> value of "success".
## Change the <code>status</code> for all split outBailments from "success" to "split".
# Update the status for any partial outBailments which exist:
## Partial outBailments have existing <code>status</code> value of "partial-".
## Calculate the total missing value needed to satisfy the partial outputs.
## The missing value of an outBailment is the originally-requested size of the outBailment minus the sum of all outputs created to satisfy it (if any exist).
### Obtain a list of eligible inputs from the next un-thawed series and calculate their total value.
### If the eligible value of the next un-thawed series is greater than the total missing value, then the next un-thawed series is the target series.
#### If not, repeat the above process while keeping a running total of eligible value until a target series is located.
### Append the number of the target series to the <code>status</code> value for every partial series.
# Update the <code>nextinputstart</code> value.
## If the input stack is empty, <code>nextinputstart</code> is the first [[address identifier]] for the next un-thawed series.
## If the input stack is not empty, <code>nextinputstart</code> is the [[address identifier]] for the next input in the stack.

{{clear}}
<hr>

===Oversize Transaction===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/4abd7b4f-1079-48d7-af9d-d892433cd65a" width="300" height="400" frameborder="0" scrolling="yes" /></div>

An oversize transaction may occur while attempting to add inputs to satisfy an output which has been added to a transaction as part of the [[#Add Next Output|Add Next Output]] step.

Even with the worst case of high <code>m</code> and/or <code>n</code> values, inputs will never be large enough that a transaction can be oversized while attempting to add the first input to a transaction.

Oversize transactions will have one change output, at least one non-change output, and many inputs.

If an oversize has two or more non-change outputs, then Add Next Output was successful for the previous output. In this case, the transaction was valid before attempting to add the current output, so the current output should be removed from the current transaction and moved to the next one.

Otherwise, the transaction has become too large while adding its first non-change output. This can happen due to a series of small inputs, or a large output, or a combination of the two. In this case the [[outBailment]] can not be satisfied with a single transaction and must be split across multiple transactions.

====Initial Conditions====

* The Add Next Output procedure has created a transaction that exceeds size limits, in one of the following circumstances:
** Immediately upon adding an output to the transaction
*** The transaction contains other outputs which were added successfully. All inputs currently in the transaction are required to satisfy the previous output(s) before the output that failed.
** After adding the first input to the transaction to satisfy an output
*** The transaction contains other outputs which were added successfully. All inputs currently in the transaction are required to satisfy the previous output(s) before the output that failed.
** After having added at least one input to the transaction to satisfy an output without causing an oversize condition.
*** At least one of the inputs in this transaction are only required to satisfy the current output, not any previous outputs (if any exist).

====Procedure====

# Count the number of non-change outputs in the transaction.
# If the number exceeds one, follow the [[#Rollback Last Output|Rollback Last Output]] procedure.
# If the number is one, follow the [[#Split Output|Split Output]] procedure.
{{clear}}
<hr>

===Rollback Last Output===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/81fbb6f6-b150-4a06-915e-7633b05da9af" width="300" height="600" frameborder="0" scrolling="yes" /></div>

This procedure is used if a transaction has exceeded the size limit, and can be brought back under the limit by removing the most-recently added output and the inputs needed to support it from the transaction

The removed inputs and outputs will be added to the beginning of a new transaction.

This procedure will remove one more input than is required to bring the transaction below size limits, and then add exactly one more. This will always result in a valid transaction because the only way to reach this procedure is by having successfully completed at least one [[#Add Next Output|Add Next Output]] cycle for the current transaction prior to adding an output or input that pushes the transaction over the size limit.

====Initial Conditions====

* An oversize transaction contains one or more outputs and their supporting inputs which do not exceed transaction size limits, and one output which does not.
* The number of inputs which are solely dedicated to satisfying the most recently-added output (not required for previous outputs) may be zero or more.

====Sequence====

# Remove the most-recently added output from the transaction and return it to the output stack.
#* This will cause the output to be the first one added to the next transaction.
# Remove the most-recently added input from the transaction and return it to the input stack.
# If the sum of input values exceeds the sum of output values by an amount greater than the required transaction fee:
#* Continue removing inputs one at a time until the sum of the input values falls below the needed output + transaction fee value.
# Add the next input from the stack to the transaction.
# Perform the [[#Finalize Transaction|Finalize Transaction]] procedure.
# [[#Initialize Transaction|Initialize]] a new transaction.

{{clear}}
<hr>

===Split Output===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/c72ce59c-65c0-4a90-943a-c669bac5a737" width="300" height="1004" frameborder="0" scrolling="yes" /></div>

This procedure is used when, either due to a large output or small inputs, the inputs required to satisfy a single output can not fit within transaction size limits.

The outBailment will be split across two or more transactions.

====Initial Conditions====

* The transaction being constructed contains one change output, one non-change output, and many inputs.
* The transaction did not exceed any size limits until the most recent input was added.

====Sequence====

# Remove the change output from the transaction.
# Decrement the value of the <code>nextchangestart</code> property of the [[withdrawal status]] object.
# Determine if the transaction still exceeds size limits.
## If yes, then remove the most-recently added input.
# Update the value of the output in the transaction to be the sum of the inputs minus the required transaction fee.
# Make a copy of the [[Outputs (Voting Pool Wallet API)|outputs]] object corresponding to this outBailmentID.
# Update the <code>amount</code> field of the copied output by subtracting the value determined in step 4.
# Push this new output to the output stack.
# Update the <code>status</code> field for this outBailmentID in the [[withdrawal status]] object to "partial-".
# Perform the [[#Finalize Transaction|Finalize Transaction]] Procedure.
# [[#Initialize Transaction|Initialize]] a new transaction.

{{clear}}
<hr>

===Insufficient Inputs===

<div style="float: right"><include iframe src="https://www.lucidchart.com/documents/embeddedchart/9b471e6e-0a62-408a-ad0e-a5d7c491aa43" width="150" height="500" frameborder="0" scrolling="yes" /></div>

This procedure is followed when the [[#Output List Initialization|Output List Initialization]] step estimated that that the input list was sufficient to fulfill the valid outputs but, due to change and/or transaction fees, one or more outputs can not be fulfilled.

====Initial Conditions====

* [[#Add Next Output|Add Next Output]] has been completed successfully at least once.
* An empty transaction skeleton has been created.
* At least one output remains in the stack, but the input stack is empty.

====Sequence====

* Pop all outputs from the output stack and update their <code>status</code> property in the [[withdrawal status]] list to "partial-".

No further action is necessary. After completing this procedure the algorithm moves on to the [[#Finalize Transaction|Finalize Transaction]] procedure which will discard the empty transaction skeleton which would have otherwise contained the outputs which were processed in this procedure.

[[Category:Voting Pool Technical Specifications]]

Talk:Transaction Construction Algorithm (voting pools)

2014-09-29T08:58:03Z

Larshesel: What happens if the output list initialization procedure returns an empty output list

Talk:Transaction Construction Algorithm (voting pools)

2014-09-26T14:57:21Z

Larshesel: Is roundID necessary in the algorithm?

Talk:Withdrawal status

2014-09-24T12:12:58Z

Larshesel:

LARS:
I've seen the exclusiveMinimum boolean in several of the json objects. What does it mean? Can we maybe create some page where the different kind of common attributes are defined?

----

All the json schema information I got from this site: http://json-schema.org/example1.html

[[User:Justusranvier|Justusranvier]] ([[User talk:Justusranvier|talk]]) 12:08, 24 September 2014 (UTC)

---

Lars: That makes sense. It specifies if we're talking about an open or a closed set.

Talk:Withdrawal status

2014-09-24T08:26:49Z

Larshesel: Created page with "LARS: I've seen the exclusiveMinimum boolean in several of the json objects. What does it mean? Can we maybe create some page where the different kind of common attributes are..."

LARS:
I've seen the exclusiveMinimum boolean in several of the json objects. What does it mean? Can we maybe create some page where the different kind of common attributes are defined?

Keyset (voting pools)

2014-09-22T13:03:12Z

Larshesel: Make it explicit that it is the private keys that are online

==Keysets==

The multisig structure of a pool is called the keyset definition and is expressed in XML and stored in the OT asset contract:

<pre>
<pool id=”uuid” version=”1”>
<blockchain>bitcoin</blockchain>
<color>0</color>
<members>
<server id=”server_id_y” />
<server id=”server_id_z” />
<server id=”server_id_w” />
</members>
<keyset schedule=”x” m=”u” n=”v”>
<series number=”1”>
<key server=”server_id_y”>xpub_y1</key>
<key server=”server_id_z”>xpub_z1</key>
<key server=”server_id_w”>xpub_w1</key>
</series>
<series number=”2”>
<key server=”server_id_y”>xpub_y2</key>
<key server=”server_id_z”>xpub_z2</key>
<key server=”server_id_w”>xpub_w2</key>
</series>
</keyset>
</pool></pre>

In the above example there are three servers, y, z, and w. All decisions made by the pool must be signed by u of v members of the pool. Every server contributes a different xpub for each series defined in the keyset.

Each pool must explicitly define the crypto-currency being managed by the pool, and whether to treat the deposits as regular units or as colored units.

Regular pools have a <color> value of 0. Colored coin pools are designated by including a [[color definition]] in the <color> section.

Pool definitions are versioned for future extendibility.

x is time interval expressed in [http://www.nncron.ru/help/EN/working/cron-format.htm Cron] format, either a semicolon-separated list of column values, or one of the [http://en.wikipedia.org/wiki/Cron#Predefined_scheduling_definitions predefined patterns]. The default and recommended schedule is “@weekly”.

===Series===

[[File:Voting_Pools_Series_Progression.png|800px]]

The keyset contains a list of series numbers, each one of which contains an [[xpub]] for every member of the pool.

Series numbers are always monotonic (strictly increasing).

Series numbers are incremented on a schedule, shown above as “x”.

All series rotations are calculated based on UTC time.

At any given time, one series is “active”. This is the series containing the keys which will be used to create deposit and change addresses. Pool members will “fill up” this series with deposits until the next series rotation, then will begin filling up the next series.

At any given time, one series is “hot”. The hot series is the one whose private keys are online and is currently being used to process withdrawals. All series between the hot series and the active series are inactive. Slightly before the hot series is depleted of unspent outputs (to avoid withdrawal delays) the private keys for the next inactive series are brought online and that series becomes the new hot series.

Each series can be subdivided into two sub-series. The deposit series consists of n lists of deposit addresses, one for each member of the pool. The change series is a list of change outputs from previous withdrawal transactions.

[[Category:Voting Pool Technical Specifications]]

Voting Pool Deposit Process

2014-09-22T12:37:43Z

Larshesel: Fix bad link to Getdepositscript

==Procedure==

===Initiation===

[[File:Voting_Pools_Inbailment_Procedure-01.png|800px]]

Customers will normally request a deposit address by interacting with the service front end web site or some other software application. When the service receives such a request, it notifies the OT client via the OT client API function: <code>[[request_bailment]]</code>.

When the OT client receives notice of a user desire to deposit funds to a voting pool, via any method, it sends a <code>[[bailment]]</code> transaction request to the transaction server to initiate the deposit process.

The transaction server validates this request, and replies with a signed receipt. A copy of this receipt is broadcasted to the <code>[[audit stream]]</code>, and another copy is stored inside an <code>[[initiatedBailment]]</code> notice that’s placed in the user’s inbox. The transaction server adds this association to a [[deposit database]] for future reference.

===Payment script generation===

[[File:Voting_Pools_Inbailment_Procedure-02.png|800px]]

When an audit server validates the transaction server’s reply to the <code>bailment</code> message from the transaction server to which it is assigned, it adds the receipt identifier to its <code>[[deposit database]]</code> and calls <code>[[Getdepositscript|getdepositscript]]</code> via the websocket interface to the blockchain wallet, using the address identifier for the next unused deposit address.

The wallet calculates and returns the designated [[Deposit Address (voting pools)|deposit address]] as [[P2SH]] output script. The audit server uses this information to update the deposit database, and to assemble and sign a <code>[[Payment Protocol (voting pools)|PaymentRequest]]</code>.

===PaymentRequest delivery===

[[File:Voting_Pools_Inbailment_Procedure-03.png|800px]]

The audit server broadcasts the <code>PaymentRequest</code> to all transaction servers and audit servers in the pool. The transaction server replaces the user’s <code>initiatedBailment</code> notice in the inbox with a <code>[[pendingBailment]]</code> notice containing a copy of the <code>PaymentRequest</code>.

When the other audit servers in the pool receive the <code>PaymentRequest</code> broadcast they add the deposit to their respective deposit databases. The other transaction servers in the pool cache the <code>PaymentRequest</code> to answer verification requests from the OT client.

The OT client should validate the <code>PaymentRequest</code> against the voting pool [[asset contract (voting pools)|asset contract]]. If it is valid then it should query a random selection of other transaction servers, at least <code>m-1</code>, using the <code>[[Payment_Protocol_(voting_pools)|PaymentRequest identifier]]</code> to verify whether they have seen it. If this check is successful, it then initiates the blockchain transaction by passing the <code>PaymentRequest </code>to the user's local wallet application which is configured to handle <code>[[bitcoin:]] URIs</code>.

===Deposit and crediting===

[[File:Voting_Pools_Inbailment_Procedure-04.png|800px]]

----

;Type 1 Event - [[Fraudulent Deposit Address]]
:A malicious or hacked operator may give the customer an invalid <code>PaymentRequest</code> in an attempt to steal deposits.

----

Each pool member’s Bitcoin wallet must notify its audit server of any deposits received to an address which the pool controls. When an incoming transaction is received to an address the audit servers are expecting due to previously broadcast <code>PaymentRequest</code>, they will use the <code>[[Voting Pool Wallet API#getinfomultisigwalletaddress|getinfomultisigwalletaddress]]</code> calls to identify the incoming transaction, and <code>[[Voting Pool Wallet API#gettransactionstatus|gettransactionstatus]]</code> to monitor its confirmation status.

----

;Type 0 Event - [[Deposit Never Received]]
:It’s possible that the customer may never actually transfer bitcoins after requesting a PaymentRequest.

;Type 1 Event - [[Unknown Deposit]]
:A deposit may be received to an address which has never been used, and for which a PaymentRequest was never created so no member of the pool knows to which nym it should be credited.

;Type 1 Event - [[Duplicate Deposit]]
:A deposit may be received from an address which has been previously used, so the audit servers know to which nym the address is assigned.

;Type 0 Event - [[Dust Handling]]:
The size of the deposit may be below the network dust threshold (small enough that it would require more in transaction fees to spend than it is worth).

----

The audit server relays the number of confirmations the incoming transaction has received to the transaction server. Once the number is sufficient according to the [[Funds_Available_Policy_(voting_pools)|Funds Available Policy]] the transaction server will issue an OT asset for the amount of the deposit to the [[nym]] of the user.

The transaction server will replace the <code>pendingBailment</code> notice (in the inbox) with a <code>[[completedBailment]]</code> notice, which includes a signed copy of the original <code>bailment</code> request, as well as a copy of the audit server’s signed notice of confirmations, which includes the transaction identifier provided by the blockchain wallet.

The OT client processes the user’s OT account inbox, removing the <code>completedBailment</code> notice, which simultaneously closes the transaction number and updates his OT balance.

The audit servers in the pool must monitor all deposits to ensure the [[Funds Available Policy (voting pools)|Funds Available Policy]] is satisfied to avoid the risk of a double spend or chain fork causing insolvency. Any server which offers more early deposit credits than what it can cover with its service account must have its audit status set to <code>[[Auditing (voting pools)|degraded]]</code>.

----

;Type 2 Event - [[Minority loss of consensus#Non-credited Deposit|Non-credited Deposit]]
:The transaction server fails to place a <code>completedBailment</code> notice in the user’s inbox after a successful Bitcoin transfer.

----

If an initially-seen deposit fails due to a chain fork, and if the user has not yet been credited with an OT receipt for the deposit, the status of the deposit remains pending. The audit server should notify the transaction server by setting the number of confirmations back to zero. In the typical case of blockchain [[reorg]] event, the deposit transaction should re-enter the [[mempool]] automatically and the wallet can assist with this by rebroadcasting it.

If an initially-seen deposit has become invalid due to conflicting transactions which made it into the blockchain, the audit server should mark the deposit as <code>failed</code> by setting the number of confirmations to -1. The audit server should notify the transaction server of the failure, who then replaces the user’s <code>pendingBailment</code> notice with a <code>[[failedBailment]]</code> notice. The transaction server should update the status to <code>failed</code> in the deposit database and the address should not be intentionally reused. The OT client can then process the user’s inbox, removing the <code>failedBailment</code> notice and closing the transaction number. In this case there is no change to the OT account balance, unlike with a <code>completeBailment</code> notice.

----

;Type 1 Event - [[Reversed Deposit]]
:A deposit could disappear from the blockchain after the user has already been issued an OT receipt

----

[[Category:Voting Pool Operations]]

Talk:Consensus Process (voting pools)

2014-09-22T12:14:45Z

Larshesel: Which wallet issues the transaction?

In computer science anything based on consensus in a distributed network is an incredibly complicated thing to implement. There are some tools out there like zookeeper (never used it) which I understand can be used for this kind of thing.

Something to keep in mind is, that roughly speaking you cannot get consensus, (two generals problem etc), but you can get consensus with some degree of certainty.

Would there be any way where we could change this such that we do not need concensus?

Why do the peers have to agree on the addresses every 5 minutes?

<hr>

We need consensus because each member of the voting pool to take the same actions. We're tried to restrict the scope of consensus to the bare minimum possible in order to make the withdrawal process work.

As far as the algorithm, we'll be using a system similar to what Ripple uses. Last year Chris was contracted to produce a custom cryptocurrency and the algorithm he used for them is compatible with what we need for voting pools.

<hr>

Good to know the consensus has been scoped to be as minimal as possible. Can we add a reference to the algorithm we're going to use?

<hr>

Yes, but it will probably be until after more of the auditor is documented before this page is filled out.

<hr>
Lars:
bullet 3: A list of valid withdrawals to be processed, sorted in TBD order, which may be an empty list.

So if each audit-server gets this list of withdrawals. And after they have all exchanged signatures and gotten consensus, which one of the wallets does actually issue a transaction to the blockchain? Do they all do that?

Voting Pool Withdrawal Process

2014-09-22T11:56:56Z

Larshesel: /* Consensus */

==Procedure==

===Initiation===

Customers will normally request a withdrawal using one of the client applications that talk to the notary. These requests will end up in the auditor stream. The auditor will then validate and batch multiple withdrawal requests and ask the blockchain wallet to construct one or more transactions with one output for every withdrawal.

'''TODO: explain why batching is important'''

=== Consensus ===

In order to withdraw funds from a M-of-N voting pool, M members must sign the blockchain transaction that moves the coins to the desired addresses. For that reason, auditors will have to periodically [[Consensus Process (voting pools)|agree on a set of parameters for the blockchain transactions]]. These parameters are then passed on to their wallets, allowing them to generate transactions deterministically.

=== Transaction Construction ===

The auditor sends a [[Startwithdrawal|startwithdrawal]] command to the wallet, which then attempts to construct blockchain transactions to satisfy the requested ouputs.

=== Transaction Signing & Broadcasting ===

Once an auditor receives new [[Siglist|signature lists]] for an in-progress transaction, it will send a [[Updatewithdrawal|updatewithdrawal]] command to the blockchain wallet, passing those new signatures. Once the blockchain wallet has received the minimum number of required signatures for a given transaction, it will be broadcast.

[[Category: Voting Pool Operations]]

Keyset (voting pools)

2014-09-22T10:00:34Z

Larshesel: Move definition of x to keyset definition

==Keysets==

The multisig structure of a pool is called the keyset definition and is expressed in XML and stored in the OT asset contract:

<pre>
<pool id=”uuid” version=”1”>
<blockchain>bitcoin</blockchain>
<color>0</color>
<members>
<server id=”server_id_y” />
<server id=”server_id_z” />
<server id=”server_id_w” />
</members>
<keyset schedule=”x” m=”u” n=”v”>
<series number=”1”>
<key server=”server_id_y”>xpub_y1</key>
<key server=”server_id_z”>xpub_z1</key>
<key server=”server_id_w”>xpub_w1</key>
</series>
<series number=”2”>
<key server=”server_id_y”>xpub_y2</key>
<key server=”server_id_z”>xpub_z2</key>
<key server=”server_id_w”>xpub_w2</key>
</series>
</keyset>
</pool></pre>

In the above example there are three servers, y, z, and w. All decisions made by the pool must be signed by u of v members of the pool. Every server contributes a different xpub for each series defined in the keyset.

Each pool must explicitly define the crypto-currency being managed by the pool, and whether to treat the deposits as regular units or as colored units.

Regular pools have a <color> value of 0. Colored coin pools are designated by including a [[color definition]] in the <color> section.

Pool definitions are versioned for future extendibility.

x is time interval expressed in [http://www.nncron.ru/help/EN/working/cron-format.htm Cron] format, either a semicolon-separated list of column values, or one of the [http://en.wikipedia.org/wiki/Cron#Predefined_scheduling_definitions predefined patterns]. The default and recommended schedule is “@weekly”.

===Series===

[[File:Voting_Pools_Series_Progression.png|800px]]

The keyset contains a list of series numbers, each one of which contains an [[xpub]] for every member of the pool.

Series numbers are always monotonic (strictly increasing).

Series numbers are incremented on a schedule, shown above as “x”.

All series rotations are calculated based on UTC time.

At any given time, one series is “active”. This is the series containing the keys which will be used to create deposit and change addresses. Pool members will “fill up” this series with deposits until the next series rotation, then will begin filling up the next series.

At any given time, one series is “hot”. The hot series is the one whose keys are online and is currently being used to process withdrawals. All series between the hot series and the active series are inactive. Slightly before the hot series is depleted of unspent outputs (to avoid withdrawal delays) the private keys for the next inactive series are brought online and that series becomes the new hot series.

Each series can be subdivided into two sub-series. The deposit series consists of n lists of deposit addresses, one for each member of the pool. The change series is a list of change outputs from previous withdrawal transactions.

[[Category:Voting Pool Technical Specifications]]

Talk:Wallet (blockchain)

2014-09-22T09:31:26Z

Larshesel:

The Wallet Creation section mentions that, when bringing extended private keys online, the auditor must specify them in the order matching the extended public keys, but there's no need for that as the wallet can figure out the matching extended public key for any given extended private key

<hr>
Lars:

''Series Identifier

''Since one wallet will need to handle multiple pools and series, a series identifier must include the pool for which it belongs.

''A wallet identifier is defined as JSON object and is composed of two parts:''

It's confusing that we're talking about a Series Identifier, but then define a wallet identifier. I suppose it should just say 'Series identifier?'

Transaction Construction Algorithm (voting pools)

2014-09-19T13:18:57Z

Larshesel: /* Initial Conditions */

Talk:Consensus Process (voting pools)

2014-09-16T14:34:42Z

Larshesel:

Input Selection Algorithm (voting pools)

2014-09-16T13:35:49Z

Larshesel: /* Eligibility criteria */

Talk:Consensus Process (voting pools)

2014-09-16T13:03:15Z

Larshesel: Created page with "In computer science anything based on consensus in a distributed network is an incredibly complicated thing to implement. There are some tools out there like zookeeper (never ..."

Talk:Keyset (voting pools)

2014-09-01T01:01:02Z

Larshesel: Created page with "I understand what an xpub is (an extended public key) but it might not be clear for the first time reader, maybe we should write that. Do we have a good reference on extended ..."