SNARK Account Predicates

[evan-forbes]

In the original forum post and in other sync discussions, we've briefly discussed what a validity predicate would actually be for a rollup that controls a SNARK Account. We can continue those discussions of what different predicates for SNARK accounts would look like, what they would require from the state machine (ie perhaps an apphash), and what they would be useful for here.

[staheri14]

Thanks Evan for opening the discussions. Among the three discussions underway (i.e., this and this), the current one is the most pivotal, as it has the potential to significantly alter the course of the other two conversations.

Context and Notation

I’d like to introduce some formal notations and context for clarity:

Consider a SNARK account associated with a predicate(x, w), where x and w are the public and private inputs, respectively. The predicate represents the specific condition or statement that must be verified as true for any transactions linked to that SNARK account. More specifically, for a withdrawal from a SNARK account to be possible, the transaction issuer must possess a private input w for a given public input x. This input is required to fulfill the condition expressed as predicate(x,w) = 1, where 1 denotes that the relation is valid. To this end, an incoming transaction carries a proof which would be used to verify this relation and the knowledge.

One example would be a SNARK account that permits withdrawals only if the issuer knows the preimage w for a hash value x. In this case, the predicate checks whether h(w) equals x.

To identify the public inputs for SNARK accounts, it's essential to first define the specific predicates that the account is designed to verify. Once this predicate is established, the associated public and private inputs can be more clearly understood and defined.

Discussion Points

In order to foster a thorough and structured discussion, I suggest addressing the following questions sequentially.

1. What specific predicates would an SNARK account be associated with? Enumerating various scenarios where these accounts are necessary could provide insight into the range of predicates that are relevant.
2. Is the predicate specified in the previous question versatile enough to be applicable to all kinds of rollups?
3. If the answer to the previous question is no, then what are the prospects and potential advantages of introducing generic SNARK accounts, where account holders can select the predicate, or hybrid SNARK accounts, which allow predicate selection but also expect specific public inputs (like the hash of the last or nth Celestia block, optionally used by the predicate)? While further feasibility analysis is needed, gathering preliminary opinions could offer valuable insights into the practicality and demand for such flexible account types.

[evan-forbes]

Great idea and those are really helpful questions!

1. I think we could get a lot simpler and more efficient than this, but just to start

public inputs:

• s = last commitment to state
• s’ = next commitment to state
• d = some celestia data root
• y = hash of SNARK tx

x = (s, s’, d, y)

private inputs:

• preimage to s
• preimage to s'
• preimage to d
• some subset of the preimage of d that is the canonical block for that rollup, calling that d'
• preimage to y

w = (
preimage to s,
preimage to s',
preimage to d,
d'
preimage to y,
)

Predicates

• Prover knows a preimage for y, d, s, and s’
• The prover knows some subset of the pre image of d that follows the forkchoice rule of the rollup, lets call it d’
• The tx in d’ is valid and the signature is valid
• When applying that transaction to the preimage of s, we get the preimage of s’
• The prover knows an account that is committed over by s’ that matches that in the preimage of y, and the amount to be withdrawn also matches that in s’

Given the last and next commitments to state, the commitment of the block data, and the snark tx, the prover can prove that some tx was applied correctly to the rollup state, and in the new rollup state there is an account wanting to withdraw that matches that in the tx.

2. for many normal rollups I think this could work. At the moment its relying on the old app hash being stored in the Celestia state machine, along with the data roots (as I'm assuming that the user will specify which data root they are pointing to). We might be able to avoid that by the rollup proving not only the current block, but also the entire chain history. We could also avoid passing the celestia data root if a celestia light client was also part of the predicate

3. What would be an example of a non-hybrid snark account?

[musalbas]

Note, we shouldn't need to add pre- and post- state roots as inputs. With the original idea this shouldn't be a requirement. Additionally, this would make it so that only one withdrawal can be processed per block, which should be avoided. Rather, the there could a private input for the previous SNARK proof for the previous block:

By tying calldata back to the L1 block headers, we can add a statement saying “I have scanned the DA layer for proofs (starting at block X and ending at block Y), and this proof builds on the most recent valid proof”. This lets us prove the fork-choice rule directly, rather than enforcing it client side! And if we’re already scanning the DA layer for proofs, we can easily scan for forced transactions as well.

[evan-forbes]

this is just ideating on what could be some of the public inputs. As you wrote in the forum post, its definitley possible to have a mina like setup with recursive proofs instead

Additionally, this would make it so that only one withdrawal can be processed per block, which should be avoided.

Do you mind elaborating on how having a state root limits withdraws to a single account?

[musalbas]

Do you mind elaborating on how having a state root limits withdraws to a single account?

This issue is that if each withdrawal immediately updates the state root of the rollup, then don't you need a lock on the state root, thus the entire state of the rollup?

[staheri14]

Thank you, Evan, for your comprehensive feedback; it was instrumental in shaping the user story and validity rules, and also in determining whether a generic SNARK account is required or if a specific predicate can be universally applied to all rollups. Here's my interpretation of the user story and rules (inspired by your feedback), with minor modifications and a revised narrative approach.

We're examining a scenario where a transaction tx' occurs within a rollup, encapsulated in a roll-up block d’. The rollup's state before tx' is denoted as s, and the state post-execution is s'.

Based on state s', an amount should be transferred from a Celestia SNARK account from_acc to another Celestia account to_acc. This transfer from from_acc to to_acc is conditional on the following criteria:

1. Block d' must be the canonical block (at height i) of the roll-up, as per the roll-up fork-choice rule.
2. s must be the canonical and correct state of the rollup, resulting from all blocks up to d'.
3. d' should contain the transaction tx’.
4. tx' must be valid according to the rollup transaction validity rules.
5. The application of tx' d' including tx' to state s should yield state s'.
6. State s' should confirm the existence of a Celestia account to_acc set to receive a specified amount amount from the SNARK account from_acc.
7. d' should be included in a Celestia block d (at height j).
8. The fields of the SNARK transaction tx destined for Celestia must match the to_acc, amount, and from_acc of the rollup state s', specifically:
   • tx.to == to_acc
   • tx.from == from_acc
   • tx.amount == amount
   • Some other criteria which are not directly relevant to this discussion

Except for points 7 and 8, the other validity criteria are internal to the rollup and vary depending on its design. Consequently, the answer to the first and second questions of this discussion would be no, i.e., it's challenging to establish a universal and generic predicate applicable to all rollups, given that they do not conform to the same validity rules e.g., state transition rules, transaction validity rules, and fork-choice rules. Please let me know if you have a different perspective.

---

Regarding the third question about Generic vs Hybrid accounts, and specifically about your comment:

1. What would be an example of a non-hybrid snark account?

In the generic model (non-hybrid), Celestia does not supply any public inputs. Instead, it uses the public inputs provided by the transaction or specified by the account holder. For instance, the hash of the SNARK transaction submitted to Celestia could serve as one of the public parameters attached to the transaction. Celestia's state can then use this hash to verify the authenticity of the transaction (i.e., to check if the transaction's hash matches the submitted transaction).

Conversely, in a hybrid model, the hash is computed by the Celestia app and fed into the SNARK verification function. In this scenario, the transaction itself does not need to include the hash.

---

Some final points: Initially, I viewed one of the design distinction between generic and hybrid accounts as follows: In a generic model, Celestia doesn't need to understand the meaning of public inputs supplied by the transaction or SNARK account holders. However, upon further reflection, in both generic and hybrid approaches, it's beneficial for some public inputs to hold common meanings for both Celestia and the rollup. This means a transaction should not merely carry arbitrary data; certain elements need to be mutually understandable. The bare minimum is the transaction hash, which is essential to bind the SNARK proof to the transaction regardless of who provides that data, celestia or the transaction origin.

[cmwaters]

Would there need to be a validity predicate for depositing into an account or just for withdrawing?

[evan-forbes]

We don't have to do anything special for deposits, since the normal tx validity and state machine rules guarantee users actually authorized the bank.MsgSend

[cmwaters]

I’m trying to develop an intuition around the snark account work as it’s likely that I will be involved in reviewing it. As I see it, at a high level it mimics the same flow as a smart contract however using proofs to reduce the amount of on-chain state. How I see the usage as it relates to rollup bridging is as follows:

• A rollup creates a new snark account which is like a regular account with an address and a balance except there is some validity predicate defined by the rollup at initialization which replaces signature verification as it relates to sending money from that account to another account.
• If a user wants to send money from that account to their account i.e. withdraw from the bridge, they need to submit a transaction with a validity proof, p. The validators of Celestia verify the transaction by taking the validity predicate attached to the account, the proof and some other public inputs (like one or more data roots).
• The proof in this case referes to one or more transactions that have occured on the rollup. It could be simply user A sending part of the funds (locked up on the snark account) to user B which is the owner of the public key that is requesting to withdraw those funds. It could also be 100 transactions which need to be processes to understand what fraction of the funds user B has access to.

Some questions I have (which I've tried to direct in the appropriate discussions):

• Does this just support validity proofs or would we also look into naysayer proofs?
• How do we capture the gas required to verify the validity of the proof. Is it constant complexity? What are DoS vectors malicious users could take. Are there limits on the complexity of the validity predicate?
• If rollup logic changes through an upgrade, how is the new validity predicate added. Is a new account created for the new rollup.
• What are the public inputs that the validators on Celestia need to have access to?

[staheri14]

Does this just support validity proofs or would we also look into naysayer proofs?

Can you please expand on what you mean by naysayer proof?
It all comes down in what is encoded in the validity predicate which is almost arbitrary.

How do we capture the gas required to verify the validity of the proof. Is it constant complexity?

The issue of gas payments has not been thoroughly explored and will be addressed in a separate discussion.
In the context of using Groth16 proof system, both the proof size and verification time are constant and independent of the predicate.

Are there limits on the complexity of the validity predicate?

The primary limitation identified so far concerns the number of public inputs for the validity predicate, which should be bounded. These should be predefined by the account creator (to be persisted as part of the account state) to ensure that incoming withdrawal transactions adhere to this limit.

What are DoS vectors malicious users could take.

The transaction origin needs to pay for withdrawal from an SNARK account like any other transaction. So, it is not expected that there would be additional DoS vector for SNARK accounts.
Except, the double spending. Since this account is holding funds related to a rollup, it needs to protected against double spending/withdrawal where one single valid proof can be used to transfer funds multiple times. One aspect I've been considering is the necessity of associating a nullifier with each withdrawal transaction. This approach could effectively eliminate the risk of double spending. One such nullifier could be roughly H(d',receiver_account), given that at each block d' of the rollup there will only be one valid withdrawal from the SNARK account to the receiver_account. Note that this area is also under research.

If rollup logic changes through an upgrade, how is the new validity predicate added. Is a new account created for the new rollup.

In the preliminary phase of the SNARK accounts experimental implementation, creating a new account will be likely to be necessary. However, there is a possibility that a SNARK account could be linked to an additional predicate, which would permit updates in the validation predicate. Though, the feasibility of this approach should be further confirmed. Also, it is important to take into account which design choice will improve user experience.

What are the public inputs that the validators on Celestia need to have access to?

Currently, the focus is on the transaction hash (to bind the transaction to the proof). Also, the block hash d’ from the rollup, and the data root d from Celestia. This latter allows verification of whether d’ is contained within d.
I plan to elaborate on a few aspects related to this in the upcoming discussion on public inputs. I’ll make sure to ping you on that discussion as well.