Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Outsource masp signature verification #3372

Merged
merged 10 commits into from
Jul 24, 2024

Conversation

grarco
Copy link
Contributor

@grarco grarco commented Jun 5, 2024

Describe your changes

Closes #3312.

Swaps the signature verification call in the masp vp with a check on the triggered vps. Introduces a new masp Action to support signature verification in the affected vps since we expect them to not be triggered by the transaction itself (no changed keys).

Indicate on which release or other PRs this topic is based on

#3516 (diffs for review: https://github.com/anoma/namada/pull/3372/files/17b9fcfa9c85f5a115646120f6595e8cf28c38a7..fc63450e3dfc2882c467d96a2600d761fb40853b)

Checklist before merging to draft

  • I have added a changelog
  • Git history is in acceptable state

@grarco grarco requested a review from murisi June 5, 2024 11:00
Copy link

codecov bot commented Jun 5, 2024

Codecov Report

Attention: Patch coverage is 12.14953% with 94 lines in your changes missing coverage. Please review.

Project coverage is 53.46%. Comparing base (8479d38) to head (fc63450).
Report is 4 commits behind head on main.

Files Patch % Lines
crates/namada/src/ledger/native_vp/masp.rs 0.00% 82 Missing ⚠️
crates/tx/src/action.rs 54.54% 5 Missing ⚠️
crates/trans_token/src/storage.rs 0.00% 4 Missing ⚠️
crates/tx_prelude/src/token.rs 0.00% 3 Missing ⚠️
Additional details and impacted files
@@            Coverage Diff             @@
##             main    #3372      +/-   ##
==========================================
- Coverage   53.48%   53.46%   -0.03%     
==========================================
  Files         320      320              
  Lines      110000   110031      +31     
==========================================
- Hits        58832    58824       -8     
- Misses      51168    51207      +39     

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

@grarco grarco marked this pull request as ready for review June 5, 2024 11:42
@grarco grarco force-pushed the grarco/outsource-masp-sig-verification branch from 9c0361a to 3add4d0 Compare June 6, 2024 09:44
@grarco grarco mentioned this pull request Jun 19, 2024
crates/tx/src/action.rs Outdated Show resolved Hide resolved
tzemanovic
tzemanovic previously approved these changes Jul 2, 2024
Copy link
Member

@tzemanovic tzemanovic left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

besides the pending question LGTM

Copy link
Contributor

@murisi murisi left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I agree that outsourcing verification is the most robust approach. But I'm not sure if these changes are robust against replay attacks...

)
.map_err(native_vp::Error::new)?;
// Otherwise the owner's vp must have been triggered
if !verifiers.contains(signer) {
Copy link
Contributor

@murisi murisi Jul 3, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I would almost certainly agree with this logic if signer's VP was being executed on the state change being checked by this MASP VP minus the state changes induced by the inner Transaction. My concern here is as follows: imagine Alice constructs an unshielding Transaction of 10 BTC to Bertha. Now imagine that Christel intercepts this Transaction and embeds it inside a Transfer Tx that increases the balance of Christel by 10 BTC (instead of Bertha who is the rightful recipient). In this case, since Tx is effectively two transfers (an unshielding Transaction of 10 BTC to Bertha followed by a transparent Transfer of 10 BTC from Bertha to Christel), the signers map would contain Bertha's address. My specific concern here is that Bertha's VP doesn't see this foul play (of rehousing the Transaction in a different Tx) and always accepts the state change because the net change to Bertha's balance as a result of the entire state change is zero (after all, Bertha is only mentioned in the transparent output of the Transaction). To me this approach would only make sense if the verifiers could be made to specifically validate just the "effective" Transfer of 10 BTC from Bertha to Christel (which would be the result of doing the above "subtraction"), in which case they would certainly demand an authorization signature from Bertha (as was being done before in an admittedly restrictive way). Am I missing something here?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

So this PR only removes the signature verification and requests the corresponding VP to be triggered. As you are saying though, Bertha's VP would not reject the tx in the attack scenario you described because the balance change is 0. To make this work I've introduced a new masp Action (i.e. a temporary write to write log that is not committed to storage) with the address of the verifier whose vp we want to check this tx (in this case Bertha). Again, the 0 balance change would lead to the tx being accepted, so on top of that, I've updated the implicit and user VPs to handle this Action with a signature check (but custom vps could add more checks if desired): so the signature check has been simply moved from the masp vp to the user and implicit vps.

For this logic to work we need some cooperation from the tx which must write the temporary action key(s) required (the ones carrying the addresses whose extra signatures have been attached to the tx).

I believe this logic is ok (but please double check again) but I think that there are other flaws in this this implementation of mine:

  1. Even though the Action carries the address of the signer this does not trigger its vp, since it's not the leading part of the key and we don't trigger VPs anymore if their address appear in non-leading locations of a key (@tzemanovic please correct me if I'm wrong). In this case we need a way for the tx to trigger the required VPs
  2. Checking that the VPs have been triggered is not enough. Someone could craft a tx that does not write the required actions but for which the relevant VPs are still triggered. In this case we could end up in the scenario you envisioned. On top of checking that VPs have been triggered we should also check that the corresponding Action has been written to storage to ensure that the VP will run the correct validation

Note that, as I've already answered Tomas before, at the moment the transactions do not support this Action logic cause with the previous design of vectorized transfers these scenario could not happen. It will become relevant after the new vectorized strategy has been merged

Copy link
Member

@tzemanovic tzemanovic Jul 5, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

For a single transfer I think we would need do something like this:

  1. If a VP of an address who must authorize the tx is not going to be triggered from the changed keys (yes, it is only the leading part) then the tx has to insert_verifier
  2. The MASP VP should require an Action to be written so a tx is not allowed to skip it (i.e. actions must not be empty)

For these to work together the MASP VP should then ensure that when the action is MaspSigner then the address in this action is contained in the verifiers set.

However, with the scenario with multiple transfers @murisi described I think this may not be sufficient. A tx could only attach a single action despite performing multiple actions. We might then need to add more information to the actions to describe the transfers in more detail and the MASP and user/implicit VPs will have to enforce that the storage changes match these actions. In this example, for the unshielding action from Alice we could have e.g. Action::Unshield { dest, amount } where dest == Bertha`` and if Christel` was to maliciously embed this transfer in another tx, either:

  • Only with the original action, an increase in Christel's balance would not be matching the action (the MASP VP has to check the transparent bundle's vout.address against the actions to enforce this)
  • With the original action and added Action::Transparent { src, dest, amount } where src == Bertha, dest == Christel and amount == 10, the user/implicit VP must require signature from Bertha (even if the overall balance change of Bertha is 0)
  • Without the original action, but with an Action::Unshield where dest == Christel, the side-effects of the storage changes would not match the actions (the actual unshielding dest is Bertha)

Copy link
Contributor

@murisi murisi Jul 10, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

So this PR only removes the signature verification and requests the corresponding VP to be triggered.

Ah, I completely misread the approach taken by this PR. My bad.

but custom vps could add more checks if desired

I see. And at the bare minimum, custom VPs must not forget to handle MASP Actions.

In this case we need a way for the tx to trigger the required VPs

Nice, I see you've now covered this case.

On top of checking that VPs have been triggered we should also check that the corresponding Action has been written to storage to ensure that the VP will run the correct validation

Nice, I see you've also covered this case.

Copy link
Contributor

@murisi murisi Jul 10, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

For a single transfer I think we would need do something like this:

1. If a VP of an address who must authorize the tx is not going to be triggered from the changed keys (yes, it is only the leading part) then the tx has to `insert_verifier`

2. The MASP VP should require an `Action` to be written so a tx is not allowed to skip it (i.e. actions must not be empty)

For these to work together the MASP VP should then ensure that when the action is MaspSigner then the address in this action is contained in the verifiers set.

At least in the current PR, this is all covered right? The current conditional forces the presence of the signer in the verifiers list. The next conditional forces the presence of the corresponding MaspSigner Action.

However, with the scenario with multiple transfers @murisi described I think this may not be sufficient.

The signer variable in this loop takes on as its value each of the Addresses whose balances are debited during processing (even if their net change is zero), so if this verifier check and the following MaspSigner check is correct then this VP should prevent Christel from committing thievery (since the Tx would be forced to trigger the signature checks elsewhere). Right?

@brentstone brentstone mentioned this pull request Jul 5, 2024
@grarco grarco force-pushed the grarco/outsource-masp-sig-verification branch from af6f1dc to fc7ab93 Compare July 9, 2024 11:36
Copy link
Contributor

@murisi murisi left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ah, now I understand what you're doing. I think. However the MASP integration tests are currently failing on my machine. Maybe related: is there any place in the TX_TRANSFER_WASM code where we push MaspSigner Actions?

)
.map_err(native_vp::Error::new)?;
// Otherwise the owner's vp must have been triggered
if !verifiers.contains(signer) {
Copy link
Contributor

@murisi murisi Jul 10, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

So this PR only removes the signature verification and requests the corresponding VP to be triggered.

Ah, I completely misread the approach taken by this PR. My bad.

but custom vps could add more checks if desired

I see. And at the bare minimum, custom VPs must not forget to handle MASP Actions.

In this case we need a way for the tx to trigger the required VPs

Nice, I see you've now covered this case.

On top of checking that VPs have been triggered we should also check that the corresponding Action has been written to storage to ensure that the VP will run the correct validation

Nice, I see you've also covered this case.

)
.map_err(native_vp::Error::new)?;
// Otherwise the owner's vp must have been triggered
if !verifiers.contains(signer) {
Copy link
Contributor

@murisi murisi Jul 10, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

For a single transfer I think we would need do something like this:

1. If a VP of an address who must authorize the tx is not going to be triggered from the changed keys (yes, it is only the leading part) then the tx has to `insert_verifier`

2. The MASP VP should require an `Action` to be written so a tx is not allowed to skip it (i.e. actions must not be empty)

For these to work together the MASP VP should then ensure that when the action is MaspSigner then the address in this action is contained in the verifiers set.

At least in the current PR, this is all covered right? The current conditional forces the presence of the signer in the verifiers list. The next conditional forces the presence of the corresponding MaspSigner Action.

However, with the scenario with multiple transfers @murisi described I think this may not be sufficient.

The signer variable in this loop takes on as its value each of the Addresses whose balances are debited during processing (even if their net change is zero), so if this verifier check and the following MaspSigner check is correct then this VP should prevent Christel from committing thievery (since the Tx would be forced to trigger the signature checks elsewhere). Right?

@@ -53,7 +53,9 @@ fn apply_tx(ctx: &mut Ctx, tx_data: BatchedTx) -> TxResult {
.wrap_err("Encountered error while handling MASP transaction")?;
update_masp_note_commitment_tree(&shielded)
.wrap_err("Failed to update the MASP commitment tree")?;
ctx.push_action(Action::Masp(MaspAction { masp_section_ref }))?;
ctx.push_action(Action::Masp(MaspAction::MaspSectionRef(
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The MASP integration tests seem to be failing for me. Probably they are failing on at least the shielding transactions because their signers have not been added as actions. So I think we need to push some MaspSigner Actions in this vicinity - the same set that will be iterated through in the for signer in signers { loop if we desire to support the Christel thieving corner case above. But at the least, all of the net debited accounts should at least be added to the MaspSigner Actions. No?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

That's correct. I'm fixing this issue rn

@grarco
Copy link
Contributor Author

grarco commented Jul 12, 2024

Ok so I've pushed some more commits, to recap:

  • In the masp vp we check that the vp of the signer has been triggered and also check that the corresponding action has been pushed (otherwise the vp might run a different validation logic, we have to inform it that it is required to validate a masp transaction)
  • I've talked to @tzemanovic for the solution he proposed (multiple actions to describe what's actually happening). We concluded that for now we can go with the current solution of just pushing a single action (@murisi I think you agreed in your previous comment that this is safe and we don't need more detailed data). His suggestion though could be taken into consideration for future updated in case we want to allow for more complicated validation logic from the implicit/user vps side
  • TX_TRANSFER_WASM has been updated to push the required MaspAction::MaspAuthorizer actions and trigger the vps
  • The multi_transfer function has been updated to return the set of addresses whose balance has gone down
  • The Transfer type has been extended to carry an additional set of masp verifiers. This is because the solution here above doesn't cover all the cases, for example, it does not cover the tamper attack that Murisi has explained before, therefore we need the transaction to trigger these extra vps too

One small annoyance, the masp vp considers required authorizers all the addresses whose balance has decreased: this includes balances that had nothing to do with the MASP in that transaction. Because of this we are forced to push actions for these addresses too: at the moment both the implicit and user vps just check for the signature which coincides with the check for a normal balance decrease, but in case the verification changed (for example in some custom vp), then this could run a validation logic which is not correct for the actual changes.

@brentstone brentstone force-pushed the grarco/outsource-masp-sig-verification branch from c9cc4e1 to cf9942a Compare July 13, 2024 07:34
@grarco grarco requested review from tzemanovic and murisi July 15, 2024 14:49
murisi
murisi previously approved these changes Jul 15, 2024
Copy link
Contributor

@murisi murisi left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The latest additions would work. But I wonder if there isn't a way to achieve outsourcing without having to augment Transfer with a vector of VP addresses... Might it be possible to collect the VP Addresses from the Authorization sections of the Tx and insert those into the verifier list instead of embedding them in the Transfer structure? Or would this be too constraining/hacky? After all the user and implicit VPs look for the signatures in these sections...

@murisi
Copy link
Contributor

murisi commented Jul 16, 2024

One small annoyance, the masp vp considers required authorizers all the addresses whose balance has decreased: this includes balances that had nothing to do with the MASP in that transaction. Because of this we are forced to push actions for these addresses too: at the moment both the implicit and user vps just check for the signature which coincides with the check for a normal balance decrease, but in case the verification changed (for example in some custom vp), then this could run a validation logic which is not correct for the actual changes.

Let me work on a separate PR to fix the MASP VP so that addresses unrelated to the MASP Transaction do not require a signature when their balances decrease. I think this should be a very minor change that does not conflict with this PR.

tzemanovic
tzemanovic previously approved these changes Jul 16, 2024
@murisi
Copy link
Contributor

murisi commented Jul 16, 2024

One small annoyance, the masp vp considers required authorizers all the addresses whose balance has decreased: this includes balances that had nothing to do with the MASP in that transaction. Because of this we are forced to push actions for these addresses too: at the moment both the implicit and user vps just check for the signature which coincides with the check for a normal balance decrease, but in case the verification changed (for example in some custom vp), then this could run a validation logic which is not correct for the actual changes.

Let me work on a separate PR to fix the MASP VP so that addresses unrelated to the MASP Transaction do not require a signature when their balances decrease. I think this should be a very minor change that does not conflict with this PR.

Attempted to fix this here: #3516

@grarco
Copy link
Contributor Author

grarco commented Jul 16, 2024

The latest additions would work. But I wonder if there isn't a way to achieve outsourcing without having to augment Transfer with a vector of VP addresses... Might it be possible to collect the VP Addresses from the Authorization sections of the Tx and insert those into the verifier list instead of embedding them in the Transfer structure? Or would this be too constraining/hacky? After all the user and implicit VPs look for the signatures in these sections...

I tend to think it would be slightly hacky and I'm not sure we can derive the address from an authorization section in case of a multisig account, or can we?

@murisi
Copy link
Contributor

murisi commented Jul 16, 2024

The latest additions would work. But I wonder if there isn't a way to achieve outsourcing without having to augment Transfer with a vector of VP addresses... Might it be possible to collect the VP Addresses from the Authorization sections of the Tx and insert those into the verifier list instead of embedding them in the Transfer structure? Or would this be too constraining/hacky? After all the user and implicit VPs look for the signatures in these sections...

I tend to think it would be slightly hacky and I'm not sure we can derive the address from an authorization section in case of a multisig account, or can we?

Fair enough agreed, probably attempting this is more trouble than it's worth.

On a separate note, I suspect that 65d07fb (i.e. with all the debited accounts as authorizers but without opt_authorizers additional authorizers field) combined #3516 (which reduces the set of authorizations required for a MASP Tx) would trigger the necessary VPs for all the transfers generated by namadac to pass. Though the difference with that approach is that it would probably be impossible to successfully execute the Alice-Bertha-Christel Tx above since Bertha's address would never be inserted by the tx as a verifier. But I'm doubting that transactions like this (where assets bounce through an intermediate account like Bertha) would actually be needed in practice, so it wouldn't be much of a loss. All this to say that I think this PR would also be perfectly fine without the Adds additional authorizers for masp transactions commit. It's up to you!

@grarco grarco dismissed stale reviews from tzemanovic and murisi via dab10a6 July 19, 2024 17:07
@grarco grarco force-pushed the grarco/outsource-masp-sig-verification branch from cf9942a to dab10a6 Compare July 19, 2024 17:07
@grarco
Copy link
Contributor Author

grarco commented Jul 22, 2024

Hey @murisi, I've pushed some last updates:

  • This branch is now based on Eliminates MASP VP's requirement for all debited accounts to sign Tx #3516
  • The Transfer data has been reverted to the previous one (no extra signers)
  • The transfer transaction pushes actions for the debited accounts but only if these were involved in the masp part of the transfer
  • The transfer transaction fails if the vins addresses of the masp transfer have not been debited
  • The masp vp now checks that only the required masp actions have been pushed

}
}

let mut actions_authorizers: HashSet<&Address> = actions
Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actions are actually a vector of Action, so it's possible to push the same action more than once. I believe from the perspective of the masp vp this is of no importance: we just want to check that the action for a specific authorizer has been written, it doesn't matter if it's duplicated

@grarco grarco requested a review from murisi July 22, 2024 10:15
Copy link
Contributor

@murisi murisi left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This PR looks fine as-is, thanks! I just a few minor notes/queries which are probably unimportant.

);
let masp_authorizers: Vec<_> = debited_accounts
.into_iter()
.filter(|account| {
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Nice reduction of the set of authorizers. This works because of the relaxation of the VP in #3516...

vin_addresses.contains(&addr_taddr(account.clone()))
})
.collect();
if masp_authorizers.len() != vin_addresses.len() {
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I guess this logic would only work for Transactions that do not trigger

authorizers.insert(addr);
. This should be fine though since I think that namadac cannot generate these, and transactions like these can probably be expressed more simply in a way that does not trigger the aforementioned code anyway.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Correct, this is a current limitation of the transfer transaction, but as you are saying we don't support these kind of transactions in the client at the moment

)
.into();
tracing::debug!("{error}");
return Err(error);
}
}
// The transaction shall not push masp authorizer actions that are not
// needed cause this might lead vps to run a wrong validation logic
if !actions_authorizers.is_empty() {
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The transaction shall not push masp authorizer actions that are not needed

This is fine, though it means that transactions need to precisely compute/maintain the required set of authorizers even when the logic at

authorizers.insert(addr);
is triggered. Theoretically this set might also contain addresses that are not in the Transaction transparent inputs and hence may be inconvenient to compute and push in transactions.

Copy link
Contributor Author

@grarco grarco Jul 23, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

That's correct, there's some burden on the transaction side to match the set of verifiers. But eventually the transaction has to either match the set of authorizers required by the vps exactly or match a superset of it (in case we wanted to relax this condition). The only thing I can think of to ease the computation on the transaction side would be to push actions for all the involved parties (which need to be computed anyway since, as you are saying, they might not be limited to the transparent inputs). This would lead to an increase in gas cost given by the extra (unneeded) signatures attached to the transaction and by the cost of their verification: at the end this might outweigh the added gas cost for the logic to be placed in the transfer transaction. Another issue is that collecting some of these signatures could be complicated and make the ux more unpleasant

)
.into();
tracing::debug!("{error}");
return Err(error);
}
}
// The transaction shall not push masp authorizer actions that are not
// needed cause this might lead vps to run a wrong validation logic
if !actions_authorizers.is_empty() {
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

this might lead vps to run a wrong validation logic

I'd assumed that redundant MASP authorizer actions only imply signature checks for redundant signatures. In a correctly implemented VP, is this not necessarily the case?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

For our VPs, that's correct, we'd just recheck the signature (which actually doesn't even happen because of the Gadget that caches the result of the signature check and ensures that we run that verification at most once). I'm not sure this holds for incorrectly VPs though: I believe the worst that could happen was the rejection of a valid transaction but not the acceptance of an invalid one. But some really broken VPs could actually end up accepting invalid transactions because of masp actions. So my reasoning here was to be very conservative, also because there's really no reason why someone should push a masp action which isn't required

brentstone added a commit that referenced this pull request Jul 22, 2024
* grarco/outsource-masp-sig-verification:
  Transfer transaction fails if masp transparent inputs are not debited
  Changelog #3312
  Masp vp checks that no unneeded actions are pushed
  Transfer transaction pushes masp actions
  Renames masp signers to authorizers
  Refactors masp action checks
  Masp vp checks for signer actions
  Moves signatures verification from masp vp to the affected vps
@brentstone brentstone merged commit 5669e94 into main Jul 24, 2024
15 of 19 checks passed
@brentstone brentstone deleted the grarco/outsource-masp-sig-verification branch July 24, 2024 22:59
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Outsource signature verification from masp vp
4 participants