[Monotone-devel] Security is hard. Let's work on policy branches anyway.

[Nathaniel J. Smith]

Each revision in the policy branch contains a set of rules, such that
for any particular cert we can look at the rules and decide whether
that cert passes.  The tricky question, that has been blocking
progress on policy branches, is how -- given a root revision in the
policy branch -- we find the heads of that policy branch.  The problem
is that as we are walking down the graph finding new revisions that
are certified by valid committers, the rules defining "valid
committer" are simultaneously changing under our feet.

There have been a number of proposals attacking the general problem of
defining trust in the policy branch itself (see mailing list
archives), but so far they've generally required statefulness on
servers and/or requiring careful security guarantees on communication.
We may yet end up with such an approach, but I want to at least make
my best attempt at a truly "monotonic" solution, that does not require
either statefulness or communication-time checking.

So here are my latest thoughts on how to do that -- with the warning
that they're incomplete and probably not explained terribly well.

But before the thoughts proper, I need to make up some notation, so I
can actually give examples :-).

Notation
========

The diagrams I have been scribbling to myself look basically like
this:

     +abc
      / \
   -c/   \+d
    /     \
  a1       b1
    \     /
   +d\   /-c
      \ /
       b2
    
This is a revision graph (particularly, the revisions in a policy
branch), with funny labeling.  The lowercase letters, here, refer not
to particular values (like they would if this was a merging diagram),
but to principals.  Keys.  People.  Whatever you want to call them.
The top node is the root of the policy branch -- the "trust seed" --
and it is annotated with the initial rules.  (Here, those initial
rules are "a, b, and c are trusted committers".)  Then, the later
revisions are labeled by the committer -- the person whose cert
vouches for the revision -- plus a number to make it easier to refer
to particular revisions/certs.  So here, a and b each committed a
parallel child of the trust seed, creating two heads, and then b
merged them.  (The root node does not have anyone vouching for it,
because it does not need to -- you have to take _something_ on faith,
and that's the trust seed.)  Finally, the edges in the graph are
labeled with the changes made.  So what a did was revoke c's access,
and what b did was grant d's access.  Sometimes it is convenient to
also annotate each node by writing out the snapshot of the trust rules
it contains, like so:

     +abc
      / \
   -c/   \+d
    /     \
  a1       b1
 +ab      +abcd
    \     /
   +d\   /-c
      \ /
       b2
      +abd

This is, of course, what is actually written down in the history --
the pluses and minuses on the edges are derived from looking at the
snapshots.

Problems
========

Okay, now we can more easily write down some of the basic cases that
make this problem interesting.  The first few should be pretty
familiar to anyone who's read the old threads on this stuff.

Problem 1 -- making revocation stick
------------------------------------

Alice and Bob both have access, and then Bob's access is revoked, and
life continues on indefinitely:

  +ab
   |
 -b|
   |
  a1
   |
   :
   |
  a50

But, eventually, Bob decides that he wants to make some change anyway
(naughty Bob!).  His access was revoked, so we do not want this to be
possible -- and it's easy to prevent it if he tries to commit a child
of a50, the actual current head.  (a50 says that Bob does not have
commit access, so when we go walking down the graph to see which nodes
are trusted, we will not walk from a50 to a node signed by Bob.)

However, we cannot prevent him from doing:

  +ab
   | \
 -b|  \
   |   \
  a1    b1
   |
   :
   |
  a50

Here, we don't want to trust b1, even though it is the immediate child
of a node that _does_ think we should trust b1.  In fact, it's
important that we completely and silently ignore b1; even warning
messages could be exploited by Bob as a kind of denial of service.

Tentative conclusion: The characteristic feature of this case is that
while a50 and b1 both have solid paths leading to them, a50 "dislikes"
b1, while b1 "likes" a50.  So somehow we should notice this, and let
a50's dislike kill off b1.

Problem 2 -- rule snapshots are not enough
------------------------------------------

Here's the thing: we like to think in terms of static snapshots
("right now, a and b are allowed to make changes"), but a more
delta-ish representation seems necessary ("a has had access granted",
"b has had access revoked").  The example is, compare these two
graphs:

     +abc           +ab      
     /  \           /  \     
    /    \-c     +c/    \    
   /      \       /      \
  a1       b1    a1       b1
 +abc     +ab   +abc     +ab
  |              | 
  c1             c1

In both of them, you have basically the same skeleton: the root, with
some divergence hanging off of it, one path containing two revisions
a1 and c1, the other path containing one revision b1.  Everyone agrees
that a and b have the right to commit -- the question is whether the
revision c1 should be trusted (given what we've just learned from
Problem 1).

The left figure is like the situation in Problem 1 -- c starts out
with access, which b revokes, but then c commits a revision hanging
off some divergence anyway.  So the Correct Answer here is for the c1
revision to be _ignored_.  And, indeed, if we look at the rules
snapshot in b1, it just says "+ab" -- it doesn't think c should have
access, so that seems to fit our tentative conclusion above.  b1 seems
to "dislike" c1.

The problem comes when we look at the right figure.  Here, we started
out with only a and b having access, and then a granted access to c as
well.  c then made use of this access to commit c1 -- which should be
perfectly valid.  Also, b happens to have committed some change off of
an older revision -- perhaps he was working on a plane or whatever --
but that's irrelevant, nothing he did had anything to do with c.  So
here it seems pretty straightforward that the Correct Answer is for c1
to be _trusted_.  But... there's the problem.  If we just look at the
snapshot for b1, it _still_ says "+ab" -- in fact, all of the
snapshots are identical to the previous case, except for the trust
root.  Here we don't want to say that b1 "dislikes" c1, even though
that's what it looks like.

Somehow we have to take into account not just the snapshots, but the
fact that in one case the +ab/+abc snapshots were achieved by starting
with +abc and revoking access on one side, and in the other case they
were achieved by starting with +ab and granting access on one side.
We need to think in terms of not just snapshots, but the deltas that
we got them from.

Well, fortunately, we do have some reasonably rigorous thoughts about
how one performs delta-like reasoning on a snapshot representation.
They're called "merge theory".  In particular, in this case, we can
see that if we merge a1 and b1 (in some sense or another), then in one
case the merge will have a +c, and in the other case it won't.

Personally, I really resisted the idea that we need to bring merge
theory into our security system.  My design intuition _hated_ the
concept: it puts a very high value on simplicity in any case, but
_especially_ when talking about security systems, where analyzability
and predictability are utterly foundational.  But I've pretty much
accepted it as necessary, because of this example -- I just can't see
any other way to deal with it -- and because I've gradually convinced
myself that binary deterministic *-merge is really not that scary
after all.  (I'll explain where exactly binary deterministic *-merge
comes in farther down.)

Anyway, tentative conclusion: Our definition of "revision foo 'likes'
revision bar" must involve reference to a merge algorithm.

Problem 3 - trust for merge nodes
---------------------------------

Problem 1 and Problem 2 dealt with some of the peculiar issues that
arise when trying to work out the interaction between candidate branch
heads.  Problem 3 deals instead with defining trust for merge nodes.
At one point I thought that this was actually closely related, because
of the way merge nodes inherently involve two different lineages
simultaneously, but after talking this stuff over with Zack earlier I
am tentatively convinced that I was wrong.  Anyway: merge revisions.

The basic question about merge revisions is, when should you trust
them.  For other revisions, it's pretty easy.  The only possible
no-parent revision is the trust seed, which you trust automatically.
For single-parent revisions, you trust them if you trust their parent,
and also that parent's rules agree that the child's changes are valid.
But merges are more complicated, because there are two parents.

Some of you will remember, way back when we were first talking about
this stuff, I argued that the right rule for merges is that you should
trust them iff _at least one_ of their parents was trusted and trusted
them.  This rule is totally and horribly wrong.  Just consider the
example from Problem 1, with a merge added:

   +ab
    | \
  -b|  \
    |   \
   a1    b1
    |    |
    :    |
    |    |
   a50   |
     \   |
    +b\  |
       \ |
        b2

Seed -> b1 -> b2 forms a solid trust path, but b2 _clearly_ should
not be trusted.  This might suggest that instead, we should declare
merges to be trusted iff _both_ of their parents were trusted and
trusted them.  However, this rule is also wrong.  Consider a
simplified version of the examples from Problem 2:

     +ab          +abc
     / \           / \
  +c/   \         /   \-c
   /     \       /     \
  a1      b1    a1      b1
 +abc    +ab   +abc     +ab
   \     /       \     /
    \   /+c       \   /+c
     \ /           \ /
      c1            c1
  
In both of these cases, we have a merge node signed by c, and one
parent who likes c and one parent who does not.  The local situation
is identical.  On the left side, c has been granted access, so it is
perfectly reasonable that c would use this access to merge up the two
divergent heads.  I.e., the correct answer is to _trust_ c, and this
shows that requiring _both_ parents to like a merge child is is too
strict to be correct.

On the right side, of course, c's access has been revoked, so the
right answer is to _distrust_ c.  Taken together, it's clear that we
cannot use any rule that depends only on the local situation and the
edges from the parents.

Tentative conclusion: we should trust a merge node iff its parents are
both trusted, and _the merge of those parents trusts the child_.

(Parenthetical paragraph 1: I am using "merge" in a somewhat loose and
undefined sense here.  For instance, you might assume that I am
suggesting we we merge a1 and b1 using the standard directory tree
merger, and then look at the resulting roster to read rules out of it.
I'm not really suggesting this; *-merge may be simple enough to
understand, but the emergent properties you get when using it to get
rename-aware directory merging are definitely not.  So let's just
assume that the above conclusion is talking about merging in some
vague sense to be determined later, and see if we can at least agree
on the need.)

(Parenthetical paragraph 2: Another way to talk about the different
options here: we know already the simple rule for single-parent nodes,
where you just look at that one parent and the edge from it.  But
there are a number of different ways one might extend this to merge
nodes.

Option 1 (OR): treat the two edges coming into the merge node like
they were two independent single-parent edges.  If either looks good
as a single parent edge, then accept the merge node.  As seen above,
this fails miserably.

Option 2 (AND): treat the two edges coming into the merge node like
they are two linked single-parent edges.  Only trust the merge node if
_both_ in-edges look good when treated as single-parent edges.  As
seen above, this is subject to a more conservative sort of misery, but
misery it is.

Option 3 (MERGE): insert a dummy "clean merge" node in the graph.
(Cf. my recent missive on deterministic merging.)  This is a
deterministic combination of two trusted nodes, so trust it
automatically.  Now the _actual_ merge node _has become_ a
single-parent node:

   a1  b1
    \ /
     ?
     |<------- this is the edge we worry about
     b2

So we can just apply the single-parent rule directly.)


Tentative solution
==================

So here's my best attempt to date to solve all the above problems.

Our algorithm operates in two passes.  The first pass determines which
nodes have some inherent trust and generates a set of head candidates;
the second pass analyzes trust between these heads and allows some
heads to be shot down by others (as per Problem 1).

First pass - inherent trust
---------------------------

The first pass is reasonably straightforward.  Let a node R be
"inherently trusted" if:
   -- R is the trust seed
   -- R has only a single parent S, S is inherently trusted, and the
      trust rules in S approve of the S->R change.
   -- R has two parents S and T, both of which are inherently trusted,
      and merge(S, T) approves of the merge(S, T)->R change.

The "natural" (I think) way to define "merge(S, T) approves of R" is
as follows.  Whatever formalism we end up using to write down
permission rules, for any particular cert and any particular set of
rules we will be able to tell whether that cert is valid according to
those rules.  This remains true even in the presence of richly
expressive rules, that include reference to what particular subsets of
files are allowed to be modified, etc.

Another way to put this is, any particular cert induces a function
from nodes in the policy branch to binary values {trusted, not
trusted}.

So suppose that we want to determine whether some merge node R is
trusted.  What we can do is take the certs that claim it should be
trusted, and walk over the graph checking for each node whether that
particular node likes this cert, i.e., mapping our function over the
DAG.  This generates a new DAG in which all the values are simple
binary scalars.  I suggest that _this_ is the right DAG to calculate
the meaning of "merge(S, T)", in the definition of inherent trust.

For instance, in the examples from Problem 3, we are interested in
whether c1 should be trusted:

     +ab          +abc
     / \           / \
  +c/   \         /   \-c
   /     \       /     \
  a1      b1    a1      b1
   \     /       \     /
    \   /+c       \   /+c
     \ /           \ /
      c1            c1

In the left case, the c1 cert looks good according to a1, only, so we
get a binary graph (using "+" for "trusted" and "-" for "not trusted")
like:
    -
   / \
  +   -
   \ /
    ?
Clearly this merges to "+", i.e., c1 trusted.

In the right case, the c1 certs look good according to a1 and the
root, but not b1.  So we get a binary graph like:
    +
   / \
  +   -
   \ /
    ?
Clearly this merges to "-", i.e., c1 untrusted.

Conflicts should be treated as distrust -- fail closed and all that.


Second pass - culling the herd
------------------------------

The first pass gives us a connected set of inherently trusted nodes.
However, Problems 1 and 2 show us that this is not enough.  For
instance, in:

  +ab
   | \
 -b|  \
   |   \
  a1    b1
   |
   :
   |
  a50

b1 is inherently trusted, but we need to distrust it anyway.

So after the first pass we have a set of candidate heads {b1, a50}.
We need to notice that a50 dislikes b1, but b1 does not dislike a50,
and that therefore we should toss out b1.  So there are two things to
do:
  -- define what exactly "a50 dislikes b1" is supposed to mean
  -- define exactly how the culling process works in the presence of
     more than 2 heads and possibly more complex ancestry chains.

I have some guess for the first question, and not really too much of
one for the second, but I can give some hairy examples.  (What, you
didn't think I was going to give you the answers on a silver platter,
did you?)

It seems to me that "a50 dislikes b1", or more generally "Q dislikes
R", has one at least one obvious way to define it.  Let a node R be
"trusted wrt Q" if:
   -- R is the trust seed
   -- R has only a single parent S, S is trusted wrt Q, and the
      trust rules in merge(Q, S) approve of the S->R change.
   -- R has two parents S and T, both of which are trusted wrt Q,
      and merge(Q, merge(S, T)) approves of the merge(S, T)->R
      change.

You'll note that these are basically a copy-paste of the "inherently
trusted" rules, with a new bit thrown in.  Basically, the idea is that
we zipper-merge Q with R, and check trust along the zipper-merge
path.  Again, I'm assuming that we do merge in some careful and
sensible way, and merge(Q, merge(S, T)) is nicely well-defined if we
can use deterministic *-merge.

(Random note: because deterministic *-merge is idempotent, an
equivalent definition for "inherently trusted" would be "trusted wrt
the trust seed".)

So, we can use this to define some sort of pair-wise trust relations
between arbitrary nodes across divergence.  The next question is what
to _do_ with such info.  It's not really clear.

Example 1:

  +ab
   | \
 -b|  \
   |   \
  a1    b1
   |
   :
   |
  a50

a50 is trusted wrt b1, but b1 is not trusted wrt a50.  So a50 should
live, while b1 is ignored.

Example 2:

     +abc           +ab      
     /  \           /  \     
    /    \-c     +c/    \    
   /      \       /      \
  a1       b1    a1       b1
 +abc     +ab   +abc     +ab
  |              | 
  c1             c1

On both sides, a1 is trusted wrt b1.  On the left, c1 _is not_ trusted
wrt b1, but on the right, c1 _is_ trusted wrt b1.  This would suggest
that on the left we should allow b1 to kill off c1, so we retreat to
a1, and get the head set {a1, b1}.  On the right side, everything is
hunky-dory, so we should get the head set {c1, b1}.

Example 3:

     +ab
     /  \
  -b/    \-a
   /      \
  a1       b1
  
Here we have some sort of determined disagreement between admins.
There isn't much monotone can do except point out the problem, and let
the people involved work it out.  There are basically two options:
wedge everything until people work things out (possibly by all users
deciding to update their trust seed to follow whichever admin is
actually trustworthy), or drop back to the last thing that everyone
can agree on (i.e., actually kill off _both_ a1 and b1, and go back to
the trust seed, in this case, for now).

Example 4:

     +abc
      / \
     /   \-c
    /     \
   c1      b1
   |
   a1

Here, c1 is clearly not trusted wrt b1.  This means that a1 is also
not trusted wrt b1.  Not entirely sure what this should do -- like a
may have simply committed that revision without knowing that c was
(about to become) illegitimate, but gets caught in the crossfire
between b and c?  Maybe issue a warning?

Example 5:

Life can get more complicated with more than two heads.

      +abc
     /  | \
  -b/ -c|  \-a
   /    |   \
  a1    b1   c1
  
Here there is a cycle of disagreement.  We can remove any one node and
get a consistent view of the world.  But since the choice is
arbitrary, we can't really make it -- this should cause a wedge or
fallback or whatever.

Example 6:

        +abcd
        / | \
       /  |  \
      /  / \  \
     /  |   |  \
  -b| -c| -d|   |
    |   |   |   | 
   a1   b1  c1  d1

This is not a cycle -- instead we have: a-kills-b-kills-c-kills-d.
Eliminating either a-and-c _or_ b-and-d will make this into an
internally self-consistent graph.  Should this be a wedge, or what?
With a chain like this that was only of length 3, you could make some
argument for eliminating the middle node, since that gives you a
maximally sized consistent set (with a-kills-b-kills-c, you can get a
consistent set by eliminating b, or a-and-c, or b-and-c), but even
that argument doesn't apply here.  (I'm not sure it's a good argument
anyway -- majority-rules is not really a great approach to security,
esp. in a world with sock-puppets etc.)

You could make an argument that since a is the only one who _no-one_
has shot down, that breaks the symmetry somehow -- maybe a alone
should survive, or maybe a-and-c should survive.

Example 7:

...so actually, you don't even need more than two heads to get
crazy-hairy cases.  Here's an example that involves just three
nodes...:

        +abc
         / \
      -c/   \-a
       /     \
      a1      b1
              |
              |+a
              |
              c1
    
Here a1 is trusted wrt c1, but c1 is not trusted wrt a1.  So
presumably we should eliminate d1, leaving us with {c1, b1} as our
candidate head set.  However, a1 is _not_ trusted wrt b1.  So
presumably we should eliminate a1 as well, leaving us with just {b1}.
But then, maybe c1 should be trusted again...?  Or what...?

Example 8:

Basically the same idea as the above, but even worse:

      +abcd
       / \
      /   \-c
     /     \
    a1      b1
    |       |
  -d|       |+c
    |       |
    c1      d1

Apparently,
  c1 kills d1,
  which triggers a retreat to b1,
  which kills c1,
  which triggers a retreat to a1,
  which unkills b1 and d1
  which re-allows c1, which.......?

A few more examples, that need an answer at some point even though I
don't have anything particular to say about them now:

      +abc
     /  | \
    / -c|  \-b        b1 and c1 attack each other with a as uninvolved
   /    |   \         bystander -- wedge or leave a as sole survivor?
  a1    b1   c1

      +abc
     /  | \           similar, but now a cracks down on both of them
 -bc/ -c|  \-b
   /    |   \
  a1    b1   c1

      +abc
     /  | \           ...or what if a only cracks down on one of them?
 -b / -c|  \-b
   /    |   \
  a1    b1   c1


"Clearly, more work is needed."


The next three sections are more tangential, but wanted to get them
down.  Maybe they'll help wash the bad taste of this part out of your
mouth.

Do merges nodes need to invoke culling?
=======================================

I mentioned up above that at once point I thought there was a close
relation between defining trust for merge nodes and trust among heads,
but had been tentatively convinced that I was wrong.  In this section
I explain what I meant.

What I originally thought, when I started writing up this note, was
that when we looked at merge node, like, say, b2:

   +ab
    | \
  -b|  \
    |   \
   a1    b1
    |    |
    :    |
    |    |
   a50   |
     \   |
    +b\  |
       \ |
        b2

Then it was insufficient to simply consider the trust at the node
merge(a50, b1); we should also check whether a50 is trusted wrt b1 and
vice-versa.  This seems plausible on the surface; it should prevent
evil people from merging up their evil nodes to good nodes, right?
Now, it happens that in this case, such a check is redundant, because
the merge(a50, b1) check is enough, but, maybe in some other cases you
need both checks...

(Even more tangentially, this is the case that caused me to work out
deterministic *-merge -- if you need to check merge node parents for
trust wrt each other, then those parent ancestry lineages might
themselves contain merge nodes whose parents need to checked for trust
wrt each other, etc.  So you need a definition of "R is trusted wrt
{A, B, C, ..., Q}", and that needs a sensible n-way merge primitive...
It looks like deterministic *-merge is pulling its weight, just not in
the way I imagined at _all_.)

AFAICT, you do _not_ need the secondary check.  One way to see this is
to observe that if someone has had their access revoked on one side of
some divergence, then certainly their access is marked on that side.
I.e., in this case, *(a50) = a1 is not be an ancestor of b1.  (You
could move b1 so it is underneath a1, but then b1 would not even be
inherently trusted.)  If you look at the definition of *-merge, this
implies that merge(a50, <anything not a descendant of a1>) can either
be a win for a50, or a conflict.  It is impossible for b1 to cleanly
win the merge, no matter what happened -- the most b can hope for is
to generate a conflict, but that won't help, since we treat conflicts
as distrust.

So once one side of the divergence distrusts our evil person, he
cannot possibly set things up so that any merge with that side trusts
him either.

Another way to think about this case is to say if a node passes the
merge(R, S) check, then what that guarantees is that -- whatever bad
blood there may be between R and S -- at least _one_ thing they can
agree on (in the merge sense) is that that child node is allowed to
pre-empt both of them.  And if everyone agrees, that's good enough for
me...

Fine-grained trust rules
========================

So far, I've only talked about trust rules that simply allow/disallow
access.  In real life, we're probably going to have to have at least
some kind of "so-and-so is allowed to commit -- so long as they only
touch directories foo and bar!" type rules.  (I'd kind of rather avoid
it entirely, but at least for the policy branch itself it seems
inevitable, so long as we want to store both things like policy branch
commit permissions there, and also the branch namespace itself.  It
should be possible to have some people who have permission to create
branches, but yet do not have permission to kick out other
developers!)

This raises some issues of its own, but I think they're
straightforwardly solvable.  For appropriate values of
"straightforward".

Anyway, here's the basic problem.  Unfortunately, my notation breaks
down here, so I have to be a little more verbose... suppose that Alice
and Bob both have write access to the policy branch, but to different
parts of it -- say Alice and Bob used to get along fine, but there was
a schism, and now Alice administers permissions for Anglicans, and Bob
administers permissions for Baptists.

Now, in parallel, Alice grants access to Alan the Anglican, while Bob
grants access to Barbara the Baptist:

            +Alice,Bob
           /          \
          /            \
       Alice1          Bob1
  +Alice,Alan,Bob  +Alice,Bob,Barbara
            
Straightforward enough so far.  Now Alice notices that there are two
heads and merges them:

            +Alice,Bob
           /          \
          /            \
       Alice1          Bob1
  +Alice,Alan,Bob  +Alice,Bob,Barbara
          \            /
           \          /
            \        /
              Alice2
        +Alice,Alan,Bob,Barbara            

So here's the problem.  Alice2, it seems, should be trusted -- I mean,
someone has to be able to merge these heads, and it'd sure be nice if
Alice and Bob couldn't trivially wedge things so that some sort of
administrator has to be called.  (In fact, Alice and Bob can only
agree on the legitimacy of one higher power, and He has enough demands
on his time already without unwedging monotone policy branches.)

But, it is not entirely obvious why Alice2 should be trusted -- why,
the Alice1->Alice2 edge clearly grants access to Barbara, which Alice
is not allowed to do!

I mentioned before that way back in the computer Pleistocene (i.e., a
year or two ago), I had argued that merge nodes should be trusted if
they had a least one good-looking in-edge.  This is the example that
made me argue that, and I actually believed it until I started writing
this...  The reasoning was, it is okay that the Alice1->Alice2 edge
grants access to Barbara, because we can see that the Bob1->Alice2
edge only grants access to Alan, which is permissible.  The fact that
Alice1->Alice2 grants access to Barbara, then, could _only_ come from
some other changes in the Bob1 side of things.  If it didn't, then
that change would have shown up on the Bob1->Alice2 edge as well.  So,
perhaps we should define "changes made in a merge node", for purposes
of checking them against which changes are actually allowed, by just
looking at each in-edge and taking whichever changes are more
favorable.

There is a really deadly counter-example, though:

            +Alice,Bob
           /          \
          /            \
       Alice1          Bob1
  +Alice,Alan,Bob  +Alice,Bob,Barbara
          \            /
           \          /
            \        /
              Alice2
         +Alice,Alan,Bob            

This is just like before, except that now Alice2 has actually
_revoked_ Barbara's access again.  By the rule just discussed, this is
allowed!  The thing is that Alice1->Alice2 is now a no-op.  A no-op is
certainly an allowed set of changes for Alice to make, so Alice2 will
be trusted.  That Bob1->Alice2 now has a revocation of Barbara's
access is irrelevant...

In fact, in general, the rule I proposed originally will always allow
clobber-merges.  Which is all kinds of broken.

At this point I got frustrated and banged my head against the wall for
a bit, and then went... "Wait.  The problem is that we need to figure
out some way to list what changes were _really_ made when someone did
a merge.  I think I have encountered this problem of defining what a
'change' is at merge time before... that's, umm, the whole theoretical
foundation of *-merge.  * = change.  ...Right, I knew that."

So, 'obviously', we should determine our list of changes by _looking
at what gets marked_.

The best way to write this is the deterministic *-merge way.  In the
first graph, we really, underlyingly, have:

            +Alice,Bob
           /          \
          /            \
       Alice1          Bob1
  +Alice,Alan,Bob  +Alice,Bob,Barbara
          \            /
           \          /
            \        /
             <nobody>
        +Alice,Alan,Bob,Barbara            
                |
                |
              Alice2
        +Alice,Alan,Bob,Barbara            

Now Alice2 is a nice single-parent node again, and the single in-edge
is a no-op.  No-ops are allowed, all is good.

In the second graph, we get

            +Alice,Bob
           /          \
          /            \
       Alice1          Bob1
  +Alice,Alan,Bob  +Alice,Bob,Barbara
          \            /
           \          /
            \        /
             <nobody>
        +Alice,Alan,Bob,Barbara            
                |
                |
              Alice2
        +Alice,Alan,Bob            

Now Alice2 still has a single parent, but the edge from that parent
is... revocation of Barbara's access.  Oops, Alice2 is not allowed.
Just as it shouldn't be.

Of course, in practice we will have to be very careful about how
_exactly_ we define "changed" (= "marked") here -- partly because it
will become a more-or-less permanent part of monotone's exposed
interface (you can't change the definition and suddenly change which
existing policy revisions are trusted!  Well, or you can, but you'll
need a good reason) -- and because there are some subtleties.
Modifying a file inside directory foo should probably count as
modifying directory foo, for these purposes, for instance.  Renaming a
file out of directory foo, likewise.  Etc.  Of course, we probably
want to track directory markings in some sense to make restricted log
fast, anyway...

(Compare this to the discussion of trust for merge nodes generally in
Problem 3 above -- it turns out that both problems created by merge
nodes have exactly the same solution.)

Writing down trust rules without time
=====================================

I'm pretty sure I've explained this before, even on the mailing list,
but for purposes of getting everything into one place... here are a
few words on how trust rules should look to handle the case where
Alice used to have access, then it was revoked for a while, and then
she got access again... where you want her old certs to remain trusted
even while her access is revoked, and her neither-old-nor-new certs to
remain untrusted even when her access is restored.  And you want to do
this without secure timestamping, because secure timestamping
frightens me.

"When in doubt use brute force".  What we really want to end up doing
is having some rule that lets us determine whether each cert Alice
issued is trusted.  The simplest such rule is a big list of all the
certs Alice has ever issued, with a mark next to each of them saying
whether that particular cert is good or not.

Of course, such a list has one major shortcoming: Alice might issue
new certs, and then our list will be out of date.  That's easy to fix,
though; we just add another note at the end saying what the default
for any certs not on the list should be.

Once we've done that, we can simplify our representation slightly: it
is redundant to say "cert asdf is trusted, and also every cert not
mentioned on this list is trusted".  Leaving asdf off of the list
altogether will give the same result as putting it on the list and
marked as trusted.  So we can compress things a bit by only listing
exceptions to the default rule.

So in conclusion, trust rules can look like:
  -- a default "trust"/"don't trust" for each key (possibly with some
     extra notations, like "only trust if their modifications only
     touch directory foo", etc.)
  -- plus an explicit list of exceptions

This seems simple and robust.

A surprise bonus is that it makes it easy to wipe out accidentally
issued certs that are Just Plain Wrong -- you can just add them to the
issuer's list of explicitly untrusted certs, even if everything else
they issued around that time should remain trusted.

I use a notation like:

         +abc
          / \
         /   \+d-d1
        /     \
      a1       b1
       |
  -a+a1|
       |
      c1
    
to write down this sort of stuff -- i.e., it looks exactly like the
notation I introduced at the beginning of this note, but extended so
that in addition to allowing "+<letter>" and "-<letter>", we allow
"+<letter><number>" or "-<letter><number>" to refer to a single
particular cert.



I think that'll do for now.
-- Nathaniel