jshaw-decides commented 1 year ago

L1: https://github.com/permaweb/rebar/blob/main/contracts/src/contract-L1.js

SEQ: https://github.com/permaweb/rebar/blob/main/contracts/src/contract-SEQ.js

The mint is a 2 step process:

create-mint (L1) creates a request {"<tx>": {qty: number, target: "<addr>", expires: number // block height}
mint (SEQ) processes the requests and adds each processed req to state.pile (string[])

Let me know if you want more info.

ppedziwiatr commented 1 year ago

Oh sorry, I've posted the issue before actually ending its content - there's much more to review/analyze than I initially expected, we will be posting some initial comments next week - but we first need to talk and analyze internally the idea with two contracts :-)

Thanks for the explanation so far!

jshaw-decides commented 1 year ago

Just wanted to update here that I just merged 1 more PR into this branch that removes the 1,000,000 feron (base unit of RebAR) validation before creating a mint request.

If people submit undefined / null reward on create-mint it will create a request for 0 tokens. The mint function filters those requests out before updating balances.

https://github.com/permaweb/rebar/pull/60

ppedziwiatr commented 1 year ago

Hmm..this one sounds weird to me. How can a L1 transaction be mined with undefined/null reward?

Even if for some reason sth like this would happen (which would probably mean some really serious error in the Arweave protocol and nodes implementation) - such transaction should be rejected in a L1 contract - probably here: https://github.com/permaweb/rebar/blob/main/contracts/src/write/create-mint.js#L22 (btw. this || 0 also looks weird - miners would not accept such transaction...and even if for some reason they would, it should be rejected by this contract).

ppedziwiatr commented 1 year ago

Also - a more general comment - not sure why exactly did you decide to use ramda to mutate the balances, but I believe it is very slow. I'm not an expert in Ramda and I don't know how exactly sth like over works internally (i thought that similar to a spread operator - but the benchmarks suggests that not) - but it seems to be really slow.

A simple benchmark that generates a balances map with 10k entries and makes 10k random changes:

import { over, lensProp, add } from 'ramda';

const iterations = 10_000;

const balancesMutate = testWithMutate(iterations);
const balancesSpread = testWithSpread(iterations);
const balancesRamda = testWithRamda(iterations);

/*console.log(balancesMutate);
console.log(balancesSpread);
console.log(balancesRamda);*/

function testWithSpread(iterations) {
  let { balances, keys } = generate(iterations);
  const keysArray = Array.from(keys);
  console.time("spread");
  for (let i = 0; i < iterations; i++) {
    const item = keysArray[Math.floor(Math.random() * keysArray.length)];
    balances = {
      ...balances,
      [item]: balances[item] + 100
    };
  }
  console.timeLog("spread");

  return balances;
}

function testWithRamda(iterations) {
  let { balances, keys } = generate(iterations);
  const keysArray = Array.from(keys);
  console.time("ramda");
  for (let i = 0; i < iterations; i++) {
    const item = keysArray[Math.floor(Math.random() * keysArray.length)];
    balances = over(
      lensProp(item),
      add(100),
      balances
    );
  }
  console.timeLog("ramda");

  return balances;
}

function testWithMutate(iterations) {
  let { balances, keys } = generate(iterations);
  const keysArray = Array.from(keys);
  console.time("mutate");
  for (let i = 0; i < iterations; i++) {
    const item = keysArray[Math.floor(Math.random() * keysArray.length)];
    balances[item] = balances[item] + 100;
  }
  console.timeLog("mutate");

  return balances;
}

function generate(iterations) {
  const keys = new Set();
  const balances = {};
  for (let i = 0; i < iterations; i++) {
    let key = makeid(43);
    while (keys.has(key)) {
      key = makeid(43);
    }
    keys.add(key);
    balances[key] = 100;
  }

  return { balances, keys };
}

function makeid(length) {
  let result = '';
  const characters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789';
  const charactersLength = characters.length;
  let counter = 0;
  while (counter < length) {
    result += characters.charAt(Math.floor(Math.random() * charactersLength));
    counter += 1;
  }
  return result;
}

Results (reproducible with each run) on my M1:

mutate: 1.092ms
spread: 21.294s
ramda: 12.394s

So it is not as slow as spread (though you're additionally spreading the whole state each time), but in general is much slower that the simple, mutable version. Not sure what is the idea with introducing immutability here - since the whole idea of the write contract functions is to mutate the state...

Maybe my benchmark is wrong - it would be great if you could review it. The 'ramda' based code has been adapted from https://github.com/permaweb/rebar/blob/main/contracts/src/util.js#L122 .

I expect this contract to have a lot of balance mutating interaction (current BAR has already ~0.5M interactions, 99% of them mutate the balances) + the balances map will be probably quite big (so - aparat from performance - there's probably also a big 'penalty' in a heap usage - which I'll measure later).

ppedziwiatr commented 1 year ago

Another benchmark, this time with a more real-world values (the current size of the balances map of the BAR contract - 1664; and the current amount of interactions (~500k).

mutate: 19.127ms
ramda: 59.058s

- so it's ~3000 times slower (!) in this case.

But maybe my testing procedure is wrong?

import { over, lensProp, add } from 'ramda';

const interactions = 500_000;
const balancesSize = 1664;

const balancesMutate = testWithMutate(interactions, balancesSize);
// const balancesSpread = testWithSpread(iterations, balancesSize);
const balancesRamda = testWithRamda(interactions, balancesSize);

/*console.log(balancesMutate);
console.log(balancesSpread);
console.log(balancesRamda);*/

function testWithSpread(iterations, balancesSize) {
  let { balances, keys } = generate(balancesSize);
  const keysArray = Array.from(keys);
  console.time("spread");
  for (let i = 0; i < iterations; i++) {
    const item = keysArray[Math.floor(Math.random() * keysArray.length)];
    balances = {
      ...balances,
      [item]: balances[item] + 100
    };
  }
  console.timeLog("spread");

  return balances;
}

function testWithRamda(iterations, balancesSize) {
  let { balances, keys } = generate(balancesSize);
  const keysArray = Array.from(keys);
  console.time("ramda");
  for (let i = 0; i < iterations; i++) {
    const item = keysArray[Math.floor(Math.random() * keysArray.length)];
    balances = over(
      lensProp(item),
      add(100),
      balances
    );
  }
  console.timeLog("ramda");

  return balances;
}

function testWithMutate(iterations, balancesSize) {
  let { balances, keys } = generate(balancesSize);
  const keysArray = Array.from(keys);
  console.time("mutate");
  for (let i = 0; i < iterations; i++) {
    const item = keysArray[Math.floor(Math.random() * keysArray.length)];
    balances[item] = balances[item] + 100;
  }
  console.timeLog("mutate");

  return balances;
}

function generate(size) {
  const keys = new Set();
  const balances = {};
  for (let i = 0; i < size; i++) {
    let key = makeid(43);
    while (keys.has(key)) {
      key = makeid(43);
    }
    keys.add(key);
    balances[key] = 100;
  }

  return { balances, keys };
}

function makeid(length) {
  let result = '';
  const characters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789';
  const charactersLength = characters.length;
  let counter = 0;
  while (counter < length) {
    result += characters.charAt(Math.floor(Math.random() * charactersLength));
    counter += 1;
  }
  return result;
}

I've also confirmed that over creates a shallow copy - that's why it behaves very similar to the native 'spread' version.

What is really alarming is that with the increasing balances size, the difference is even bigger - e.g. for a 5000 entries in balances (and same 500k interactions):

mutate: 23.46ms
ramda: 4:36.545 (m:ss.mmm)

12000x slower...

I'm not even trying to measure this with 10k entries in balances :-)

jshaw-decides commented 1 year ago

Wow! Thanks for this. Already looking into how to solve some of these issues.

Issue 1 (0 reward)

Hmm..this one sounds weird to me. How can a L1 transaction be mined with undefined/null reward?

Going to solve this in create-mint by:

ce(roundDown(SmartWeave.transaction.reward / 1e6) < 1, 'You must mint at least 1 feron.')

Issue 2 (benchmarks)

Another benchmark, this time with a more real-world values (the current size of the balances map of the BAR contract - 1664; and the current amount of interactions (~500k).

Thanks so much for these tests. Great catch, we can remove ramda from any state changes. Reading through these docs, it sounds like it would be smarter to go with Key/Value for balances, https://docs.warp.cc/docs/sdk/advanced/kv-storage#enabling-kv-storage-for-contract.

I'm planning to refactor with Key / Value, does that sound good to you?

jshaw-decides commented 1 year ago

Hmm..this one sounds weird to me. How can a L1 transaction be mined with undefined/null reward?

Even if for some reason sth like this would happen (which would probably mean some really serious error in the Arweave protocol and nodes implementation) - such transaction should be rejected in a L1 contract - probably here: https://github.com/permaweb/rebar/blob/main/contracts/src/write/create-mint.js#L22 (btw. this || 0 also looks weird - miners would not accept such transaction...and even if for some reason they would, it should be rejected by this contract).

I will remove the || 0 as it wont be an issue with the solution to Issue 1

ppedziwiatr commented 1 year ago

Hey, we will discuss this internally tomorrow and will return with an advice. The autosync feature currently does not sync the kv storage values (we will obviously introduce such feature at some point..), but...

Let's be realistic here - there are currently ~160k addresses on Arweave (according to https://viewblock.io/arweave/stats?tab=address - not sure, how to verify this 'directly). A map with this amount of address takes 12-14mb in memory (if I'm profiling correctly..), so it's not that bad. The benchmark with the simple, mutable version, takes 60ms (with 500000 interactions and 150k entries in balances), so it's also fine for now (I didn't test this case with ramda - a test with 10k entries in balances took over 12 minutes on my M1..).

To sum up - even with all current Arweave addresses, the standard approach should be fine for now - as long as you will simply mutate the state (the ramda version is really slow.

Do you plan to introduce the evolve feature? How do you plan to handle potential bug fixes, etc?

jshaw-decides commented 1 year ago

Hey, we will discuss this internally tomorrow and will return with an advice. The autosync feature currently does not sync the kv storage values (we will obviously introduce such feature at some point..), but...

Let's be realistic here - there are currently ~160k addresses on Arweave (according to https://viewblock.io/arweave/stats?tab=address - not sure, how to verify this 'directly). A map with this amount of address takes 12-14mb in memory (if I'm profiling correctly..), so it's not that bad. The benchmark with the simple, mutable version, takes 60ms (with 500000 interactions and 150k entries in balances), so it's also fine for now (I didn't test this case with ramda - a test with 10k entries in balances took over 12 minutes on my M1..).

To sum up - even with all current Arweave addresses, the standard approach should be fine for now - as long as you will simply mutate the state (the ramda version is really slow.

Do you plan to introduce the evolve feature? How do you plan to handle potential bug fixes, etc?

We plan on releasing this without the evolve feature. We want to get this right.

jshaw-decides commented 1 year ago

Issue 1 PR (i'll have another one shortly for Issue 2)

https://github.com/permaweb/rebar/pull/63

jshaw-decides commented 1 year ago

Issue 2 PR

https://github.com/permaweb/rebar/pull/64

jshaw-decides commented 1 year ago

Key value store implemented in #66

All tests passing. @ppedziwiatr we ready for you 😄

jshaw-decides commented 1 year ago

@ppedziwiatr you'll be happy to know we are no longer doing any spreads and have removed ramda.

This was done here: https://github.com/permaweb/RebAR/pull/69

Looking forward to hearing back 😄

ppedziwiatr commented 1 year ago

Hey, we will be reviewing this again today and/or tomorrow.

jshaw-decides commented 1 year ago

Hey, we will be reviewing this again today and/or tomorrow.

Beautiful, thanks. This PR adds a constructor function for migrating the balances into the KV store: https://github.com/permaweb/RebAR/pull/71. There won't be anymore code going in until you're done.

ppedziwiatr commented 1 year ago

Ok, here are some new comments:

KV Storage

I believe our recommendation was to stick with traditional state for now :-). The KV is still kinda young and not-so-mature solution + as we've mentioned, it does not currently work with autoSync feature of the SDK. I've pasted you in a message earlier (https://github.com/permaweb/RebAR/issues/52#issuecomment-1537522237) some estimates re. state size in a pessimistic scenario (i.e. all current addresses in state - ~150K - current BAR has ~1500, so 2 orders of magnitude less) - and it would still hold up pretty well. It probably could become a problem in case of millions of addresses - but not sure when this will happen (and it could be probably handled by a "hard fork" of a contract - i.e. deploying a new contract with a initial state from the old one (and moving the balances into KV storage in the constructor function of the forked contract). Again, we're trying to be realistic here. The final decision is up to you :-)

Minor comments in this case:

if you decide to stick with KV - https://github.com/permaweb/RebAR/blob/main/app/src/api/interface/index.ts#L9 - is this definition still valid?
the L1.state.requests seems to be used as an array - https://github.com/permaweb/RebAR/blob/main/contracts/initial-state-L1.json#L8 https://github.com/permaweb/RebAR/blob/main/contracts/src/write/create-mint.js#L23 but is defined an object/map: https://github.com/permaweb/RebAR/blob/main/app/src/api/interface/index.ts#L38
shouldn't be divisibility be defined in L1 contract? - it used there 'directly' - as a hardcoded value in contract code: https://github.com/permaweb/RebAR/blob/main/contracts/src/write/create-mint.js#L18 It is defined in L2 contract - https://github.com/permaweb/RebAR/blob/main/contracts/initial-state-SEQ.json#L9 - but doesn't seem to be used by the L2 contract code. Or maybe it should be defined in both contracts?
shouldn't the L2 contract be deployed with internalWrites:true in manifest? If so, have you considered whitelisting sources? https://github.com/warp-contracts/warp/issues/403

Scalability

You've tried to optimize the balances storage (via the KV storage) - but there seems to be much bigger potential issues with contract scalability:

The `L1Contract.requests` array

The L1Contract.requests array (https://github.com/permaweb/RebAR/blob/main/contracts/src/write/create-mint.js#L23), which seems to grow with each new create-mint and is not pruned/cleared anywhere. So we can assume that it will have ~ as many entries, as there will be interactions with the L1 contract
(current BAR contract has ~600k interactions). This array is then returned by the view function in the L2 contract - i.e. each time all entries - https://github.com/permaweb/RebAR/blob/main/contracts/src/write/mint.js#L15.

What is worse, again Ramda is being used on this whole (potentially huge!) array with multiple 'map' operations - each probably creates a new copy of the array (to stick with functional programming 'immutable data' mantra) - which will probably again KILL the performance and potentially cause the V8 to explode with OOM (on the default heap size settings).

Additionally - the L2 contract holds its own array - pile - which - if we understand correctly - holds all the processed transactions - https://github.com/permaweb/RebAR/blob/main/contracts/src/write/mint.js#L27 - and will also grow quickly. This will slow down the notInPile function - https://github.com/permaweb/RebAR/blob/main/contracts/src/write/mint.js#L43 Also - the notInPile function has potentially quadratic complexity - (filter x includes). Ideally, the pile should be modeled as a Set, which would allow to simply use the has method (which has O(1) complexity)) - but sets cannot be stored in state, as they are not serialized by default by JS stringify/parse.

The combineQuantitiesByTarget https://github.com/permaweb/RebAR/blob/main/contracts/src/write/mint.js#L53 has also potentially O(n2) time complexity - as it effectively makes two nested iterations over arrays (forEach x findIndex) The combinedArr should be a Map in this case (instead of an array), which will allow lookups in constant time. Also, we would advise to use a traditional for loop (instead of a forEach, which tends to have 2-3x worse performance)

Our recommendations :

clear the L1Contract.requests on each create-mint operation - we believe that all the expired entries can be simply removed. Since the entries expire after 720 blocks - a pessimistic estimation here is that (with pruning) the array will hold at most 720000 elements (Arweave allows max 1000 transactions in a block and we assume here that all of them will be create-mint) - so it's still a potentially huge array to handle
clear the L1Contract.pile array. This array currently seems to hold only the tx ids, so it's hard to find a criteria on which the array could be cleared. Maybe consider storing a map txId->expiryHeight - and remove all the entries that would be otherwise expired?
Try to further minimze the use of Ramda - i.e. be aware that all the operations create copies of the input data - which in case of big arrays like the requests and pile might have a huge performance and memory penalty.
Make some performance tests - i.e. simulate 1M create-mint interactions with 10k different wallets - and observe both the evaluation time and memory usage (with a help of a profiler)

Usability

Who will be responsible for calling the 'mint' function on the L2 contract? do you plan to add some scheduler that will perdiodically generate such interaction?

ppedziwiatr commented 1 year ago

One last question - how do you plan to handle forks in case of L1 create-mint transactions?

Let's assume this scenario:

Someone calls create-mint on L1 contract
after some time, the 'mint' on L2 is being called and tokens from point 1 are minted in L2 contract
BUT after few more blocks it turns out that the transaction from point 1 happened to land in a forked block (which is no longer part of the 'main' chain - nor is the 'create-mint' transaction from this block) - what now? The L2 tokens have been effectively minted on a 'non-existent' L1 transaction basis.

jshaw-decides commented 1 year ago

Hey @ppedziwiatr, thanks for the feedback above. I have implemented most of it already.

Regarding this:

One last question - how do you plan to handle forks in case of L1 create-mint transactions?

Let's assume this scenario:

Someone calls create-mint on L1 contract

after some time, the 'mint' on L2 is being called and tokens from point 1 are minted in L2 contract

BUT after few more blocks it turns out that the transaction from point 1 happened to land in a forked block (which is no longer part of the 'main' chain - nor is the 'create-mint' transaction from this block) - what now? The L2 tokens have been effectively minted on a 'non-existent' L1 transaction basis.

@twilson63 mentioned this:

Based on the warp documentation, I read that the Warp Sequencer does not sync L1 transactions until they have been confirmed after 10 blocks. So it might be best to ask PPE, if this is the case

Is this the case?

The choice to split the contract comes down to a tradeoff:

we don't want people to be able to be able to make a transfer with tokens on L1 and then transfer the same tokens with an L2 transaction.

In a perfect world, we would be able to do something like this to control SourceType at the function level:

{
  "sourcePermissions": {
    "mint": SourceType.ARWEAVE,
    "transfer": SourceType.SEQUENCER,
    "*": SourceType.SEQUENCER
  }
}

If this were the case, we would only use 1 contract.

ppedziwiatr commented 1 year ago

Based on the warp documentation, I read that the Warp Sequencer does not sync L1 transactions until they have been confirmed after 10 blocks. So it might be best to ask PPE, if this is the case

Is this the case?

The choice to split the contract comes down to a tradeoff:

we don't want people to be able to be able to make a transfer with tokens on L1 and then transfer the same tokens with an L2 transaction.

Yeah, I realized that's handled on our side - as long as you will be using Warp with default settings and/or our standard DRE nodes. So this one shouldn't be an issue.

{ "sourcePermissions": { "mint": SourceType.ARWEAVE, "transfer": SourceType.SEQUENCER, "*": SourceType.SEQUENCER } }

Interesting idea, we will discuss this internally.

ppedziwiatr commented 1 year ago

Ok, so how about leaving one contract, without changing the manifest implementation (we don't want to make it even more complicated than now), but:

each interaction has info about its source (arweave or sequencer - GQLNodeInterface.source) - this information simply isn't available in the SmartWeave global object - but that's a quick and easy change. Having this information available in the contract code, you could verify it at the beginning of the 'mint' function (i.e. verify if SmartWeave.transaction.source == 'arweave' (that's how this information would be probably exposed for the contract)
additionally - you would need to verify whether the 'mint' transaction is a 'direct' transaction (not an internal write) - because obviously only direct transactions should be allowed in this case. This can be easilly verified by checking whether SmartWeave.transaction.owner == SmartWeave.caller (they are different for internal writes - i.e. the SmartWeave.caller is than set to the txId of the calling contract).

ppedziwiatr commented 1 year ago

E.g. https://github.com/warp-contracts/warp/commit/9228f4dffe611c565abcbe038f0682119f11c84a - SmartWeave.transaction.origin would return L1 or L2 - L2 should be blocked in the contract for the 'create-mint' operation.

jshaw-decides commented 1 year ago

Ok, so how about leaving one contract, without changing the manifest implementation (we don't want to make it even more complicated than now), but:

each interaction has info about its source (arweave or sequencer - GQLNodeInterface.source) - this information simply isn't available in the SmartWeave global object - but that's a quick and easy change. Having this information available in the contract code, you could verify it at the beginning of the 'mint' function (i.e. verify if SmartWeave.transaction.source == 'arweave' (that's how this information would be probably exposed for the contract)

additionally - you would need to verify whether the 'mint' transaction is a 'direct' transaction (not an internal write) - because obviously only direct transactions should be allowed in this case. This can be easilly verified by checking whether SmartWeave.transaction.owner == SmartWeave.caller (they are different for internal writes - i.e. the SmartWeave.caller is than set to the txId of the calling contract).

Hey, would love this @ppedziwiatr, though not necessary now?

I believe we avoid the issue with the current architecture, so long as we know only interactions with 10 confirmations are in the queue (and I believe we do).

Working on the perf test right now.

ppedziwiatr commented 1 year ago

I was proposing a solution for the

If this were the case, we would only use 1 contract.

(without further complicating the manifest itself, but with the same functionality/safety).

Obviously it's up to you to decide whether you want to stick with two different contracts or merge into one :-).

Who will be responsible for calling the L2's mint function?

jshaw-decides commented 1 year ago

The user will be responsible for claiming their tokens, though they should never have to assuming bundlers will be running mint as well.

jshaw-decides commented 1 year ago

All of the issues are resolved here: https://github.com/permaweb/RebAR/pull/72

ppedziwiatr commented 1 year ago

hmm, I don't see a fix for clearing the 'requests' array in the L1 contract - https://github.com/permaweb/RebAR/pull/72/files#diff-314fb570ac40b4149c4efaac3179576fbfff006d8f3c160a6d7ce84dbcc7fb19

There's only a fix for clearing the 'pile' in the L2 contract - byt mayby I'm missing something?

jshaw-decides commented 1 year ago

@ppedziwiatr The requests are being filtered here: https://github.com/permaweb/RebAR/blob/main/contracts/src/contract-L1.js#L14 in the handle function.

permaweb / U

Contract code #52

Issue 1 (0 reward)

Issue 2 (benchmarks)

Issue 1 PR (i'll have another one shortly for Issue 2)

Issue 2 PR

KV Storage

Scalability

The `L1Contract.requests` array

Usability

permaweb / U

Contract code #52

Issue 1 (0 reward)

Issue 2 (benchmarks)

Issue 1 PR (i'll have another one shortly for Issue 2)

Issue 2 PR

KV Storage

Scalability

The L1Contract.requests array

Usability

The `L1Contract.requests` array