1#[cfg(test)]
4mod tests;
5
6extern crate alloc;
7
8use alloc::collections::btree_map::Entry;
9use alloc::collections::BTreeMap;
10#[cfg(not(feature = "std"))]
11use alloc::string::{String, ToString};
12use alloc::sync::Arc;
13#[cfg(not(feature = "std"))]
14use alloc::vec::Vec;
15use core::mem;
16use derive_more::{AsMut, AsRef, Deref, DerefMut, From, Into};
17use kzg::eip_4844::{BYTES_PER_G1, BYTES_PER_G2};
18use kzg::{FFTFr, FFTSettings, Fr, KZGSettings, G1, G2};
19#[cfg(feature = "std")]
20use parking_lot::Mutex;
21use rust_kzg_blst::types::fft_settings::FsFFTSettings;
22use rust_kzg_blst::types::fr::FsFr;
23use rust_kzg_blst::types::g1::FsG1;
24use rust_kzg_blst::types::g2::FsG2;
25use rust_kzg_blst::types::kzg_settings::FsKZGSettings;
26use rust_kzg_blst::types::poly::FsPoly;
27#[cfg(not(feature = "std"))]
28use spin::Mutex;
29use static_assertions::const_assert_eq;
30use subspace_core_primitives::pieces::{RecordCommitment, RecordWitness};
31use subspace_core_primitives::segments::SegmentCommitment;
32use subspace_core_primitives::solutions::ChunkWitness;
33use subspace_core_primitives::ScalarBytes;
34use tracing::debug;
35
36pub const EMBEDDED_KZG_SETTINGS_BYTES: &[u8] = include_bytes!("eth-public-parameters.bin");
42pub const NUM_G1_POWERS: usize = 32_768;
44pub const NUM_G2_POWERS: usize = 65;
46
47fn bytes_to_kzg_settings(
51 bytes: &[u8],
52 num_g1_powers: usize,
53 num_g2_powers: usize,
54) -> Result<FsKZGSettings, String> {
55 if bytes.len() != BYTES_PER_G1 * num_g1_powers + BYTES_PER_G2 * num_g2_powers {
56 return Err("Invalid bytes length".to_string());
57 }
58
59 let (secret_g1_bytes, secret_g2_bytes) = bytes.split_at(BYTES_PER_G1 * num_g1_powers);
60 let secret_g1 = secret_g1_bytes
61 .chunks_exact(BYTES_PER_G1)
62 .map(FsG1::from_bytes)
63 .collect::<Result<Vec<_>, _>>()?;
64 let secret_g2 = secret_g2_bytes
65 .chunks_exact(BYTES_PER_G2)
66 .map(FsG2::from_bytes)
67 .collect::<Result<Vec<_>, _>>()?;
68
69 let fft_settings = FsFFTSettings::new(
70 num_g1_powers
71 .checked_sub(1)
72 .expect("Checked to be not empty above; qed")
73 .ilog2() as usize,
74 )
75 .expect("Scale is within allowed bounds; qed");
76
77 Ok(FsKZGSettings {
82 fs: fft_settings,
83 secret_g1,
84 secret_g2,
85 precomputation: None,
86 })
87}
88
89#[derive(Debug, Clone, From)]
91pub struct Polynomial(FsPoly);
92
93impl Polynomial {
94 pub fn normalize(&mut self) {
96 let trailing_zeroes = self
97 .0
98 .coeffs
99 .iter()
100 .rev()
101 .take_while(|coeff| coeff.is_zero())
102 .count();
103 self.0
104 .coeffs
105 .truncate((self.0.coeffs.len() - trailing_zeroes).max(1));
106 }
107}
108
109#[derive(Debug, Default, Copy, Clone, Eq, PartialEq, Deref, DerefMut)]
111#[repr(transparent)]
112pub struct Scalar(FsFr);
113
114const_assert_eq!(
115 mem::size_of::<Option<Scalar>>(),
116 mem::size_of::<Option<FsFr>>()
117);
118const_assert_eq!(
119 mem::align_of::<Option<Scalar>>(),
120 mem::align_of::<Option<FsFr>>()
121);
122
123impl From<&[u8; ScalarBytes::SAFE_BYTES]> for Scalar {
124 #[inline]
125 fn from(value: &[u8; ScalarBytes::SAFE_BYTES]) -> Self {
126 let mut bytes = [0u8; ScalarBytes::FULL_BYTES];
127 bytes[1..].copy_from_slice(value);
128 Self::try_from(bytes).expect("Safe bytes always fit into scalar and thus succeed; qed")
129 }
130}
131
132impl From<[u8; ScalarBytes::SAFE_BYTES]> for Scalar {
133 #[inline]
134 fn from(value: [u8; ScalarBytes::SAFE_BYTES]) -> Self {
135 Self::from(&value)
136 }
137}
138
139impl TryFrom<&[u8; ScalarBytes::FULL_BYTES]> for Scalar {
140 type Error = String;
141
142 #[inline]
143 fn try_from(value: &[u8; ScalarBytes::FULL_BYTES]) -> Result<Self, Self::Error> {
144 Self::try_from(*value)
145 }
146}
147
148impl TryFrom<[u8; ScalarBytes::FULL_BYTES]> for Scalar {
149 type Error = String;
150
151 #[inline]
152 fn try_from(value: [u8; ScalarBytes::FULL_BYTES]) -> Result<Self, Self::Error> {
153 FsFr::from_bytes(&value).map(Scalar)
154 }
155}
156
157impl TryFrom<&ScalarBytes> for Scalar {
158 type Error = String;
159
160 #[inline]
161 fn try_from(value: &ScalarBytes) -> Result<Self, Self::Error> {
162 FsFr::from_bytes(value.as_ref()).map(Scalar)
163 }
164}
165
166impl TryFrom<ScalarBytes> for Scalar {
167 type Error = String;
168
169 #[inline]
170 fn try_from(value: ScalarBytes) -> Result<Self, Self::Error> {
171 Self::try_from(&value)
172 }
173}
174
175impl From<&Scalar> for [u8; ScalarBytes::FULL_BYTES] {
176 #[inline]
177 fn from(value: &Scalar) -> Self {
178 value.0.to_bytes()
179 }
180}
181
182impl From<Scalar> for [u8; ScalarBytes::FULL_BYTES] {
183 #[inline]
184 fn from(value: Scalar) -> Self {
185 Self::from(&value)
186 }
187}
188
189impl From<&Scalar> for ScalarBytes {
190 #[inline]
191 fn from(value: &Scalar) -> Self {
192 ScalarBytes::from(value.0.to_bytes())
193 }
194}
195
196impl From<Scalar> for ScalarBytes {
197 #[inline]
198 fn from(value: Scalar) -> Self {
199 Self::from(&value)
200 }
201}
202
203impl Scalar {
204 pub fn to_bytes(&self) -> [u8; ScalarBytes::FULL_BYTES] {
206 self.into()
207 }
208
209 pub fn try_to_safe_bytes(&self) -> Option<[u8; ScalarBytes::SAFE_BYTES]> {
212 let bytes = self.to_bytes();
213 if bytes[0] == 0 {
214 Some(bytes[1..].try_into().expect("Correct length; qed"))
215 } else {
216 None
217 }
218 }
219
220 #[inline]
223 pub fn slice_to_repr(value: &[Self]) -> &[FsFr] {
224 unsafe { mem::transmute(value) }
226 }
227
228 #[inline]
231 pub fn slice_from_repr(value: &[FsFr]) -> &[Self] {
232 unsafe { mem::transmute(value) }
234 }
235
236 #[inline]
239 pub fn slice_option_to_repr(value: &[Option<Self>]) -> &[Option<FsFr>] {
240 unsafe { mem::transmute(value) }
244 }
245
246 #[inline]
249 pub fn slice_option_from_repr(value: &[Option<FsFr>]) -> &[Option<Self>] {
250 unsafe { mem::transmute(value) }
254 }
255
256 #[inline]
259 pub fn slice_mut_to_repr(value: &mut [Self]) -> &mut [FsFr] {
260 unsafe { mem::transmute(value) }
262 }
263
264 #[inline]
267 pub fn slice_mut_from_repr(value: &mut [FsFr]) -> &mut [Self] {
268 unsafe { mem::transmute(value) }
270 }
271
272 #[inline]
275 pub fn slice_option_mut_to_repr(value: &mut [Option<Self>]) -> &mut [Option<FsFr>] {
276 unsafe { mem::transmute(value) }
280 }
281
282 #[inline]
285 pub fn slice_option_mut_from_repr(value: &mut [Option<FsFr>]) -> &mut [Option<Self>] {
286 unsafe { mem::transmute(value) }
290 }
291
292 #[inline]
295 pub fn vec_to_repr(value: Vec<Self>) -> Vec<FsFr> {
296 unsafe {
299 let mut value = mem::ManuallyDrop::new(value);
300 Vec::from_raw_parts(
301 value.as_mut_ptr() as *mut FsFr,
302 value.len(),
303 value.capacity(),
304 )
305 }
306 }
307
308 #[inline]
311 pub fn vec_from_repr(value: Vec<FsFr>) -> Vec<Self> {
312 unsafe {
315 let mut value = mem::ManuallyDrop::new(value);
316 Vec::from_raw_parts(
317 value.as_mut_ptr() as *mut Self,
318 value.len(),
319 value.capacity(),
320 )
321 }
322 }
323
324 #[inline]
327 pub fn vec_option_to_repr(value: Vec<Option<Self>>) -> Vec<Option<FsFr>> {
328 unsafe {
332 let mut value = mem::ManuallyDrop::new(value);
333 Vec::from_raw_parts(
334 value.as_mut_ptr() as *mut Option<FsFr>,
335 value.len(),
336 value.capacity(),
337 )
338 }
339 }
340
341 #[inline]
344 pub fn vec_option_from_repr(value: Vec<Option<FsFr>>) -> Vec<Option<Self>> {
345 unsafe {
349 let mut value = mem::ManuallyDrop::new(value);
350 Vec::from_raw_parts(
351 value.as_mut_ptr() as *mut Option<Self>,
352 value.len(),
353 value.capacity(),
354 )
355 }
356 }
357}
358
359#[derive(Debug, Default, Copy, Clone, PartialEq, Eq, From, Into, AsRef, AsMut, Deref, DerefMut)]
361#[repr(transparent)]
362pub struct Commitment(FsG1);
363
364const_assert_eq!(
365 mem::size_of::<Option<Commitment>>(),
366 mem::size_of::<Option<FsG1>>()
367);
368const_assert_eq!(
369 mem::align_of::<Option<Commitment>>(),
370 mem::align_of::<Option<FsG1>>()
371);
372
373impl Commitment {
374 const SIZE: usize = 48;
376
377 #[inline]
379 pub fn to_bytes(&self) -> [u8; Self::SIZE] {
380 self.0.to_bytes()
381 }
382
383 #[inline]
385 pub fn try_from_bytes(bytes: &[u8; Self::SIZE]) -> Result<Self, String> {
386 Ok(Commitment(FsG1::from_bytes(bytes)?))
387 }
388
389 #[inline]
392 pub fn slice_to_repr(value: &[Self]) -> &[FsG1] {
393 unsafe { mem::transmute(value) }
396 }
397
398 #[inline]
401 pub fn slice_from_repr(value: &[FsG1]) -> &[Self] {
402 unsafe { mem::transmute(value) }
405 }
406
407 #[inline]
410 pub fn slice_option_to_repr(value: &[Option<Self>]) -> &[Option<FsG1>] {
411 unsafe { mem::transmute(value) }
415 }
416
417 #[inline]
420 pub fn slice_option_from_repr(value: &[Option<FsG1>]) -> &[Option<Self>] {
421 unsafe { mem::transmute(value) }
425 }
426
427 #[inline]
430 pub fn slice_mut_to_repr(value: &mut [Self]) -> &mut [FsG1] {
431 unsafe { mem::transmute(value) }
434 }
435
436 #[inline]
439 pub fn slice_mut_from_repr(value: &mut [FsG1]) -> &mut [Self] {
440 unsafe { mem::transmute(value) }
443 }
444
445 #[inline]
448 pub fn slice_option_mut_to_repr(value: &mut [Option<Self>]) -> &mut [Option<FsG1>] {
449 unsafe { mem::transmute(value) }
453 }
454
455 #[inline]
458 pub fn slice_option_mut_from_repr(value: &mut [Option<FsG1>]) -> &mut [Option<Self>] {
459 unsafe { mem::transmute(value) }
463 }
464
465 #[inline]
468 pub fn vec_to_repr(value: Vec<Self>) -> Vec<FsG1> {
469 unsafe {
472 let mut value = mem::ManuallyDrop::new(value);
473 Vec::from_raw_parts(
474 value.as_mut_ptr() as *mut FsG1,
475 value.len(),
476 value.capacity(),
477 )
478 }
479 }
480
481 #[inline]
484 pub fn vec_from_repr(value: Vec<FsG1>) -> Vec<Self> {
485 unsafe {
488 let mut value = mem::ManuallyDrop::new(value);
489 Vec::from_raw_parts(
490 value.as_mut_ptr() as *mut Self,
491 value.len(),
492 value.capacity(),
493 )
494 }
495 }
496
497 #[inline]
500 pub fn vec_option_to_repr(value: Vec<Option<Self>>) -> Vec<Option<FsG1>> {
501 unsafe {
505 let mut value = mem::ManuallyDrop::new(value);
506 Vec::from_raw_parts(
507 value.as_mut_ptr() as *mut Option<FsG1>,
508 value.len(),
509 value.capacity(),
510 )
511 }
512 }
513
514 #[inline]
517 pub fn vec_option_from_repr(value: Vec<Option<FsG1>>) -> Vec<Option<Self>> {
518 unsafe {
522 let mut value = mem::ManuallyDrop::new(value);
523 Vec::from_raw_parts(
524 value.as_mut_ptr() as *mut Option<Self>,
525 value.len(),
526 value.capacity(),
527 )
528 }
529 }
530}
531
532impl From<Commitment> for RecordCommitment {
533 #[inline]
534 fn from(commitment: Commitment) -> Self {
535 RecordCommitment::from(commitment.to_bytes())
536 }
537}
538
539impl TryFrom<&RecordCommitment> for Commitment {
540 type Error = String;
541
542 #[inline]
543 fn try_from(commitment: &RecordCommitment) -> Result<Self, Self::Error> {
544 Commitment::try_from(**commitment)
545 }
546}
547
548impl TryFrom<RecordCommitment> for Commitment {
549 type Error = String;
550
551 #[inline]
552 fn try_from(commitment: RecordCommitment) -> Result<Self, Self::Error> {
553 Commitment::try_from(&commitment)
554 }
555}
556
557impl From<Commitment> for SegmentCommitment {
558 #[inline]
559 fn from(commitment: Commitment) -> Self {
560 SegmentCommitment::from(commitment.to_bytes())
561 }
562}
563
564impl TryFrom<&SegmentCommitment> for Commitment {
565 type Error = String;
566
567 #[inline]
568 fn try_from(commitment: &SegmentCommitment) -> Result<Self, Self::Error> {
569 Commitment::try_from(**commitment)
570 }
571}
572
573impl TryFrom<SegmentCommitment> for Commitment {
574 type Error = String;
575
576 #[inline]
577 fn try_from(commitment: SegmentCommitment) -> Result<Self, Self::Error> {
578 Commitment::try_from(&commitment)
579 }
580}
581
582impl From<Commitment> for [u8; Commitment::SIZE] {
583 #[inline]
584 fn from(commitment: Commitment) -> Self {
585 commitment.to_bytes()
586 }
587}
588
589impl From<&Commitment> for [u8; Commitment::SIZE] {
590 #[inline]
591 fn from(commitment: &Commitment) -> Self {
592 commitment.to_bytes()
593 }
594}
595
596impl TryFrom<&[u8; Self::SIZE]> for Commitment {
597 type Error = String;
598
599 #[inline]
600 fn try_from(bytes: &[u8; Self::SIZE]) -> Result<Self, Self::Error> {
601 Self::try_from_bytes(bytes)
602 }
603}
604
605impl TryFrom<[u8; Self::SIZE]> for Commitment {
606 type Error = String;
607
608 #[inline]
609 fn try_from(bytes: [u8; Self::SIZE]) -> Result<Self, Self::Error> {
610 Self::try_from(&bytes)
611 }
612}
613
614#[derive(Debug, Default, Copy, Clone, PartialEq, Eq, From, Into, AsRef, AsMut, Deref, DerefMut)]
616#[repr(transparent)]
617pub struct Witness(FsG1);
618
619impl Witness {
620 const SIZE: usize = 48;
622
623 pub fn to_bytes(&self) -> [u8; Self::SIZE] {
625 self.0.to_bytes()
626 }
627
628 pub fn try_from_bytes(bytes: &[u8; Self::SIZE]) -> Result<Self, String> {
630 Ok(Witness(FsG1::from_bytes(bytes)?))
631 }
632}
633
634impl From<Witness> for RecordWitness {
635 #[inline]
636 fn from(witness: Witness) -> Self {
637 RecordWitness::from(witness.to_bytes())
638 }
639}
640
641impl TryFrom<&RecordWitness> for Witness {
642 type Error = String;
643
644 #[inline]
645 fn try_from(witness: &RecordWitness) -> Result<Self, Self::Error> {
646 Witness::try_from(**witness)
647 }
648}
649
650impl TryFrom<RecordWitness> for Witness {
651 type Error = String;
652
653 #[inline]
654 fn try_from(witness: RecordWitness) -> Result<Self, Self::Error> {
655 Witness::try_from(&witness)
656 }
657}
658
659impl From<Witness> for ChunkWitness {
660 #[inline]
661 fn from(witness: Witness) -> Self {
662 ChunkWitness::from(witness.to_bytes())
663 }
664}
665
666impl TryFrom<&ChunkWitness> for Witness {
667 type Error = String;
668
669 #[inline]
670 fn try_from(witness: &ChunkWitness) -> Result<Self, Self::Error> {
671 Witness::try_from(**witness)
672 }
673}
674
675impl TryFrom<ChunkWitness> for Witness {
676 type Error = String;
677
678 #[inline]
679 fn try_from(witness: ChunkWitness) -> Result<Self, Self::Error> {
680 Witness::try_from(&witness)
681 }
682}
683
684impl From<Witness> for [u8; Witness::SIZE] {
685 #[inline]
686 fn from(witness: Witness) -> Self {
687 witness.to_bytes()
688 }
689}
690
691impl From<&Witness> for [u8; Witness::SIZE] {
692 #[inline]
693 fn from(witness: &Witness) -> Self {
694 witness.to_bytes()
695 }
696}
697
698impl TryFrom<&[u8; Self::SIZE]> for Witness {
699 type Error = String;
700
701 #[inline]
702 fn try_from(bytes: &[u8; Self::SIZE]) -> Result<Self, Self::Error> {
703 Self::try_from_bytes(bytes)
704 }
705}
706
707impl TryFrom<[u8; Self::SIZE]> for Witness {
708 type Error = String;
709
710 #[inline]
711 fn try_from(bytes: [u8; Self::SIZE]) -> Result<Self, Self::Error> {
712 Self::try_from(&bytes)
713 }
714}
715
716#[derive(Debug)]
717struct Inner {
718 kzg_settings: FsKZGSettings,
719 fft_settings_cache: Mutex<BTreeMap<usize, Arc<FsFFTSettings>>>,
720}
721
722#[derive(Debug, Clone)]
724pub struct Kzg {
725 inner: Arc<Inner>,
726}
727
728impl Kzg {
729 #[expect(
733 clippy::new_without_default,
734 reason = "Default must not be implemented, because Kzg should be cloned instead. Cloning is cheap and instantiation is not."
735 )]
736 pub fn new() -> Self {
737 let kzg_settings =
738 bytes_to_kzg_settings(EMBEDDED_KZG_SETTINGS_BYTES, NUM_G1_POWERS, NUM_G2_POWERS)
739 .expect("Static bytes are correct, there is a test for this; qed");
740
741 let inner = Arc::new(Inner {
742 kzg_settings,
743 fft_settings_cache: Mutex::default(),
744 });
745
746 Self { inner }
747 }
748
749 pub fn poly(&self, data: &[Scalar]) -> Result<Polynomial, String> {
754 let poly = FsPoly {
755 coeffs: self
756 .get_fft_settings(data.len())?
757 .fft_fr(Scalar::slice_to_repr(data), true)?,
758 };
759 Ok(Polynomial(poly))
760 }
761
762 pub fn commit(&self, polynomial: &Polynomial) -> Result<Commitment, String> {
764 self.inner
765 .kzg_settings
766 .commit_to_poly(&polynomial.0)
767 .map(Commitment)
768 }
769
770 pub fn create_witness(
772 &self,
773 polynomial: &Polynomial,
774 num_values: usize,
775 index: u32,
776 ) -> Result<Witness, String> {
777 let x = self
778 .get_fft_settings(num_values)?
779 .get_expanded_roots_of_unity_at(index as usize);
780 self.inner
781 .kzg_settings
782 .compute_proof_single(&polynomial.0, &x)
783 .map(Witness)
784 }
785
786 pub fn verify(
789 &self,
790 commitment: &Commitment,
791 num_values: usize,
792 index: u32,
793 value: &Scalar,
794 witness: &Witness,
795 ) -> bool {
796 let fft_settings = match self.get_fft_settings(num_values) {
797 Ok(fft_settings) => fft_settings,
798 Err(error) => {
799 debug!(error, "Failed to derive fft settings");
800 return false;
801 }
802 };
803 let x = fft_settings.get_expanded_roots_of_unity_at(index as usize);
804
805 match self
806 .inner
807 .kzg_settings
808 .check_proof_single(&commitment.0, &witness.0, &x, value)
809 {
810 Ok(result) => result,
811 Err(error) => {
812 debug!(error, "Failed to check proof");
813 false
814 }
815 }
816 }
817
818 fn get_fft_settings(&self, num_values: usize) -> Result<Arc<FsFFTSettings>, String> {
821 let num_values = num_values.next_power_of_two();
822 Ok(
823 match self.inner.fft_settings_cache.lock().entry(num_values) {
824 Entry::Vacant(entry) => {
825 let fft_settings = Arc::new(FsFFTSettings::new(num_values.ilog2() as usize)?);
826 entry.insert(Arc::clone(&fft_settings));
827 fft_settings
828 }
829 Entry::Occupied(entry) => Arc::clone(entry.get()),
830 },
831 )
832 }
833}