Public Inputs for SNARK Accounts

[evan-forbes]

Typical zk-rollups utilize smart contracts to enforce what must be provided as a public input when verifying a proof. Since smart contracts are not an option, we must define sufficiently general required public inputs.

In the forum post, it suggests that

the public input to the rollup’s Celestia ZK address would be the last Celestia block height (which would be enforced as an input by Celestia’s state machine), and the identifier of some “withdrawal transaction” on the rollup.

However AFAIU, this would require the Celestia state machine to parse the withdrawal transaction to check that the transaction controlling the SNARK Account is actually sending the correct amount of funds to the correct address.

Instead, I think we could actually pass the hash of the transaction (or the hash of the body of the transaction) as a public input. This would allow for much more arbitrary actions to be proven. The circuit would first prove that some tx bytes hash to some value, and then prove arbitrary things about those bytes. Such as they contain only the correct bank.MsgSends.

There might be values that would be very useful to include as [optional] public inputs. Recall that a rollup would have to prove the fork choice rule and inclusion of some data. This could be done by first proving a light celestia light client, and then using that light client to verify data roots. Those data roots could then be used to verify inclusion and or the fork choice rule.

Alternatively, the state machine could require that some commitment to block data be included as a public input. This commitment could be the raw data roots themselves, or perhaps some meta commitment such as what is used for blobstream.

[musalbas]

I only meant that the block height is the only consensus-enforced public input; the rest can be arbitrary.

[staheri14]

Based on the discussions we've had so far in #2904 , it appears infeasible to establish a universal predicate applicable to all rollups. Consequently, while it's not possible to determine the exact public inputs required by each rollup, it is essential to anticipate potentially useful public inputs and provide them to the rollups predicate verification function. Rollups will have the option to utilize or disregard these inputs. However, they are expected to accept these inputs in their validity predicate/circuit.

Such public inputs include:

• tx_hash: This is the hash of the withdrawal transaction intended for the SNARK account. The specific fields of the transaction that should be included in the hash computation need to be specified. However, the amount(s) and the address(es) of the receiver account(s) are definite inclusions. The aim is for Celestia to associate each transaction with its corresponding proof, thereby preventing replay attacks.
• The data root of the ith block of Celestia, where i is determined by the withdrawal transaction. (a general case covering what mentioned in this comment as well)
• The block d' (where d' can be the blob share commitment corresponding to the rollups data submitted to Celestia). d' is expected to be included in the i-th block of Celestia (as explained in here).

[puma314]

When traversing the Namespace Merkle Tree, can you prove that a blob is the i-th entry in the tree (assuming it is the i-th blob posted to that namespace)? And is that proof just a standard merkle proof, so proving items i through j will take log_n * (j-i) time?

[musalbas]

You can't prove that a blob is the i-th entry but you can prove that a share is the i-th share. Why do you to prove a blob is the i-th entry?

[bakugo49]

Without proving that the blob is the i-th entry, how does the SNARK account verify that no blobs have been skipped over by the prover in the proof?

[musalbas]

if you know the namespace starts at share index x for example, and ends at index x+y, then you check no shares were skipped over between x and x+y

[evan-forbes]

1 transaction on the rollup can have multiple "withdraws" within that transaction (for example imagine that you make a smart contract that calls the "withdraw" contract on the rollup 10 times with 10 different withdrawal addresses). I think it might be hard to prevent this behavior on rollups (or something that is bad to assume in general), so I think just using the transaction hash is not sufficient (at least on the rollup -> Celestia direction).

@puma314 do you mind expanding on this point? I'm not yet following why the tx hash could be used for a single withdraw, but not multiple

On Celestia, my understanding is that we can make the assumption that 1 transaction = 1 rollup deposit due to the limited nature of transaction types, right?

unfortunately, we can't make this assumption. we have have a module that enables authorization of other accounts to perform certain actions. Since a transaction can contain an arbitrary number of actions, its possible or a single authorized account to send funds for an arbitrary number of accounts in a single transaction.

[staheri14]

I’d like to present a classification of public inputs, which I've found beneficial in designing and managing the workflow of snark accounts and the current and future discussions:

Classification	Description	Example	Belongs to
Static Inputs	These inputs do not change over time; are provided by the account holder at the time of account creation.	Maximum withdrawal amount for each transaction (if applicable)	Account state
Dynamic Inputs	Inputs that are time dependant. They are supplied at the time of submitting withdrawal transactions.	Data root of the ith Celestia block	Transaction fields

The Dynamic Inputs can be further grouped:

Classification of Dynamic Inputs	Description	Example
Mutual Inputs	Such public inputs are mutually understandable by the rollup users (account holder/tx owners) and celestia. They may be supplied by celestia or the rollup (i.e., tx owner).	tx_hash, d, d'
Rollup-Specific Inputs	Such inputs are rollup specific; the interpretation of these inputs are outside the scope of SNARK account design.	anything

And the last classification is about the Mutual Inputs:

Classification of Mutual Inputs	Belongs to
Supplied by Rollup/Transaction Owner	Part of the transaction fields.
Supplied by Celestia	Omitted from the transaction fields.

With the presented classification, I'd like to draw several observations and design ideas:

1. The public inputs for the SNARK verification algorithm fall into these four categories:

• Static Inputs
• Dynamic Mutual Inputs Supplied by Celestia
• Dynamic Mutual Inputs Supplied by Rollup
• Dynamic Rollup-Specific Inputs

2. For verifying a SNARK proof, these four classes of public inputs should be serialized and positioned correctly before being fed into the verification algorithm (vk stands for verification key):
   Verify(vk, proof, [Dynamic Mutual Inputs Supplied by Celestia] || [Dynamic Mutual Inputs Supplied by Rollup] || [Static Inputs] || [Dynamic Rollup-Specific Inputs]).

3. Given that the number of public inputs varies based on the SNARK predicate, the account holder must specify the total number of public inputs at the time of account creation. This value is static and should be persisted as part of the account's state.

4. The mutual inputs provided by Celestia could be predefined. Therefore, all SNARK accounts' circuits should be designed to accept these inputs at a specific position in their circuit. It is up to the SNARK account holder to either discard or utilize these inputs in the SNARK validity predicate.

5. Similarly, there could be a predefined list of mutual inputs provided by the rollup or transaction owner. These inputs will form additional SNARK-related and named fields of a withdrawal transaction. Celestia may perform correctness checks on such inputs for additional security and integrity.

[staheri14]

cc: @cmwaters follow-up on #2904 (reply in thread)