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

ab_proof_of_space/
chiapos.rs
