Schelling tests

Cryptoeconomics
1

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.

1 Like
2

I read the post a few times. One area that I thought could be of direct impact is airdrops. In particular, I am thinking similar to universal basic income protocols or perhaps something more crypto native like a means to distribute tokens to a desired group of people.

it seems that if the cost of traveling to Calcutta is less than the reward received, then the rational move is always to travel to Calcutta. And by cost here i also mean cost inclusive of reputational cost.

You are suggesting three approaches to increase the cost / reduce the reward of gaming the system:

  1. time-based constraints
  2. slashing (reputation + economic slashing)
  3. behavioral pattern analysis

Is this correct?

2 Likes
3

Yes, that’s also the main motivating use-case for me here – although I think there could be others as well, such as certain kinds of distributed / fault-tolerant oracles (the attestation could include more than a 0/1 value).

Yes, although depending on the slashing constructions the costs may be incurred by more than one party (e.g. perhaps Bob’s bond will be slashed if it is later determined that he attested to Charlie incorrectly - giving Bob reason not to do this without some referral from a previous party who knew Charlie, which Charlie cannot obtain without outing himself.

1 and 2 - yes. 3 - I’m suggesting that we could design additional mechanisms to test whether or not conflicting attestations have been published that extend beyond two parties directly comparing the “Charlies” which they know. I haven’t spelled out the details of these mechanisms yet.

1 Like
4

a few other half-baked ideas.

  • use of biometric data to prove uniqueness; e.g. fingerprint or eyeball scan. these come with some downsides though including where and how that particular data is stored. i also have argued with worldcoin maxis that you can indeed fake the iris scan by creating a fake face with fake eye balls.
  • is there any other information which in some circumstances may be useful to jump start the Schelling test. for example, let’s say that Charlie is known to have funded a particular EOA from a centralized exchange as that information is public. this means that Charlie used coinbase to fund that account, so this means that there is a human associated with that EOA. maybe this doesn’t particularly solve this specific problem. also, people can easily withdraw to multiple EOAs and reliance on a centralized solution for KYC (know your customer) based proof of humanity isn’t really what you want, just an idea. but if you combined this type of identifier with a trust graph of attestations, you potentially could get a better idea if Charlie is cheating or not.
  • allow lists - determine up front which identities you are willing to airdrop to based on attestations which require in person verification with an exposed public key. for example, charlie would have to register his address in person. not dissimilar to getting scanned by a world coin orb, but at least there is no iris scan. without it though, this type of system can be gamed easily.
  • another thing you could do is just assume people will try to game the system and just treat each human identity like half a human or a quarter or an eighth, for example. this has downsides, as allocation then still will go to farmers / sybils, but they will not be as handsomely rewarded.

all of these suggestions are inferior to the solutions proposed above. maybe worth mentioning just for the sake of it.

2 Likes
5

I think this kind of data is data that could factor into the judgement (of a particular party) as to whether to grant an attestation or not. Nothing stops – for example – Worldcoin from attesting to parties whose irises that they have scanned (dystopian as we may think this is) – but their bond would be at stake and potentially slashed if it turns out they got fooled by a fake iris.

To me this seems similar to the above case - having conducted KYC would be data that Coinbase (or some party observing interactions with a Coinbase account) might use in order to make these “is-human” attestations.

This is starting to get pretty similar to how governments actually do ID verification (before issuing a passport or a driver’s license or whatever) – (as I remember) you show up to some office in person and fill out some forms. Imposing a person-time cost to Sybil attacks is always helpful, as person-time is fundamentally expensive.

How does this help? I don’t quite follow. If you want to distribute some universal per-human token allocation, for example, you would just have to distribute more in order to get the same amount to real humans, and the bots / farmers / etc. would benefit just as much, no?

2 Likes
6

maybe not much, didn’t think deeply about it. but my thinking is that if you tell people up front that its assumed their identity is a sybil then it incentives those bot farms and other mercenaries to go elsewhere where ROI is potentially higher. but yeah, you probably just wind up distributing more and the allocations wind up the same.

1 Like
7

I have spent some time digging up resources,[1] wrapping my head around concepts, in particular asking myself what a Schelling Test would be elsewhere. Luckily I have found the following.[2]

The [specific] Schelling test consists of a series of 14 tacit coordination questions. For example, if you are to meet a friend in New York City at an unknown time and place, where would you choose to meet? The most frequent response, which forms a plurality, is Central Station at noon. Students are then ranked from best to worst in their ability to anticipate the interests of others and obtain correct answers.

Now, I guess, “semantic assertions” are in analogy to the (answers to) coordination questions, in order to come up with the term Schelling test. However, I am a bit puzzled, since a semantic attestation can be either true or false, and there is nothing intrinsic in the best answers in a Schelling test.

However, maybe I just had the wrong working definition?

Semantic claim

This consists of

  • a piece of digital data
  • bearing a digital signature
  • (references to) truth conditions that go beyond the piece of data (and the signature)

I essentially jumped over the rabbit hole of theory of names (but that’s just personal preference—while definite descriptions are fun).

Now, on a courser resolution: this post is about

  • data
  • statistical inference, and
  • some kind of resilience to (malicious) colluding groups.

My heureka moment was that I should “just” search in the federated learning department, and found, in chronological order

So, my conjecture is that we are looking for something like Byzantine-Robust Federated Learning ᴡɪᴛʜ ᴏʀᴀᴄʟᴇꜱ … and if not, then it may be worth to present “our cause” in relation to this area of work.[4] Prove me wrong :wink:

  1. I have read the below posts by @apriori and replies by @cwgoes ; however, I came to the conclusion that they rather are about specific use cases rather than the general principle; see also my last footnote … ↩︎

  2. The quote is from this paper. ↩︎

  3. Moreover, he is recognized highly in French academia. ↩︎

  4. I also read up on liberté, égalité, fraternité, but that’s for another post in the heterotopia category. ↩︎

2 Likes
8

Only intersubjectively – at least in the sense that I mean. No fixed or objective measure delineates “humans” from “non-humans”, but we can define the truth conditions for semantic attestations as ~ intersubjective agreement, which is what I’ve done here.

… from this I infer that we probably agree. Of course, there are many actual reasons why someone may choose to believe that I am human or not, but none of these reasons are intrinsic to the attestation per se, and we may intersubjectively agree but for different reasons.

Yes, in some sense, I think that this is a problem of agreeing on naming – hence my use of the word “semantic” – but that rabbit hole likely introduces many problems which we don’t need to solve.

Interesting conjecture (and interesting sources)! I don’t quite follow how federated learning would result in the type of output we’re looking for here, though – in my (very naive) understanding, the aim of federated learning is typically to train a single logical model using data from multiple sources, without those sources being required to reveal their data to a single training server (or cluster). What is the model in our case / what would it be trying to predict? Training a model to predict whether a particular public key is associated with a unique human or not seems… overkill to me, although perhaps there’s some abstract mathematical correspondence. What sort of correspondence did you have in mind here / what would the formulation of the training problem and inference outputs look like?

2 Likes
9

Observer dependent uniqueness proof

This sounds like we should be able to turn this into a (succinct ZK) proof, which attests uniqueness within this set. Then instead of the omniscient observer, we use a local observer (potentially with a TEE or MPC) to compute the proof. Different observers could use different methods (of varying guarantees) of verifying identity. Generating anonymous credentials tied to the proof at the same time could optionally enable proof bearers to reveal partial information about the participating set, e.g. set size, identity subsets, computing nodes, a group identity for the set.

Local observers could cooperate with others and run a private set intersection over attested identities before generating the proof, proving uniquness for the union of subsets, up to the trust assumptions. If plaintexts are cached, this could also happen over time.
By perfoming (iterated) private set intersection over more and more subsets, we can improve confidence in identities being unconnected in-band.

Out-of-band uniqueness and Sybil Resistance

Charlie can prove to Alice that he has control of a key, by producing a signature or decrypting a message using it, but he can not prove to her that he doesn’t control Bobs keys too, using only cryptography, so there is no way to give a uniqueness proof.

That means we have to assume there will also be sybils which are newly created and not connected to the history of another identity. Accumulating attestations for them will be costly, and we could use different parameters to influence the cost and raise the bar for sybil attacks being worth it.
We can also punish sybils upon detection, when a proof for multiple identities being connected is discovered. This would work similarly to a proof of collusion.

Proof-of-Personhood and Pseudonym Parties are one approach to guarantee uniqueness, but are probably less practical than we would like. For global uniqueness, they would all have to be synchronous.

Further Reading

Genuine Personal Identifiers and Mutual Sureties for Sybil-Resilient Community Formation

2 Likes
10

I think we’re directionally in agreement. I haven’t thought through all of the specific possible ways to generate and combine the local-observer proofs, but in general, my idea of the approach here is:

  1. Figure out what kind of query a hypothetical omniscient observer would run (let’s call it Q), then
  2. Figure out how to create compositional proofs that – post-composition – prove some statement like ~ “If an observer ran that query Q, the result would be X”

In principle – assuming that the parties with the relevant information participate – this decomposition should always be possible, with varying specific requirements as to what has to be disclosed to whom during proof creation depending on details that we haven’t fully spelled out yet.

Yes. The general approach here is two-pronged, namely:

  1. Make it sufficiently difficult to acquire attestations (particularly for new identities unconnected to any previous history), and
  2. Punish detected Sybils / conflicting attestations, and punish parties who enabled them (what level of transitive punishment is required here is still TBD).

I think that these “pseudonym party” / “physical synchrony” mechanisms are not likely to be feasible as the sole mechanisms to provide proof-of-unique-personhood, but I think that they might indeed be useful in convincing someone to give you an attestation. Suppose that psuedonym parties are regular, and somewhat aligned with existing social groupings (which have a purpose beyond just the pseudonym parties). I might be reasonably willing to give an attestation to someone I’ve just met in person at a pseudonym party if they already have a bit of a reputation within the community – meaning that their attempts at defection might prove costly, and faking a whole in-person community is pretty expensive.

Ahaha, of course it would be none other than Ehud Shapiro who has already formalized something quite close to this very proposal. This paper looks fantastic, let’s add it to the reading list.

1 Like
11

It is unclear to me whether we can generate proofs that compose after being locally computed, but we might be able to come up with practical protocols that might require some amount of synchronous computation or delegation. Relevant work:

If parties are regular enough and communities have some overlap, they might help to detect people who try get attestations for different identities. To mitigate malicious calling out of a legitimate participant we need to think about further mechanisms:

  • Proof of revocation/deletion, s.t. one can prove a former identity not being in use anymore retired
  • (Social) mechanisms to validate accusations

After a cursory reading, it looks to me that attestation graph is not private, but apart from this, the system should have the properties we want.

1 Like
12

We could potentially provide bounds for the above problem as follows:

Pseudonym Parties for Rate Limiting

Even if pseudonym parties are not practical to guarantee global uniqueness, having parties distributed in space, but synchronized in time, would help to rate limit the amount of pseudonyms an agent could accumulate, which is already worthwhile for some use cases.

Example

If there is a network of parties, which are all on e.g. day of week = number of week in year % 7, hour = (number of week in year % 24) in UTC, to enable access to people with diverse schedules, one could accumulate at most 52 identities per year, given that find one party every week that has no overlap with the last one.

2 Likes
13

I read the paper somewhat more thoroughly – this is indeed nearly exactly in line with what we want, I think. A lot of work remains to be done to figure out how exactly this would work in the Anoma context (the paper assumes a single, globally ordered + available bulletin board, which we probably don’t want to assume, doesn’t specify reward/punishment mechanisms, and doesn’t provide a full analysis of incentive-compatibility), but it’s certainly the same general approach and illustrates the basic principle.

I think we can now split this work into ~ two tracks:

  • The practical track, focused on iterative prototyping of an associated application (for attestations).
  • The theoretical track, focused on further study and analysis.

Let’s discuss this more soon.

2 Likes