# Marketplace state restoration
There are requirements in the Marketplace for allowing both client and host nodes to be restarted (due to power failures, hardware failures, node maintenance, etc). When a client/host is restarted, the state of the client's purchases and the host's sales must be restored. The decision was made to maintain the state on-chain, and when a node is restarted, its client/host (or both) state can be obtained from the current on-chain state. This requires the ability to retrieve a client's requests (their purchases) and a host's slots (their sales). The state management is mostly straightforward: client's requests can be added, removed individually, and listed, and host's slots can be added, removed individually, and listed, by using an `EnumerableSet.Bytes32Set` data structure. However, the complication comes when a request is failed, all the slots in a request must be removed from the list of host's slots, and this is not possible without iterating and deleting one-by-one. This type of iteration and deletion approach incurs significant gas penalties and if not capped, could cause gas out-of-gas exceptions (though it is capped in the DAL approach).
This reports explores two different approaches to solve the complication of storage request failures: the data access layer (DAL) approach and the additional interaction (AI) approach.
## Considerations
The issue was avoided for cancelled requests by altering the requirements such that hosts who want to get paid for their time occupying a slot before cancellation must call `freeSlot` directly.
Additional required interactions, or transactions interacting with the marketplace contract, from hosts and clients to continue using Codex are seen as negative because of the cost and effort involved. Additionally, there are UX considerations to be worked out as the data required for interaction decision making needs to be made available and presented to the end user (client or host).
## Methodology
The gas reports were produced using https://github.com/cgewecke/hardhat-gas-reporter, which uses https://github.com/cgewecke/eth-gas-reporter to compute the gas used in each transaction, including deployment of the contract(s). For this test comparison, only the marketplace tests were run, as those are the only relevant tests needed. A [free coinmarketcap API key](https://coinmarketcap.com/api/pricing/) was obtained for testing purposes and added to the local environment. Tests were run using the following command:
```shell=
export CMC_API_KEY=xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx
REPORT_GAS=1 npm test test/Marketplace.test.js
```
Apart from the normal marketplace unit tests, a special unit test was created to test the limits of the contract. This unit test creates a storage request with 256 slots (the max in the DAL approach) and a `maxSlotLoss` of `0` which means the contract is considered failed after the first slot is freed. These parameters create the conditions for the maximum gas cost of creating a slot as well as the maximum number of slots to be deleted on the first `freeSlot` transaction. More realistic storage request parameters would likely be used by clients, however these parameters are still within the allowed ranges.
## Data Access Layer (DAL) approach
This [branch](https://github.com/status-im/dagger-contracts/tree/list-of-active-sales) introduces a data access layer to the marketplace contract. It has a cap of 256 slots and deletes slots when a request is failed. The data access layer keeps track of data between tables bi-directionally, so they can be referenced in both directions (from one-to-many and many-to-one), randomly (using a mapping), and sequentially (using an array index), allowing for referential integrity to be maintained. For example, a slot cannot be added when it references a request that doesn't exist, nor can a request be deleted when it references slots that exist.
The major downside of this approach is that there is a 10x gas penalty for iterating and deleting the maximum number of slots (256) from the list of host's slots, when compared to the AI approach.
```shell
·--------------------------------------|---------------------------|--------------|-----------------------------·
| Solc version: 0.8.8 · Optimizer enabled: true · Runs: 1000 · Block limit: 30000000 gas │
·······································|···························|··············|······························
| Methods · 12 gwei/gas · 1240.70 eur/eth │
····················|··················|·············|·············|··············|···············|··············
| Contract · Method · Min · Max · Avg · # calls · eur (avg) │
····················|··················|·············|·············|··············|···············|··············
| TestMarketplace · deposit · 78119 · 129419 · 112822 · 68 · 1.68 │
····················|··················|·············|·············|··············|···············|··············
| TestMarketplace · fillSlot · 412400 · 1187346 · 664152 · 407 · 9.89 │
····················|··················|·············|·············|··············|···············|··············
| TestMarketplace · freeSlot · 93368 · 3115596 · 209407 · 33 · 3.12 │
····················|··················|·············|·············|··············|···············|··············
| TestMarketplace · payoutSlot · - · - · 145619 · 7 · 2.17 │
····················|··················|·············|·············|··············|···············|··············
| TestMarketplace · requestStorage · 1369315 · 1463058 · 1454358 · 71 · 21.65 │
····················|··················|·············|·············|··············|···············|··············
| TestMarketplace · withdraw · - · - · 68089 · 1 · 1.01 │
····················|··················|·············|·············|··············|···············|··············
| TestMarketplace · withdrawFunds · 104750 · 104762 · 104760 · 6 · 1.56 │
····················|··················|·············|·············|··············|···············|··············
| TestToken · approve · 46219 · 46243 · 46226 · 142 · 0.69 │
····················|··················|·············|·············|··············|···············|··············
| TestToken · mint · 51223 · 68335 · 55507 · 288 · 0.83 │
····················|··················|·············|·············|··············|···············|··············
| Deployments · · % of limit · │
·······································|·············|·············|··············|···············|··············
| TestMarketplace · - · - · 3720155 · 12.4 % · 55.39 │
·······································|·············|·············|··············|···············|··············
| TestToken · - · - · 685484 · 2.3 % · 10.21 │
·--------------------------------------|-------------|-------------|--------------|---------------|-------------·
```
## Additional Interaction (AI) approach
This [branch](https://github.com/status-im/dagger-contracts/tree/mark/list-of-active-sales) is using two `EnumerableSet.Bytes32Sets` to keep track of requests per client, and slots per host. The downside of this approach is that there is an additional host interaction required to free their slot when a request has failed. There is also no reference integrity as in the DAL approach.
```shell
·----------------------------------------|---------------------------|--------------|-----------------------------·
| Solc version: 0.8.8 · Optimizer enabled: true · Runs: 1000 · Block limit: 30000000 gas │
·········································|···························|··············|······························
| Methods · 11 gwei/gas · 1241.11 eur/eth │
····················|····················|·············|·············|··············|···············|··············
| Contract · Method · Min · Max · Avg · # calls · eur (avg) │
····················|····················|·············|·············|··············|···············|··············
| TestMarketplace · deposit · 95197 · 129397 · 113592 · 66 · 1.55 │
····················|····················|·············|·············|··············|···············|··············
| TestMarketplace · fillSlot · 323821 · 1098767 · 568487 · 396 · 7.76 │
····················|····················|·············|·············|··············|···············|··············
| TestMarketplace · forciblyFreeSlot · 67649 · 84152 · 74517 · 25 · 1.02 │
····················|····················|·············|·············|··············|···············|··············
| TestMarketplace · freeSlot · 69656 · 218432 · 152305 · 13 · 2.08 │
····················|····················|·············|·············|··············|···············|··············
| TestMarketplace · requestStorage · 1339870 · 1413094 · 1405603 · 69 · 19.19 │
····················|····················|·············|·············|··············|···············|··············
| TestMarketplace · withdraw · - · - · 67993 · 1 · 0.93 │
····················|····················|·············|·············|··············|···············|··············
| TestMarketplace · withdrawFunds · - · - · 198711 · 6 · 2.71 │
····················|····················|·············|·············|··············|···············|··············
| TestToken · approve · 46219 · 46243 · 46225 · 136 · 0.63 │
····················|····················|·············|·············|··············|···············|··············
| TestToken · mint · 51223 · 68335 · 55507 · 276 · 0.76 │
····················|····················|·············|·············|··············|···············|··············
| Deployments · · % of limit · │
·········································|·············|·············|··············|···············|··············
| TestMarketplace · - · - · 3262303 · 10.9 % · 44.54 │
·········································|·············|·············|··············|···············|··············
| TestToken · - · - · 685484 · 2.3 % · 9.36 │
·----------------------------------------|-------------|-------------|--------------|---------------|-------------·
```
## Comparison
Overall, the most significant difference is in `freeSlot`, which is an expected result based on the difference in approaches. `freeSlot` is called every time a slot is freed, which determines if a request has failed, and thus executes the failed request logic (to free up all host's slots). However, the gas difference is quite extreme: it is 10x higher in the DAL approach.
For freeing slots, the maximum gas difference, ${\Delta}_{gas}$, using DAL max gas cost, $D_{max}$, and AI max combined gas costs (`freeSlot` and `forciblyFreeSlot`), $A_{max}$, can be used to calculate the total gas difference of the most expensive transaction in the two approaches:
${\Delta}_{gas} = D_{max}-A_{max}$
The total value in Euros, $T_{price}$, given the gas price, $p_{gas}$ and ETH price, $ETH_{price}$ is:
$T_{price} = {\frac {p_{gas}}{1e^9}} \cdot ETH_{price} \cdot {\Delta}_{gas}$
From the gas reports:
$D_{max} = 3115596 gas$
$A_{max} = 218432 + 84152 = 302584 gas$
${\Delta}_{gas} = 3115596-302584 = 2813012 gas$
At time of writing:
$ETH_{price}$ = €1241.11
$p_{gas}$ = $11 gwei$
And therefore, the total difference in transaction cost in Euros:
$T_{price} = {\frac{11gwei}{1e^9}} \cdot €1241.11 \cdot 2813012 gas = €38.40$
Keep in mind that this transaction cost would only occur at maximum one time per request when it fails.
### Filling slots
| Approach | Min | Max | Avg |
| -------- | ------:| -------:| ------:|
| DAL | 412400 | 1187346 | 664152 |
| AI | 323821 | 1098767 | 568487 |
The smallest transactions incurred a ~60k gas penalty in the DAL branch, while the largest and average transactions incurred a ~100k gas penalty. This is almost certainly due to the additional data access layer overhead, which keeps track of data between tables bi-directionally, so there are additional storage requirements per transaction.
There is a large difference between the minimum and maximum cost of filling a slot as each subsequent slot filling costs more than the previous, as well as takes longer to execute. This means the first slot fill is the cheapest and the last one is the most expensive, with the maximum number tested being 256.
### Freeing slots
| Approach | Min | Max | Avg |
| --------------------- | -----:| -------:| ------:|
| DAL | 93368 | 3115596 | 209407 |
| AI `freeSlot` | 69656 | 218432 | 152305 |
| AI `forciblyFreeSlot` | 67649 | 84152 | 74517 |
Understanding the implications of freeing slots, especially during request failure, was a core goal of the gas reporting. Indeed, the most significant gas savings are in the AI approach when calling `freeSlot`. In the DAL approach, `freeSlot` is called by an aggregator when enough proofs are missed, and when too many slots are freed, host's slots are iterated and deleted one-by-one, which costs a substanial amount of gas (max 3115596). In AI's approach, hosts are required to call `freeSlot` themselves (instead of the aggregator) when a request is finished or cancelled and they want to get paid or withdraw their funds. The approach requires calls to both `freeSlot` and `forciblyFreeSlot`, however even combining their maximum gas together produces a factor of 10x less gas spent than the DAL approach. Here, host's slots are deleted individually, preventing iteration and deletion, thus the gas savings. However, AI's approach holds a couple of downsides. The most notable downside is the additional interaction required on behalf of the host to free a slot and get paid. Also, if the request fails, there is no immediate incentive for a host to call `freeSlot` as there is no payout to be sent to the host. However, if a host wants to withdraw its collateral, it would be required to call `freeSlot` first, as withdrawal of collateral requires no active slots for a host.
## Further exploration
### Mapping gas boundaries
Additional tests were setup to understand further how mappings use gas in add/delete operations, what the gas impact is on leaving dangling values in a mapping, and what the upper bounds on the quantities of danging values may be.
#### Methodology
The tests can be run by [cloning the repo](https://github.com/emizzle/ethereum-gas-tests) and running:
```shell
npx hardhat test
```
This performs a series of tests on three different "simple" types of mappings:
```solidity
mapping(uint => bool) public simpleBool;
mapping(uint => uint) public simpleUint;
mapping(uint => Simple) public simpleStruct;
```
Each struct is added to and deleted from once for each run. The default number of runs is 2048, which can be overridden using:
```shell
RUNS=10000 npx hardhat test
```
There is an additional mapping type being tested that uses a `uint` index "pointer" that points to an `EnumerableSet.Bytes32Set` which can store an unordered list of `bytes32` values and each of those values can be randomly or sequentially accessed:
```solidity
mapping(uint => EnumerableSet.Bytes32Set) private enumSet;
```
For each run, there a default of three sets created (at mapping index `0`, `1`, and `2`) with each set being added to and removed from `RUNS` times (default 256). The default number of sets can be overridden using:
```shell
NUM_SETS=5 npx hardhat test
```
And it can be combined with the number of runs:
```shell
RUNS=10000 NUM_SETS=5 npx hardhat test
```
#### Findings
Tests were setup such that we could attempt to answer the following questions:
1. How do mappings use gas in add/delete operations and how does this impact execution time?
2. What are the gas impact on subsequent transactions when leaving dangling values in a mapping and what are the impacts on execution time?
3. What are the upper bounds on the quantities of danging values that can be left in a mapping?
##### 1. Add/delete gas impacts
The tests were run 2048 times with 5 sets, using:
```
NUM_SETS=5 npx hardhat test
```
Raw data results can be found in Appendix A.
Adding and deleting values from both the simple and "pointer" mappings shows that the only gas penalty arose from the initial transaction to allocate the mapping in storage. The gas penalty for the initial transaction where the first value of the mapping was set was about 17,000 gas across both simple and "pointer" methods. A somewhat unexpected result was that the longest execution time did not belong to the first transaction (where storage was allocated), but occurred during a seemingly random iteration -- perhaps there were variances in the test machine's cpu/io load.
Gas used during deletions varied based on the size of storage allocations being freed, as expected. These deletions were all constant across runs, with minimal variance, and no differences between position (eg first or last).
##### 2. Gas impacts of dangling values
The tests were run 2048 times with 5 sets, using:
```
NUM_SETS=5 npx hardhat test
```
Raw data results can be found in Appendix A.
The gas impacts of dangling values was tested using the "pointer" method. Three `EnumerableSet.Bytes32Set`s were created in a single mapping, each accessible by an index. Each run of 100,000 added or deleted a value to/from each set, without resetting any values between sets. The goal here is to continually load or deload the mappings and see if the gas increased (in the case of additions), decreased (in the case of deletes), or if there was any execution time impact at all.
When adding values to the mappings, as with #1, the greatest gas cost and execution time was for allocating the mapping structure in storage on the first transaction. Each additional transaction was nearly constant in gas/time, with negligible variances. Additionally, creating more dangling in each additional set did not create a gas penalty, with the min, max, and average gas costs between all sets being roughly the same (±100gas).
When rmeoving values from the mappings, each removal was nearly constant in gas and time, with negligible differences.
##### 3. Dangling value upper bounds
This test was isolated to the "pointer" method and only for addition. The test was run 100,000 times with 1 set in an attempt to see if the upper boundary of the mapping was able to be reached with 100,000 values:
```
RUNS=100000 NUM_SETS=1 npx hardhat test
```
The test completed in about 18 minutes. The gas spent for each addition operation was exactly the same as with lower boundary tests, meaning the gas was highest in the initial transaction then constant thereafter. However, the execution time for a seemingly random iteration (#97547) was quite high at nearly 1 second, even though the average time per transaction was 9ms. It's very hard to determine if this max value anomaly is in fact anomalous, or if it is something that correlates with the larger dataset.
```shell
Total runs: 100000
Gas Used
min: 74067 (10ms, run #8456)
max: 91203 (39ms, run #0)
avg: 74101 (9ms)
Execution time
min: 8ms (run #312)
max: 975ms (run #97547)
avg: 9ms
```
### Preventing an additional interaction
To prevent the additional interaction, the AI approach could introduce the iterative deletion that the DAL uses. In order to iteratively delete host's slots in the AI approach when the request fails, there would need to be a way to iterate the slots for the request that failed and remove them from `slotsPerHost`. The way the marketplace contract is currently setup, this would require iterating all slots on the network, filtering by request, then removing that slot from `slotPerHost`. This would almost certainly run out of gas as iterating all the slots in the network is unfeasible. An additional data structure can allow for random access of slots per request, which needs to be maintained through the request lifecycle. Adding this type of data structure to the AI approach starts to resemble the DAL approach, however without the referential integrity. Additional gas reporting would be needed to understand how the gas penalty would compare to the DAL approach. If the gas penalty is less than that of the DAL approach, then the AI approach overall could likely have a lower gas profile altogether and could be the ideal approach overall.
## Appendix A: Gas data
```shell
NUM_SETS=5 npx hardhat test
Mapping
Create
Simple
✓ Should create a bool in the mapping (19780ms)
Total runs: 2048
Gas Used
min: 48671 (20ms, run #1)
max: 65771 (35ms, run #0)
avg: 48679 (8ms)
Execution time
min: 7ms (run #252)
max: 35ms (run #0)
avg: 8ms
✓ Should create a uint in the mapping (27255ms)
Total runs: 2048
Gas Used
min: 48574 (15ms, run #1)
max: 65674 (20ms, run #0)
avg: 48582 (9ms)
Execution time
min: 8ms (run #918)
max: 58ms (run #298)
avg: 9ms
✓ Should create a struct in the mapping (35920ms)
Total runs: 2048
Gas Used
min: 162699 (14ms, run #1574)
max: 179871 (20ms, run #0)
avg: 162773 (13ms)
Execution time
min: 11ms (run #18)
max: 65ms (run #1003)
avg: 13ms
EnumerableSet.Bytes32Set
Filling set 0
Total runs: 2048
Gas Used
min: 74079 (12ms, run #30)
max: 91203 (13ms, run #0)
avg: 74109 (11ms)
Execution time
min: 9ms (run #11)
max: 69ms (run #29)
avg: 11ms
✓ Should create value in a bytes32 set in the Bytes32Set (30059ms)
Filling set 1
Total runs: 2048
Gas Used
min: 74079 (11ms, run #199)
max: 91203 (14ms, run #0)
avg: 74109 (11ms)
Execution time
min: 10ms (run #13)
max: 34ms (run #513)
avg: 11ms
✓ Should create value in a bytes32 set in the Bytes32Set (30336ms)
Filling set 2
Total runs: 2048
Gas Used
min: 74079 (13ms, run #54)
max: 91203 (11ms, run #0)
avg: 74109 (11ms)
Execution time
min: 9ms (run #247)
max: 90ms (run #1105)
avg: 11ms
✓ Should create value in a bytes32 set in the Bytes32Set (31405ms)
Filling set 3
Total runs: 2048
Gas Used
min: 74079 (12ms, run #113)
max: 91203 (11ms, run #0)
avg: 74109 (11ms)
Execution time
min: 10ms (run #77)
max: 204ms (run #87)
avg: 11ms
✓ Should create value in a bytes32 set in the Bytes32Set (31772ms)
Filling set 4
Total runs: 2048
Gas Used
min: 74067 (12ms, run #1969)
max: 91203 (10ms, run #0)
avg: 74109 (11ms)
Execution time
min: 10ms (run #0)
max: 167ms (run #1131)
avg: 11ms
✓ Should create value in a bytes32 set in the Bytes32Set (31781ms)
Delete
Simple
✓ Should delete a bool in the mapping (43933ms)
Total runs: 2048
Gas Used
min: 21985 (10ms, run #0)
max: 22009 (9ms, run #257)
avg: 22007 (9ms)
Execution time
min: 7ms (run #297)
max: 171ms (run #1)
avg: 9ms
✓ Should delete a uint in the mapping (43230ms)
Total runs: 2048
Gas Used
min: 21952 (7ms, run #0)
max: 21976 (9ms, run #257)
avg: 21974 (9ms)
Execution time
min: 7ms (run #0)
max: 175ms (run #676)
avg: 9ms
✓ Should delete a struct in the mapping (60572ms)
Total runs: 2048
Gas Used
min: 41724 (11ms, run #0)
max: 41744 (12ms, run #257)
avg: 41742 (13ms)
Execution time
min: 10ms (run #1539)
max: 203ms (run #1)
avg: 13ms
EnumerableSet.Bytes32Set
Clearing set 0
Total runs: 2048
Gas Used
min: 23958 (10ms, run #0)
max: 23982 (9ms, run #257)
avg: 23980 (8ms)
Execution time
min: 7ms (run #2)
max: 206ms (run #910)
avg: 8ms
✓ Should delete value in a bytes32 set in the Bytes32Set (25491ms)
Clearing set 1
Total runs: 2048
Gas Used
min: 23958 (10ms, run #0)
max: 23982 (8ms, run #257)
avg: 23980 (8ms)
Execution time
min: 7ms (run #8)
max: 63ms (run #888)
avg: 8ms
✓ Should delete value in a bytes32 set in the Bytes32Set (25504ms)
Clearing set 2
Total runs: 2048
Gas Used
min: 23958 (10ms, run #0)
max: 23982 (9ms, run #257)
avg: 23980 (8ms)
Execution time
min: 7ms (run #698)
max: 41ms (run #793)
avg: 8ms
✓ Should delete value in a bytes32 set in the Bytes32Set (25475ms)
Clearing set 3
Total runs: 2048
Gas Used
min: 23958 (10ms, run #0)
max: 23982 (9ms, run #257)
avg: 23980 (8ms)
Execution time
min: 6ms (run #1404)
max: 212ms (run #1083)
avg: 8ms
✓ Should delete value in a bytes32 set in the Bytes32Set (25295ms)
Clearing set 4
Total runs: 2048
Gas Used
min: 23958 (9ms, run #0)
max: 23982 (9ms, run #257)
avg: 23980 (8ms)
Execution time
min: 7ms (run #63)
max: 186ms (run #1370)
avg: 8ms
✓ Should delete value in a bytes32 set in the Bytes32Set (25286ms)
·-----------------------------------|----------------------------|-------------|-----------------------------·
| Solc version: 0.8.17 · Optimizer enabled: false · Runs: 200 · Block limit: 30000000 gas │
····································|····························|·············|······························
| Methods │
·············|······················|··············|·············|·············|···············|··············
| Contract · Method · Min · Max · Avg · # calls · usd (avg) │
·············|······················|··············|·············|·············|···············|··············
| Mapping · enumSetAdd · 74067 · 91203 · 74110 · 20480 · - │
·············|······················|··············|·············|·············|···············|··············
| Mapping · enumSetClear · 23958 · 23982 · 23980 · 20480 · - │
·············|······················|··············|·············|·············|···············|··············
| Mapping · enumSetCreate · 26455 · 43555 · 29875 · 5 · - │
·············|······················|··············|·············|·············|···············|··············
| Mapping · simpleBoolCreate · 48671 · 65771 · 48679 · 6144 · - │
·············|······················|··············|·············|·············|···············|··············
| Mapping · simpleBoolDelete · 21985 · 22009 · 22007 · 4096 · - │
·············|······················|··············|·············|·············|···············|··············
| Mapping · simpleStructCreate · 162699 · 179871 · 162773 · 6144 · - │
·············|······················|··············|·············|·············|···············|··············
| Mapping · simpleStructDelete · 41724 · 41744 · 41743 · 4096 · - │
·············|······················|··············|·············|·············|···············|··············
| Mapping · simpleUintCreate · 48574 · 65674 · 48582 · 6144 · - │
·············|······················|··············|·············|·············|···············|··············
| Mapping · simpleUintDelete · 21952 · 21976 · 21974 · 4096 · - │
·············|······················|··············|·············|·············|···············|··············
| Deployments · · % of limit · │
····································|··············|·············|·············|···············|··············
| Mapping · - · - · 795059 · 2.7 % · - │
·-----------------------------------|--------------|-------------|-------------|---------------|-------------·
16 passing (9m)
```
Sign in with Wallet
Connect another wallet