ab_proof_of_space/
chiapos.rs

1//! Chia proof of space reimplementation in Rust
2
3mod constants;
4mod table;
5#[cfg(all(feature = "alloc", test))]
6mod tests;
7
8#[cfg(feature = "alloc")]
9use crate::PosProofs;
10use crate::chiapos::constants::NUM_TABLES;
11#[cfg(feature = "alloc")]
12pub use crate::chiapos::table::TablesCache;
13#[cfg(feature = "alloc")]
14use crate::chiapos::table::types::Position;
15use crate::chiapos::table::types::{Metadata, X, Y};
16#[cfg(feature = "alloc")]
17use crate::chiapos::table::{PrunedTable, Table};
18use crate::chiapos::table::{compute_f1, compute_fn, has_match};
19#[cfg(feature = "alloc")]
20use ab_core_primitives::pieces::Record;
21#[cfg(feature = "alloc")]
22use ab_core_primitives::pos::PosProof;
23#[cfg(feature = "alloc")]
24use ab_core_primitives::sectors::SBucket;
25#[cfg(feature = "alloc")]
26use alloc::boxed::Box;
27use core::array;
28use core::mem::MaybeUninit;
29#[cfg(feature = "alloc")]
30use core::mem::offset_of;
31#[cfg(any(feature = "full-chiapos", test))]
32use sha2::{Digest, Sha256};
33
34#[expect(clippy::inline_modules, reason = "Intentional tiny module inline")]
35mod private {
36    pub trait Supported {}
37}
38
39/// Size of the proof in bytes for a given `K` value
40pub const PROOF_SIZE<const K: u8>: usize =
41    2usize.pow(u32::from(NUM_TABLES - 1)) * usize::from(K) / u8::BITS as usize;
42
43/// Proof-of-space proofs
44#[derive(Debug)]
45#[cfg(feature = "alloc")]
46#[repr(C)]
47pub struct Proofs<const K: u8> {
48    /// S-buckets at which proofs were found.
49    ///
50    /// S-buckets are grouped by 8, within each `u8` bits right to left (LSB) indicate the presence
51    /// of a proof for corresponding s-bucket, so that the whole array of bytes can be thought as a
52    /// large set of bits.
53    ///
54    /// There will be at most [`Record::NUM_CHUNKS`] proofs produced/bits set to `1`.
55    pub found_proofs: [u8; Record::NUM_S_BUCKETS / u8::BITS as usize],
56    /// [`Record::NUM_CHUNKS`] proofs, corresponding to set bits of `found_proofs`.
57    pub proofs: [[u8; PROOF_SIZE::<K>]; const { Record::NUM_CHUNKS }],
58}
59
60#[cfg(feature = "alloc")]
61impl From<Box<Proofs<const { PosProof::K }>>> for Box<PosProofs> {
62    fn from(proofs: Box<Proofs<const { PosProof::K }>>) -> Self {
63        // Statically ensure types are the same
64        const {
65            // TODO: Latest nightly can't understand `{ PosProof::K }` for some reason, hence a
66            //  separate assert
67            assert!(PosProof::K == 20);
68            assert!(size_of::<Proofs<20>>() == size_of::<PosProofs>());
69            assert!(align_of::<Proofs<20>>() == align_of::<PosProofs>());
70            assert!(offset_of!(Proofs<20>, found_proofs) == offset_of!(PosProofs, found_proofs));
71            assert!(offset_of!(Proofs<20>, proofs) == offset_of!(PosProofs, proofs));
72        }
73        // SAFETY: Both structs have an identical layout with `#[repr(C)]` internals
74        unsafe { Box::from_raw(Box::into_raw(proofs).cast()) }
75    }
76}
77
78#[cfg(feature = "alloc")]
79impl<const K: u8> Proofs<K> {
80    /// Get proof for specified s-bucket (if exists).
81    ///
82    /// Note that this is not the most efficient API possible, so prefer using the `proofs` field
83    /// directly if the use case allows.
84    #[inline]
85    pub fn for_s_bucket(&self, s_bucket: SBucket) -> Option<[u8; PROOF_SIZE::<K>]> {
86        let proof_index = PosProofs::proof_index_for_s_bucket(&self.found_proofs, s_bucket)?;
87
88        Some(self.proofs[proof_index])
89    }
90}
91
92type Seed = [u8; 32];
93#[cfg(any(feature = "full-chiapos", test))]
94type Challenge = [u8; 32];
95#[cfg(any(feature = "full-chiapos", test))]
96type Quality = [u8; 32];
97
98/// Pick position in `table_number` based on challenge bits
99#[cfg(all(feature = "alloc", any(feature = "full-chiapos", test)))]
100const fn pick_position(
101    [left_position, right_position]: [Position; 2],
102    last_5_challenge_bits: u8,
103    table_number: u8,
104) -> Position {
105    if ((last_5_challenge_bits >> (table_number - 2)) & 1) == 0 {
106        left_position
107    } else {
108        right_position
109    }
110}
111
112/// Collection of Chia tables
113#[derive(Debug)]
114pub struct Tables<const K: u8>
115where
116    Self: private::Supported,
117{
118    #[cfg(feature = "alloc")]
119    table_2: PrunedTable<K, 2>,
120    #[cfg(feature = "alloc")]
121    table_3: PrunedTable<K, 3>,
122    #[cfg(feature = "alloc")]
123    table_4: PrunedTable<K, 4>,
124    #[cfg(feature = "alloc")]
125    table_5: PrunedTable<K, 5>,
126    #[cfg(feature = "alloc")]
127    table_6: PrunedTable<K, 6>,
128    #[cfg(feature = "alloc")]
129    table_7: Table<K, 7>,
130}
131
132impl<const K: u8> Tables<K>
133where
134    Self: private::Supported,
135{
136    /// Create Chia proof of space tables.
137    ///
138    /// There is also `Self::create_parallel()` that can achieve higher performance and lower
139    /// latency at the cost of lower CPU efficiency and higher memory usage.
140    #[cfg(all(feature = "alloc", any(feature = "full-chiapos", test)))]
141    pub fn create(seed: Seed, cache: &TablesCache) -> Self {
142        let table_1 = Table::<K, 1>::create(seed);
143        let (table_2, _) = Table::<K, 2>::create(table_1, cache);
144        let (table_3, table_2) = Table::<K, 3>::create(table_2, cache);
145        let (table_4, table_3) = Table::<K, 4>::create(table_3, cache);
146        let (table_5, table_4) = Table::<K, 5>::create(table_4, cache);
147        let (table_6, table_5) = Table::<K, 6>::create(table_5, cache);
148        let (table_7, table_6) = Table::<K, 7>::create(table_6, cache);
149
150        Self {
151            table_2,
152            table_3,
153            table_4,
154            table_5,
155            table_6,
156            table_7,
157        }
158    }
159
160    /// Create proofs.
161    ///
162    /// This is an optimized combination of `Self::create()` and `Self::find_proof()`.
163    ///
164    /// There is also `Self::create_proofs_parallel()` that can achieve higher performance and lower
165    /// latency at the cost of lower CPU efficiency and higher memory usage.
166    #[cfg(feature = "alloc")]
167    pub fn create_proofs(seed: Seed, cache: &TablesCache) -> Box<Proofs<K>> {
168        let table_1 = Table::<K, 1>::create(seed);
169        let (table_2, _) = Table::<K, 2>::create(table_1, cache);
170        let (table_3, table_2) = Table::<K, 3>::create(table_2, cache);
171        let (table_4, table_3) = Table::<K, 4>::create(table_3, cache);
172        let (table_5, table_4) = Table::<K, 5>::create(table_4, cache);
173        let (table_6, table_5) = Table::<K, 6>::create(table_5, cache);
174        let (table_6_proof_targets, table_6) = Table::<K, 7>::create_proof_targets(table_6, cache);
175
176        // TODO: Rewrite this more efficiently
177        let mut proofs = Box::<Proofs<K>>::new_uninit();
178        {
179            let proofs_ptr = proofs.as_mut().as_mut_ptr();
180            // SAFETY: This is the correct way to access uninit reference to the inner field
181            let found_proofs = unsafe {
182                (&raw mut (*proofs_ptr).found_proofs)
183                    .as_uninit_mut()
184                    .expect("Not null; qed")
185            };
186            let found_proofs = found_proofs.write([0; _]);
187            // SAFETY: This is the correct way to access uninit reference to the inner field
188            let proofs = unsafe {
189                (&raw mut (*proofs_ptr).proofs)
190                    .cast::<[MaybeUninit<_>; const { Record::NUM_CHUNKS }]>()
191                    .as_mut_unchecked()
192            };
193
194            let mut num_found_proofs = 0_usize;
195            'outer: for (table_6_proof_targets, found_proofs) in table_6_proof_targets
196                .as_chunks::<{ u8::BITS as usize }>()
197                .0
198                .iter()
199                .zip(found_proofs)
200            {
201                // TODO: Find proofs with SIMD
202                for (proof_offset, table_6_proof_targets) in
203                    table_6_proof_targets.iter().enumerate()
204                {
205                    if table_6_proof_targets != &[Position::ZERO; 2] {
206                        let proof = Self::find_proof_raw_internal(
207                            &table_2,
208                            &table_3,
209                            &table_4,
210                            &table_5,
211                            &table_6,
212                            *table_6_proof_targets,
213                        );
214
215                        *found_proofs |= 1 << proof_offset;
216
217                        proofs[num_found_proofs].write(proof);
218                        num_found_proofs += 1;
219
220                        if num_found_proofs == Record::NUM_CHUNKS {
221                            break 'outer;
222                        }
223                    }
224                }
225            }
226
227            // It is statically known to be the case, and there is a test that checks the lower
228            // bound
229            debug_assert_eq!(num_found_proofs, Record::NUM_CHUNKS);
230        }
231
232        // SAFETY: Fully initialized above
233        unsafe { proofs.assume_init() }
234    }
235
236    /// Almost the same as [`Self::create()`], but uses parallelism internally for better
237    /// performance and lower latency at the cost of lower CPU efficiency and higher memory usage
238    #[cfg(all(feature = "parallel", any(feature = "full-chiapos", test)))]
239    pub fn create_parallel(seed: Seed, cache: &TablesCache) -> Self {
240        let table_1 = Table::<K, 1>::create_parallel(seed);
241        let (table_2, _) = Table::<K, 2>::create_parallel(table_1, cache);
242        let (table_3, table_2) = Table::<K, 3>::create_parallel(table_2, cache);
243        let (table_4, table_3) = Table::<K, 4>::create_parallel(table_3, cache);
244        let (table_5, table_4) = Table::<K, 5>::create_parallel(table_4, cache);
245        let (table_6, table_5) = Table::<K, 6>::create_parallel(table_5, cache);
246        let (table_7, table_6) = Table::<K, 7>::create_parallel(table_6, cache);
247
248        Self {
249            table_2,
250            table_3,
251            table_4,
252            table_5,
253            table_6,
254            table_7,
255        }
256    }
257
258    /// Almost the same as [`Self::create_proofs()`], but uses parallelism internally for better
259    /// performance and lower latency at the cost of lower CPU efficiency and higher memory usage
260    #[cfg(feature = "parallel")]
261    pub fn create_proofs_parallel(seed: Seed, cache: &TablesCache) -> Box<Proofs<K>> {
262        let table_1 = Table::<K, 1>::create_parallel(seed);
263        let (table_2, _) = Table::<K, 2>::create_parallel(table_1, cache);
264        let (table_3, table_2) = Table::<K, 3>::create_parallel(table_2, cache);
265        let (table_4, table_3) = Table::<K, 4>::create_parallel(table_3, cache);
266        let (table_5, table_4) = Table::<K, 5>::create_parallel(table_4, cache);
267        let (table_6, table_5) = Table::<K, 6>::create_parallel(table_5, cache);
268        let (table_6_proof_targets, table_6) =
269            Table::<K, 7>::create_proof_targets_parallel(table_6, cache);
270
271        // TODO: Rewrite this more efficiently
272        let mut proofs = Box::<Proofs<K>>::new_uninit();
273        {
274            let proofs_ptr = proofs.as_mut().as_mut_ptr();
275            // SAFETY: This is the correct way to access uninit reference to the inner field
276            let found_proofs = unsafe {
277                (&raw mut (*proofs_ptr).found_proofs)
278                    .as_uninit_mut()
279                    .expect("Not null; qed")
280            };
281            let found_proofs = found_proofs.write([0; _]);
282            // SAFETY: This is the correct way to access uninit reference to the inner field
283            let proofs = unsafe {
284                (&raw mut (*proofs_ptr).proofs)
285                    .cast::<[MaybeUninit<_>; const { Record::NUM_CHUNKS }]>()
286                    .as_mut_unchecked()
287            };
288
289            let mut num_found_proofs = 0_usize;
290            'outer: for (table_6_proof_targets, found_proofs) in table_6_proof_targets
291                .as_chunks::<{ u8::BITS as usize }>()
292                .0
293                .iter()
294                .zip(found_proofs)
295            {
296                // TODO: Find proofs with SIMD
297                for (proof_offset, table_6_proof_targets) in
298                    table_6_proof_targets.iter().enumerate()
299                {
300                    if table_6_proof_targets != &[Position::ZERO; 2] {
301                        let proof = Self::find_proof_raw_internal(
302                            &table_2,
303                            &table_3,
304                            &table_4,
305                            &table_5,
306                            &table_6,
307                            *table_6_proof_targets,
308                        );
309
310                        *found_proofs |= 1 << proof_offset;
311
312                        proofs[num_found_proofs].write(proof);
313                        num_found_proofs += 1;
314
315                        if num_found_proofs == Record::NUM_CHUNKS {
316                            break 'outer;
317                        }
318                    }
319                }
320            }
321
322            // It is statically known to be the case, and there is a test that checks the lower
323            // bound
324            debug_assert_eq!(num_found_proofs, Record::NUM_CHUNKS);
325        }
326
327        // SAFETY: Fully initialized above
328        unsafe { proofs.assume_init() }
329    }
330
331    /// Find proof of space quality for a given challenge
332    #[cfg(all(feature = "alloc", any(feature = "full-chiapos", test)))]
333    pub fn find_quality<'a>(
334        &'a self,
335        challenge: &'a Challenge,
336    ) -> impl Iterator<Item = Quality> + 'a {
337        let last_5_challenge_bits = challenge[challenge.len() - 1] & 0b0001_1111;
338
339        let first_k_challenge_bits = u32::from_be_bytes(
340            challenge[..size_of::<u32>()]
341                .try_into()
342                .expect("Challenge is known to statically have enough bytes; qed"),
343        ) >> (u32::BITS as usize - usize::from(K));
344
345        // Iterate just over elements that are matching `first_k_challenge_bits` prefix
346        self.table_7.buckets()[Y::bucket_range_from_first_k_bits(first_k_challenge_bits)]
347            .iter()
348            .flat_map(move |positions| {
349                positions
350                    .iter()
351                    .take_while(|&&(position, _y)| position != Position::SENTINEL)
352                    .filter(move |&&(_position, y)| y.first_k_bits() == first_k_challenge_bits)
353            })
354            .map(move |&(position, _y)| {
355                // SAFETY: Internally generated positions that come from the parent table
356                let positions = unsafe { self.table_7.position(position) };
357                // SAFETY: Internally generated positions that come from the parent table
358                let positions = unsafe {
359                    self.table_6
360                        .position(pick_position(positions, last_5_challenge_bits, 6))
361                };
362                // SAFETY: Internally generated positions that come from the parent table
363                let positions = unsafe {
364                    self.table_5
365                        .position(pick_position(positions, last_5_challenge_bits, 5))
366                };
367                // SAFETY: Internally generated positions that come from the parent table
368                let positions = unsafe {
369                    self.table_4
370                        .position(pick_position(positions, last_5_challenge_bits, 4))
371                };
372                // SAFETY: Internally generated positions that come from the parent table
373                let positions = unsafe {
374                    self.table_3
375                        .position(pick_position(positions, last_5_challenge_bits, 3))
376                };
377                // SAFETY: Internally generated positions that come from the parent table
378                let [left_position, right_position] = unsafe {
379                    self.table_2
380                        .position(pick_position(positions, last_5_challenge_bits, 2))
381                };
382
383                // X matches position
384                let left_x = X::from(u32::from(left_position));
385                let right_x = X::from(u32::from(right_position));
386
387                let mut hasher = Sha256::new();
388                hasher.update(challenge);
389                let left_right_xs = (u64::from(left_x) << (u64::BITS as usize - usize::from(K)))
390                    | (u64::from(right_x) << (u64::BITS as usize - usize::from(K * 2)));
391                hasher.update(
392                    &left_right_xs.to_be_bytes()
393                        [..(usize::from(K) * 2).div_ceil(u8::BITS as usize)],
394                );
395                hasher.finalize().into()
396            })
397    }
398
399    /// Similar to `Self::find_proof()`, but takes the first `k` challenge bits in the least
400    /// significant bits of `u32` as a challenge instead
401    #[cfg(feature = "alloc")]
402    pub fn find_proof_raw(
403        &self,
404        first_k_challenge_bits: u32,
405    ) -> impl Iterator<Item = [u8; PROOF_SIZE::<K>]> + '_ {
406        // Iterate just over elements that are matching `first_k_challenge_bits` prefix
407        self.table_7.buckets()[Y::bucket_range_from_first_k_bits(first_k_challenge_bits)]
408            .iter()
409            .flat_map(move |positions| {
410                positions
411                    .iter()
412                    .take_while(|&&(position, _y)| position != Position::SENTINEL)
413                    .filter(move |&&(_position, y)| y.first_k_bits() == first_k_challenge_bits)
414            })
415            .map(move |&(position, _y)| {
416                // SAFETY: Internally generated positions that come from the parent table
417                let table_6_proof_targets = unsafe { self.table_7.position(position) };
418
419                Self::find_proof_raw_internal(
420                    &self.table_2,
421                    &self.table_3,
422                    &self.table_4,
423                    &self.table_5,
424                    &self.table_6,
425                    table_6_proof_targets,
426                )
427            })
428    }
429
430    #[cfg(feature = "alloc")]
431    #[inline(always)]
432    fn find_proof_raw_internal(
433        table_2: &PrunedTable<K, 2>,
434        table_3: &PrunedTable<K, 3>,
435        table_4: &PrunedTable<K, 4>,
436        table_5: &PrunedTable<K, 5>,
437        table_6: &PrunedTable<K, 6>,
438        table_6_proof_targets: [Position; 2],
439    ) -> [u8; PROOF_SIZE::<K>] {
440        let mut proof = [0u8; _];
441
442        // TODO: Optimize with SIMD
443        table_6_proof_targets
444            .into_iter()
445            .flat_map(|position| {
446                // SAFETY: Internally generated positions that come from the parent table
447                unsafe { table_6.position(position) }
448            })
449            .flat_map(|position| {
450                // SAFETY: Internally generated positions that come from the parent table
451                unsafe { table_5.position(position) }
452            })
453            .flat_map(|position| {
454                // SAFETY: Internally generated positions that come from the parent table
455                unsafe { table_4.position(position) }
456            })
457            .flat_map(|position| {
458                // SAFETY: Internally generated positions that come from the parent table
459                unsafe { table_3.position(position) }
460            })
461            .flat_map(|position| {
462                // SAFETY: Internally generated positions that come from the parent table
463                unsafe { table_2.position(position) }
464            })
465            .map(|position| {
466                // X matches position
467                X::from(u32::from(position))
468            })
469            .enumerate()
470            .for_each(|(offset, x)| {
471                let x_offset_in_bits = usize::from(K) * offset;
472                // Collect bytes where bits of `x` will be written
473                let proof_bytes = &mut proof[x_offset_in_bits / u8::BITS as usize..]
474                    [..(x_offset_in_bits % u8::BITS as usize + usize::from(K))
475                        .div_ceil(u8::BITS as usize)];
476
477                // Bits of `x` already shifted to the correct location as they will appear
478                // in `proof`
479                let x_shifted = u32::from(x)
480                    << (u32::BITS as usize
481                        - (usize::from(K) + x_offset_in_bits % u8::BITS as usize));
482
483                // TODO: Store proofs in words, like GPU version does
484                // Copy `x` bits into proof
485                x_shifted
486                    .to_be_bytes()
487                    .iter()
488                    .zip(proof_bytes)
489                    .for_each(|(from, to)| {
490                        *to |= from;
491                    });
492            });
493
494        proof
495    }
496
497    /// Find proof of space for a given challenge
498    #[cfg(all(feature = "alloc", any(feature = "full-chiapos", test)))]
499    pub fn find_proof(
500        &self,
501        first_challenge_bytes: [u8; 4],
502    ) -> impl Iterator<Item = [u8; PROOF_SIZE::<K>]> + '_ {
503        let first_k_challenge_bits =
504            u32::from_be_bytes(first_challenge_bytes) >> (u32::BITS as usize - usize::from(K));
505
506        self.find_proof_raw(first_k_challenge_bits)
507    }
508
509    /// Similar to `Self::verify()`, but takes the first `k` challenge bits in the least significant
510    /// bits of `u32` as a challenge instead and doesn't compute quality
511    pub fn verify_only_raw(
512        seed: &Seed,
513        first_k_challenge_bits: u32,
514        proof_of_space: &[u8; PROOF_SIZE::<K>],
515    ) -> bool {
516        let ys_and_metadata = array::from_fn::<_, 64, _>(|offset| {
517            let mut pre_x_bytes = 0u64.to_be_bytes();
518            let offset_in_bits = usize::from(K) * offset;
519            let bytes_to_copy =
520                (offset_in_bits % u8::BITS as usize + usize::from(K)).div_ceil(u8::BITS as usize);
521            // Copy full bytes that contain bits of `x`
522            pre_x_bytes[..bytes_to_copy].copy_from_slice(
523                &proof_of_space[offset_in_bits / u8::BITS as usize..][..bytes_to_copy],
524            );
525            // Extract `pre_x` whose last `K` bits start with `x`
526            let pre_x = u64::from_be_bytes(pre_x_bytes)
527                >> (u64::BITS as usize - (usize::from(K) + offset_in_bits % u8::BITS as usize));
528            // Convert to the desired type and clear extra bits
529            let x = X::from(pre_x as u32 & (u32::MAX >> (u32::BITS as usize - usize::from(K))));
530
531            let y = compute_f1::<K>(x, seed);
532
533            (y, Metadata::from(x))
534        });
535
536        let mut next_ys_and_metadata = [MaybeUninit::uninit(); _];
537        let ys_and_metadata =
538            Self::collect_ys_and_metadata::<2, 1, 64>(&ys_and_metadata, &mut next_ys_and_metadata);
539        let mut next_ys_and_metadata = [MaybeUninit::uninit(); _];
540        let ys_and_metadata =
541            Self::collect_ys_and_metadata::<3, 2, 32>(ys_and_metadata, &mut next_ys_and_metadata);
542        let mut next_ys_and_metadata = [MaybeUninit::uninit(); _];
543        let ys_and_metadata =
544            Self::collect_ys_and_metadata::<4, 3, 16>(ys_and_metadata, &mut next_ys_and_metadata);
545        let mut next_ys_and_metadata = [MaybeUninit::uninit(); _];
546        let ys_and_metadata =
547            Self::collect_ys_and_metadata::<5, 4, 8>(ys_and_metadata, &mut next_ys_and_metadata);
548        let mut next_ys_and_metadata = [MaybeUninit::uninit(); _];
549        let ys_and_metadata =
550            Self::collect_ys_and_metadata::<6, 5, 4>(ys_and_metadata, &mut next_ys_and_metadata);
551        let mut next_ys_and_metadata = [MaybeUninit::uninit(); _];
552        let ys_and_metadata =
553            Self::collect_ys_and_metadata::<7, 6, 2>(ys_and_metadata, &mut next_ys_and_metadata);
554
555        let Some((y, _metadata)) = ys_and_metadata.first() else {
556            return false;
557        };
558
559        // Check if the first K bits of `y` match
560        y.first_k_bits() == first_k_challenge_bits
561    }
562
563    /// Verify proof of space for a given seed and challenge
564    #[cfg(any(feature = "full-chiapos", test))]
565    pub fn verify(
566        seed: &Seed,
567        challenge: &Challenge,
568        proof_of_space: &[u8; PROOF_SIZE::<K>],
569    ) -> Option<Quality> {
570        let first_k_challenge_bits =
571            u32::from_be_bytes([challenge[0], challenge[1], challenge[2], challenge[3]])
572                >> (u32::BITS as usize - usize::from(K));
573
574        if !Self::verify_only_raw(seed, first_k_challenge_bits, proof_of_space) {
575            return None;
576        }
577
578        let last_5_challenge_bits = challenge[challenge.len() - 1] & 0b0001_1111;
579
580        let mut quality_index = 0_usize.to_be_bytes();
581        quality_index[0] = last_5_challenge_bits;
582        let quality_index = usize::from_be_bytes(quality_index);
583
584        // NOTE: this works correctly but may overflow if `quality_index` is changed to
585        // not be zero-initialized anymore
586        let left_right_xs_bit_offset = quality_index * usize::from(K * 2);
587        // Collect `left_x` and `right_x` bits, potentially with extra bits at the beginning
588        // and the end
589        let left_right_xs_bytes = &proof_of_space[left_right_xs_bit_offset / u8::BITS as usize..]
590            [..(left_right_xs_bit_offset % u8::BITS as usize + usize::from(K * 2))
591                .div_ceil(u8::BITS as usize)];
592
593        let mut left_right_xs = 0u64.to_be_bytes();
594        left_right_xs[..left_right_xs_bytes.len()].copy_from_slice(left_right_xs_bytes);
595        // Move `left_x` and `right_x` bits to most significant bits
596        let left_right_xs =
597            u64::from_be_bytes(left_right_xs) << (left_right_xs_bit_offset % u8::BITS as usize);
598        // Clear extra bits
599        let left_right_xs_mask = u64::MAX << (u64::BITS as usize - usize::from(K * 2));
600        let left_right_xs = left_right_xs & left_right_xs_mask;
601
602        let mut hasher = Sha256::new();
603        hasher.update(challenge);
604        hasher
605            .update(&left_right_xs.to_be_bytes()[..usize::from(K * 2).div_ceil(u8::BITS as usize)]);
606        Some(hasher.finalize().into())
607    }
608
609    fn collect_ys_and_metadata<
610        'a,
611        const TABLE_NUMBER: u8,
612        const PARENT_TABLE_NUMBER: u8,
613        const N: usize,
614    >(
615        ys_and_metadata: &[(Y, Metadata<K, PARENT_TABLE_NUMBER>)],
616        next_ys_and_metadata: &'a mut [MaybeUninit<(Y, Metadata<K, TABLE_NUMBER>)>; N],
617    ) -> &'a [(Y, Metadata<K, TABLE_NUMBER>)] {
618        let mut next_offset = 0_usize;
619        for &[(left_y, left_metadata), (right_y, right_metadata)] in
620            ys_and_metadata.as_chunks::<2>().0
621        {
622            if !has_match(left_y, right_y) {
623                continue;
624            }
625
626            next_ys_and_metadata[next_offset].write(compute_fn::<
627                K,
628                TABLE_NUMBER,
629                PARENT_TABLE_NUMBER,
630            >(
631                left_y, left_metadata, right_metadata
632            ));
633            next_offset += 1;
634        }
635
636        // SAFETY: Initialized `next_offset` elements
637        unsafe { next_ys_and_metadata[..next_offset].assume_init_ref() }
638    }
639}
640
641macro_rules! impl_supported {
642    ($($k: expr$(,)? )*) => {
643        $(
644impl private::Supported for Tables<$k> {}
645        )*
646    }
647}
648
649// Only these k values are supported by the current implementation
650#[cfg(feature = "full-chiapos")]
651impl_supported!(15, 16, 18, 19, 21, 22, 23, 24, 25);
652#[cfg(any(feature = "full-chiapos", test))]
653impl_supported!(17);
654impl_supported!(20);
ab_proof_of_space/chiapos.rs

ab_proof_of_space/
chiapos.rs
