Conundrum: Testing for EQ

Architecture Conundrums
1

[Mark Miller added this to the list. Someone please supply a link/text describing the exact form of this conundrum, which I will happily replace this text with.]

[See also Conundrum: LiveRefs, SturdyRefs, and Certs]

2

“EQ” here refers to lisp’s EQ (or eq? in scheme). Similar ideas appear in other languages; Python has is (but it’s not quite as precise as EQ). The idea really is, “do these objects point to the same thing?” Another way to think of it is:

  • "EQ asks whether two objects are the same thing by looking at their address.
  • EQUAL asks whether two objects are the same thing by looking at their contents."

Thus (eq? obj1 obj1) asks “are obj1 and obj2 the same by where they point to”. This is in contrast to (equal? obj1 obj2) which instead asks “whether obj1 and obj2 contain the same information”.

Another way to put it:

;; make two objects, both a cons of the 'a and 'b symbols
(define obj1 (cons 'a 'b))
(define obj2 (cons 'a 'b))
(define obj3 obj1)

(eq? obj1 obj2)        ; false
(equal? obj1 obj2)     ; true
(eq? obj1 obj3)        ; true

This has been spelled out in the greatest length in the Grant Matcher Puzzle writeup which gives a motivator for EQ: consider a grant-giving institution which is willing to donate to any charity which Alice and Dana both choose, should Alice and Dana both also donate to that institution. How does the grant giving institution know they have chosen the same place, and that one of them isn’t trying to trick the institution into pocketing the money?

Some functional programmers tend to find EQ very disturbing; isn’t something best described based on what it is? However, ocap people embrace encapsulated objects whose contents we might not even know and which also are designed to be able to change over time. So EQ is useful.

Alan Karp, and some others, pronounce EQ as “Eee Cue”, but I pronounce EQ as “eek!” Kevin Reid joked at one point that “this might be a reasonable response to EQ once you realize what it is!” I agree: though I think EQ is necessary, it gets into the realm of identity-comparison. If you aren’t careful, identity-comparison can accidentally lead to ACLs, and even without ACLs, confused deputies (I will expand on this in a separate thread). Still, I think we can’t live without it once we build social systems. Human communication requires multiple parties to both refer to the same object. Since Spritely is building social community platforms, we won’t be able to escape EQ either: it shows up in Petnames, and to a lesser extent, in the human-diagnostic portion of Horton. Guess we’re going to have to figure out how to deal with it safely… eek!

1 Like
3

Suppose you didn’t have an EQ, but somebody handed you a function calling itself EQ, telling you that it implemented EQ. How would you know whether it was a ‘correct’ EQ? What experiments could you perform that might support or rule out its being EQ? If you could do inductive reasoning over its definition, what would you check for?

Basically I find EQ disturbing not from a functional programming point of view, but from a distributed programming point of view. My intuition is that we cannot take identity to be primitive. It has to be built out of other things.

2 Likes
4

One interesting bit about that is that eq?'s interactions with promises… the promises themselves will not be eq?, but the things they resolve to should be. In MarkM’s dissertation this comes up with join implemented in section 19.5.

But note that there are disturbing implications for eg handoff values and hashmap keys and EQ in CapTP once three-party handoffs are involved: since A is handing B a reference to Carol on C, but it’s done via a handoff, Carol will appear as a promise reference in a hashmap rather than as Carol herself. See the lost resolution bug for some hand-wringing about this.

You can ignore this issue of “promises not really pointing to the final thing” and handoffs making those common in a lot of places, but in general the place where EQ really super ultra rears its head is in a petname database. As it turns out, the very first thing Jessica Tallon started implementing for Spritely is a petname database, and we found that for all that code, we had to pay careful attention that we fully resolved all promises in lots of places before dealing with referenced actors. A real headache.

5

I wonder if the right thing is to consider EQ as partial, or temporarily partial, and expose the partial/total distinction in the user interface. That is: suppose we have petnames for a set of references (resolved or not) R1, R2, … For any pair Ri, Rj we might know that they refer to ‘the same object’ (they’re EQ), or we might know they refer to ‘different objects’ (they’re not EQ), or we just might not know one way or another. I hypothesize that it is the differentness/samenesses that a user would care about. So when petnames are displayed they should be flagged as to whether they’re sufficiently resolved enough to distinguish their targets from those of other sufficiently resolved petnames. One way to do this would be to simply require syntactically distinguishable petnames for the two classes of references (sufficiently resolved vs. not sufficiently resolved). When resolution is achieved later on a reference could be given a higher quality pet name. … this is sort of like the ‘a’ vs. ‘the’ distinction. In language, names are definite (like ‘the’ phrases) and it is bad form to have two names for the same thing. But undetermined ‘a’ phrases do not look or behave like names and aren’t expected to. Just noodling here! I’m sure you’ve thought of all this.

1 Like
6

@jar I think what you’re describing resembles the way names get bound in human language and everyday experience, but the problem is also that that way of binding names also is what leaves people vulnerable to phishing. (Humans are the ultimate confused deputy!)

I think we need to aim for more precision, which is why selecting for strongly self-authenticating designators, and then mapping human meaning on top of them, ends up being important.

7

Uh, no, I didn’t say that at all. I was arguing for more precision so that instead of one kind of pet name for references, you’d have two kinds of pet names, one for definite (distinguishable) references and another for indefinite references. Building on whatever pet name system you have and refining it in a particular way. I understand the need for and theory of pet names.

1 Like
8

Ah! My mistake.

One way in which this might occur is that one would have a persona, but then that persona may appear in multiple subcontexts. For example, you and I might both appear in a MUD type game, and I might want to “know it’s you”, and the persona I have a petname for you signs off on this being a contextual presence of “you”. But can the game claim actions done by your character that you would not have done?

See also Chip’s post on the unum pattern, which introduces the idea of multiple “presences” of an “object”.

Some more thoughts on this on some cap-talk threads:

(Insert standard caveat that virtual world example given less as goal but more as robust example to test against.)

9

The erights.org page on the unum pattern and its example of how to solve certain kinds of scaling issues with the “ampitheater pattern” also introduces interesting EQ questions. The unum in general does this, and since our system needs to handle both una and petnames, it’s something we’re going to have to struggle through.

Alan’s ideas of “pre-authorized channels” lead to some of the solution for this in goblin-chat, but not all of it. The other piece came from sealers/unsealers. (That deserves documentation; it’s on the radar for Jessica and I to do so.)

10

It is reasonable to innumerate the different forms of EQ-Like tests in our capabilities & promises contexts? Perhaps initially using Descriptive-Function-Names?

Here’s some not-serious suggestions for consideration, where I use Unum in the EC way as a type of capability-object.

Same-Unum? [not just identifier] returns bool
Unum-Contents-Match-Test? [similar to stncmp in non-bool result of overlap, perhaps attribute matching?] returns something complex
Quiescent-Contents-Match? [waits for promise resolution?] bool

And perhaps we could define EQ? and EQUAL? to throw exceptions to prevent new-cap-programmer confusion?

Again, these aren’t serious suggestions, but riffing on comments made so far. What, exactly, are the EQ-like tests do we need? What does Agoric use, and why? What about other capability languages?

1 Like
11

Client Utility had the EQ problem because it used path based identifiers. Our enterprise customers were extremely worried about that, so I implemented the “Ask Bob” protocol that generated a trace record. (The origin of the name, while true, sounds like a shaggy dog story.) I never saw one of those trace records in the 6 months or so that I stayed with the product team. That lesson has limited value, because business interactions have a lot of builtin trust.

Is EQ a good idea in all circumstances, or is it something best left to individual applications? For example, “Ask Bob” prevented different objects from claiming to be the same one, but it allowed an object to deny that two references to it were the same. (It also had a vulnerability if the two paths shared a common node.) In game terms, you can say that the protocol allowed players to keep different personas separate if they wanted to.

2 Likes
12

Here is a similie I use to explain various ways of EQ? :

Imagine a house that sits at the corner of two streets.
Due to some wonkyness it has two house numbers, one for each street.
Now Alice wants to send Bob who lives in that house a postcard.
She can address it to him and use either address of the house.
Carol, knows Bob and sends him letters every whenever.
But one day Carol sees an ad in a newspaper that states an psuedonymous person is holding an limeric competetion and please send your attempt to Forwarding Box xxxx.
Carol does not know that Bob is holding that competetion and Alice is unaware at all that such competetion is taking place.

The questions of EQ? is often split up into:
1. are the addresses equal? that is if you xor their bits together you end up with a string of zeros.
2. are the addresses naming the same place?
3. will the messages (letters and postcards) sent via those addresses end up at the same place?
4. will they end up with the same person?
5. could the two personas cooperate in Ask Bob protocol? only if they are in cahoots with one and other.
6. by postmans mistake one of the letters to Bob got put into Daves postbox in the house, Dave was away for the week and could only rectify the mistake once he returned. Isnt the final place of the letter still Bobs?

If you need to use EQ? over such bits only medium for rights amplification you can use Ask Bob or use random sum seceret sharing to synthesize an bitstream channel from two such addresses by sending half of the shares one way and the other half the other way.

14

You’re completely right @dale.schumacher! Fixed, thanks!