Side-channel considerations

[cjpatton]

A couple of observations about sharding.

First, the wraparound randomness needs to be sampled from a specific distribution, which is simulated by the following algorithm:

rand_bits = sample_bytes_from_an_rng()
if rand_bits == 0b00:
    rand_field = self.Field(self.Field.MODULUS - 1)
elif rand_bits == 0b01 or rand_bits == 0b10:
    rand_field = self.Field(0)
else:
    rand_field = self.Field(1)

Branch prediction might leak the value of rand_bits. The risk here is that if I know the randomness the client uses and can observe its computation, I might be able to learn which wraparound tests failed.

Second (and probably worse), the encoding finalization step might leak which wraparound tests failed (and which were skipped).

    if is_in_range:
                # If the result of the current wraparound check is
                # in range, and number of passing repetitions hasn't
                # reached `self.NUM_PASS_WR_REPS`, set success bit
                # to be 1, otherwise set it to be 0.
                if num_passed_wr_reps < self.NUM_PASS_WR_REPS:
                    success_bit = self.Field(1)
                    num_passed_wr_reps += 1
                else:
                    success_bit = self.Field(0)
            else:
                # Set the wraparound check result to be zero,
                # and success bit to be zero.
                curr_wr_res = self.Field(0)
                success_bit = self.Field(0)

Implementations will probably want to make these things constant-time, if possible. We should figure out how we might do this and add some guidance to the draft.

[junyechen1996]

I think the z vector is known to both prover and verifiers, but the x vector and bits for wraparound check results are both secret-shared, so verifiers won't learn the dot product, or which wraparound test failed. Quote from the paper in section 4.2: "The verifiers will not learn whether any of the individual repetitions succeeded, but only whether “many” of them succeeded.".

Could you elaborate on "Implementations will probably want to make these things constant-time, if possible"?

[cjpatton]

Could you elaborate on "Implementations will probably want to make these things constant-time, if possible"?

The goal would be to have an algorithm whose runtime doesn't depend on secret state. This is to make side-channel attacks harder.

By the way, there's no reason to worry about this right now, but eventually we'll need to think this through.

I think the z vector is known to both prover and verifiers, but the x vector and bits for wraparound check results are both secret-shared, so verifiers won't learn the dot product, or which wraparound test failed.

It's not the server side computation that is the (potential) issue: it's the client side. Imagine the attacker gets to observe how long it takes the client to run the sharding algorithm; if the runtime depends on secret state, then the attacker can potentially learn that state.

Quote from the paper in section 4.2: "The verifiers will not learn whether any of the individual repetitions succeeded, but only whether “many” of them succeeded.".

This is true only in the absence of side channels, which the paper doesn't account for. By the way this is not to suggest there is a problem with the paper -- typically considering side channels is left to implementation.