Re: [Monotone-devel] Re: nuskool & certs created after a revision

[William Uther]

On 02/05/2008, at 2:59 PM, Graydon Hoare wrote:

> William Uther wrote:
>
> > Yeah - Graydon had a plan for this I thought.  It vaguely sounded  
> > similar to yours, with some differences in details.  From memory it  
> > was something like: build a separate tree of certs based on time of  
> > cert creation, and sync it using the same nuskool algorithm.
> > While I can see that working, something feels a little untidy about  
> > it.  I started trying to think of other ways of doing it.
>
> (de-lurking momentarily)
>
> I am curious about this "untidy" comment;

Hrm.  I certainly didn't give it a huge amount of thought.  My  
disquiet stemmed from the fact that the cert creation time information  
is mixed up in this new cert DAG.

In particular, I didn't see how the new cert 'DAG' is more than a  
list.  This might not be a problem.  Hrm, thinking about it more now,  
I guess that working as an individual you'd only ever get a single  
list.  Branching would occur when people with different cert-creation  
histories sync (merge their cert histories).  You'd then 'auto-merge'  
all heads in the cert DAG back into one head (there is no problem with  
this - merge is just a union of certs operation - as you note below).

> it's by far the tidiest idea I stumbled across in the process, and  
> I'd recommend you give it a shake if you're keeping the gsync code  
> alive at all.
>
> IMO the problem with other approaches lies in thinking about certs  
> as sets. There is no need to. You can think of any set of certs you  
> have as being "a state" -- from which you can calculate something  
> like a manifest name, given any deterministic storage order of the  
> set -- and then you can use the existing state-evlution-over-history  
> mechanism in monotone to track the expansions of that set as history  
> edges in a DAG (that syncs using the same algorithm).

So we're both using a 'state hash' representing the set of certs in  
that state.  You are thinking of a crypto-hash of a manifest (list of  
certs in deterministic order), whereas I was just thinking of using  
the xor of the crypto-hashes of the certs.  The xor makes the hash of  
the set order independent.  I haven't done a full security audit, but  
I was assuming that if you can't easily manufacture a single crypto- 
hash by creating a cert then you can't easily manipulate the xor of  
all the certs either.  This method of creating the cert state hash  
doesn't require the 'manifest'.

The difference in our methods then consists of how these sets are  
sync'd.  I was thinking of using the revision DAG structure.  You were  
thinking of introducing a new parallel DAG structure based on cert  
creation times.  Both use a nukool-like algorithm over that structure.

> If I receive multiple history edges -- thus multiple heads -- I can  
> always trivially merge them just by unioning all the certs found on  
> all the edges. It's like the canonical example of the algorithm:  
> merging the histories of set-expansions always automatically succeeds.
>
> Any time you can get the system to move from thinking about sets to  
> thinking about DAGs, you get more structure to drive your algorithms  
> off of.

Agreed.  I was just trying to re-use the revision DAG rather than  
creating a new DAG for certs.

Cheers,

Will        :-}

P.S.  I also find the merkle tries quite beautiful.  And I haven't  
seen another method that looks as nice for syncing certs.  But I  
freely admit that that is a very fuzzy, subjective, judgement.  (And I  
note that there is nothing particularly beautiful redundant code...)