binius_field/
tower.rs

1// Copyright 2024-2025 Irreducible Inc.
2
3//! Traits for working with field towers.
4
5use trait_set::trait_set;
6
7use crate::{
8	as_packed_field::PackScalar,
9	linear_transformation::{PackedTransformationFactory, Transformation},
10	polyval::{
11		AES_TO_POLYVAL_TRANSFORMATION, BINARY_TO_POLYVAL_TRANSFORMATION,
12		POLYVAL_TO_AES_TRANSFORMARION, POLYVAL_TO_BINARY_TRANSFORMATION,
13	},
14	underlier::UnderlierType,
15	AESTowerField128b, AESTowerField16b, AESTowerField32b, AESTowerField64b, AESTowerField8b,
16	BinaryField128b, BinaryField128bPolyval, BinaryField16b, BinaryField1b, BinaryField32b,
17	BinaryField64b, BinaryField8b, ExtensionField, PackedExtension, PackedField, TowerField,
18};
19
20/// A trait that groups a family of related [`TowerField`]s as associated types.
21pub trait TowerFamily: Sized {
22	type B1: TowerField + TryFrom<Self::B128>;
23	type B8: TowerField + TryFrom<Self::B128> + ExtensionField<Self::B1>;
24	type B16: TowerField + TryFrom<Self::B128> + ExtensionField<Self::B1> + ExtensionField<Self::B8>;
25	type B32: TowerField
26		+ TryFrom<Self::B128>
27		+ ExtensionField<Self::B1>
28		+ ExtensionField<Self::B8>
29		+ ExtensionField<Self::B16>;
30	type B64: TowerField
31		+ TryFrom<Self::B128>
32		+ ExtensionField<Self::B1>
33		+ ExtensionField<Self::B8>
34		+ ExtensionField<Self::B16>
35		+ ExtensionField<Self::B32>;
36	type B128: TowerField
37		+ ExtensionField<Self::B1>
38		+ ExtensionField<Self::B8>
39		+ ExtensionField<Self::B16>
40		+ ExtensionField<Self::B32>
41		+ ExtensionField<Self::B64>;
42}
43
44pub trait ProverTowerFamily: TowerFamily {
45	type FastB128: TowerField + From<Self::B128> + Into<Self::B128> + ExtensionField<Self::B1>;
46
47	fn packed_transformation_to_fast<Top, FastTop>() -> impl Transformation<Top, FastTop>
48	where
49		Top: PackedTop<Self> + PackedTransformationFactory<FastTop>,
50		FastTop: PackedField<Scalar = Self::FastB128>;
51
52	fn packed_transformation_from_fast<FastTop, Top>() -> impl Transformation<FastTop, Top>
53	where
54		FastTop: PackedTransformationFactory<Top>,
55		Top: PackedField<Scalar = Self::B128>;
56}
57
58/// The canonical Fan-Paar tower family.
59#[derive(Debug, Default)]
60pub struct CanonicalTowerFamily;
61
62impl TowerFamily for CanonicalTowerFamily {
63	type B1 = BinaryField1b;
64	type B8 = BinaryField8b;
65	type B16 = BinaryField16b;
66	type B32 = BinaryField32b;
67	type B64 = BinaryField64b;
68	type B128 = BinaryField128b;
69}
70
71impl ProverTowerFamily for CanonicalTowerFamily {
72	type FastB128 = BinaryField128bPolyval;
73
74	fn packed_transformation_to_fast<Top, FastTop>() -> impl Transformation<Top, FastTop>
75	where
76		Top: PackedTop<Self> + PackedTransformationFactory<FastTop>,
77		FastTop: PackedField<Scalar = Self::FastB128>,
78	{
79		Top::make_packed_transformation(BINARY_TO_POLYVAL_TRANSFORMATION)
80	}
81
82	fn packed_transformation_from_fast<FastTop, Top>() -> impl Transformation<FastTop, Top>
83	where
84		FastTop: PackedTransformationFactory<Top>,
85		Top: PackedField<Scalar = Self::B128>,
86	{
87		FastTop::make_packed_transformation(POLYVAL_TO_BINARY_TRANSFORMATION)
88	}
89}
90
91/// The tower defined by Fan-Paar extensions built on top of the Rijndael field.
92#[derive(Debug)]
93pub struct AESTowerFamily;
94
95impl TowerFamily for AESTowerFamily {
96	type B1 = BinaryField1b;
97	type B8 = AESTowerField8b;
98	type B16 = AESTowerField16b;
99	type B32 = AESTowerField32b;
100	type B64 = AESTowerField64b;
101	type B128 = AESTowerField128b;
102}
103
104impl ProverTowerFamily for AESTowerFamily {
105	type FastB128 = BinaryField128bPolyval;
106
107	fn packed_transformation_to_fast<Top, FastTop>() -> impl Transformation<Top, FastTop>
108	where
109		Top: PackedTop<Self> + PackedTransformationFactory<FastTop>,
110		FastTop: PackedField<Scalar = Self::FastB128>,
111	{
112		Top::make_packed_transformation(AES_TO_POLYVAL_TRANSFORMATION)
113	}
114
115	fn packed_transformation_from_fast<FastTop, Top>() -> impl Transformation<FastTop, Top>
116	where
117		FastTop: PackedTransformationFactory<Top>,
118		Top: PackedField<Scalar = Self::B128>,
119	{
120		FastTop::make_packed_transformation(POLYVAL_TO_AES_TRANSFORMARION)
121	}
122}
123
124trait_set! {
125	/// An underlier with associated packed types for fields in a tower.
126	pub trait TowerUnderlier<Tower: TowerFamily> =
127		UnderlierType
128		+ PackScalar<Tower::B1>
129		+ PackScalar<Tower::B8>
130		+ PackScalar<Tower::B16>
131		+ PackScalar<Tower::B32>
132		+ PackScalar<Tower::B64>
133		+ PackScalar<Tower::B128>;
134
135	pub trait ProverTowerUnderlier<Tower: ProverTowerFamily> =
136		TowerUnderlier<Tower> + PackScalar<Tower::FastB128>;
137
138	/// A packed field type that is the top packed field in a tower.
139	pub trait PackedTop<Tower: TowerFamily> =
140		PackedField<Scalar=Tower::B128>
141		+ PackedExtension<Tower::B1>
142		+ PackedExtension<Tower::B8>
143		+ PackedExtension<Tower::B16>
144		+ PackedExtension<Tower::B32>
145		+ PackedExtension<Tower::B64>
146		+ PackedExtension<Tower::B128>;
147}
binius_field/tower.rs

binius_field/
tower.rs
