ml-dsa: Lower stack usage for verification on embedded targets

オープン
#1,498 コメント 1 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

まだ誰も着手していません。

評価

難易度
4/5
見積もり時間
3〜5日
初心者へのやさしさ
48/100
issue の種類
機能追加
明瞭さ
おおむね明確
活発さ
活発
技術スタック
rust

調査の方向性

Start by reading the ml-dsa key decoding and verification code, especially how VerifyingKey::decode stores A_hat, t1, and 2^d * t1. Measure stack usage on a Cortex-M target for decoding and verification to confirm the reported peaks. Compare caller-owned expansion storage with generating matrix entries during verification; done means one approach substantially reduces stack use while preserving verification behavior.

索引モデルが issue の本文から書いたものです。

説明

Hi!

We're using ml-dsa (0.1.1) to verify ML-DSA-65 certificate chains on a Cortex-M MCU (no_std / without alloc), and the stack usage is quite a bit higher than we can afford. I measured on target and it's quite large:

Operation Peak stack
VerifyingKey::decode ~134 kB
decode + verify ~147 kB
verify with already decoded input ~47 kB

As I see it, most of this comes from VerifyingKey precomputing A_hat, t1 and 2^d * t1 at decode. The key is 43 kB, and it's built and returned by value, so a few copies end up on the stack (I think this is the main contributor that bloats stack usage).

I see two possible ways to help this, and I'm not sure which one fits the crate best:

  1. A decode_into (or similar) that writes the expanded key into storage the caller owns, so it never passes through the stack.
  2. An on-the-fly verification path that generates the A entries from rho when needed and never stores the matrix. That trades some speed for a few kB of stack, which is a good trade for us embedded folk.

Would you be open to a PR for either of these? :)
I could not find existing discussions on this, feel free to correct me if I missed something!

主要言語
Rust
スター
672
フォーク
213
平均マージ
23時間 39分
マージ済み PR(30日)
19

環境構築

このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

RustCrypto/signatures のほかの issue

RustCrypto/signatures の issue をすべて見る

似ている issue

Rust の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。