Identity-based policy signatures

[orthecreedence]

This is an extension of #31. As currently implemented at the time of writing, policies only allow one type of signature: admin key signatures. This means that a policy needs to have a specific set of admin keys in order to be valid. This works, but is somewhat brittle. The idea behind Stamp's key system is that policies and admin keys can shift and change over time as needed. Requiring outside policies to update every time this happens is borderline useless.

While it makes sense to retain the ability to require signatures from a specific admin key, we should also allow signatures from the TransactionBody::SignV1 transaction. However, this alone would require a shitty lookup (or even multiple) with every signature. Instead shipping the signature transaction and proof that it is valid is ideal.

As it stands, it seems the only way to do this is to pass a chain of transactions (ie, the identity itself). However, this could get bloated really fast. It makes sense to only ship transactions that update the identity's policies and admin keys. We can do this by using some kind of skip list...we track two sets of previous_transactions: the standard one which lists the transactions that came before, and policy_transactions which only links back to transactions affecting admin keys or policies (and obviously the genesis). Then we can ship valid but condensed identity objects with our signature transaction that can be verified on the spot. This means that any valid signature from the identity would satisfy the policy condition (as opposed to a specific key).

I'm curious if there's a more condensed way of doing this. ZKPs seemed initially promising, but proving a chain of transactions that require multiple signatures to be valid seems ...tricky. The entire stamp protocol would have to be encoded into some kind of ZKP solver, which would be a feat in itself. I'm wondering if the skip list is the best way of going about this.

[orthecreedence]

I had two thoughts on this.

Skip hashes

One thing I saw while reading through p2panda is the concept of skip hashes (or skip lists, don't know the exact term). The idea is that you still have previous_transactions but also have something like previous_key_transactions which would store the last admin key/policy transaction ids. This method allows shipping a verifiable (but somewhat compressed) proof that a particular key belongs to the identity.

• Pro: complete verification of the identity's admin keys is quick and built-in, including against various policies.
• Con: this "proof" chain, even though only containing policy/key transactions, can grow endlessly. This is because a single transaction in this proof chain could have multiple signatures, each of them their own proof chain that contain multiple signatures, etc etc. There's no way to "flatten" or compress this chain.

Separate signing chain

The second idea is some kind of straight up signing chain. You have your alpha/genesis key(s), and each time you add another key, you record the signature of that new key's public key signed by the existing admin key that signed the transaction. In the end, you get a tree of keys all pointing back to the genesis key(s).

• Pro: Doesn't have the "ballooning proof chain" problem detailed above.
• Con: Doesn't give full verification: anybody can add any key to this proof chain (that's not necessarily in the identity) and sign it with some other key...meaning, we can't actually verify the signing chain has valid keys for that identity. This circumvents the protocol and everything that makes it "secure."
• Con: The identity is a transaction log...this signing chain isn't a transaction, and would need a "special" place to live which isn't very architecturally sound. We could make it a transaction of sorts (one that's always dangling and never referenced in previous_transactions) but that's ugly.

[orthecreedence]

Of the two options, there's no standout winner. Both are kind of shitty sets of trade-offs. This makes the ZKP idea more interesting. If there's a way to prove that the given admin key is cryptographically a member of an identity without shipping entire transaction chains around, that would be ideal. However, from what I know this might involve reimplementing Stamp in some sort of ZKP solver language, which would be...interesting (and by "interesting" I mean "nightmarish").

At least we have three half-baked possible solves, now.

[orthecreedence]

A note: I'm exploring the idea of identity branches #43 which would make having policy-specific backlinks (skip hashes) redundant...you can effectively just put your policy transactions in your master branch and have everything else branch off of it.