🤖 Protocol messages

Scope and status

This chapter lists the messages peers exchange in the Fungi protocol suite. For each message it says who sends it, to whom, in which setting, what it carries, and what the channel carrying it must provide.

It is a draft. Wire encodings, field sizes and signature profiles are not specified yet. Sizes below are orders of magnitude. Each section ends with its open questions.

The messages fall into these groups:

Channel requirements

Channels are described by their properties, not by a transport. Choosing a transport that has these properties belongs to another layer.

Delivery guarantees, timing and metadata hiding are tags: properties declared about a channel.

Metadata hiding is always with respect to the initiator: the sender, or the side that connects on a stream. The responder is always identified, by its peer ID or its address.

An unlinkable channel used for one message at a time yields unlinkable messages, with caveats. For example, an implementation that reuses circuits can leak timing metadata.

Every message type states explicitly which channels are appropriate for it. Two are specified so far:

Open questions:

• What do gossip, set and public gossip messages require of their channels?
• What do transaction construction messages require in the honest setting?

Peer introduction

Honest and semi-honest settings only.

A user adds a peer ID out of band, with one of four trust levels:

Open questions:

• Should there be an introducer role, for self, trusted and semi-trusted peers, that may add peers at or below its own trust level?

Gossip

Gossip always happens within a namespace, also called a topic.

Some namespaces are ephemeral. Their name is derived from a shared secret using a tagged hash. Some are well known, such as the version 1 public order book. Co-spend proposals are namespaced by a Bitcoin block hash. If an object’s ID is derived from a namespace that includes a block hash, the ID can be short.

Minimal gossip

These three messages suffice in the honest setting:

🤖 Small messages are pushed eagerly to neighbors. A block is pushed as just its header, expecting the receiver to already know its Merkle tree.

🤖 After an anonymous submission enters the broadcast domain, peers disseminate it by gossip or set reconciliation. Anonymous submission does not replace dissemination.

Unsolicited push

The semi-honest and Byzantine settings add one message:

A peer receiving a new object by unsolicited push forwards it by push to one randomly selected peer, and announces it to its other peers.

Open questions:

• How to scope ephemeral namespaces: by shard, by time, or by number of messages.

Sets

Every message carries a state commitment. It includes the Merkle roots of the sender’s mutable sets, its height and its set sizes.

Immutable sets

An immutable set is referenced by its Merkle root. Sets are sparse Merkle trees, in the style of Libra’s. A block commits to two immutable sets: its parents and its messages.

Mutable sets

A mutable set is tracked as a sequence of Merkle roots. A peer has these:

Fetching an ever-growing collection of sets is a resource exhaustion risk. Blocks are needed for progress, and are rate limited by cordiality. A dishonest majority can still flood.

Set listing

Leaves here are hashes, not preimages. Listing all leaves lets the receiver recompute the root.

Set reconciliation

Two methods are candidates:

• Range based. List to a given depth, with clamping.
• RIBLT. A stream of rateless coded symbols for a set.

For mutable sets, randomize the hash and restart the stream on each new item. Reply to a range based request with the children, then stream RIBLT data.

The RIBLT cells need a multiset hash. Elliptic curve multiset hash (ECMH) candidates are:

• GLS254;
• a GLS254 analogue with m = 61 or m = 67, where complete formulae should hold;
• the curve25519 ECMH in fastcrypto;
• secp256k1.

Open questions:

• Can only the latest root of each mutable set be queried?
• Should listing to a given depth return the intermediate nodes?
• Should a range based reply jump ahead, up to some listing size, instead of returning only the children? How does range based reconciliation apply to mutable sets?
• Is range based reconciliation only for immutable sets, or throttled for mutable ones?
• Should immutable sets use a hybrid, interspersing RIBLT with range based reconciliation?
• Can reconciliation data be carried in padding and in announce messages?

Public gossip

Public gossip uses a well known namespace. These objects form the order book for coalition formation.

Willingness to be a validator is one of: demands it, opts in at the aggregator’s discretion, or declines.

Negotiation

Byzantine setting. These messages go over the channel named in the recipient’s listen advertisement, or are gossiped as partial proposals where peers opt in.

In the semi-honest setting the ring signatures can be skipped. Owners then negotiate MuSig2 directly.

Session initialization

Transaction construction

These messages are gossiped to the session’s topic. Transaction contributions project into unordered PSBT state and combine according to concurrent PSBT construction. In the Byzantine setting, the wire format consists of specified protocol messages, rather than arbitrary PSBTs. Honest and semi-honest construction can tolerate PSBT extensions; extensions in the Byzantine setting must be specified as protocol extensions.

In the semi-honest and Byzantine settings they need a send channel with unlinkable messages, reliable delivery and broadcast addressing. Outputs in particular must always be message-unlinkable and hide metadata.

Initialize

Sets up the session parameters. The sort seed is the transcript hash: the Merkle set commitment of the accepted construction messages at the agreed state before signing, including the applicable proofs. Later input signatures and acknowledgement-only blocks do not change this seed. Concurrent PSBT construction allows this by setting PSBT_GLOBAL_SORT_DETERMINISTIC and leaving PSBT_GLOBAL_SORT_SEED unset, so each replica supplies the seed when it orders the transaction.

Add input

An input map with its prevout data. In the Byzantine setting, initial inputs are named by the coalition formation proposal, so only auxiliary inputs carry prevout data. The message also carries:

• an ownership proof committing to an online key;
• a signature by that online key on the message, committing to the session ID or gossip topic.

Add output

An output contribution, which projects into a PSBT output map. Its unique ID becomes PSBT_OUT_UNIQUE_ID, so adding it twice is idempotent, while two equal outputs added separately stay distinct.

🤖 In the optimistic phases, each admitted output has an amount of at least 1 sat, as required by the construction rules.

Add fee contribution

A 16 byte unique ID and an amount, which project into a PSBT_GLOBAL_EXPLICIT_FEE_CONTRIBUTION entry. Fee contributions let peers account for fees exactly.

🤖 In the optimistic phases, each admitted fee contribution accounts for at least 1 sat. The overflow signal has the separate meaning described below.

Issue and redeem

Byzantine setting only. These messages carry validity proofs. Issuance is from initial inputs or from auxiliary inputs. Their contents depend on the validity proof construction, which is specified separately.

Sign

The signer first converts the PSBT to an ordered one, then signs with SIGHASH_ALL. A signature is tens of bytes. In the Byzantine setting the message can be larger, bounded by the size of the input’s ownership proof.

Signers differ in how they can be used:

Interactive payments

Messages to a designated peer, the counterparty of a payment:

The concurrent PSBT specification defines what is confirmed and in what order, including how cycles are broken by net receivers. It is concerned with state only. These messages carry that state between the counterparties.

These messages need send and receive channels with reliable delivery and peer addressing. They may be linkable or unlinkable. The payer must authenticate the payee. Whether the payee authenticates the payer depends on the payment; game theory suggests it shouldn’t.

Interactive payments belong to the honest or semi-honest threat model, not the Byzantine one. They can still take place within a broader Byzantine session.

Blocks

Blocks provide consistency and synchronization, in the style of a blocklace. They are used in the semi-honest and Byzantine settings.

A block contains:

• the Merkle set commitment of its parent blocks;
• the Merkle set commitment of the gossiped transaction construction messages it includes;
• its parent block by the same node;
• the nonce point R its successor will be signed with.

A block is signed with the nonce point committed in its own-node parent.

Phase change signals

Blocks also signal phase changes:

Open questions:

• In the semi-honest setting, can additional validators just join? If not, how is initialization synchronized?