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.