0xMiden / 0xMiden/air-script

Avoid Matrix Construct in MDS Multiplication

Ouverte
#506 2 commentaires 1 réaction 0 personnes assignées Voir sur GitHub
Langage dominant
Rust
Étoiles
96
Forks
39
Métriques de merge des PR
Aucune PR mergée en 30 j

Description

The RPO permutation round currently uses a 2D matrix construct for MDS matrix multiplication.
This can be simplified by defining individual row constants and computing explicit dot products, avoiding nested matrix iteration.

### Current Implementation
```
const MDS = [
[7, 23, 8, 26, 13, 10, 9, 7, 6, 22, 21, 8],
[8, 7, 23, 8, 26, 13, 10, 9, 7, 6, 22, 21],
// ... 10 more rows
];

fn apply_mds(state: felt[12]) -> felt[12]{
return [sum([s * m for (s, m) in (state, mds_row)]) for mds_row in MDS];
}
```

This approach uses:
- A 2D matrix constant MDS
- Nested list comprehension iterating over matrix rows
- Matrix indexing to access individual rows

### Proposed Implementation

Define MDS rows as individual constants and compute dot products explicitly:
```
# MDS matrix rows used for computing the linear layer in a RPO round
const MDSROWA = [7, 23, 8, 26, 13, 10, 9, 7, 6, 22, 21, 8];
const MDSROWB = [8, 7, 23, 8, 26, 13, 10, 9, 7, 6, 22, 21];
const MDSROWC = [21, 8, 7, 23, 8, 26, 13, 10, 9, 7, 6, 22];
// ... 9 more rows (D through L)

fn apply_mds(state: felt[12]) -> felt[12]{
# Compute dot product of state vector with each MDS row
let result0 = sum([s * m for (s, m) in (state, MDSROWA)]);
let result1 = sum([s * m for (s, m) in (state, MDSROWB)]);
let result2 = sum([s * m for (s, m) in (state, MDSROWC)]);
// ... 9 more dot products

return [result0, result1, result2, result3, result4, result5,
result6, result7, result8, result9, result10, result11];
}
```

#505 shows the viability of this change.

Guide de contribution

Ouvrir le guide de contribution

Évaluation

Cette issue n'a pas encore été évaluée.

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.