Upgrade design of linear IDs

Description

Background

Linear IDs were originally implemented as a convenience to support queries. Nothing in the platform guarantees that a UUID genuinely refers to (globally) a single chain of states. In particular notaries don't guarantee this. For this reason a Linear ID vault query may return more than one state.

The API was self-consistent in this regard until LinearPointer was added. During review we failed to notice that resolution of LinearPointer simply asserts the existence of a single known chain. This means if by accident or malice someone creates two state chains and gives them both the same UUID, LinearPointer.resolve() will throw an exception and refuse to proceed. This is in a sense correct - the system entered an unintended state - but enables a denial of service attack in which a malicious or broken peer could issue a new chain of states with the same ID as an existing one, thus causing your app to stop working because it can't handle the ambiguity.

Technically speaking this is OK because our current security commitments explicitly exclude member-on-member denial of service attacks. But the fact that linear IDs aren't actually globally unique despite using UUIDs ("universally unique identifiers") is unintuitive and confusing. It's a pothole in our design story that we should fill.

Short term solution

There's a simple solution available to app developers for now: pick a party that is responsible for ensuring there's never more than one chain of states with a particular UUID, and write your app logic to require that issuances of a new linear state are signed by that party. This makes the party into a kind of app-specific notary. If package namespace ownership is used to claim the class name of your state type, adversaries cannot create their own state of that type even if they write their own app.

This requires a small adjustment to the LinearPointer.resolve method, which should be entirely backwards compatible, so it could be put into a 4.x release. StatePointer.kt line 119 can pass through the most precise type using the `this.type` property it already has, thus ensuring the query for a UUID takes place within the scope of the desired type not all possible states. This is a one line change - a few more considering unit tests. But then the pattern will be secure against DoS attack.

Longer term solution

This isn't actually hard to implement at all, so we should tackle it as part of the same work as fixing StatePointer.kt.

The idea is we create a new convention for LinearState.id - it's set to the first 128 bits of the transaction ID (Merkle root hash) of the transaction that issued the linear state. Because transaction components include a randomized privacy nonce, this is semantically equivalent to today: the ID of a linear state is randomly chosen. However the crucial difference is that you can't create two different transaction with the same ID, so, by selecting the UUID in this way and checking it in the contract logic, you are assured that the linear ID can't refer to two different chains of states.

This is better because then you don't need a special party that guarantees UUID uniqueness anymore.

There are two sub-problems to solve to enable this design:

1. A transaction cannot contain its own identifier; that would be circular. So a newly issued linear state must have a special UUID of zero, indicating, "look elsewhere for my identifier". The UUID should only be set the first time the state is evolved, at which point the transaction ID of the issuance transaction is available. The smart contract must enforce this rule: "propagate from the prior value, unless it's zero, in which case propagate from the input stateref". We should have a bit of code in the platform that performs the necessary linear ID propagation checks, and invoke it automatically when the app has a sufficiently high target version (as this would be a behavioural change).
2. That in turn means the vault's implementation of LinearQueryCriteria needs to be adjusted to query not only for "states of type T that use the given UUID" but also to query for states where the state ref begins with that ID.

There are some design subtleties here that need care and would get knocked out by a design doc review (may not need a full DRB).

1. I am using the term "transaction ID" above but what I really mean is "StateRef". The difference matters if you have a transaction that creates multiple linear states at once. The UUID must be derived from both the transaction ID and the output index, which is interestingly problematic. Should the UUID be TRUNCATE(H(stateref))? Or is it sufficient to chop 16 bits off the hash, leaving 112 bits of hash + 16 bits of output index?
2. It'd be nice to simplify the developer experience of using linear IDs so the contract logic can be a single method call, which starts being done for you later on. But what about apps that already use linear IDs? They would trigger because the ID would be "wrong". So it implies that, for now, the user needs to opt-in to this behaviour by calling a static method we provide.
3. Can we ensure the Linear ID -> state lookup remains efficient and we don't run two separate queries, despite the more complex logic?

Status

Assignee

Cais Manai

Reporter

Mike Hearn

Labels

Feature Team

Kernel Group

Story Points

13

Fix versions

None

Ported to...

None

Priority

Medium
Configure