On Protocol Buffers and determinism

[jordipainan]

Define a set of rules for deterministic Protobuf serialisation:

From the official Google Protobuf docs

By default, repeated invocations of serialization methods on the same protocol buffer message instance may not return the same byte output; i.e. the default serialization is not deterministic.

From the release note of Protobuf 3.0.0

Added a deterministic serialization API (currently available in C++). The deterministic serialization guarantees that given a binary, equal messages will be serialized to the same bytes. This allows applications like MapReduce to group equal messages based on the serialized bytes. The deterministic serialization is, however, NOT canonical across languages; it is also unstable across different builds with schema changes due to unknown fields. Users who need canonical serialization, e.g. persistent storage in a canonical form, fingerprinting, etc, should define their own canonicalization specification and implement the serializer using reflection APIs rather than relying on this API.

From the opencontainers.com Google group

In any case, the upshot of this is that while a particular implementation of the proto library may deterministically produce the same serialized proto every time when given a particular proto message, there’s no guarantee that two different proto libraries will serialize it in the same way, nor are there any guarantees that any particular proto library serializer will be stable over time.

The following checks may fail for a protocol buffer message instance

foo.SerializeAsString() == foo.SerializeAsString()

Hash(foo.SerializeAsString()) == Hash(foo.SerializeAsString())

CRC(foo.SerializeAsString()) == CRC(foo.SerializeAsString())

FingerPrint(foo.SerializeAsString()) == FingerPrint(foo.SerializeAsString())

The problem is not only cross-language, but it may affect a single library too. There is no guarantee that the same library will consistently implement a deterministic encoding over time.

The indeterminism is caused by:

• The absence of guarantees on how known or unknown fields should be ordered upon writing them
• Map serialisation relies on iteration, and there is no ordering guarantee while iterating over map items

Examples where determinism is not guaranteed:

• Encoding fields in different order than the tag number order.

• Encoding packed fields as unpacked.

• Encoding integers as longer varint byte sequences than needed.

• Encoding same (non-repeated) field multiple times.

Proposed solutions by other projects

Proposed solution by Cosmos

Proposed solution Regen Network

Protocol labs

[p4u]

IMO the most realistic and friction-less approach to solve this (possible) issue is by following a set of rules for defining the protobuf models similar to the Cosmo's one https://docs.cosmos.network/master/architecture/adr-027-deterministic-protobuf-serialization.html

Right now the most affected Protobud spec (which needs to be compatible across different programing language implementations) is this https://github.com/vocdoni/dvote-protobuf/blob/master/src/common/vote.proto

So a first step would be to make our own Cosmos-like canonical guide and to apply it in the vote.proto model.

[jordipainan]

cc: @mvdan Discussion regarding proto & determinism on serialisation is centralized here.

[p4u]

This issue was handled by adding a new extra protobuf bytes field that contains the origin Marshaled bytes. The signature is not included on this protobuf message so the receiver can verify it directly using the original payload (before Unmarshal).

The new protobuf message is named "SignedTX": https://github.com/vocdoni/dvote-protobuf/blob/master/src/vochain/vochain.proto#L34