[bisq-network/bisq] Hashes in Bisq are not potentially un-stable (#3391)

Justin Carter notifications at github.com
Fri Oct 11 04:40:45 UTC 2019

This is a summary of the findings from investigating https://github.com/bisq-network/bisq/issues/3367. The new ticket is because the initial description of the issue doesn't match real-world behaviour so here is a summary of the real-world impact.

## Issue

Protobuf serialization is [non-deterministic](https://gist.github.com/kchristidis/39c8b310fd9da43d515c4394c3cd9510). There are many sources for non-determinism with the biggest issue being the order of entries in [maps](https://developers.google.com/protocol-buffers/docs/proto3#maps).

> Wire format ordering and map iteration ordering of map values is undefined, so you cannot rely on your map items being in a particular order.

This is a problem because Bisq currently uses the protobuf serialized bytes as the [basis for hashing](https://github.com/bisq-network/bisq/blob/master/p2p/src/main/java/bisq/network/p2p/storage/P2PDataStorage.java#L842-L844) to uniquely identify payloads.

Serialization being non-deterministic means the produced hashes are not stable and could change over time. Since hashes are used for referencing payloads from other messages (eg in [`RefreshOfferMessage`](https://github.com/bisq-network/bisq/blob/master/common/src/main/proto/pb.proto#L152) or [`DaoStateHash`](https://github.com/bisq-network/bisq/blob/master/common/src/main/proto/pb.proto#L1880)) this means broken hashes could have a detrimental impact on the entire bisq project.

## Real World

Monitoring mainnet data has shown that there are only a very small number of issues that come up which could be a result of unstable hashes. The ones that _did_ show up could also be explained through other behaviour.

The small number of issues implies that hashes in bisq _are in fact_ largely stable contrary to the non-determinism.

This is thanks to an implementation detail in the java protobuf library we are using. Internally the library instantiates `LinkedHashMap`s when [deserialising map fields](https://github.com/protocolbuffers/protobuf/blob/f9d8138376765d229a32635c9209061e4e4aed8c/java/core/src/main/java/com/google/protobuf/MapField.java#L171). `LinkedHashMap` preserves insert order of the entries which means the byte order (and hashes) will be stable after re-serializing.

## Risks

While we seem to be clear for the time being there is no guarantee this will remain so. Implementations in other languages (including the reference implementation in golang) don't use order preserving maps internally and are not be able to reliably reproduce the hashes across nodes.

If the implementation details of the java pb lib change, or other sources of non-determinism come into play Bisq may be completely broken.

## Possible work around

Moving to a deterministic form of hashing is the only long-term mitigation. However this initially appears to be quite difficult in a backwards-compatible way (more investigation required).

One possible work around identified in [this](
https://havoc.io/post/deterministic-protobuf/) article is to change the `map` fields in the proto schema definition to `repeated` fields.

ie going from:
message TempProposalPayload {¬
    Proposal proposal = 1;
    bytes owner_pub_key_encoded = 2;
    map<string, string> extra_data = 3;
message TempProposalPayload {¬
    Proposal proposal = 1;
    bytes owner_pub_key_encoded = 2;
    repeated StringKV extra_data = 3;

message StringKV {
    string key = 1;
    string value = 2;

These 2 schemas are bit compatible on serialization. The second one is guaranteed to preserve order, which would remove the most critical source of non-determinism.

Editing the schemas to implement this work around would involve changing all references from maps to arrays of 2 element tuples. Wether or not this is worth the effort as short-term mitigation also requires more investigation.

You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.bisq.network/pipermail/bisq-github/attachments/20191010/4eecc82e/attachment.html>

More information about the bisq-github mailing list