-
Notifications
You must be signed in to change notification settings - Fork 54
/
GreedyInputSelector.ts
231 lines (202 loc) · 8.13 KB
/
GreedyInputSelector.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
/* eslint-disable max-params */
import { Cardano, coalesceValueQuantities } from '@cardano-sdk/core';
import { InputSelectionError, InputSelectionFailure } from '../InputSelectionError';
import { InputSelectionParameters, InputSelector, SelectionConstraints, SelectionResult } from '../types';
import {
addTokenMaps,
getCoinQuantity,
hasNegativeAssetValue,
sortByCoins,
stubMaxSizeAddress,
subtractTokenMaps,
toValues
} from '../util';
import { splitChange } from './util';
/** Greedy selection initialization properties. */
export interface GreedySelectorProps {
/**
* Callback that returns a map of addresses with their intended proportions expressed as weights.
*
* The weight is an integer, and relative to other weights in the map. For example, a map with two addresses and
* respective weights of 1 and 2 means that we expect the selector to assign twice more change to the second address
* than the first. This means that for every 3 Ada, 1 Ada should go to the first address, and 2 Ada should go to
* the second.
*
* If the same distribution is needed for each address use the same weight (e.g. 1).
*
* This selector will create N change outputs at this change addresses with the given proportions.
*/
getChangeAddresses: () => Promise<Map<Cardano.PaymentAddress, number>>;
}
/**
* Given a set of input and outputs, compute the fee. Then extract the fee from the change output
* with the highest value.
*
* @param changeLovelace The available amount of lovelace to be used as change.
* @param constraints The selection constraints.
* @param inputs The inputs of the transaction.
* @param outputs The outputs of the transaction.
* @param changeOutputs The list of change outputs.
* @param currentFee The current computed fee for this selection.
*/
const adjustOutputsForFee = async (
changeLovelace: bigint,
constraints: SelectionConstraints,
inputs: Set<Cardano.Utxo>,
outputs: Set<Cardano.TxOut>,
changeOutputs: Array<Cardano.TxOut>,
currentFee: bigint
): Promise<{ fee: bigint; change: Array<Cardano.TxOut>; feeAccountedFor: boolean }> => {
const totalOutputs = new Set([...outputs, ...changeOutputs]);
const fee = await constraints.computeMinimumCost({
change: [],
fee: currentFee,
inputs,
outputs: totalOutputs
});
if (fee === changeLovelace) return { change: [], fee, feeAccountedFor: true };
if (changeLovelace < fee) throw new InputSelectionError(InputSelectionFailure.UtxoBalanceInsufficient);
const updatedOutputs = [...changeOutputs];
updatedOutputs.sort(sortByCoins);
let feeAccountedFor = false;
for (const output of updatedOutputs) {
const adjustedCoins = output.value.coins - fee;
if (adjustedCoins >= constraints.computeMinimumCoinQuantity(output)) {
output.value.coins = adjustedCoins;
feeAccountedFor = true;
break;
}
}
return { change: [...updatedOutputs], fee, feeAccountedFor };
};
/**
* Recursively compute the fee and compute change outputs until it finds a set of change outputs that satisfies the fee.
*
* @param inputs The inputs of the transaction.
* @param outputs The outputs of the transaction.
* @param changeLovelace The total amount of lovelace in the change.
* @param changeAssets The total assets to be distributed as change.
* @param constraints The selection constraints.
* @param getChangeAddresses A callback that returns a list of addresses and their proportions.
* @param fee The current computed fee for this selection.
*/
const splitChangeAndComputeFee = async (
inputs: Set<Cardano.Utxo>,
outputs: Set<Cardano.TxOut>,
changeLovelace: bigint,
changeAssets: Cardano.TokenMap | undefined,
constraints: SelectionConstraints,
getChangeAddresses: () => Promise<Map<Cardano.PaymentAddress, number>>,
fee: bigint
): Promise<{ fee: bigint; change: Array<Cardano.TxOut>; feeAccountedFor: boolean }> => {
const changeOutputs = await splitChange(
getChangeAddresses,
changeLovelace,
changeAssets,
constraints.computeMinimumCoinQuantity,
constraints.tokenBundleSizeExceedsLimit,
fee
);
let adjustedChangeOutputs = await adjustOutputsForFee(
changeLovelace,
constraints,
inputs,
outputs,
changeOutputs,
fee
);
// If the newly computed fee is higher than tha available balance for change,
// but there are unallocated native assets, return the assets as change with 0n coins.
if (adjustedChangeOutputs.fee >= changeLovelace) {
const result = {
change: [
{
address: stubMaxSizeAddress,
value: {
assets: changeAssets,
coins: 0n
}
}
],
fee: adjustedChangeOutputs.fee,
feeAccountedFor: true
};
if (result.change[0].value.coins < constraints.computeMinimumCoinQuantity(result.change[0]))
throw new InputSelectionError(InputSelectionFailure.UtxoFullyDepleted);
return result;
}
if (fee < adjustedChangeOutputs.fee) {
adjustedChangeOutputs = await splitChangeAndComputeFee(
inputs,
outputs,
changeLovelace,
changeAssets,
constraints,
getChangeAddresses,
adjustedChangeOutputs.fee
);
if (adjustedChangeOutputs.change.length === 0)
throw new InputSelectionError(InputSelectionFailure.UtxoFullyDepleted);
}
for (const out of adjustedChangeOutputs.change) {
if (out.value.coins < constraints.computeMinimumCoinQuantity(out))
throw new InputSelectionError(InputSelectionFailure.UtxoFullyDepleted);
}
if (!adjustedChangeOutputs.feeAccountedFor) throw new InputSelectionError(InputSelectionFailure.UtxoFullyDepleted);
return adjustedChangeOutputs;
};
/** Selects all UTXOs to fulfill the amount required for the given outputs and return the remaining balance as change. */
export class GreedyInputSelector implements InputSelector {
#props: GreedySelectorProps;
constructor(props: GreedySelectorProps) {
this.#props = props;
}
async select(params: InputSelectionParameters): Promise<SelectionResult> {
const { utxo: inputs, outputs, constraints, implicitValue } = params;
const utxoValues = toValues([...inputs]);
const outputsValues = toValues([...outputs]);
const totalLovelaceInUtxoSet = getCoinQuantity(utxoValues);
const totalLovelaceInOutputSet = getCoinQuantity(outputsValues);
const totalAssetsInUtxoSet = coalesceValueQuantities(utxoValues).assets;
const totalAssetsInOutputSet = coalesceValueQuantities(outputsValues).assets;
const implicitCoinInput = implicitValue?.coin?.input || 0n;
const implicitCoinOutput = implicitValue?.coin?.deposit || 0n;
const implicitAssetInput = implicitValue?.mint || new Map<Cardano.AssetId, bigint>();
const totalLovelaceInput = totalLovelaceInUtxoSet + implicitCoinInput;
const totalLovelaceOutput = totalLovelaceInOutputSet + implicitCoinOutput;
const totalAssetsInput = addTokenMaps(totalAssetsInUtxoSet, implicitAssetInput);
const changeLovelace = totalLovelaceInput - totalLovelaceOutput;
const changeAssets = subtractTokenMaps(totalAssetsInput, totalAssetsInOutputSet);
if (inputs.size === 0 || totalLovelaceOutput > totalLovelaceInput || hasNegativeAssetValue(changeAssets))
throw new InputSelectionError(InputSelectionFailure.UtxoBalanceInsufficient);
const adjustedChangeOutputs = await splitChangeAndComputeFee(
inputs,
outputs,
changeLovelace,
changeAssets,
constraints,
this.#props.getChangeAddresses,
0n
);
const change = adjustedChangeOutputs.change.filter(
(out) => out.value.coins > 0n || (out.value.assets?.size || 0) > 0
);
if (changeLovelace - adjustedChangeOutputs.fee < 0n)
throw new InputSelectionError(InputSelectionFailure.UtxoBalanceInsufficient);
if (
inputs.size >
(await constraints.computeSelectionLimit({ change, fee: adjustedChangeOutputs.fee, inputs, outputs }))
) {
throw new InputSelectionError(InputSelectionFailure.MaximumInputCountExceeded);
}
return {
remainingUTxO: new Set<Cardano.Utxo>(), // This input selection always consumes all inputs.
selection: {
change,
fee: adjustedChangeOutputs.fee,
inputs,
outputs
}
};
}
}