[cap-talk] solve CSRF by making references unforgeable, not unshareable

[David-Sarah Hopwood]

Sam Mason wrote:
> On Tue, Mar 31, 2009 at 01:59:54PM -0700, Bill Frantz wrote:
>> sam at samason.me.uk (Sam Mason) on Tuesday, March 31, 2009 wrote:
>>
>>> I thought that hash tables have asymptotic complexity of O(1) the same
>>> as a lookup table.  Admittedly the constant is a bit higher, but I'm not
>>> sure what you'd gain by having any sort of dense index here.
>>
>> In this case, a hash table will use the hash of the Swiss number to select
>> a chain head (simple indexing). There may be more than one object with the
>> same hash, and these are linked together in a list. Traversing that list is
>> O(n) where n is the number of entries on the list. One can reduce n by
>> increasing the number of hash chain heads.
> 
> Yes, but surely that's why it's the "asymptotic complexity" and not
> worst case analysis.

I think you're confusing "asymptotic" with "average-case".

In any case, IMHO the choice of representation can safely be left to
individual cap system implementors, who will have a better knowledge of
how the lookup cost, and other consequences of the representation, are
affected by implementation details of their system.

-- 
David-Sarah Hopwood ⚥