Suppose that we have a dataset of semantic attestations, i.e. signed statements attesting to some semantic claim that cannot be verified by any algorithm (for example, that a particular public key is controlled by a specific person). It would be very useful if we could craft some kind of statistical test to aggregate many such attestations and test whether a particular claim is “true”, in a way in which:
- any party can be tested,
- no specific central entity has the determining vote,
- individual parties need make no more than a constant number of attestions, and
- small groups of colluding participants cannot determine the outcome.
The main motivating use-case here is some kind of decentralized proof-of-humanity, whereby this statistical test could be used to determine whether a particular public key corresponds to a unique human (uniqueness is a thorny problem which we will cover in more detail below), in a sufficiently robust manner that e.g. tokens could be distributed on this basis, with some confidence that a small group of colluding participants could not abuse the system.
For a second, let’s drop the uniqueness requirement, and analyze a simpler case. Suppose that we have a directed graph of “is-human” attestations, and wish to construct a test such that a colluding group of no more than n parties could affect the outcome. Assuming an omniscient observer, we can simply test whether or not, for any subset of n or fewer nodes, the set of paths from a selected party a to the tested party b includes paths which do not include any of the nodes in the selected subset. n colluding nodes all attesting to b will thus be unable to determine the outcome.
Approximating the perspective of the omniscient observer is a separate Bayesian statistics problem which we will bracket for now.
This test, of course, has no way to prevent a particular human from soliciting attestations for different public keys from different parties, and thus appearing to the test as multiple distinct humans (and perhaps claiming multiple shares of distributed tokens). In order to enforce some kind of uniqueness, we need participating parties to somehow be able to compare the attestations which they are making, and see whether or not attestations for two different public keys in fact correspond to only one human. This is fundamentally a problem of naming: in effect, we need a way for Alice and Bob to compare the Charlie who they both know (as Charlie), and notice if this Charlie has requested attestations for two distinct public keys.
Suppose that they have such a mechanism (a simple practical instantiation is for Alice and Bob to periodically compare their contact lists on Signal, or so to speak, and revoke multiple attestations where encountered), and suppose that there is some way to punish conflicting attestation requests which are likely to be intentional. I think perhaps we can simply combine this mechanism with the simpler (non-unique-enforcing) test, and thereby achieve a reasonably secure proof-of-humanity (assuming a solid dataset).
Of course, one could imagine a scenario where Charlie meets Alice in Alaska, requests an attestation to public key A, takes a long flight, meets Bob in Calcutta, requests an attestation to public key B, and Alice and Bob never meet – so Charlie may thereby claim two allocations. If attestations have a time limit, and must be periodically renewed, this will become expensive for Charlie to repeat: interacting in a way such that the parties you interact with cannot speak of you as one human carries serious costs in social and economic cooperation, which I think should be enough to more than offset the potential benefits in most cases here. One can also imagine stricter conditions for making such attestations (perhaps punishment is also extended to the conflicting-attestors), slightly delayed attestations (not immediately valid), and/or more complicated tests involving name-comparison across more layers of gossip, all of which raise the costs / reduce the rewards of attempting to game the system.
This isn’t fully worked out or formalized, but I wanted to jot my thoughts down and open this up for discussion. Pinging in particular @graphomath @apriori @mariari @adrian @degregat who may have opinions here.