Transaction proof fails to verify for new accounts

[igamigo]

When running transactions on new accounts, proofs do not verify:

miden-client git:(igamigo-test-verification) cargo run --release --features testing -- tx new mint 0x5ea990df9618df14 0x95af1e1f94fadcf7 1000

    Finished release [optimized] target(s) in 0.14s
     Running `target/release/miden-client tx new mint 0x5ea990df9618df14 0x95af1e1f94fadcf7 1000`
Account seed for 0x95af1e1f94fadcf7 is Some([15550717405134310864, 2087076094303456840, 11532054896839160962, 3698114614818582351]), hash is 0x355ba1dbeedb652760959891a7fc2df1dcb05d2312c1cdd4260c0485c383eb8d, nonce is 0

TransactionVerificationFailed(VerifierError(InconsistentOodConstraintEvaluations))

On new existing accounts, it does verify correctly:

miden-client git:(igamigo-test-verification) cargo run --release --features testing -- tx new mint 0x5ea990df9618df14 0x95af1e1f94fadcf7 1000

    Finished release [optimized] target(s) in 0.19s
     Running `target/release/miden-client tx new mint 0x5ea990df9618df14 0x95af1e1f94fadcf7 1000`
Account seed for 0x95af1e1f94fadcf7 is None, hash is 0xada7fb078c21b88fcd83776ef999a965dcc70b9886f8a537858c02df88ab70a4, nonce is 1

2024-02-07T19:27:53.154772Z  INFO miden_client::cli::transactions: Executed transaction, proving and then submitting...
2024-02-07T19:27:57.900895Z  INFO miden_client::client::transactions: Verification succesful
2024-02-07T19:27:57.900911Z  INFO miden_client::client::transactions: Proved transaction, submitting to the node...
2024-02-07T19:27:57.941398Z  INFO miden_client::store::transactions: Transaction id 0x9bf9a0851cc3ed2462671a6a47e15675d00d6516420b6c7b65d849f8022dd9f3
2024-02-07T19:27:57.941409Z  INFO miden_client::store::transactions: Transaction account id: 0x95af1e1f94fadcf7

Note that this is verifying locally, before submitting to the node (the branch igamigo-test-verification adds verification step before submitting for testing this problem). Also, this is using the accounts generated by the node with make-genesis and the testing flag on.

@phklive might be able to expand on this as he was working on 0xPolygonMiden/miden-node#171, to which this is related. After discussing on a call, we are not sure what could be causing the problem but guess that there are some inputs missing on the proof, specifically related to the account seed.

[bobbinth]

On new accounts, it does verify correctly:

Do you mean on "existing accounts"?

[igamigo]

Correct, apologies for the confusion

[bobbinth]

@phklive - as the first step, let's create a "prove" test which tests consumption of a note into a new account. I'm expecting this test will fail with a similar message. I'll look into what could be causing this.

[bobbinth]

The root of the issue is pretty simple:

1. To construct stack inputs for the VM, both the prover and the verifier use TransactionKernel::build_stack_inputs() function.
2. This function expects init_acct_hash to be None for new accounts. And that's how the prover invokes it.
3. But the verifier always uses Some with the actual initial account hash (see here). This works fine for existing accounts, but would fail for new accounts.

One way to fix this is to change how we construct ProvenTransaction struct. Specifically, right now ProvenTransaction.initial_account_hash is set to the actual hash of the initial account state for both new and existing accounts. But maybe, for new accounts, we should just set it to [ZERO; 4] - since this is the info the verifier is going to use anyway.

This will also help us eliminate the TODO we left for error checking of transaction inputs in the miden-node.

[phklive]

@phklive - as the first step, let's create a "prove" test which tests consumption of a note into a new account. I'm expecting this test will fail with a similar message. I'll look into what could be causing this.

Add the test in miden-base? Asking because I believe it could also live in miden-client.

[bobbinth]

Add the test in miden-base? Asking because I believe it could also live in miden-client.

I think having it in miden-base is sufficient.

[bobbinth]

One way to fix this is to change how we construct ProvenTransaction struct. Specifically, right now ProvenTransaction.initial_account_hash is set to the actual hash of the initial account state for both new and existing accounts. But maybe, for new accounts, we should just set it to [ZERO; 4] - since this is the info the verifier is going to use anyway.

So, I think we should do the following here:

1. When creating a ProvenTransaction, for new accounts we should pass Digest::default() the initial_account_hash parameter.
2. For TransactionKernel::build_stack_inputs(), we should change the type of init_acct_hash parameter to just Digest (rather than Option<Digest>). And we should also make sure that Digest::default() is passed in to this function for new accounts.

Hopefully, everything else will work without any additional changes.

[phklive]

One way to fix this is to change how we construct ProvenTransaction struct. Specifically, right now ProvenTransaction.initial_account_hash is set to the actual hash of the initial account state for both new and existing accounts. But maybe, for new accounts, we should just set it to [ZERO; 4] - since this is the info the verifier is going to use anyway.

So, I think we should do the following here:

1. When creating a ProvenTransaction, for new accounts we should pass Digest::default() the initial_account_hash parameter.
2. For TransactionKernel::build_stack_inputs(), we should change the type of init_acct_hash parameter to just Digest (rather than Option<Digest>). And we should also make sure that Digest::default() is passed in to this function for new accounts.

Hopefully, everything else will work without any additional changes.

Hello @bobbinth I have implemented your requests and am working on testing it now.

Thinking through it I have not fully understood the reason why we would want to pass Digest::default() instead of the actual account_hash of an account to the prover / verifier.

Also when we are talking about a new account what are we talking about ( I have seen different situations ):

• Account is not recorded in the store
• Account has a nonce of 0

Because the account could be recorded in the store and have a nonce of 0 right, like the accounts generated at genesis.

Thank you

[bobbinth]

Thinking through it I have not fully understood the reason why we would want to pass Digest::default() instead of the actual account_hash of an account to the prover / verifier.

The prover actually does get the full initial state of the account - but the way it is provided to the VM is via advice inputs rather than stack inputs. The VM then verifies that for new accounts the prover can also provide a valid account seed (i.e., that hashing (code root, storage root etc. of the initial account state together with the seed yields the expected account ID).

The verifier, however, does not need to know the initial account state for new accounts. In case of new accounts, we are basically saying that: (1) there was some new account with an initial state which was consistent with the specified account ID, (2) a transaction was executed against this new account, and (3) here is the resulting state. From the verifier/node standpoint.

Also when we are talking about a new account what are we talking about ( I have seen different situations ):

• Account is not recorded in the store
• Account has a nonce of 0

Because the account could be recorded in the store and have a nonce of 0 right, like the accounts generated at genesis.

This is a very good question and we may actually need to change slightly how genesis account generation works. Basically, a new account is the one that has nonce $0$. An account with nonce $0$ is not recorded in the store because there have been no transactions against this account (once a transaction is executed against an account, its nonce is incremented and then when it gets stores in the store). So, the store should only contain accounts with nonce $\gt 0$. I believe this is not how our current genesis generation procedure works - so, we need to look into how to update it (and maybe this needs to happen before this issue is resolved).

[phklive]

I believe this is not how our current genesis generation procedure works - so, we need to look into how to update it (and maybe this needs to happen before this issue is resolved).

A few questions:

• Regarding how we create new accounts and record them on-chain. Is the process: 1. local POW to generate new account 2. send network tx to record account on chain. Is there a specific type of tx to signify that you are trying to record a new account on chain or does any type of tx works?

• When you say "We need to look into how to update it" do you have some direction to provide? I have looked into the code and don't believe that we can simply insert the newly generated account at genesis with a nonce of 1. Hence it would require us to make tx's for each newly generated account at genesis. Am I correct or am I missing something?

[phklive]

Thinking through it I have not fully understood the reason why we would want to pass Digest::default() instead of the actual account_hash of an account to the prover / verifier.

The prover actually does get the full initial state of the account - but the way it is provided to the VM is via advice inputs rather than stack inputs. The VM then verifies that for new accounts the prover can also provide a valid account seed (i.e., that hashing (code root, storage root etc. of the initial account state together with the seed yields the expected account ID).

The verifier, however, does not need to know the initial account state for new accounts. In case of new accounts, we are basically saying that: (1) there was some new account with an initial state which was consistent with the specified account ID, (2) a transaction was executed against this new account, and (3) here is the resulting state. From the verifier/node standpoint.

Also when we are talking about a new account what are we talking about ( I have seen different situations ):

• Account is not recorded in the store
• Account has a nonce of 0

Because the account could be recorded in the store and have a nonce of 0 right, like the accounts generated at genesis.

This is a very good question and we may actually need to change slightly how genesis account generation works. Basically, a new account is the one that has nonce 0. An account with nonce 0 is not recorded in the store because there have been no transactions against this account (once a transaction is executed against an account, its nonce is incremented and then when it gets stores in the store). So, the store should only contain accounts with nonce >0. I believe this is not how our current genesis generation procedure works - so, we need to look into how to update it (and maybe this needs to happen before this issue is resolved).

A few questions:

• What do you call "Full initial state" would it be the Account, hashed, hence it's whole state commitment or something else?:

  miden-base/objects/src/accounts/mod.rs

  Lines 96 to 111 in 4db70c0

  	// PUBLIC ACCESSORS
  	// --------------------------------------------------------------------------------------------
  	/// Returns hash of this account.
  	///
  	/// Hash of an account is computed as hash(id, nonce, vault_root, storage_root, code_root).
  	/// Computing the account hash requires 2 permutations of the hash function.
  	pub fn hash(&self) -> Digest {
  	hash_account(
  	self.id,
  	self.nonce,
  	self.vault.commitment(),
  	self.storage.root(),
  	self.code.root(),
  	)
  	}

• My understanding of what an init_seed is: The init seed is used to generate the account, it is used as seed to the hash function. The hash function being deterministic, the same account seed would yield the same account. Am i correct?

• What is the difference between an init_seed

  miden-base/miden-lib/src/accounts/wallets/mod.rs

  Line 30 in 4db70c0

  init_seed: [u8; 32],

  and an account seed

  miden-base/miden-lib/src/accounts/wallets/mod.rs

  Line 68 in 4db70c0

  let account_seed = AccountId::get_account_seed(

  ?

The VM then verifies that for new accounts the prover can also provide a valid account seed (i.e., that hashing (code root, storage root etc. of the initial account state together with the seed yields the expected account ID).

• It is using this function to re-create the account id and compare, right?

  miden-base/objects/src/accounts/account_id.rs

  Lines 70 to 95 in 4db70c0

  	/// Returns a new account ID derived from the specified seed, code root and storage root.
  	///
  	/// The account ID is computed by hashing the seed, code root and storage root and using 1
  	/// element of the resulting digest to form the ID. Specifically we take element 0. We also
  	/// require that the last element of the seed digest has at least `23` trailing zeros if it
  	/// is a regular account, or `31` trailing zeros if it is a faucet account.
  	///
  	/// The seed digest is computed using a sequential hash over
  	/// hash(SEED, CODE_ROOT, STORAGE_ROOT, ZERO). This takes two permutations.
  	///
  	/// # Errors
  	/// Returns an error if the resulting account ID does not comply with account ID rules:
  	/// - the ID has at least `5` ones.
  	/// - the ID has at least `23` trailing zeros if it is a regular account.
  	/// - the ID has at least `31` trailing zeros if it is a faucet account.
  	pub fn new(seed: Word, code_root: Digest, storage_root: Digest) -> Result<Self, AccountError> {
  	let seed_digest = compute_digest(seed, code_root, storage_root);
  	// verify the seed digest satisfies all rules
  	Self::validate_seed_digest(&seed_digest)?;
  	// construct the ID from the first element of the seed hash
  	let id = Self(seed_digest[0]);
  	Ok(id)
  	}

The verifier, however, does not need to know the initial account state for new accounts.

• Why is there or is there a difference between how the Prover / VM / Verifier handles new from old accounts? ( 0 nonce vs > 0 nonce )

[bobbinth]

What do you call "Full initial state" would it be the Account, hashed, hence it's whole state commitment or something else?

The full initial state is all underlying info about the account (not just a commitment). This includes full info about account code, storage, vault etc.

• My understanding of what an init_seed is: The init seed is used to generate the account, it is used as seed to the hash function. The hash function being deterministic, the same account seed would yield the same account. Am i correct?
• What is the difference between an init_seed?

No - init_seed is not used to generate the account. The account is defined by the user - that is, the user selects what code and storage they want the account to have (take a look at how creation of basic wallet works). Once the user defined code and storage for their account, they need to derive an account ID for it. This is where account_seed comes in. By hashing account code, storage, and seed, we get an account ID. There are some restrictions we place on the values both the account ID and account seed can have, and thus, not every random value would work for an account seed. This is why the user needs to expand PoW to find the right account seed.

In this context, init_seed is just a starting point for the search of the account seed. This process is deterministic only if ran in a single thread. If the search of account seed is multi-threaded, the same init seed may result in different account seeds (recall how you fixed the issue of some tests failing by using single-threaded account seed generator).

It may actually be a good thing to write up in the docs (there are some comments about this in the code, but they are probably scattered and difficult to follow). Once you go through the code and have a deeper understanding of the process - could you write up a few paragraphs and add them to the docs?

It is using this function to re-create the account id and compare, right?

Yes, there is a MASM implementation of this function which is actually used in the VM.

Why is there or is there a difference between how the Prover / VM / Verifier handles new from old accounts? ( 0 nonce vs > 0 nonce )

Depends on what you mean by "handles." The prover/VM needs to know the entire account state to execute a transaction. The verifier just needs to know a limited set of public inputs to verify the same transaction. For new accounts, for example, the verifier does not need to know the initial state - it just needs to know that the transaction involved a new account.

[bobbinth]

Mostly closed by #458. The only remaining thing is to add a test and we can do it as a part of #462.