Spike: Evaluate cost of MPT verification in plutus

[ch1bo]

What & Why

We want to know as early as possible whether we would be running into execution budget limits for using Merkle (Patricia) Tree in our validators. More specifically, the (asymptotic) complexity of memory and cpu utilization of checking whether a UTXO is part of a tree given it's proof using the Plutus implementation and cost models is to be estimated.

[ch1bo]

We implemented a plutus-merkle-tree package and measured execution costs of membership checks and construction in Plutus:

https://github.com/input-output-hk/hydra-poc/wiki/Logbook#2021-01-11

[ch1bo]

Copying the results here. Reproducible on 73c2090 with cabal run contract-cost.

Percent of full budget (current parameters) for both membership and MT building:

# UTXO	Mem (member)	CPU (member)	Mem (build)	CPU (build)
1	3.79926	1.66382747	3.92862	1.69953237
2	4.00523	1.78074127	6.41958	2.61146129
3	4.14665	1.86060451	11.8103	4.55927679
4	4.2112	1.89765508	17.63118	6.64887027
5	4.29852	1.94672544	28.82442	10.66935212
6	4.35262	1.97751831	40.44782	14.83161195
7	4.39126	1.99951322	52.50138	19.13564976
8	4.41717	2.01456888	64.9851	23.58146555
9	4.46705	2.04247043	87.78338	31.7472801
10	4.50449	2.06363924	111.01182	40.05487263
20	4.71046	2.18055305	0	0
30	4.81784	2.24175466	0	0
40	4.91643	2.29746685	0	0
50	4.98234	2.33487927	0	0
60	5.02381	2.35866846	0	0
70	5.07426	2.38716361	0	0
80	5.1224	2.41438066	0	0
90	5.15983	2.43554948	0	0
100	5.18831	2.45179308	0	0
120	5.22978	2.47558227	0	0
140	5.28023	2.50407741	0	0
160	5.32837	2.53129446	0	0
180	5.3658	2.55246328	0	0
200	5.39428	2.56870688	0	0
220	5.41757	2.5819971	0	0
240	5.43575	2.59249607	0	0
260	5.45449	2.60326714	0	0
280	5.4862	2.62099122	0	0
300	5.51269	2.63589112	0	0
320	5.53434	2.64820827	0	0
340	5.55488	2.65975424	0	0
360	5.57177	2.66937709	0	0
380	5.58611	2.67762308	0	0
400	5.60025	2.68562069	0	0
420	5.6128	2.69274686	0	0
440	5.62354	2.69891091	0	0
460	5.63335	2.70453895	0	0
480	5.64172	2.70940988	0	0
500	5.64942	2.71389113	0	0

[ch1bo]

Graphs of our above measurements in checking Merkle-Tree membership:

And building a Merkle-Tree:

[ch1bo]

In addition to Merkle-Tree construction and membership checks, we also measured performance of

• hashing bytes using builtin Plutus hash functions -> O(n) see PR Spike: costs of hashing #155
• encoding a TxOut into bytes using a simple CBOR encoder -> O(n) see PR Spike: cost of on-chain CBOR encoding  #154 and these graphs:

List of ada-only TxOut:

Single TxOUT with varying number of assets:

This also shows that we can continue measurements and cost estimation with Ada-Only TxOuts and trade them roughly against number of assets in a single TxOut.