[darcs-devel] [issue992] short secure version identifiers

[Zooko]

New submission from Zooko <zooko at zooko.com>:

My Primary Canary is Brian Warner.  He is the most important person for me to
work with, and if he is not happy with darcs, then I'm not happy.

Last November he wrote this letter:

http://allmydata.org/pipermail/tahoe-dev/2007-November/000228.html

The parts about performance are still an issue (he recently said, when I asked
him, "I would like it to be faster."), but this ticket is about the other part:
short, secure identifiers for versions.  I recently asked him to clarify exactly
what he wanted:

<zooko> By the way, I am very interested in satisfying your desires for darcs 
        functionality, and I think many of the other darcs developers would 
        be, too. 
<zooko> But so far I don't understand what you want precisely enough to write 
        it down in a darcs issue ticket.
<zooko> I certainly understand parts of it, but not all of it. 
<warner> 'darcs get -r SHORTSTRING http://repo new-tree' 
<warner> darcs status -> SHORTSTRING + diffs
<zooko> Thanks.  :-) 
<zooko> I'll write that down now. 
<warner> also, SHORTSTRING should be a cryptographically secure description of 
         a specific source tree 
<zooko> More precisely, there should be at most one source tree matching 
        SHORTSTRING, right?
<warner> yes 
<warner> oh, and computing SHORTSTRING from a given darcs repo should be O(1), 
         and 'get -r SHORTSTRING' should be O(not too bad)
<zooko> Hm.  I don't think that you mean that it has to beaconstant time 
        regardless of repo size and shape
<warner> it is in hg :) 
<zooko> as that would be impossible to conform with the unique repo 
        requirement... 
<zooko> Well, I'm sure it is possible if you amortize away the cost of 
        computing it, and then you take only O(1) time to look up the stored 
        answer.  ;-) 
<warner> I expect SHORTSTRING to be computed during the process of 'darcs get' 
         or 'darcs record' 
<zooko> I see.  ;-) 
<zooko> Ok. 
<zooko> I'll write that down too.
<warner> (basically I'm trying to discourage an implementation that, say, 
         sorts all the patches by name and then hashes the result) 
<zooko> Wait, 
<warner> well, not discourage it, but make it clear that 'what version am I 
         using' is supposed to be a cheap question, so that we could use it in 
         a 'make version' step
<zooko> your requirements are about the functionality that you need, not about 
        the implementation. 
<zooko> "cheap" is definitely a requirement. 
<zooko> O(1) I'm willing to accept, although I really don't think that's a 
        requirement of yours. 
<zooko> "Nos sorting and hashing" is definitely not a requirement you havfe. 
<zooko> I'll write down whatever you say.
<warner> you're right 
<zooko> But I might feel free to append my own opinion that if it is fast 
        enouugh then you won't know the difference.  ;-) 
<warner> darcs has some operations which are O(n!), and 'get version' must not 
         be one of them 
<zooko> The darcs people are all fired up about performance nowadays... 
<zooko> I can definitely write that down as a requirement. 
<warner> and I'd consider it a bug if it were O(Npatches), since that will be 
         usable for small repos but become less-so for large ones
<warner> so "very fast even for large/complex repos" is a better way to 
         express my requirement 
<zooko> Yes, okay. 
<warner> I don't want tahoe to be discouraged from using 'make version' on 
         every build step, for example 
<zooko> That is surely a fair requirement on your part. 
* zooko nods. 
<warner> as we are right now :)

----------
messages: 5439
nosy: beschmi, dagit, zooko
priority: bug
status: unread
title: short secure version identifiers

__________________________________
Darcs bug tracker <bugs at darcs.net>
<http://bugs.darcs.net/issue992>
__________________________________