Where applicable, enforce uniqueness when handling slices

[wadealexc]

Many methods accept slices as arguments but do not explicitly enforce uniqueness of the slice's elements. This issue proposes criteria for various method params that should be met to ensure uniqueness.

Note that many methods implicitly enforce uniqueness. For example, Market.PublishStorageDeals relies on the market's state machine to ensure that passed-in Deals are unique:

https://github.com/filecoin-project/specs-actors/blob/0d2ebd356c45acb4c3d340ab9d81b20eb65fea03/actors/builtin/market/market_actor.go#L210-L217

While this particular implicit check appears sound, an explicit check will provide a stronger guarantee that changes to this method continue to enforce this important property.

Miner

• Miner.Constructor:
  • params.ControlAddrs[i] < params.ControlAddrs[i + 1]
  • params.Multiaddrs[i] < params.Multiaddrs[i + 1]
• Miner.ChangeWorkerAddress:
  • params.NewControlAddrs[i] < params.NewControlAddrs[i + 1]
• Miner.SubmitWindowedPoSt:
  • params.Partitions[i].Index < params.Partitions[i + 1].Index
• Miner.PreCommitSector:
  • params.DealIDs[i] < params.DealIDs[i + 1] (Note: this could be enforced in Market.VerifyDealsForActivation, instead)
• Miner.ExtendSectorExpiration:
  • This method should use the same approach used as TerminateSectors: adding passed-in ExpirationExtensions to a map, and ignoring duplicates. Alternatively, filter based on Deadline / Partition.
• Miner.ChangeMultiaddrs:
  • params.NewMultiaddrs[i] < params.NewMultiaddrs[i + 1]

Market

• Market.PublishStorageDeals:
  • adt.CidKey(params.Deals[i]) < adt.CidKey(params.Deals[i + 1])
• Market.VerifyDealsForActivation:
  • params.DealIDs[i] < params.DealIDs[i + 1]
• Market.ActivateDeals:
  • params.DealIDs[i] < params.DealIDs[i + 1]
• Market.OnMinerSectorsTerminate:
  • params.DealIDs[i] < params.DealIDs[i + 1]
• Market.ComputeDataCommitment:
  • params.DealIDs[i] < params.DealIDs[i + 1]

[anorth]

As an alternative to requiring the caller to sort parameters, we can check uniqueness in a dictionary. But the general principle of minimising on-chain work where we can offload it to callers suggests the sorting approach is good. It implies work for Lotus though (@arajasek @magik6k)

Related to #604.

[Stebalien]

I'm concerned that it could be asking too much of external implementers to require sorted inputs at this point.

[anorth]

The non-Go implementers? I wouldn't think so. They either have to match this, or match the dictionary-based uniqueness checks we'd add in each re-implemented actor method. Sorting seems easier, of the two.

@austinabell @Alexey-N-Chernyshov ?

[Stebalien]

I assumed external implementers were using the go specs-actors, right? All non-buggy implementations of everything outside of specs-actors should already avoid submitting duplicates (in most cases, at least). However, they almost certainly don't sort arrays.

[anorth]

They are re-implementing actors.

[Stebalien]

Oh, oh my.

[austinabell]

The non-Go implementers? I wouldn't think so. They either have to match this, or match the dictionary-based uniqueness checks we'd add in each re-implemented actor method. Sorting seems easier, of the two.

Dictionary based uniqueness checks isn't a problem. If the intention for a lot of this sorted and unique kvs, can just use rust's BTreeMap. Even if the sorting is offloaded to outside actors execution, we would still have to do the check inside, so I don't see how that helps in any way.

I would actually have a preference to not have to deserialize params and handle any respective sorting outside of actors, that seems really clunky. I don't really have a strong opinion on this but can think about it more later.

Oh, oh my.

rt, but how would you have expected anyone to consume this? Even without the panics and recovering for error handling, go -> c for an FFI isn't really an option from what I'm aware, and compiling to wasm from this with how it's setup isn't an option either (although I would have loved for this to be the case and would have personally preferred working toward this)

[Stebalien]

I was expecting people to write small shim VMs in go. Correctly re-implementing the abstract data types in other languages, mimicking caching behavior such that GAS charges are the same, will be tricky.

[austinabell]

I was expecting people to write small shim VMs in go. Correctly re-implementing the abstract data types in other languages, mimicking caching behavior such that GAS charges are the same, will be tricky.

Not possible to do this way for multiple reasons, and yes gas charges especially will be tough to match esp since tied to blockstore reads/writes, but that is only option with what we have available. I'm not too worried about the functionality of ADTs, I've matched cid roots in a bunch of test cases against go impls.

Thankful for the test vectors being developed now as this would be much more painful to match otherwise.

[whyrusleeping]

Why not just enforce uniqueness inside the actor methods? Seems like a lot of extra work to require this detail to leak out to anyone who wants to call any of these methods from any language

[anorth]

Why not just enforce uniqueness inside the actor methods?

We can, but "why not" is because it's extra work inside chain execution, extra work for every validating node in a flow that is already a bottleneck, as opposed to computation that happens just once at a caller. And similarly, extra complexity inside a security-critical component as opposed to off-chain.

The work and complexity are both minor, but our principle usually is to avoid them here.

[anorth]

We've determined this isn't a critical change needed for network launch. As we approach that point, adding more constraints on the node implementations adds risk there. It is still something I'd like to follow up with later just to reduce degrees of freedom.

@wadeAlexC I'd appreciate your reappraisal, in particular whether any of the case you cite don't have an implicit uniqueness constraints or could behave incorrectly given a duplicate.

[wadealexc]

I wasn't able to find any issues related to the cases I mentioned, as they all have implicit uniqueness checks.