State Expiration Persistent 'has' ops | Stellar Developers | Page 1

wheat apex Jun 16, 2023, 1:28 AM

#

In the new state expiration proposal, for persistent data is 'has' reliability supported or how do we support it?

has or exists is usually simple, true or false.

With the new evicted cache, what would be the behavior?

cc @fringe dirge @lofty wave @formal echo

#

It might be helpful if we can write out a matrix of behaviors for every function: create, has, get, set.

#

With what the behavior is if never existed, deleted, created and on ledger, created and expired, created and evicted, created and evicted and bloom filter miss, never existed and bloom filter miss, etc.

sour flare Jun 16, 2023, 2:06 AM

#

Why would we want to complicate it? “Exists” should require a proof if not on ledger (and panic). That way it only returns true/false.

wheat apex Jun 16, 2023, 2:56 AM

#

I don't want to complicate it, I want to understand what the plan is.

#

How does the env distinguish between the false and panic cases?

#

I think we still need to spec this very clearly.

wheat apex Jun 16, 2023, 3:42 AM

#

sour flare Why would we want to complicate it? “Exists” should require a proof if not on le...

@sour flare is the below consistent with what you mean by, on ledger?

never existed = false

never existed and bloom filter miss = panic

deleted = false

deleted and bloom filter miss = panic

created and on ledger = true

created and expired (on ledger) = true

created and evicted = true

created and evicted and bloom filter miss = panic

fringe dirge Jun 16, 2023, 6:20 AM

#

This is correct with one small caveat

#

Created and evicted and bloom filter miss is not possible. This would require the bloom filter to return a false negative, which is not possible. A bloom filter might falsely claim that an entry is in the ESS when it really isn't, but if an entry is in the ESS, the bloom filter is guaranteed to claim the entry exists

wheat apex Jun 16, 2023, 6:42 AM

#

Adjusting to better capture that explanation. Is this accurate?

never existed = false

never existed but bloom filter incorrectly says it is evicted = panic

deleted = false

deleted but bloom filter incorrectly says it is evicted = panic

created and on ledger = true

created and expired (on ledger) = true

created and evicted = true

#

I think there's a problem in what I wrote above though. How does the environment tell the difference between these cases, for something like a call to env.storage().persistent().has("key")?

never existed but bloom filter incorrectly says it is evicted = panic

deleted but bloom filter incorrectly says it is evicted = panic

created and evicted = true

If the bloom filter says the value is evicted either correctly or incorrectly, we'll need to pick one of the above two values, panic, or true. @sour flare It sounds like you suggested the value should be panic.

#

So the matrix would be:

never existed = false

never existed but bloom filter incorrectly says it is evicted = panic

deleted = false

deleted but bloom filter incorrectly says it is evicted = panic

created and on ledger = true

created and expired (on ledger) = true

created and evicted = panic

#

So I think the logic can be described:

evicted from the perspective of the bloom filter = panic
otherwise, true or false

wheat apex Jun 16, 2023, 3:50 PM

#

Because has can panic, we'll also need a try_has which will presumably return: true, false, maybe.

ancient elm Jun 16, 2023, 6:39 PM

#

I think we decided against that, right?

wheat apex Jun 16, 2023, 6:43 PM

#

Yes, I think consensus when discussing this morning was that:

has and get will consistently panic if believed evicted (which may be a false positive), otherwise true/false
- Why: So it behaves just like footprints that don't contain a value.
and, that @fringe dirge will write up a matrix of the has/get/set behaviour in true/false/panic scenarios to make sure it's really clear what the behaviors will be

#

Nobody said this explicitly, but I believe set is also consistent and will follow the same rule as has and get.

#

@fringe dirge is that accurate?

fringe dirge Jun 16, 2023, 7:34 PM

#

No, I think what we decided on is thatset will be the only function that uses the bloom filter. Here is the matrix with different failure modes: https://docs.google.com/spreadsheets/d/1uv_QV8NUWF2Ncul2Yvz6jSCtYL--AAGhRrtZebnHa8s/edit?usp=sharing

Google Docs

Storage Proof Failure Modes for Persistent Entries

Sheet1

Operation,Entry Live On BucketList*,Not in BucketList, not in ESS, bloom correct,Not in BucketList, not in ESS, bloom false positive,Not in BucketList, in ESS
get,Returns entry,panic,panic,panic
set,Sets entry,creates entry,panic,panic
has,returns true,panic,panic,panic
remove,removes ent...

#

I think we should rename has to is_live, where is_live returns true if the entry in on the BucketList and returns false is the entry either has never existed or is in the ESS

ancient elm Jun 16, 2023, 7:41 PM

#

why should has panic if entry is not in ess?

#

it should just return false

#

because we know that the entry doesn't exist in storage, right?

#

we only panic if we think that entry might be in ESS

fringe dirge Jun 16, 2023, 7:47 PM

#

I don't think we can have a has function that is both safe and useful. Suppose the flow looks like this

has(key):
  if existsOnBucketList(key):
    return true
  else if bloom_filter.isInESS(key):
    # The bloom filter could return a false positive
    # We have no way of knowing if key exists in ESS or not
    panic()
  else if !bloom_filter.isInEss(key):
    return false

#

You're right, I modified the matrix a bit to account for this

#

The issue is if the entry exists on the BucketList, we can give a deterministic answer. Otherwise, we have no way of knowing if the entry actually exists in the ESS or if we get a false positive. We can only return false if we get a bloom miss, which is not deterministic

ancient elm Jun 16, 2023, 7:50 PM

#

basically for simplicity we can phrase is in terms of state, without going into details. I think the states are: "definitely exists", "definitely doesn't exist", "maybe evicted". 'maybe' is because of false positives

#

I think your matrix doesn't map to that though; it misses the case when entry is not on bucket list and bloom filter gives negative response ('definitely doesn't exist' in my notation)

fringe dirge Jun 16, 2023, 7:52 PM

#

Sure, but do we want to expose this to users? Again like in the random nonce NFT example, this allows users to create nonces for free and not pay rent because they can just call has without actually restoring the entry

ancient elm Jun 16, 2023, 7:52 PM

#

that's not possible, is it?

#

has will only work if entry definitely doesn't exist. if bloom filter returns a positive result, it will just panic

fringe dirge Jun 16, 2023, 7:58 PM

#

ancient elm I think your matrix doesn't map to that though; it misses the case when entry is...

Sure, but we're introducing a nondeterministic nonce bug if we allow try_has. Consider a sneaky nonce implementation that want's to avoid paying for nonce restoration:

fn does_nonce_exist(key)
{
  Option<bool> op = env.storage().persistent().try_has(key);
  if op.has_value():
    return op;
  else if !op.has_value():
     // This is only incorrect 1:1 billion times
     return true;
}

#

This is not a correct implementation, but it's so unlikely to be incorrect that I would probably do it if I wanted to spin up a bunch of random nonces and not pay for them

ancient elm Jun 16, 2023, 8:00 PM

#

but we don't allow try_has, do we?

fringe dirge Jun 16, 2023, 8:01 PM

#

If we don't allow try_has I think it's fine

ancient elm Jun 16, 2023, 8:03 PM

#

I think we decided we don't want to allow it

#

there is another issue, but it's somewhat tangential; I'll post about it in a different thread

wheat apex Jun 16, 2023, 8:46 PM

#

I think we should leave out try_has. It would only serve to provide insight into eviction state.

#State Expiration Persistent 'has' ops