Fee estimation

[paweljakubas]

Context

We have added coin selection and fee calculation in the context of the former.

Decision

We need to add fee estimation. Fee estimation is determined based on bytes imprinted in transaction send to the node. The estimation can be relatively simple as:
(a) Inputs are always of the same size because they're a hash and index
(b) Outputs have variable sizes, but that can be easily determined regarding their value (<24 one byte, <256 2 bytes, <65536 3 bytes etc ... ). The additional variable is derivation scheme adopted.
(c) tx witnesses, one per input, are also fixed-sized
(d) there is fixed-sized cbor bits (connected with building lists)
(e) network can be mainnet or testnet

Acceptance Criteria

1. We must be able to adjust a coin selection for fee
2. We must estimate the size of a (Byron) transaction accurately
3. Estimated size must always be greater than or equal to the actual size
4. Fee estimation may not be exact, but ideally with a error of <1%

---

Development Plan

PR

Number	Base
#176	master
#196	master

QA

See extensive tests in Cardano.Wallet.CoinSelection.FeeSpec. We test mostly on two fronts:

• The adjustForFee function is tested via a few hand-crafted unit tests. The function is in practice non-deterministic (runs in MonadRandom m => ...), though, with a small number of available inputs or, by making them all the same, we can "predict" what input will be selected.

• On the other hand, we do also check a few properties for this function (see here):

  • No fee gives back the same selection, when fees are null
  • Fee adjustment is deterministic when there's no extra inputs (because indeed, we only need the 'MonadRandom' to randomly select a new input. If there's none, we can either adjust without any extra inputs, or we fail; but the algorithm is always deterministic).
  • Adjusting for fee (/= 0) reduces the change outputs or increase inputs; that's the basic intuition we can have of this function, it divvies the fee over all change outputs and decrease them by the requested amount. If there's not enough change to cover for fees, then a new input is selected.

• On the other hand, we do also compute fees for a given coin selection. This is rather "tricky" because fees depends on the underlying binary representation for a transaction (cf: comments here). So, we do have a property checking that "Estimated fee is the same as taken by encodeSignedTx", which computes, for any given coin selection, the actual true fee for the corresponding transaction. Our estimation has to be rather "identical" (which is not possible in practice, because we can't know upfront the size of the change address. In practice, sequential address payloads on mainnet will vary between 39 & 43 bytes, so we consider equality here with a margin of 4 bytes per change output. Note that we also run the property a thousand time because the generator work in a rather big input domain (up to 100 inputs and outputs; because many of the CBOR encodings change / increase when list length get bigger than 23!). Hence, we check that estimated fee are at least as big as if exact, and, we allow them to be bigger than the actual fee up-to 4 bytes per change output: https://github.com/input-output-hk/cardano-wallet/blob/master/test/unit/Cardano/Wallet/CoinSelection/FeeSpec.hs#L380-L388

[piotr-iohk]

I have same remark as -> #92 (comment), but with regards to https://coveralls.io/builds/23064602/source?filename=src/Cardano/Wallet/CoinSelection/Fee.hs.

I'm not sure how feasible is to cover the missing parts for both Fee.hs and Random.hs but just want to make sure it's the best possible.

[KtorZ]

Well, for the invariant, we won't be able to cover them (otherwise it means something's really going wrong 😂). However, there are indeed some extreme corner case / overflow case we could probably cover with a hand-written unit test. Let me try.

[KtorZ]

@piotr-iohk I believe we can now close this one. Remaining "uncovered" areas are:

• Invariants:
  
  

• Some un-evaluated Coin 0 or [] because the results are always discarded (cleaned-up as 'Dust' or partially evaluated via null ... and similar checks).

• Some particular "security" guards which are hard (impossible?) to met in practice: