Considerations for locked states

[awrichar]

In reviewing the latest "lock states" functionality (added in #110), I'm trying to understand the current overall state model of Zeto, and whether it can be considered a UTXO model or something else entirely.

For the most part, Zeto follows UTXO - states have a value and an owner, and they can be spent exactly once as an input to a transaction. However, with the addition of "locked states", each state can now have additional metadata specifying whether or not the state is "locked". In the UTXO world, this seems similar to a "spending rule" or "script", as used in systems like Bitcoin and Cardano. However, the Zeto implementation appears to be novel because you can attach or alter this metadata without spending the state. Consider:

• A - $100 coin, spendable by whoever can generate a valid proof
• A' - same as A, but only spendable by one specific address

As of #110, it's possible to transform A to A' without spending A. And from there it may transform back to A, or to A'', etc. This presents problems when trying to index Zeto coins. A normal UTXO indexer deals in very "final" operations - a state comes into existence exactly once, and gets spent exactly once. With this notion of mutable spending rules, a much more sophisticated indexer would be needed - one which tracks that A may become spendable or not spendable at various moments throughout its lifetime, based on a set of changing rules.

Given this, I believe there is a fundamental choice to be made in terms of Zeto's future design around "locks":

1. We conform to UTXO, meaning that A is spent to generate A', and we explore the implications for ZKPs under this constraint (for instance, can we create a proof that is valid to spend either A or A', because it relies only on the owner/value of A and not on the "locked" status?)
2. We design a novel system of "UTXO with mutable spending rules", and figure out the implications for building a robust indexer for such a system

[jimthematrix]

Thanks @awrichar for initiating the discussion.

A fundamental assumption of the observation above is the fact that a UTXO can only have one state transfer verb, "spend". I would argue that this assumption has already been violated with the usage of nullifiers. When using nullifiers, a UTXO's state doesn't change at all, but instead a separate mechanism of tracking nullifiers are utilized to avoid double spending without anybody knowing which UTXOs have been "spent", except for the UTXO owner, or a centralized trusted party such as the notary in the case of the Noto token implementation.

This means an indexer with special knowledge beyond the simple "spending" verb already has to be built to support the special lifecycle needs for a privacy preserving token. So the argument that sticking to a "spend-only" state model would simplify the construction of the indexer isn't very strong.

[awrichar]

@jimthematrix I don't think nullifiers change the execution graph of the UTXO model - they just change the mechanism by which you spend. A state is only spendable if you can generate the proper nullifier for it. To facilitate this, in Paladin we have taught it about this specific spending rule, and it is turned on at a contract level (to say "all states in this contract must be spent by generating nullifiers"). Another option of course would be to have more "generalized" spending rules spelled in a DSL, such as other UTXO models have adopted - but that's a big lift and we haven't yet decided to take it on.

But that's a huge difference from states that change their spending rules on the fly. I can't have a state that was generated without requiring nullifiers, and change the spending rule to say that from this point, it will have to be spent with a nullifier instead. This is the big difference I see with the current locking behavior - the rules around spending UTXOs are not fixed throughout the life of the UTXO, but they can change independent of the UTXO itself.

[jimthematrix]

Correct, which I think is the same when a UTXO is spent and the new UTXO in the output has different spending rules than the ones that just got spent. The indexer still has to react on a per UTXO basis based on each UTXO's spending rules. Not sure I see yet a big difference b/w the current implementation of keeping the same UTXO id but updating the spending rules vs. the proposal to spend and create a new UTXO with a different spending rule and a different ID.

[awrichar]

I think the following are generally needed to be able to index UTXOs:

1. Each UTXO can be uniquely identified
2. Each UTXO can only be spent once, and can't go back to "unspent" after being spent

I believe you're saying that to satisfy (1), an indexing system could elect to identify UTXOs by the union of (UTXO id, locked status). Therefore if A transitions to A' by changing the locked status but not the on-chain id of the UTXO, the indexer could consider that A is spent and A' is a new state.

However, if A' is altered to remove the "locked" status, this would turn it back into A again, which would involve A transitioning from "spent" to "unspent", and would violate (2) above.

I think (2) is a pretty fundamental rule of a UTXO system, so I'm having trouble coming up with an indexing model that doesn't require it to be true.

[jimthematrix]

No argument with the above assertions. I think we are narrowly defining all state transitions in an UTXO systems as spending, so there can be no other types of state transitions such as locking which can be reverted without spending the UTXO.

I tried to search for formal UTXO definitions in the academia space, such as researchgate.net and mdpi.com, but haven't found any unfortunately. If there are such definitions that clearly spells out the above assumptions, I think we have an easy decision to make.

In the absence of that, I'm trying to discover the benefit of the above assumption. One obvious benefit is the fact that it leads to a DAG type state transition graph that is more efficient to manage than the graphs that have cycles. For instance in the DB storage design for implementing a Zeto client, we can have an append-only scheme by inserting new records to reflect state transitions, rather than relying on updates. Such schemes result in higher performance. This is the current design of Paladin.

[awrichar]

It's not particularly academic, but I asked ChatGPT about it and generally got what I'd expect: https://chatgpt.com/share/6776f6c1-c090-8012-9338-ce1d73120415

I don't know of any current UTXO systems that allow for a transition other than "spend", or that allow for cycles in a state graph.

[jimthematrix]

In the UTXO model, scripts cannot be changed on the fly. Instead, to modify the conditions or script associated with a UTXO, you must:

- Spend the UTXO (fulfilling its current script requirements).
- Create a new UTXO with a different script.

This is because UTXOs are immutable once created. The immutability ensures the integrity and security of the blockchain, as any changes to a UTXO would undermine the consensus rules.

and

Why UTXOs Can’t Change Scripts on the Fly
- Immutability: UTXOs are a fundamental part of the blockchain's ledger state. Changing them directly would break the chain of cryptographic proofs linking transactions.
- Determinism: The UTXO model relies on deterministic validation. Every UTXO’s state must be reproducible across all nodes in the network. Allowing mutable scripts would introduce complexity and potential inconsistencies.
- Simpler Validation: Keeping UTXOs immutable ensures that nodes can easily verify whether a UTXO is valid without tracking dynamic state changes.

I think the above are the most relevant part of the ChatGPT response. However they are in the context of a blockchain protocol based on UTXO. In a UTXO system built on EVM, immutability and determinism are guaranteed by the underlying protocol (account based) already. So I don't think having a UTXO design that can alter its spending rules fundamentally breaks anything (again this is without having authoritative sources on what UTXOs should be).

[jimthematrix]

That said, I'm leaning toward changing the lock mechanism to spending rather than modifying as you have proposed, for the benefits discussed so far related to client implementations.

[awrichar]

Right - we definitely could have a system that is UTXO-like, and yet has more complex rules (such as having states other than spent/unspent, and more allowable transitions between states). Would it still be called UTXO? Maybe. Like you said, there's really no authority that will determine yes or no. That's a more academic question when you get down to it.

I'm mostly concerned with 1) properly describing the state model to others, and 2) making it easy for anyone to efficiently index Zeto contracts. Adhering to basic UTXO and ensuring indexing can be built in an append-only fashion definitely help on these counts.

[Chengxuan]

Great thoughts.
Here is what's Zeto today as per my understanding:

• (base). Zeto follows UTXO model
• (locking). Zeto provides an extra function (optional) to record locking states on chain.
  • Zeto has other optional functions (e.g. kyc, erc20 anchoring)

Also, locking can be implemented without using this optional function:

• (escrowlocking). transfer the amount to an escrow address
• (externallocking). UTXO owner have external web3/web2 app to manage the locking states. (locking states are not recorded inside the coin contract in any way)

In the conversation, I saw the following threads that have been discussed:

1. exploring whether locking should become a required feature (part of base) by influencing the definition of UTXO model
2. have better/more formal documentation on the interaction pattern when the locking is used
3. remove locking, and encourage locking to be handled outside coin contract to be the best practice.

I think 3 is probably OK for designing a coin that follows the existing UTXO model. 2 is a stepping stone towards 1 and is an interesting area to explore, however, I don't think it's a Zeto-specific thing (at least at the interface level).

[awrichar]

@Chengxuan I think some form of locking and delegation must be standardized and provided in base Zeto. Otherwise there will be no standard way to implement any form of atomic settlement using Zeto.

Zeto tokens can only be held by EOAs, as you must generate BJJ keys and ZKPs in order to move them. They can't be held by other smart contracts in the way that ERC20 can, for example. Therefore, the only way to provide programmable atomic constructs is to let an EOA set up the proofs and states, and lock them to be finalized by a particular address (which may be an EOA or smart contract).

Similar to how most ERC token standards are built, I believe a token needs a minimum of two capabilities:

• ability to transfer value
• ability to delegate/approve some other address to transfer value on my behalf

[Chengxuan]

I do think locking and delegation are two different things and we should not mix them together. my understanding of delegation is how approval works in erc20: it sets a limit for some other address to transfer values but not prevent that amount of tokens from being spent. (e.g. I can approve A to spend 80, but I can still spend all my tokens).

[awrichar]

@Chengxuan correct. But with Zeto I think there's no way to say "A can spend any amount of my tokens in any number of different transactions, totaling up to a max of 80" - at least not in a way that is guaranteed in the smart contract. @jimthematrix is more of an authority on what's possible with the ZKPs, but because of the way value is tracked, I don't think we can do this in the same way it's done on ERC-20.

What we can do is say "I approve A to spend exactly this set of UTXO states", and pre-select a set of states totaling 80. We've landed on "locking" the states while the approval is in effect, simply because it's much too easy to accidentally go and spend those states on something else and therefore invalidate the approval (that was the focus of #110). You could argue for a less reliable form of approval where A has no idea if the states will continue to be valid or not - I'm not saying it's useless, but I don't know under what scenario you would want that instead.

There's another form of delegation sometimes called "approval for all" that's used in ERC-1155 and some other standards. It's something we haven't explored in detail, but I think Zeto could potentially support this pattern of delegation as well, if there was a use for it. But it would be a different ZKP.

In summary I think we have:

1. approve someone to spend a specific set of states
2. approve someone to spend any arbitrary set of states totaling up to a maximum
3. approve someone to spend any of my states

I believe 1 & 3 are possible, and 2 is not possible.

[Chengxuan]

@awrichar my understanding is also 2 is not possible without a client that does the amount <--> UTXO translation/break up.

I think it worth clarifying the problem we are trying to solve there.

Reading this issue

I think what we are trying to solve is enabling a smart contract address to spend Zetos even though a smart contract address:

1. it can't spend any tokens, because it won't be able to generate ZKP (doesn't have any BJJ key).
2. it doesn't have any indexing capabilities and needs to rely on the Zeto contract to validate the value <--> hash mapping using a ZKP provided by the owner

In addition, if a locking is amount based, there will need to be some translation between the amount and UTXO. E.g. I want to lock 1 (value), but the owner only has one UTXO with 10, what should I do. (this translation is often a client-side job for a UTXO-based system).

Another important aspect to consider is: any ownership/transaction information should not be revealed in the Zeto contract due to the locking.

One possible solution could be: the locking method consumes all the input UTXOs and generates 1 UTXO (change) to the owner (A) and 1 locked UTXO that can be owned by either A or B when finalized. the "finalize" function

1. must be called by the locking contract
2. when it's called the first time, the owner of the locked UTXO is decided and the UTXO becomes spendable by that owner (ownership decided and immutable).

@jimthematrix @awrichar ^^ wonder whether that's something feasible and worth exploring/ aligns with your thinking. I've not thought through the whole data flow to ensure the parameters needed for the lock and finalize method don't reveal UTXO ownership/transfer information.

[awrichar]

Yes, I believe this aligns with where we're going. You've summarized mostly how the Noto implementation of locks is now proposed to work on Paladin, and based on discussion here and #118, it feels like Zeto is trending in a similar direction ("locking" means spending the inputs and generating some number of "locked" outputs along with a refunded "remainder", if necessary). All preparation of input/output states and proofs has to be done by a client, but spending of locked value can be delegated/finalized by a smart contract address.

One major goal here is to enable Zeto to be atomically swapped with any other token (either an ERC20, or Noto, etc). So you're exactly right with enabling a smart contract address to spend Zetos, and additionally we want to be sure Zeto offers a way to give some counterparty protection in the window between when I delegate spending ability, and when the spending happens.

[jimthematrix]

agreeing with the above conversation @Chengxuan @awrichar. No additional comments to add.

Something I'd like to call out as a potential significant decision as I got further with the idea to "spend the UTXOs and create locked UTXOs in the output". @awrichar and I have had some preliminary discussions about this.

When I initially implemented the new locking function for the non-nullifier token implementations, both for fungible and non-fungible tokens, it was pretty straightforward to do:

• the locked UTXOs are managed in the same map as regular (unlocked) UTXOs, but additionally marked as locked in a separate map for all locked UTXOs
• the lock() function is a regular transfer plus adding the locked outputs to the locked UTXOs map
• the transfer() function is enhanced to check that the inputs are either unlocked, or are locked and the transaction submitter is the designated delegate according to the locked UTXOs map

This works pretty well, with a small overhead in all transfer() calls, to check the inputs against the locked UTXOs map. The benefit is that we can use a single transfer() function for consuming both unlocked and locked states.

However when I got to tokens using nullifiers, I realized that to keep using a single transfer() function, it would have to proof two things:

1. that the nullifiers are bound to UTXOs in the regular UTXOs merkle tree (which is already included in the proof statements), aka inclusion proof
2. that the nullifiers are bound to UTXOs NOT in the locked UTXOs merkle tree, aka non-inclusion proof

Both statements are required for every transfer() call. This is going to make the transfer() function very expensive, especially on the prover side.

On the other hand, if we maintain the locked UTXOs in a separate list, and have two separate functions for spending unlocked vs. locked UTXOs, then each transfer function only needs to deal with one inclusion proof.

I'm leaning toward tracking unlocked and locked UTXOs separately and having two separate functions for spending unlocked vs. locked UTXOs.

BTW regardless of the approach, for checking against the locked list in a nullifier based token, we need the merkel tree to record the UTXO hash as the key and the delegate address as the value. In the proof to demonstrate inclusion in the locked UTXOs, the proof must use the delegate address as a public input.