The Pebble Bank: Digital cash in an asynchronous environment
23 views
Skip to first unread message
Christine Lemmer-Webber
Dec 12, 2021, 5:51:52 PM12/12/21
to cap-...@googlegroups.com
New blogpost by Jessica Tallon over on the Spritely Project blog:
https://spritelyproject.org/news/pebble-bank.html
Jessica and I talked about this at Friam recently, but basically this is
a demonstration of a simple ocap bank design which Jessica came up with
on *week two* on the job being fulltime on Spritely stuff.
Jessica was challenging me whether or not synchronous operations were
really ever needed in the vat design. I was explaining her the
traditional ocap mint example from the Ode paper and saying "this is why
we need synchronous operations", and Jessica said "I don't think that's
true", and proceeded to explain the above approach.
I walked dazed down to lunch. Morgan (my spouse) and I were supposed to
be having a conversation but I was so overwhelmed trying to find a hole
in Jessica's design that I was unable to talk and Morgan said "okay,
just go upstairs and write an implementation because you've clearly been
made useless by this idea until you have it written down." Both Jessica
and I wrote implementations; they're mostly the same, but mine shows up
in the blogpost because it was a bit more conventional to Spritely
Goblins' coding style.
The design is all Jessica's, I merely contributed the name. The
metaphor is a banker sitting on a wide beach with a ledger. The banker
has a meticulous eye and has written down the set of current valid
pebbles. When a payment is desired, Alice merely hands some pebbles to
Bob. Bob exchanges them with the banker who crosses off the old pebbles
(they're invalid) and hands Bob some new pebbles. Thus Alice has no
access to the old currency, so exclusivity is preserved. Something akin
to "purses" is still possible, but we call them "pouches", but they have
no essential role: they're just an object to store some pebbles and
cache their current accumulated value.
- Christine
PS: Note that this takes an almost "peano arithmetic" approach; we use
the smallest denomination of the currency (akin to working entirely in
pennies) in the example with a set that shows all the current "valid
pebbles". However as Jessica notes in the post, we can provide
compression and have larger denominations: simply use a hashtable
mapping the valid pebble to its numerical value and when exchanging
permit giving the requested numerical change values.
PPS: I think I might have thoroughly broken MarkM for about two minutes
when explaining the above also based on him seeming to need to sit down
and his face seeming to scrunch into a temporary black hole as he
thought about it. But afterwards he said that the ocap mint approach
was one of the convincing examples for vats, and that Joule had an
example in its documentation, which I think is this (which I've tried to
understand previously, unsuccessfuly):
http://erights.org/history/joule/MANUAL.BK8.pdf
But the Joule example was more complicated and had bugs, so the swapping
idea being sufficient was the surprising thing.
PPPS: This doesn't mean that synchronous turns in vats are out of the
running now, though. I explained a problem I had run into in my
previous actor-MUD type sytems, where a player needed to move between
rooms and have an "official location" at any given time. Strange things
would happen if this was all done asynchronously: the departing room,
the player, and the entering room would often be out of sync with
conflicting beliefs as to where the player was. This was especially
risky with saving and restoring, and could lead to weird things if
attacking another player and a fireball hitting them in the back of the
head after they enter a separate room! Jessica agreed that this was
still a good example for vat synchrony... or at least, that she didn't
(yet) have a good counter-proposal...!
https://spritelyproject.org/news/pebble-bank.html
Jessica and I talked about this at Friam recently, but basically this is
a demonstration of a simple ocap bank design which Jessica came up with
on *week two* on the job being fulltime on Spritely stuff.
Jessica was challenging me whether or not synchronous operations were
really ever needed in the vat design. I was explaining her the
traditional ocap mint example from the Ode paper and saying "this is why
we need synchronous operations", and Jessica said "I don't think that's
true", and proceeded to explain the above approach.
I walked dazed down to lunch. Morgan (my spouse) and I were supposed to
be having a conversation but I was so overwhelmed trying to find a hole
in Jessica's design that I was unable to talk and Morgan said "okay,
just go upstairs and write an implementation because you've clearly been
made useless by this idea until you have it written down." Both Jessica
and I wrote implementations; they're mostly the same, but mine shows up
in the blogpost because it was a bit more conventional to Spritely
Goblins' coding style.
The design is all Jessica's, I merely contributed the name. The
metaphor is a banker sitting on a wide beach with a ledger. The banker
has a meticulous eye and has written down the set of current valid
pebbles. When a payment is desired, Alice merely hands some pebbles to
Bob. Bob exchanges them with the banker who crosses off the old pebbles
(they're invalid) and hands Bob some new pebbles. Thus Alice has no
access to the old currency, so exclusivity is preserved. Something akin
to "purses" is still possible, but we call them "pouches", but they have
no essential role: they're just an object to store some pebbles and
cache their current accumulated value.
- Christine
PS: Note that this takes an almost "peano arithmetic" approach; we use
the smallest denomination of the currency (akin to working entirely in
pennies) in the example with a set that shows all the current "valid
pebbles". However as Jessica notes in the post, we can provide
compression and have larger denominations: simply use a hashtable
mapping the valid pebble to its numerical value and when exchanging
permit giving the requested numerical change values.
PPS: I think I might have thoroughly broken MarkM for about two minutes
when explaining the above also based on him seeming to need to sit down
and his face seeming to scrunch into a temporary black hole as he
thought about it. But afterwards he said that the ocap mint approach
was one of the convincing examples for vats, and that Joule had an
example in its documentation, which I think is this (which I've tried to
understand previously, unsuccessfuly):
http://erights.org/history/joule/MANUAL.BK8.pdf
But the Joule example was more complicated and had bugs, so the swapping
idea being sufficient was the surprising thing.
PPPS: This doesn't mean that synchronous turns in vats are out of the
running now, though. I explained a problem I had run into in my
previous actor-MUD type sytems, where a player needed to move between
rooms and have an "official location" at any given time. Strange things
would happen if this was all done asynchronously: the departing room,
the player, and the entering room would often be out of sync with
conflicting beliefs as to where the player was. This was especially
risky with saving and restoring, and could lead to weird things if
attacking another player and a fireball hitting them in the back of the
head after they enter a separate room! Jessica agreed that this was
still a good example for vat synchrony... or at least, that she didn't
(yet) have a good counter-proposal...!
Christine Lemmer-Webber
Dec 12, 2021, 6:10:50 PM12/12/21
to cap-...@googlegroups.com
hole of ponderance/processing could have also been the result of being
in a noisy venue, I wasn't sure. :)
William ML Leslie
Dec 12, 2021, 7:40:15 PM12/12/21
to cap-talk
Very nice.
If all usage of the set of active pebbles is linear and constructive, it does not matter if the functions on sets are synchronous or not, since the mint already preserves constraints about serial updates.
The challenge is often that linearity can be difficult to maintain without a type system that checks for this.
--
You received this message because you are subscribed to the Google Groups "cap-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cap-talk+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/cap-talk/87sfux308p.fsf%40dustycloud.org.
Christine Lemmer-Webber
Dec 13, 2021, 9:24:10 AM12/13/21
to cap-...@googlegroups.com, William ML Leslie
Heh, you're pointing at one part which we glossed over in the
demonstration... we use actor-like-"become" operations *in conjunction*
with Racket's existing immutable sets. Of course, even "cons" would be
sufficient (although O(n) the size of your beach), but cons isn't
exactly asynchronous-actor'y.
But since most actor systems "in practice" seem to permit something like
local immutable arrays of data, etc, I figured we could gloss over that.
But if not, just first create your universe with asynchronous actor data
containers, then bake the following pebble pie. ;)
demonstration... we use actor-like-"become" operations *in conjunction*
with Racket's existing immutable sets. Of course, even "cons" would be
sufficient (although O(n) the size of your beach), but cons isn't
exactly asynchronous-actor'y.
But since most actor systems "in practice" seem to permit something like
local immutable arrays of data, etc, I figured we could gloss over that.
But if not, just first create your universe with asynchronous actor data
containers, then bake the following pebble pie. ;)
David Nicol
Dec 13, 2021, 10:56:29 AM12/13/21
to cap-...@googlegroups.com
Having pondered this stuff since the mid-nineties, it is my belief that the only requirement for synchronization in a ledger system is to prevent double-spending. This is accomplished by single-threadng the perimeter to the system, at account grain. Ledger grain works too -- doing it account grain allows greater parallelism, analogous to table-locking versus row-locking in databases.
To view this discussion on the web visit https://groups.google.com/d/msgid/cap-talk/877dc81t2u.fsf%40dustycloud.org.
"Lay off that whiskey, and let that cocaine be!" -- Johnny Cash
Alan Karp
Dec 13, 2021, 1:49:09 PM12/13/21
to cap-...@googlegroups.com
On Sun, Dec 12, 2021 at 2:51 PM Christine Lemmer-Webber <cwe...@dustycloud.org> wrote:
I walked dazed down to lunch. Morgan (my spouse) and I were supposed to
be having a conversation but I was so overwhelmed trying to find a hole
in Jessica's design that I was unable to talk and Morgan said "okay,
just go upstairs and write an implementation because you've clearly been
made useless by this idea until you have it written down." Both Jessica
and I wrote implementations; they're mostly the same, but mine shows up
in the blogpost because it was a bit more conventional to Spritely
Goblins' coding style.
And very readable code it is. I don't speak Goblins, but I could follow even without the comments.
PPPS: This doesn't mean that synchronous turns in vats are out of the
running now, though. I explained a problem I had run into in my
previous actor-MUD type sytems, where a player needed to move between
rooms and have an "official location" at any given time. Strange things
would happen if this was all done asynchronously: the departing room,
the player, and the entering room would often be out of sync with
conflicting beliefs as to where the player was. This was especially
risky with saving and restoring, and could lead to weird things if
attacking another player and a fireball hitting them in the back of the
head after they enter a separate room! Jessica agreed that this was
still a good example for vat synchrony... or at least, that she didn't
(yet) have a good counter-proposal...!
I wonder if you can apply CRDTs (Conflict-free Replicated Data Types) to this problem. It doesn't seem to be all that different from shared editing of a document. Another choice would be a consensus protocol, such as Paxos or Raft, but that may be too much overhead.
--------------
Alan Karp
Raoul Duke
Dec 13, 2021, 2:32:22 PM12/13/21
to cap-...@googlegroups.com
>> PPPS: This doesn't mean that synchronous turns in vats are out of the
>> running now, though. I explained a problem I had run into in my
>> previous actor-MUD type sytems, where a player needed to move between
>> rooms and have an "official location" at any given time. Strange things
>> would happen if this was all done asynchronously: the departing room,
>> the player, and the entering room would often be out of sync with
>> conflicting beliefs as to where the player was. This was especially
>> risky with saving and restoring, and could lead to weird things if
>> attacking another player and a fireball hitting them in the back of the
>> head after they enter a separate room! Jessica agreed that this was
>> still a good example for vat synchrony... or at least, that she didn't
>> (yet) have a good counter-proposal...!
ot'ing...
>> running now, though. I explained a problem I had run into in my
>> previous actor-MUD type sytems, where a player needed to move between
>> rooms and have an "official location" at any given time. Strange things
>> would happen if this was all done asynchronously: the departing room,
>> the player, and the entering room would often be out of sync with
>> conflicting beliefs as to where the player was. This was especially
>> risky with saving and restoring, and could lead to weird things if
>> attacking another player and a fireball hitting them in the back of the
>> head after they enter a separate room! Jessica agreed that this was
>> still a good example for vat synchrony... or at least, that she didn't
>> (yet) have a good counter-proposal...!
In my (limited) professional work on video games, not having a correct
ordering of events AND not having timestamps (reliable ones,
handwaving) means yeah bugs are going to show up.
I guess there's a difference between several locations thinking the
player is in their area, vs. there being times when no location thinks
the player is in their area.
The former seems to me could be addressed with timestamps of
leaving-entering (somehow, handwavy) but I assume the latter is an
inevitable worst case thing to have to design for.
Matt Rice
Dec 13, 2021, 3:18:54 PM12/13/21
to cap-talk
example than fireballs from nowhere),
that I've seen this sort of bug as the source of item duplication bugs
in games, where you get into the multi-location state, and somehow
drop things at all the locations then go around and pick them up.
William ML Leslie
Dec 13, 2021, 4:09:16 PM12/13/21
to cap-talk
On Tue, 14 Dec 2021, 1:24 am Christine Lemmer-Webber, <cwe...@dustycloud.org> wrote:
Heh, you're pointing at one part which we glossed over in the
demonstration... we use actor-like-"become" operations *in conjunction*
with Racket's existing immutable sets. Of course, even "cons" would be
sufficient (although O(n) the size of your beach), but cons isn't
exactly asynchronous-actor'y.
But since most actor systems "in practice" seem to permit something like
local immutable arrays of data, etc, I figured we could gloss over that.
But if not, just first create your universe with asynchronous actor data
containers, then bake the following pebble pie. ;)
What I mean to say is that in order to prevent double spend, this code relies on the fact that nothing else can touch the set of valid pebbles until this method completes. It's nice that it all fits within one method here, with the bcom enforcing that even if the set functions were asynchronous, there's still only one interaction going on at a time.
The challenge being that if the behaviour doesn't fit within a single method supplimented by pure functions, you'l still really want synchronous local calls!
Christine Lemmer-Webber
Dec 13, 2021, 4:20:34 PM12/13/21
to cap-...@googlegroups.com, Matt Rice
kately...@gmail.com
Dec 13, 2021, 4:33:26 PM12/13/21
to cap-talk
First off, this is a fantastic blog post! It's really exciting to see smart people working on ocap-based token design. When I was working on ERTP at Agoric, it felt like we were the only ones.
I'm interested in a comparison of the pebble-bank to the current ERTP implementation (https://github.com/Agoric/agoric-sdk/tree/master/packages/ERTP). Mark, Christine indicated that you were surprised by synchronous operations not being required in Jessica's "burn and then mint" idea for transfers. Can you explain why?
This seems like it would work in the current ERTP. To give context for everyone else, in ERTP, a deposit works like this: a user has a Far payment object, which "holds" (is mapped to) a certain amount (either a number in the case of a fungible token, or an identity/description in the case of a non-fungible token). A user has a reference to a Far purse object, and asynchronously calls the deposit method on the purse, passing in the payment object. After some checks are done, the payment is synchronously destroyed (deleted from the map), and the purse balance is synchronously updated. It seems like the payment could be destroyed asynchronously, returning the amount of the payment, and then the amount from the payment could be asynchronously added to the purse balance. Rights conservation (the invariant that transfers maintain the same amount of tokens) wouldn't hold, but you might be able to fix that with a "pool" that holds amounts from destroyed payments that can be later added to purses. Once you account for the amounts in transit in the "pool", rights conservation does hold.
I'm interested in a comparison of the pebble-bank to the current ERTP implementation (https://github.com/Agoric/agoric-sdk/tree/master/packages/ERTP). Mark, Christine indicated that you were surprised by synchronous operations not being required in Jessica's "burn and then mint" idea for transfers. Can you explain why?
This seems like it would work in the current ERTP. To give context for everyone else, in ERTP, a deposit works like this: a user has a Far payment object, which "holds" (is mapped to) a certain amount (either a number in the case of a fungible token, or an identity/description in the case of a non-fungible token). A user has a reference to a Far purse object, and asynchronously calls the deposit method on the purse, passing in the payment object. After some checks are done, the payment is synchronously destroyed (deleted from the map), and the purse balance is synchronously updated. It seems like the payment could be destroyed asynchronously, returning the amount of the payment, and then the amount from the payment could be asynchronously added to the purse balance. Rights conservation (the invariant that transfers maintain the same amount of tokens) wouldn't hold, but you might be able to fix that with a "pool" that holds amounts from destroyed payments that can be later added to purses. Once you account for the amounts in transit in the "pool", rights conservation does hold.
What do you think?
Best,
Kate
kately...@gmail.com
Dec 13, 2021, 4:33:37 PM12/13/21
to cap-talk
First off, it's fantastic to read blog posts like this! It's great to see someone super smart working on tokens with an ocap design. When I was working on ERTP, it seemed like it was just me and the rest of Agoric, so this is very exciting!
I wonder how the pattern of a transfer being an internal asynchronous burn of pebbles and then asynchronous mint of pebbles compares to current ERTP code. To deposit into a purse, current ERTP code works like this: the user calls the deposit method on a purse (a Far object, so this is an asynchronous call to the user), passing in the payment object. After checks pass, the purse synchronously destroys a payment object (deletes it from a map) and then synchronously updates the balance of the purse. (The payment may "contain" (aka be mapped to) a natural number in the case of a fungible token, or a unique identifier and other information in the case of an NFT).
It seems plausible to me that this could be done in two asynchronous steps, similar to the pebbles, at the cost of "rights conservation" (the principle that transfers maintain the same total amount). The two steps would be: asynchronously attempt to delete the payment, if that succeeds, you get the amount of the payment. Then, asynchronously make a call to the purse admin facet to add the amount as a delta, with no knowledge of the current purse balance. Because these two calls would not be exposed to the user, there is no additional access control needed - the mint/issuer already has the authority to destroy payments and update purse balances. It also seems like rights conservation could be maintained with the addition of a "pool" of amounts that had been in destroyed payments, but hadn't yet been added to purses.
Mark, Christine indicated you were very surprised by Jessica's approach. Can you explain why?
Best,
Kate
On Sunday, December 12, 2021 at 2:51:52 PM UTC-8 cwe...@dustycloud.org wrote:
Christine Lemmer-Webber
Dec 13, 2021, 9:46:16 PM12/13/21
to cap-...@googlegroups.com, kately...@gmail.com
"kately...@gmail.com" <kately...@gmail.com> writes:
> First off, this is a fantastic blog post! It's really exciting to see
> smart people working on ocap-based token design. When I was working
> on ERTP at Agoric, it felt like we were the only ones.
Hey Kate! Thanks for this follow-up. Yes unshockingly I'm very
> First off, this is a fantastic blog post! It's really exciting to see
> smart people working on ocap-based token design. When I was working
> on ERTP at Agoric, it felt like we were the only ones.
interested in that direction. :)
In fact, right after I told Mark, you mentioned some of the below to me,
and how Jessica's "swap" operation sounded just like "mint" and "burn"
combined, and I think you're right but I didn't cite it in my followup
here. I should have because I think you're onto something interesting!
> I'm interested in a comparison of the pebble-bank to the current ERTP
> implementation
> (https://github.com/Agoric/agoric-sdk/tree/master/packages/ERTP).
to me. But I have printed it out to read it more tonight.
> Mark, Christine indicated that you were surprised by synchronous
> operations not being required in Jessica's "burn and then mint" idea
> for transfers. Can you explain why?
asynchronous-only banks were desired previously but hard to do, and that
this was a strong justification for synchronous near-behavior in vats).
> This seems like it would work in the current ERTP. To give context for
> everyone else, in ERTP, a deposit works like this: a user has a Far
> payment object, which "holds" (is mapped to) a certain amount (either
> a number in the case of a fungible token, or an identity/description
> in the case of a non-fungible token). A user has a reference to a Far
> purse object, and asynchronously calls the deposit method on the
> purse, passing in the payment object. After some checks are done, the
> payment is synchronously destroyed (deleted from the map), and the
> purse balance is synchronously updated.
- E's mints had "purses" only, with intermediate purses used for
payments, but they're still just purses. (Purses as the ultimate
monetary abstraction.)
- Agoric's mints has "purses" and "payments" as fundamental structures.
There's a song and dance to move things between purse-land and
payment-land.
- Jessica's Pebble Bank has "payments" only, with "pouches" being
purse-like things that really just hold pebbles as a convenience, but
do nothing else interesting, and are not essential. (Payments as the
ultimate monetary abstraction.)
> It seems like the payment could be destroyed asynchronously, returning
> the amount of the payment, and then the amount from the payment could
> be asynchronously added to the purse balance. Rights conservation (the
> invariant that transfers maintain the same amount of tokens) wouldn't
> hold, but you might be able to fix that with a "pool" that holds
> amounts from destroyed payments that can be later added to
> purses. Once you account for the amounts in transit in the "pool",
> rights conservation does hold.
seems like a tricky thing to maintain without synchronous operations.
Note that our implementation does effectively the burn and the mint in
the same operation with "swap" (but using a single actor update but
which uses a local rich datastructure). But really one could view
"swap" as a capability enclosing "burn" and "mint". But if those are
done on a truly asynchronous datastructure as two operations, then there
will be a weird fluctuation of "total value" in the bank between burning
and minting time. My suspicion is that any attempt to fix this with
asynchronous things will be too complicated for anyone to reason about,
because the pools seem to have the same race condition problems, just
moved somewhere else. Asynchronous turtles all the way down, and that.
> What do you think?
I think it's time for me to finally read Agoric's ERTP Guide! Printed
out, reading tonight. :)
- Christine
Reply all
Reply to author
Forward
0 new messages