[darcs-users] Re: End-to-end validation [was: applying patches on windows]

David Roundy droundy at darcs.net
Fri Nov 11 12:29:33 UTC 2005


On Wed, Nov 09, 2005 at 04:02:32PM +0000, Tuomo Valkonen wrote:
> On 2005-11-09, David Roundy <droundy at darcs.net> wrote:
> > On Tue, Nov 08, 2005 at 04:18:40PM +0100, Juliusz Chroboczek wrote:
> >> The trouble with that is that Darcs plays the commutation game, which
> >> invalidates any form of end-to-end hash.  The obvious solution would
> >> be to compute hashes in a minimal context, but I'm not sure whether
> >> that would be computationally feasible.
> >
> > I think I see.  You mean to store the patches as always, but to compute
> > (and check) their hashes in a minimal context? That's a clever idea.
> > Somehow I've been caught up on the "signed patch bundle" idea, which
> > requires a new repository format, and didn't think of the idea of storing
> > patches in their current format, but commuting them into another context
> > for hashing.
> 
> This has, however, been suggested before (although perhaps not as 
> explicitly):
> 
> http://www.abridgegame.org/pipermail/darcs-devel/2005-March/001388.html
> 
>     ... I've been thinking that it might be better to record patches in a
>     "minimal context" ... This would enable support for signed patches and
>     "freely floating patches". ... patches could also include an unsigned 
>     version of themselves for "current/repository context" ... 

The difference (which may have been in what I understood, not what was
said) is that these had the idea of *storing* minimal-context patches,
which would be considerably more expensive than simply *hashing*
minimal-context patches.  Storing minimal-context patches would make all of
darcs much slower, rather than just the (optional) hash-verification step.

> http://www.abridgegame.org/pipermail/darcs-devel/2005-March/001401.html
> 
>    ... which could be stored as a light patch-of-a-patch (the modifications
>    should be just changes in line numbers, mergers, and so on, right?).

This idea adds extra complexity--you effectively store the minimal-context
patch plus the actual patch, but in order to verify the patch, you still
need to commute it back into its minimal-context, so we've gained very
little relative to simply storing the current patch and the minimal-context
hash.  What you'd gain is precisely the ability to do a partial
verification, which verifies that the stored minimal-context patch hasn't
been corrupted, but doesn't tell you anything about the current patch.
This partial verification doesn't really gain you anything against directed
attacks, and the only real function of end-to-end verification is against
intentional attacks.  Hashes of the "current" repository can protect you
from disk or transmission-related corruption--everything but intentional
attacks and bugs in darcs itself.
-- 
David Roundy
http://www.darcs.net




More information about the darcs-users mailing list