compact encoding for hare preround message

[dshulyak]

hare preround message includes every proposal that is eligible for rewards. it references it by specifying first 20 bytes of blake3 hash of the full proposal. with 50 proposals per layer the message is around 1KB, not including vrf and regular signature. with 500 proposals per layer it grows to 10KB per preround message. number of preround messages are bounded to the size of hare committee, right now we are running it with 400 participants, but aim to increase it to 800.

with 10KB per preround message every peer has to download 4MB of unique data within 12s, in practice it downloads some duplicates because of the redundancy on gossip layer. the other part of the problem is that it scales with number of connections that node maintains. if node has 1000 connections, it can expect to be requested 4GB of data within 12s. eventually, if not now, this will be unsustainable to keep such number of connections.

compact encoding protocol

the reason why we keep 20 bytes is to prevent collisions, as otherwise votes are ambiguous and cannot be counted properly. moreover adversary can create collisions intentionally if identifier will be kept short to 2 or 4 bytes.

the proposal is to introduce compact encoding that is not open to dos attack, maintain low rate of accidental collisions, and in case of collisions provide a safe fallback. it can reduce traffic either x5 or x10, depending on the option that we choose.

protocol for encoder:

• construct preround message with a collection of full proposal identifiers. proposals should be sorted in lexicographic order
• sign message with full proposal identifier
• replace each proposal identifier with an output from short_hash(vrf, proposal_identifier)

short_hash is a cheap hashing function, such as siphash or halfsiphash https://github.com/veorq/SipHash/blob/master/halfsiphash.c. we may decide how much we want to truncate output.

protocol for decoder:

• receive a message, verify a vrf
• for all proposals that you have locally compute short_hash(vrf, proposal_identifer)
• if received message votes several times on the same proposal
• validate signature on reconstruct message

we need to handle two edge cases due to possible collisions:

• message includes multiple short identical id. in this case we decode them in lexicographic order. so for example if we received short ids [4,4], and we have locally proposals 0xa, and 0xb, we decode 0xa and then 0xb.
• message includes single id, but locally we have collisions. in such case we have to verify signatures for different proposal and find if one of the matches.

[dshulyak]

i introduced label https://github.com/spacemeshos/go-spacemesh/labels/draft to signal that the discussion about this only ready to be implemented yet.

[acud]

@dshulyak I have several questions arising from reading the related materials:

• my understanding is that overriding the proposal IDs will happen only in the preround
• right now the type on Value is an array of 20 byte blake3 hashes
• if we switch to another hashing algo it means we need to change the type on Value
• if we want to only change the type for the preround message, we should either:
• • introduce a new field on Value, something like CompactProposals []types.CompactProposalID. This field will only be used in the preround
• • use a different message exchange for the preround
• • change the type of Proposals to allow dynamic sizing of the data, i.e. Proposals [][]byte
• I would prefer to use the first option, or the second
• any objections to using this as a siphash implementation?
• what should we use for the key for the sip hash?
• since by using 1 or 2 byte sections of the hash, is there preference for big- or little-endian encoding before slicing the relevant bits out?
• for all proposals that you have locally -> where do these come from? protocol.initial?

[dshulyak]

i think new type []CompactID is superior, each opaque []byte type will have to be prefixed with compact integer, one more byte or 50% increase per id. one more option is to use bit packing and then do variable length encoding for proposals if we know that there are collisions.

---

regarding whole siphash thing, in original idea i wanted it to be keyed by vrf (truncated to whatever is the size of the key). however there is also this "extension" that needs to be implemented.

how about even simpler approach. preround message is encoded with 2/4 bytes, simply 2/4 first bytes of the proposal hash without any additional randomness. message is signed using full proposal hash, as discussed previously, so that signature verification is always executed on correct message.but in case of ambiguity, where we cannot deterministically decode the message for signature verification, we will do one more round trip and download message with full ids from the peer that sent message with small ids. so if adversary pulls out an attack, we potentially will have to download 10%-25% more data, and we also know how to disconnect a peer that intentionally sends ambiguous messages

and in this case there seems to be no difference between truncating original blake3 hash to 2 or 4 bytes or using siphash. as ambiguous proposals will always have to be requested from the peer that sent message with them.

with this extension the decoding protocol is like this:

• receive a message, verify eligibility with vrf
• decode proposals according to the lexicographic order of full proposal, for example full proposals 0xaabbcc and 0xaabbdd, compact ids for both of them are 0xaabb
• we can try to decode the message and check signature if both are included
• if signature fails or not both are included we have to do a roundtrip and ask a peer for full hashes of the proposal that it upvoted that start with 0xaabb in layer X. in this last case peer can reply only with hash, and not the full proposal

one more thing is that hare gossip handler right is in synchronous mode, but it will have to be switched into a mode that spawns goroutine per request in gossip libp2p.

---

there was a question about breaking protocol changes and upgrade path, it should be as follows:

• introduce new protocol version for gossip, i would suggest to keep it as hare31. new version will have an updated type
• keep two versions in the codebase until the transition happens
• transition is orchestrated by configuring enabled/disabled layer. for example hare3 stop at 10000, hare31 starts at 10001
• after transition it is ok to remove previous code

[mathcrypto]

After discussion, we arrived to the following conclusion:

• Proposal IDs are truncated into smaller compact IDs before being sent over the gossip network.
• Each proposal ID is initially truncated to 2 bytes.
• The sender constructs a message with truncated proposal IDs and includes auxiliary data for resolving any detected collisions.
• Auxiliary data includes additional bytes to extend truncated IDs when collisions are detected.
• The sender then signs the pre-round message with the full IDs and includes the truncated IDs and auxiliary data.

Handling Collisions:

When collisions (same truncated ID for different proposals) are detected:

• First check: Sender extends the truncated ID to a longer size (6 bytes from the Blake3 hash) to reduce collisions.
• Final check: If collisions still exist, include the full proposal ID (32 bytes).

Verification Process:

• The (honest) receiver checks the digital signature of the message using the sender's public key.
• The signature should validate against the full proposal IDs (or the reconstructed full IDs from the truncated and auxiliary data).
• The receiver uses the truncated IDs and any auxiliary data provided by the sender to reconstruct the full proposal IDs.
• If verification fails (can't reconstruct the message or verify signature), the message is rejected and not rebroadcast.
• Otherwise, receiver forwards the message.
• Receiver should not engage in extensive additional communication to resolve IDs (non-interactive process).