intro.org 65.3 KB
Newer Older
1 2
#+TITLE: Spritely Crystal

3
*Recommended reading:* [[https://gitlab.com/dustyweb/magenc/][Magenc]], [[https://gitlab.com/spritely/golem/blob/master/README.org][Golem]], [[https://people.csail.mit.edu/rivest/Sexp.txt][canonical s-expressions]]
4

5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
* Introduction

# - Introduction
#   - Motivation
#     - What Magenc gave us
#     - What Magenc lacked

In [[https://gitlab.com/dustyweb/magenc/][Magenc]], we saw that it was possible to have long-lived URI-type
identifiers that represented content where the content could be hosted
in multiple places, yet still only be readable by the intended
recipients.
In [[https://gitlab.com/spritely/golem/blob/master/README.org][Golem]], we saw Magenc applied to a federated social network using
ActivityPub, meaning that if a server went down, actively interested
parties can still refer to its content (which is a current major
problem with the existing federated social web).

#   - What Crystal is/adds
#   - But as we'll see, we can get ourselves into trouble
#     - Is this still worth it?
#     - It can still be a powerfully useful tool
#     - And as we will come to see, the problems that we will identify
#       here are already present in some of the systems we use, so it
#       is also worth understanding them.

Unfortunately, this fell short in one major way: there was no way to
/update/ said content.
What if you made a new version of your image?
What if your microblog post had a typo and you accidentally linked
to the wrong address for your party, but you'd like to update it?

In this document we'll be introducing a version of "Crystal URIs",
with this first implementation going under the "quartz:" URI scheme
(we might change some implementation details of how they work in
future revisions while retaining the same underlying semantics, at
which point we might change the URI scheme to a different crystal name
to reflect the change).
Like Magenc URIs, Crystal URIs do not live on "one" particular server;
if one node goes down, the content may continue to exist.
Also like Magenc URIs, nodes can cooperatively distribute data without
necessarily knowing its content; only entities which have been
explicitly given access can read the relevant content.
46 47 48 49 50
However, unlike Magenc URIs, Crystal URIs can be updated over time,
and "crystal registries" can track, verify, and report what new
revisions are available for a crystal, without having the authority to
read the contents of those revisions or write new revisions
themselves.
51 52
(Also like Magenc, Crystal URIs draw their ideas largely from
[[https://tahoe-lafs.org/][Tahoe-LAFS]] and to a lesser extent [[https://freenetproject.org/][Freenet]].)
53 54 55 56 57

Perhaps this strikes you as odd; here we are proposing adding the
ability for mutation to a generally immutable storage structure.
While we will indeed pull off that trick, we will discover that
in doing so, many of the problems of mutation come back.
58 59 60 61
Just like many real-world crystals, while they may appear solid,
they have the curious property that they can grow.
However this solidity does not indicate sturdiness; improper handling
can lead to their fracturing.
62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
Nonetheless, if we are aware of their limitations, Crystal URLs
still prove useful.
And as we explore the challenges of their design, we will discover
that many of these problems already exist in many of our decentralized
network designs and are emergent from a particular selection of
tradeoffs.
In understanding the possible tradeoffs that are made available to
us, we can better decide which ones are appropriate at which time.

* Crystals by example

# - A simple tutorial

#   Premise: Alyssa and Ben are playing a pen-and-paper RPG.
#   Ben is the GM, and Alyssa is playing an enchantress.
#   Alyssa is making updates, while Ben is checking for updates
#   now and then.

** Setting up

#   - Start up servers
#     - A content-addressed store
#     - Two crystal registries

86 87 88 89
First off, this example builds on the ideas presented in the [[https://gitlab.com/dustyweb/magenc/][Magenc]]
writeup; if you haven't read that yet, please do so then come back
here.

90 91
To follow along on your own computer, you should install Crystal like
so:
92

93
: $ raco pkg install crystal
94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135

Crystal's current implementation actually makes use of the same
content-addressed-storage (CAS) system that Magenc does... in fact, it
uses magenc under the hood both to store keys and data.
It will be easiest to understand this tutorial if we use the same
content-addressed storage for both "crystal registries" we'll be
setting up, so let's run one now:

: $ raco cas-server
: Your Web application is running at http://localhost:8000.
: Stop this program at any time to terminate the Web Server.

Now let's hook up two different crystal registries; both will use
the CAS server above for where they store and reference public keys.

In one terminal, run:

: $ raco crystal-server \
:        --port 8001 \
:        --key-store-url http://localhost:8000
: Your Web application is running at http://localhost:8001.
: Stop this program at any time to terminate the Web Server.

Then in another terminal, run:

: $ raco crystal-server \
:        --port 8002 \
:        --key-store-url http://localhost:8000

As a refresher, we're now hosting:
 - on port 8000: the content-addressed store on port 8000
 - on port 8001: a crystal registry (which talks to our CAS server)
 - on port 8002: another crystal registry (which talks to the same CAS
   server)

Of course, in a real world example, there is no reason that all three
servers would be served over a loopback address on the same machine;
for the sake of simplicity in demonstration we must use our
imaginations a bit.

Now that we're all set up, let's meet the characters of our story.

136 137
** An example scenario

138 139
*** Uploading a character sheet

140
#   - A description of a character in a game
141 142 143 144 145 146 147 148 149 150 151 152

Alyssa and Ben are friends who like to meet up to play a
fantasy pencil-and-paper RPG.
Ben performs the role of "game master"; he introduces and manages
story elements and sets up challenges.
Alyssa is a player; she describes what her character would like
to do in the world conveyed by the game master, and occasionally
rolls some dice to see whether or not her character succeeds or
fails in some scenario.
Alyssa is playing an enchantress; a lot of her character's actions
involve casting magic spells.

153
#   - Initial version
154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190

Alyssa comes home after one particularly exciting session and decides
that she'd really like to upload her character sheet so she can
reference it later or show it to interested friends.
She writes out a file for her character that looks like so:

#+BEGIN_SRC text
Name: Eliza Dragonscale
Description: Eliza has long dark hair and stunning purple eyes.
  A formidable caster, seeking her true self.
  
Class: Enchantress
Level: 15

HP:    75
MP:    108
Armor: 8

Strength:     8
Wits:         16
Dexterity:    12

Spells:
 - Ozocubu's Armor
 - Swiftness
 - Cone of confusion
 - Blade floor
 - See hidden
 - Dazzling Spray
#+END_SRC

She saves this file to =dragonscale.txt=.
However, before she can upload it to the store and register this
version, she must create a new "crystal".

#+BEGIN_SRC text
$ raco crystal new
191 192
== verify-only cap ==
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g
193
== read cap ==
194
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
195
== read-write cap ==
196
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rwk=MeMgmy_j0CI8jwT0EUX01bF7N0UAVSYwHhNQ67h2WAE
197 198
#+END_SRC

199 200 201 202
There are three kinds of Crystal URLs (also known as "Crystal
Capabilities", or "crystal caps", for short), here listed from least
to most powerful:

203
 - *verify-only caps* (aka /verify/ caps): Can verify that the metadata
204 205 206 207 208 209 210 211 212 213 214 215 216 217 218
   describing a revision is an authorized revision, even though it
   can't read the revision's contents or write new authorized
   revisions.
   This is the only crystal capability that the registry knows about;
   we never share read or write capabilities with registries.
 - *read caps* (aka /verify-read/ caps): Can verify that a revision is
   valid, and can read the associated contents, but can't write out
   new authorized revisions.  Can be transformed into a verify-only
   cap.
 - *read-write caps* (aka /verify-read-write/ caps): Can verify
   revisions, read the contents described by revisions, and can even
   write new authorized revisions.  Can be transformed into a read cap
   or verify-only cap.  Users holding a read-write cap should be very
   careful about handing these out and coordinating writes, as we will
   see.
219 220 221 222

Now Alyssa is ready to upload her file:

#+BEGIN_SRC text
223 224
$ cat dragonscale.txt | raco crystal write quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rwk=MeMgmy_j0CI8jwT0EUX01bF7N0UAVSYwHhNQ67h2WAE
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g/0/vKjw-WlG-759CxsCa9CI6oCe8a2JFsrYfFDssj51qqo?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
225 226 227 228 229
#+END_SRC

She verifies that she can read the file, both with the read-write cap:

#+BEGIN_SRC text
230
$ raco crystal read quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rwk=MeMgmy_j0CI8jwT0EUX01bF7N0UAVSYwHhNQ67h2WAE
231 232 233 234 235 236 237 238 239
Name: Eliza Dragonscale
Description: Eliza has long dark hair and stunning purple eyes.
  A formidable caster, seeking her true self.
[...]
#+END_SRC

And just as well with the read cap:

#+BEGIN_SRC text
240
$ raco crystal read quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256
Name: Eliza Dragonscale
Description: Eliza has long dark hair and stunning purple eyes.
  A formidable caster, seeking her true self.
[...]
#+END_SRC

Alyssa decides she would like Ben to be able to see her character as
she updates it.
She opens up an instant message session with him.

#+BEGIN_SRC text
<alyssa> hey ben, remember that crystal thing I was talking about?
<alyssa> did you install it?
<ben> yes, why?
<alyssa> I want to show you something
<alyssa> try entering:
257
<alyssa>   raco crystal read quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
258 259 260 261 262 263 264 265 266 267 268
<alyssa> in your terminal, that is
<ben> hold on, trying
<ben> wow cool!  It's your character sheet
<alyssa> :D
<alyssa> this way I can update it, and you can see it
<ben> awesome.  are we still on for another session next week btw?
<alyssa> yes, see you then.
#+END_SRC

*** Updating the character sheet

269 270
#   - Update two: switches gender

271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312
The next week, Alyssa and Ben have another exciting session.
Alyssa's character Eliza raids a dungeon, fighting off beasts and
collecting loot.
Eliza gains a level, and amongst the loot finds a "potion of change
gender".
Alyssa and Ben both think that this may be an interesting way to
resolve the "seeking her true self" part of Eliza's storyline, and
so Alyssa's character drinks the potion.
In resolving that plot point, Alyssa also decides to change her
character's name to "Elzan".

Upon returning home, Alyssa decides to update her uploaded character
sheet to reflect the changes.
She opens =dragonscale.txt= and adjusts it to look like the following:

#+BEGIN_SRC text
Name: Elzan Dragonscale
Description: Elzan has long dark hair and stunning purple eyes.
  A formidable caster, all the more powerful for having found
  his true self.
  
Class: Enchanter
Level: 16

HP:    80
MP:    115
Armor: 8

Strength:     8
Wits:         17
Dexterity:    13

Spells:
 - Ozocubu's Armor
 - Swiftness
 - Cone of confusion
 - Blade floor
 - See hidden
 - Dazzling Spray
#+END_SRC

#+BEGIN_SRC text
313 314
$ cat dragonscale.txt | raco crystal write quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rwk=MeMgmy_j0CI8jwT0EUX01bF7N0UAVSYwHhNQ67h2WAE
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g/1/bNIYWl3VtH5e3m0Znp80fU5qtH6IvqpGl3GlyXmNoD0?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334
#+END_SRC

Alyssa pings Ben over instant message:

#+BEGIN_SRC text
<alyssa> hey Ben, I updated my character sheet...
<alyssa> try running that "crystal read" command I gave you last week again
<alyssa> does it update?
<ben> hold on, testing...
<ben> cool, I got the new version.
<ben> nice, I see you updated your description and leveled up
<alyssa> yea :D  increase in wits/dexterity too ;)
#+END_SRC

Alyssa wonders... what happened to the old version?
Was it still around?
She discovers the "crystal known-history" subcommand and decides
to give it a whirl:

#+BEGIN_SRC text
335
$ raco crystal known-history quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
336
== 0 ==
337
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g/0/vKjw-WlG-759CxsCa9CI6oCe8a2JFsrYfFDssj51qqo?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
338
== 1 ==
339
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g/1/bNIYWl3VtH5e3m0Znp80fU5qtH6IvqpGl3GlyXmNoD0?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
340 341 342 343 344 345 346 347 348 349
#+END_SRC

Alyssa suddenly recognizes that these are the same URLs that were spit out
after each "crystal write" respectively.
Could these be referencing /specific/ revision of the crystal URI?
She decides to give it a try.

First she checks the first one:

#+BEGIN_SRC text
350
$ raco crystal read quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g/0/vKjw-WlG-759CxsCa9CI6oCe8a2JFsrYfFDssj51qqo?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
351 352 353 354 355 356 357 358 359 360
Name: Eliza Dragonscale
Description: Eliza has long dark hair and stunning purple eyes.
  A formidable caster, seeking her true self.
[...]
#+END_SRC

That looks like the first version alright.
And the second one?

#+BEGIN_SRC text
361
$ raco crystal read quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g/1/bNIYWl3VtH5e3m0Znp80fU5qtH6IvqpGl3GlyXmNoD0?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393
Name: Elzan Dragonscale
Description: Elzan has long dark hair and stunning purple eyes.
  A formidable caster, all the more powerful for having found
  his true self.
[...]
#+END_SRC

Yup, that looks like the second version.

Alyssa ponders this for a minute.
As far as her understanding of how Crystal works so far, she knows that
once a revision is published, there is not necessarily any "central"
source for that information.
The advantages of being able to continue to reference information you
care about, to store it anywhere while retaining privacy, and to be
able to update that content while retaining the same core identifier
seem clear.
However, Alyssa has also done enough research to know and understand
that from a mathematical perspective, once an entity gets ahold of
some information, it is impossible to prevent them from retaining or
distributing that information without either confinement, surveilance
combined with punishment, compliance in response to societal requests,
or compliance in the face of societal pressure.
Due to Crystal's design, once someone has a particular revision, they
can always refer to it and verify that it was an update produced by
someone with access to the crystal's read-write capability.
Alyssa considers that with her character sheet, she doesn't particularly
mind if someone can see or confirm an older revision, but that there
may be times when the ability to reference an older version of something
might be awkward or uncomfortable... perhaps in such a case, using an
identifier which can be verifiably updated over time is an altogether
difficult fit.
394
But this also seems like a difficult thing to avoid or even change the
395 396 397 398 399 400 401 402
design for, since in such cases probably someone would still want to
be able to update their content while still retaining their original
identifier and everything that points to it.
Tough stuff.

But Alyssa decides that that's enough philosophizing about the nature
of identity for this particular moment.

403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536
*** Syncing registries

#   - Ben says he'd like to see, but is using a different a phone app
#     that uses a different crystal server.  Alyssa thinks it's cool
#     so she adds it to her phone too.
#   - Now we sync servers, and Ben can see

Before Ben shows up to the next gaming session, he decides it would be
handy if he could reference Alyssa's character sheet on the go.
He finds an application for his phone called "Crystalizr" which claims
to provide a simple mobile interface for viewing and editing simple
documents stored in Crystal.

Ben copies over the read cap that alyssa sent him and tries to pull up
the document.
But Ben is confused... Crystalizr says that no revisions are found.
Ben opens up a chat session with Alyssa to try to figure out what's
going on.

#+BEGIN_SRC text
<ben> alyssa hellllllp
<alyssa> what's up ben?
<ben> so I found this phone app called Crystalizr so I could check out
      your profile on the go
<alyssa> oh is that a crystal client for the phone?  I should install it
<ben> yeah I mean, it looks cool, but I tried putting in the read cap
      you gave me and nothing comes up :\
<alyssa> huh, that's strange...
<alyssa> hold on, I have a guess as to what this is
<alyssa> is there a settings menu?  what "registry" server does it say
         it's talking to?
#+END_SRC

Ben takes a look, and confirms with Alyssa that the default registry
on the Crystalizr application is different than the default for the
desktop application.

In fact, if you've been following along at the console, you can see
this issue for yourself.
The default crystal registry for the crystal command line client is
=http://localhost:8001=, but we're also running another registry at
=http://localhost:8002=.
Thus all the writes we've made so far are to the former rather than
the latter, and we can see the difference:

#+BEGIN_SRC text
# first registry
$ raco crystal read \
       --registry http://localhost:8001 \
       quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
Name: Elzan Dragonscale
Description: Elzan has long dark hair and stunning purple eyes.
  A formidable caster, all the more powerful for having found
  his true self.
[...]

# second registry
$ raco crystal read \
       --registry http://localhost:8002 \
       quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
ERROR: No revision found.
#+END_SRC

Seeing this, Ben replies to Alyssa over chat.

#+BEGIN_SRC text
<ben> okay, yeah that was the problem.
<ben> but I've been looking at the docs, and I think there's a way
      to "synchronize" the servers.
<alyssa> ooh
#+END_SRC

Ben runs a command to sync the servers.
We can do something similar on our end:

#+BEGIN_SRC text
$ raco crystal sync \
       --registry http://localhost:8001 \
       --registry http://localhost:8002 \
       quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
Added /1/bNIYWl3VtH5e3m0Znp80fU5qtH6IvqpGl3GlyXmNoD0 to http://localhost:8002
Added /0/vKjw-WlG-759CxsCa9CI6oCe8a2JFsrYfFDssj51qqo to http://localhost:8002
#+END_SRC

The client, recognizing that =http://localhost:8001= had revisions
that =http://localhost:8002= did not, added them to the latter.

Now Ben tries pulling it up on his mobile client.
Yup, it works!
Ben excitedly returns to his chat with Alyssa.

#+BEGIN_SRC text
<ben> so it turns out all I had to do was sync the contents between
      servers.  seems to work!
<alyssa> cool!
<alyssa> that has me thinking... currently we're using crystal for our
         pen & paper RPG, but what about that distributed online RPG
         we've been talking about?
<ben> so like... a person's character sheet / profile could live on
      many servers?
<alyssa> yes, exactly
<ben> manually syncing servers seems hard
<alyssa> but if we built it into the protocol, this could happen
         automatically, right?
<alyssa> if a server sees an update, it can also publish that update
         to its friends... etc, etc
<ben> that seems true...
<ben> but I wonder... would it run into the same problem we hit today?
<alyssa> of things going out of date?
<alyssa> I suppose even with the "automatic sharing" of updates,
         there are timing updates and some updates might just not make
         it to certain servers
<ben> right
<alyssa> maybe slightly-out-of-date-profiles isn't the biggest problem
         in this particular game design.  but let's keep it in mind.
<ben> hey, what about our own rpg?  the one we're actually playing
      next week?  are we still on for that?
<alyssa> yep... see you then!
#+END_SRC

*** Conflict!

#   - Update three: adds her spells
#     - Initially, adds from her computer
#     - But while she's out and about, Ben says he hasn't seen the update
#     - Alyssa is confused, but updates the character sheet from her phone
#       to the best of her ability.
#     - accidentally done from two separate devices
#   - Now we sync servers
#   - Uhoh, there's a conflict!
#   - Update four: grows wings
#   - No more conflict in "latest version"
#   - But the conflict is still there, in the past!

537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801
Another week, another great gaming session.
Alyssa heads home and updates her character sheet again...
this time Elzan leveled up and learned some new magic tricks.

#+BEGIN_SRC text
Name: Elzan Dragonscale
Description: Elzan has long dark hair and stunning purple eyes.
  A formidable caster, all the more powerful for having found
  his true self.
  
Class: Enchanter
Level: 17

HP:    80
MP:    115
Armor: 8

Strength:     8
Wits:         17
Dexterity:    13

Spells:
 - Ozocubu's Armor
 - Swiftness
 - Cone of confusion
 - Blade floor
 - See hidden
 - Dazzling Spray
 - Force Lance
#+END_SRC

She saves the file and re-uploads it:

#+BEGIN_SRC text
$ cat dragonscale.txt | raco crystal write quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rwk=MeMgmy_j0CI8jwT0EUX01bF7N0UAVSYwHhNQ67h2WAE
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g/2/k5SJJMP0GBJS6fclkN99rvLhmSmefNHQv-CFa9VQlX8?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
#+END_SRC

Later, Alyssa is out running some errands when she gets a message from
Ben on her phone:

#+BEGIN_SRC text
<ben> hey, I thought you were gonna update your character sheet
<alyssa> I *did* update it
<ben> I just checked on my phone, it doesn't look updated
<alyssa> hm, let me see
#+END_SRC

Alyssa opens Crystalizr on her phone.
Indeed, Elzan looks out of date

#+BEGIN_SRC text
<alyssa> that's strange, I could have sworn I updated it, but
         I was in a hurry, maybe I forgot to upload it
<alyssa> I am out and about, I'll have to update it from my
         phone. I am out of chickpeas, chickpea emergency
#+END_SRC

Alyssa tosses a can of chickpeas into her cart and updates
the character sheet from her phone's editor.

#+BEGIN_SRC text
Name: Elzan Dragonscale
Description: Elzan has long dark hair and stunning purple eyes.
  A formidable caster, all the more powerful for having found
  his true self.
  
Class: Enchanter
Level: 17

HP:    80
MP:    115
Armor: 8

Strength:     8
Wits:         17
Dexterity:    13

Spells:
 - Ozocubu's Armor
 - Swiftness
 - Cone of confusion
 - Blade floor
 - See hidden
 - Dazzling Spray
 - Fulminant Prism
#+END_SRC

Alyssa saves and uploads the update from the Crystalizr interface.
We can simulate her update by running the following:

#+BEGIN_SRC text
$ cat dragonscale.txt | raco crystal write --registry http://127.0.0.1:8002 quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rwk=MeMgmy_j0CI8jwT0EUX01bF7N0UAVSYwHhNQ67h2WAE
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g/2/GDVYQMSkwnPeh6cbiBPEN82SuHBU6n83xZVFSP6FKvM?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
#+END_SRC

She messages Ben:

#+BEGIN_SRC text
<alyssa> do you see it now
<ben> hold on, refreshing...
<ben> got it!  thanks, level 17 and everything
<ben> oh uh you forgot a spell; you also learned Force Lance
<alyssa> what I swear I added that
<alyssa> I don't have time for this, I'll look when I get home
<ben> ok
#+END_SRC

Alyssa finishes her errands and gets home.
She runs =crystal read= on her desktop and sees:

#+BEGIN_SRC text
[...]
Spells:
 - Ozocubu's Armor
 - Swiftness
 - Cone of confusion
 - Blade floor
 - See hidden
 - Dazzling Spray
 - Force Lance
#+END_SRC

Huh?  Then she looks at Crystalizr.  It says:

#+BEGIN_SRC text
[...]
Spells:
 - Ozocubu's Armor
 - Swiftness
 - Cone of confusion
 - Blade floor
 - See hidden
 - Dazzling Spray
 - Fulminant Prism
#+END_SRC

Suddenly Alyssa remembers... her desktop and her phone clients were
connecting to different registries, and no sync happened, so neither
one saw the update from the other!
Alyssa runs =crystal sync= out of frustration:

#+BEGIN_SRC text
$ raco crystal sync --registry http://localhost:8001 --registry http://localhost:8002 quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
Added /2/GDVYQMSkwnPeh6cbiBPEN82SuHBU6n83xZVFSP6FKvM to http://localhost:8001
Added /2/k5SJJMP0GBJS6fclkN99rvLhmSmefNHQv-CFa9VQlX8 to http://localhost:8002
#+END_SRC

Wait a minute... did that mean that both servers now have two
"revision 2" versions?

#+BEGIN_SRC text
$ raco crystal known-history quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs 
== 0 ==
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g/0/vKjw-WlG-759CxsCa9CI6oCe8a2JFsrYfFDssj51qqo?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
== 1 ==
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g/1/bNIYWl3VtH5e3m0Znp80fU5qtH6IvqpGl3GlyXmNoD0?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
== 2 ==
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g/2/k5SJJMP0GBJS6fclkN99rvLhmSmefNHQv-CFa9VQlX8?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g/2/GDVYQMSkwnPeh6cbiBPEN82SuHBU6n83xZVFSP6FKvM?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
#+END_SRC

Uhoh, it sure looked like it.
What would happen if Alyssa tried doing "crystal read"?

#+BEGIN_SRC text
$ raco crystal read quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
ERROR: Version conflict!  I don't know what to pick?
#+END_SRC

Alyss panics and opens up her chat with Ben:

#+BEGIN_SRC text
<alyssa> ben!!! ben I broke it
<ben> what huh?
<alyssa> open up my character sheet
<ben> ok, hold on
<ben> uhoh!  version conflict, huh?
<alyssa> yeah D:
<ben> but... the data isn't gone, right?
<ben> it looks like I can specify a specific revision, it just doesn't
      know which one is the default new one
<alyssa> oh, let me try
#+END_SRC

#+BEGIN_SRC text
$ raco crystal read quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g/2/k5SJJMP0GBJS6fclkN99rvLhmSmefNHQv-CFa9VQlX8?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
[...]
 - See hidden
 - Dazzling Spray
 - Force Lance

$ raco crystal read quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g/2/GDVYQMSkwnPeh6cbiBPEN82SuHBU6n83xZVFSP6FKvM?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
[...]
 - See hidden
 - Dazzling Spray
 - Fulminant Prism
#+END_SRC

Alyssa decides to try fixing the conflict herself by uploading a new
version.
She updates dragonscale.txt to include both spells, then syncs
the servers, and =crystal read= works again without specifying a
particular revision:

#+BEGIN_SRC text
$ cat dragonscale.txt | raco crystal write quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rwk=MeMgmy_j0CI8jwT0EUX01bF7N0UAVSYwHhNQ67h2WAE
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g/3/CzE7ltqKMjxpQr8NRh_raQtHoNDg-NzclBjrxUDqIlY?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs

$ raco crystal sync --registry http://localhost:8001 --registry http://localhost:8002 quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
Added /3/CzE7ltqKMjxpQr8NRh_raQtHoNDg-NzclBjrxUDqIlY to http://localhost:8002

$ raco crystal read quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
Name: Elzan Dragonscale
Description: Elzan has long dark hair and stunning purple eyes.
  A formidable caster, all the more powerful for having found
  his true self.
  
Class: Enchanter
Level: 17

HP:    80
MP:    115
Armor: 8

Strength:     8
Wits:         17
Dexterity:    13

Spells:
 - Ozocubu's Armor
 - Swiftness
 - Cone of confusion
 - Blade floor
 - See hidden
 - Dazzling Spray
 - Force Lance
 - Fulminant Prism
#+END_SRC

Alyssa breathes a sigh of relief.

#+BEGIN_SRC text
<alyssa> okay, I fixed it.  I just pushed a new version.
<ben> yep, seems fine on my end now.
<alyssa> but that makes me wonder, would this be a problem in the
         distributed rpg?
<ben> maybe... it seems like the data doesn't go away, but it's not
      clear "which version" is the newest version
<alyssa> right
<ben> I mean, maybe this isn't so bad
<ben> we could maybe make one-off decisions when this happens?
<alyssa> like, maybe just select one and show a warning/selection to
         show multiple versions are available?
<ben> yeah exactly
<alyssa> that's ok for some things maybe, but it's not a very general
         solution.
<ben> maybe we could roll back to the "last known good" revision?
<alyssa> what if none of them are known to be good? :P
<ben> oh, I don't know.
<ben> this seems like a pretty general problem though... hold on, I
      seem to remember there's a bunch of literature out there on
      this...
#+END_SRC

802 803 804 805
* More on conflicts and the CAP theorem

# - On conflicts
#   - Tahoe-LAFS documentation comment on the write key
806 807 808 809

As said earlier, much of Crystal's design (and Magenc's) come from
the [[https://tahoe-lafs.org/][Tahoe-LAFS]] project.
[[https://tahoe-lafs.readthedocs.io/][Tahoe's documentation]] has some wise words to say on the matter
810
of the "mulit-writer problem" in a section tellingly named
811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872
[[https://tahoe-lafs.readthedocs.io/en/latest/specifications/mutable.html#the-prime-coordination-directive-don-t-do-that][The Prime Coordination Directive: "Don't Do That"]]:

#+BEGIN_QUOTE
The current rule for applications which run on top of Tahoe is “do not
perform simultaneous uncoordinated writes”.
That means you need non-tahoe means to make sure that two parties are
not trying to modify the same mutable slot at the same time.
For example:

 - Don’t give the read-write URI to anyone else.  Dirnodes in a
   private directory generally satisfy this case, as long as you don’t
   use two clients on the same account at the same time.
 - If you give a read-write URI to someone else, stop using it
   yourself. An inbox would be a good example of this.
 - If you give a read-write URI to someone else, call them on the
   phone before you write into it.
 - Build an automated mechanism to have your agents coordinate
   writes. For example, we expect a future release to include a FURL
   for a “coordination server” in the dirnodes. The rule can be that
   you must contact the coordination server and obtain a lock/lease on
   the file before you’re allowed to modify it.

If you do not follow this rule, Bad Things will happen. The worst-case
Bad Thing is that the entire file will be lost.
A less-bad Bad Thing is that one or more of the simultaneous writers
will lose their changes.
An observer of the file may not see monotonically-increasing changes
to the file, i.e. they may see version 1, then version 2, then 3, then
2 again.
#+END_QUOTE

Alyssa and Ben discovered the consequences of violating The Prime
Coordination Directive when Alyssa began writing updates from two
different devices.

# TODO: Am I using this term right?  I think so based on:
#   https://tahoe-lafs.org/pipermail/tahoe-dev/2010-October/005352.html

We could also be vulnerable to "rollback attacks".
Consider if Alyssa and Ben were using some social network software
where users can publish a public encryption key on their profile that
users can make use of to send a confidential message.
Alyssa wants to update her key because either the previous key's
cipher has found to have vulnerabilities or because she believes
it may have been compromised, so she generates a new key pair
and updates her profile.
But if Mallet is in charge of the crystal registry that Ben is using,
Mallet could choose to not share the newer version in favor of
the version that favors Mallet; if Mallet has a way to subvert
Alyssa's older key and a way to monitor Ben and Alyssa's communication
channel, then Mallet might be able to intercept Ben's communications.
Of course, if Ben talked to multiple registries, then Ben increases
his chance of finding the newest profile, but if Mallet is able to
control all registries that Ben has access to, then Mallet can control
which registry Ben will see.
(Tahoe-LAFS also has this problem but less so since it is designed
less to be on an open / public system than on a specific and
intentional quorum of servers.
This also leads Tahoe to be able to provide stronger assurances that
data will remain available than Magenc and Crystal can provide on their
own.)

873 874 875 876
#   - This might seem like Crystal is a hopeless design.
#     But in fact, the tradeoffs here exist in many systems.
#   - ActivityPub has chosen Available and Partition tolerant, and also
#     *already* has these problems, as we will see in Crystal Golem.
877 878 879 880 881 882 883 884 885 886 887

This may lead us to wonder... is Crystal a bad or hopeless design?  In
fact, many existing systems that we use today already have made
similar tradeoffs:

 - [[https://git-scm.com/][Git]] and similar revision control systems are designed to allow for
   branching, but merging two desirable branches again often requires
   expert involvement.
   In general, while git is itself decentralized, semi-centralization
   and server liveness is relied on to establish what is considered
   authoritative content.
888 889 890
   This isn't a perfect approach either; servers can go down (or are
   stuck footing the bandwidth bill for popular content) and "rebases"
   can cause havoc.
891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970
 - At [[https://github.com/ssbc/ssb-db/issues/157][the time of writing]], if conflicting writes are made in
   [[https://www.scuttlebutt.nz/][Secure Scuttlebutt]], that feed is considered "forked" and is
   generally considered corrupt.
   Just as happened with Alyssa, users tend to run into trouble
   if they try to update their feeds from multiple devices.
 - In the [[https://www.w3.org/TR/activitypub/][ActivityPub]] federation protocol, it is possible to deliver
   different information to different servers resulting in confusion.
   Some nodes may go down and might not receive updates or deletions.
   Server URLs can be considered the "canonical" source of truth, but
   servers can go down or tell conflicting information to different
   authenticated parties.

And so on and so on.
Are these systems simply badly designed?

#   - CAP theorem

To better understand what's happening here, we should turn to the
[[https://en.wikipedia.org/wiki/CAP_theorem][CAP theorem]].
To quote Wikipedia (particularly [[https://en.wikipedia.org/w/index.php?title=CAP_theorem&oldid=887835667][this revision]]):

#+BEGIN_QUOTE
The CAP theorem, also named Brewer's theorem after computer scientist
Eric Brewer, states that it is impossible for a distributed data store
to simultaneously provide more than two out of the following three
guarantees:

 - *Consistency:* Every read receives the most recent write or an
   error
 - *Availability:* Every request receives a (non-error) response –
   without the guarantee that it contains the most recent write
 - *Partition tolerance:* The system continues to operate despite an
   arbitrary number of messages being dropped (or delayed) by the
   network between nodes
#+END_QUOTE

The CAP theorem is a trilemma: we can think of it as a triangle
where each point represents a possible choice, but where we can only
choose two of the three points (thus, only one side/edge).
Realistically however, any distributed system has to account for
"partition tolerance" because nodes will always go down and network 
problems are just a fact of life.
Thus the real choices we have are between Consistency and Partition
tolerance (CP) or Availability and Partition tolerance (AP).

The rollout of Spritely Crystal we have described so far follows an AP
scheme.
Even if servers go down or some nodes have failed to communicate with
each other (or never even had a path to communicate), you can always
reach out to nodes that you do know or are available to you to get
some information, even if it might be out of date.
This can sometimes also lead to conflicts.

However, we /could/ consider a CP based rollout.
One simple example we could imagine would be that we design a system
where we know all nodes participating the network and consider them
all to be trusted, and in the event of a write, we have to wait for
all nodes to sign off on their acknowledgement and record of the write
before the transaction completes, and have all servers agree to consider
the write completed at the exact same microsecond.
Then all servers can serve the new write.

Of course, this doesn't match our needs.
The proposed design requires that all servers be trustworthy enough to
not cause trouble and sign off on two different writes.
There are also potential deadlock challenges if multiple writes are
attempted.
We could require the reverse, that instead instead of a write, a read
requires that all servers be online and available, but this has the
same problems.
Consider what would happen if we tried to deploy email over such a
system... it would quickly ground to a halt.
So for our needs, it seems that we must choose AP.

But it is possible that even if we cannot be consistent, available,
and partition tolerant all at once, perhaps we could at least solve
that tricky problem of what happens once we hit a merge conflict.
Maybe we could decide that only one write wins, and get back
linear history?

971
#   - "Eventually consistent" systems exist, but are very expensive.
972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998

There is another approach, where our systems are available and
partition-tolerant by default, but where they become "eventually
consistent".
Famously, some blockchains like Bitcoin or Etherium are required by
their design to have a solution to this problem; they must be
available and partition tolerant, but there is something called the
"double spending problem" which they absolutely must avoid according
to their design.
It is bad enough that Alyssa could write out two conflicting character
profiles, but the world can go on without too much damage to it.
However, if Mallet were to tell one group of people that they were to
give money to say George and tell another group of people that they were
to give money to Harriet and both groups moved forward under those
assumptions (especially if that money was then to pass hands from Harriet
or George to someone else), that would be a very problematic deceit!
The way such systems get around it is by "linearizing" history by voting
on it: if enough of the network agrees that Mallet gave the money to
Harriet, that keeps Mallet from being also able to say that they gave
the money to George.
Unfortunately, such systems are extremely costly to implement, result
in a forever-growing set of history, and are themselves vulnerable to
attacks where enough of the network is controlled by a malicious entity
or entities where they conspire to "rewrite history" by overwhelming
the network with enough information to claim a different outcome of a
previous election.

999 1000 1001 1002
#   - Ultimately, you will always have tradeoffs in a distributed
#     system; the key is realizing which tradeoffs you have chosen
#     where.

1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013
It may be that for some systems, the risk of inconsistency simply
isn't too serious.
For example if Mallet is using an ActivityPub powered social network
and sends an Update activity to Alyssa saying that the party's address
has changed to one place while sending Bob an Update saying that it
has changed to something else, Mallet might ruin someone's night, but
likely not much else (and Bob and Alyssa might simply respond by
cutting Mallet out of their lives).
For systems such as distributed social networks, the cost of eventual
consistency is simply too high, but for other systems, the cost might
be the only way forward while preserving core design decisions.
1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046

However, we can improve our handling of the multi-writer problem in
the case of avoiding /accidental/ conflicts.
When distributing a read-write cap, we could simultaneously deliver
a coordination endpoint.

One simple way to build this coordination endpoint is to have it be a
special one-off crystal registry designed only for this crystal, where
initial writes are intended to occur.
When a revision is being pushed up to this registry, if there is
already a known revision with that revision number, then the server
rejects it.
The uploader can then compare and manually merge the two revisions,
delete the local conflicting revision, and upload a revision merging
the two with a new revision number.
This is a special case registry only for the writers to coordinate
with; in general, if there are conflicts, the network should know
about it, otherwise participants may be receiving conflicting
information and would be unaware of it.
However, since this is a one-off registry only designed to coordinate
between writers of that crystal, this is acceptable.
Unfortunately, this design does have the downside that it does not
easily allow participants to work when connectivity to the coordination
endpoint cannot be established.

Another way to handle things is to expect and anticipate conflicts
but simply make aware all participants that such conflicts occur.
This time, the coordination registry can also be subscribed to; upon
conflict, a message can be sent out to all subscribed writers that a
conflict has occurred.
This permits for offline work, but it does not prevent conflicts from
propagating to the network.

1047
* How it works
1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059

# (We will see how these work later, but it is already easy to observe
# that the URIs are the same with the exception that the former has a
# value under the =rok= (read only key) query parameter while the latter
# has a different value under the =rwk= (read-write key).)

# Technically, there is a the "read cap" is more accurately called a
# "verify-read cap" and the "read-write cap" is more accurately called a
# "verify-read-write cap".
# If we remove the =rok= or =rwk= query parameters we get the
# "verify-only cap".

1060 1061 1062 1063 1064 1065 1066 1067 1068 1069
When running the command =crystal known-history=, Alyssa's client
talked to a "registry" to find out what revisions of a crystal are
known to be available.
The registry doesn't store the actual data of each revision, just the
metadata describing information about the revision.
The registry does know what authorized revisions have been reported as
being available for crystals that it knows about, and yet it doesn't
actually know what the contents of the revision data actually are.
How is this achieved?

1070
** Understanding crystal caps and their keys
1071 1072 1073 1074 1075

Recall when Alyssa ran "crystal new" initially:

#+BEGIN_SRC text
$ raco crystal new
1076 1077
== verify-only cap ==
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g
1078
== read cap ==
1079
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
1080
== read-write cap ==
1081
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rwk=MeMgmy_j0CI8jwT0EUX01bF7N0UAVSYwHhNQ67h2WAE
1082 1083
#+END_SRC

1084 1085 1086
The read cap has the parameter "rok" which stands for "read-only key",
whereas the read-write cap has "rwk" which stands for "read-write
key".
1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118
The verify-only cap is like both of the above, except minus any query parameter
at all.

Stucturally, the verify-only cap looks like:

: quartz:<keydata-hash>.<keydata-decryption-key>

The read cap looks like:

: quartz:<keydata-hash>.<keydata-decryption-key>?rok=<read-key>

And the read-write cap looks like:

: quartz:<keydata-hash>.<keydata-decryption-key>?rwk=<write-decryption-key>

The main idea here is more or less that the signing key (aka public
key) /is/ the primary "identifier" of a file.
However, embedding the full key would be too large for a URI here,
so we upload it (along with some additional metadata) to the encrypted
content-addressed store.
That's right... we're storing the signing key in a magenc content-addressed
store!
So this crystal URI structure:

: quartz:<keydata-hash>.<keydata-decryption-key>

Becomes this magenc URI:

: magnet:?xt=urn:sha256d:<keydata-hash>&ek=<keydata-decryption-key>&es=aes-ctr-sha256

Knowing that, we can now transform Alyssa's crystal URI from:

1119
: quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g
1120 1121 1122

to:

1123
: magnet:?xt=urn:sha256d:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk&ek=6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g&es=aes-ctr-sha256
1124 1125 1126 1127 1128

We could try fetching that data using the command-line client, and we'd
end up with something like the following:

#+BEGIN_SRC text
1129
$ raco magenc --get "magnet:?xt=urn:sha256d:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk&ek=6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g&es=aes-ctr-sha256" http://localhost:8000
1130 1131 1132 1133 1134
(7:keydata(16:rsa-pcks1-sha256(1:e<...a bunch of binary garbage...>
#+END_SRC

Hm, we definitely hit something, and "keydata" is very promising!
Unfortunately it's not so easy to look at on the terminal; the
1135 1136 1137 1138
retrieved data is in the "canonical" (or "transport")
[[https://people.csail.mit.edu/rivest/Sexp.txt][canonical s-expression]] (csexp) format, which is very efficient at
containing binary data, but binary data isn't always so easy to look
at.
1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157

Sound familiar?
That's the same serialization format that [[https://gitlab.com/dustyweb/magenc/blob/master/magenc/scribblings/intro.org][Magenc used]]!
Here's what the keydata structure looks like as a template:

#+BEGIN_SRC scheme
(keydata <verify-key> <encrypted-write-key>)
#+END_SRC

The verify-key is also a csexp:

#+BEGIN_SRC scheme
(rsa-pcks1-sha256
 (e <e-value>)
 (n <n-value>))
#+END_SRC

So altogether that looks like:

1158 1159
# TODO: Actually show this using the advanced csexp format

1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187
#+BEGIN_SRC scheme
(keydata (rsa-pcks1-sha256
          (e <e-value>)
          (n <n-value>))
         <encrypted-write-key>)
#+END_SRC

Where e-value and n-value are also binary.
It's not important that you understand what the e-value and n-value
mean, just that this is the underlying verification "public" key
information.[fn:spki-sdsi]

But what's up with the encrypted-write-key?
On its own, it just looks like binary data because (as you might
have guessed), it's encrypted.
How do we decrypt it?
Well, if you recall, if you're in possession of the read-write-key,
it looks something like this:

: quartz:<keydata-hash>.<keydata-decryption-key>?rwk=<write-decryption-key>

If we decrypt the =encrypted-write-key= with the =write-decryption-key=
using =aes-ctr= and an all-zero initialization vector (the =write-decryption-key=
isn't used for anything else, so not having a real IV isn't a big deal),
then we can decrypt the write-key contents.

Our read-write-key looked like the following:

1188
: quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rwk=MeMgmy_j0CI8jwT0EUX01bF7N0UAVSYwHhNQ67h2WAE
1189

1190
Which means that =MeMgmy_j0CI8jwT0EUX01bF7N0UAVSYwHhNQ67h2WAE= is the
1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223
base64 encoded =write-decryption-key=.
Using that information, we can decrypt the write-key, and we'll find
that we get something that matches the following template:

#+BEGIN_SRC scheme
(rsa-pcks1-sha256
 (d <d-value>)
 (dp <dp-value>)
 (dq <dq-value>)
 (e <e-value>)
 (n <n-value>)
 (p <p-value>)
 (q <q-value>)
 (qInv <qInv-value>))
#+END_SRC

This is the csexp representation of the writing "private" key.
Even though that data was sitting there alongside the "verification"
key information all along, it's now understandable how only someone
with the read-write cap can retrieve the write-key.[fn:do-we-need-put-the-key-in-magenc]

The read cap has the read-only key directly on the URI:

: quartz:<keydata-hash>.<keydata-decryption-key>?rok=<read-key>

But we said that one can "derive" the appropriate read cap using the
read-write cap.
How is that done?
Quite simply, the decrypted but serialized private-key csexp is hashed
with sha256 to /generate/ the read key.
Thus, once one has the read-write cap, the read key can always be
derived, but not vice versa.

1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253
One more thing... if we run =crystal known-history= we can see some
extra information added to the path:

#+BEGIN_SRC text
$ raco crystal known-history quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g
== 0 ==
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g/0/vKjw-WlG-759CxsCa9CI6oCe8a2JFsrYfFDssj51qqo
== 1 ==
quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g/1/bNIYWl3VtH5e3m0Znp80fU5qtH6IvqpGl3GlyXmNoD0
#+END_SRC

That's because Crystal URIs can specify extra information about which
revision they represent, like so:

: <base-crystal-url>/<rev-num>
: <base-crystal-url>/<rev-num>/<rev-sig-hash>

So, if we add to the path:

: /0

We'll be saying we're referring data under the 0th revision number of
this crystal.
And if we add:

: /0/vKjw-WlG-759CxsCa9CI6oCe8a2JFsrYfFDssj51qqo

We'll be specifying more precisely the 0th revision that has the exact
rev-sig hash of =vKjw-WlG-759CxsCa9CI6oCe8a2JFsrYfFDssj51qqo=.

1254 1255 1256 1257
[fn:spki-sdsi] In fact, canonical s-expressions were originally
  designed /for/ a cryptographic key management and certificate system
  called [[http://world.std.com/~cme/html/spki.html][SPKI/SDSI]] (pronounced "spooky"/"sudsy").
  According to conversations with Christopher Allen, one of the lead
1258 1259 1260 1261
  authors of the SSL/TLS specification, many of the designers hoped to
  use SPKI/SDSI, but unfortunately prominent implementations resulted
  in the rollout of the X.509/ASN.1 and certificate authority system
  we know today.
1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280
  This is a really unfortunate incident of history; not only are
  canonical s-expressions a dramatically easier to read and parse
  system than the mostly-opaque X.509/ASN.1 family of encodings, but
  SPKI/SDSI did much innovation with a [[https://github.com/cwebber/rebooting-the-web-of-trust-spring2018/blob/petnames/draft-documents/making-dids-invisible-with-petnames.md][petname]]-cenrtic web of trust
  approach, as opposed to the centralized and extremely vulnerable to
  corruption certificate authority system we got today.

[fn:do-we-need-put-the-key-in-magenc] Do we really need to put the
  keydata in a magenc store?
  Since in this =quartz:= version of Crystal URIs we used RSA, the
  public and private keys are long enough that yes, we unfortunately
  do have to.
  However, there is another option: if we used elliptic curve
  cryptography, the keys would be short enough that we could store
  them in the URIs directly.
  Probably the next revision of Spritely Crystal will account for
  and make this improvement, but in the interest of not delaying this
  current demo, the existing code using RSA keys was used instead.

1281
** Reading revisions
1282

1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379
That's all well and good, but what happens when reading and writing
revisions?
First of all, we should emphasize: the registries DO NOT actually
keep the revision content, only revision metadata.
We can get a sense of where revisions are actually kept by passing
in the =--display-magenc= flag to =crystal known-history=:

#+BEGIN_SRC text
$ raco crystal get-location quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g?rok=wtNehlhYRxooG1un7cLBDMvjs2S-uEz1jLFgfDEH3Cs
magnet:?xt=urn%3Asha256d%3AZR4rPmkrRF87GldhWA6-SlyzTCPGWRPgmz4BoHAmlGI&ek=45LQIZY1v4MxmkIwVPFGOAwHswD-cltfSdcGMQRujvQ&es=aes-ctr-sha256
#+END_SRC

Hm.  Let's try fetching that first one with the magenc client:

#+BEGIN_SRC text
$ raco magenc --get \
    "magnet:?xt=urn%3Asha256d%3AZR4rPmkrRF87GldhWA6-SlyzTCPGWRPgmz4BoHAmlGI&ek=45LQIZY1v4MxmkIwVPFGOAwHswD-cltfSdcGMQRujvQ&es=aes-ctr-sha256" \
    http://localhost:8000
Name: Elzan Dragonscale
Description: Elzan has long dark hair and stunning purple eyes.
  A formidable caster, all the more powerful for having found
  his true self.
[...]
#+END_SRC

Note that this command won't work with a verify-only cap:

#+BEGIN_SRC text
$ raco crystal get-location quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g
ERROR: requires capability with read access
#+END_SRC

That should give us a nice hint: we can deduce that since the
crystal registry only operates on verify caps, it must not know
where the magenc URIs are itself.
This makes a lot of sense, since once you know where the magenc
URI is, you know what the data is.
So we must be decrypting where the magenc URI is directly in the
client right?

So... what /does/ the registry know about?
It turns out we can find out fairly easily.
We can query the registry directly, asking it to give us the
same history it would have given our client.

#+BEGIN_SRC text
$ curl "http://localhost:8001/known-history?verify-cap=quartz:gl6qBg6i3dc5dz9cylxPcxIWn4SgLdTxWFzyqtwIljk.6B4Vy69Z6GnqF3VAk8eZkUBZbXgR5tWWoC1C_6Pbe7g" --output -
(7:history((7:rev-sig(8:revision1:0<...a bunch of binary garbage...>
#+END_SRC

Binary garbage again!
Oh wait, yep, this is another csexp.
Okay, if we parse it, we can see that the structure looks something
like the following, in "advanced" [[https://people.csail.mit.edu/rivest/Sexp.txt][canonical s-expression]] representation:

#+BEGIN_SRC scheme
  (history
    ((rev-sig (revision "0"                         ; revision number
                        |EFcucckHs5cW3UuLmveHgQ==|  ; initialization vector
                        ; encrypted location
                        |d2NRVIzp+PinMA+lvGa88GGvuXUt5kYM7Ctr7f9zXja6msrZbH8K8Q
                         l0Qmg+Fnrb1A9NSCkP5KpOM+1gz0BMDkqbbdaZgDuFmBtX+wbUDGwp
                         KF26qLB3AtJjOBCLtKhkbExrR+OlT9jOdk6WH21eVOblLfIhoNdALi
                         xa3mhdpKWq7LVk11kC|)
              ; signature
              |cdnIl9sDqgN12c8FB7onMC7mK5vCu+qmXm1F19Tw2BcLl83MGRTiUQFyMFHtRP1p
               rkEfr4z+o82LDB7TeV6a2ihIxIeIaLklb/J4VQolqd22J4x/SwHnp6rojJbt8CL6
               Q/1I24KparU5mJT3QXQlD91imd1zo5VHy0CSLNLWeKqkXyPMbexFML3Br/9YIaXU
               86L4dvZgDj3Bj5I7yEaBR7+0P90HH71kQdnkdziBRgvrIna0W3c6kqo/WJ316b6Q
               hB3cmciP15sufWgOXWm0ZyMT6PBIxjVgvWeEFQuogPzOnhfuKnvpsCTeVKDiLEbF
               e/Z+XJX5waPo8AhMoT29FA==|))
    ((rev-sig (revision "1"                         ; revision number
                        |7eHIQQO6d+oKFEpiPr+zIQ==|  ; initialization vector
                        ; encrypted location
                        |cX5I7Kq8swMIAVFpcxhHbjOXrjiztaV5Im0fA0HYnwmUN8jGh8N0AR
                         wAUKOoQV8tHUSFdztXuppKksX2wtFIpg3AFH5Kbt91SybS/nolr3Q1
                         L75FnGC9ryY3WmQG3h+kfVTmh+2teKP/9SVe2ZyLXpV3GPohIBaAev
                         R//sCNPFExqthcCdi3|)
              ; signature
              |ThJRgIzK87mKpSi4kqzcLdNKl+h7Awc9j7mCNO7YdJ6d5uELKBWAclm9NACvwcTp
               b1KRUYRJWuBCxkkd9RDPbM/dxdR8vC57rqGUyd6a7kV6BSweJyDMAXXpw/bqXygU
               pov1tgzh0OUZTJiBsK6zkxe7g/1Ss6VG5UoqF7NIiagWMa/ff2Icp0JVXGmSoVbg
               m6yl048ut26DGXn7O0DBwfoxkAbL0sZqRN08uHgyexEHVWV7Zmv/+luc72x+5lp5
               pDUUiVBZJWUQLklKx/aWIxy3Ag6SIOPKfeV+LoRrfuh/zQ0DV4ki+bKvBsuvYa+P
               OLDFXVrC8UgRCQgZZRHtqw==|)))
#+END_SRC

The data between =|= characters represents binary data which is, for
the sake of easier display, base64 encoded (however, in "transport" form
of the csexp it's still binary data and doesn't bear the overhead of base64
encoding).

Looking at the above we can see that =history= consists of multiple
lists of =rev-sig= structures, which themselves contain =revision=
objects.

#+BEGIN_SRC scheme
1380 1381 1382 1383 1384 1385 1386 1387
  ;; outer history
  (history <revision-history-0> <revision-history-1> ...)
  ;; where each revision-history contains a list of rev-sigs...
  (<rev-sig-0> <rev-sig-1> ...)
  ;; and each rev-sig looks like...
  (rev-sig <revision> <signature>)
  ;; and each revision looks like...
  (revision <num> <iv> <encrypted-location>)
1388 1389
#+END_SRC

1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404
Now we can understand how a client could fetch the contents of
revision 1:

 - If we decrypt the =encrypted-location= of revision 1 using the =iv=
   and the read key, we would get back
   =magnet:?xt=urn:sha256d:ZR4rPmkrRF87GldhWA6-SlyzTCPGWRPgmz4BoHAmlGI&ek=45LQIZY1v4MxmkIwVPFGOAwHswD-cltfSdcGMQRujvQ&es=aes-ctr-sha256=,
   so now we know where the data is.
 - If we then serialize the =revision= csexp and check its =signature=
   from the =rev-sig= against the verification key, we would see
   that it's valid.
 - So now we know that it's a valid revision, and where to get it from
   the magenc store.
   So we use the normal magenc retrieval operation, and we're done.
   Great!

1405
** Writing revisions
1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443

Now that we understand reading revisions, writing them is pretty
much the same process, in the reverse direction.

But this may be easier to understand by considering the steps taken
in uploading some content.
Let's consider, from the client's end, what it was like to write out
the second revision.

 - First, the client is given both the data to write and the
   read-write url.
   From the read-write url, the client is able to retrieve all of
   the write key, the read key, and the verification key, as described
   in the previous subsection.
 - Next, the client does a =magenc put= to write the data to a magenc
   store.  It gets back the magenc URI of
   =magnet:?xt=urn:sha256d:ZR4rPmkrRF87GldhWA6-SlyzTCPGWRPgmz4BoHAmlGI&ek=45LQIZY1v4MxmkIwVPFGOAwHswD-cltfSdcGMQRujvQ&es=aes-ctr-sha256=
 - So, now the actual file is uploaded, and we have a URI to refer to
   it.
   But we need to encrypt that URI so that only read-capable entities
   can know where to find it.
   So we generate an initialization vector, =iv=, and encrypt it.
   Now that's our =encrypted-location=.
 - At this point, we can make a =revision= record containing the
   revision number =num=, the =iv=, and the =encrypted-location=.
 - But we still need to authorize that revision, so now we sign the
   revision using the writing key and get back =signature=.
   We can now compose together the bundle of revision + signature as
   a =rev-sig= record containing =revision= and =signature=.
 - Now we contact any crystal registries that we want to know about
   this new revision, giving it the =rev-sig= and the associated
   crystal verify cap.
   The registry will take a look at the =rev-sig=, checking the
   =revision= against the verification key it looked up using the
   verify cap, and if it all checks out, it can update its table
   noting the new revision.

Whew!
1444

1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477
* Conclusions

Immutability is preferable when possible, and is the foundation for
content-addressed storage systems, which enable peer to peer storage.
Sadly, the world moves and changes, and so too must our data.
We can build mutability on top of a content-addressed infrastructure
through the successive availability of new authorized revisions which
point to said immutable data.
We have shown that it is possible to preserve privacy while allowing
for updates; registries are only privvy to the existence of a crystal
and knowledge that update exist, but not the contents of what those
updates point to.

Unfortunately, even when mutability is layered on top of immutability,
many of the challenges introduced by mutability come back in such a
system, made worse through the difficulty of synchronizing state in a
decentralized system.
(Although, old revisions at least may always be retrieved.)
If a malicious entity with writing capability wishes to intentionally
confuse systems by writing out multiple conflicting revisions, it is
difficult to prevent this scenario without dramatic tradeoffs in cost.
Systems using Crystal, or other Available + Partition-tolerant systems,
must be prepared for this possibility.
Still, it is possible to add synchronization systems to reduce the
pain of the multiple writer problem by allowing better cooperation
amongst well intentioned writers.

However, it turns out that the difficulties of synchronization which
appear in Crystal appear in many other distributed systems.
It turns out that there is no perfect system, only sets of tradeoffs.
What we can do is be well informed of the tradeoffs while we are
designing our systems and do our best to account for them.

1478
* Limitations and future work
1479

1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499
Spritely Crystal, at the time of writing, is still a demo, though the
hope is that it will become more serious over time.
It has some significant limtations at the time being.

 - Consistency issues are described in detail in this document; read
   above.
 - As with magenc, if a chunk relevant to a file is lost, that file
   cannot be recovered.
   Freenet and Tahoe provide redundancy in terms of erasure encoding,
   whereas for the sake of smaller storage size and simplicity, the
   assumption in Magenc and Crystal is that if you want to keep around
   files, make sure their chunks survive, possibly by having multiple
   uploads.
 - Currently, new revisions are entirely new uploads.
   This has the potential to be very expensive if a sizable file
   is edited many times.
   Crystal thus resembles Tahoe's [[https://tahoe-lafs.readthedocs.io/en/latest/specifications/mutable.html#small-distributed-mutable-files][Small Distributed Mutable Files]];
   with some work, deltas could be supported, and we could make the
   update to somethin like [[https://tahoe-lafs.readthedocs.io/en/latest/specifications/mutable.html#medium-distributed-mutable-files][Medium Distributed Mutable Files]] by
   specifying chunk-sized deltas between revisions.
1500
 - Something even more efficient like [[https://github.com/tahoe-lafs/tahoe-lafs/compare/master...ccxcz:crdt-dirs-spec#diff-cc7a8cc512c2ccaee3686626851bc5bd][casually-consistent data storage]]
1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518
   may be interesting to explore; it isn't clear to the author how
   possible this is or if this design can scale to a peer to peer
   system.
 - Like with Magenc, if the underlying encryption schemes fail or
   weaken, that threatens the integrity of Crystals, allowing any
   of collisions, unauthorized updates, or divulgence of private data.
 - The author didn't leave in a way to upgrade the cryptographic
   schemes in the "quartz:" revision of crystal URIs; future proofing
   demands fixing this, and later revisions should accomodate that.
 - The decision to use incrementally increasing numerical identifiers
   and not a merkle tree was made because a) it implified
   implementation and b) we need a good way to find what is referred
   to as the "latest" valid revision (though the length of a branch
   could also be used for this).
   It could be that a merkle tree is better in that it provides better
   guidance for merges (though this may mean that dropping old metadata
   is harder).

1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560
# * Zarutian 's reconstruction of MarcS algorithm for ScoopFS: three
#   cryptographic hashes, one for last version, one for current version
#   and one for the new incomming version. If the prior hash given in an
#   update is equiv to current version hash then no conflict, if it is
#   equiv to last version hash then conflict and also if the prior hash
#   is not equiv to any of those, conflict, probably.
# <dustyweb> Zarutian: interesting, so more or less rely on the
#   same-parent'ing of merkle tree?
# <Zarutian> no, it is simpler than that.
# <Zarutian> the hashes are only used to name the versions unambigously,
#   nothing more.

# <dustyweb> Zarutian: btw I decided to go with the
#   incrementing-numerical-id approach that tahoe also uses rather than a
#   merkle tree like git
# <dustyweb> because I figured in this design
# <dustyweb> all that really mattered is whether or not it's the
#   "latest"
# <dustyweb> you could also do "what's the latest" measurement by "the
#   longest branch"
# <dustyweb> I suppose
# <dustyweb> secure scuttlebutt apparently does both, puts the numerical
#   id inside a merkle tree, which seems like nonsense to me
# <dustyweb> why do both?
# <dustyweb> one advantage of the numerical id, I suppose
# <dustyweb> is it allows you to more easily drop history
# <Zarutian> sure. But this also reminds me of Norm's databank
#   ideas. Though resources are identified by the hash of the contents,
#   there were also possibility of querying a 'bank if it had any deltas
#   to or from a spefic resource.

# <dustyweb> Zarutian: btw mind if I put this conversation as comments
#   in my documentation?
# <dustyweb> just so I remember for making some revisions
# <Zarutian> go ahead, though this isnt citable material. (Treat it like
#   you would encyclopedia in citing)
# <dustyweb> yep

* Further reading and acknowledgements

# TODO: Look at https://alanhkarp.com/scoopfs/index.html

1561 1562 1563 1564 1565
Crystal's design is largely derivative from ideas in [[https://tahoe-lafs.org/][Tahoe-LAFS]] and to
a lesser extent [[https://freenetproject.org/][Freenet]].
The suggestion of a coordination server came from conversations with
Alan Karp about those in [[https://alanhkarp.com/scoopfs/index.html][ScoopFS]], though for the sake of brevity, the
suggested solution was simplified.
1566

1567 1568
Thanks to Morgan Lemmer-Webber, Zarutian, and various members of the
[[https://groups.google.com/forum/#!forum/friam][Friam]]/[[https://groups.google.com/forum/#!forum/cap-talk][cap-talk]] communities for feedback on this document.