Implement: genesis nonce scheme

[lrettig]

See #104

For genesis we are implementing a simple "counter with gaps" nonce scheme: we use simple, ordered uint nonces, no bitfield, and nonces must be monotonically increasing but we allow gaps. (Note that we plan to upgrade to a more complex, generalized scheme later; see this forum thread for more information.)

Here's the straightforward specification for the scheme, including the four required algorithms:

• account state: stores a single 64-bit value (interpreted as uint64 for now)
• transaction data: given a raw tx, ParsePayload template method returns a uint64 nonce value (note that, in general, the nonce will be included explicitly in the tx, and may be compressed as a varint, but that in future some templates may choose to calculate the nonce some other way; none of this matters from the perspective of go-spacemesh)
• New tx filter (for mempool admittance)
  • New tx nonce must be strictly higher than current account state nonce value
  • If this nonce is already in the mempool, the new tx must have a higher fee than the existing tx; if so, the old tx is replaced; if not, the new tx is dropped
• Sorting
  • Strict integer ordering
• Validity predicate (execution phase)
  • New tx nonce must be strictly larger than current account state nonce value
• State update (execution phase)
  • Set account nonce to tx nonce

dev task breakdown:

• [x] https://github.com/spacemeshos/go-spacemesh/issues/3401
• [x] https://github.com/spacemeshos/go-spacemesh/issues/3402

[dshulyak]

remove reference to NextNonce(); change inequality (validity predicate) to compare >= current account nonce Set account nonce to tx nonce

this suggestion doesn't work. if you set account nonce to tx nonce, then the validity predicate will not exclude other txs with the same nonce.

i think what should be done is to change validity predicate to tx.Nonce >= account.NextNonce() and leave everything else as is

[lrettig]

@pigmej I think this is "refined" and ready for implementation

[countvonzero]

startNonce needs to be refactored. it should only contain the current nonce.

@lrettig what does current nonce mean? startNonce is the next nonce usable for this account.

[lrettig]

startNonce needs to be refactored. it should only contain the current nonce.

@lrettig what does current nonce mean? startNonce is the next nonce usable for this account.

removed this. I spent some time looking over the conservative cache code. I don't fully understand 100% of it. My gut feeling is that the number of required changes in small, but some of the changes will be subtle and hard to find. Will leave it to you to figure out how much needs to be refactored. txsByNonce is indexed by "nonce offset" (distance from next nonce?) - this logic is a little confusing - but I think this data structure is more or less okay if there are gaps. The logic around moreInDB will need to change a little to allow for gaps.

[countvonzero]

The logic around moreInDB will need to change a little to allow for gaps.

moreInDB was meant for 3 use cases

1. there are too many nonces for an account in the mempool. save the bigger nonce in db and retrieve later after earlier layers is applied
2. txs arrive with nonce gap in the mempool, they are saved in db and retrieved when the bridging txs arrive.
3. txs were deemed insufficient balance by the conservative state, but can be feasible after an earlier layer applied (may having incoming fund for that account)
4. a better tx arrived (higher fee) and made higher nonce txs infeasible due to insufficient balance deemed by conservative state. those kicked out txs are also retrieved from db once an earlier is applied. (variance of 3.)

with gap, we can eliminate scenario 2.

[countvonzero]

update. moving the last issue out of this PM issue as it's a genera database bug

https://github.com/spacemeshos/go-spacemesh/issues/3386