Estimate max number of allowed inputs in coin selection

[KtorZ]

Context

We currently use a hard-coded limit of 10 inputs for a single transaction. This is pretty far from what reality allows.

https://github.com/input-output-hk/cardano-wallet/blob/eccc130290f71a18b471f2e16a31614b3cddc2d4/lib/core/src/Cardano/Wallet/Api/Server.hs#L363-L364

When working on benchmarking, we've already explored a bit the true limitation of the system, although based on a transaction max size known a priori (8kb):

https://github.com/input-output-hk/cardano-wallet/blob/master/lib/core/test/bench/db/Main.hs#L183-L229

Decision

How many inputs are we allowed to select is a tricky question to answer in practice because not all inputs are born equals! One inputs may increase the transaction's size more than another one (and vice-versa) because of the impact it has on change.

Therefore, a simpler strategy to adopt would be to:

• Figure out the "theoretical" maximum number of inputs, from a given maximum transaction's size (irrespective of the number of outputs), for a given backend target (this depends on the transaction's binary format)
• Run the coin selection using this number
• After constructing a transaction, control that its size doesn't exceed the maximum transaction size.

This would be fairly resilient in practice and be a real best-effort at constructing transactions with the downside of sometimes wasting computing power in making selection for transactions that will require too many inputs already.

Acceptance Criteria

1. For each binary format / backend target, we must compute a theoretical maximum number of inputs from a given transaction's max size (https://github.com/input-output-hk/cardano-wallet/blob/master/lib/core/test/bench/db/Main.hs#L183-L229 is a good starting point).

2. TransactionLayer for http-bridge must be extended with a function:

   estimateMaxNumberOfInputs 
       :: Quantity "byte" Word16 
       -- ^ Transaction max size in bytes
       -> Word8
       -- ^ Maximum number of inputs, estimated

3. TransactionLayer for jormungandr must be extended with a similar function.

4. Both implementation must include extensive comments about where the results come from and what hypotheses or simplifications were made.

---

Development Plan

• Properties for the estimateMaxNumberOfInputs function. Something like larger transaction ⇒ higher maximum for inputs. Make sure generator includes boundaries of the Word16 parameter.
• Implement most of the logic within binary modules.
• Start with jormungandr because its tx size formula is simpler.
• Use the size estimation in order to compute the coin selection option in the wallet layer
  • May require to have access to the txMaxSize ?

PR

Number	Base
#495	master
#536	master

QA

1. The new functions have unit tests. See Cardano/Wallet/TransactionSpecShared

   • Used in Cardano/Wallet/Jormungandr/TransactionSpec
   • Used in Cardano/Wallet/HttpBridge/TransactionSpec

2. The implementations are documented adequately with source code comments. See Cardano/Wallet/Transaction

[rvl]

1. Should the estimate be a max bound? That is, if there were coin selection with maxNumInputs + 1, then the encoded tx would exceed the max size.
2. About the estimation strategy. "Control that its size doesn't exceed the maximum transaction size" -- what does that mean? Does it mean to repeatedly run coin selection with lower maxNumInputs until the transaction size is below the max?
3. Should this estimation function use the network backend Binary modules to calculate exact transaction sizes?

[KtorZ]

@rvl

1. It should be as close as possible to a realistic max bound, using what we know of how the CS algorithm work (for instance, there's at least one input per output). And it's preferable for this limit to be slightly more permissive than the opposite. We may indeed sometimes end up with transaction that are slightly too big (cf answer to your second question).

2. No, it means that we run it once, if it fails we reject the transaction because it's too big. Incidentally, if the fallback (largest first) yield a transaction that is too big, there's no point retrying with less inputs because we can't yield a better selection anyway. In practice we could fix the max number of inputs to an arbitrary big value and always measure the actual size afterwards. We try to make this upper bound smaller to avoid wasting computational time on tx we know would already be too big.

3. Yes.

[KtorZ]

Moving this back to In Progress since we aren't using the corresponding functions in the wallet layer at the moment:

https://github.com/input-output-hk/cardano-wallet/blob/39050fd491e36ca0c40e5519fcb5e402d44b0bc3/lib/core/src/Cardano/Wallet.hs#L624-L629

I'll add a bullet point to the ticket and make sure it's used.

[KtorZ]

@rvl I've also extended the QA section with links. The idea is really to make the work easy for @piotr-iohk and avoid having him figuring out where to look for the tests. We're starting to have a rather big codebase, with tests spread across many modules, and even though there are some naming convention, it's always good to point at the information you want to highlight 👍

[rvl]

I thought the corresponding wallet layer functions would be implemented in another ticket. There is nothing in the AC about it.

[piotr-iohk]

lgtm 👍

Sort of related tests are in #533.