Coding for Ethereum block propagation (proposed by Arantxa)

Can you improve the efficiency of this sharding protocol that was proposed for the Ethereum blockchain? Specifically, can you decrease the amount of data that must be sent for coefficients and commitments?

Here is a summary of the importart parts of the protocol.

A “proposer” has a message (an Ethereum block) of size ~100 KB; it wants to send the message in distributed fashion over a network to ~50,000 nodes. To do this:

• The message is split into ten equal-sized “chunks” $v_1, \ldots, v_{10}$, each of which is interpreted as a vector over $\mathbb{F}_p$. (Here $p \approx 2^{256}$, so each chunk is a vector of length ~300.)

The proposer sends messages (“shards” of the block) to some nodes as follows:

• For each node, the proposer chooses ten random “coefficients” in $\mathbb{F}_p$: $b_1, ..., b_{10}$.
• The proposer sends:
  • The linear combination $\sum b_i v_i$
  • The coefficients $b_i$
  • Ten Pedersen commitments to the vectors $v_1, ..., v_{10}$, and
  • A signature on the concatenation of the ten Pedersen commitments.

Note that the full block can be recovered (with very high probability) from any 10 such shards.

Each node waits until it has received some number $k \leq 10$ of shards, $S_1, ..., S_k$ (from the proposer or other nodes). (Maybe $k = 3$.) Then:

• The node chooses $k$ coefficients $c_1, ..., c_k$.
• The node computes the “linear combination of shards” $c_1 S_1 + \cdots + c_k S_k$, and sends it to other nodes. This “linear combination” is a package of:
  • The combined vector $\sum b_i v_i$ – here $b_i = \sum_j c_j b_{i, j}$
  • The combined coefficients $b_1, \ldots, b_{10}$
  • The same ten Pedersen commitments to the vectors $v_1, ..., v_10$, and
  • A signature on the concatenation of the ten Pedersen commitments.

Why this protocol?

Two questions for Arantxa:

Why shard at all, rather then sending the full block?

Why not make the node wait for $k=10$ messages to come in?

Why use random linear combinations, rather than just sending each node some randomly chosen chunk $v_i$? With linear combinations, any node that receives ten random “shards” will be able to recover the full block (with high probability).

Why send commitments to the vectors $v_i$? This is an integrity mechanism: since Pedersen commitments are linear, a node can verify the correctness of any purported linear combination of the $v_i$’s. If a node does not verify correctness, errors will propagate across the network.

Things we want: decrease the communication cost.

1. The coefficients $b_i$ require 10 field elements, or about 320 bytes. Can you decrease this?

2. The commitments to the vectors $v_i$ require 10 Pedersen commitments, or again about 320 bytes. Can you decrease this?