Re: [Monotone-devel] branch representation

[Daniel Carosone]

On Wed, Oct 26, 2005 at 05:05:14PM -0700, Nathaniel Smith wrote:
> So the idea is: what if we got rid of branch certs, and put a branch
> field inside the revision object?  So each revision is uniquely,
> irrevocably, in a single branch.  

So if an identical revision (in terms of resulting code) is to be on
more than one branch, it needs to be more than one revision, and I now
need some other way to prove that the revisions are
identical-apart-from-branch?

> Anyway, this wouldn't help with things that people find
> counter-intuitive like, "this branch is discontinuous", or "this
> branch has multiple branch points", or "this branch has multiple
> heads".

Good. Because I like these things. For me at least, it's not so much
that they were counter-intuitive at first introduction, more that they
were couter to previous training with other VCSs.  I found them very
intuitive, in part because they represented a simple consistent
underlying pattern and deeper insight.  They represented to me that
monotone was fundamentally sane.

Many of the issues that remain in the 'counter to previous training'
category are matters of UI maturity, 'best practice patterns'
development, etc.

> It would help with the confusion about revs being in multiple
> branches, and generally reduce the weirdness we have all the time
> where we have to assume all revs have branch certs on them, and try
> and guess an appropriate branch name given a revision, and so on -- it
> seems like the code and users both want to think of branch certs as at
> least somewhat special.  

Maybe. I'm not familiar with these assumptions and cases in the code,
I have to defer to you there.

> It might make doing trust stuff significantly easier.  I _think_ a
> design criterion for a trust system is that I want to be able to
> specify rules for trusting certs that aren't branch certs, and I want
> to do this per-branch.  
> 
> This seems very tricky, if the rule for deciding whether you trust a
> 'foo' cert begins "collect all branch certs on the same rev, invoke
> the branch trust rules on them, for each branch cert that turns out
> to be trusted, find that branch's trust rules for 'foo' certs, and
> then somehow combine the results of applying each branch's rules".

I'm not sure it's that bad.  It probably helps to think about trust
having a direction. A lot of the rest of monotone is about directed
graphs, trust pretty much should be too.

The endpoint is revisions - ultimately, revisions are trusted if
there's a path to them through the trust graph.  Equally importantly,
all the other nodes in the trust graph are *not* revisions; they're
either direct or indirect certs.  Right now, we only have direct certs
(branch, etc) that point to revisions, indirect certs would be
permissions certs and identity certs and trust certs of some or other
form. 

These forms might include path constraints in the trust graph, such as
for example the requirement that in order for the branch cert trust to
apply to a revision, there must also be a (trusted) testresult
(author/date/etc) cert for a certain name.

All identities are trusted now, adding identity trust certs with
constraints, makes this graph deeper, but not necessarily any less
directed.  In fact, if we're looking for a design criterion around
trusts, I think one should be that trust should always remain directed
at least in evaluation.

For comparative illustration, think about gpg web-of-trust
evaluation. The certs themselves are a web; the trust evaluation
algorithm searches through this graph adding weighted trust scores to
build a directed tree from the trust roots.

You example above sounds convoluted, because you change direction
several times when trying to describe the trust evaluation algorithm.
Say instead you do something morally equivalent to:

 * build a graph of all certs
 * (early optimisation) prune all paths that don't lead to the desired
   selection criteria (revision(s), branches, etc .. if relevant;
   perhaps you're searching for trusted revisions)
 * starting at the identity trust root(s?), start labelling certs with
   identity trust by signer
 * prune all certs that aren't trusted for identity (maybe we need a
   specific terminology for this, perhaps 'authenticated')
 * starting at the permission trust root(s?), start labelling certs
   according to trust-constraint matching rules
 * prune all certs that don't have their permissions constraints met
 * any certs remaining lead from both identity and trust roots,
   through to trusted revisions.

Furthermore, this thought model might provide useful design clues for
(especially) permissions rules/certs.

Put it another way.. perhaps one of the reasons the users and the code
want to treat branches specially right now is that, right now, the
*only* trust/permission mechanisms we really have in practical use are
based around branches.  (testresult certs, as the next-in-line
candidate, reveal more about the lack of a stronger permissions system
than they do about a model for further development, i think)

> And there are probably horrible convoluted attacks:
> [..]

Yes, and there are many other less convoluted cases to consider.  I'm
worried about transitive trusts even for simpler scenarios.  Alice
trusts Bob, Bob trusts Charlie.  Charlie does a commit, Bob does a
merge without looking carefully, Alice winds up with trusts on
Charlie's code.  Perhaps this means that Alice's trust in Bob is
misplaced - we just need to consider exactly what we want from a
permissions and trust system, when we come to it.

> I guess the unavoidable conclusion is that you can't determine cert
> trust based on just the contents of the DB plus the current trust
> rules, but also need to know something about the current context?
> (checkout -b B -r t:A-release should work, checkout -b A -r
> t:A-release should silently ignore it?)  This seems bad.  Maybe I'm
> missing something.

I think you might well be right. I think the "-b B" is part of the
"selection criteria" I pruned (early) in my example above.  (in
reality, step 1 is the db, step 2 is the initial selection)

> (Okay, maybe trust issues _have_ been stewing around in the back of my
> head for more than 3 months.  But I don't really understand them, so
> it's maybe premature to use them as arguments in a discussion...)

I think probably we need to start the discussion there, and understand
the trust issues, objectives, requirements, model first. Then allow
that to guide further design or infrastructure change.  It's really
the next major stage of evolution for monotone as I see it.

> This idea does add a significant new piece to the model -- instead of
> the nice clean DAG of snapshots _here_, and generic metadata mechanism
> _there_ setup, we have a piece of magic metadata, that needs to be
> handled differently, etc.

Yeah. Without drastic inherent and evident benefit, I dislike it for
that reason alone, but it's a great thought-provoker.

--
Dan.

pgp6hsJ3oO_RT.pgp
Description: PGP signature