Proof of Possession in the Stardust protocol

[lunfardo314]

Proof of Possession in the Stardust protocol

Summary

There's no way to prove possession of certain assets by the address to the Stardust VM on L2 without explicitly sending funds to it. This makes it impossible such contacts as DAO voting based on possession of tokens.

The root cause is a design decision of the L1 protocol: eventual pruning of all transactions and impossibility to extract transaction for an UTXO deterministically.

The least breaking solution it seems to be introduction of the Proof of Possession Feature Block.

Use case

1. for example, we want to implement DAO voting contract based on the principle "1 token = 1 vote". The user sends an off-ledger request to the DAO SC to vote on topic.
2. in blockchain it is trivial to implement such voting because the global ledger state number of tokens in possession per account is accessable globally and deterministic at the moment of counting votes
3. in IOTA L1, UTXO ledger is not the case, because there's no deterministic ledger state on L1
4. in ISC it is easy to write such a voting contract too, because ISC chain it has global deterministic state. However, we face a problem of proving possession of tokens on L1 to the L2 in a trustless manner
5. in the voting request, together with the voting choice for/against the user must provide the (trustless) Proof of Possession of some ledger assets (e.g. iotas, SMR or other tokens) at the moment when votes are counted. That would be a number of votes the user is entitled to.
6. the DAO smart contract will keep registry of votes, it will be deterministic and Sibil-protected. It will make a (trustless) decision on the outcome of voting based on that. The DAO SC itself would be rather simple.

The possibility of such a proof of possession has been envisioned as a part of ISC concept since beginning by including the on-ledger voting request and the Proof of Possession (PoP) into the same request transaction. This way the VM would have a PoP in the SC without any additional trust. In the pre-Stardust implementation it was possible because L2 VM had access to the whole transaction, not just request UTXO.

Specifically:

• Proof of Possession of $N$ tokens by the address $A$ in the moment $T$ is the UTXO where $A$ sends those $N$ tokens to itself with the timelock until $T$. For example I vote with my tokens, so I lock them until announced deadline and expose it as a prove. I do not give up ownership of my tokens
• by including PoP UTXO into the same transaction as a UTXO representing on-ledger voting request to DAO SC, we are proving required fact in the context of the request, i.e. atomically.

Unfortunately, this is only possible if the whole transaction is available in the context of the request. Such DAO contract is not possible with the current protocol design.

Why this is happening?

Absence of the ledger transactions containing unspent UTXOs in the ledger state a serious tradeoff in the protocol.

Main motivation for transaction pruning is optimization of storage. This is justified for the transactions without unspent outputs, however, in general each transaction contains a very crucial information, a proof of atomic ledger update and a proof of atomic inclusion of elements of transaction: inputs, outputs, unlock blocks/signatures etc. The transaction ID is the commitment to the atomic state update. It is important as a context of unspent outputs.

Nodes keep transactions enwrapped into Tangle messages for some time/epochs otherwise nodes wouldn't be able to sync. It is possible to retrieve the transaction for the output while it is still there. However, from the POV of the L2 app, availability of the transaction becomes non-deterministic, because ultimately the transaction is pruned after some time even if it contains unspent outputs.

This non-determinism caused by protocol optimization makes the L1 VM assume the transaction in general is not available. This, in turn, brings about functional limitations and attack vectors, which, when known, should be patched some other way with ad hoc protocol elements:

• inability to securely identify the sender (signer) is solved by the introduction of Sender block, essentially is a commitment to the signature in the output
• fake output attack was mitigated with input commitment in the transaction
• commitment to sub-essence feature block is needed in order to open possibility of fraud proofs on L2 (in the sketch stage)
• proof of possession feature block described here is another example we might need in L1 otherwise certain things are not possible on L2

We may speculate if the list above is final or not (for example, knowing a list of signers of the transaction in SC may be very handy too). In any case, any such addition it a heavy process of updating L1 protocol.

The most flexible solution for L2 VM would be access to the whole transaction containing on-ledger request output in the context of the VMs sandbox.

A plan to go on with the DAO voting

It seems that introduction of Proof of Possession feature block (PoPFB) is the most realistic approach to enable the DAO voting contract.

Here's a sketch for the PoPFB to be discussed.

The PoPFB syntax

(skipping details such as type prefixes and lengths. Real spec may differ)

PoPFB = OwnedAssets [Deadline], i.e. the PoPFB proves certain amount of assets owned by the sender (see below) until optional Deadline.

OwnedAssets is one of:

• BaseTokenAmount (uint64) (amount of e.g. iotas)
• NativeTokenID: Amount (uint256)
• NFTID or AliasID

In those rare cases when you need to prove ownership of several types of assets in one output, you put several blocks of this type into the transaction. Alternatively, the PoPFB may be specified to include multi-asset proof. That would be semantically equivalent.

Semantically, OwnedAssets states that the sender (signer or alias) of the transaction owns (possesses) at least the specified amount of assets until the Deadline, inclusively.

The Deadline, if present, specifies a moment in time (real time and/or milestone index) until which the ownership of tokens by sender of the transaction is guaranteed by the L1 protocol.

If Deadline is absent, the protocol guarantees only ownership of said assets in the context of containing transaction. It means, for the consumer of the output, ownership is deterministically proven but it is not guaranteed otherwise.

The PoPFB always goes with the Sender feature block in the same output.

Validation rules

If PoPFB is present in the output, for the whole transaction to be valid the transaction, the Sender block must be present in the same output.

In addition, the transaction must contain another output or outputs called proving outputs which proves the ownership statement. Specifically:

• for fungible assets, sum of transfers of the asset to the sender's address must be at least the specified amount
• for non-fungible assets (NFTs or Alias Output), the corresponding IDs must be transited in the transaction to the possession of the sender.
• if Deadline is present in the PoPFB, the timelocking or expiry conditions of proving outputs must guarantee for the said assets to be in sender's possession until the deadline:
  • most commonly, proving outputs must contain timelocks until at least Deadline
  • for NFTs and Aliases it is the same
  • the expiry conditions may be used too (not sure, must be checked)

Other

Adding the PoPFB block won't be breaking for the L1. It would require expanding the Stardust VM of ISC with few sandbox functions.

PoPFB will enable possible voting and many other applications on L2.

The client side (e.g. Firefly) will have to be extended with the concept of Proof of Possession. The key point is that by sending on-ledger request to the SC you can add a prove you own some asset(s) for some time by locking it for some time but not giving up the control of it to anybody else. The SC may access the prove and act accordingly to its logic: voting, authorization etc

[lukastanisic99]

Doesn't this make it impossible to vote on multiples things at the same time?

I cast a vote for a governance decision on 1 chain, but my funds are locked until deadline, so I can't vote on anything else until the deadline expires and the UTXO becomes consumable.

[lunfardo314]

no in general, it depends how exactly you timelock your funds. You can lock it in the chain constraint (Alias/delegation/NFT) so that it can be spent only back to yourself until time T (this require certain programmability, not much tho). Then you can use the locked tokens for voting on many different things until time T (you won't be able to change the T nor transfer ownership until T, that is the whole point). The proofs of possession are bridgeless, that is how they are different from proofs of inclusion which require global state root and bridge