Set Reconciliation

Lei Yang

MegaETH; work done while at MIT

Issue with Gossipping: Redundant Messages

Alice

Bob

Charlie

Dave

0xabcd1234

0xabcd1234

0xabcd1234

0xabcd1234

same item received twice

Announcing Hashes Is Not Efficient Either

Alice

Bob

Charlie

Dave

• Have you seen 0xbeef?
• No
• 0xabde1234

• Have you seen 0xbeef?
• Yes

• Have you seen 0xbeef?
• Yes

Problem: Send / Receive “New” Information Only

What’s optimality?

• Alice and Bob receives stuff exclusive to each other and nothing more.

Problem: figuring out what to send

• This is called the “set reconciliation problem”.
• Rough definition: let one of Alice and Bob learn A U B.

Alice

Bob

A

B

What’s known to be possible?

• A brief history
• Alice (or Bob) can learn A U B with exactly |A\B U B\A| communication and quadratic computation [1]
• Alice (or Bob) can learn A U B with ~|A\B U B\A| communication and log-linear computation, but needs to guess/know |A\B U B\A| [2]
• Alice (or Bob) can learn A U B with ~|A\B U B\A| communication and log-linear computation [3]
• References
• [1] Set Reconciliation with Nearly Optimal Community Complexity. Minsky et al. IEEE Trans. Inf. Theory. 2003.
• [2] Invertible Bloom Lookup Tables. Goodrich and Mitzenmacher. IEEE Allerton. 2011.
• [3] Practical Rateless Set Reconciliation. Yang et al. ACM SIGCOMM. 2024.

What’s known to be possible?

• Let d = |A\B U B\A|, the size of the difference between their sets
• Communication: 1.35d
• Computation: O(d log(d))
• Tens of Mbps per CPU core.
• Round trips: 1/2
• One one-way trip for Alice or Bob to learn the union; another one-way trip for the other participant to learn it as well.
• Tl;dr: near optimal complexity; especially useful for short items when signalling (e.g., sending hashes and other protocol messages) may introduce excessive overhead

The Basic Idea

• Imagine that items to be reconciles are integers
• Consider a special case: A and B differ by exactly one item
• A = {343, 556, 789, 134}
• B = {343, 556, 134}
• Alice calculates a = 343 + 556 + 789 + 134 = 1822
• Bob calculates b = 343 + 556 + 134 = 1033
• Alice sends a to Bob
• Bob calculates a - b = 789
• Needs much more care when A and B do not differ by just one item, but the idea stays the same

Set Reconciliation in Signature Aggregation

Alice

(Aggregator)

Bob

Charlie

Dave

a, b, c

a, b, d

c, d, e

a, b

Set Reconciliation in Signature Aggregation

Alice

(Aggregator)

Bob

Charlie

Dave

a, b, c

a, b, d

c, d, e

a, b, c

1

Set Reconciliation in Signature Aggregation

Alice

(Aggregator)

Bob

Charlie

Dave

a, b, c

a, b, d

c, d, e

a, b, c, d

1

2

Set Reconciliation in Signature Aggregation

Alice

(Aggregator)

Bob

Charlie

Dave

a, b, c

a, b, d

c, d, e

a, b, c, d, e

1

2

3

Set Reconciliation in Bitcoin

• Erlay: Efficient Transaction Relay for Bitcoin. Naumenko et al. ACM CCS.
• Graphene: Efficient Interactive Set Reconciliation Applied to Blockchain Propagation. Ozisik et al. ACM SIGCOMM.
• Focuses on transaction propagation which shares a lot of features with signature propagation.
• Idea: reconcile hashes of transactions in the pool instead of flooding them.
• Erlay is implemented in Bitcoin Core and progressing towards deployment.

Next Steps

• Implementation is more or less ready
• leiy.net/riblt in golang, implementations in other languages in the readme
• Simulations
• Metrics
• Latency for all signatures to propagate throughout the network
• Communication overhead: total bytes received / unique signature bytes received
• Baseline: gossipsub; what else?
• Schedule of reconciliation?
• Alice reconciles with each peer concurrently non-stop?
• Alice reconciles with one peer at a time in round robin?
• Alice and peers form a ring and reconcile with neighbors on the ring?
• Off-topic: other applications in the Ethereum ecosystem, such as fixing corrupted databases or synchronizing transaction pools?