[Resolved] Interpretations of UTXOs

Aztec
, ,
1

I asked a question on Slack the other day, but I think there’s more to squeeze out of this discussion, so here’s some background, followed by some new points/questions…

Original Q

The question I asked:

"
UTXO question, maybe for Zac:_
If a storage slot is used in multiple not-yet-nullified UTXOs (i.e. the ‘unbounded array-based utxo representation’), the only way my brain can currently think to interpret that is:

  • the ‘actual’ value of the storage slot can be deduced by treating the value within each UTXO as a summand, and summing all of these summands.

To broaden my brain: are there any other example interpretations of an ‘unbounded array-based utxo representation’ of a storage slot?
"

Background

Zac wrote this nice proposal for UTXOs and Private State Semantics. Definitely read it before continuing.

Responses so far to the Q

From Zac:

The mental model in my head is that, for the purposes of storage slots, we treat UTXOs very much like Solidity mappings.

If a contract has a private storage variable that represents UTXOs (e.g. private UnboundedArray<uint> values, that variable is given a defined slot number (e.g. values.slot = 4 if its the 5th storage variable in the contract).

However each actual UTXO object has a unique slot number, which is the hash of the slot number and a given UTXO commitment. e.g. slot = Hash(values.slot, singleValueNote.commitment.

This is similar to how mappings are treated in Solidity. e.g. imagine we have mapping(address => uint) values and the contract writes a value values[msg.sender] = 10, under the hood, the storage slot will be defined as keccak(msg.sender, values.slot) and the evm code will do the equivalent of sstore(keccak(msg.sender, values.slot), 10).

In the EVM model, the mapping ‘key’ is hashed with the variable slot to get the object slot.
In the UTXO model, the UTXO commitment is the equivalent of the mapping ‘key’.

To clarify a bit more - the mental model I have treats UTXOs as distinct objects with unique slot numbers - derived from a variable slot and the UTXO commitment.

At the protool level there is no concept of a ‘value’ represented across multiple UTXOs (e.g. automatic summing) - you need to code that up yourself as a contract writer if you want it.

(this touches on the doc I wrote about private state semantics - https://hackmd.io/np0KGkUWRbqQf7n7EWt9xg. The idea is that treat UTXOs as UTXOs and don’t attempt to create protocol-level (or language-level) abstractions that pretend a set of UTXOs are a single variable. Instead we provide enough flexibility in the Noir++ language to allow devs to code up ways of effectively manipulating UTXOs so they can create subroutines that perform UTXO summing and similar actions).

(TLDR: we do what Solidity does and we treat UTXO collections like mappings)

Continuing the discussion

Zac’s mental model makes sense to me - I just have some questions.

Q1:

Consider a mapping to collections of UTXOs:

private mapping(address => UnboundedArray<uint256>) collections;

I’ll call each entry in the mapping a “collection of UTXOs”.

As per Zac’s comments, and as per Solidity, collections[mike_address] would live at storage slot keccak(mike_address, collections.slot). It makes sense to ascribe a storage slot to a “collection of UTXOs”.

But I’m not sure about the need to ascribe a “storage slot” to each UTXO within a collection of UTXOs.

My mental model is that each UTXO in a collection of UTXOs should be interchangeable, or ‘fungible’ in some abstract way. It feels like the information contained in the value field of a UTXO’s preimage should be the only way to distinguish between the UTXOs at a particular ‘proper’ storage slot (rather than ascribing each UTXO in a collection a unique “storage slot”).

I’d hypothesise that if someone needs each UTXO to have a unique ‘storage slot’, then they should probably be using an array, struct or a mapping to achieve their goals.

Q2:

Defining the ‘storage slot’ of a particular UTXO commitment to be slot = hash(collections[mike_address].slot, commitment) seems cyclic.

The storage “key” is being derived from the “value” being stored, which is unconventional, and feels problematic.

Also, usually states are accessed based on meaningful state variable names. But looking-up a state w.r.t. a ‘commitment’ isn’t ‘meaningful’ in the same way. I’m not sure I see the need to differentiate between each UTXO in a particular collection, in terms of ascribing ‘storage slots’ to each of them.

Q3:

I’d like to see some concrete examples of other interpretations of a ‘collection of UTXOs’, to justify the extra complexity of allowing devs full control over UTXOs.

The only example interpretation I’ve seen of UTXOs is to represent a single value, when the UTXOs are summed. E.g. bitcoin, zcash, aztec.

Here’s my attempt at trying to come up with examples to support the notion that an Unbounded Array of UTXOs can be used more generally than just ‘summing values’:

Spoiler alert… I wrote a framework below, and then actually came up with some examples! You can see the moment it clicked!

Hypotheses

  • The only time a dev would need a private state variable to be ‘split’ across multiple not-yet-nullified UTXOs (a.k.a. a “collection of UTXOs”), is if they would like someone other than the owner to insert a new UTXO into that collection, in a way that’s parallelisable and doesn’t cause collisions.
  • A “collection of UTXOs” should only be used to ‘combine’ a (possibly infinite) collection of identical ‘types’.
  • Any two UTXOs in a “collection of UTXOs” should be ‘combinable’ into a single UTXO of the same type. E.g. nullify two and create one to represent the ‘combination’ of them both. If a collection of ‘things’ doesn’t meet this property, then the ‘things’ must be distinct in some way, and therefore I’d suggest each ‘thing’ should inhabit its own ‘proper’ storage slot, and therefore a “collection of UTXOs” isn’t a suitable type for those ‘things’.
  • The ‘proper’ storage slot of a variable which points-to such a “collection of UTXOs” would always represent the ‘statistic’ or ‘combination’ of that collection.
  • I’d suggest for many cases, we wouldn’t need to use a “collection of UTXOs”: a different container, such as a struct, array, or mapping could be used instead. We could either entirely compress such a container into a single UTXO, or split each element of such a container across multiple single UTXOs where each UTXO is located at a distinct, ‘proper’ storage slot. The latter is different from a “collection of UTXOs”.
    • Even if we want someone other than the owner to be able to insert a thing into a set, a mapping could often be used instead - e.g. if each element in the mapping is mapped-to from a user’s address.
    • Note: an array seemingly doesn’t fulfil the requirement to be able to add to a collection ‘in parallel and without collisions’. But a public function could determine the ordering of pushing partial-commitments of private values to an array, by ‘completing the commitments’ with a storage slot.

So what examples can I come up with, other than summing values, for which an unbounded array of utxos would be useful…:

I list some below [and suggest in square brackets why an unbounded collection of UTXOs might not be necessary].

  • A sum of numeric types in a collection, to represent a single summed value.
  • A count of items in a collection
    • [A ‘count of items’ doesn’t fulfil the requirement that two items can be combined into a single UTXO, since then the count would reduce from 2 to 1].
  • The weighted average of values in a collection.
    • [Maybe this fits into a ‘collection of UTXOs’ model if each value itself represents a ‘weighted average’ (since then two UTXOs could be combined into one, and the resulting UTXO would still represent a ‘weighted average’), but that’s quite abstract, and I can’t think of a real-world use for this, and you could probably perform this calculation on single UTXOs which each inhabit a distinct storage slot of a mapping, for example].
  • The median / standard deviation / variance of values in a collection
    • [as above]
  • A collection of strings, interpreted as a single string or sentence.
    - Possibly…
  • A geometric or topological property of items in a collection, e.g. area or volume of a group of objects.
    • Hmm… this has led me to something more general…
  • A collection of private structs of the same type, where the struct describes something fungible.
    • E.g. an inventory of apples. Apples are pretty interchangeable. No one cares about keeping track of each.
      • Bob adds an item to Alice’s collection: { type: apple, quantity: 300, weight: 1 kg, average_weight: 3.33 g }
      • Charlie adds an item to Alice’s collection: { type: apple, quantity: 100, weight: 0.2 kg, average_weight: 2 g }
      • Now… these can be combined into a single UTXO of the same type, based on custom logic which is not simply summation: { type: apple, quantity: 400, weight: 1.2 kg, average_weight: 3 g }
      • Oooh, interesting!!!
  • Summing a collection of complex numbers
  • Summing a collection of polynomials
  • Multiplying a collection of numbers, such as annualised compound interest rates.
  • Combining a collection of sets of pixels to construct an image. (E.g. contributing to privately to some (likely very messy) artwork or collage)!
  • A collection of functions, being combined into a single function?
  • A collection of snarks, being rolled-up into a single snark?

Q4: Any other nice examples?

Q5: Is there a nice generalised description for what a collection of UTXOs should be used for?

Q6: Can any of these examples be done without a collection of UTXOs? Or rather, which of these examples can only be done with a collection of UTXOs?

11 Likes
2

Heya, still reading through this will answer as I go

Re: Q1, I have reservations about treating UTXOs as fungible at the protocol level because there are many cases where this isn’t the case.

It also adds protocol complexity to treat them as fungible at the protocol lager because we’d be creating an abstraction layer that treats UTXOs as …something that’s not a UTXO.

Imo we’ve fulfilled our responsibilities at the protocol level if contract devs can code abstractions of their own that can represent fungible assets via UTXOs. Iirc the doc I wrote had an example.

—-
Q1 continued: why we need independent storage slots per utxo

A UTXO is a unique piece of data regardless of whether we want it to be or not. We need a way of individually accessing that data and I don’t see a way that can be done unless we give each UTXO a unique slot number

6 Likes
3

Re Q2 yeah that’s a good point

I think we can treat UTXOs closer to mappings, where the key is a combo of:

1: variable slot number
2: address of utxo owner
3: index of utxo in the unbounded array

E.g. consider the UnboundedArray dogCoin. Mike has 5 dogCoin UTXOs. The 4th utxo has a slot number that’s equal to:

H(dogCoin.slot, address(Mike), 3)

5 Likes
4

Re: examples of non fungible UTXOs. NFTs would be one.

If our old CreditMint idea was implemented on A3 then each syndicated loan would be a large struct of data represented as a UTXO (it’s useful to know total size of the loan book for a fund but you may want to apply filter conditions on the loans you’re summing)

You could have semi-fungible assets e.g. a collection of loans. Each loan could have a value and a collateralisation ratio.

You may want to do conditional sums on the above (e.g. sum of loans with collateralisation ratios below 1.5)

Gaming NFTs could fit the description here. E.g. a token with a public value and some secret data. The contents of the secret data defines whether the public value can be summed into a single value (a bit abstract this one)

Aztec Connect claim notes aren’t fungible but their natural representation in an A3 contract would be an unbounded utxo array.

4 Likes
5

I think there’s been a misunderstanding. This entire post was centred around discussing the “UnboundedArray UTXO type”, which I refer to as a “collection of UTXOs” in the post. So all of my questions relate to that type only.

So I’m completely ignoring any discussion about singleton UTXOs here. Singleton UTXOs make sense to me. I’m solely focussing on when a ‘conventional storage slot’ points to an unbounded array of UTXOs and how such an array can be interpreted.

4 Likes
6

I was also thinking about unbounded arrays when I gave those examples :o

To step back a bit, let’s discuss why we need UnboundedArray (UB) and where it’s useful?

Imo UBS are needed when a user is the owner of a UTXO they did not create.

E.g. Alice gives Bob 10 duckaroos or similar.

At the database level, the UTXOs that represent an A3 state variable form an unordered set.

Q1: what protocol level abstraction layer do we want as some variables will represent a fungible quantity and others do not

There are 3 categories of UTXO collections in this context:

1: fungible
2: non fungible
3: conditionally fungible

Option 3 is fiddly and somewhat novel vs Ethereum. I’m thinking of assets that are nominally fungible but each utxo holds secret data that determines fungiblity conditions. Let’s ignore for now.

Let’s take a non fungible example: the NFT.

Nominally a regular mapping would work for NFTs even if they’re in utxo form. However there’s an NFT pattern that presents a problem: enumerable NFTs.

An enumerable NFT on Ethereum has a mapping that maps a user address to a dynamic array of the NFT ids that they own.

You can’t replicate this with private UTXOs. If Alice gives Bob an enumerable NFT, the contract cannot ‘push’ the nft id onto an array because Alice does not know how many NFTs Bob owns.

More generally, we cannot support dynamic arrays of private objects that are owned by a user but can be pushed to by entities that are not the user.

4 Likes
7

There is another question I think is worth discussing here as well.

Q: Should the protocol present an abstraction layer that hides the underlying data type of variables?

For example, UTXOs that compose an integer. Sum of a users UTXOs equals the ‘value’.

The underlying data type is an unordered set of UTXOs, whether we want it to be or not; those are the leaves going into the A3 Merkle tree.

The desire, as I understand it, is to present this at both the protocol and language level as an integer.

I don’t think this can be done without creating UX hurdles and domain knowledge burdens to developers.

Let’s consider what would have to happen to achieve the abstraction layer for ‘private mapping(address => int) balance’

  • if balance[user] equals ‘value’, the contract must be able to deduct arbitrary amounts from ‘value’ (given access to users decryption key). This means either nullifying all of the users UTXOs at the protocol level (how?) or always representing a user’s ‘balance’ as one UTXO
  • when !owner adds to the variable, owner needs to automatically generate a proof that combines the new UTXO with their existing UTXO because of the above condition
  • this ‘merge’ transaction must happen before the user can create transactions that modify ‘value’ and it will cost the user tx fees as they will be generating new notes and nullifiers
  • the operations available to the developer are not consistent with the canonical understanding of the ‘int’ type. You can’t do anything other than add unless you own the variable. An abstraction layer that requires the user to understand the concepts being abstracted in order to use it is a bad abstraction layer!

Why is it the responsibility of the protocol or the client software to handle any of the above? It adds complexity and makes several assumptions about how developers will use UTXOs that are both restrictive and untested.

If we hide the underlying data type we will 100% create situations where developers have to fight against the abstraction layers we create, which is not a good place to be.

This is why the UnboundedArray concept exists. It does not hide the underlying data types from developers. It does give contract developers the tools and flexibility to create user-generated libraries that can treat an unordered set of UTXOs as a fungible integer. Imo this gives us the best of both worlds.

4 Likes
8

To give an example of fighting against the abstraction layer and causing problems:

Let’s say we have a private ‘int’ abstraction to represent fungible UTXOs.

Dev wants to make a loan platform. They need to subtract from a users balance, but they can’t. So what to do?

Logical solution is to create a ‘credit’ variable and a ‘debit’ variable. A user cannot create a valid transaction unless their credit > debit

Problem solved? No! The act of aggregating UTXOs under the hood is a user-side opt-in process that cannot be enforced at the protocol level as the protocol does not know how many UTXOs a user has.

A user can therefore refuse to accumulate their ‘debit’ notes and, when the contract checks credit > debit, they give the contract their smallest debit note. This allows a malicious user to drain the contract of funds.

This problem is not intuitive to non-cryptographer devs

What do they have to understand to avoid this foot gun? They have to understand UTXOs! The primary goal of the fungible int abstraction layer has failed. Worse, it leads devs towards coding patterns that look idiomatic but in reality are extremely dangerous

3 Likes
9

Note for posterity:

Zac & I had a chat about all this. The original post was slightly misinterpreted.

The original post was basically:

  1. Suggesting that we don’t need a storage slot per UTXO in an unbounded utxo array (but simply a storage slot representing the entire unbounded array).
  2. Supporting the proposition that an unbounded utxo array can be used for more than just summing variables, with a long list of examples.

The subsequent answers misinterpreted point 2.; thinking I was arguing against flexible control of utxos, whereas I was coming round to the idea. The original post could have been clearer, for sure.

Anyway… the long and short of the chat was:

  1. UTXOs in an unbounded array of UTXOs can be treated somewhat ‘interchangeably’ (or ‘fungibly’), in the sense that there won’t be a storage slot per UTXO. An SLOAD won’t specify a particular UTXO by some ‘utxo storage slot’ when dealing with an unbounded array. The sort and filter functions of an SLOAD will just whittle-down the entire collection into a few UTXOs that can be opened / modified / nullified within a circuit, based on the contents of that UTXO. Notably, each UTXO belonging to a particular unbounded array, will contain in its preimage the same storage slot.
  2. Yep, unbounded arrays of UTXOs won’t always be sums of values, but can have more general uses.
3 Likes