Social Choice Around the Block: On the Computational Social Choice of Blockchain

Strictly, this paper has no qualifying anchor. It contains no numbered Theorem, Lemma, Corollary, or Proposition, and proves no named result of the form NP-hard, polynomial-time, FPT, or similar. The claims about Gibbard’s theorem, FLP, and Casper’s \(2/3\)-stake guarantee are cited background or protocol facts, not results proved here. Thus I cannot honestly claim a mirror of “Theorem 3” or use the cited manipulation hardness in [8] as this paper’s anchor.

The strongest positive case is nevertheless in Section 3.2, where the paper explicitly proposes adapting manipulation decision problems to “shares of the agents population” and Byzantine agents. My lead is a continuous version of that challenge.

Consider a proof-of-stake network resolving one fork. The candidates \(A\) are the competing blocks or branches. A type is a complete validator class \(t=(\succ_t,\ell_t,\gamma_t)\), where \(\succ_t\) is the validator’s ranking of the branches, \(\ell_t\in\{H,S,B\}\) says whether it is honest, strategic, or Byzantine, and \(\gamma_t\) records its reporting costs and other behavioural parameters. A society is a rational distribution \(\mu\) over these types, where \(\mu_t\) is the fraction of total stake held by type \(t\). Thus mass means voting power, not merely headcount.

This is plausible in a delegated proof-of-stake regime with many validators or stake units but relatively few combinations of client software, fork preference, stake denomination, behavioural policy, and Byzantine status. A network may have millions of stake-holding units while having only a moderate number \(\tau\) of such types. The scenario is weaker for a small permissioned committee, but strong for a large, pooled, permissionless network. It also matches the paper’s own insistence that Casper’s votes are weighted by stake and that Byzantine shares should be modelled.

Call the problem Continuous Byzantine Stake-Weighted \(R\)-Manipulation\(_\infty\). Fix a voting rule \(R\), a target branch \(a^\star\), the type distribution \(\mu\), and a budget \(K\). For every strategic type \(t\) and reported ranking \(\rho\), choose a nonnegative mass \(x_{t,\rho}\), with \(\sum_\rho x_{t,\rho}=\mu_t\). This is the mass of strategic stake reporting \(\rho\). For every honest receiver type \(h\), Byzantine type \(b\), and ranking \(\rho\), choose \(y_{h,b,\rho}\), with \(\sum_\rho y_{h,b,\rho}=\mu_b\). The dependence on \(h\) represents Byzantine equivocation: the same Byzantine stake may send different votes to different honest validators.

The profile seen by honest type \(h\) has mass

\(P^h_\rho=\sum_{t\in H:\succ_t=\rho}\mu_t+\sum_{t\in S}x_{t,\rho}+\sum_{b\in B}y_{h,b,\rho}\).

The decision question is whether there exist \(x\) and \(y\) such that

\(\sum_{t\in S,\rho}\gamma(t,\rho)x_{t,\rho}\le K\)

and \(R(P^h)=a^\star\) for every honest type \(h\). Requiring the same unique winner in every honest view captures both target finality and safety. The optimization version minimizes the reporting cost. If equivocation is disallowed, impose that \(y_{h,b,\rho}\) is independent of \(h\).

This is a direct continuous analogue of the paper’s proposed computational problem: strategic voting or bribery is performed by transferring stake mass, and the Byzantine condition is a bound on Byzantine stake share rather than a bound on a named set of individuals. It does not continuize the outcome, the lottery, or time; it continuizes the population that participates in voting.

For the actual Casper-style threshold rule on a fixed fork, I would expect this lead problem to be Class A. After fixing tie and finality conventions, target finality and safety are linear inequalities in \(x\) and \(y\), so the problem is a linear program. The \(2/3\) threshold becomes a constraint on stake mass, and Byzantine equivocation produces one finite family of view-specific constraints. This is not a theorem of Grossi’s paper, but it is a credible first computational result suggested by it.

The richer research question is what happens when \(R\) is replaced by a nontrivial social-choice rule. For scoring rules, the continuous problem may again be an LP whose difficulty lies in pricing over rankings. For rules with agenda-driven manipulation hardness, hardness may transfer into the continuous problem; for other rules, fractional stake may dissolve the discrete obstruction. Byzantine universal-safety constraints could also create a genuinely continuum-specific source of hardness. These are precisely the Class A/B/C questions the paper’s Section 3.2 leaves open.

The mirror covers only the paper’s voting and Byzantine-manipulation challenge. It does not claim to continuize the perpetual-lottery fairness discussion or the trust-network/Sybil discussion, both of which would require additional modelling choices and have no qualifying computational anchor here.

The weakest point is that the faithful Casper specialization may be too easy: a referee could regard it as an obvious weighted-threshold LP rather than a substantial new mirror. Making the rule richer creates more computational interest, but also moves from Casper’s concrete protocol to a family of blockchain voting mechanisms. More fundamentally, the paper’s actual trust and consensus systems involve graph structure, timing, and individually distinct validator identities; collapsing those into stake types can lose important protocol behaviour. The positive case therefore supports a strong, precise mirror of the paper’s proposed voting agenda, but not a theorem-level mirror of a result actually established in this paper.