So you have a list of constraints: c1, c2, c3. You have a secret key on your server, 'k'. You calculate the signature as 'HMAC( HMAC( HMAC(k, c1), c2) c3)'.

So anyone can add constraints and then create a new valid signature by HMAC'ing the additional constraint into the existing signature, right? You can add constraints, but of course, you can't remove them later if you only have the latest iteration of the signature.

I'm trying to see the use-case here... is it a 3rd party taking one of these signed strings in order to append their own "constraints" onto it, cycle the signature, pass it to an end-user, who will then hand it back to your server? And even if this happened, how would you know at the end of the day who actually added the constraint? All but the first HMAC can be done by anyone, so aren't you just creating work for yourself?

Specifically how is this ever better than just doing a single HMAC(key, data) on everything that you control, specifying some delimiter character to know where your own signed data ends, and then everything else is just unsigned? I guess if you trust your link to the 3rd party, and if you trust they will add the proper constraints, then the only benefit is you know once constraints are added they cannot be removed without access to the original signature.

Going directly to the paper, they show an example on Page 4 (http://imgur.com/ARJNdu6) of a 3rd party service adding additional constraints onto an existing set;

  For example, Figure 4 shows a macaroon authorizing a user at client C to
  access chunk 235 at a key-value storage service TS. This macaroon has
  been derived as a strict attenuation of another, more permissive macaroon
  —held by the social-networking “forum service” FS—by both eliding that
  macaroon’s signature (called, say KFS), and by adding caveats whose 
  predicates require a specific chunk and client IP address to be present
  in the request context. Even so, this macaroon’s signature, KUSER, both
  allows the target storage service to verify its integrity, and also
  allows its bearer to derive new, further attenuated macaroons. In this
  manner, macaroon signatures both protect integrity and act as keys.

"Integrity" usually means you know something was not altered, so I think it's a bit dangerous to call it that. The coloring of the figure is also misleading. With the proposed nested HMAC construction, we do not actually know which caveats were added by TS versus which were added by FS, or perhaps Mallory. All that 'TS' knows is that these constraints exist, it loses a key piece of information, namely, the ability to prove which of the constraints are guaranteed to be first-party constraints, versus which were added later by third parties. For example, this could expose 'TS' to potential DoS attacks because anyone can add potentially expensive-to-verify "first-party" constraints which the server could be tricked into thinking that it had actually added itself.

Instead, the server should HMAC the full set of its own constraints with its own key, and then a single delimiter should be added. If third-parties want to add additional sets of constraints, then the nested HMAC can start being used, but again I would propose, first, sets of constraints be added atomically with some delimiter to reduce the number of wasted HMAC cycles, and second, there should be a way to include an additional shared secret between TS and FS in the HMAC process so that TS can actually validate who added the constraints without significantly increasing the size of the payload.

Edit: So, what I get out of this after ~30 minutes of review is it's a very high level protocol for how an already trusted set of servers might go about letting each other specify constraints. Frankly, I'm not sure why that's 16 pages of research. I think the HMAC chain implies more security than you actually get, and actually involves a subtle trade-off that I don't see addressed anywhere in the paper (but I didn't read it thoroughly)