Consider proto.Any / proto compatible message for registered types

[liamsi]

Currently "registered types" are done via prefixing the (proto) encoded struct bytes with its "prefix bytes" as described in the Readme.
An alternative we could consider is to use proto.Any:

• https://github.com/protocolbuffers/protobuf/blob/78ca77ac8799f67fda7b9a01cc691cd9fe526f25/src/google/protobuf/any.proto#L122-L155
• https://developers.google.com/protocol-buffers/docs/proto3#any

Basically we would use the type URL to differentiate between the actual send bytes.

Pros:

• full proto compatibility
• more human readable (as URL is string based; basically as the amino name)

Cons:

• type URLs could be long(er than current prefixes)

---

Update: The discussion (here and on slack) evolved quite a bit. It could be worthwhile to write our own proto wrapper for any registered type and keep the prefix bytes instead of a string based URL scheme (like proto.Any).

Here I summarize pros/cons of both approaches:

proto.Any

Pros:

• developers might already be familiar with the concept
• proto implementations provide some tooling around proto.Any
• messages contain a human readable/understandable identifier (the type URL)

Cons

• additional overhead of adding a (non size limited) string to the proto encoding (type URL)

our own proto message / BytePrefixedAny

Pros:

• closer to the existing amino library (we can keep the prefix/disfix logic)
• byte prefix / disfix are shorter -> less load on the wire or when storing

Cons:

• people need to understand how prefix/disamb bytes are computed (we need to provide guidance and implementations)
• slightly more computation when computing prefix
• less human parseable

to be continued

[mossid]

As another alternative, we can tweak the prefix bytes generation to make it proto field bytes. The available range of field numbers is 1 - 2^29-1 which is encoded into max 4 bytes varint(with 3 bytes 5 bit modifiable bits). This is narrower than current range and we cannot use disfix bytes, but I think this can be covered by other mechanics, such as rehashing several times to find unreserved prefix bytes and use the 5bit part of the modifiable bits for indicating how many times rehash been done

[jordaaash]

Interesting!

I saw this @ https://github.com/protocolbuffers/protobuf/blob/78ca77ac8799f67fda7b9a01cc691cd9fe526f25/src/google/protobuf/any.proto#L144-L146

  // Note: this functionality is not currently available in the official
  // protobuf release, and it is not used for type URLs beginning with
  // type.googleapis.com.

There's also this issue: protobufjs/protobuf.js#435

I'm not very familiar with protobuf in general, so I'm not sure how to determine whether this is supported.

[jordaaash]

Looks like it has at least some support in JS.
Refs (primarily for myself) to check out:

https://github.com/protobufjs/protobuf.js#using-custom-classes
protobufjs/protobuf.js#677
protocolbuffers/protobuf#2612
protobufjs/protobuf.js#1082
protocolbuffers/protobuf-javascript#68
https://github.com/protocolbuffers/protobuf/blob/master/js/binary/proto_test.js#L646-L662

[liamsi]

@jordansexton I think proto.Any is well supported by now in JS implementations. I have not experimented with it a lot though, at least not in JS.

@mossid Thanks! If I understand you correctly, you are suggesting to encode registered messages like this:

message SomeRegisteredType {
  bytes prefix = 1; // prefix & potentially disfix bytes
  ActualMsg msg = 2; // actual concrete struct
}

message ActualMsg { /* ... */}

or even (?):

message SomeRegisteredType {
  bytes prefix = 1; // prefix & potentially disfix bytes
  bytes value = 2; // proto encoding of actual concrete struct
}

The main benefit / motivation for this instead of Any would be that we can save some bytes on the wire with this approach, right?

[mossid]

Not exactly, but I think that will also work.

message MessageContainingInterface {
    oneof interf_message {
        RegisteredTypeA rta = 3856223;
        RegisteredTypeB rtb = 21998056;
    }
}

is closer, where the fields values are encoded into varlength prefix bytes. @liamsi And yes both alternatives will take much smaller size on encoded form than storing full type url.

One problem with this alternative is that the size is limited to 29bit, so we cannot add disamb prefix when collision happens. Using large field numbers by default & use explicit prefix field when collision seems good combination of two methods.

[liamsi]

oneof would be even more compact but has the downside that the order of fields (inside the oneof) has to be exactly the same for everyone involved. That makes it more difficult to coordinate when we want to extend this and add another concrete implementation (every app / module developer need to have the same oneof). With proto.Any it is only the new type URL(s) you care about that you need to know (and order does not matter). In that sense proto.Any is more independent as you do not need to know about all implementations of an interface.

In your message example definition above: why would prefix bytes be necessary at all? My understanding is that oneof determines what the "one" thing contained is by the field number. Or are you suggesting the field numbers should be represented by the prefix bytes (and hence they are so large in your example? namely 3856223 and 21998056)?

[liamsi]

After chatting with @mossid over lunch: he is indeed proposing to use the prefixes as the field number. Some things to consider:

You also cannot use the numbers 19000 through 19999

https://developers.google.com/protocol-buffers/docs/proto#assigning-field-numbers

I think collisions are less of a concern. Wouldn't we only need to prevent collisions per interface (oneof message)? These should be less likely than "global collisions". This approach would definitely work as well and could potentially save us some bytes on the wire. Thanks Joon!

[liamsi]

I think using proto.Any instead of oneof providers users more flexibility & more convenience when they want to add their own types (any two side communicating just need to know the URL/name and the value can simply be anything proto encoded; parties talking to each other need of course to know what the value will be).

The oneof approach is closer to what we have now and needs slightly more coordination/orchestration (updating the central proto file / codec whenever sth changes/new types get added).

I think the first better fits with the vision of apps and app devs easily and autonomously can add their own types. Any thoughts on this?

[mossid]

After discussing: proto.Any is essentially a pair of {type_url, value}. The binary file which handles the Any switches over the type_url and manually decodes the value. This seems more flexible, as we don't have to modify interface type messages each time we add a new concrete type on it. However, the type_url is a human readable url-style dynamic length string. Considering that the concrete type will be wrapped with Any all the times and they are stored in the state(which is the most expensive operation), it will be better to use fixed size bytestring, as we are doing in current amino.

We can define a new message type like Amino(basically the same one with #267 (comment)) which is equivalent to Any but type_url is substituted with prefix_bytes, a fixed size(4 or 8bytes) prefix bytes. To increase the size efficiency further, the prefix bytes can have a type of fixed32, which is 4 byte fixed size integer, as it does not require a byte indicating the length of the byte slice(there is no fixed size bytestring in protobuf).

[liamsi]

Speaking in terms of protobuf this means introducing another wrapper type which is very similar to proto.Any. The wrapper would be message like this:

message BytePrefixedAny {
  bytes amino_prefix = 1; // the amino prefix bytes (default will be 4 bytes but this is not size limited and could also be with disambiguation bytes)

  // Must be a valid serialized protocol buffer of the above specified type.
  bytes value = 2;
}

Instead of switching over the URL, users will need to switch over the prefix bytes; the prefix bytes will be computed by via the name as usual in amino:

go-amino/codec.go

Lines 747 to 761 in dc14acf

	func nameToDisfix(name string) (db DisambBytes, pb PrefixBytes) {
	hasher := sha256.New()
	hasher.Write([]byte(name))
	bz := hasher.Sum(nil)
	for bz[0] == 0x00 {
	bz = bz[1:]
	}
	copy(db[:], bz[0:3])
	bz = bz[3:]
	for bz[0] == 0x00 {
	bz = bz[1:]
	}
	copy(pb[:], bz[0:4])
	return
	}

We can provide minimalistic helpers for other languages that deal with these cases.

[liamsi]

Note: @mossid also suggested that the message could also look like this (to make sure the prefix bytes are indeed just 4 bytes).

message BytePrefixedAny {
  sfixed32 prefix = 1; // the amino prefix bytes 
  sfixed64 disfix = 2; // Disamb+Prefix

 // Must be a valid serialized protocol buffer of the above specified type.
  bytes value = 3;
}

Joon is thinking of ways to further optimize this and will post his thoughts later.

[mossid]

Found out that the fixed32 and fixed64 are efficient than varint only if the size is bigger than 3bytes 4bit and 7bytes, respectively, which is not for the prefix/disfix case, as each takes 3 bytes and 7 bytes. Using varint will be more efficient.

message BytePrefixedAny {
  oneof prefix {
    uint32 prefix = 1;
    uint64 disfix = 2;
  }
  bytes value = 3; 
}

The encoder will:

• If a value is not registered, it is simply used as a message, not using BytePrefixedAny at all.
• If a value is registered and not colliding with any other, prefix is filled with 3-byte prefix bytes.
• If a value is registered and colliding with any other, disfix is filled with 7-byte disfix bytes.

The decoder will:

• If a value is not BytePrefixedAny, just decode it.
• If a value is BytePrefixAny and disfix is not empty, slice it and decode it depending on the prefix bytes and disamb bytes.
• If a value is BytePrefixAny and disfix is empty, decode it depending on the prefix bytes.

[liamsi]

I still vouch for the simplest form here from #267 (comment)

message BytePrefixedAny {
  bytes amino_prefix = 1; // the amino prefix bytes (default will be 4 bytes but this is not size limited and could also be with disambiguation bytes)

  // Must be a valid serialized protocol buffer of the above specified type.
  bytes value = 2;
}

This won't waste any bytes either and this is similar to the current simple prefixing.

[jaekwon]

This won't waste any bytes either and this is similar to the current simple prefixing.

It does though... there is an extra key-length (since amino_prefix and value are now two separate arrays), and the BytePrefixedAny itself is also length-prefixed, so there are 2 extra length prefix bytes, as well as the overhead of the top level BytePrefixedAny length prefixing.

I have an idea on how to extend Amino so that we can use OneOf as well as support the existing prefix bytes. I think there is real merit to the existing design, and that it should be supported, as well as the ability to compress further via OneOf.

[liamsi]

That's absolutely right. What I meant was that it does not waste more bytes than necessary, e.g. compared to the separate encoding of pre- and disfix, like described here: #267 (comment), or like using a string based URL scheme (like in proto.Any).

I have an idea on how to extend Amino so that we can use OneOf as well as support the existing prefix bytes.

Awesome! I would like to know more. Can you provide a simple protobuf message to explain that OneOf idea?

[aaronc]

Is something along these lines still going to happen? Has a decision on the best approach been made? I remember hearing several months ago that full proto3 compatibility was just around the corner, seems like it's still a WIP

[jackzampolin]

@aaronc We are still working to integrate it through the stack. We have also recently resourced this work again and we should see some movement here.

[ethanfrey]

If I understood the original intention, it was to have byte compatibility and the ability to (dynamically) export protobuf messages that correspond to amino structs, so it is easy to build client in multiple languages. Amino works great as long as all code using the data is in go. And porting amino to multiple languages seems to be a slow process... but maybe finally coming to javascript via jordan's work.

It would be great to hear about the specific goal and design of the approach. And if there is someone resourced to work on it, maybe they can chime in.

[aaronc]

@ethanfrey the latest work I could find on this is this PR: #276.

I have a bunch of thoughts on the current amino design and what is proposed in the above PR that I intend to comment on soon.

Also, I have heard that @jordansexton has made progress on exporting amino types into typescript or at least has the typescript implementation working pretty well. Maybe he can comment.

[tac0turtle]

the current progress with related to this issue is:

in the Tendermint codebase bez is aiming to solve this issue: tendermint/tendermint#4208, then we start back up again with testing throughout the stack and writing more tests soon after this we hope to cut all the necessary releases to get the changes into the SDK.

If you have design recommendations, please post them here or in the PR soonish so we can address them and hopefully discuss them in detail if they vary to the current design.

We started a migration doc for amino for the coming months, I hope to post that in this repo in the coming weeks.

[jordaaash]

https://github.com/cosmos/amino-js seems to be working decently (based on user reports) for Hub 2 / gaia 1.x. The Go code it contains (for compiling with gopherJS) was manually stripped from the SDK and Tendermint as a proof of concept. The TypeScript types it contains were derived from these, but are fairly incomplete (only some of the interfaces have fields, not much is documented).

I'm currently working on amino-js compatibility for Hub 3 / gaia 2, which involves generating complete Go code and TypeScript types from the SDK and Tendermint. Once this is done, I will backport it and generate for previous versions of the SDK.

The changes to Amino to become Proto3 compatible should not affect the public API of amino-js. Eventually, once we have .proto files for the registered types, amino-js will presumably become a wrapper around generated Proto3 JS code, and gopherJS won't be used anymore.

[aaronc]

If you have design recommendations, please post them here or in the PR soonish so we can address them and hopefully discuss them in detail if they vary to the current design.

I have been writing some quite lengthy thoughts. We are just wrapping up a team retreat here but I see this conversation as quite important and definitely intend to post something this week.

I'm currently working on amino-js compatibility for Hub 3 / gaia 2, which involves generating complete Go code and TypeScript types from the SDK and Tendermint. Once this is done, I will backport it and generate for previous versions of the SDK.

Could you possibly point to where you're working on this export code @jordansexton ?

[aaronc]

Apologies for what turned out to be a very long post. I first want to say that I understand a lot of people have invested a lot of time in this project. I've met most of you in person and appreciate all of you, and I'm trying to approach this discussion from the standpoint of trying to enable a healthy decentralized network of interoperable protocols. The current design of amino, unfortunately, seems to be a big roadblock in the ecosystem. I see some of this discussion as a step in the right direction, but it's moving slowly and I'm not sure the things that need to get addressed are going to get addressed. I feel the need to speak up about it so that Regen Network and the other projects in the Cosmos ecosystem can have a solid foundational encoding layer that they can evolve upon.

---

I first want to address this 4 vs 7 prefix bytes issue. The current implementation uses this and RegisteredAny in protocolbuffers/protobuf#276 uses the same design. I find this design problematic. It breaks schema evolution which means it can basically break a whole blockchain in an upgrade.

Say we have version 1 of a blockchain where none of the types need the extra 3 disamb bytes. We can add new types and as long as we don't do anything crazy like reordering fields in a struct (which is its own issue I'll address below), we can evolve our schema and add new types. Later versions of the blockchain will still be able to read the state stored by version 1 until we register enough types such that disamb bytes are now needed for some types. At this point, the new version of the blockchain will no longer be able to unambiguously read state from the old version that in the new version needs disamb bytes. The old version was fine with 4 bytes and stored those structs as such. Now the new version demands 7 bytes and fails to read the old structs (https://github.com/tendermint/go-amino/blob/master/codec.go#L407).

This tradeoff is unacceptable. There is no infrastructure that I'm aware of that would alert anyone in testing as to whether the amino codec is going to switch from 4 to 7 bytes. None of this would be detected in any testing unless there was extensive testing of an upgrade from an earlier blockchain state that happened to come across this case. Likely this would show up later in production where all of the sudden some state is unreadable.

I would like everyone to take a moment and consider what is necessary for a healthy network of interoperable, decentralized blockchains. I see a lot of discussion here about trying to optimize message size. Is it worth it to save 3 bytes some of the time if this means that protocols can break in arbitrary ways with no warning?

There are a lot of other things besides message size that are important for a healthy decentralized network. I urge everyone to please put aside personal investments in particular approaches for a moment. We are trying to build the future of the internet here.
Message size is of course a concern, but there are other things like schema evolution and interoperability that are very important... Unfortunately I see them not being addressed in this ecosystem. For instance, as I've pointed out to some of you before, there are places in the Tendermint commit history where the block format gets broken just because someone reordered fields in a struct (I'm not linking to commits so as to not unduly direct blame to any individuals).

Because there is no textual representation of a schema like a .proto file that can be checked, backwards compatibility seems really hard to ensure. Maybe we want to "move quickly and break things" for a bit, but I really think backwards compatibility and schema evolution need to be first order concerns.

Here are some places where breaking backwards compatibility can cause issues in an IBC world:

• new versions of a blockchain can no longer read an old blockchain state - basically corrupted state
• old clients of a blockchain can no longer interact with a new version
• IBC peers can no longer communicate with each other after an upgrade
• existing WASM smart contracts can no longer interact with their host chain

The last one regarding smart contracts seems almost impossible to fix without more discipline upstream and could be super problematic.

---

Coming back to this issue, I see this as being a step in the right direction. Making amino protobuf compatible will make client side development possible on many more platforms, and having a .proto file that can be extracted will make schema evolution possible so that breaking changes can be prevented with prototool break check.

Potential Solutions

Just use proto.Any with the full type name

I have spent some time thinking about the tradeoffs of different solutions and I think the initial proposal may be the best way to deal with cases where adhoc polymorphism is really needed. Again, I encourage everyone to please consider all the pros and cons and not just message size. Yes this results in more message bytes, but for one maybe this is not even an issue given we can use rocksdb LZ4 dictionary compression in the store.

Looking a bit more into the initial motiviations for amino's interfaces, I see some frustration with one-of's. I did a "Find Usages" on RegisterInterface in the tendermint and cosmos-sdk code-bases and examined the implementors of all those interfaces, and I really only found three cases - gov.Content, PubKey, sdk.Msg itself - that I would call legitimate uses of interfaces as opposed to one-ofs. All the other interfaces seem to define all their concrete types in the same RegisterCodec call.

Personal preferences aside, I think that in every other case, an interface could be equally if not better specified with a oneof. The one-of solution in these cases would result in fewer message bytes than either proto.Any or the current amino prefix solution (usually 1 byte). And although some may find them ugly, oneof's are actually quite nice in that they clearly specify all the expected concrete types for client users. With either the amino solution or the proto.Any solution client users need some extra information to know which concrete types implement an interface.

So again, I feel like this may be another case of pre-mature optimization. We want to support interfaces, but that adds a lot of complexity... and there are actually just a few use cases. PubKey is actually more secure as a oneof. sdk.Msg could also be made into a oneof on a per chain basis, and proto.Any could be used anywhere it's needed more dynamically. So if it were just gov.Content, gov proposals are so infrequent relative to other transactions that I think proto.Any would add so little overhead that it's not worth worrying about the extra bytes.

I'm not arguing that there aren't or won't be other cases of ad hoc polymorphism (I'm finding some in the key management work that we're doing). But if we add complexity at the protocol level to handle these cases and it's an experimental approach (like 4 or 7 bytes based on arbitrary conditions), there's going to be a cost and we need to think about who's going to pay that cost.

By the way, there are even ways to extract the gov.Content case into a oneof and I could get into it in another post. It may be clunkier than interfaces, but there are other benefits... Either way, I think it's worth considering that maybe the most prudent approach is to not prematurely optimize, and just use proto.Any where there is a real ad hoc polymorphism case, and for the majority of other cases, just embrace `oneof, even though it's maybe not as pretty.

Figure out a way to extract a oneof to support interfaces

There are many ways I can think of to do this:

• have prefixes at both the module level and type-level that define the oneof field number
• auto-generate one-of prefixes in InitChain and store them in state so that they're always the same for any chain
• create a cross-chain schema registry of oneof prefixes

These are all interesting ideas, but I think they all suffer from what was mentioned before - namely that different chains will have different .proto files for a lot of the same modules. I would like to see an ecosystem with reusable client side modules corresponding to on-chain modules and having different message definitions for the same module on different chains will be problematic without some special infrastructure to support this. So in general, I see this approach as another premature optimization over proto.Any.

Cap-n Proto

I'm a bit hesitant to add even more complexity here by mentioning it, but I think it's worth saying that Cap-n Proto addresses many of the design concerns of amino (except developer ergonomics). It is one of the few formats I found that explicitly supports a canonical encoding (the other two being ASN.1 and RDF). It has support for generics which I think would address the ad hoc polymorphism use cases more cleanly than interfaces, in that it makes interface implementations explicit for clients and allows for clean reusable modules. I know there is a developer ergonomics motivation for amino's support for interfaces and cap-n proto doesn't fulfill that, but I would argue that this comes at too high a cost in general. Anyway, I'm not actually arguing we use cap'n proto, just pointing out it exists and if I were personally to design a system from scratch today, it's likely what I would choose.

Regarding canonicalization, I think there has been some concern that protobuf doesn't support this. It is true that it can't support a canonical form in a general sense. However, I would argue for a blockchain protocol, that a textual json format for canonicalizing signed message (like the cosmos-sdk does) is actually a pretty correct approach. It ensures that a binary message has the intended semantics which is pretty hard to do otherwise. The main thing that's needed is for state machines to encode messages in state deterministically, and I think an off-the-shelf protobuf implementation or "proto3" amino could actually do that quite well

Use BytePrefixedAny with a fixed 7-byte prefix

I hope the nightmare scenario I laid out above discourages the continuation of the current 4 vs 7 prefix, but I could see an argument for using a fixed 7 or 8-byte hash prefix as opposed to proto.Any.

I guess this could work, but I actually want to encourage this community to not prematurely optimize and just use proto.Any. I feel there is a pattern of trying to optimize for this one special case of ad hoc polymorphism through go interfaces which is actually having quite a high collateral cost in other ways.

As I've said above: in most cases a regular oneof is more efficient than a 4 or 7 byte prefix (usually just 1 byte), the real cases for ad hoc polymorphism are actually quite rare, and our database supports dictionary compression.

Using a BytePrefixedAny again pushes complexity onto clients. Maybe it's not too high of a cost, but it might not be insignificant either.... it may require clients to have a whole special type registration infrastructure that mostly duplicates proto.Any does.

Anyway, maybe I could live with this - it might postpone some refactoring. But, my personal opinion is that the straight proto.Any approach with an embrace of oneof is better. If that still seems like too high a cost, maybe a more holistic solution like cap'n proto is worth a look.

---

Anyway... I'll stop there...

Again, I understand people have spent lots of time on this design. I'm trying to share what I think is needed to support a healthy decentralized network, and I hope you can all take it in that way with an open mind... I appreciate all your hard work, the community, all your support of us, and hope we can move this discussion forward to something that really supports a healthy, evolving ecosystem of chains, dapps, and meaningful projects that transform the world...

[liamsi]

I first want to address this 4 vs 7 prefix bytes issue. The current implementation uses this and RegisteredAny in protocolbuffers/protobuf#276 uses the same design. I find this design problematic.

The design we ended up with in protocolbuffers/protobuf#276 was mainly because it was an explicit requirement to keep exactly the same public API go-amino is currently exposing together with it the 4 bytes prefix (the 7 bytes version is never used anyways as far as I know). As far as I remember this was mainly due to not wanting to change all the places where amino currently is used (and at the same time wanting full protobuf compatibility). Oh, and I think keeping the messages as short as possible was also an explicit requirement... I currently don't work on amino anymore but wanted to give this as some context. I agree with you TBH. I'm also in favour of just using proto.Any (!) where necessary and oneof everywhere else. How cool would it be if we just used protobuf ;-) Cap-n Proto also looks super cool but I'd still vote for vanilla protobuf if possible.

Thanks for the well worded and thoughtful write-up! ❤️

[jaekwon]

Just wanted to raise awareness of proposal protocolbuffers/protobuf#302 (see just above this), still championing that until someone changes my mind about the justifications there.