We introduce a new framework for polling responses from a large population of humans.
Our framework allows to gather information without violating the responders' anonymity
and at the same time enables public verification of the poll's result. In contrast
to prior approaches to the problem, we do not require trusting the pollster
for faithfully announcing the poll's results, nor do we rely on strong identity
verification (a prerequisite for publicly verifiable voting systems).
We propose an "effort based" polling protocol whose results can be publicly verified
by constructing a "responder certification graph" whose nodes are labeled by
replies to the poll, and whose edges cross-certify that adjacent nodes correspond to
human votes. Cross-certification is achieved using a newly introduced (privately
proof of "human effort" (PHE). The proof relies on expansion properties of the
In effect, our protocol can be thought of as a method for converting certain types
protocols into a publicly-verifiable protocol.
Our results are applicable to a variety of settings in which crowd-sourced information
gathering is required. This includes political polling, recommendation systems, viewer
voting in TV shows and prediction markets.