[cap-talk] Amplify with WeakKeyMaps, it's cleaner. (was: horton questions)

[Mark Miller]

On 6/9/07, Jed Donnelley <capability at webstart.com> wrote:
> At 02:38 PM 6/8/2007, Peter Amstutz wrote:
> >One thing I found confusing about Horton [...] "getGuts".  [...]
>
> I agree.  I've commented to MarkM about this and suggested that
> another writeup using just capabilities as data and conventional
> cryptography would be very helpful.  Would you like to collaborate
> on such a writeup (perhaps you are on the road alone with what
> you describe below?)?
>
> Regarding "getGuts", did you take a look at the version of Horton
> that uses rights amplification:
>
> http://www.erights.org/elib/capability/horton/amplify.html
>
> ?  It does away with "getGuts" and uses wrapping more appropriately
> (if with somewhat more complexity).  Perhaps MarkM can comment
> more accurately.

The WeakKeyMap technique for rights amplification used there was
suggested by Ping and Alan, and is similar to my first exploration of
rights amplification in the 1987 Logical Secrets paper, which, sadly,
does not seem to be online.

A WeakKeyMap is a kind of mutable hash table (FlexMap in E) whose keys
are used only for their unique EQ-ness identity (in E, the keys are
resolved references to selfish E objects). The map is weak-on-keys in
that the existence of an association from key K1 to value V1 does not
itself cause the key K1 to be reachable. If key K1 is not otherwise
reachable (i.e., by traversing strong pointers from roots), then the
garbage collector is free to collect K1. Should the garbage collector
collect K1, the K1=>V1 association must (seem to) disappear from this
WeakKeyMap atomically at that moment, and likewise for all other
weakKeyMaps with an association keyed off of K1.

So long as we do not enumerate the map or ask its size, a WeaKeyMap
acts just like a regular FlexMap, since, if K1 no longer exists, no
one could have tried looking it up to find that it's been removed.
Therefore, resource utilization aside, all our uses of a WeakKeyMap
for amplification could have used a normal FlexMap instead.

To demonstrate the use of WeakKeyMaps for rights amplification, here
is yet another implementation of makeBrandPair in E using this
technique. The following is essential the "Ping Sealer/Unsealer"
pattern from <http://eros-os.org/~majordomo/e-lang/1062.html> updated
to modern E.

def makeWeakKeyMap := <unsafe:org.erights.e.elib.tables.makeWeakKeyMap>

def makeBrandPair(_) {
    def boxAmps := makeWeakKeyMap()
    def sealer {
        to seal(contents) {
            def boxKey {}
            boxAmps[boxKey] := contents
            return boxKey
        }
    def unsealer {
        to unseal(boxKey) {
            return boxAmps[boxKey]
        }
    }
    return [sealer, unsealer]
}

This technique is arguably cleaner than the others in one way: The
sealed box contains no internal-use methods whatsoever, thereby not
exposing these as interface noise which is useless to its clients
anyway.

The big advantage of the WeakKeyMap technique is that you can directly
amplify existing selfish objects as well, without needing to invent
sealer/unsealers as an intermediate level of abstraction. Compare the
money example code at:

<http://www.erights.org/elib/capability/ode/ode-capabilities.html#simple-money>

with:

def makeMint(name) :any {
    def purseAmps := makeWeakKeyMap()
    def mint {
        to makePurse(var balance :(int >= 0)) :any {
            def decr(amount :(0..balance)) :void {
                balance -= amount
            }
            def purse {
                to getBalance() :int { return balance }
                to sprout()     :any { return mint.makePurse(0) }

                to deposit(amount :int, src) :void {
                    purseAmps[src](amount)
                    balance += amount
                }
            }
            purseAmps[purse] := decr
            return purse
        }
    }
    return mint
}

Not only is it simpler, it reproduces the same advantage at a higher
level. Purses no longer expose a getDecr() message which is anyway
useless to its clients.

The amplification shown here among purses of the same currency is much
like the amplification among proxies of the same principle shown at
<http://erights.org/elib/capability/horton/amplify.html>. The
mailkeys/horton adaptation at
<http://www.erights.org/elib/capability/horton/mailkeys.html> no
longer even imports E's makeBrandPair, using the WeakKeyMap technique
to open-code all rights amplification.

-- 
Text by me above is hereby placed in the public domain

    Cheers,
    --MarkM