Simple information flow control for partial transactions

Protocol Design
1

Background reading

  • Viaduct paper. In the language used by Viaduct, Anoma is a “runtime”, not a language. There are other differences - e.g. Anoma will need to compute acceptable protocols dynamically at runtime, not once in a compiler, and programs for Anoma are written for a local perspective view and composed, not so much top-down like Viaduct - but those can be covered separately in further analysis; we just need something simple for now.

Context

Anoma sends many different kinds of messages over the network - intents, consensus votes, P2P metadata gossip, etc. - and eventually we will want information flow control for all of them. Initially, however, I suggest we start simple, with the most important data - intents (represented by partial transactions). Intents are typically sent by a user to the intent gossip network, sometimes directly to a solver, sometimes not. They then may be gossiped amongst multiple solvers, with partial solving happening, before being submitted to the mempool, ordered by consensus, and executed. The user who authors an intent may want precise control over where the information in their intent goes - perhaps they have a set of trusted solvers, but don’t want any data leaked to the consensus provider. I propose that we craft the right “type” for this kind of precise control, but limit the instantiations to the most useful, simple ones at first (as full analysis of compositional information flow control will take awhile).

Proposal

Specifically, I propose that we add a field to partial transactions called information_flow_predicate, of type PTX \to ExternalIdentity \to {0 | 1}. Conceptually, this predicate is a way for the author of the partial transaction to instruct nodes (especially solvers) who may be processing it who they are allowed to forward the results of processing it to.

Runtime

At runtime - e.g. in the engines related to solving, and wherever else partial transactions are processed, when constructing a partial transaction which includes (by composition) a previously received partial transaction, and deciding whether or not to send this new partial transaction to a particular node (identified by their external identity), Anoma MUST send this new partial transaction only if this predicate returns true, when called on the new partial transaction and the external identity in question.

Instantiation

Initially, instead of being instantiated by an arbitrary function (which would be difficult to analyze), this predicate MUST be instantiated by one of the following options:

data InformationFlowPredicate
  = AllowAny
  | AllowOnly (Set ExternalIdentity)
  | RequireShielded (Set Hash)
  | And (Set InformationFlowPredicate)
  | Or (Set InformationFlowPredicate)

In English:

  • AllowAny allows any derived partial transaction to be sent to anyone.
  • AllowOnly allows any derived partial transaction to be sent to any of the specified external identities.
  • RequireShielded (Set Hash) requires that the included hashes have been wiped from the partial transaction extra data (and associated resource proofs created, in order to make the derived partial transaction valid).
  • And (Set InformationFlowPredicate) requires that all included predicates in the set are satisfied. For example, one might use And (RequireShielded (...), AllowOnly (...)) to only allow members of the listed identity set to view the derived partial transaction, and only after the listed resources have been shielded.
  • Or (Set InformationFlowPredicate) requires that one of the included predicates in the set is satisfied. For example, one might use Or (RequireShielded, AllowOnly (...)) to allow anyone to view the derived partial transaction after the specified resources are shielded, or only members of the listed identity set to view it beforehand.

I think that these predicates should be relatively easy and computationally efficient for a solver to analyze.

Partial transaction composition

When partial transactions are composed, their information flow predicates MUST be and-ed together (e.g. with And (Set InformationFlowPredicate)), to ensure that the properties desired by all prior partial transactions are satisfied.

Thoughts & feedback welcome.

4 Likes
2

Seems generally reasonable, bearing in mind that if any of the people who are allowed to receive the message are less than honest, they may leak information to anyone.

I’m not sure I understand RequireShielded, mostly because I don’t unerstand what partial transaction extra data is. Is removing some set of hashes from the extra data the only way we expect information to leak? What if I encrypted those hashes, and put the encrypted version in the extra data of related transactions? Anyone with the decryption keys could receive the information leak, but nominally, I “followed the policy.”

3 Likes
3

Yes, we will need to specify this more precisely. Typically, some resource data might be passed in extradata before the resource has been consumed (this is especially likely for ephemeral resources), but once a solver has consumed the resource (and probably done other modifications), they can remove this data. I think at least initially we can mostly just try to reason about the behaviour of the default honest implementation, and accept that dishonest nodes may violate the policy in ways that are not necessarily detectable.

4

Makes sense to me as well

How would it be enforced that the partial transactions were only sent to the nodes that satisfy the requirements?

5

You (as a node) can enforce it, and nodes who you send it to can enforce it if they want to - you can’t prevent them from leaking information, but you can choose who you send to in the first place (so this kind of information flow control requires trust, but you still have choice).

2 Likes
6

Could we even remove AllowAny and do that via the All ID and AllowOnly, or does that necessarily introduce overhead?

Maybe the All ID should be hardcoded and canonical, s.t. we don’t need to call into cryptographic operations.

7

Ah I see what you mean - yeah, that might work.

1 Like
8

Scalars

Thinking about IFC for routing, scalars could come in handy, e.g. to express ranked preferences for relay nodes.

IFC enforcement

Do I understand correctly that we assume at least honest-but-curious or trusted agents for the IFC?

Then for PTX or Intents we can as @isheff mentioned not prevent forwarding to 3rd parties, but we could enforce signature checks, s.t. 3rd parties could use intents as side information, but PTX that were solved at unintended solver or so would not be able to be validated.

Do we see this as part of IFC or just as belonging to the realm of PTX predicates (implemented as ephemeral resource logics, I presume)?

2 Likes
9

We should work this out in more detail (probably as part of the next version of the RM report).

I am not sure if it’s correct to see this as part of information flow control, since it isn’t actually controlling information flow, but rather expressing boundary conditions on settlement - it’s more of an “intent flow” control mechanism than an information flow control one. The two choices may often be aligned (e.g. only solvers whose signatures would be valid should be able to see the intent); in principle they don’t have to be, but it seems odd to send intents to solvers who couldn’t solve them anyways. I haven’t fully thought through this though, and there may be reasons why one would want to do that.

In an analogy to Unix permissions which may or may not be helpful, information flow control is like a read permission and signature checks for settlement is like an execute permission.