Optimised proposal commitment scheme

Sharding
1

In this post we present an optimised version of the proposal commitment scheme from this post. When combined with this challenge scheme it addresses the proposer withholding attack.

Construction

During his assigned period p the eligible validator gathers all the proposals p_1, ..., p_n he has received from proposers. The proposals p_i are hashed and the hashes H(p_i) are Merklelised in a Merkle tree with root r where the leaves H(p_i) are ordered lexicographically. The validator signs [p, r] with a signature s to form a commitment C = [p, r, s]. The commitment C is then broadcasted alongside the leaves H(p_i) to the proposers.

A commitment C is valid if:

  1. The period p is valid
  2. The signature s is valid

We now introduce two slashing rules to the VMC as follows:

  1. Improper ordering: If a valid commitment C alongside two leaves H(p_j), H(p_k) matching r are presented to the VMC for which the lexicographic ordering is not respected then the validator is slashed.
  2. Non-membership: If a valid commitment C alongside two leaves H(p_j), H(p_k) matching r are presented to the VMC for which H(p_j), H(p_k) are immediately adjacent in the Merkle tree and H(p_j) < H(\widetilde{p}) < H(p_k) where \widetilde{p} is the proposal submitted to the VMC then the validator is slashed. The “left” and “right” edge cases also need to be handled.

Discussion

The scheme allows proposers to safely disclose their collation body to the validator once they have received a valid commitment C alongside the leaves H(p_i) which match r.

This scheme has been optimised compared to the original scheme because, in the default case, there is no overhead to the VMC. In particular, there is no need for an extra field or extra data in the collation headers. Notice also that the scheme imposes no storage overhead in the VMC.

1 Like
2

It turns out there are two further optimisations:

  1. We don’t need the first “Improper ordering” slashing condition. Instead, proposers ignore commitments C for which the leaves H(p_i) are improperly ordered.
  2. By requiring the left-most leaf in the Merkle tree to be 0x000...0 and the right-most leaf to be 0xFFF...F then we don’t need the “left” and “right” edge cases in the “Non-membership” slashing condition.
3

We may have an optimal construction! :slight_smile: Instead of using an ordered Merkle tree we use an ordered linked list where the validator signs individual links. Credits to @vbuterin for pointing in this new direction.

Construction

The validator builds signatures s_i for [p, H(p_i), H(p_{i+1})] for i = 0, ..., n where:

  • H(p_0) := \texttt{0x0}
  • H(p_{n+1}) := \texttt{0xFFF...F}
  • H(p_i) < H(p_{i+1}) for every i

The commitment C is [p, H(p_1), ..., H(p_n), s_0, ..., s_n] and we have a single slashing condition:

  • Non-membership: If [H(p_i), H(p_{i+1}), s_i] is presented to the VMC such that the signature s_i is valid and H(p_i) < H(\tilde{p}) < H(p_{i+1}) where \tilde{p} is the proposal submitted to the VMC then the validator is slashed.
2 Likes