> <i>How large do the pointers need to be? The natural answer is that each pointer uses log nbits. However, the fact that each pointer has a distinct owner makes it possible to compress the pointers to o(log n) bits.</i><p>What if you have to <i>debug</i> the whole situation, such that you don't always know who is the owner of a pointer you are looking at?<p>> <i>A user k can call Allocate(k) in order to get a tiny pointer p; they can dereference the tiny
pointer pby computing a function Dereference(k,p) whose value depends only on k, p, and random bits;
and they can free a tiny pointer p by calling a function Free(k,p).</i><p>That is tantamount ot saying that the pointer is not actually <i>p</i> but the tuple <i><k, p></i>, and so its size consists of the number of bits in <i>k</i>, the number of bits in <i>p</i> plus an indication of where the division between these bits lie: where <i>k</i> ends and <i>p</i> begins.<p>We can abbreviate <i><k, p></i> to <i>p</i> in contexts where <i>k</i> can be implicitly understood.