chia_consensus/
build_compressed_block.rs

1use crate::consensus_constants::ConsensusConstants;
2use crate::error::Result;
3use chia_bls::Signature;
4use chia_protocol::SpendBundle;
5use clvmr::allocator::{Allocator, NodePtr};
6use clvmr::serde::{Serializer, node_from_bytes_backrefs};
7use std::borrow::Borrow;
8
9#[cfg(feature = "py-bindings")]
10use pyo3::prelude::*;
11#[cfg(feature = "py-bindings")]
12use pyo3::types::PyList;
13
14/// Maximum number of mempool items that can be skipped (not considered) during
15/// the creation of a block bundle. An item is skipped if it won't fit in the
16/// block we're trying to create.
17const MAX_SKIPPED_ITEMS: u32 = 6;
18
19/// Typical cost of a standard XCH spend. It's used as a heuristic to help
20/// determine how close to the block size limit we're willing to go.
21const MIN_COST_THRESHOLD: u64 = 6_000_000;
22
23/// Returned from add_spend_bundle(), indicating whether more bundles can be
24/// added or not.
25#[derive(PartialEq)]
26pub enum BuildBlockResult {
27    /// More spend bundles can be added
28    KeepGoing,
29    /// No more spend bundles can be added. We're too close to the limit
30    Done,
31}
32
33/// This takes a list of spends, highest priority first, and returns a
34/// block generator with as many spends as possible, that fit within the
35/// specified maximum block cost. The priority of spends is typically the
36/// fee-per-cost (higher is better). The cost of the generated block is computed
37/// incrementally, based on the (compressed) size in bytes, the execution cost
38/// and conditions cost of each spend. The compressed size is not trivially
39/// predicted. Spends are added to the generator, and compressed, one at a time
40/// until we reach the target cost limit.
41#[cfg_attr(feature = "py-bindings", pyclass)]
42pub struct BlockBuilder {
43    allocator: Allocator,
44    signature: Signature,
45    sentinel: NodePtr,
46
47    // the cost of the block we've built up so far, not including the byte-cost.
48    // That's seprated out into the byte_cost member.
49    block_cost: u64,
50
51    // the byte cost, so for, of what's in the Serializer
52    byte_cost: u64,
53
54    // the number of spend bundles we've failed to add. Once this grows too
55    // large, we give up
56    num_skipped: u32,
57
58    // the serializer for the generator CLVM
59    ser: Serializer,
60}
61
62fn result(num_skipped: u32) -> BuildBlockResult {
63    if num_skipped > MAX_SKIPPED_ITEMS {
64        BuildBlockResult::Done
65    } else {
66        BuildBlockResult::KeepGoing
67    }
68}
69
70impl BlockBuilder {
71    pub fn new() -> Result<Self> {
72        let mut a = Allocator::new();
73
74        // the sentinel just needs to be a unique NodePtr. Since atoms may be
75        // de-duplicated (for small integers), we create a pair.
76        let sentinel = a.new_pair(NodePtr::NIL, NodePtr::NIL)?;
77
78        // the generator we produce is just a quoted list. Nothing fancy.
79        // Its format is as follows:
80        // (q . ( ( ( parent-id puzzle-reveal amount solution ) ... ) ) )
81
82        // the list of spends is the first (and only) item in an outer list
83        let spend_list = a.new_pair(sentinel, a.nil())?;
84        let quoted_list = a.new_pair(a.one(), spend_list)?;
85
86        let mut ser = Serializer::new(Some(sentinel));
87        ser.add(&a, quoted_list)?;
88
89        Ok(Self {
90            allocator: a,
91            signature: Signature::default(),
92            sentinel,
93            // This is the cost of executing a quote. we quote the list of
94            // spends
95            block_cost: 20,
96            byte_cost: 0,
97            num_skipped: 0,
98            ser,
99        })
100    }
101
102    /// add a batch of spend bundles to the generator. The cost for each bundle
103    /// must be *only* the CLVM execution cost + the cost of the conditions.
104    /// It must not include the byte cost of the bundle. The byte cost is
105    /// unpredictible as the generator is being / compressed. The true byte cost
106    /// is computed by this function. / returns true if the bundles could be added
107    /// to the generator, false otherwise. Note that either all bundles are
108    /// added, or none of them. If the resulting block exceeds the cost limit,
109    /// none of the bundles are added
110    pub fn add_spend_bundles<T, S>(
111        &mut self,
112        bundles: T,
113        cost: u64,
114        constants: &ConsensusConstants,
115    ) -> Result<(bool, BuildBlockResult)>
116    where
117        T: IntoIterator<Item = S>,
118        S: Borrow<SpendBundle>,
119    {
120        // if we're very close to a full block, we're done. It's very unlikely
121        // any transaction will be smallar than MIN_COST_THRESHOLD
122        if self.byte_cost + self.block_cost + MIN_COST_THRESHOLD > constants.max_block_cost_clvm {
123            self.num_skipped += 1;
124            return Ok((false, BuildBlockResult::Done));
125        }
126
127        if self.byte_cost + self.block_cost + cost > constants.max_block_cost_clvm {
128            self.num_skipped += 1;
129            return Ok((false, result(self.num_skipped)));
130        }
131
132        let a = &mut self.allocator;
133
134        let mut spend_list = self.sentinel;
135        let mut cumulative_signature = Signature::default();
136        for bundle in bundles {
137            for spend in &bundle.borrow().coin_spends {
138                // solution
139                let solution = node_from_bytes_backrefs(a, spend.solution.as_ref())?;
140                let item = a.new_pair(solution, NodePtr::NIL)?;
141                // amount
142                let amount = a.new_number(spend.coin.amount.into())?;
143                let item = a.new_pair(amount, item)?;
144                // puzzle reveal
145                let puzzle = node_from_bytes_backrefs(a, spend.puzzle_reveal.as_ref())?;
146                let item = a.new_pair(puzzle, item)?;
147                // parent-id
148                let parent_id = a.new_atom(&spend.coin.parent_coin_info)?;
149                let item = a.new_pair(parent_id, item)?;
150
151                spend_list = a.new_pair(item, spend_list)?;
152            }
153            cumulative_signature.aggregate(&bundle.borrow().aggregated_signature);
154        }
155
156        let (done, state) = self.ser.add(a, spend_list)?;
157
158        // closing the lists at the end needs 2 extra bytes
159        self.byte_cost = (self.ser.size() + 2) * constants.cost_per_byte;
160        if self.byte_cost + self.block_cost + cost > constants.max_block_cost_clvm {
161            // Undo the last add() call.
162            // It might be tempting to reset the allocator as well, however,
163            // the incremental serializer will have already cached the tree we
164            // just added and it will remain cached when we restore the
165            // serializer state. It's more expensive to reset this cache, so we
166            // leave the Allocator untouched instead.
167            self.ser.restore(state);
168            self.byte_cost = (self.ser.size() + 2) * constants.cost_per_byte;
169            self.num_skipped += 1;
170            return Ok((false, result(self.num_skipped)));
171        }
172        self.block_cost += cost;
173        self.signature.aggregate(&cumulative_signature);
174
175        // if we're very close to a full block, we're done. It's very unlikely
176        // any transaction will be smallar than MIN_COST_THRESHOLD
177        let result = if done
178            || self.byte_cost + self.block_cost + MIN_COST_THRESHOLD > constants.max_block_cost_clvm
179        {
180            BuildBlockResult::Done
181        } else {
182            BuildBlockResult::KeepGoing
183        };
184        Ok((true, result))
185    }
186
187    pub fn cost(&self) -> u64 {
188        self.byte_cost + self.block_cost
189    }
190
191    // returns generator, sig, cost
192    pub fn finalize(mut self, constants: &ConsensusConstants) -> Result<(Vec<u8>, Signature, u64)> {
193        let (done, _) = self.ser.add(&self.allocator, self.allocator.nil())?;
194        assert!(done);
195
196        // add the size cost before returning it
197        self.block_cost += self.ser.size() * constants.cost_per_byte;
198
199        assert!(self.block_cost <= constants.max_block_cost_clvm);
200        Ok((self.ser.into_inner(), self.signature, self.block_cost))
201    }
202}
203
204#[cfg(feature = "py-bindings")]
205#[pymethods]
206impl BlockBuilder {
207    #[new]
208    pub fn py_new() -> PyResult<Self> {
209        Ok(Self::new()?)
210    }
211
212    /// the first bool indicates whether the bundles was added.
213    /// the second bool indicates whether we're done
214    #[pyo3(name = "add_spend_bundles")]
215    pub fn py_add_spend_bundle(
216        &mut self,
217        bundles: &Bound<'_, PyList>,
218        cost: u64,
219        constants: &ConsensusConstants,
220    ) -> PyResult<(bool, bool)> {
221        let (added, result) = self.add_spend_bundles(
222            bundles.iter().map(|item| {
223                // ideally, the failures in here would be reported back as python
224                // exceptions, but map() is infallible, so it's not so easy to
225                // propagate errors back
226                // TODO: It would be nice to not have to clone the SpendBundle
227                // here
228                item.extract::<Bound<'_, SpendBundle>>()
229                    .expect("spend bundle")
230                    .get()
231                    .clone()
232            }),
233            cost,
234            constants,
235        )?;
236        let done = matches!(result, BuildBlockResult::Done);
237        Ok((added, done))
238    }
239
240    #[pyo3(name = "cost")]
241    pub fn py_cost(&self) -> u64 {
242        self.cost()
243    }
244
245    /// generate the block generator
246    #[pyo3(name = "finalize")]
247    pub fn py_finalize(
248        &mut self,
249        constants: &ConsensusConstants,
250    ) -> PyResult<(Vec<u8>, Signature, u64)> {
251        let mut temp = BlockBuilder::new()?;
252        std::mem::swap(self, &mut temp);
253        let (generator, sig, cost) = temp.finalize(constants)?;
254        Ok((generator, sig, cost))
255    }
256}
257
258// this test is expensive and takes forever in debug builds
259#[cfg(not(debug_assertions))]
260#[cfg(test)]
261mod tests {
262    use super::*;
263    use crate::consensus_constants::TEST_CONSTANTS;
264    use crate::flags::ConsensusFlags;
265    use crate::flags::MEMPOOL_MODE;
266    use crate::owned_conditions::OwnedSpendBundleConditions;
267    use crate::run_block_generator::run_block_generator2;
268    use crate::solution_generator::calculate_generator_length;
269    use crate::spendbundle_conditions::run_spendbundle;
270    use chia_protocol::{Bytes, Coin};
271    use chia_traits::Streamable;
272    use rand::rngs::StdRng;
273    use rand::{SeedableRng, prelude::SliceRandom};
274    use std::collections::HashSet;
275    use std::fs;
276    use std::time::Instant;
277
278    #[test]
279    fn test_build_block() {
280        let mut all_bundles = vec![];
281        println!("loading spend bundles from disk");
282        let mut seen_spends = HashSet::new();
283        for entry in fs::read_dir("../../test-bundles").expect("listing test-bundles directory") {
284            let file = entry.expect("list dir").path();
285            if file.extension().map(|s| s.to_str()) != Some(Some("bundle")) {
286                continue;
287            }
288            // only use 32 byte hex encoded filenames
289            if file.file_stem().map(std::ffi::OsStr::len) != Some(64_usize) {
290                continue;
291            }
292            let buf = fs::read(file.clone()).expect("read bundle file");
293            let bundle = SpendBundle::from_bytes(buf.as_slice()).expect("parsing SpendBundle");
294
295            let mut a = Allocator::new();
296            let conds = run_spendbundle(
297                &mut a,
298                &bundle,
299                11_000_000_000,
300                ConsensusFlags::empty(),
301                &TEST_CONSTANTS,
302            )
303            .expect("run_spendbundle")
304            .0;
305
306            if conds
307                .spends
308                .iter()
309                .any(|s| seen_spends.contains(&*s.coin_id))
310            {
311                // We can't have conflicting spend bundles, since we combine
312                // them randomly. In this case two spend bundles spend the same
313                // coin
314                panic!(
315                    "conflict in {}",
316                    file.file_name().unwrap().to_str().unwrap()
317                );
318            }
319            if conds.spends.iter().any(|s| {
320                s.create_coin.iter().any(|c| {
321                    seen_spends.contains(&Coin::new(*s.coin_id, c.puzzle_hash, c.amount).coin_id())
322                })
323            }) {
324                // We can't have conflicting spend bundles, since we combine
325                // them randomly. In this case one spend bundle spends the coin
326                // created by another. This is probably OK in most cases, but
327                // not in the general case. We have restrictions on ephemeral
328                // spends (they cannot have relative time-lock conditions).
329                // Since the combination is random, we may end up with an
330                // invalid block.
331                panic!(
332                    "conflict in {}",
333                    file.file_name().unwrap().to_str().unwrap()
334                );
335            }
336            for spend in &conds.spends {
337                seen_spends.insert(*spend.coin_id);
338                for coin in &spend.create_coin {
339                    seen_spends
340                        .insert(Coin::new(*spend.coin_id, coin.puzzle_hash, coin.amount).coin_id());
341                }
342            }
343
344            // cost is supposed to not include byte-cost, so we have to subtract
345            // it here
346            let cost = conds.cost
347                - (calculate_generator_length(&bundle.coin_spends) as u64 - 2)
348                    * TEST_CONSTANTS.cost_per_byte;
349
350            let mut conds = OwnedSpendBundleConditions::from(&a, conds);
351            for s in &mut conds.spends {
352                // when running a block in consensus mode, we don't bother
353                // establishing whether a spend is eligible for dedup or not.
354                // So, to compare with the generator output later, we need to clear
355                // this field
356                s.flags = 0;
357                s.fingerprint = Bytes::default();
358                // when parsing conditions, create coin conditions are stored in
359                // a hash set to cheaply check for double spends. This means the
360                // order of this collection is not deterministic. In order to
361                // compare to the generator output later, we need to sort both.
362                s.create_coin.sort();
363            }
364            all_bundles.push(Box::new((bundle, cost, conds)));
365        }
366        all_bundles.sort_by_key(|x| x.1);
367        /*
368        let mut last_cost = 0;
369        for entry in &all_bundles {
370            let (cond, cost, _) = entry.as_ref();
371            if *cost != last_cost {
372                println!("\n== {cost}");
373                last_cost = *cost;
374            }
375            print!("{}.bundle ", cond.name());
376        }
377        println!("\n");
378        */
379        println!("loaded {} spend bundles", all_bundles.len());
380
381        let num_cores: usize = std::thread::available_parallelism().unwrap().into();
382        let pool = blocking_threadpool::Builder::new()
383            .num_threads(num_cores)
384            .queue_len(num_cores + 1)
385            .build();
386
387        for seed in 0..30 {
388            let mut bundles = all_bundles.clone();
389            let mut rng = StdRng::seed_from_u64(seed);
390            pool.execute(move || {
391                bundles.shuffle(&mut rng);
392
393                let start = Instant::now();
394                let mut builder = BlockBuilder::new().expect("BlockBuilder");
395                let mut skipped = 0;
396                let mut num_tx = 0;
397                let mut max_call_time = 0.0f32;
398                let mut spends = vec![];
399                for entry in &bundles {
400                    let (bundle, cost, conds) = entry.as_ref();
401                    let start_call = Instant::now();
402                    let (added, result) = builder
403                        .add_spend_bundles([bundle].into_iter(), *cost, &TEST_CONSTANTS)
404                        .expect("add_spend_bundle");
405
406                    max_call_time = f32::max(max_call_time, start_call.elapsed().as_secs_f32());
407                    if added {
408                        num_tx += 1;
409                        spends.extend(conds.spends.iter());
410                    } else {
411                        skipped += 1;
412                    }
413                    if result == BuildBlockResult::Done {
414                        break;
415                    }
416                }
417                let (generator, signature, cost) =
418                    builder.finalize(&TEST_CONSTANTS).expect("finalize()");
419
420                println!(
421                    "idx: {seed:3} built block in {:>5.2} seconds, cost: {cost:11} skipped: {skipped:2} longest-call: {max_call_time:>5.2}s TX: {num_tx}",
422                    start.elapsed().as_secs_f32()
423                );
424
425                //fs::write(format!("../../{seed}.generator"), generator.as_slice())
426                //    .expect("write generator");
427
428                let mut a = Allocator::new();
429                let conds = run_block_generator2::<&[u8], _>(
430                    &mut a,
431                    generator.as_slice(),
432                    [],
433                    TEST_CONSTANTS.max_block_cost_clvm,
434                    MEMPOOL_MODE,
435                    &signature,
436                    None,
437                    &TEST_CONSTANTS,
438                )
439                .expect("run_block_generator2");
440                assert_eq!(conds.cost, cost);
441                let mut conds = OwnedSpendBundleConditions::from(&a, conds);
442
443                assert_eq!(conds.spends.len(), spends.len());
444                conds.spends.sort_by_key(|s| s.coin_id);
445                spends.sort_by_key(|s| s.coin_id);
446                for (mut generator, tx) in conds.spends.into_iter().zip(spends) {
447                    generator.create_coin.sort();
448                    generator.flags = 0;
449                    generator.fingerprint = Bytes::default();
450                    assert_eq!(&generator, tx);
451                }
452            });
453            assert_eq!(pool.panic_count(), 0);
454        }
455        pool.join();
456        assert_eq!(pool.panic_count(), 0);
457    }
458}
chia_consensus/build_compressed_block.rs

chia_consensus/
build_compressed_block.rs
