Generalize view service notes request to get notes satisfying a set of constraints

[plaidfinch]

In support of planning fully general intents, the view service needs to be able to return notes based on more complex constraints. Specifically, we should be able to specify in a single request:

1. How much value is requested from each of a list of exact address indices?
2. How much value is requested from each of a list of accounts (exclusive of the amounts required by 1)?
3. How much value is requested from any source (exclusive of the amounts required by 1 and 2)?

The set of notes returned should satisfy all the constraints, which is to say:

• there are no duplicate notes returned,
• the sum of all the notes for each exact address index is equal to or greater than the sum specified in (1) for that address index,
• the sum of all the notes for each account is equal to or greater than the sum specified in the subset of address indices in (1) which belong to that account, added to the sum specified in (2) for that account, and
• the sum of all the notes returned in aggregate is equal to or greater than the sum specified in (1), (2), and (3) combined.

We can also add a field to specify constraints on the height the note was created or spent, which allows us to fold the voting notes requests into this kind of request. The Lifetime represents two intervals [not_created_before, created_before) and (spent_after, not_spent_after] which bound the creation height and spend height of the note. Any of the fields can be unset, which means that the interval is unbounded on that side. For this interval calculation, an unspent note is considered to be spent at height infinity, which means that specifying not_spent_after = u64::MAX excludes unspent notes, and specifying spent_after = u64::MAX excludes spent notes.

The proposed new request looks like:

message NotesRequest {
  // Specify value to be drawn from a specific address index
  message FromAddress {
    core.crypto.v1alpha1.AddressIndex address = 1;
    optional core.crypto.v1alpha1.AssetId asset_id = 2;
    optional core.chain.v1alpha1.Amount amount = 3; // if unset, demand all; must be set if `asset_id` is
  }

  // Specify value to be drawn from a specific account
  message FromAccount {
    uint32 account = 1;
    optional core.crypto.v1alpha1.AssetId asset_id = 2;
    optional core.chain.v1alpha1.Amount amount = 3; // if unset, demand all; must be set if `asset_id` is
  }

  // Specify value to be drawn from any source whatsoever
  message FromAnywhere {
    optional core.crypto.v1alpha1.AssetId asset_id = 2;
    optional core.chain.v1alpha1.Amount amount = 3; // if unset, demand all; must be set if `asset_id` is
  }

  // All the constraints on specific addresses
  repeated FromAddress from_addresses = 2;

  // All the constraints on specific accounts
  repeated FromAccount from_accounts = 3;

  // All the constraints on the entire set of notes
  repeated FromAnywhere from_anywhere = 4;

  // Constraint on the lifetime of all notes returned
  message Lifetime {
    optional uint64 not_created_before = 1;
    optional uint64 created_before = 2;
    optional uint64 spent_after = 3;
    optional uint64 not_spent_after = 4;
  }

  // Bounds the "lifetime" for all returned notes by this request. If unset, the default
  // is the lifetime constraint of [0, infinity) -> (u64::MAX, infinity], which restricts
  // to all unspent notes, created at any height. (This default is useful because in the
  // case of a spend, you just care about the fact that notes are unspent.)
  Lifetime lifetime = 5;

  // Identifies the FVK for the notes to query.
  optional core.crypto.v1alpha1.AccountID account_id = 14;

  // Authorizes the request.
  optional ViewAuthToken token = 15;
}

Internally, the procedure for fulfilling this request in the view service should be to iterate through the constraints, finding notes that satisfy each. After each constraint is satisfied, attempt to satisfy or partially satisfy all remaining constraints with the excess value beyond that which was used to satisfy all satisfied constraints. Modify all the constraints which were able to be (partially) satisfied by this procedure to reduce their demand, then continue the iteration, making sure to skip note records in the database which already were accumulated. An important note is that constraints with "infinite" demand (i.e. unset amount fields) must be dealt with last or else they will greedily eat up value. So we should solve all the finite constraints first, then fulfill all the remaining ones afterwards.

Note that each voting note request must be made separately for each proposal, because each NotesRequest below only accommodates a single Lifetime constraint. This is intentional, because while it's tractable to solve the constraints when each only demands a typed amount, adding arbitrary interval constraints to each demand makes the problem NP-hard, I'm pretty sure (reduces to knapsack). But also, multiple NotesRequests for multiple proposal votes is precisely what you want: because the design of the NotesRequest is to return non-overlapping sets of note records, it wouldn't actually tell you, for each proposal, which notes you can use; you'd have to do that logic again, in the client. Instead, you should (as presently) make a separate request for each proposal you want to vote on.

[plaidfinch]

CC: @aubrika, this is what I think we should do with the view service.

[hdevalence]

I'm not sure I understand why we need this, rather than the (much simpler) request we already have, which allows filtering at account-level granularity. What's the concrete use case here?

[hdevalence]

Implementing this API will be a lot of work, and it's not clear what benefit it gives over the existing API, or who the intended consumer is. I don't think that this will be a good use of resources prior to mainnet, rather than working out the more basic problems we already have with the Plan/View system. Since none of this is consensus-critical, we can always improve it after we ship and have actual users running into problems with the system we built initially.

[plaidfinch]

The intended consumer is the compiler from a transaction intent to a transaction plan, i.e. the planner. This has not been fully described because I haven't had time to articulate the transaction intent design yet. I am re-opening this issue in "on hold" status as per https://github.com/penumbra-zone/penumbra/issues/2076#issuecomment-1466577607 so that we don't lose track of this (partial) design work in the future when we do have resources to allocate to this work.