0xMiden / 0xMiden/protocol

N-15: Redundant Per-Iteration Memory and Storage Traffic in verify_signatures

Aberta
#3,254 0 comentários 0 reações 0 responsáveis Ver no GitHub
standards
Linguagem predominante
Rust
Estrelas
132
Forks
167
Merge médio
1d 23h
PRs com merge (30d)
110

Descrição

The `verify_signatures` procedure loops once per approver to validate multisig-style authentication. Within each iteration it repeats work whose result is either constant for the entire transaction or already available on the operand stack, so the work does not contribute to the result. The combined overhead scales linearly with the number of approvers and increases the proving cost of authentication.

First, each iteration issues two separate `active_account::get_initial_map_item` [calls](https://github.com/0xMiden/protocol/blob/2ef8056323df258917d119383a7cdd49b064d88a/crates/miden-standards/asm/standards/auth/signature.masm#L281), one for the approver public key and one for its scheme identifier. Each call is a kernel syscall that re-resolves the storage slot by name, validates the slot type, hashes the key, and walks the storage map tree. Both read the initial storage state, which is fixed for the duration of the transaction, so the roots of the two storage maps are constant across every iteration of the loop yet are re-resolved for each signer.

Second, the fetched public key is written to [local memory](https://github.com/0xMiden/protocol/blob/2ef8056323df258917d119383a7cdd49b064d88a/crates/miden-standards/asm/standards/auth/signature.masm#L227) at `CURRENT_PK_LOC` and [reloaded](https://github.com/0xMiden/protocol/blob/2ef8056323df258917d119383a7cdd49b064d88a/crates/miden-standards/asm/standards/auth/signature.masm#L261) later within the same iteration, even though the value is still available on the operand stack. Similarly, the current signer index `i-1` is [written to ](https://github.com/0xMiden/protocol/blob/2ef8056323df258917d119383a7cdd49b064d88a/crates/miden-standards/asm/standards/auth/signature.masm#L215)`SIGNER_INDEX_LOC` at the top of each iteration and [read back](https://github.com/0xMiden/protocol/blob/2ef8056323df258917d119383a7cdd49b064d88a/crates/miden-standards/asm/standards/auth/signature.masm#L274) to rebuild the approver map key. At that load site the stack holds `[PUB_KEY, MSG, MSG, i-1]`, so the same `i-1` value is already present at stack depth 12 and could be obtained with `dup.12`. The index is additionally retained on the stack as the loop counter throughout the iteration, so the dedicated local is not required at all. Both values therefore incur a store and a load per iteration that produce no result not already on the stack.

Consider reading the two storage map roots once before the loop and resolving each signer's public key and scheme identifier by querying the storage map tree directly against those cached roots, so that the per-iteration kernel syscalls are eliminated. To preserve the current fail-closed behavior, where a non-map slot causes the transaction to abort, consider validating that each slot is a map exactly once before the loop rather than relying on the per-lookup type check. Consider also reusing the public key already present on the operand stack instead of round-tripping it through `CURRENT_PK_LOC`, and eliminating the `SIGNER_INDEX_LOC` store and load by duplicating the signer index from the stack where it is needed, which frees the local slot.

However, what suggested by the auditors is that the finding's two halves: (1) memory round-trips + unused locals, and (2) two `get_initial_map_item` syscalls re-resolving constant storage-map roots every loop iteration. Only half (1) was done by https://github.com/0xMiden/protocol/pull/3230. The core recommendation — cache the two roots once before the loop — was not implemented; both per-iteration syscalls remain, and that was the larger cost.

Guia de contribuição

Abrir o guia de contribuição

Avaliação

Esta issue ainda não foi avaliada.

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.