[darcs-users] Signing patches

[Florent Becker]

Daniel Carrera <daniel.carrera at theingots.org> writes:
> The reason I ask is that I want to figure out whether every patch has a
> unique set of dependencies or not. If the list of dependencies is
> unique, I have a potential idea for making unique hashes+signatures:
>
> * I'm going to define the hash H which I hope will be uniquely
> defined for any patch. If H is unique, we can sign H.
>
> Definition: Given a patch U...
>
> 1. If U has no dependencies, let H_u = SHA1(U') where U' is U applied to
> the empty repository.
>
> 2. If U has dependencies, find the minimal set of patches needed for U.
> In other words, commute away everything that can be commuted. This
> leaves us with something like this:  ABCDU'.  This is not uniquely
> defined. For example, A and B might commute, so that B'A'CDU' is equally
> acceptable. But in either case, U' will look the same (right?). Now we
> can define H_u:
>
> H_u = SHA1( join(sort(H_a,H_b,H_c,H_d)) ++ SHA1(U'))
>
> In other words, take the H hashes for A-D, sort them alphabetically,
> concatenate them, concatenate that with SHA1(U').
>
> In this way, the hash H for any patch depends on that patch's
> dependencies. But you can see that this is only well defined if the
> concept of "that patch's dependencies" is well defined, and it isn't if
> we can replace patch A by patch X.

Correct me if i'm saying rubbish, but:

I think that the problem with that approach is that hash verification is
exponential: in order to check that your hash is good, i have to put U in
the same context as you in order to get U', that is, put A B C and D in
the same order. As I have no way to know in what order you saw them, I
have to try them all…

Maybe there is a way to normalise that, for example by requiring that
ABCD is "pseudo-sorted": every pair of adjacent patches is either
dependent on each-other or in hash-alphabetical-order. This still makes
computing and checking hashes quadratic in the length of ABCD.

Florent