Faulty inclusion requirement

[victorshoup]

The following requirement is stated:

If an honest party commits block $R$, let $e = \mathrm{epoch}(T_R)$. Then for any sequence number $s$, if either $s=0$ or a bundle with epoch $e$ and sequence number $s-1$ is included in $R$ or an earlier round result committed by the same member, and if at least $F+1$ honest members received a bundle with epoch $e$ and sequence number $s$ before $T_R-d$ (according to each such member's local clock), then some bundle with epoch $e$ and sequence number $s$ is included in $B_R$.

I don't think the reference impl satisfies this requirement.

For simplicity, assume d=0 and F=1, so there 4 parties, one of which may be corrupt. For this argument, we do not need any corrupt parties. Suppose that parties 1,2,3,4 submit their inputs to round R at times 1,2,3,4, respectively. Suppose that inputs from parties 2,3,4 are included in the inclusion list. Then $T_R = 3$. Now, we assume that two parties received a priority bundle b at time 2.5. The conclusion should be that b must be included in $B_R$. However, if these two parties are 1,2, then they will have submitted their inputs before receiving b.

I'm not sure how critical this property really is. If we do want something like this property to hold, then we would need to assume that the bundle was received by all honest parties before time $T_R$, rather than $F+1$ honest parties.

[victorshoup]

Adding to my list of doubts, I'm also not sure if things fall apart even more when one takes into account the logic of taking the max of the previous round and the median timestamp

[victorshoup]

OK, here is another counter-example to the above requirement, in this case when we require that all honest members receive before $T_P$, but we incorporate the "max" logic.

Suppose have parties 1, 2, 3, 4. They start one round at times 0, 2, 4, 6, and say parties 2, 3, 4 get included, so we compute the median timestamp 4 = median(2, 4, 6). They start the next round at times 1, 3, 5, 7. Suppose parties 1, 2, 3 get included. We compute median(1,3,5) = 3, and the consensus timestamp is max(3,4) = 4.

Now suppose that party 3 is corrupt. So the only included honest parties are 1, 2, with start times of 1, 3. A bundle b may be received just before time 4 by all honest parties, but since the only included honest parties started the round at times 1, 3, and so b will not be included in the round.