Have a deterministic Map struct that can be go-wired

[sunnya97]

No description provided.

[zmanian]

Here are the options based on previous research.

1. Fork this code
   https://golang.org/src/runtime/hashmap.go and just create a constructor that sets hash0 via an initialization argument.
   Downsides: breaks interoperability with Golang builtins but it otherwise the same api as normal golang maps and uses the audited code that everyone uses.

2. This is a pretty sane looking deterministic hashmap but no one really uses it . https://github.com/cornelk/hashmap

3. As far as I know golang maps are only unsafe in consensus if control flow depends on iteration order. These things are pretty easy to detect. We could probably write a lint against this pattern more easily than 1 or 2

[cwgoes]

I think this is worthwhile - even if we could write Gaia without it, I can imagine lots of SDK applications that would want to use a map - better that we provide a common option, test it ourselves, and provide clear documentation on how to use it safely (deterministically).

[ebuchman]

As far as I know golang maps are only unsafe in consensus if control flow depends on iteration order. These things are pretty easy to detect. We could probably write a lint against this pattern more easily than 1 or 2

I like the idea of getting a linter into SDK app build workflow - we can flag other sources of non-determinism too, like time, rand, float

[mappum]

One thing to watch out for with deterministic maps is that attackers may be able to make operations extra expensive by choosing colliding hashmap hashes for many values, so that the bucket gets really long and you get worst-case performance. (This was a problem in Node.js for a while, they fixed it by making the hash function different across processes).

I think we'd have to fix this by doing something like consuming gas based on the number of values in the bucket.

[ebuchman]

Yeh good point. Linting obviously isn't enough.

What about just using the KVStore interface for this ? We would just need a way to marshal/unmarshal KVStore ...

[sunnya97]

I think maybe having a Map interface would be good, and then we can have like different implementations. TreeMap, HashMap, ListMap, etc?

Also regarding a TreeMap, if amino gives us length of the bytes, could we serialize the TreeMap efficiently, such that we can read in log(n) without deserializing the entire tree?

[zmanian]

@mappum This is super insightful.

[ebuchman]

I think maybe having a Map interface would be good, and then we can have like different implementations. TreeMap, HashMap, ListMap, etc?

Let's do this.

Also regarding a TreeMap, if amino gives us length of the bytes, could we serialize the TreeMap efficiently, such that we can read in log(n) without deserializing the entire tree?

That would be great - will have to investigate

[jackzampolin]

I think we changed encoding formats since go-wire so I'm going to assume this issue has been addressed. Closing.

[cwgoes]

I think we changed encoding formats since go-wire so I'm going to assume this issue has been addressed. Closing.

Alas, that was merely a name change - this is still a problem. Definitely post-launch though.

[jackzampolin]

Is this still something we should do?

[alexanderbez]

With the move to directly using proto (or a simple wrapper of one), I don't see the need for this.

[zmanian]

The way protobuf works is that the spec doesn't specific deterministic maps but most implementation sort keys before serialization.

[alexanderbez]

Seems reasonable to me. This is generally something we hold as an invariant in the SDK anyway.

[jackzampolin]

So going to close.